THE EFFECT OF ADVERSARIAL TRAINING: A THEORETICAL CHARACTERIZATION
Authors: Mingyang Yi
Huishuai Zhang
Wei Chen
Zhi-Ming Ma
Tie-Yan Liu
Venue:  (2020)
Keywords: adversarial training
robustness
separable data

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.

Under review as a conference paper at ICLR 2020
THE EFFECT OF ADVERSARIAL TRAINING: A THEO- RETICAL CHARACTERIZATION
Anonymous authors Paper under double-blind review
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 stan- dard training is limited. In this paper, we characterize the solution of adversarial training for linear classification problem for full range of adversarial radius Specifically, we show that if the data themselves are "E-strongly linearly separa- ble", adversarial training with radius smaller than converges to the hard margin solution of SVM with a faster rate than standard training. the data themselves are not "s-ssrongly linearly separable", we show that adversarial training with ra- dius & is stable to outliers while standard training is not. Moreover, we prove that the classifier returned by adversarial training with large radius has low confi- dence in each data point. Experiments corroborate our theoretical finding well.
INTRODUCTION
Despite the impressive performance of deep neural networks on various learning tasks, the widely existing adversarial examples (Goodfellow al. 2014, Szegedy et al.] (017) has thwarted its ap- plication in the safety- sensiivve 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 train robust deep neural net- work 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 train- ing. Specifically, in this paper for adversarial training, consider the attack in le norm, i.e. the following objective
N N
min
max 15
E(x, 0).
This is in contrast with the standard training objective mino 1 EN l(x 0). To obtain a clear theoretical characterization, we focus on the linear classifier.
N
In fact, for linearly separable data, Soudry et al. (017)); 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 rate of ((loggt)-)) However, we find things become much different for adversarial training. We first prove that for "e-strongly linearly separable" data (Definition D.. GD can find the hard margin classifier with faster rate of ((log t)-(1+)")) with the same exponential tail loss used in Soudry et al. (201)). Here e* ([S]s(E) - e))/N, where is the distance between the support vectors and the hard margin solution of SVM, and [S] the number support vectors corresponding to hard margin classifier. This result shows that
find robust solution much faster by adversarial training if the data themselves are more separable than the adversarial radius.
When the data are not e-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 e-strongly linearly separable while there several outliers 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
not
not linearly

---

Under review as a conference paper at ICLR 2020
be sensitive to outliers. However, the classifier returned by adversarial training is slightly affected by outliers. Next, we also show that adversarial training leads to 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 large e. The low confidence in each training data naturally induces 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.
show the stability of adversarial training to outliers, i...
1.1 RELATED WORK
Plenty of work trying to obtain a large margin solution to promote model robustness. Cisse et al. (217 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 [Seraa et 2018 2018|
Croce et al. 2019) uses a first order approximation to compute the margin deep neural network, and then find large margin solution by setting the approximation to be the optimization objective. However, none these works come up with a theoretical guarantee.
Our paper is also related with Soudry al. (2017); Ji & Telgarsky (018)) who prove that gradient descent with logistic loss converge to the hard margin classifier for linearly separable data but with rate of O (log 1)
non-linearly separable data with rate of Olog log t// log t). Nacson eet al. 2018) extend this result to stochastic gradient descent. Gunasekar et al.] (2018) study the convergence under other optimization methods. [Lyu & Li (2019) provides similar result for the homogeneous neural networks. However, they all target the standard optimization problem rather than the adversarial training.
Ilas 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 adver- sarial training.
NOTATIONS AND ASSUMPTIONS
In this section, introduce the notations and assumptions used in this paper. We consider binary classification problem.
Notations. Dataset is represented as {x, yt N where æ; Rd and yi E {-1,1}. The loss function is represented by E(.)- || means l2 norm this paper. The objective of standard training can be represented
1 Co(we) = N
Σ flw" yam.),
where E dRd is a linear classifier. Adversarial training has the objective of
((w) = Σ
max 2=
f(w"" y:
(3)
where E is the adversarial radius. An intuitive explanation of adversarial training that it requires the classifier perform well in the e-ball centered at each data æ; In this paper, w, is the iterate at step of gradient descent (GD) under adversarial training. We use to represent the solution of SVM (8. Now, we give the definition of e-strongly linearly separable data.
Definition (e-strongly linearly separable). I The dataset is e-strongly linearly separable, if there exists w" such that Væ:, "I y 0 and w " y;.: s|[w*|||
The e-strongly linearly separable means there exists 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
Please notice that e-strongly linearly separable is a stronger condition compared with linearly separable. It distinguishes with the separability under soft margin which allows some "." y,a, < 0 but n y,m, > a |ee" ||.
2

---

Under review as a conference paper at ICLR 2020
In addition, linearly separable refers to choosing E 0 in Definition 1 We now define confidence of classifier.
Definition 2 (Confidence). For a given linear classifier of binary classification problem, the logits 1/(1 + e- wn 2.) and e e-w" 2: /(1 + e-w" 2.) for category and -1. Then max(1/( (1/(1 + 2s ) eee w" æ: /(1 +--w"a))) is the confidence of to on data Zt.
The confidence measures how confident the classifier is about the prediction. the sequel, we use 2; to represent y, for simplify the notations. We introduce the assumptions used in this paper.
Assumption 1. The loss function e(- satisfies that Vu, E(u) > 0. (w) < 0, (u) N
0, lim E(u) = liml--soo E (u) = O, and the E(u) has Lipschitz gradient D
Assumption 2. The I(.) and (').) have exponential tail, which means there exists some constant uo and C2, C2 satisfies that Vu uo. Cie I(u) S C2c well as (u
Assumption 3. The w xo [| has the range of lci, oc) each 2;, where C1 > -00. | 2 02 for some constant C2
Due to the properties of loss function, the adversarial training objective explicit formula
with radius & has an
((w)
N w -lllwl]l)
(4)
The adversarial training objective equation is optimized by the gradient descent, i.c.,
Wr+11 = -/)w) = e' (w:" x ellwoel) ( (x: - [wa
(5)
where 7) is the learning rate.
3 ADVERSARIAL TRAINING CONVERGES FASTER TO HARD MARGIN FOR E-STRONGLY LINEARLY SEPARABLE DATA
In this section, we theoretically characterize where adversarial training converges when the data themselves are e-strongly linearly separable. We first have the following key lemma which ensures the loss of adversarial training with radius data. The proof of this lemma is delegated to Appendix A
converge to zero E-strongly linearly separable
Lemma 1. The adversarial training objective equation is convex and L-smooth for some positive
constant L. Then if the data are e-strongly linearly separable 77. the ilerates (we) returned by GD under adversarial training satisfy 1): lim, L(w,) 0, 2): lim lim;-oc w x, - =||w,|| = oc
[wel oc. and 3);
The distance of x; away from linear classifier w, is |w x wel) Then, the convergence result in the Lemma [ does not inform us the robustness of trained classifier. Fortunately, the results in Soudry et al. (2017): : & Telgarsky (2018) claim that the iterates of standard training updated by GD can converge hard margin classifier with the rate of O(llg t)- Now, give the main result of this section. The conclusion is similar to Theorem convergence is much sharper.
Soudry et al. (0177) while the
Theorem 1. For any e-strongly linearly separable data (Definition 1. and loss function E(-) satisfies Assumption 7 and 2 If the Assumption 3 holds, then the gradient flow iterates wil),
dw(() [(ww((())
(6)
dt
satisfies
un (t) = t O (logt) + A((t)
"The loss set to be positive, differentiable, monotonically decreasing convex function. Lots of general used loss functions are satisfied, such as e log +1) etc.
II means that [f( e' ('(x)) I L/u v| for some positive constant L.
4 Lots of loss functions we used such as log (1 + e e="), e are satisfied with this assumption.
This assumption be attained by re-scale the norm of if necessary.
3

---

Under review as a conference paper at ICLR 2020
for large t. Here v is the hard margin solution SVM: ||w]|
arg min
s.t. w 2 1.
(8)
wezd
[I(tt]] is in the order of oloog t). Then
lim 1
w((
v
1 O((log ()+()=)))
(9)
[
where ex | -c) {E:} is the sorted distance of data away from the hard margin solution of
SVM, and S {i wh 2; = Ei of adversarial training updated by GD with step size 1 satisfies
|| Rwlll ]: [S] is the number of elements in set S. Finally, iterates [w;}
w| w w(n)) S O()),
(10)
for k E NT.. Then we can conclude
Wi
lim t-
w (ta)
+ O(r).
(11)
x
We give a brief discussion to hard margin solution of SVM. Since the dataset is s-strongly linearly separable, by KKT condition, we have & < l/|| which informs us all the distance between æ; and vu are larger than Then, we present that perturbations smaller than can be defended by w. Hence, the linear classifier w, becomes robust for a large since has the same direction with w. We then conclude adversarial training on e-strongly linearly separable data helps iterates (wy] 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 E-strongly linearly sepa- rable data.
Adversarial training converges to a robust solution, the same as standard training, with faster rate. The acceleration is determined by the constant s* = (S)e(E) =))/N which related with the true margin E and the number support vectors [
Large proportion of support vectors [S|/N, and appropriate choice of (e1/2 is the best) increase the convergence rate.
We next study where adversarial training converges when the data are not e-strongly linearly sepa- rable.
ADVERSARIAL TRAINING WHEN DATA ARE NOT E-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 non-e-strongly linearly separable data is also crucial.
4.1 THE INFLUENCE OF OUTLIERS
We consider the case that clean data are e-strongly linearly separable but the whole data is e-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 non- linearly separable data.
As shown in Soudry et al. (0017) 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 reasonably good classifier, it has potential to be non-robust, if one intentionally insert outliers to be support vectors. The following proposition presents that hard margin classifier somehow can be non-robust.
4

---

Under review as a conference paper at ICLR 2020
Proposition 1. For two linearly separable datasets {- and {x,); let wi and w be their hard margin classifier respectively. Then, the hard margin classifier ib of union dataset { U No satisfies
||(0|] || max[||201ll, [| [|
This proposition can be derived from the definition of hard margin classifier, which suggests that adding some extra outliers dataset can easily effect the robustness of hard margin classifier, since | 2 max{| |li || and one of w, 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.
N, :=1 is well linearly separable with large margin, which means the hard margin classifier w, has a small norm. We insert some outliers which have the form {0. xz.) 1,m and N1 >> N2. If the outlier is linearly separable with relatively small margin, the corresponding hard margin solution is Wy then we have | << ||202||-
Example 1. Suppose dataset { ()}
We can show that hard margin classifier on the union dataset { (ax 0) (m), thz). Then for each (at, 0), we have
1 0)
(0(),²))) is
(wi,, " (at.0)) (w1, (22) |I
2 a
1 ax
/ a |
(12)
V 1
|
This shows the distance between each { {a)), 0) come extremely small due to a few outliers { (0, i=1'
} and new hard margin classifier (ı01, W22 be-
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 more general description of outliers based on the understanding of Example Given two datasets [ and [ No with N1, N2 data respectively, where N1 > N2. {-/} them- selves are e-strongly linearly separable, but {x]], Nz are not. Then, dataset { 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 {<,?",,?")) - E IRdi+dz
E-strongly linearly separable but span(æ??,... ,xk,)
{(0, (0,x) ) N₂ E RRdidd2 is not linearly separable. Let
span (2t2 .... [N,)) Without loss of generality, we assume { themselves are linearly sep- arable but the hard margin classifier of them ii has relativey small margin compared to the {mx 12 Ni
JEE ie.. || >> [1 where 1h12 is the hard margin classifier on (x) 121N
The union datasets [(x!' ",t"","??)))) 2 UE(O, a;?) is not linearly separable because of the outliers set {(0, ) Even worse, we show in this case, the classifier returned by standard training make the prediction most based on the useful but non-robust information ) 2019).
) (Ilyas al.
happens to be the "Strongly Convex Part" as in Theorem 4.1 of Ji & Telgarsky (2018). then the iterates {w,} updated by gradient de- scent of standard training converge to a direction of the hard margin classifier ú1 of dataset {IIs- (a) { No the presence of outliers {0,, x0,x²?" >>))) renders the classifier returned by standard training on union N2 datasets with poor robustness while the true hard margin classifier on dataset {(x:") 2 T is robust.
The reason as follows. The outliers
! = {(x]] M- where 1l (-) is the projection operator of space S-. Then,
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² ) into correct category renders the classifier (ıù,, (02) to be non-robust. The second describes that the outliers mute the information from {00 ) No for
dataset { !- Then, the classifier turns into a non-robust but useful classifiers.
min [1en Il, | II} which leads to TThe hard margin classifier of (xx) ,n N tे satisfies ||
even robust solution.
5

---

0. Under review as a conference paper at ICLR 2020
4.1.2 ADVERSARIAL TRAINING IS STABLE TO OUTLIERS
Now, we turn the behavior of adversarial training on the above two examples. Lemma shows that the iterates } of adversarial training on e-strongly linearly separable data updated by GD can satisfy lim |well = oc. But the non-e-strongly linearly separability of data ensures there exists some zb such that w 2 E|| || S 0 for each specific t. Hence, || can not go to infinity, otherwise we end up with an infinite loss. This is the essential distinction caused by non-s- strongly linearly separability. Now, we give formal analysis to the stability of adversarial training to outliers.
Due to Lemma
iterates of adversarial training updated by GD converge to minimum w". Then, = =|| II) = p¹¹ we have
let (w" x
VL(w")
N1
N2
ps
k
| |w-1
w
(13)
k=1
It gives
w
2 N2
2
Ny
2 EXPL.
pj
ps
(14)
[ww
k=
k=
k=1
where X = (af x. and ps:
(ph pN.) This implies that the direction of vector wt
is decided by a linear combination of data points. X represents the contribution brought by (at Ji=
2 we see step///f = o(1 (/wel goes to infinity) for any support vector æt and non-support vector æ of wn/ ///l|='||- Hence, the direction of w² is mostly decided by support vectors. This is consistent with the conclusion that hard margin solution of SVM v satisfies (KKT condition) v Σi_ Σ a.æ where a = 0 for non- support 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.
When data are e-strongly linearly separable, by Assumption
However, things become different for non-e-strongly linearly separable data. Since || can not go to infinity, we have the relation p //y" O()). Then the following inequality
(x] X2) P
|apall XiPI
(x3 X.) Ipall
min
Amax
(15)
X x
|pal
(XfX1) ||:Il
mmax
informs us the stability of adversarial training to outliers, where Amin ( (A), Amax(A) (A) are respectively the smallest and largest eigenvalue of matrix A. From equation [3] see the direction of w" can be decided by both dataset {o) 1. and {x, {x?), Since p\ has the same scale with P for every j and N₂ >> N2, we see ||p:] >> ||pel|. then [X >>>>> |X2p2ll- Hence, equation 15 implies that XaP2 has little contribution to the direction of w". Thus, wn can not be the hard margin classifier on union dataset. In addition, w" is mostly decided by data (x!} which tells the stability of adversarial training outliers.
We now provide a discussion to the stability of adversarial training via the lens of babust/non-robur but useful features proposed by llyas 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 given distribution (I,, y). if (mma)) ly-fffl f())] 2 for some 0, but (( inf |6 V. f(x + 8)] I O, then f(-) is non-robust but useful feature.
The definition of robust feature can be generalized for f() with E(m,,) [inf |f y- f(x + 8)] > O. We see the feature is defined by classifier f(.) which is for linear case. Then, the hard margin solution of SVM w;, w2 for [ and {a No in Example and 2 are respectively robust feature and non-robust feature. Further more, let w0 be the classifier (feature) captured by adversarial training. We note that w" being stable 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. (019) while they only empirically verify it.

---

Under review as a conference paper at ICLR 2020
We can also understand other scenarios from equation 15| that not limited to N1 > N2. If N1 s 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.
4.2 CONFIDENCE OF ADVERSARIAL TRAINING
In this subsection, we give characterization to the confidence of classifier returned by adversarial training where data is not e-strongly linearly separable. As shown in Section (4..2 (.1.2 to some constant when data is not e-strongly linearly separable. According to Definition 2 the confidence of classifier is decided by |ww xy on each E₁. Then, bounded || | corresponds to a relatively low confidence in each Zt.
|we|| converges
To give a formal description to the confidence of wt. we discuss an extremely large E 2 max;,; ||x; xyاb which means each E-ball centered at æ; has overlap with each other. For 2; larger w æi, corresponds with higher prediction confidence. For given dataset {æ; let N1. N2 respectively be the number of data in each category and æk.i represents the data from the k-th category. Then we have following theorem descriping the confidence of classifier.
Theorem 2. Let ((u) eee ", for classifier w" returned by adversarial training on non-linearly separable data, |w0 Ikiil is either smaller than E =|[w*|| or satisfies
Ny
max
((--Fatelw""))
if w xx.1 2 E1|w"11,
Nw
2:
(16)
c(lw 1
c- - oN =llw011), II),
if ff"" xus S -E||w"||, w xe 2 0,
Nw
for Ie #/H +k. k.
Our results also applies to ((-) discussed in this paper. A more explicit upper bound for those " TK,,, 2 =||w=|| is referred to equation 56 We notice that ||="|| is bounded on non-e-strongly linearly separable data. Then, this theorem implies that ww" xz on each æ; can not be extremely large. Hence, relatively low confidence in each 2;. A detailed proof of this Theorem is delegated Appendix D Here we use & 2 max., ||> xz out of simplicity, large ε for adversarial training can also correspond to 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 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).
EMPIRICALLY STUDY
In this section, we compare adversarial training with standard training via linear classifier for two scenarios, i.e., e-strongly linearly separable data and non-e-strongly linearly separable data. All experiments are conducted with loss function E(u) = log (1 + +e"), and the update rule is GD with learning rate 0.01.
5.1 EXPERIMENTS ON E-STRONGLY LINEARLY SEPARABLE DATA
We first conduct series of simulations to verify our conclusion on e-strongly linearly separable data. The dataset includes support and non-support vectors. We generate non-support vectors {x, J.N N(y 2 12, 0.3 I2) and support vectors the 1 æ;; y: 2. If there exists least support vector in each category, the hard margin solution of SVM v is 12. See Figure for an example. The distance of support vectors away from the hard margin classifier is v2. Hence, the data are at most v V2llinearly separable. We respectively verify our conclusions Theorem of the convergence rate, support vector number [S] and adversarial radius E.
7

---

Under review as a conference paper at ICLR 2020
(a) Dataset with 5000 support vec- (b) Dataset with 2500 support vec- (c) Dataset with support vector tors and 2500 con-support vectors and 4999 non-support vectors in each category.
tors in each category.
in each category.
Figure I: Three types of datasets.
eec oen repor ou sert suseeiiio
ade (1a riseen yom Metter cempeten
one ou sueer (ok ne sepeen
13%
20/00
25000
(a) Adversarial training with differ- (b) Adversarial training with differ- (c) Standard training with diffcrent ent number of support vectors. number of support vectors
ent 6.
Figure 2: Gap between the direction of iterates and direction of hard margin classifier.
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, 1999) (see Figure D. The results can be referred to Figure 2 Some extra experiments are
delegated to Appendix B We should highlight the direction of {w, here can converge with rate of
((log 0.01 )) and O (log0.01 0.01 -t) +)=(1++))) )), respectively for standard training and adversarial
training due to equation 1I
The "margin gap" in Figure means distance between the direction of iterates w and hard margin solution of SVM 1 2. In Figure 2 the label, for example "Adv: 2500 support 2500 non support: 0.1 varepsilon" means adversarial training with
0.1 dataset with 2500 support vec- tors and 2500 non-support vectors in each category. From the results, we see that adversarial training indeed accelerates convergence rate of w, w//ll On the other hand, both adversarial training and standard training can benefit from the number of support vectors. Finally, as we claimed in Theorem the best adversarial radius is e which is 222 here.
5.2 EXPERIMENTS ON NON-E-STRONGLA LINEARLY SEPARABLE DATA
In this subsection, we conduct experiments on linearly separable (but non-e-strongly linearly sepa- rable) 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 correspond-
ing to Example 1 We generate [xx) ( === 100000 ~ (N(s; 2- 12, 0.3 I2), 02) and {(02, xz) 1000 ~
NO,,N(y, 0.5 2. 1..00.1... I2)). The number of the two datasets in each category are 5000 and 50.
The dataset (02, ) is linearly separable while non-e-strongly linearly separable for = 1.5. {(x) (2)]11000 10000 is e-strongly linearly separable for = 1.5. {02, )
100 can be viewed as out- liers. Then, we compare the stability of adversarial training and standard training conducted on the union dataset to outliers. The adversarial radius E is 1.5. Detailed results can be referred to Figure
3a
8

---

Under review as a conference paper at ICLR 2020
Propertin of Tan Parte
Propertion on Twn Partc
seavee rin wannta popwad
Exratinn
faratin
(a) Non-e-strongly linearly separable but linearly separable data.
(b) Non-linearly separable data.
Figure 3: Adversarial and standard training on non-e-strongly linearly separable but linearly sepa- rable data and non- non-lincarly separable data.
Prequency conficence eocetch data under adversaril learning
Presuenn ncy confilence for nrrch data under adversaria learning
250
10
0.564
6.554
0.66
0.52
0.02
0004
0.54
0.95
0.58
1.00
Frequency of confidence for data point (b) Frequency of confidence for data point under standard learning
under adversarial training
Figure 4: The confidence distributions of adversarial training and standard training when data are linearly separable but 2 1/2 maxi, ||ær; æzyll The y-axis is number of data.
For linearly separable data, the solid lines in Figure are the norm of iterates returned by adversarial training and standard training. The dash lines in Figure Bal for example, "Adv-sep/whole" means the ratio between the norm of classifier decided by the s-strongly linearly separable part that is the first two dimensions of iterates and whole norm of iterates ([ww,, //|/w]], where w E R$ = (w1, w2) E 22+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 some constant rather than infinity. Second, The direction of iterates is mostly decided by { )2) 10000, 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 {(2,, )
Then, we present the results on non-linearly separable data with respect Example 2 we generate 5000 {(x!' (r( Fi=1 ~ (N(y) 0.5 12, 0.1 I2,, 2 12, 0.3 I2) and 50 N0. yi 0.5 12. 0.5- in each category. Here {(22. 21)0 the source 100000000 corresponds with a robust hard margin classifier while
{(0,, 1 of non-linearly separability. {2 Ji=l
(a: (a.11 | is not. {(0,, ax?) 10000 can be viewed as outliers. We conduct adversarial training with = -.77. 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 it- erates. 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, xx) 1,000 The dash lines in Figure 3b for example, "Adv:sep-nrol" and "odv-non sep-rob" are respectively the proportion in norm for the norm of the first and the last two dimensions of iterates ([|w)]]/ /// will and ||/=2|/||/0]] where IR4 (w), W2) E R222).
9

---

Under review as a conference paper at ICLR 2020
We standard training 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 at- tributes to outliers {[02, 22)) But adversarial training can oppositely capture the information from "mostly robust" part.
the confidence of the classifier obtained by adversarial training with 2 max;;; ||æ; z,ll- We generate 5000 samples {x:) ~ ~= 12, 0.1 I2) in each cate- gory. The data linearly separable but non-s-strongly linearly separable for 1, besides that, 1 12 2 maxi, 12; æy ||. We compare the confidence in each data point for classifiers returned by adversarial training with
Finally,
and standard training. The distributions of confidence via classifiers in data can be referred to Figure 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, large e for adversarial training can hurt the prediction confidence of classifier.
CONCLUSION
In this paper, we give theoretical characterization adversarial training for linear classifiers under various settings. We conclude that on e-strongly linearly separable data, adversarial training helps iterates converge the hard margin classifier with rapid rate compared with standard training. means iterates of adversarial training can be robust with less update steps. Furthermore, we charac- terize the adversarial training on non-e-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 not. Finally, we discuss the confidence of the classifier obtained by adversarial training- We prove that under the condition of & 2 maxi. || æy |l. the confidence of classifier obtained by adversarial training keeps in a low level. This reveals that a large for adversarial training is not wisc choice.
REFERENCES
Sanjeev Arora, Simon Hu Wei Du, S, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. arXiv preprint arXiv: //555, 2019.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
Chenyi Chen, Ari Seff, Alain Kornhauser, and Jianxiong Xiao. Deepdriving: Learning affordance for direct perception in autonomous driving. 2015 IEEE International Conference on Computer Vision (ICCV), 2015.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier, Parseval networks: Improving robustness to adversarial examples. arXiv preprint arXiv: 08847, 2017.
Francesco Croce, Maksym Andriushchenko, and Matthias Hein. Provable robustness of relu net- works via maximization of linear regions. Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. Proceedings of the 36th International Conference on Machine Learning (ICML), 2019.
F. Gamaleldin Elsayed. Dilip Krishnan, Hossein Mobahi, Kevin Regan, and Samy Bengio. Large margin deep networks for classification. arXiv preprint arXiv: arXiv:7803.05596 2018.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv: 2014.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. Proceedings of the 35th International Conference on Machine Learning (ICML), 2018.
Kaiming He, Xiangyu Zhang, Ren Shaoqing, and Jian Sun. Deep residual learning for image recog- nition. arXiv preprint arXiv: 15/ 12.03388 2015.
10

---

Under review as a conference paper at ICLR 2020
Matthias Hein and Maksym Andriushchenko. Formal guarantees the robustness of classifier against adversarial manipulation. arXiv preprint arXiv: S..i::/770000475 2017.
Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry. Adversarial examples are not bugs, they features. arXiv preprint (rXXiv:900.021115 2019.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and gener- alization in neural networks. Advances Neural Information Processing Systems 31 (NeurlPS), 2018.
Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint arXiv:1803.07:300, 2018.
A Krizhevsky. Sutskever I., and E.G. Hinton. Imagenet classification with deep convolutional neural networks. Advances in Neural Information Processing Systems 25 (NeurIPS), 2012.
Alexey Kurakin, lan Goodfellow, and Samy Bengio. dversarial examples in the physical world. arXiv preprint arXiv: 1607000220 2016.
Guang-He He Lee, David Alvarez-Melis, and Tommi Jaakkola, S. Towards robust, locally linear deep 2019a.
networks. arXiv preprint
Jachoon Lee, S Samuel Xiao, Lechao Schoenholz, Yasaman Bahri, Jascha Sohl-Dickstein, and Jef- frey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. arXiv preprint arXiv: 06700000 2019, 2019b.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint 1ew.:19060089990 2019.
Alcksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. Proceedings of the International Conference on Representation Learning (ICLR), 2018.
Mor Nacson, Shpigel, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate. arXiv preprint 1.Kiv:8006001990 2018.
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. In Proceedings of the 35th International Conference on Machine Learning (ICML), 2018
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent separable data. arXiv preprint arXiv: 2017.
Weijie Su, Stephen Boyd, and Candes Emmanuel. differential equation for modeling nesterov's 2015..
accelerated gradient method: Theory and insights. arXiv preprint
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199, 2017.
Vladimir Vapnik. Convex Optimization. Springer, Data mining and knowledge discovery, 1995.

---

Under review as a conference paper at ICLR 2020
A PROOF OF LEMMA
I
Proof. We first give convexity the adversarial training objective. For any wi, w2, and 0 s 1, by the convexity and monotone decreasing property of E(-), we have
Awofa x; N)w2 x; -------a0 1l1Aw1 (1 X)wall
N
< N
(xwfar az + 2)w03 = (1 2)]lwall)
(17)
K Xe - + + (1 2)e (m az =||wa|l)
which implies the convexity of adversarial training objective. On the other hand, u (TT2[((w)) can be bounded by L||u||a for some L, then L(w) is L-smooth. We see that
Σ
N ('(w" T a: - =||wo]]) (xx -
w
(m:
w
|
|
(18)
(w" mi - =|Iw]]))([ wn"")
Then, u u² can be divided into two parts, respectively compute them
1" (ww" xz - =||w|]) (1a" az)² - &
Twll u² "''w"""
(u T w)))
u
w
(19)
Lo N
|ull
Amax (xxx) + 28
| + 26a
Here X is matrix (xf ... xN 7T and Amax (x"X) is the largest eigenvalue of X X. On the other
hand, according to Assumption
(w w: -e] ww" )u 28 |uul
(20)
Combining the two above equations. we conclude that largest eigenvalue of V ((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 convex and L-smooth function f(-), GD with step size will ensure the iterates {xt} satisfies f(x)) - f(x)) & O (+). Since the adversarial training loss goes to zero only if wi x - e||well goes to infinity for each x.. It reveals our two conclusions lim,- || = oc and lim wi m e||w,]| oc.
B ORDER OF NORM
In this section we give the order of ||w(t)] on E-strongly linearly separable data, which is highly related to the convergence rate of bound the difference between flow iterates
w(() i
Our proof is based on the gradient flow, we first
[wl
w(( and wi.
Lemma 2. Let we be the iterates updated by GD equation have
then for der(t) dt
- (t))w(t)), we
[[ - wull < O(n).
(21)
Proof. Let
m(kk) un(k ())) - 17 L(r(( 1)m))-
(22)
12

---

Under review as a conference paper at ICLR 2020
Then by Lipschitz gradient of [(-),
km
rb(kr))l = (
VL(wo(u)) VL(w(((: 1)m))du
(k-13) 131
km
Elleo(u) w((k 1)m)ll du
(k-1)n
(23)
ky
L
VL(w0()))ds) du
(K-11M
0612)
Then we have
(((kk)) mxxl 1l 5 lmp m((n)) [|/((k) ((k))
$ 1 1)n) we |l| 1/l 1)m)) [[(we-)]]++
s (1 + nT. |/20((k 1)m) u=-1ll 0(7²)
(24)
$ S - nT, ||mr(0) mmol + O(n)
O
for (0) wp. which results in the conclusion.
Before proving the Theorem we give a lemma to illustrate that w(() will converge to the direction of i.
Lemma 3. There exists to. for to. have
w(1) p({) + le(L);
(25)
for some p(t) and h(t). Here p(t) goes to infinity and [[/(t)]] is in the order of o(p(t)).
Proof. Let
[o(t]] |
r(t w(t)
w
(26)
|r[|]]| = o (t) will implies the conclusion. Since ('()) has exponential tail Assumption there exists to, for t >> to, have
d ||((t]] dt
*" (t)r(t) [[((t]] [|(())] (1
1
w(t)" i (((((()))rr(t [[((t||| 2b1l
[[)ll]] (1 cos(w(t), w)) Σ exp (-w(1)" + ellw((t))) (0.. (a:-c [[o(t)]]
mn(t)
) r(t).
(27)
Then, we see
N
(())) +=|lwo(())) (a:: [ea=)((w()]] [wo(t)]
wr(t)
)² T
Σ exp
r(()
(r((t)=a: [[w(t)] æ:
w(t)
Σ exp
+ e||la(()))
(x: ee ( r(1)
|
exp
[t) m: + =((l((()1] - eexp
||00|||
(rr(t)T x:
[0t x:
|
+ e(]wo(())]
[[((t]] (())
w())
< N exp (-(1: - (t)l)
(28)
where ú is the hard margin classifier and s is the distance between support vectors and w. Here we the relationship that se < for any z and w(t)7 (rt)) 2 0. Since
r(t) Tm
(1 cos(w(t), w))
(29)
(()) ||
13

---

Under review as a conference paper at ICLR 2020
and r(t)" 2 - O, have d
r(t)* i dt ||((t]]| & -CN || (ttt)lllw(ttllll
CN
exp (-(e1 =)]]
exp (-(51 e)]l) (30)
||
Similar to Theorem 3 in Su et al. 2015). by exponential tail of ((-) Assumption 2 we have
Ci exp (-w(1) (t)" a; el]w(()) s (w(())) - =|(w((Iil
|| woll
(31)
for constant C₁ and any w.. Then we
20h
log
+ logt & w(t)" a; - =|[w((]]]-
(32)
N N|
woll
On the other hand, by the definition of hard margin classifier and Lemma there exists 2; such that w(l)²as a; S E1 ((]]) Combining this and equation 32 we have
C1 N wo
log
log
s [|w(()]]-
(33)
Plugging this into equation 30 and we that there exists such that logt 2 log Mi then
C1
[+)l < [|r Att)l (er =) woll saor
L
flogt" dt loogg)
(34)
CO1
fort to At.. Combining these, conclude that [|r(()]] is in the order of o (t)l)
Next, we use lemma to illustrate the explicit order of p(t)
Lemma 4. p(t) in Lemma 3 is on the scale of logt hurd murgin solution of SVM w.
z1-2" where {ei} is the sorted distance of { to
Proof. From Lemma and have
w
u (t) = p(t)
+ (ttt,
(35)
[
where p(() - and ||A())]== o((()) Specifically, the h(!) can be chosen to be orthogonal with w. otherwise we can use a decomposition in a direct sum. For [[w(t)]], we have
[[]] ve(()² (+(1))
-o(t)== [1((1)112 p(t) + p(t) (VPlly | +
11(00)1+++())))) p(t)
(VP(0)+1N(0]]) -P())) + p(t)
(36)
Ve(t)² + [|b(t)]? p(t)
12(1))2
p(t) Ve(t)2 [ + P(t)
On the other hand, for large enough,
d
w()
[w(()) = (t)
dt
[t]]l
Ci
(a: ( mn(t)
w(( æ, + =((w(())))
N
[[w(t)]]
[w((t]l
Ci
-p(t) to x;
[/(())]1
T x
N
exp
[
h(tt)* x Ep(t) +
p(() + / p())² + |
C2
M
exp
(-(e: =)p(t)) -8)
N
(37)
14

---

Under review as a conference paper at ICLR 2020
for some constant C1 C2. Since p(t) goes to infinity and [[h(()]] o(p(t)). the derivation of 14(a)l will (t)) Similar to equation 37 we can get the lower bound of [[(())))
p(t)+ /o())*+ h(D
In summary, we have
N exp (-(1) =)p(t)) (E1 5) p(()) C2 e2exp(((51 (-(51 =)p(t)) (EN E)
(38)
for constant some C3. Hence we can conclude that
logt -
logt
Cs p(t) E1 - + Ca,
(39)
for constant Ca, Cg. It results in p(t) O(log t).
We have proven that (()) will converge to the direction of úh. Now, we will show wn(t) will have the same support vector with ip when is large. It's key fact of proving Theorem [
Lemma 5. There exists to such that w()) will have the same support vectors with vo for > to.
Proof. Let S {i: 2t" x; = for E S.j o S, we have
w(()² [t]]]] (ai - x,, = (p(t) Ro
+ h((t)) T
(a; m.,)
[[][1
(40)
(p()) w0
(x: xz) + [|((()]] - -251l)
|0
2 | (z; - x3) 0. Then, ||{(t]] = o(p(t)) shows that
Since æ; is the support vector of w.
w(t)" [w())]] (x: z;j) S for a large t. Then we get the conclusion.
C PROOF OF THEOREM
In this section, we give fully characterization the proof of Theorem 1
Restate of Theorem [ For any e-strongly linearly separable data (Definition 7 and loss function the Assumption 3 holds, then the gradient flow tterates w((t).
E(-) satisfies Assumption 7 and 2
dw(tt
[[w((()
(41)
dt
satisfies
w() = の O (log !) + h()),
(42)
for a large t. Here ip is the hard margin solution of SVM:
ab = arg min ||al||
s.t. w T n; 2 1.
(43)
werd
[I(())] is in the order of o(log t). Then
lim
w(t)
w |
S O 1) -(+ee))))
(44)
[|x(()]]
where e* = (Sle(e--)) { is the sorted distance of data away from the hard margin solution of SVM, and S {i TTT x; E [11l00]] } |S] is the number of elements in set S. Finally, iterates {w,} of adversarial training updated by GD with step size r will satisfy
ww w(kv)) 5 O(r).
(45)
for k E N Then we can conclude
Wt
lim E-
wi (t))
[ + +06)
(46)
Tw (wr)
15

---

Under review as a conference paper at ICLR 2020
|لll|| + h(t). Denoting the support vectors set by S, fi w/ El E1]rö|]]. By the exponential tail of (u) (Assumption 2). there exists to. for >> to. we have
Proof. Let w(t) p(t) vb
||((t)]
dt
V0 VL(w(()) + p'())
[ )
T 1((1) = VV((((()))
C
exp (- w()) + (())(( (xi-s (5 w(1)
Σ
[wo(T]] [
hn(t)
N
C
TT x; |
|1(())1
w(I) T [w(t)]l tc(1)
N
exp
-p(()
h(1)Ta: + sp(() + p()) + v p((()) + [+(])
a E
IES
N
exp
(p((
|0
24
h(11" 0z Ep(() )(:))===-)))) (x:-c w(()
Tw((()]
1((L)
FES
(1 - (5: - =))(()) [/((t))12
Σ exp (-
p(t)
(47)
Here we use fact that 2 htt)= S 0 due vi is the hard margin classifier. In addition,
|4(1I2 (() V [((())=
S exp (
1+
(48)
(()) + VP(0 + (1(E))
With this, we can choose a to such that
Σ exp ((1) i
h(1) x; + =p(())
-2 w(t) T h(t) p(() ve(12² + |A(0)
[w/lI (
(49)
w(t)
exp wt))) + ([]
x -
[w)(t))
h(t) 20.
for > to. This concludes the equation equation 47 Let [|
[x: be C(t), we can first derive that [[b(f)]l will converge to zero, then C(t) can be close to zero. By Gronwall's inequality, we have
[|(()| < [[(( exp (f.
se C(u)
Σ exp ee)(( du
(50)
Np(u)
FES
C(I) can be arbitrary small when / > lo- Plugging this into equation 50 and combining Lemma we have
[|((t) 18 s [[A((6) exp
E(EI - 8)
Σ
du
N log
iES
E(E1 - E)
[[((to) 1 exp
ulog u du
N
u
(51)
to
S]a((E
[[h(to) 1 exp
log log
N
O(logt)
where =x [Sle(e)-E) Since we have
(())
p(t)
à
ha(t)
(52)
[
p(() +
[[CCO] o(0)
[
p()) +
[A
7 Herr we hide the constant C in the last inequality, which is decided by loss function 7(-). O will usually smaller than in fact.
16

---

Under review as a conference paper at ICLR 2020
Compa Adversor
Comparision
Ado 3530 sugpot 25.0 snvassee d. parpiitinn
Adyy supiic eate sapert seraslke 23.0 sugpon 2332 rappen sarepalion
2330 sappon 2222 reppon d.e nampiier
3071
10%1
2074
1earcc dic
100122 Mtc
(a) Adversarial training with different e.
(b) Adversarial training with different num- her of support vectors.
Figure 5: Gap between the direction of iterates and direction of hard margin classifier in 4 space.
Compaiitsion of Adversar of Rodius
Compatision of Support Vectors
12'
samppition Adh 3930 support 2533 varvaceeel 0.39 warepulia
127
ramppition Joh. 5330 soorr Dree ia supert 6.3 verepiiee
5074
20m1
30'11
20033
40030
68/300
$3000
300090
20030
40030
60/000
13000
300090
(a) Adversarial training with different
(b) Adversarial training with different num- her of support vectors.
Figure 6: Gap between the direction of iterates and direction of hard margin classifier in Lo space.
then we see
(()
i
p(()
S 1
[t][
|| |
p(L)
P(() +
1A0E P(9)
P(T)
[[((1)]1
[|((t)]]
(53)
p(t) + [(]] +
p(t) + [[CO
p(t)
- (1++7)
when l goes to infinity. Since h(()= < Olog ")==" for e* [Sla(e) can get the conclusion.
Combining Lemma we
D PROOF OF THEOREM 2
Proof. The Th, will either satisties |w0 xv.al I E||w>|| nor |w 2x,5 2 e||w>|l, []. We know the first inequality represents the distance between ØA and w² is smaller than e. Then for æw a for any i,j, there exists Ihe E
T Tg.s 2 E|lw"ll, due to E 2 2 max,,j || LR.i aw (2( with k k,,k= = 1,2 and k'' # k. By triangle inequality, the distance be- u mx.
B2 (a
tween a and un is smaller than Thw I| by the monotone decreasing property of e(-), we have
Since may locates in different category with an.i
f(-w""
TT Th.i + =||lw" II) E ((cks)) S
max Elw" R Im
x).
(54)
|m- SSe
17

---

Under review as a conference paper at ICLR 2020
Trequrccy
(a) Non-e-strongly lincarly separa- ble but lincarly separable data.
(b) Non-lincarly separable data.
(c) Frequency of confidence for data point under adversarial train- ing
Figure 7: Adversarial training in 4 space. Outliers are added into dataset of the first two subfig- ure. The third subfigure confidence distribution for adversarial training when data are linearly separable but e 2 3 max,,) || 2il1- The y-axis in the third pictures is number of data.
Prppctica cet seperco
atuene Prpprtion
Freque ny www.lleeeeeee sivenaatiiie
Sdler you ritemnie
120%
XD02
2005
(a) Non-e-Strongly linearly separa- ble but linearly separable data.
(b) Non-linearly separable data.
(c) Frequency of confidence for data point under adversarial train- ing
Figure 8: Adversarial training in Lo space. Outliers added into dataset of the first two subfig- ure. The third subfigure is confidence distribution for adversarial training when data are linearly separable but e 2 / maxi.j ||0; 2.,l1- The y-axis in the third pictures is number of data.
Hence have
N NN
8(-w"2 xu., =E|lw"") 11)
max 2e.
=
(55)
1=1
Then, have
No8 (-1w0 m1.5 + e|lw= + N18 " x2.1l + +ellwo") S (N1 N2)e(0),
(56)
wn can correctly predict point far from margin larger than in each category. for those w T Tkii 2 s||w>|| due w² is minimum, then L(w") I L(O). On the other hand, for w Tg.i 5 - ww] can immediately derive
flw" xu.)) S f(-w" "" x E||w"") I))
(57)
by triangle inequality where TT 2 0. Then we get the conclusion.
E EXTRA EXPERIMENTS
E.1 ADVERSARIAL TRAINING IN Ip SPACE
Our conclusions obtained for adversarial training in ly space while it can be conducted in more general Ip space (Goodfellow et al.) 2014, Madry et al. 2018).. It is meaningful to verify whether these conclusions still hold in (, space. Hence, we extend our experiments to I, space.
18

---

Under review as a conference paper at ICLR 2020
The adversarial training objective within linear classifier can be formulated
[(w)
max l(w" x)) i; Si
(58)
in 1p space, where ||p is Ip norm. It has explicit formulation
1 ((w) N E e w0 æ; - ==|20olo)
Ee(w"=
(59)
where
We conduct experiments for p and oo.
We empirically verify that adversarial training in I, space helps accelerating the convergence to hard margin solution of SVM on e-strongly linearly separable data. Besides that, adversarial training can benefit from more support vectors and an appropriate adversarial radius E. For non-e-strongly linearly separable data, we try validate that adversarial training in l 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] In addition, should notice that the distance between support vectors locate in 1 x =d and hard margin classifier la in lp space is d different p.
expect for the p are respectively chosen 4 and co.
Hence should adjust the adversarial radius for [[allo
We first verify the conclusion for e-strongly linearly separable data. The results for = 4 and p can be respectively referred to Figure and 6 Noticing that the distance between support vectors and hard margin solution of SVM is TLll d Then for = 4, = oo and d = 2, we
have 2 = 1.18, 2 = 1. From the results, we see that an appropriate adversarial radius (E = E1/ and more support vectors are helpful for adversarial training even Ip space.
Now, we pay our attention to non-c-strongly linearly separable data. We respectively verify our conclusions about stability and confidence of adversarial training. The experimental settings are again same with S5ction The results can be referred to [ggure7[an[] We see that our conclusions are still hold in I, space, i.e. classifier obtained by adversarial training is stable to outliers and the confidence of it will consist keep in low level for a large E.
matter of fact, we can generalize our theoretical results to Ip space by following the methods in this paper. The inner product (-.-) of linear classifier is derived from || lla while l2 is Hilbert space, but lp space is not. The inner product we used does not math the 4p space. Hence, we need adding some extra bounded conditions to extend our conclusions to 1p space.
E.2 ADVERSARIAL TRAINING FOR NEURAL NETWORK
Our conclusions are derived from linear classifier, but Du et al. (2019); Jacot et al. (001)) Lee et al. (2019)); Arora et al. (2019) suggest that over-parameterized neural networks of sufficient width (or infintte 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. this subsection, we try to empirically verify our conclusions about adversarial training within neural network model.
We use CIFAR1O (Krizhevsky et al. 2012) to conduct our experiments. CIFAR10 is dataset with 10 categories. To simplify the experiments, we only keep the first two categorics, which turns the experiments into binary classification problem. The model used for adversarial training is ResNet20 (He et al. 2015). which a CNN with 20 layers. The experiments are conducted lg and loc space.
Since we can not compute the exact distance between data and classifier, we use the loss on training data R 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 al. (2018). We use PGD find the arg max =ell=lee. ((x, 9) for each æ;-
Here we only focus on training data hecause we do not discuss the generalization of model obtained by adversarial training.
19

---

Under review as a conference paper at ICLR 2020
Prequeency
Ady 8:35 vapiiii 24roeripi
call vemepiiinn
10
60
20-
Epech
(a) Adversarial training with different e for (b) Frequency of confidence for data point under adversarial training with an extremely large
outliers exist or not.
Figure 9: Performance of adversarial training in la space
Jlle E1E1 Adu SAuL uneediion
6615 acrepatte wit compaatoon
20
1.0
bpach
(a) Adversarial training with different æ for (b) Frequency of confidence for data point outliers exist or not.
under adversarial training with an extremely
large
Figure 10: Performance of adversarial training in 4.0 space
The steps of PGD is 10 for each x;. 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 s-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 will benefit from an appropriate choice of adversarial radius e. To compare the influence of e, we choose E ==0 0.25, 1.0, 2.0 in (2 space and æ = 2/255, 8/255, 16/255 in loo space. The size of perturbations are from Madry et al. (2018). Besides that, the perturbations of trained model are 1.0 and 8/255 respectively in l2 space and loc space. The experimental results in le and Loc space can be referred to Figure 9a 10 and 10a The label of curves, for example, "Adv: 0.25 varepsilon" means adversarial training with E = 0.25. From the figures, we see that the models returned by adversarial training with and = 8/255 are respectively the most robust in l2 and Loc space. Hence, the conclusion that adversarial training can benefit from an appropriate choice of e also holds for neural network.
training set set to verify the robustness
Then, for non-e-strongly linearly separable data, we respectively discuss the influence of outliers and a large e. First, we construct 50 outliers { 1100 ~ -V(+0008122 1a2x 0.045 32xa) in
each category in both l2 and 1.0 space. The influence of outliers for adversarial training in l and Loe space can be respectively referred to Figure 9a and T0a
" "Adv with outliers: 0.25 varepsilon"
We should highlight that the perturbations are recalculated after each epoch of training. 10We only list the results of adversarial leaning, hecause the loss on data with perturbation of standard training will not converge (always larger than 2.0).
20

---

Under review as a conference paper at ICLR 2020
means adversarial training with outliers added into dataset and 0.25. From the results, that outliers will barely effect the performance adversarial training. Hence, we can conclude that adversarial training is still stable outliers, even the model is neural network. On the other hand, respectively choose e equal to and 32 2255 in 12 and lo space to verify the confidence of classifier returned by adversarial training. The distributions of confidence via adversarial training in l2 and loo space can be respectively referred to Figure and neural network trained by adversarial training with large is fairly low level in each data.
and I0b) The results reveal that the confidence of
To summary, although our conclusion about adversarial training are derived from linear classifier, the empirically results suggest can be somehow extended the case of neural networks. Thus, theoretical exploration for neural network is crucial in the future work.
21


Reviews:
[{"review_id": "r1gP-GPSqr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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).\n\nOverall, the paper is not recommended for publication for many reasons. \n\nFirst, 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. \n\nSecond, the paper needs to be proof-read. It has a lot of typos and grammatical errors that make sentences difficult to understand. Examples include: \n- \"while there several outliers are not or even not linearly separable\", \n- \"a simple generalization error bound informs the high loss on test set\"\n\nThird, 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. \n\nForth, 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.\n\nSome additional comments: \n- How did the authors arrive at Eq 4? I don't see how this follows from the assumptions. Can you please elaborate? \n- I am not aware of any book written by Vapnik in 1995 called \"Convex Optimization\". I think the authors meant the SVM paper. \n\nGiven 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. \n\n=========== \n#Post Rebuttal Remarks\n\nRegarding 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. \n\nThanks 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.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BygvfpMCFS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nThe first result of this paper is interesting, that adversarial training converges faster than standard training. Studying the difference between the convergent points between adversarial training and standard training is also an interesting research problem. However, I still have two main concerns about the current version of the paper.\n1. The paper is trying to develop rigorous results, but its writing is arguably not rigorous. Many statement are not clear and some notations are used without definition. Section 4.1 has many vague statements. See more concrete comments below. \n2. I am not sure about the significance of the results in the paper. The results highly depend on the linear setting with convex losses. More than that, Theorem 1 assumes the \\eps strongly linear separable, and Theorem 2 assumes a large \\eps (if the statement is that |w* x_{k,i}| is less than a large number, it seems much less interesting). These are very strong assumptions that are usually not true in practice. Experimental results only cover carefully designed simulation as well.\n\nDetailed comments for item 1 above:\n1. Assumption 3, what is the quantifier for w? Is it for every w? There exists some w? How do you guarantee by “rescale the norm of w” (from the footnote) to make sure that c_1 is not -\\infty?\n2. Lemma 1, this is for every x_i, or some particular x_i?\n3. What is w(t)?\n4. What is the condition on \\eta in Theorem 1? Why it is O(\\eta) in equation (11) or equation (24)?\n5. The claims in section 4.1 seem to be depended on carefully designed examples. Would it still true rigorously for general cases? \n6. In section 4.1.2 first paragraph, why ||w_t|| can not go to infinity? in the third paragraph, how assumption 2 implies p^k_i / p^k`_j = o(1), or later  p^k_i / p^k`_j = O(1)?\n7. In section 4.2 second paragraph, what is “k_th category”?\n8. Is w^* unique in Theorem 2?\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "Bkeuqk7NtS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "TL;DR: The paper gives interesting, theoretical results to adversarial training. The paper only uses linear classifiers, which are hardly the same problem as deep networks where adversarial attacks are problematic. Some conclusions from theorems can be vague or informal, and therefore are not very convincing. I vote for rejecting this paper since it is hard to claim it informs deep learning research (the motivating reason for doing adversarial training). However, I am not familiar with theoretical analysis of adversarial attack/defense, so I am open to counter-arguments.\n\n=================\n1.    What is the specific question/problem tackled by the paper?\nThe paper gives a theoretical analysis to the theoretically less-studied procedure of adversarial training, and shows properties of adversarial training in comparison to regular training, for both linearly separable data or inseparable data. The paper sheds light on some empirical behavior of adversarially trained networks, namely that they are more robust to outliers and lower in performance.\n\n2.    Is the approach well motivated, including being well-placed in the literature?\nI am not an expert of adversarial samples, so I am ill-equipped to judge the novelty of the paper. The research direction itself is well motivated, and in the realm of deep learning, it is posed as a first paper to theoretically analyze adversarial training.\nHowever, the authors only analyzed linear classifiers. This makes the results of the paper ill-suited for deep networks, whose non-linearity is arguably the reason why adversarial samples are such a problem. The motivation of the paper is thus greatly diminished. For linear classifiers, I do not know if there are existing work on their robustness when perturbation of samples are being trained on, but to be well-placed in the literature, the authors must either claim there is none, or cite those papers.\n\n3.    Does the paper support the claims? This includes determining if results, whether theoretical or empirical, are correct and if they are scientifically rigorous.\nClaims and novelties in this paper include:\n(1) Adversarial training converges faster than regular training if samples are ε-strongly linearly separable,\n(2) If samples are not \"ε-strongly linearly separable\", adversarial training is robust to outliers, while regular training is not,\n(3) Confidence is low for all (training) samples if ε is large. \n\nOnly (1) seems to be sufficiently proved. I am not certain that this is a very useful result, and I am open to counter-arguments.\n(2) and (3) have steps that are vague and informal:\n\n(2) That regular training is susceptible to outliers is proof by example and people already know that. Also the claim relies on the assumption that pi^1 and pj^2 are on the same scale, while those samples that violate the decision boundary can have arbitrarily large pi^1 or pj^2. Since outliers are often the violators, and inliers often are not, a small number of carefully placed outliers can make ||p2|| quite large while each pi^1 can be very small. It is also worth noting the logic seems to boil down to \"N1>>N2, so inliers should overwhelm outliers, making the training robust\". The claim is not guaranteed.\n\n(3) I am not very sure if I understand it correctly, but the logic seems to be that the logits are bounded, so they cannot be too large, and so the confidence is low. However, the bound also involves the magnitude of w and x from the other class, so the final step of the proof is either unclear or the bound can indeed be quite large. Note that |wx| does not need to be very large for the confidence to be high (e.g. if logit is 5, the confidence is 1/(1+e^-5)=99.3%). The claim also relies on the assumption that epsilon is larger than the distance between the farthest points in the dataset, which is extreme since you can find an adversarial sample that can be considered to be simultaneously \"close enough\" to the two most dissimilar samples in the dataset.\n\nIn the end, the results are not very convincing or useful for informing deep learning research.\n\n=============\nTo improve paper:\n- Clarify motivation and how this would inform adversarial training highly non-linear classifiers;\n- Add related work for robustness to perturbation of linear models, or state that they don't exist;\n- Clarify weaknesses in the claims.\n\nEditorial changes:\nDefinition 2: \"logit\" <--- people call this probability estimates; logits are wTx\nSec. 4.1.2 needs to clarify what k in x_i^k means -- it's continued from proposition 1 which at first glance is irrelevant\n\n\n=================\nPost rebuttal\n\nApologies for not interacting earlier due to deadlines. \nThe rebuttal does not address my major concern (motivation), nor does it discuss its relationship with related work. The math questions are not answered very clearly; I do not see how section 4.1.2 proves p_i^1 has the same scale as p_j^2, except maybe that they are all smaller than some constant for certain samples. And other discussions in the rebuttal simply confirms my concern. \nIn summary, I think this paper is not yet ready for publication.\n\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies adversarial training in the linear classification setting, and shows a rate of convergence for adversarial training of o(1/log T) to the hard margin SVM solution under a set of assumptions. 

While 2 reviewers agree that the problem and the central result is somewhat interesting (though R3 is uncertain of the applicability to deep learning, I agree that useful insights can often be gleaned from studying the linear case), reviewers were critical of the degree of clarity and rigour in the writing, including notation, symbol reuse, repetitions/redundancies, and clarity surrounding the assumptions made.

No updates to the paper were made and reviewers did not feel their concerns were addressed by the rebuttals. I therefore recommend rejection, but would encourage the authors to continue refining their paper in order to showcase their results more clearly and didactically.
Decision: Reject