Implicit Bias of Adversarial Training for Deep Neural Networks
Authors: Bochen Lv
Zhanxing Zhu
Venue: ICLR 2022 Poster (2022)
Keywords: adversarial training
adversarial examples

Abstract: We provide theoretical understandings of the implicit bias imposed by adversarial training for homogeneous deep neural networks without any explicit regularization. In particular, for deep linear networks adversarially trained by gradient descent on a linearly separable dataset, we prove that the direction of the product of weight matrices converges to the direction of the max-margin solution of the original dataset. Furthermore, we generalize this result to the case of adversarial training for non-linear homogeneous deep neural networks without the linear separability of the dataset. We show that, when the neural network is adversarially trained with  $\ell_2$ or $\ell_{\infty}$ FGSM, FGM and PGD perturbations, the direction of the limit point of normalized parameters of the network along the trajectory of the gradient flow converges to a KKT point of a constrained optimization problem that aims to maximize the margin for adversarial examples. Our results theoretically justify the longstanding conjecture that adversarial training modifies the decision boundary by utilizing adversarial examples to improve robustness, and potentially provides insights for designing new robust training strategies.

Published as a conference paper at ICLR 2022
IMPLICIT BIAS OF ADVERARIAL TRAINING FOR DEEP NEURAL NETWORKS
Bochen Lyu DataCanvas Lab DataCanvas, Beijing, China 1vbc zetyun.com
Zhanxing Zhu
The University of Edinburgh, UK zhanxing igg..in zzu@gma 11 com
ABSTRACT
We provide theoretical understandings of the implicit bias imposed by adversarial training for homogeneous deep neural networks without any explicit regularization. In particular, for deep linear networks adversarially trained by gradient descent on linearly separable dataset, we prove that the direction of the product of weight matrices converges to the direction of the max-ma margin solution of the original dataset. Furthermore, we generalize this result the case of adversarial training for non-linear homogeneous deep neural networks without the linear separability of the dataset. We show that, when the neural network is adversarially trained with & or &xx FGSM, FGM and PGD perturbations, the direction of the limit point of normalized parameters of the network along the trajectory the gradient flow converges to a KKT point of constrained optimization problem that aims to maximize the margin for adversarial examples. Our results theoretically justify the longstanding conjecture that adversarial training modifies the decision boundary by utilizing adversarial examples to improve robustness, and potentially provides insights for designing new robust training strategies.
INTRODUCTION
Deep neural networks (DNNs) have achieved great success in many fields such as computer vision (Krizhevsky et al. 2012 He et al. 2015) and natural language processing (Collobert & Weston 2008) and other applications. These breakthroughs also lead the importance of research on the robustness and security issues of DNNs, among which those about adversarial examples are especially prevalent. Adversarial examples are obtained by adding craftily designed imperceptible perturbations to the original examples, which can sharply change the predictions of the DNNs with high confidence (Szegedy et al.) 2014, Nguyen et al. (0155). Such vulnerability of DNNs renders security concerns about deploying them in security-criticat systems including vision for autonomous recognition. It is therefore crucial to develop defense mechanisms against these adversarial examples for deep learning.
and face
To this end, many defense strategies have been proposed to make DNNs resistant to adversarial examples, such adding a randomization layer before the input the classifier (Xie al. 2018). input transformations (Guo et al. 2018), adversarial training (Madry et al. 2018)) etc. However, Athalye al. (0088) pointed out that most of the defense techniques are ineffective and give a false sense of security due to obfuscated gradients except for adversarial training a method which has not been comprehensively attacked yet. Given a C'-clas training dataset ((),,))) with natural example x; E Idd and corresponding label yi E {I,..., C}, adversarial training is formulated as solving the following minimax optimization problem
1 Σ max e (x; + 8,(W),, v:: W). W &.EB(O.e)
min ((W)- W
-min
(1)
where f is the DNN function, is the loss function and (W) is the adversarial perturbation generated by some adversary A(z,, y6; W) typically depending model parameters W, within the set ((00e) e) = (6 ||ó0| S t} around the natural example σ,, Commonly, adversarial training conducts two-player game at each iteration: the inner maximization is attack the model and

---

Published as a conference paper at ICLR 2022
find the corresponding perturbation of the original example that maximizes the classification loss f; the outer minimization, on the other hand, is to update the model parameters W with the gradient descent method such that the loss is minimized on adversarial examples generated by the inner maximization (see Algorithm for details).
To have better theoretical understanding of the fact that adversarial training empirically improves the robustness of DNNs against adversarial examples, /Zhnn et al. (2019) decomposed the prediction error for adversarial examples and identified a trade-off' between robustness and accuracy while Li et al. (2020) studied the inductive bias of gradient descent based adversarial training for logistic regression on linearly separable data. Faghri et al. (202T) studied adversarial robustness of linear neural networks by exploring the optimization bias of different methods. Yu et al. (2021) studied adversarial training through the bias-variance decomposition and showed that its generalization error on clean examples mainly comes from the bias. However, even for the simplest DNN the deep linear network, we notice that there exists no work to theoretically understand such robustness achieved by adversarial training through exploring its implicit bias.
On the other hand, for the standard training, recent works extensively explored the implicit bias imposed by gradient descent or its variants for DNNs in different settings. For a simple setting of linear logistic regression on linearly separable data, (ouudyy et al. (2018); Di & Telgarsky (2018); Nacson al. (2019b) derived that the direction of the model parameter converges to that of the max-(2-margin with divergent norm. |hhamir (2021) concluded that gradient methods never overfit when training linear predictors over separable dataset. Viewing the above model single-layer network, a natural but more complicated extension is that for the deep linear network on linearly separable data: Ji & Telgarsky (2019) proved that the gradient descent aligns the weight matrices across layers and the product of weight matrices also converges to the direction of the max-ly-margin solution: Gunasekar al. (2018) showed the implicit bias of gradient descent on linear convolution networks. |acson et al. (2019)); Lyu & Li (2020) further promoted the study of implicit bias of gradient descent for standard training to the case of more general homogeneous non-linear neural networks and proved that the limit point of the optimization path is along the direction of a KKT point of the max--mariin problem. Wei et al. (2019) studied the regularization path for homogeneous DNNs and also proved the convergence to the mar-in direction in this setting, [Banburkki et al. (2019) showed that gradient descent induces a dynamics of normalized weights converging to an equilibrium which corresponds to minimal norm solution.
is therefore our goal in this paper to theoretically understand the resistance to adversarial examples for adversarially trained DNNs, linear and non-linear ones, through the lens of implicit bias imposed by adversarial training. Due to the inner maximization, adversarial training differs a lot from standard training and one should be careful analyze the perturbed training dynamics. For the adversarial training objective Eq. [ various approaches have been proposed to solve the inner maximization, such as fast gradient sign method (FGSM (Goodtellow et al. (0155) and its stronger version projected gradient descent (PGD (Madry et al. 2018). The widely used adversarial training adopts PGD to attack the model, while recent work (Wong et al., (020) also suggested that weaker adversary can also surprisingly yield a model with satisfying robustness. Thus to conduct a comprehensive study about the implicit bias of adversarial training for DNNs, we will use f--fast gradient method (FGM (Miyato et al. 2016)), loo FGSM, P2D and l. -PG to solve the inner maximization of the adversarial training objective.
1.1 OUR CONTRIBUTION
In this paper, we devote answering two questions. First, is there any implicit bias imposed by adversarial training for DNNs without explicit regularization? Second, if there exists such an implicit pronggencepopprtttee properties of the model parameters along the adversarial training
bias, what are the convergence trajectory?
To this end, we first investigate the adversarial training with Eg adversarial perturbations for deep linear networks on linear separable data where the allowed Euclidean distances from the adversarial of
examples to their corresponding original examples || - æzll2 are less than the max- the original dataset. Despite the simplicity of this setting, this problem is meaningful due to its non-convexity and the introduction of adversarial examples, which heavily depend on the model parameters, during the training process. We prove that gradient descent for adversarial training
2

---

Published as a conference paper at ICLR 2022
implicitly aligns weight matrices across layers and the direction of the product of weight matrices also surprisingly converges to that of the max-éy-margin solution of the original dataset- similar to that of standard training for deep linear network (Ji & Telgarsky 2019p. Our results significantly generalize those in Li et al. (2020) for adversarial training of logistic regression. This simple yet insightful case positively answers our first question but partially answers the second one because it still remains unclear why such convergence property can improve robustness considering its similarity to that for the standard training. In fact, adversarial training differs from standard training in the way how they impose such convergence property for parameters: the first one is to maximize the margin of adversarial examples while the latter is maximizing that of the original dataset, and these two optimization problems happen to possess solutions along the same direction.
We then move forward to explore a more general situation, adversarial training for homogeneous non-linear DNNs without the linear separability of the dataset. We study the limit point of the normalized model parameters along the adversarial training trajectory and show that
Theorem (Informal). When the deep neural network adversarially trained with one of the 22-FGM, FGSM, EzPGG and fxPGGD perturbations, the limit point of the normalized model parameters is along the direction of a KKT point of a constrained optimization problem which aims to maximize the margin of adversarial examples.
This indicates that adversarial training is implicitly maximizing the margin of adversarial examples rather than that of original dataset. Thus Theorem provides another view for high bias error on clean examples of adversarial training in Yu et al. (2021) since distributions of adversarial and clean examples are different. To the best of knowledge, these results are the first attempt to analyze the implicit bias of adversarial training for DNNs. We believe understanding on the elfectiveness of adversarial training for improving robustness against adversarial examples. It could potentially shed light how enhance the robustness of adversarially trained models or even further inspire more effective defense mechanisms.
results provide theoretical
This paper is organized as follows. Section Diis about notations and settings. Section 3 presents main results on the implicit bias of adversarial training for DNNs. Section D provides numerical experiments to support our claims. We conclude this work Section 5 and discuss future directions. Some technical proofs deferred to supplementary materials.
Organization.
Algorithm 1 Adversarial Training
Input: Training set S = {(x,, y)) Adversary A to solve the inner maximization, learning rate 17, initialization W₁ for k {I....,
for f S'(t)= 0
to T do
for = 1 to n do
(1) A(zi, Mi, W(!)
S'(1) = ((())(((())))))
end for
for k = 1 to L do
Wa(t + 1) = W (t) (t))
(1):W
aW4
end for end for
PRELIMINARIES
Notations. For any matrix A e Rm we denote its i-th row j-th column entry by Ayy Let AT denote the transpose of A. || -|r represents the Frobenius norm and ||- l|p is the l, norm. The training set is {x,, yi) where I; E RRd ||æ:||2 < 1 and y E {1, 11. For scalar function f Rd + R, we denote its gradient by Vf. Furthermore, tr (A) = E. Au denotes the trace for the matrix A.
We study the adversarial training for the L-layer positively homogeneous deep neural network
f(x; W) WL (WL-1 1......... (WWes"))) ...)
(2)
3

---

Published as a conference paper at ICLR 2022
where W3 is the le-th layer weight matrix and Pp is the activation function of the k-th layer The multi-c-homoeenetty of the network is defined by
L f(z; ai WT, ,LLWL) = II (); R=1
(3)
for any positive constants ag's and c 2 1, where W (W1,". Wr.) is the collection of the parameters of the network. For example, deep ReLU networks are multi- --ooo-oenoooou...... For convenience, we also adopt the following notations for multi-e- hollii--homogeneuuss DNN:
Pk [W .ip. and [(z; W); ((;;) pf W),
where W, = W&/l| with ||W for k (I....,,
We use 6, (W) to represent the adversarial perturbation of the original example x; within the perturba- tion set ((00 e) {6 || < around the original example for f(z; W). Furthermore, use the scale invariant adversarial perturbations defined as follows for adversarial training in this paper.
Definition (Scale invariant adversarial perturbation). An adversarial perturbation said to be scale invariant adversarial perturbation for fxx; WI...., WL) and loss function È if it satisfies
b L)) = 6.W,......... WL)
ag
(5)
for any positive constants ag 's.
We will show in Section 3.2 that FGSM, 42-F l2-PGD and PPGD perturbations for homoge- neous DNNs are all scale invariant perturbations, which are important for analyzing different types of perturbation in unified manner. The empirical adversarial training loss with the perturbation (W) given by
1 ! E(W)
Σ 1=1
(vI, Fy W)
n Σ &
For ease notation, we denote (((W) = E(y;, Fe; W). The loss function l is continuously differen- tiable and satisfies
Assumption (Loss function),
<> 0, l' < 0, lim {(z) 0 and f0 (I)
Many widely used loss functions satisfy the above assumption such as E(x) e and the logistic loss f(x) In + +))).. Furthermore, make the following common assumptions about the smoothness of f(;; W) and the adversarial perturbation 8(W):
Assumption (Smoothness). With respect to W, yf(x; W) is locally Lipschitz for any fixed x: yrf( W) further have locally Lipschitz gradients and (W) locally Lipschitz for all training examples zt.
Remark. Our results can also be generalized non-smooth homogeneous neural networks straight- forwardly (Appendix B.4).. Assuming Lipschitzness about perturbations is because we focus on popular perturbations such as 42- and PGD perturbations which have explicit forms and depend on gradients of the network, whose Lipschitzness assumptions are quite common.
3 MAIN RESULTS
We present our main theoretical results on the implicit bias of the gradient flow/gradient descent for adversarial training in this section. For the deep linear neural network, a special kind of homogeneous models, in Section 3.1 we further restrict the dataset to be linearly separable and focus on E2 adversarial perturbations. We prove that the singular vectors corresponding to the largest singular values of weight matrices get aligned across layers with the progress of adversarial training [ Based this key result, the product weight matrices converges to the direction the maximum margin solution
4 is a vector in our notations. This phenomenon for standard training has been studied by Ji & Telgarsky 2019 first.
4

---

Published as a conference paper at ICLR 2022
under the original data. Furthermore, study much more general scenario in Section without the assumption of linearly separability of data and norm constraints on adversarial perturbations, show that the gradient flow of adversarial training with scale invariant adversarial perturbations for the homogeneous nonlinear neural networks implicitly performs margin maximization under the adversarial data. Due to the space limit, some technical proofs of Section 3.1 are deferred to
Appendix A and we present proof's of Section 3.2 in Appendix B
3.1 ADVERSARIAL TRAINING FOR DEEP LINEAR NETWORK
In this section we restrict the dataset {(r;, V/ 9:)) ]i= to be linearly separable in the sense that there exists a unit vector u such that Vi E {1,...,M) " Mi (u) 0 and we explore the adversarial training dynamics of gradient descent for deep linear networks, i.c., with identity activation function sP (xr) for all layers,
f(x, W) WL WIx.
Now let
ū = arg max
min (Ii, u)
1 m)
be the max-margin solution given by the the max-margin where = arg (1...e( (I,, u). We only consider the f--norm adversarial perturbations in this section, i.c., B(0, e) = {ō 1|0112 S E}. The allowed Euclidean distance from an adversarial example x' to its original example xr is assumed to satisfy
SVM and 7/m = max||ull 9m (Im u) be
|| - 2| S e S 7m-
(8)
We denote the product of all weight matrices by Wn Wt. Wi, which is simply vector. Our model is adversarially trained by gradient descent
ac(t)
W&(t + 1) = W& (t) - n(t) aW)(t)
The inner maximization of the adversarial training objective Eq. can be solved exactly in this case, where the adversarial perturbations are taken as
(n(())
(W) Vie
(10)
[Wn
for the t-th iteration of adversarial training. For any layer k the weight matrix can be decomposed as
W₂ = VV
where Uj and Vj are the left and right singular matrices, respectively. Furthermore, to represent the left and right singular vectors corresponding to the largest singular value, respectively. We emphasize that the training dynamics abruptly changes due this perturbation and one should be careful to analyze its effects. It can be easily seen that Eq. (TO) is scale invariant adversarial perturbations by our definition. Note that with this kind perturbation, the adversarial data during the training are still linearly separable, since we have required that the perturbation is smaller than the max-margin of the original dataset described in Eq. (8). We further assume that & satisfies
u4 and ug
Assumption 3. The loss function e is 3-smooth and 1e" << a.
such as logistic loss. We are now ready to explore the implicit bias of the gradient descent for adversarial training. Inspired by the idea of studying the smoothness of loss function from [i & Telgarsky (2019) for standard training, here we first examine whether our adversarial training loss Eq. possesses smoothness. Let the set S(r) denote the of weights with bounded norm
S(r) ((r)=(w][in))) [W|llWelle r, 1|Wull F, ks 1..... L}.
(11)
where r 2 and is a small constant to avoid trivial solution. To simplify the notation, we let
aB Fr.
F(r, 3
1 1 l
3 pt. 2a B (
(12)
The following lemma provides us a first view of the overall trends gradient descent for adversarial training in deep linear network linear separable dataset.
5

---

Published as a conference paper at ICLR 2022
Lemma (Overall trends of adversarial training for deep linear network). With adversarial pertur- bation Eq. (10), under Assumption [ Assumption 3nd and the requirement Eq. (). for the deep linear network adversarially trained by gradient descent linear separable data, the adversarial training objective (T) is B(r, F, (f,,))ssooot within the given set S(r) for constant r. However, with constant step size for gradient descent, the weight matrices will eventually leave the set S(r) if remains unchanged during the training
[[a((t)) r (1.....
max
for some t O.
(13)
The first part of this lemma implies the smoothness of the adversarial training loss Eq. ① while also leading the weight matrices to leave the set S(r). In fact, this is saying that ma.kee1...... [[Will is divergent along the adversarial training trajectory since (e...e(1...... [|Wallr will be larger than for any given r. We can keep (t + 1) inside S(r(t)) at every step t by delicately adjusting the step function of the step
size of gradient descent and treating
Lemma 2 (Smoothness of the adversarial training loss). If the learning rate is taken 17(1)
min (f, then the adversarial training loss L(W) is 3(r, (ir,F,e, e)smoothh where r(t (t++b) 1) is taken as
+tt+ + [r(t) (r(t)= u(t)
if ((++ E S(r(t) - -m(t)),
otherwise
during the training, where μ = - +c)//((rFFFF)))
We show the divergence of ma [|W along the adversarial training trajectory in Lemma 1. and now we can further derive that the Frobenius norms of weight matrices for all layers are divergent with the smoothness of the adversarial training loss in hand, considering that the differences between any two layers during the adversarial training are always bounded (Lemma 6). Due to this divergence of weight norms, only the direction of the product of weight matrices is important for the model to make predictions.
Now we present our main theorem to provide insights on the theoretical understanding of the implicit bias of gradient descent for adversarial training of deep linear network.
Theorem 2 (Convergence to the direction of the max-man max-margin solution). With adversarial perturbation Eq. (1). under Assumption 7 Assumption 3 and requirement (8), for gradient descent of the adversarial training objective Eq. (6) with logistic loss, the singular vectors of the largest singular
values of adjacent layers get aligned if the learning rate is taken as that in Lemma 2
Vk (I..,....,
Kug, U841)l +1
(14)
as t oc. As result, the direction of the product of weight matrices converges to that of the max-margin solution
WI
(15)
|Wall2
Remark. The alignment phenomenon for standard training has been showed in the previous work & Telgarsky (2019), here we further extend this result to the case of adversarial training, where the training objective different from that of the standard training due to the introduction of adversarial perturbation dependent on the parameters of the network. Our work is also significant generalization of of et al. (2020) which studied the convergence to mar-ma solution of adversarial training for logistic regression, single-layer linear network.
Furthermore, although the direction of the solution Eq. (15) given by adversarial training does not differ from that of standard training, i.e., the direction of u, these two solutions are not same: the first is maximizing the margin of adversarial examples while the latter is maximizing that original Bataset-which happens to be the same one in this setting. The similarity of these two solutions comes from the fact that the adversarial data are also linearly separable under the requirement Eq. (8). whose max-margh solution has the same direction as that of u. The above reasoning will be more clear in the next section where we show the solution of adversarial training as a max margin solution of adversaria examples more explicitly.

---

Published as a conference paper at ICLR 2022
3.2 ADVERSARIAL TRAINING FOR HOMOGENEOUS DEEP NEURAL NETWORK
Additional definitions For simplicity, we will use exponential loss ((x) = e- in this section. For an original example 24, the margin for its adversarial example x; + ++,,(W is defined as &t waf(r; + 6, &W)); W) while for the whole dataset {<),, )- the margin for their corresponding adversarial examples is denoted by 7m where m arg m fr
+ (W); W). We
introduce the normalized margin as 5 = [=; + 8; (W); W) to explore the convergence properties, where Wi- = W&/ | such that ||Wlll 1 for any layer k. Furthermore, the margin for the original example z; is defined to be , = fz, W) 2 %. To relieve the headaches of picking suitable learning rates, we consider gradient flow, gradient descent with infinitesimal step, of the training loss Eq. (6) which leads to
T
dW4 dt
oc aW
(16)
for & E (I,..., L}. Note that the introduction of adversarial perturbations (relying on the network parameters) abruptly perturbs the training dynamics. In this section, to conduct a comprehensive study of adversarial training. we do not restrict the perturbation used for solving the inner maximization of the adversarial training objective in advance while only require it to be scale invariant adversarial perturbation. By noting the following lemma, we can easily generalize our results to the commonly used adversarial attacks:
Lemma 3. Under Assumption !
f2-FGM, FGSM, P2DPG and -PGD perturbations for homoge- neous DNNs all scale invariant adversarial perturbations.
The RHS of Eq. (16) is different from that of standard training due to the inner maximization. Our key observation is the following property of adversarial training which can drastically simplify our analysis despite of the complexity brought by the adversarial examples.
Lemma 4. For the exponential loss, along the gradient flow trajectory of adversarial training with scale invariant adversarial perturbations for homogeneous DNN fa; W), we have
ac aw
WR
(17)
n
In the case of deep linear network, we adopt linearly separable dataset with the requirement Eq. (8) yielding the fact that the adversarial data are also linearly separable. In this section we do not impose such conditions but only apply weaker assumption in more general scenario.
Assumption 4. There exists a separability of adversarial examples of the datase there exists a time to such that fxf + 6, (fo));
(tto)) W (to)) > ffror all i [I.....n..
Theoretically, Zhang et al. 2020); Gao et al. (2019) proved the convergence to low robust training loss for heavily overparametrized nets. Moreover, adversarial training can typically achieve this separability in practice, i.e., the model can fit adversarial examples of the training dataset, which makes the above assumption reasonable one. In Section 3.11 we obtain divergent weight norms for adversarial training. Thanks to Lemma 4 we can further generalize it to the case of homogeneous network without linearly separability of dataset and the requirement Eq. (8) for adversarial examples. This divergence of model parameters is necessary for the convergence of the adversarial training loss.
To begin with, recalling our definition of p IIK PE -Ik ||W]|| F. state first main theorem regarding the overall trend for gradient flow of adversarial training as follows.
Theorem (Divergence of weight norms). For the adversarial training objective T6) of the binary classification task with exponential loss and scale invariant adversarial perturbations, under Assump- tion 2 and Assumption 4 the product of the Frobenius norms of weight matrices diverges to infinity along the trajectory of the gradient flow
p= Ω (In - 00,
and, as result, the training loss È converges to zero as t + Dc.
Similar assumptions are previously used in Lyu & 2020 Ji & Telgarsky 2020
7

---

Published as a conference paper at ICLR 2022
Remark. The divergence of weight norms for standard training of homogeneous DNNs has been studied by, for example,[yy [Lyu & Li (2000); Wei et al. (2019). The above theorem considers adversarial training, which implies that the margin for adversarial example, 5/z for any i {I...., n), also goes to infinity along the adversarial training trajectory. This makes the normalized margin 9/ necessary understand the convergence properties of the adversarial training solution t co. Built upon this result, we first shed some lights on the implicit bias of the gradient flow for the adversarial training through the following theorem, which discusses the training dynamics of the normalized margins for the adversarial examples.
Theorem 4 (Non-dccrcasing ad adversarial margin). For adversarial training with scale invariant adversarial perturbations, when the separability of adversarial examples is achieved at to, the weighted sum of the changing rates of normalized margins for the adversarial examples are non- negative for all 2 to:
di
11 2 to
Σ
2 0:
(18)
dt
there exists a sufficiently large time t1 >> to such that
dimm dt
w(()) = for all t 2 t1. 2 Of tm
The above theorem reveals relation for the normalized margins for adversarial examples. According to the above lemma, since / 0o as -> oc, the term with weight e e- roughly speaking, dominates the LHS of 18) after some time 1 2 to. Then /ftm/dffwww will never be negative for Vt 2 t1. This directly implies that the gradient flow is actually maximizing the margin for the adversarial examples of the original dataset. Applying Lemma 4 and Theorem 33 in the following theorem, we further strengthen the above observation for adversarial training for homogeneous DNNs.
Theorem 5 (Convergence to the direction of a KKT point). Under Assumption 2 and f for ex- ponential loss and mulli-c-homogeneen
DNNs, the limit point of normalized weight parameters [W/I[W]|a 2 0} of the gradient flow for the adversarial training objective Eq. (6) with scale invariant adversarial perturbations is along the direction of KKT point of the constrained norm- minimization problem
1 1 2
min W Wi..., Ws
E (1.....m).
(19)
According to Lemma 3 the above theorem can be directly applied to f2MFGM, FGSM, lg and lae perturbations. The requirement Eq. (8) in Section 3.1 is not required since the dataset in this section is no longer lincarly separable. It is well-known that the norm- comm-miniiizatinn problem closely related to the mariiiiiiaiiiiiiionnn problem in the sense that max W2
Remark 1.
Optimization problem 19)
s.t. [W112 =1
Remark 2. Theorem 5 is the key theorem of this section. It shows that, for adversarial training. the gradient flow is implicitly maximizing the margin of adversarial examples. Therefore, for perturbations with norm constraints other than fz-norm, (19) no longer an f2-norm optimization problem but a mixed-nome one due to the perturbation o(W) in 7m. which was first observed by Li et al. (020)) for adversarial training of one-layer neural network while our results are for more general deep non-linear homogeneous neural networks. This is one of the major differences between adversarial training and standard training-thhr are formulated from solving different optimization problem. [3 theoretical understandings of the folklore that adversarial training can modify the decision boundary against adversarial examples to improve robustness.
Remark 3. In the context of standard training, Lyu & Li (0200) studied the properties of the nor- malized margin through its approximation, the smooth-normalized margin. One can try to generalize the analysis method in Lyu & Li (220)) to adversarial training with various kinds of adversarial perturbations by further assuming the local smoothness regarding gradients when considering non- smooth analysis. Generalizinig our results to non-smooth case can be found in Appendix BB.4 To easily adapt to adversarial training, our new strategy in this work is to directly analyze the normalized margin itself for adversarial examples instead and utilizes the alignment phenomena observed by Ji & Telgarsky| (2020). Most importantly, what we seek to push forward in the current work are the theoretical understandings of the adversarial training for DNNs through its implicit bias.
'Strictly speaking, this is not well-defined since m may not be unique. However, can use this definition in an approximately correct way for sufficiently large.
8

---

Published as a conference paper at ICLR 2022
0.23
with peoortatin
8:00
-2.0
-.9
dlocarazaning
165
300
1900 1350 2865 1ite 3066 rol0s 2000 srin ssioo
esachh
(a) FGSM adversarial examples
(h) fo adversarial examples
(c) FGSM adversarial examples
Figure I: Adversarial training for the 3-layer neural network on MNIST, Adversarial normalized
margin for (a) FGSM adversarial examples; (b) l -PGD adversarial examples; (c) FGSM adversarial examples after 10000 epochs.
Trade-off between robustness and accuracy. More significantly, Theorem also implies that adversarial training leads to the trade-off between robustness and accuracy as Zhang et al. (2019). This can be seen as follows. Let f(, W) denote the classifier obtained from adversarial training. Then for clean training example (x. y) with y = for simplicity, we have yf + 8(W): W) f(z + 5(W); W) > 0 since fx; W) is max-margin classifier over adversarial data. This means that, for any clean test example (x', (2') around x in the sense that x' x ++ with || S c, we will
have
f(x', W) = f(x + t; W) 2 [(x + 8(W); W) >
(20)
due to the definition of 5(W) when = 1: 8(W) = max,e ((yf(r + u; w;))
gBt.) f(x + v; W) for < 0. Therefore, as a result of forcing our model to correctly classify the adversarial example x + ((W), it will classify any such x' = x + 7 as having labels even there may be some of them having true labels -1, which leads to the drop of accuracy at the cost of increasing robustness. Besides, since adversarial training maximizes the margin of the specific adversarial perturbation used for training, the trained model performs worse other perturbations.
4 NUMERICAL EXPERIMENTS
In this section, we conduct numerical experiments on MNIST dataset to support our claims. We adversarially trained 3-layer neural network using SGD with constant learning rate and batch-size 80. The model has the architecture of input layer-1024-B8 Ree---RLLU-------------
layer. We present results for adversarial training with: (1) FGSM perturbations with e 16/255; (2) & PGG perturbations, where the PGD is ran for 5 steps with step size 6/255 and = 16/255. As comparison, we also standardly trained a model with the same architecture to evaluate the normalized margin for adversarial examples by attacking it with FGSM and PGD during its training process.
Fig. [(a) shows that the normalized margin for FGSM adversarial examples keeps increasing during the process of adversarial training with FGSM perturbations. Meanwhile, the standardly trained model has lower normalized margins for FGSM adversarial examples. Similar results exist for
PPGD adversarial examples as showed by Fig, [(b) To see that adversarial normalized keeps increasing more clearly, we also plot the adversarial training with FGSM perturbations after 10000 epochs in Fig. [cc] More detailed experiments are in Appendix C These empirical findings support our claims that adversarial training implicitly maximizes the margin of adversarial examples.
5 CONCLUSION
In this paper, we have studied the implicit bias of adversarial training for the deep linear networks and, more generally. the homogeneous DNNs. We proved that adversarial training with scale invariant adversarial perturbations implicitly performs margin-maximizann training process. Intuitively, such implicit bias strongly implies that adversarial training encourages the neural networks to utilize adversarial examples more to improve its robustness. It will be an interesting future direction to improve the effect of adversarial training by promoting it to enlarge the margins of adversarial examples more effectively. It is also possible to design new defense mechanisms by explicitly requiring the standard training have the bias of maximizing the margin of adversarial examples. We will leave these potential benefits of our theoretical analysis as future work.
for adversarial data during its

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENT
This project is supported by Beijing Nova Program (No. 202072) from Beijing Municipal Science Technology Commission.
REFERENCES
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. In arXiv:1882.006509 2018.
A. Athalye, N. Carlini, and D. Wagner. Obfuscated gradients give false sense of security: Circum- venting defenses to adversarial examples. In International Conference Machine learning(ICML), 2018.
A. Banburski, Q. Liao, B. Miranda, T. Poggio, L. Rosasco, F. D. L. Torre, and J. Hidary, Theory ii:: Dynamics and generalization in deep networks. In arXiv: /99999990099,,..... 2019.
Frank H Clarke. Generalized gradients and applications. 1975.
Frank H Clarke. Optimization and nonsmooth analysis. 1983.
R. Collobert and J. Weston. A unified architecture for natural language processing; Deep neural networks with multitask learning. Proceedings the 25th international conference on Machine learning(ICML), 2008.
Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, and Jason D. Lee. Stochastic subgradient method converges on tame functions. In crXiv:/804.07795. 2018.
S. S. Du, W. Hu, and D. Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. In arXiv: 1806,00900, 2018.
J. Dutta, K. Deb, R. Tulshyan, and R. Arora. Approximate kkt points and proximity measure for termination. Journal of Global Optimization, pp. 1463-1499, 2013.
Fartash Faghri, Sven Gowal, Cristina Vasconcelos, David J. Fleet, Fabian Pedregosa, and Nico- las Le Roux. Bridging the gap between adversarial robustness and optimization bias. In arXiv: 2102.08868, 2021.
R. Gao, T. Cai, H. Li, L. Wang, C. Hsich, and J. Lee. Convergence of adversarial training in overparametrized neural networks. In arXiv:1906.0790 2019.
Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. In International Conference Learning Representations (ICLR), 2015.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Implicit bias of gradient descent on linear convolutional networks. In arXiv: 1806.00468, 2018.
C. Guo, M. Rana. M. Cisse, and L. van der Maaten. Countering adversarial images using input transformations. In International Conference on Learning Representations((IIRR) 2018.
K. He. X. Zhang, S. Ren, and Sun. Delving deep into rectifiers: Surpassing human-leved per- formance on imagenet classification. In International conference on computer vision (ICCV), 2015.
Z. Ji and M. Telgarsky. Risk and parameter convergence of logistic regression. In arXiv:1803.073000 2018.
Z. Ji and M. Telgarsky. Gradient descent aligns the layers of deep linear networks. In International Conference Learning Representations((CLRR) 2019.
Z. Ji and M. Telgarsky. Directional convergence and alignment in deep learning. In arX1v:2006.06657, 2020.
10

---

Published as a conference paper at ICLR 2022
A. Krizhevsky, I. Sutskever, and G. Hinton. Imagenent classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems(NeurIPSS, 2012.
Y. Li, E. X.Fgn, H. Xu, and T. Zhao. Inductive bias of gradient descent based adversarial training separable data, In International Conference on Machine Learning(/CLR), 2020.
K. Lyu and J. Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations//CLR)) 2020.
A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Represeettations/CCLR) 2018.
Miyato, A. M. Dai, and I. Goodfellow. Adversarialtraiinng methods for semi-supervised text
classification. In (rXXi::605.00725. 2016.
M. S. Nacson, S. Gunasekar, J. Lee, N. Srebro, and D. Soudry. Lexicographic and depth- mar- gins in homogeneous and ton-homogeneous deep models. In Proceedings of the 36th International Conference on Machine Learning, 2019a.
M. S. Nacson, N. Srebro, and D. Soudry. Stochastic gradient descent separable data: Exact convergence with a fixed learning rate. In Proceedings of Machine Learning Research, 2019b.
A. Nguyen, J. Yosinski, and J. Clune. Deep neural networks are easily fooled: High confidence predictions for unrecognizable images. Conference on computer vision and pattern recognition (CVPR), 2015.
Ohad Shamir. Gradient methods never overfit on separable data. Journal of Machine Learning Research, 2021.
D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro. The implicit bias of gradient descent on separable data. Journal of Machine Learning Research, pp. 1-57, 2018.
C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations (ICLR), 2014.
C. J. Lee, Q. Liu, and T. Ma. Regularization matters: Generalization and optimization neural nets v.s. their induced kernel. In Advances in Neural Information Processing Systems(NeurlPP) 2019.
E. Wong, L. Rice, and J. Z. Kolter. Fast is better than free: Revisiting adversarial training. In International Conference on Learning Representations (ICLR), 2020.
C. Xie, Wang, Z. Z.ZZhang. 7. Ren, and A. Yuille. Mitigating adversarial effects through randomization. In International Conference on Learning Representations (ICLR), 2018.
Yaodong Yu. Zitong Yang, Edgar Dobriban, Jacob Steinhardt, and Yi Ma. Understanding gen- eralization in adversarial training via the bias- variance decomposition. In arXiv: 2/03.09947, 2021.
H. Zhang, Y. Yu, J. Jiao, E. P. Xing. L. Ghaoui, and M. I. Jordan. Theoretically principled trade-off between robustness and accuracy. In International Conference on Machine Learning//LLR), 2019.
Y. Zhang, O. Plevrakis, S. S. Du, X. Li, 7.. Song, and S. Arora. Over-parameterrzed adversarial training: An analysis overcoming the curse of dimensionality. In arXiv: 2002,06668, 2020.
A PROOFS OF SECTION 3.1
In Section A. we discuss the smoothness of the adversarial training loss. In Section A.2 we prove the alignment phenomenon of adversarial training for deep linear networks. We make the common assumption that (O)( < Ž(()) E(O) and VZ(W(0)) o 0 start adversarial training.
11

---

Published as a conference paper at ICLR 2022
A.1 SMOOTHNESS OF THE ADVERSARIAL TRAINING LOSS
A.1.1 PROOF OF LEMMA
Proof. We first prove that the adversarial training loss for the deep linear network is smooth within S(r). For any W.V E S(r), let ow and ōy denote the adversarial perturbations of the network f(;; W) and f(;; V), respectively. Then we have, by taking derivatives of L w.r.t W and using that ||A|| + |B F 2 ||A BllF,
a ac
<
W
WF - Vs. ......V... VV y (
OW1
0V,
π
F
1=1
(8)
(Ww)) á
|iall ((vi))
(21)
7
OW
0Vi
F
where the term (b) abruptly changes the training dynamics. For simplicity, we use æ, and E' without the subscript i because the analysis can be done similarly for any i E (1....,n) .n). We begin with the term (a) of Eq. (T):
(a)
W3 WF ye (Wi) V2- WF (Win)
1/2 V2'" W xt ye (Wn1) - V22 ...Ve a² ye (VT))
< WW2 - 1/21 W3 WT xT y (W11)
+ |1/1| W3 ... .. ve (WT)) V/2 ... V.' (ViT)
W2 - 1/21 1 a + r W/ ... WT (Wn) -Vz- ... VT ur (Vi)
Σ 2 2 W Vill + - V || (Wn)) [
(1--2a(1 alL 1) + 2L || - VII.
(22)
where c follows from ||||| - 1, ||&l| || and 8' S a; repeating the procedure of c until L gives us d; e is because W - Vvll < | - V|| for any k and
((Wn) - [ s BllWn
Vill $ 3Lr VIl
(23)
considering that is 8-smooth function. It now remains us to bound the term (b) of Eq. 21 Note
that
a Wulle
WT- ... ..WWW W1
(24)
aw,
||
12

---

Published as a conference paper at ICLR 2022
then we have
W ... W.
W1 (Win) V/ ... ...WEW Wi ((Wn)
(b) c
|Will
|Will
W3 ... ...,. ... Wi ((Wn)
1/21 V3 ... VL ... V1 ((Vn))
+
[Wn]]
Vull
2ar22-2
11W2 Vi2l
fL
W3 W.,. ... W1 (WTn))
VJ VTV. ... V1 ((vm)
+er
|Winll
[[Vn
1A (2T. - 1) 2ap21-22 21.-
(WWn)
(Vin
IW - VII + 21-2
pl.
1W [[Vill
2L.22-2
2-2
$ (2T. 1)
I - -VI + 7L
(((wn)
(Vin)
Vn
FL
FLL
21
(2L - 1)a + 1-1 a.3L pL
I|W -V
(25)
pL
where с follows from WWell < and e' < at repeating for 2L times gives d: follows from [|] - -I[V < Wn - Vnnl; invoking Eq. (2) gives us f. Now we can bound Eq. (21) by
combing the above results
ac ac
OW,
QV
$ aab= 1) 3p22-22 2p2b22
astrl-11
(2L (2L (2L-1)a+ l)a
3Lr--1
I
vil
FL
Gl
e FL L s+
2a 22+
3+
ag FL
| VIl.
(26)
where the last inequality is because we choose r 2 1. The above analysis is for the first layer. Now we can apply the same technique to other layers, which finally gives us
a8
(VŻ(W)- - vv(V) 3 L a 3 FI
2a
B
IW
VIl.
(27)
FL
thus is A(r, F, c)-smooth inside S(r) where
aB FI 2a + B +
FI ]
((), 33 1 a + 3+
(28)
We now prove the second statement of Lemmal which says that W will leave S(r) with constant and learning rate 17. Let W (t), W + 1) E S(r) and n)()) = min (r, F, e)).
Lemma (Adapted from Lemma 6 in Ji & Telgarsky (2019). Under Assumption 1 and Assumption
3 suppose gradient descent for adversarial training is run with constant step size 1/3(r, (B(rr,,). c,F). Then there exists time t when max; [t)ll) > r.
Eq. 27 states that Ż B(r, F. F.er, -mooth,h therefore
Ž(W (LW(+1)) ()) < (vē(W()). ( -(02(((0)) + 3 F()(t, (()))
7(1)
(V)(W(
(29)
2
which also implies that ((W()) (t)) never increases during the training
[( + 1)) < Z(W()) 7(1) 2 (V)((())))
(30)
By repeatedly applying Lemma when the learning rate is constant, we know W will eventually leave S(r), which also implies that max ||Wa]|r is unbounded in this case.
13

---

Published as a conference paper at ICLR 2022
A.1.2 PROOF OF LEMMA
Proof. For any step with the learning rate in the Lemma we then have
suppose that W(1) S(r(t) plt)).
ac (W |
n(t) [ 1) = [[a(t) -(())
I [[&+(t)l+++ +((t)
where the last inequality follows from
ac
$|WErs WW WF ... (e(n))
0 || ll ((Wi))
2
+
(t)
OW
<1 = Jan
(31)
Therefore |[ + 1)1l will always stay S(r(t)) and the smoothness is preserved. [[Wa(t= + F F is still less than r(t) u(t), then we keep r(t 1) r(t) while increase 1)
r(t + 1) r(t) +((t)
if r(t) p(t)= S [ + 1)Il, S (t)) such that [| 1) r(t) < ju(t + 1). which means that W(t ( 2) will stay inside S(r((+1)) The overall smoothness can then be proved by induction.
A.2 ALIGNMENT PIENOMENON
We start with the following lemma for the adversarial training to prove the alignment phenomenor Lemma 6 (Bounded differences between weight norms). The difference of Frobenius norms for any two layers is bounded during the adversarial training process
W (t)l (t)) 2α(W(0)) - [|) (W)( Vk,j E (1....,
Proof. If there is not adversarial perturbation, then we can easily obtain
OC Oc
WT A+1 OW
W
(32)
ow
by conducting some algebra, where L stands for the empirical loss without adversarial perturbation. Then invoking Eq. (24) for k by noting that tr (A) ir (A*) and tr (ABC) tr (CAB), we have
[[illl yee(Wu) 11
y W
WT.
k+1 WEW W.WT W
ow h+1
0 11 wT. OW
vc((Wn)
(33)
Combining Eq. 32 for the adversarial empirical loss, we have
OC
ac WT oW
WT WR+1 oW
(34)
which will give the following relation
T
ac
ac
Wfi (t 1)W&+1 1)= = W (t) + ntt22
OW++i(t)
Hw oW*+i(t)
T
Oc
ac
(tt W (t)
W4+z(t)
a @Wr+1(t
+
@Wk+1(t)
TThis property for standard training has previously heen studied & Telgarsky 2019
Arora et al.
2018
14

---

Published as a conference paper at ICLR 2022
which can be easily seen by writing out the gradient descent update explicitly. One derive similar relation for W&(t + + (t+ + 1). Combing Eq. 32, we have
T
oC @W*+1(1) ac
aC @W
W + (I W (1) 10(12
T
ac @W
Wx((+ (6(4+11)10 1)W (1++) - (1) n1(1²
(35)
(W
Summing up the above equation from 0 to f will give us
(1) (0) A 1 (1) Ww(O)W (2(O) B&(1)
(36)
where symmetric matrices A& and B3 are defined by
1-1
oc @Ww(T)
T
ac @WW(T)
(x(1) = Σ n())2
==0
and
2-1
ac aWi(T)
ac aWie())
T
Bx(l) - Σ 1(7)
Also notice that
tr (
(37)
where
@W*(T) )
ac
ac
tr (Ax(t)) I
tr
?(T)
==11
1-1
ac
?(T)2
ow (T)
k=1r=0
((7)
V[(W
22 Σ ((T)
b
- E(W(F -(W (x +1)
c 2C(W(O)) - (t) < 2ū))
(38)
where a is because 7) < 1; b is due to Eq. 29):: summing up from 7 = to - and noting that Ż >> 0 give us C. For any two layers l < j. taking trace of both sides of (36) and summing from k to have that the differences between the Frobenius norms for any two layers
(0)) I1, 1 Ir (A)( |W tr (Bx (1) I|W (1)
s 2C( (0)) (0)) (1))
are always bounded. Since maxigeer | W > oo, the above result implies that || + 00 for all k.
A.2.1 PROOF OF THEOREM 2
Intuitively, Wi can be decomposed as
Wa(() U2(E) (1).
15

---

Published as a conference paper at ICLR 2022
For WR. denote the first singular value, the corresponding left singular vector and right singular vector by Oe. 4y and lk-- Since 0e - oc, the initialization becomes negligible as - oc. According to Eq. 36 this will lead
( (t)U
(0)
as + CO. On the other hand, since Wy. W has rank 1 for Wr being row vector, all layers have W, rank 1 because they get aligned with Wz and [wll. + Z.an
To further elaborate the above reasoning, we provide more exact proof starting with the definition of the alignment phenomenon.
Definition (Alignment phenomenon for deep linear networks.). For deep linear network [(x; W)
=
WL ... WIT, the alignment phenomenon is defined as
4k {1....,
(wx Uk+1)
++1
(39)
and Wx W + fnيu as l + ou along the training trajectory, where uk, are the left and right singular vectors correspond to the largest singular value of Wk.
The proof for the alignment phenomenon of adversarially trained deep linear networks in our setting as follows
Proof. Note that
(uk, uk+1) 12 = up WT+ Wh+1 + uf (UR+10 - W W
(40)
we have
WT. WK+1 U k+1
W 12 |
S (un,vu+1) 5
(41)
of
by utilizing the definition of matrix norm and
|| 2 ux WT Wa+1UK-
(42)
According to Eq. 36 let
I& WT. (0) (O) + As+1
Bk.
(43)
and replace W
k++ 1 with F& W&WWiin in Eq.
41
we have
of
o Taus +
W
(ux, 2k+1)
(44)
k+1
To prove the alignment phenomenon, now bound the RHS of Eq.
44 with where
when / + oc. We are going to bound 3 terms, namely uf TT Tau.. W
W& and /
1. Bound ui TuuR.
u Tgu 2 -uT (O) uk TI BAuK
2 20) 1r (Br)
2 2-IIW( 2C))
(45)
where we used Eq.
38 in the third inequality.
2. Bound ||
W& 112-- According to the definition of singular values, we have
W l1 o. of W&W uk+1
- ( k+ W Tx)
> o 1 (0 - tr (Bx)
(46)
'Some parts of the proof inspired by Ji & Telgarsky 2019
16

---

Published as a conference paper at ICLR 2022
where (W) = W& (O) WT+ (0)We+1 and used that (Bx)
Bxll2
in the second inequality. On the other hand, by taking trace of both sides of Eq. (36). we have
I | Wi++lli- WW++1(0)1 || tr +
(47)
Combined with Eq. (4)), have
[W&112 |Wall > [ || 1+11
(I[ (0) - -
+ (tr (Ax+1) tr (Bx)) - tr (Bx)
2 1|W++2122 - -1
+ (1] - -
- (W + (0+)
+ (Ax - tr (Ba)) - (Ba) + tr (B++1)
IV
I-1
[W)(3 (0]
Σ F==
AW
Σ tr (Bxr k'=
+ (At) (B&)
M - (T)
(48)
where a follows from Eq. (37): b follows from summing a from k to T. and that
[Wrl2= = |[LLlF;; C because Eq. (38) and that
L-1
M = min (0) (O)
Σ
(0))
(49)
W=k
is finite.
3. Bound 0 k+1-
Eq. 446
gives us that
o
(0) - tr tr().)
21 k
(0) + 2C(W(())
(50)
of k+1
2
o
where of (O)ok++ + 20) finite.
Putting the bounds obtained from the above 1, 2 and 3 back to Eq.
44
will give us
(4k, Uk+1) 2 (0) 12 2(L (W M + of (0)
(51)
o
Considering that 0g and the numerator is finite, we thus conclude that the RHS of Eq. (11 will converge to 1. Therefore, we have that
(uk, Uk+1) 2 +
(52)
t oc. Furthermore, since ||W++111 - | is finite (see Eq. (48) and o (i.e.,
||WIIB//\W// + 1), have Twalle - u because other singular values are negligible. We now have the alignment phenomenon.
W
Furthermore, we have
WTT
un + mn-
(53)
W2
We now move forward to prove the alignment phenomenon for the first layer. We assume that the support vectors span the data space and denote the orthogonal complement span(2) (ū) by a- Let Pı denote the projection onto h Under this assumption, Ji & Telgarsky (2019) showed the following lemma
TThis lemma is based Lemma 12 in Soudry et al. 2018).
17

---

Published as a conference paper at ICLR 2022
Lemma (Lemma 3 in Ji & Telgarsky (2019)). Let S denote the set of indices of support vectors, then with probability I.
min 11 iES
max (5,3,)))
(54)
the data sampled from absolutely continuous distribution.
To begin with, we first introduce the following lemma.
Lemma 8. For the logistic loss function 8. = 1n(1 ln(1+e=)), if (Wn, ū) 2 0 [P1 2 2n/en
s, then
ac
P W1, OW1
20.
(55)
Proof. We first decompose Eq. (55)
as two parts:
2c P1W1,
n
0f W)
0 ||Wlll
)}
PLW1,
PLW,,
(56)
OW1
π2
OW1
OW
where
P W1.
(P1 WT ... WEW W2)
OW,
[
(P1 P1 Pn) 2 O.
[Wnll
Since i'
0, we have
ac P1W, 11, OW,
af(za W)
Σ Ey P1W1,
Σ
P WH,, 2.. (57)
aw
1=1
Let 25 E arg maxes
(-P1 Wn, z.yi) which means that (-Pi Wn, 2yus)) xl|Pi Wnll-
Then we have
Pi Wn. x.n (WT))
n
1
(5)
P Wny
(Wa
n
1
Σ
(W
(11, P1x;91)
+ (W
d=1
1
- (Wa,():+5)))))
(-PL Plx.y)
12 ++e (Wn
1
e (W)16))+4))55)
(ms
(-P1 Wn. PlzmD)
e (Wn,(su (-P1 Wn. Pi
n (Wn.
kEC,
(58)
where C+ [k: (-P Wn, P_ayy)) < 0}. Considering that ZyMy is support vector, the first term of (58) can be bounded as follows:
e (Wn.())66)bs))
(Wn.6))6))))) PI Wn. P1oay))
-Win
PP Wwlll---Winneee (W
>
+ e- (W,
ePP__ Pia
P Wnlle - (Wunna) ( (WWlll
+ e Wille Wn.P Wi,Pi (WWn)))) (Wn.70)
K
P, Wn le -fille-WWn,dd (Wn,7 e|[]]
(59)
2n
18

---

Published as a conference paper at ICLR 2022
where that cl| Wills (Wi, yu), (P1 Wi, PLæzUR) 0. Each term of the second part of (58) can be bounded by
6 (Wn,
14c (we (-P WTT, PIzaa))
e (Wn..a ( (-P_ PiTNyK)
elWWill (Wn.71)) é (Wi.. 74) (-P1 Wn. P P17UK)
wellWnlle- ( (Wn.ra) - (-P1 Wm. xuve) (-P1Wn PIZANA
(-2)-
(60)
where the second inequality follows from
(Wn, TbyK - -Yū) = (WIT, P1x191 + (W1, Z23A PITADR -u)
2 (Wn, PITxUk) (P1 Wn, MitWnnPPiaa PITADR)
while the last inequality comes from f(x) xe 2 -1/e for x 2 Finally, we have
(PI WT., (xt d.)y; ).)):((Wi)) -Win,aa) ellWiill (NlIP_ Wnll 4
(61)
2n
Therefore, (PL Wn, (x; + +.))) (W))) 2 if
2n
|| Wnll 2
4.
(62)
CK
We are now ready to prove the alignment phenomenon for the first layer. Let P1 W1 denote the projection of rows of Wi onto ū- We start from exploring the asymptotic behavior of PP Wile when - cc. The update of P_ W1 + 1) can be written explicitly as
[[il
|P (t + 1)
ac PLWi(t),P_ (1)
P ac aw (1)
||P1 (07(0)
702
ac P PLWi(t),P P @W1(1)
ac
< ||PW) (0)
+ (02
OW (1)
ac
WI (0)
P. (1(),
+2 (E(W(L 1)) E(W(I))
(63)
(t)
where the last inequality follows from Eq. t 2 to. we have
30). We define large enough step tn as follows: for any
2
ac @W1(t)
ac @W1(t)
Wi - 1)11 (W)( 2n(t)
(1)),,
+ (nt))²
2 (t)l
F
(64)
where "large enough to" means that
4²2 + E(1o)
(65)
| [
as [| + xo. Suppose that there exists a 1, to such that
| Wn 1)]le < & and [P (P))lll 4,
(66)
19

---

Published as a conference paper at ICLR 2022
which is to say (recalling Lemma 8
ac Pa (I))()) WWi(t)
20 ( + 1) - (P 2 ((W
(67)
for to t1 St to and t2 if we never have |PP_W(lt)ll after t1. If there does not exist such a 1, then we directly conclude that IP Walle since || -> oc. On the other hand, for any to I t t t
IP + (E(W(h)) - -(W(()
Pa W (+)I W (O1F
P Wi(()) (((((()))
[11
x² + 2u(11){ + (²(L)) + 22(W((1)
$(p, t2)
(68)
[t
where the last inequality follows from Eq. (31) and (f(,, (1) defined by #(p,,t = x² + 22((t)p + (t)) + 22(W 2 ((p,t')
(69)
for any 2 1 because the loss and y never increase. Therefore we can conclude that
(P)W)
t(g.t) I p(p,tz) - IW: [[
(70)
for any 1 2 h1 As result,
(t)
(71)
B PROOFS OF SECTION 3.2
We present some useful properties and proofs of Lemma 3 and Lemma 4 in Section B.1 Section B.2 focuses the divergences of weight norms. Section B.3 is about the convergence KKT
points(Theorem 5)
Additional notations We use Wijsk to represent the i-th row j-th column entry of the k-th layer
weight martrix.
B.1 USEFUL PROPERTIES AND PROOFS OF LEMMA 3 AND LEMMA 4
For any m X n matrix A, we denote v(A), an mn-dimensional vector, as the vectorized version of it:
An
A2i
v(A) =
(72)
Am1
Amn
then the trace operator be represented by
tr BA u(A)" uBB) =BB) v(A). (AA)
(73)
We first introduce the Fuler's theorem homogeneous functions.
20

---

Published as a conference paper at ICLR 2022
Lemma 9 (Euler's 's theorem homogeneous functions). If f(W...... ,.. is positive multi-ck- homogeneous function
S..WW....PPW.. = II Pk (W....,,W,
(74)
k=1
for positive constants pic" and Ck 1, then have:
(W .......... WL) Wa (Wi,... WL).
(75)
oW
Proof. Taking derivatives of pk both sides of Eq.
(74) for any given & E {I,...,L., we have
0f Wk: OW
0s
L II
tr We oW
Pi f(z;; W)ckkh c0-1
(76)
k
Since Pk: is arbitrary, we let PL
Pk
P1 then the above equation becomes
W/ @f(WW....,, .W/)
cu caf(WW W2)
(77)
OW
for any E LJ..
Furthermore, we have
Os(a; W) OW
(oS(;; OW
W
Σtr
WR
k=1 kx,,
(78)
where K = Eken Cg. For the deep neural networks defined in Eq. (2) with homogeneous property. we can then apply the above lemma to them.
We examine whether Assumption 2 can still be applied to adversarial margin under Assumption 1
Lemma 10 (Assumption 2 for adversarial training). For any fixed
uf; W) is locally Lipschitz, then so does yf(x + 8(W); W) with perturbation 6(W).
Proof. For fixed x, suppose (fV is locally Lipschitz on Y, then for each W Y there is Zw containing W such that (W) is Lipschitz on Zw:
(lbs(W) - vVVll < TwlIW- - V|I for W.V C Zw-
(79)
For the adversarial perturbation, by definition 5(W) and 8(V) are solutions of the inner maximization for the adversarial training, other words,
yf(x + 8(W); < vf(x + W(V);WW yf(z 8(V); < yf(x ([
(80)
(81)
because then will have {(x + 5(W): {(x 8(V); W) since is non-increasing As a result.
under Assumption]] [
yf(x + 5WW): - yf(x 8(V): S yf(x + - +
Lw W -
(82)
for yf 8(W); yf(x 5(V); V). The result for yf 8(W); y 6(V): is similar.
V'i v. (s,; W) have locally Lipschitz gradients, then do ys f + 5,()): W).
21

---

Published as a conference paper at ICLR 2022
Proof. For fixed x, suppose y fWW) is locally Lipschitz Y, then for each W Y there is a Zw containing W such that y yV f(W). 6(W) are Lipschitz on Zw, for W, V C Zw:
1 (x; ( - [ V)Il & LwIWW- - -V
(83)
11vV ((W): v4 6(V); W\ll Tw (wwllo(W) 8(V)
- Lwa Lw V1
(84)
Then
11 V s(: (W)); W) 31 V + 8,(V); V
11 V J + (W); W) - 1/4 V/(x + (W);; V)Il
+ 1l1s ff(;; + (:W V) - 31 VV + V(V)
- (Iw + [ws) W -VI-
(85)
B.1.1 PROOF LEMMA
Proof. The proof can be done for note that
networks as defined in Lemma
We first
Wef(:::Wi............ = II P (n; WL)
(86)
1=1
by taking derivatives with respect to x on both sides of Eq. 74).. Therefore VaJ(x; Wi,..., Wt.)
also positive homogeneous. Under Assumption [ we prove Lemma in the following cases:
1. FGM perturbation. This perturbations taken
eyL V ff; Wi....,
Ey f1; WL)
ÓFG
(87)
y 2 W...... Wz)
[V W Wi..... Wx)l
because &' Invoking Eq. (86). we know that
ey II P 2 V zs (2; WT... w...... Wz)
8FG =
Ih c+ V fx; W1,..., WI)ll
ey ax; Wi.... W1)
VV,/( W W....., WL)l
6FOM (W,, Wz).
(88)
2. FGSM perturbation.
8PUsM| (W) esgn ( a=; WT.... W2)).
(89)
where sgn() denotes the sign function. Then we have
ÓFGsM( W ... (T.W) esgn ye
Wa .Wy)
-FGSSM (W)
(90)
since Pk for any & thus will not affect the sign operation.
3. E2 and 4x.-PGD perturbation. We only prove the case for lg- PGD and the case for loo- -PG
is similar.
b+t((W) = PPs...)) (wo
Va, W Wr.)
(91)
[V WI,...,W Wz)
22

---

Published as a conference paper at ICLR 2022
where PB(O..) denotes the projection operator, B(0, <) is the perturbation set, is the step indices of PGD and Ç the step size. We prove by induction. For j = 0, we have
Waf(<z; ,I....,, W2) V=](<; WT..... W2)Il
PGD Wi,... P..W.) PB(O.))
8RGD (W WI..... Wz).
(92)
If we have (p
(W1 WL). then for j 1, we have
8 (PD - y/ I Ps V vx WT..... WL)
(eD Pr....,,PWW.. = PB(0,e)
II Pk I V= W Wi...., W
(W) - y V W..... WI)
PB(O.e)
[V, W Wx)l
Spc (W1,, 1..... W.).
(93)
Therefore, these four adversarial perturbations are all scale invariant adversarial perturbations by our definition.
B.1.2
PROOF LEMMA
Proof.
This can be easily proved by noting that, for any multi-cg-hoomogennuus functions,
L
+ (..
PL = II
p 6 WL); W
WL)
k=1
(94)
because 5(W) is a scale invariant adversarial perturbations. Then f(x + 8(W); W) is still a homoge- neous function and Lemma 9 can be applied f(x 5(W); W W...... WL) and have
ac OW
Of(c: +o(();; W1. WL) WR
WR
OW
C₁
%/c "g:f(x; + &o(WW;; W,, Ws)
Ck
(95)
n
Taking C1 cL gives Lemma
B.2 DIVERGENCES OF FROBENTUS NORMS OF WEIGHT MATRICES
B.2.1 DIVERGENCES OF ALL LAYERS
Lemma 11. The Frobenius norms of all layers grow at approximately the same rate along the trajectory of gradient flow for adversarial training with scale invariant adversarial perturbations for multi-cy- homiogeeoss DNNs
1 d W2
1
d W WL
1 d Wi
(96)
Cr.
CT.-1
dt
dt
Remark. Note that a similar conclusion as that of Lemmal I1 training for multi- l--ooggeneous networks Du et al. (2018) We generalize this property to the adversarial training of multi-c, c--oomgeeneouss neural networks. When ej = ... = Cr. we have that all layer grow at the same rate.
exists for gradient flow of the standard
23

---

Published as a conference paper at ICLR 2022
Proof. For any Wk.
d
d
W
Wijthhi
W
ac
T
-2
2
W jesk
dt
dt
WWyj
i.j
2Ck
a
(97)
11
where dW
and Lemma 4 One then immediately notice that the above equation does not depend on any specific k. thus we have
ac
oW
WL 13
d L-112
d 11?
(98)
dl
CT.
di
C1
dl
B.2.2 PROOF OF THEOREM 3
We prove this theorem by exploring the time evolution of p.
Proof. We start from a -hmmoeeeoos function then take f(z; W. pf(x; W) where Wi Ws/ ||W*]| and
CD. Recalling
I
x II
W
(99)
k=1
the adversarially trained predictor with scale invariant adversarial perturbation is still homogeneous (see Eq. (4)):
I [ ((W): w) pʃ (sr ((W):
(100)
For Pk [. have
dpk
Ck
(101)
dt
npk
by invoking Eq. 97 The dynamical evolution of p will then be
dp
dp
Σ 72
(102)
P
1=1
Let to denote the time such that all worst adversarial examples correctly classified. We study the trends for after lo. On one hand, the empirical adversarial loss does not increase:
dc ac dW dW 2
0.
(103)
dt aw dt
On the other hand, recalling our definition of normalized adversarial margin, let
m arg min tt arg min iE(! (E(......)
p% ic i
(104)
and note the definition of to. have
e fm < Σ c -
7m 2 In
2 In
> 0
(105)
n
C(t)
L(to)
because E does not increase and ā(t) < E(to) 1. This also implies that 7m thus 7y for all i E (1)....n.. be arbitrarily close to which a contradiction. Therefore we can immediately conclude that dp/dt > in Eq. (022, which implies that p may diverge t co. To have clearer view
not be arbitrarily close to 0. Otherwise one would conclude that L(t) may
24

---

Published as a conference paper at ICLR 2022
about the convergence property of p. we study the following relation regarding the time evolution of (Pu.((ctto.(W) after to:
de Ke.
dp
df + 6;(W): W)
+
Σ e
Pl:
(106)
dt
dt
dt
(a)
(b)
The term (a) can be computed by invoking Eq.
102
(a)
TTP
Σ 0
k=
G2pp
n
2
+
9t's
(ce(in
eppls -0060-1))))
n.pk
i=1
x2
p²C² npk
(107)
k=1
k=1
where the first inequality follows from x/x 2 2 for 2 0 and we denote the minimum of Σ: 9/ for 2 to as Ç > The existence of such Ç has been discussed below Eq. (00)).
The term (b) needs more analysis. For any fixed adversarial example z, + 5(W), we have
(f: + 8,
L
@f((: + 6,(W); W dWr
yi
yo
tr
(108)
dt
OWn
dt
where <W&/dt can be computed follows
dW jlik
aw
stk
dW mn:k
dt
a mngk
dt
ma,
Wark
dW mank
Σ
aw monk
Vtr (WATT)
dt
dW juck
W jiik
Die Ui
(109)
Pk
dt
T&kk
On the other hand, we that
dWR
ac
05(0; + dWW);; W)
T
Σ Of(a;
dt
+ W:WW):
OW
P Σ Uje 35 @ff(z (WW
(110)
npk
aWk
because 0f(W)
( OWe Pk aw
Combing Eq.
1199 and Eq.
110
we have
[f((z + 5,(WW;; W) ) T
dW, dt npk
Σ Use -
is
(111)
aw,
Therefore
dWs
P Σ yie to Agu
@f(2; + +o;(W); W)
(112)
npk
ow
25

---

Published as a conference paper at ICLR 2022
where
(WZ) (WZ)² 7
A₁
W
W
(113)
W P.
can be seen as projector operator. Putting Eq.
112 into Eq.
(108)
will give us the expression
T
of (2; 5c(WW); W)
(W)(W)
(Q:(WW)
y/s
Af v
(114)
OW
OWn
Now the term (b) in Eq. (106) is, by putting Eq.
114
back into
07 OW
T
0%
(b)
Pi
Σ
e
Pisu
Al
0
TIPE
Ow
k=1
L
0%
89/
V
A A
(0(3--0) + p(
(115)
2
W
1.j
(c)
Rearranging e 93) + (( as follows
el(t--9) + e p(%--t) ( + t - -6e9 - -E-S) pP)
will allow to rewrite (c)
09 ei A&u
OGis OW
(c)
Σ of
ALU
OW
0his oW
Σ (e0 -E-
0%
0%
Σ
c Akd
+
Pic A
aW
OW
0%
0%
Ugu
A&
OW
OW
2 0.
(116)
Combing Eq. 1007 and Eq. 116 with Eq.
(166), will have
d ( (WW
(())2
(117)
dt
p2)p((t)
1=1
According to Eq. 101), we know that Vk dpa/dl bounded by its value at to for E [lo, 2o) because
0 after lo, therefore Vk: p2/2 is lower
d
2 d
II
2016 PK
Pk
dt
dt
# W
=2(ck
1)p 3
Pk
II
Pk
200
Pk
20
2cw Pk)
20v -1
pi
II
Pkr
200"
0,
(118)
where Py denotes dpx/dt for any & due to Eq. to to gives us
101). Integrating both sides of Eq. 117 from
(²())22 dr n2 p (T)
Σ (cetOm//l::b (olto),.
p² (tn)s (t to); (119)
n²p
26

---

Published as a conference paper at ICLR 2022
where the last inequality follows from Eq. (188 Let t - oo in the above equation, will have
(In + oc
(120)
since yzf(z, + (WW,); weights have norm and is lower bounded as discussed before. Taking ej ct. gives us the conclusion.
); W) is upper bounded, which can be easily deduced considering that all
Note that p .... and Pk for any l grows at the same rate for homooge-oos functions
(Lemmal [1]. we immediately have
L): Corollary 1. Ak E (1....,L): Pk 00 as + cc.
B.3 CONVERGENCE TO KKT POINT
B.3.1 PROOF OF THEOREM
Proof. Most calculations needed for the proof of this theorem have been done in Section B.2.2
According to Eq. (14], have
Σ
e Fg
df + 6:) W
L
E
Ee
(8,(W))
Af
(%)(W)
dt
OW
OW
k=1
L
09%s
Σ
Σ
Fu
Ake
2 0.
(121)
OW k
B.3.2 PROOF OF THEOREM 5
The KKT conditions for the optimization problem Eq.
19 are
app
72
0%
vk:
(122)
20W
aWk
Vi E (l...., n} A Ar 1) 0.
(123)
Following Dutta et al. 2013 Lyu & Li (020). we define the approximate KKT point in our settings Definition (Adapted from Definition C.4 in Ln & (2020)). The approximate KKT points of the oplimization problem 79 are those feasible points which satisfy the following condtions:
1.
all
9% MW
S
2
OW
2. Vi E (I...., n} A177
1) E.
where X, > 0 and X 2 0. These points are said to be (x, -aprrxxiiie KKT points.
We now present the proof Theorem 5
Proof. Let
W
P
(124)
W
V
(125)
7m
where K= = -th C c= cl. Since
cf W) c./ (x; V)
(126)
27

---

Published as a conference paper at ICLR 2022
according to the definition of the mulltic-homoogneouur functions and
af(2; W)
c((xzVV== = -Vi.. af(x;V]
(f(x;W)
Wks
(127)
oW
0V
have
0f(z;V] v) OV
0f(;;
(128)
7t (K-1)/
OW
Specifically, in the following, we will show that V is a (x -aprr--apoo KKT points of the optimization problem (19) with x. -> along the training trajectory. Because the homogeneous property the network trained with scale invariant adversarial perturbations, it satisfies the MFCQ condition by simply noting that
Vi E [I....,m} tr (
0i Wi OW
ct: > 0.
(129)
This makes point being a KKT point necessary condition for be the optimal solution.
We now show that the limit point of V along the adversarial training trajectory is an () -apprxximat KKT point with X. starting with the first condition. Let
-(1100 ac aw
))
x; =
(K2)/KK e-,,
(130)
then we have
Of(r; + (VV) (L): V)
A
0f(r; + (W);; W)
V
Σ
Asni
0V
7:11
(K 11/K Tm
aw
ac W,
2(En P?.)
aw
(l. P 20)1/KK711 2/K
II
OE 20
(,
BE aw
2Lp
x(t)
(131)
Pk. 7/m.
22/K
||
ae
SW
where a follows from 128
K' arg max; Pk and k" arg ming Pk- This is the first condition for the limit point of being an approximate KKT point. We can further show that X + 0 as by noting the following alignment phenomenon which (2020) and intended for standard training with fixed training examples:
originally observed by Ji & Telgarsky
Lemma 12 (Adapted from Theorem 4.1 in Ji & Telgarsky (2020)) Under Assumption and
Assumption 4 for exponential loss and homogeneous deep neural networks, along the trajectory of adversarial training with scale invariant adversarial perturbations, we have
(W),,,
ac
(t)
SW
Vk E (1,..., k) lim
11
(132)
||]
ac aw
(t)
The extension of Theorem 1.1 in Ji & Telgarsky (020), which intended for fixed training examples, to our settings is because, by our construction for adversarial training with seale invariant adversarial perturbations, the adversarial training margin are locally Lipschitz with locally Lipschitz gradients and the prediction function f(x + o(W); W) is positively (multi)homogeneous with respect Wsee Lemma 10 and Eq. (4)). Invoking Lemma and considering that in can not be arbitrarily
close to ( and vkc + oc at the same rate according to Lemma 11 thus Px' can not be infinite, we have.
Per
lim (t) + 0. (000
(133)
*See Eq. 1055 In fact, it keeps increasing after time according Theorem
28

---

Published as a conference paper at ICLR 2022
On the other hand, the second condition for the limit point of V being approximate KKT point is
n
A 7
|
ac
1)
9m))
Ym
22/K
OW
im
F
Ex P
7u (.%
Fmm
/²/ K Ri1
OC W. aW
ne 91 (7: 7/m
12 Pm
Kpe Pm E5 f
+ (W)) W)
Σ pk
ti -m 3m
Σe
2(3--99m))
Kpl Kpl+2/
2/KK
Pm
Σ EkPl Pk
12/ (2/444///++2/// 2
nT.pk.
Keppl.. 142/KK E,
(134)
where a follows from (W, 02 - [W] aw
ac b is due to Lemma 4 and Vi : 9/6 2 7m C uses aw
Vi 5. 2 7m again; d is due to e =xx is upper bounded by its value x for x 0. Since p
not be infinite thus vk: limm (t) - at the same rate, conclude that lim L
lim; E(t) + O because 9m not be arbitrarily close to 0 and lim, P co. Therefore, the limit point of V is an (x. appprrxxiie KKT point of the mini-norm problem along the trajectory of adversarial training with scale invariant adversarial perturbations where lim; x(1), E({) - O. Restating the theorem in Dutta et al. (2013) regarding the relation between (x, aapproxximae KKT point and KKT point in our setting:
Theorem 6 (Theorem 3.6 in Dutta et al. 2013) and Theorem C.4 in Lyu & Li (020 Let {x, t N} be a sequence of feasible point of the optimization problem 79
Ie is an (Xe, Et) approximate
KKT poiint for all with two sequences {xt > 0 E N} and { > O: t E N and x & + O. If
Ft + x as oo and MFCQ holds x, then x is a KKT point of this optimization problem.
We then immediately conclude that the limit point of [W[t)/[[] :t 0} of gradient flow for the adversarial training objective Eq. (6) is along the direction of KKT point of the optimization problem 19
B.4 GENERALIZATION TO NON-SMOOTH CASE
is not hard to generalize the current analysis to non-smooth case, which will include the deep ReLU network, because, in our main steps, there counterparts of our conclusions for non-smooth case for that sub-differential (Clarke, 1975) is a generalization of gradient. The non-smooth analysis can be done by first replacing the gradient flow equation Eq. (16) with its generalization,
dW
dt E (C((((())
(135)
where Ot)) the sub-differential. Then one can follow similar procedures as our approach to make the generalization.
Proof. For simplicity, we only consider multi- -homogeneous networks here, i.e., Ci = =.. = c₁. = 1, which include the deep ReLU neural networks. Lemma can be generalized to non-smooth case according to Lemma C. in & Telgarsky (2020) or Theorem B.2 in Lyu & Li (2020):
Lemma 13 (Lemma C. in Ji & Telgarsky (020 Suppose f R" + R is locally Lipschitz and L-positively homogeneous, then for any W E R and any W E Of(W),
(W, W*) T.(W).
(136)
29

---

Published as a conference paper at ICLR 2022
The starting point of the proof for Lemma promoted to handle the non-smooth case.
B is the homogeneity of f(; W) and can be easily
With generalizations of Lemma and Euler's theorem homogeneous functions for non-smooth case, the proof of Lemma 4 can also be generalized to non-smooth case accordingly because is based the Euler's theorem homogeneous functions and Lemma 3 for adversarial training. Specifically, it will become
dW dt
W
(137)
The proof of Theorem aadopts Lemma 4 and can be generalized to non-smooth case by combining the chain rule (Clarke 1983) for gradient flow to ensure Eq. (103)
dW dC - (L(((()) dt
dW
2
(138)
dt
dt
with similar approach as in Lemma B.9 in & Telgarsky (2020) or Lemma 5.2 in Davis et al. 2018)
Then generalizing the rest of the proof of Theorem straightforward.
Finally, the generalization of Theorem 5 to non-smooth case can also be done because it adopts Theorem 3 Lemma the chain rule, and the gradient alignments Lemma 12 which holds for non-smooth case.
B.5 DEEP LINEAR NETWORKS ADVERSARIALLY TRAINED WITH fox PERTURBATIONS
Following the settings of Section 3.1, the fe perturrbaaion for deep linear networks f(;; W) Wr. Wix be given exactly
=
8(W = sgy -ey.sgn(WW(()).
(139)
According to Theorem 5 the adversarial training solution is formulated from solving the following optimization problem:
max 2
|W12
(140)
s.t. min 3: Wn.; W||Wi 2 1.
(141)
iE (E......))
can be seen that this optimization problem, a mixed-norm optimization problem, will have different solutions when compared the margin-maximizztiin problem of the original data, which will lead to different decision boundary distinguishing adversarial training methods from the standard ones.
Besides, the constraint (Eq. K for f2 perturbation) should also be changed accordingly such that the adversaria training examples are still linear separable:
S 7m,1
(142)
where 1m is the max-6 -orrm norm margin:
1m,1
max min y,uzz | (E (E.......
(143)
C SUPPLEMENTED EXPERIMENTS
C. ADVERSARIAL TRAINING WITH DIFFERENT LOSS FUNCTIONS, ARCHITECTURES AND VARYING PERTURBATION SIZES
We present the results for adversarial training with different loss functions, architectures and varying perturbation sizes in this section to further verify theorems and assumptions. We use two different models: one is a 3-layer neural network with the same architecture as that in the Section the other www.nnggg--cc
is a CNN with architecture where Conv stands for convolution layer, FC stands for fully connected layer and Pooling is max-pooling layer.
30

---

Published as a conference paper at ICLR 2022
0.04
adversarial normalized margin
0.03
0.02
0.01
0.00
-0.01
FGSM, 8/255
FGSM, = 12/255
-0.02
FGSM, 24/255
PGD, & 8/255
-0.03
PGD, c 12/255
-0.04
PGD, 24/255
500
1000
1500
2000
2500
epochs
(a) Adversarial normalized margins for varying perturbation sizes
100
adversarial training accuracy
98
96
94
FGSM, 8/255
FGSM, = 12/255
FGSM, 24/255
PGD, 8/255
PGD, = 12/255
86
PGD, 24/255
100
200
300
400
500
epochs
(b) Adversarial training accuracy varying perturbation sizes
Figure 2: Adversarial training for the 3-layer neural network on MNIST perform binary classi- fication. The perturbations used for training are FGSM and PPG perturbations with varying perturbation sizes = 8/255, 12/255 and 24/ 24/255. The adversarial normalized margins and adversar- ial training accuracies are evaluated with the corresponding perturbations used for training.
For the 3-layer network, we conduct adversarial training using both FGSM and & -GD perturbations with perturbation sizes c = 8/255, 12/25 and 24/ 24/255 to perform binary classification where we choose all examples with labels "3" and "8" from MNIST be our dataset. The loss function is logistic loss. Fig. 2(a) shows that for both FGSM and -PG perturbations with varying perturbation sizes, the adversarial normalized margins during training keep increasing after some step. Fig. 2(b) reveals that the adversarial training accuracy can achieve 100% (after ~ 200 epochs), which supports Assumption 4.
For the custi-classification task, let f(x; W)[i denote the j-th output. Then the margin for an adversarial example x; + ò; corresponding the original example x; defined by
f/ f(z: 5;; W)ss
max f(a; + 8, W)Li)
31

---

Published as a conference paper at ICLR 2022
adversarial normalized margin
0.2
0.0
-0.4
FGSM, = 16/255
-0.6
FGSM, 32/255
PGD, & 16/255
-0.8
PGD, 32/255
100
200
300
400
500
epochs
(a) Adversarial normalized margins for varying perturbation sizes
adversarial training accuracy
100
FGSM, = 16/255
FGSM, 32/255
PGD, 16/255
PGD, E 32/255
0
100
200
300
400
500
epochs
(b) Adversarial normalized margins for varying perturbation sizes
Figure 3: Adversarial training for the CNN on all training examples of MNIST to perform multi- classification. The perturbations used for training are FGSM and -PD perturbations with varying perturbation sizes 16/255 and 32/255. The adversarial normalized margins and adversarial training accuracies are evaluated with the corresponding perturbations used for training.
32

---

Published as a conference paper at ICLR 2022
and the margin for the adversarial data is defined to be
7m
min (E()....))
%
Then for the CNN, conduct adversarial training using both FGSM and & PPG perturbations with perturbation sizes = 16/255 and 32/255 to perform custiiclassiiicationn on all training examples of MNIST to verify our claims and assumptions when the perturbation sizes are large. The loss function is cross-entropy loss. It can be seen from Fig. ((a) that the adversarial normalized margins keep increasing after about 250 epochs, i.e., after the model fits all adversarial training examples, for all adversarial perturbations. Fig. ((bb clearly shows that the adversarial training accuracy can reach 100% for all perturbation types and sizes, even the large size e 32/255.
These experiments show that adversarial normalized margins are different whenever perturbation types or sizes are different. All models adversarially trained with all perturbations and loss functions can achieve 100% adversarial training accuracy, which verifies Assumption 4. Moreover, the trends that adversarial normalized margins all keep increasing are clear, even long after the separation of adversarial training examples. These results well support the claims of Theorem 5.
C.2 EXPERIMENTS ABOUT 22-FGM PERTURBATIONS FOR BINARY CLASSIFICATION
1.0
109
adversor al trahiing standierd traiiing
0.5
00
0.0
80-
-1.0
-1.-
73
-2.0
60-
-3.0
59
1.00
200
300
4000
100
200
300
409
spochs
aoochs
(a) Eg F2M adversarial examples
(b) Adversarial training accuracy
Figure 4: Adversarial training for the 3-layer neural network on MNIST. The attack method is f2-FGM with e 8. (a) Adversarial normalized margin for 42-FGM adversarial examples during adversarial training and standard training. (b) Adversarial training accuracy for 22-FGM adversarial training.
In the MNIST dataset, we adversarially trained a 3-layer neural network with the same architecture as that in Section Jusinn SGD with constant learning rate and batch-size 64. To have a clear view about the difference between the implicit bias for standard training and adversarial training, the adversarial perturbation used for training is f2-FGM perturbation with e = 8 since even the standard model can fit 2-FGMM adversarial examples easily in the MNIST dataset when the perturbation size is not large. As comparison, we also standardly trained a model with the same architecture to evaluate the normalized margin for adversarial examples by attacking it with e fg-FGM during its training process.
As showed in (b)] the adversarilly training accuracy reaches 100% very quickly, which supports Assumption 4 It can be seen in Fig 4(a) that the adversarial normalized margin keeps increasing dur- ing the adversarial training process while the standardly trained model maintains a lower adversarial normalized margin.
C.2.1 EXPERIMENTS ABOUT EXPONENTIAL LOSS
For completeness, we also conduct experiment about the binary classification where the model is adversarially trained with exponential loss (Fig(5) for FGM perturbations. We select the examples with label "2" and "8" from MNIST and adversarially trained a 2-layer neural network using SGD with constant learning rate 10 10-5, 5 The hidden layer is of size 10000 and the activation function is
ReL.U. The normalized margin for adversarial data defined exactly as in Section 3.2 The adversarial
33

---

Published as a conference paper at ICLR 2022
adversarial training
0.0025
2000
4000
6000
B000
Figure 5: Adversarial normalized margin during adversarial training for binary classification. The loss function during training is taken as exponential loss.
1.8
1.0
0.8
[[h]]
[Wel]
0.6
[Wal
25000
23000
30000
3000
33000
epochs
epechs
(a) 4-layer deep linear network
(b) 3-layer deep linear network
18
144
1.0
0.8
[|all
5000
30000
15600
20000
25000
30502
epochs
(c) 2-layer deep linear network
Figure Frobenius norms for weights of deep linear networks with different layers during adversarial training. The perturbations are & perturbations.
perturbations during the adversarial training are given by FGM with = As showed in Fig 5 although extremely slowly, the normalized margin for adversarial data gradually increases during the adversarial training.
C.3 DIVERGENCE OF WEIGHT NORMS FOR DEEP LINEAR NETWORKS DURING ADVERSARIAL TRAINING
We conduct adversarial training of deep linear networks with & perturbation a linearly separable dataset. The loss function logistic loss. Specifically, we use deep linear networks with layers 2, and 4, respectively. Since the divergence is slow (~ In t), it is hard to observe that [W&l|r co.
34

---

Published as a conference paper at ICLR 2022
6(b) and Fig. 6(c) the trends that ||alle for all layers of deep linear networks with different layers keep increasing are clear. Furthermore, we can see that the ratios ||&ll2// /I W for all layers of deep linear networks with different layers also keep increasing, as
However, showed in Fig. 6(a) Fig.
showed by Fig. 7(a) Fig. 7(b) and Fig. (cc)
1.00
[P9 (bdlR IF
1.0
0.3
0.0
0.80
0.75
0.20
0.6
[Woll
30000
(a) 4-layer deep linear network
(b) 3-layer deep linear network
1.50
0.85
5000
10000
15020
20020
25000
30003
epochs
2-layer deep linear network
Figure 7: Ratios of 2-norm and Frobenius norm for weights of deep linear networks with different layers during adversarial training. The perturbations are lg perturbations.
35


Reviews:
[{"review_id": "uh2MtzVXN-4", "reviewer": "Reviewer_uXwk", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "*Implicit Bias of Adversarial Training for Deep Neural Networks*\nanswers a prevalent question in the theory of adversarial robustness:\nhow exactly (in closed mathematical form) does adversarial training\nimprove adversarial robustness? The paper proves a theorem stating\nadversarial training produces an implicit bias on the normalized\nweights $\\frac{W}{\\lVert W \\rVert}$ (with a more precise statement in\nSummary Of The Paper). The majority of the paper is clearly written\nand correct. The paper's results place a milestone in the theory of\nadversarial robustness. However, the proof of Theorem 2 may have\npotential errors (which may be from my confusion on some statements\nand notation). Adversarial training in linear neural networks is a corollary to Theorem 5,\nso any potential errors in Theorem 2 do not invalidate Theorem 5's results.\n In addition, there are several statements and notation\nthat are vague and ill-defined in the theorems. This makes the exact\nstatement of the theorems difficult to ascertain.\n\n## Potential errors in the proof of Theorem 2\n\nLemma 5 requires a constant step size $1/\\beta(r, \\bar{r}, \\epsilon)$\nfor\n$$ \\beta(r, \\bar{r}, \\epsilon) = r^{3L}L^2\\left[ \\alpha + \\beta +\n\\frac{\\epsilon}{\\bar{r}^L} \\left( 2\\alpha + \\beta + frac{\\alpha\n\\beta}{\\bar{r}^L} \\right) \\right].$$\nThe constant step size implies in Lemma 5 that\n$$\\max_k \\lVert W_k(t) \\rVert > r(t)$$\nfor some $t$. However, in Lemma 2, the step size $\\eta(t)$ is not constant where\n$$\\eta(t) = \\min \\{ 1, \\beta(r(t), \\bar{r}(t), \\epsilon) \\}$$\nand\n$$r(t+1) = r(t) + \\mu(t)$$\nfor $W(t+1) \\not\\in \\mathcal{S}(r(t) - \\mu(t))$. As the $\\eta(t)$ decreases whenever \n$W(t+1) \\not\\in \\mathcal{S}(r(t) - \\mu(t))$, the step size $\\eta(t)$ \ndecreases at $\\mathcal{S}(r(t) - \\mu(t))$ and not at $\\mathcal{S}(r(t))$.\nIt is not obvious that Lemma 5 holds as the step size is not constant in $\\mathcal{S}(r(t))$.\nThis is particularly important as a Lemma 6 and Theorem 2 assume that\n $\\max_k \\lVert W_k \\rVert_F \\to \\infty$. Could you please provide a short proof\nthat $\\max_k \\lVert W_k \\rVert_F \\to \\infty$ under the assumptions of Theorem 2?\n\nIt is also unclear how statements under\nEquation 39 hold as a result of $\\max_k \\lVert W_k \\rVert_F \\to \\infty$. Why does \n$$U_k \\Sigma_k \\Sigma_k^T U_k^T \\to V_{k+1}\\Sigma^T_{k+1}\\Sigma_{k+1}V^T_{k+1}?$$\nWhy does this imply $\\Sigma_k \\Sigma^T_k$ and $\\Sigma^T_{k+1}\\Sigma_{k+1}$ are\n\"approximately the same\"? How is \"approximately the same\" defined? Why do all layers \nhave rank 1?\n\n## Vague language, ill-defined statements, and undefined definitions\n\nThe paper suffers from several instances of vague language. For\ninstance, \"alignment phenomenon\" on pages 6, 15, and 17 are not\ndefined in the paper. Although I can figure out your intended\ndefinition, it makes Theorem 2's precise statement difficult to\nascertain.  Other instances include \"approximately the same\" on page\n15 and improper use of limits on Equation 52.  In addition, the\nassumptions in the theorems sometimes do not match the proofs.  The\nproof of Theorem 2 assumes only a logistic loss function while Theorem\n2's statement assumes a broader class of loss functions.\n\n## Limited experimental results\n\n**These comments did not impact my review recommendation.**\n\nIn many theoretical papers, experimental sections typically\nquantitatively measure the difference between general theoretical\nstatements and common real-world cases. For example, experiments show\nhow theorems in compressed sensing deviated from typical use cases. In\nthe paper, a particular area for improvement is the experimental\nsection. This section show the training accuracy and the normalized\nmargin. Both plots will clearly increase as a result of adversarial\ntraining and do not add any useful information to the paper. Do the\nweights' singular values diverge to infinity in practice? Does Theorem\n5's statement on the normalized weights still occur when you use other\nlosses and neural networks or remove Assumptions 2 and 4?\n", "summary_of_the_paper": "*Implicit Bias of Adversarial Training for Deep Neural Networks*\nexplores how minimizing the exponential loss (i.e., $l(x) = e^{-x}$)\nof a homogeneous neural network (i.e., a neural network such that $$\nf = a_L W_L \\circ \\sigma_L \\circ \\cdots \\circ \\sigma_2 \\circ a_1 W_1 =\n\\prod^L_{k=1} a_k^c (W_L \\circ \\sigma_L \\circ \\cdots \\circ \\sigma_2 \\circ\nW_1 $$ for activation functions $\\sigma_L, \\ldots, \\sigma_2$, weights\n$W_L, \\ldots, W_1$, $a_L, \\ldots, a_1 > 0$, and $c \\geq 1$) on samples\nwith perturbations that maximizing the loss influences the optimized\nneural network's weights. Specifically, this paper proves that, for an\nexponential loss and a multi-c-homogeneous neural network, the limit point for $\\frac{W}{\\lVert W \\rVert}$\nwith respect to the gradient flow \n$$\n\\frac{dW}{dt} = - \\left( \\frac{d\\tilde{\\mathcal{L}}}{\\partial W} \\right)^T\n$$\nof the adversarial training objective\n$$\n\\tilde{\\mathcal{L}} = \\frac{1}{n}\\sum^n_{i=1}\\ell(x_i + \\delta_i(W), y_i)\n$$\nunder $\\ell_2$-FGM, FGSM, $\\ell_2$-PGD, and $\\ell_\\infty$-PGD is along the Karush-Kuhn-Tucker (KKT) point \nof the constrained minimization problem\n$$\n\\min_{W_1, \\ldots, W_L} \\frac{1}{2} \\lVert W \\rVert^2_{\\ell_2} \\text{ s.t. } \\tilde{\\gamma_i} \\geq 1\n$$\nwhere $\\tilde{\\gamma_i} = y_i f(x_i + \\delta_i(W))$ and $W = (W_1, \\ldots, W_L)$.\n\nThis theorem demonstrates that---for a class of neural networks and adversarial perturbations---adversarial training has\nan implicit bias that can be expressed in closed form. This result provides an important contribution to understanding \nhow adversarial training improves adversarial robustness.\n", "summary_of_the_review": "*Implicit Bias of Adversarial Training for Deep Neural Networks*\ncontributes a milestone result to the theory of adversarial\nrobustness. The majority of the paper is clearly written and\ncorrect. However, the Adversarial Training for Linear Neural Networks\nportion of the paper has several flaws: potential errors, vague\nlanguage and ill-defined statements (such as \"approximately the same\"\nand improper use of limits in Equation 52), and use of undefined\nnotation and definitions (such as alignment phenomenon). Nevertheless,\nthe contributions are significant and novel, and the paper would\nreceive an accept if Adversarial Training for Linear Neural Networks\nis amended or removed. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "m1K8I-2zenx", "reviewer": "Reviewer_kpiH", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "Some minor concerns:\n1. the notation of loss function is abused. The loss function in (6) takes both x and y as the input, while in Assumption 1, the loss function only takes one argument. I suppose the loss function in (6) means l(x,y;W) = l' (f(x;W)*y) where l' is the loss function in Assumption 1.\n2. I don't quite understand the remark at the top of page 9. LHS of (20) is about the prediction of the clean test sample, the RHS of (20) is about the fitting of the adversarial training sample. How does this inequality relate to the trade-off between robustness and accuracy? Please add more discussion.\n3. Page 21, after eq (81), \"and Lemma 4 can be applied to \". It should be \"and Lemma 9 can be applied to\".", "summary_of_the_paper": "This paper aims to understand the training results of adversarial training, and proves that under certain conditions, adversarial training results maximize the margin for the adversarial training samples. Similar results have been observed in the cleaning training of DNN, this paper's contribution is to extend them to the adversarial training settings. The paper seems technically sound (although I don't have the time to go over all the appendix). The results, to be honest, are not surprising, given previous works on standard training. But I believe the rigorous justification presented in the paper is of importance.", "summary_of_the_review": "The theoretical contribution of this paper is good to me (unless other reviewers find technical errors in the proof). I think it is a good supplement to the current theory of adversarial DNN training. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "lPQN9EfxXdj", "reviewer": "Reviewer_eZ8u", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "This paper focuses on the convergence behavior of adversarial training methods. The paper tries to show the implicit bias of adversarial training in a simplified setting with a deep linear neural network and linearly separable data for a binary classification problem. Under this setting, the paper proves the gradient descent algorithm will converge asymptotically to the max-margin solution. Later, the paper extends this result to homogeneous neural network functions with the exponential loss function and a separation assumption in Assumption 4. Overall, the paper targets an interesting question and proves some useful results on the behavior of adversarial training problems. However, I have some comments on the assumptions made to simplify the analysis, some of which seem to be quite restrictive and limit the results' application to real adversarial training problems.\n\nRegarding the paper's theoretical setting, I think some of the assumptions are quite strong. In section 3.1, the analysis is limited to deep linear networks and linearly separable data in binary classification. Also, the convergence result is an asymptotic guarantee which does not bound the iteration complexity of finding the max-margin solution. The convergence guarantee to the max-margin solution also holds for the standard training algorithm, which questions whether the result can distinguish adversarial training methods from standard training algorithms.\n\nWhile the results in section 3.1 are written clearly, I think section 3.2 lacks a clear presentation and puts several limiting assumptions. First, the gradient steps are replaced with gradient flow which is inconsistent with real adversarial training experiments. Also, the exponential loss function used for theoretical analysis is not used in practical adversarial training experiments. It is not clear whether the results can be extended to standard cross-entropy and squared-error loss functions in deep learning classification problems. Also, Assumption 4 on the separability of adversarial examples is pretty strong and essentially assumes the adversarial training method finds a perfect solution at some iteration t_0, which is too strong given that the paper wants to study the convergence behavior of adversarial training. Therefore, I think the assumptions are too restrictive for a real adversarial learning setting and significantly limit the application of the results to practical deep learning experiments. I will look forward to the authors' responses regarding the reasoning behind these assumptions to give my final score.", "summary_of_the_paper": "The paper studies the adversarial training problem under deep linear network classifiers and standard L_2 and L_\\infty perturbations. The paper's main result suggests that in the linearly separable case the adversarially trained model via gradient descent will asymptotically converge to the max-margin solution. Some extensions of this result to homogenous neural networks with exponential loss function have been provided. The paper also performs some preliminary numerical experiments to support the theoretical results.", "summary_of_the_review": "While the paper shows some insightful results on the convergence of adversarial training for deep linear networks, the assumptions for the analysis of deep nonlinear networks seem too restrictive to me. Also, replacing the gradient steps with the gradient flow seems incompatible with standard adversarial training experiments. The paper would become much stronger after relaxing some of the assumptions and performing the analysis for the actual gradient descent algorithm rather than considering the gradient flow.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "RcXbqBusnoP", "reviewer": "Reviewer_QB5M", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "Strengths:\n- The results are novel and extend prior theoretical results.\n- To the extent I have verified, the proofs are correct.\n\n\nMinor comments:\n- Theorem 5: one limitation of this result is that it depends on the adversarial perturbation as part of the constraints in Eq 19. That is in comparison with related results of Li et al 2020 and Faghri et al 2021 that their characterizations make the difference between the solution for various Lp-norm perturbations clear. Understandably, Theorem 5 is a more general result for homogenous models but it would still be useful to derive prior linear results as corollaries of Theorem 5.\n- Assumption 4 can easily be false for large perturbation sizes. The footnote says similar assumptions have been made in prior work but those were not about separability of adversarial examples. Can you provide more justification for this assumption?\n- Figure 1: This is an interesting plot confirming the increase in adversarial margin. Can you plot FGSM and PGD on the same plot? I understand that the adversarial margin for the two is different because the corresponding optimization problem is different. However, a natural question is, is there a relation between the two problems?\n- Page 9, Trade-off between standard and adversarial accuracy: I’m not sure I understand the theoretical argument of this part. Is there a concrete result based on Theorem 5?\n- Section 4: Have you verified these results for varying epsilon size (other than 16/255)? How about other network architectures? Is there a challenge in doing so?\n", "summary_of_the_paper": "This paper characterizes the bias of adversarial training toward specific minimum-norm solutions or KKT points of a particular optimization problem. Their results generalizes the work of Li et al 2020 by proving the directional alignment with the adversarial max-margin solution for deep linear models for L2 perturbations (Theorem 2) as well as convergence in direction for homogenous networks for L2 FGM, FGSM, and L2, Linf PGD perturbations (Theorem 5).", "summary_of_the_review": "This paper makes a solid theoretical contribution. It could be improved with more empirical verification of the results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is a nice addition to the developing theory of implicit bias in neural training. While the results are somewhat expected, the technical aspects are fairly involved due to the adversarial component.
Decision: Accept (Poster)