Year: 2021

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 `2 or `∞ 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.

heading: 1 INTRODUCTION
text: 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 to 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., 2015). Such vulnerability of DNNs renders security concerns about deploying them in security-critical systems including vision for autonomous cars and face recognition. It is therefore crucial to develop defense mechanisms against these adversarial examples for deep learning.
To this end, many defense strategies have been proposed to make DNNs resistant to adversarial examples, such as adding a randomization layer before the input to the classifier (Xie et al., 2018), input transformations (Guo et al., 2018), adversarial training (Madry et al., 2018), etc. However, Athalye et al. (2018) 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-class training dataset {(xi, yi)}ni=1 with natural example xi ∈ Rd and corresponding label yi ∈ {1, ..., C}, adversarial training is formulated as solving the following minimax optimization problem
min W L̃(W ) = min W
1
n n∑ i=1 max δi∈B(0, ) ` (xi + δi(W ), yi;W ) , (1)
where f is the DNN function, ` is the loss function and δi(W ) is the adversarial perturbation generated by some adversary A(xi, yi;W ) typically depending on model parameters W , within the set B(0, ) = {δ : ‖δ‖p ≤ } around the natural example xi. Commonly, adversarial training conducts a two-player game at each iteration: the inner maximization is to attack the model and find the corresponding perturbation of the original example that maximizes the classification loss `; 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 1 for details).
To have a better theoretical understanding of the fact that adversarial training empirically improves the robustness of DNNs against adversarial examples, Zhang 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. (2021) 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, Soudry et al. (2018); Ji & Telgarsky (2018); Nacson et al. (2019b) derived that the direction of the model parameter converges to that of the max-`2-margin with divergent norm. Shamir (2021) concluded that gradient methods never overfit when training linear predictors over separable dataset. Viewing the above model as a 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-`2-margin solution; Gunasekar et al. (2018) showed the implicit bias of gradient descent on linear convolution networks. Nacson et al. (2019a); 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-margin problem. Wei et al. (2019) studied the regularization path for homogeneous DNNs and also proved the convergence to the max-margin direction in this setting. Banburski et al. (2019) showed that gradient descent induces a dynamics of normalized weights converging to an equilibrium which corresponds to a minimal norm solution.
It 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 to analyze the perturbed training dynamics. For the adversarial training objective Eq. (1), various approaches have been proposed to solve the inner maximization, such as fast gradient sign method (FGSM (Goodfellow et al., 2015)) 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., 2020) also suggested that a 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 `2-fast gradient method (FGM (Miyato et al., 2016)), `∞ FGSM, `2-PGD and `∞-PGD to solve the inner maximization of the adversarial training objective.

heading: 1.1 OUR CONTRIBUTION
text: In this paper, we devote to 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 bias, what are the convergence properties of the model parameters along the adversarial training trajectory?
To this end, we first investigate the adversarial training with `2 adversarial perturbations for deep linear networks on linear separable data where the allowed Euclidean distances from the adversarial examples to their corresponding original examples ‖x′i − xi‖2 are less than the max-`2-margin of 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 implicitly aligns weight matrices across layers and the direction of the product of weight matrices also surprisingly converges to that of the max-`2-margin solution of the original dataset—similar to
that of standard training for deep linear network (Ji & Telgarsky, 2019). 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 1 (Informal). When the deep neural network is adversarially trained with one of the `2-FGM, FGSM, `2-PGD and `∞-PGD 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 1 provides another view for the 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 our results provide a theoretical understanding on the effectiveness of adversarial training for improving robustness against adversarial examples. It could potentially shed light on how to enhance the robustness of adversarially trained models or even further inspire more effective defense mechanisms.
Organization This paper is organized as follows. Section 2 is about notations and settings. Section 3 presents our main results on the implicit bias of adversarial training for DNNs. Section 4 provides numerical experiments to support our claims. We conclude this work in Section 5 and discuss future directions. Some technical proofs are deferred to supplementary materials.
Algorithm 1 Adversarial Training Input: Training set S = {(xi, yi)}ni=1, Adversary A to solve the inner maximization, learning rate η, initialization Wk for k ∈ {1, . . . , L} for t = 0 to T − 1 do S′(t) = ∅ for i = 1 to n do x′i(t) = A(xi, yi,W (t)) S′(t) = S′(t) ⋃ (x′i(t), yi)
end for for k = 1 to L do Wk(t+ 1) = Wk(t)− η(t)∂L̃(S ′(t);W ) ∂Wk
end for end for

heading: 2 PRELIMINARIES
text: Notations. For any matrix A ∈ Rm×n, we denote its i-th row j-th column entry by Aij . Let AT denote the transpose of A. ‖ · ‖F represents the Frobenius norm and ‖ · ‖p is the `p norm. The training set is {(xi, yi)}ni=1 where xi ∈ Rd, ‖xi‖2 ≤ 1 and yi ∈ {1,−1}. For a scalar function f : Rd 7→ R, we denote its gradient by∇f . Furthermore, tr (A) = ∑ iAii 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ϕL (WL−1 · · ·ϕ3(W2ϕ2(W1x)) · · · ) (2)
where Wk is the k-th layer weight matrix and ϕk is the activation function of the k-th layer 1. The multi-c-homogeneity of the network is defined by
f(x; a1W1, · · · , aLWL) = L∏ k=1 ackf(x;W ) (3)
for any positive constants ak’s and c ≥ 1, where W = (W1, · · · ,WL) is the collection of the parameters of the network. For example, deep ReLU networks are multi-1-homogeneous. For convenience, we also adopt the following notations for a multi-ck-homogeneous DNN:
ρk = ‖Wk‖F , ρ = ρc1 · · · ρcL and f(x;W ) = ρf(x; Ŵ ), (4)
where Ŵk = Wk/‖Wk‖F with ‖Ŵk‖F = 1 for k ∈ {1, . . . , L}. We use δi(W ) to represent the adversarial perturbation of the original example xi within the perturbation set B(0, ) : {δ : ‖δ‖p ≤ } around the original example xi for f(x;W ). Furthermore, we use the scale invariant adversarial perturbations defined as follows for adversarial training in this paper. Definition 1 (Scale invariant adversarial perturbation). An adversarial perturbation is said to be a scale invariant adversarial perturbation for f(xi;W1, . . . ,WL) and loss function ` if it satisfies
δi(a1W1, . . . , aLWL) = δi(W1, . . . ,WL) (5)
for any positive constants ak’s.
We will show in Section 3.2 that FGSM, `2-FGM, `2-PGD and `∞-PGD perturbations for homogeneous DNNs are all scale invariant perturbations, which are important for analyzing different types of perturbation in a unified manner. The empirical adversarial training loss with the perturbation δi(W ) is given by
L̃(W ) = 1 n n∑ i=1 ˜̀(yi, xi;W ) = 1 n n∑ i=1 ` (yif(xi + δi(W );W )) . (6)
For ease of notation, we denote ˜̀i(W ) = ˜̀(yi, xi;W ). The loss function ` is continuously differentiable and satisfies Assumption 1 (Loss function). ` > 0, `′ < 0, limx→∞ `(x) = 0 and `x→−∞(x) =∞.
Many widely used loss functions satisfy the above assumption such as `(x) = e−x and the logistic loss `(x) = ln(1 + e−x). Furthermore, we make the following common assumptions about the smoothness of f(x;W ) and the adversarial perturbation δ(W ): Assumption 2 (Smoothness). With respect to W , yf(x;W ) is locally Lipschitz for any fixed x; yif(xi;W ) further have locally Lipschitz gradients and δi(W ) are locally Lipschitz for all training examples xi.
Remark. Our results can also be generalized to non-smooth homogeneous neural networks straightforwardly (Appendix B.4). Assuming Lipschitzness about perturbations is because we focus on popular perturbations such as `2-FGM and PGD perturbations which have explicit forms and depend on gradients of the network, whose Lipschitzness assumptions are quite common.

heading: 3 MAIN RESULTS
text: 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 `2 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 training2. Based on this key result, the product of weight matrices converges to the direction of the maximum margin solution
1ϕk is a vector in our notations. 2This phenomenon for standard training has been studied by Ji & Telgarsky (2019) first.
under the original data. Furthermore, we study a much more general scenario in Section 3.2: without the assumption of linearly separability of data and norm constraints on adversarial perturbations, we 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 proofs of Section 3.2 in Appendix B.

heading: 3.1 ADVERSARIAL TRAINING FOR DEEP LINEAR NETWORK
text: In this section we restrict the dataset {(xi, yi)}ni=1 to be linearly separable in the sense that there exists a unit vector u such that ∀i ∈ {1, . . . , n}, yi 〈u, xi〉 > 0 and we explore the adversarial training dynamics of gradient descent for deep linear networks, i.e., with identity activation function ϕk(x) = x for all layers, f(x,W ) = WL · · ·W1x. (7) Now let
ū = arg max ‖u‖=1 min i∈{1,...,n}
yi 〈xi, u〉 > 0
be the max-margin solution given by the hard-margin SVM and γm = max‖u‖=1 ym 〈xm, u〉 be the max-margin, where m = arg mini∈{1,...,n} yi 〈xi, u〉. We only consider the `2-norm adversarial perturbations in this section, i.e., B(0, ) = {δ : ‖δ‖2 ≤ }. The allowed Euclidean distance from an adversarial example x′ to its original example x is assumed to satisfy
‖x′ − x‖2 ≤ ≤ γm. (8) We denote the product of all weight matrices by WΠ = WL · · ·W1, which is simply a vector. Our model is adversarially trained by gradient descent
Wk(t+ 1) = Wk(t)− η(t) ∂L̃(t) ∂Wk(t) . (9)
The inner maximization of the adversarial training objective Eq. (1) can be solved exactly in this case, where the adversarial perturbations are taken as
δi(W (t)) = −yi WΠ(t)
‖WΠ(t)‖2 (10)
for the t-th iteration of adversarial training. For any layer k, the weight matrix can be decomposed as
Wk = UkΣkV T k
where Uk and Vk are the left and right singular matrices, respectively. Furthermore, we use uk and vk to represent the left and right singular vectors corresponding to the largest singular value, respectively. We emphasize that the training dynamics abruptly changes due to this perturbation and one should be careful to analyze its effects. It can be easily seen that Eq. (10) is a scale invariant adversarial perturbations by our definition. Note that with this kind of 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 Assumption 3. The loss function ` is β-smooth and |`′| ≤ α.
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 Ji & Telgarsky (2019) for standard training, here we first examine whether our adversarial training loss Eq. (1) possesses smoothness. Let the set S(r) denote the set of weights with bounded norm
S(r) = { W ∣∣‖Wk‖F ≤ r, ‖WΠ‖2 ≥ r̄, k = 1, . . . , L} , (11)
where r ≥ 1 and r̄ is a small constant to avoid trivial solution. To simplify the notation, we let β(r, r̄, ) = r3LL2 [ α+ β +
r̄L
( 2α+ β + αβ
r̄L
)] . (12)
The following lemma provides us a first view of the overall trends of gradient descent for adversarial training in deep linear network on linear separable dataset.
Lemma 1 (Overall trends of adversarial training for deep linear network). With adversarial perturbation Eq. (10), under Assumption 1, Assumption 3 and the requirement Eq. (8), for the deep linear network adversarially trained by gradient descent on linear separable data, the adversarial training objective (1) is β(r, r̄, )-smooth within the given set S(r) for a constant r. However, with constant step size for gradient descent, the weight matrices will eventually leave the set S(r) if r remains unchanged during the training
max k∈{1,...,L} ‖Wk(t1)‖F > r for some t1 > 0. (13)
The first part of this lemma implies the smoothness of the adversarial training loss Eq. (1) while also leading the weight matrices to leave the set S(r). In fact, this is saying that maxk∈{1,...,L} ‖Wk‖F is divergent along the adversarial training trajectory since maxk∈{1,...,L} ‖Wk‖F will be larger than r for any given r. We can keep W (t+ 1) inside S(r(t)) at every step t by delicately adjusting the step size of gradient descent and treating r as a function of the step t.
Lemma 2 (Smoothness of the adversarial training loss). If the learning rate is taken as η(t) = min{1, 1/β(r, r̄, )}, then the adversarial training loss L̃(W ) is β(r, r̄, )-smooth where r(t+ 1) is taken as
r(t+ 1) = { r(t) if W (t+ 1) ∈ S(r(t)− µ(t)), r(t) + µ(t) otherwise
during the training, where µ = rL−1(1 + )α/β(r, r̄, ).
We show the divergence of maxk∈{1,...,L} ‖Wk‖F 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-margin solution). With adversarial perturbation Eq. (10), under Assumption 1, 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:
∀k ∈ {1, . . . , L} : |〈uk, vk+1〉| → 1 (14)
as t → ∞. As a result, the direction of the product of weight matrices converges to that of the max-margin solution
WΠ ‖WΠ‖2 → ū. (15)
Remark. The alignment phenomenon for standard training has been showed in the previous work Ji & Telgarsky (2019), here we further extend this result to the case of adversarial training, where the training objective is 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 a significant generalization of Li et al. (2020) which studied the convergence to max-margin solution of adversarial training for logistic regression, a 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 of original dataset—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-margin 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 adversarial examples more explicitly.

heading: 3.2 ADVERSARIAL TRAINING FOR HOMOGENEOUS DEEP NEURAL NETWORK
text: Additional definitions For simplicity, we will use exponential loss `(x) = e−x in this section. For an original example xi, the margin for its adversarial example xi + δi(W ) is defined as γ̃i = yif(xi + δi(W );W ) while for the whole dataset {(xi, yi)}ni=1, the margin for their corresponding adversarial examples is denoted by γ̃m where m = arg minm∈{1,...,n} yif(xi + δi(W );W ). We introduce the normalized margin as γ̂i = yif(xi + δi(Ŵ ); Ŵ ) to explore the convergence properties, where Ŵk = Wk/ ‖Wk‖F such that ‖Ŵk‖F = 1 for any layer k . Furthermore, the margin for the original example xi is defined to be γi = yif(xi;W ) ≥ γ̃i. 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
dWk dt = − ( ∂L̃ ∂Wk )T (16)
for k ∈ {1, . . . , 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 a 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 1, `2-FGM, FGSM, `2-PGD and `∞-PGD perturbations for homogeneous DNNs are 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 f(x;W ), we have
tr ( ∂L̃ ∂Wk Wk ) = − c n n∑ i=1 e−γ̃i γ̃i. (17)
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 a weaker assumption in a more general scenario. Assumption 4. There exists a separability of adversarial examples of the dataset3: there exists a time t0 such that yif(xi + δi(W (t0));W (t0)) > 0 for all i ∈ {1, . . . , 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 a reasonable one. In Section 3.1, 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 ρ = ∏L k=1 ρ c k = ∏L k=1 ‖Wk‖ c F , we state our first main theorem regarding the overall trend for gradient flow of adversarial training as follows. Theorem 3 (Divergence of weight norms). For the adversarial training objective (6) of the binary classification task with exponential loss and scale invariant adversarial perturbations, under Assumption 2 and Assumption 4, the product of the Frobenius norms of weight matrices diverges to infinity along the trajectory of the gradient flow
ρ = Ω (ln t)→∞,
and, as a result, the training loss L̃ converges to zero as t→∞. 3Similar assumptions are previously used in Lyu & Li (2020); Ji & Telgarsky (2020)
Remark. The divergence of weight norms for standard training of homogeneous DNNs has been studied by, for example, Lyu & Li (2020); Wei et al. (2019). The above theorem considers adversarial training, which implies that the margin for an adversarial example, γ̃i for any i ∈ {1, . . . , n}, also goes to infinity along the adversarial training trajectory. This makes the normalized margin γ̂i necessary to understand the convergence properties of the adversarial training solution as t → ∞. 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-decreasing adversarial margin). For adversarial training with scale invariant adversarial perturbations, when the separability of adversarial examples is achieved at t0, the weighted sum of the changing rates of normalized margins for the adversarial examples are nonnegative for all t ≥ t0:
∀t ≥ t0 : n∑ i=1 e−ργ̂i dγ̂i dt ≥ 0; (18)
there exists a sufficiently large time t1 > t0 such that dγ̂mdt ≥ 0 if ∀i : γ̂i − γ̂m = ω( 1 ρ ) for all t ≥ t1.
The above theorem reveals a relation for the normalized margins for adversarial examples. According to the above lemma, since ρ → ∞ as t → ∞, the term with weight e−ργ̂m , roughly speaking, dominates the LHS of (18) after some time t1 ≥ t0. Then dγ̂m/dt4 will never be negative for ∀t ≥ 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 3, 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 4, for exponential loss and multi-c-homogeneous DNNs, the limit point of normalized weight parameters {W/‖W‖2 : t ≥ 0} of the gradient flow for the adversarial training objective Eq. (6) with scale invariant adversarial perturbations is along the direction of a KKT point of the constrained normminimization problem
min W1,...,WL
1 2 ‖W‖22 s.t. γ̃i ≥ 1 ∀i ∈ {1, . . . , n}. (19)
Remark 1. According to Lemma 3, the above theorem can be directly applied to `2-FGM, FGSM, `2 and `∞-PGD perturbations. The requirement Eq. (8) in Section 3.1 is not required since the dataset in this section is no longer linearly separable. It is well-known that the norm-minimization problem is closely related to the margin-maximization problem in the sense that
Optimization problem(19)⇐⇒ max W1,...,WL γ̃m, s.t. ‖W‖2 = 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 `2-norm, (19) is no longer an `2-norm optimization problem but a mixed-norm one due to the perturbation δ(W ) in γ̃m, which was first observed by Li et al. (2020) 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—they are formulated from solving different optimization problem. Theorem 5 provides 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 (2020) studied the properties of the normalized margin through its approximation, the smooth-normalized margin. One can try to generalize the analysis method in Lyu & Li (2020) to adversarial training with various kinds of adversarial perturbations by further assuming the local smoothness regarding gradients when considering nonsmooth analysis. Generalizinig our results to non-smooth case can be found in Appendix B.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.
4Strictly speaking, this is not well-defined since m may not be unique. However, we can use this definition in an approximately correct way for t sufficiently large.
Trade-off between robustness and accuracy. More significantly, Theorem 5 also implies that adversarial training leads to the trade-off between robustness and accuracy as in Zhang et al. (2019). This can be seen as follows. Let f(·,W ) denote the classifier obtained from adversarial training. Then for a clean training example (x, y) with y = 1 for simplicity, we have yf(x + δ(W );W ) = f(x+ δ(W );W ) > 0 since f(x;W ) is a max-margin classifier over adversarial data. This means that, for any clean test example (x′, y′) around x in the sense that x′ = x+ τ with ‖τ‖p ≤ , we will have f(x′,W ) = f(x+ τ ;W ) ≥ f(x+ δ(W );W ) > 0 (20) due to the definition of δ(W ) when y = 1: δ(W ) = maxv∈B(x, ) `(yf(x + v;W )) = minv∈B(x, ) 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+ τ as having labels 1 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 on other perturbations.

heading: 4 NUMERICAL EXPERIMENTS
text: In this section, we conduct numerical experiments on MNIST dataset to support our claims. We adversarially trained a 3-layer neural network using SGD with constant learning rate and batch-size 80. The model has the architecture of input layer-1024-ReLU-64-ReLU-output layer. We present results for adversarial training with: (1) FGSM perturbations with = 16/255; (2) `∞-PGD perturbations, where the PGD is ran for 5 steps with step size 6/255 and = 16/255. As a 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. 1(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 `∞-PGD adversarial examples as showed by Fig. 1(b). To see that adversarial normalized keeps increasing more clearly, we also plot the adversarial training with FGSM perturbations after 10000 epochs in Fig. 1(c). More experiments are in Appendix C. These empirical findings support our claims that adversarial training implicitly maximizes the margin of adversarial examples.

heading: 5 CONCLUSION
text: 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-maximization for adversarial data during its 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 to have the bias of maximizing the margin of adversarial examples. We will leave these potential benefits of our theoretical analysis as future work.

heading: A PROOFS OF SECTION 3.1
text: In Section A.1, 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 L̃(W (0)) ≤ L̃(0) = `(0) and∇L̃(W (0)) 6= 0 to start adversarial training.

heading: A.1 SMOOTHNESS OF THE ADVERSARIAL TRAINING LOSS

heading: A.1.1 PROOF OF LEMMA 1
text: We first prove that the adversarial training loss for the deep linear network is smooth within S(r). For any W,V ∈ S(r), let δW and δV denote the adversarial perturbations of the network f(x;W )
and f(x;V ), respectively. Then we have, by taking derivatives of L w.r.t W and using that ‖A‖F + ‖B‖F ≥ ‖A−B‖F ,∥∥∥∥∥ ∂L̃∂W1 − ∂L̃∂V1 ∥∥∥∥∥ F ≤ 1 n n∑ i=1 ∥∥∥WT2 · · ·WTL xTi yi ˜̀′i(WΠ)− V T2 · · ·V TL xTi yi ˜̀′i(VΠ)∥∥∥ F︸ ︷︷ ︸
(a)
+
n n∑ i=1 ∥∥∥∥∂ ‖WΠ‖∂W1 yi ˜̀′i(WΠ)− ∂ ‖VΠ‖∂V1 yi ˜̀′i(VΠ) ∥∥∥∥ F︸ ︷︷ ︸
(b)
, (21)
where the term (b) abruptly changes the training dynamics. For simplicity, we use x, y and ˜̀′ without the subscript i because the analysis can be done similarly for any i ∈ {1, . . . , n}. We begin with the term (a) of Eq. (21):
(a) ≤ ∥∥∥WT2 · · ·WTL xT y ˜̀′(WΠ)− V T2 WT3 · · ·WTL xT y ˜̀′(WΠ)∥∥∥ + ∥∥∥V T2 WT3 · · ·WTL xT y ˜̀′(WΠ)− V T2 · · ·V TL xT y ˜̀′(VΠ)∥∥∥
≤ ‖W2 − V2‖ ∥∥∥WT3 · · ·WTL xT y ˜̀′(WΠ)∥∥∥
+ ‖V2‖ ∥∥∥WT3 · · ·WTL xT y ˜̀′(WΠ)− V T3 · · ·V TL xT y ˜̀′(VΠ)∥∥∥
c ≤ ‖W2 − V2‖ rL−2α+ r ∥∥∥WT3 · · ·WTL xT y ˜̀′(WΠ)− V T3 · · ·V TL xT y ˜̀′(VΠ)∥∥∥ d ≤
L∑ k=2 rL−2α ‖Wk − Vk‖+ rL−2‖VL‖ ∥∥∥˜̀′(WΠ)− ˜̀′(VΠ)∥∥∥
e ≤ ( rL−2α(L− 1) + βLr2L−2 ) ‖W − V ‖ , (22)
where c follows from ‖x‖ ≤ 1, ‖Wk‖ ≤ r and `′ ≤ α; repeating the procedure of c until k = L gives us d; e is because ‖Wk − Vk‖ ≤ ‖W − V ‖ for any k and∥∥∥˜̀′(WΠ)− ˜̀′(VΠ)∥∥∥ ≤ β‖WΠ − VΠ‖ ≤ βLrL−1‖W − V ‖ (23) considering that ` is a β-smooth function. It now remains us to bound the term (b) of Eq. (21). Note that
∂ ‖WΠ‖2 ∂W1 = WT2 · · ·WTLWL · · ·W1 ‖WΠ‖2 , (24)
then we have (b) ≤ ∥∥∥∥WT2 · · ·WTLWL · · ·W1‖WΠ‖ ˜̀′(WΠ)− V T 2 W T 3 · · ·WTLWL · · ·W1 ‖WΠ‖ ˜̀′(WΠ) ∥∥∥∥ +
∥∥∥∥V T2 WT3 · · ·WTLWL · · ·W1‖WΠ‖ ˜̀′(WΠ)− V T 2 V T 3 · · ·V TL VL · · ·V1 ‖VΠ‖ ˜̀′(VΠ) ∥∥∥∥ c ≤ αr 2L−2
r̄L ‖W2 − V2‖
+ r ∥∥∥∥WT3 · · ·WTLWL · · ·W1‖WΠ‖ ˜̀′(WΠ)− V T 3 · · ·V TL VL · · ·V1 ‖VΠ‖ ˜̀′(VΠ) ∥∥∥∥ d ≤ (2L− 1) αr 2L−2
r̄L ‖W − V ‖+ r2L−2 ∥∥∥∥∥ ˜̀′(WΠ)‖WΠ‖ − ˜̀ ′(VΠ) ‖VΠ‖ ∥∥∥∥∥ e ≤ (2L− 1) αr 2L−2
r̄L ‖W − V ‖+ r
2L−2
r̄L ∥∥∥˜̀′(WΠ)− ˜̀′(VΠ)∥∥∥ + αr2L−2 r̄2L ‖WΠ − VΠ‖
f ≤ r
2L−2
r̄L
( (2L− 1)α+ βLrL−1 + αβLr L−1
r̄L
) ‖W − V ‖ , (25)
where c follows from ‖Wk‖ ≤ r and ˜̀′ ≤ α; repeating c for 2L− 1 times gives d; e follows from ‖‖WΠ‖ − ‖VΠ‖‖ ≤ ‖WΠ − VΠ‖; invoking Eq. (23) gives us f. Now we can bound Eq. (21) by combing the above results∥∥∥∥∥ ∂L̃∂W1 − ∂L̃∂V1 ∥∥∥∥∥ F
≤ [ rL−2α(L− 1) + βr2L−2L+ r 2L−2
r̄L
( (2L− 1)α+ βLrL−1 + αβLr L−1
r̄L
)] ‖W − V ‖
≤ r3LL [ α+ β +
r̄L
( 2α+ β + αβ
r̄L
)] ‖W − V ‖, (26)
where the last inequality is because we choose r ≥ 1. The above analysis is for the first layer. Now we can apply the same technique to other layers, which finally gives us
‖∇L̃(W )−∇L̃(V )‖ ≤ r3LL2 [ α+ β +
r̄L
( 2α+ β + αβ
r̄L
)] ‖W − V ‖, (27)
thus L̃ is β(r, r̄, )-smooth inside S(r) where β(r, r̄, ) = r3LL2 [ α+ β +
r̄L
( 2α+ β + αβ
r̄L
)] . (28)
We now prove the second statement of Lemma 1, which says that W will leave S(r) with constant r and learning rate η. Let W (t),W (t+ 1) ∈ S(r) and η(t) = min{1, 1/β(r, r̄, )}. Lemma 5 (Adapted from Lemma 6 in Ji & Telgarsky (2019)). Under Assumption 1 and Assumption 3, suppose gradient descent for adversarial training is run with a constant step size 1/β(r, , r̄). Then there exists a time t when maxk ‖Wk(t)‖F > r.
Eq. (27) states that L̃ is β(r, r̄, )-smooth, therefore L̃(W (t+ 1))− L̃(W (t)) ≤ 〈 ∇L̃(W (t)),−η(t)L̃(W (t)) 〉 + β(r, r̄, )η(t)2
2 ‖∇L̃(W (t))‖2
= − η(t) 2 ‖∇L̃(W (t))‖2, (29)
which also implies that L̃(W (t)) never increases during the training
L̃(W (t+ 1)) ≤ L̃(W (t))− η(t) 2 ‖∇L̃(W (t))‖2. (30)
By repeatedly applying Lemma 5 when the learning rate is constant, we know W will eventually leave S(r), which also implies that maxk ‖Wk‖F is unbounded in this case.

heading: A.1.2 PROOF OF LEMMA 2
text: Proof. For any step t with the learning rate in the Lemma 2, suppose that W (t) ∈ S(r(t)− µ(t)), we then have
‖Wk(t+ 1)‖F ≤ ‖Wk(t)‖F + η(t) ∥∥∥∥∥ ∂L̃∂Wk(t) ∥∥∥∥∥ F ≤ ‖Wk(t)‖F + µ(t),
where the last inequality follows from∥∥∥∥∥ ∂L̃∂Wk(t) ∥∥∥∥∥ ≤ ∥∥∥Wk+1 · · ·WTL xTWT2 · · ·WTk−1y ˜̀′(WΠ)∥∥∥ + ∥∥∥∥∂ ‖WΠ‖2∂Wk ˜̀′(WΠ) ∥∥∥∥
≤ (1 + r̄L )αr2L. (31)
Therefore ‖Wk(t+ 1)‖F will always stay in S(r(t)) and the smoothness is preserved. If ‖Wk(t+ 1)‖F is still less than r(t) − µ(t), then we keep r(t + 1) = r(t) while we increase r(t+ 1) to
r(t+ 1) = r(t) + µ(t) if r(t) − µ(t) ≤ ‖Wk(t+ 1)‖F ≤ r(t) such that ‖Wk(t+ 1)‖F ≤ r(t) ≤ r(t + 1) − µ(t + 1), which means that W (t+ 2) will stay inside S(r(t+ 1)). The overall smoothness can then be proved by induction.

heading: A.2 ALIGNMENT PHENOMENON
text: We start with the following lemma for the adversarial training to prove the alignment phenomenon5: Lemma 6 (Bounded differences between weight norms). The difference of Frobenius norms for any two layers is bounded during the adversarial training process∣∣ ‖Wk(t)‖2F − ‖Wj(t)‖2F ∣∣− 2L̃(W (0)) ≤ ∣∣ ‖Wk(0)‖2F − ‖Wj(0)‖2F ∣∣, ∀k, j ∈ {1, . . . , L}. Proof. If there is not adversarial perturbation, then we can easily obtain
WTk+1 ∂L
∂Wk+1 = ∂L ∂Wk WTk (32)
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) = tr ( AT ) and tr (ABC) = tr (CAB), we have
y ˜̀(WΠ)W T k+1 ∂ ‖WΠ‖2 ∂Wk+1 = y ˜̀(WΠ) ‖WΠ‖2 WTk+1 · · ·WTLWL · · ·W1WT1 · · ·WTk
= y ˜̀(WΠ) ∂ ‖WΠ‖2 ∂Wk WTk . (33)
Combining Eq. (32), for the adversarial empirical loss, we have
WTk+1 ∂L̃
∂Wk+1 = ∂L̃ ∂Wk WTk , (34)
which will give us the following relation
WTk+1(t+ 1)Wk+1(t+ 1) = W T k+1(t)Wk+1(t) + η(t) 2
( ∂L̃
∂Wk+1(t)
)T ( ∂L̃
∂Wk+1(t)
)
− η(t) WTk+1(t) (
∂L̃ ∂Wk+1(t)
) + ( ∂L̃
∂Wk+1(t)
)T Wk+1(t)  , which can be easily seen by writing out the gradient descent update explicitly. One can derive a similar relation for Wk(t+ 1)WTk (t+ 1). Combing Eq. (32), we have
WTk+1(t+ 1)Wk+1(t+ 1)−WTk+1(t)Wk+1(t)− η(t) 2
( ∂L̃
∂Wk+1(t)
)T ( ∂L̃
∂Wk+1(t)
)
= Wk(t+ 1)W T k (t+ 1)−Wk(t)WTk (t)− η(t)
2
( ∂L̃
∂Wk(t)
)( ∂L̃
∂Wk(t)
)T . (35)
Summing up the above equation from 0 to t will give us
WTk+1(t)Wk+1(t)−WTk+1(0)Wk+1(0)−Ak+1(t) = Wk(t)WTk (t)−Wk(0)WTk (0)−Bk(t) (36)
where symmetric matrices Ak and Bk are defined by
Ak(t) = t−1∑ τ=0 η(τ) 2
( ∂L̃
∂Wk(τ)
)T ( ∂L̃
∂Wk(τ) ) and
Bk(t) = t−1∑ τ=0 η(τ) 2
( ∂L̃
∂Wk(τ)
)( ∂L̃
∂Wk(τ)
)T .
5This property for standard training has previously been studied by Ji & Telgarsky (2019); Arora et al. (2018).
Also notice that
tr (Ak(t)) = tr (Bk(t)) (37)
where
tr (Ak(t)) ≤ L∑
k′=1
tr t−1∑ τ=0 η(τ) 2 ( ∂L̃ ∂Wk′(τ) )T ( ∂L̃ ∂Wk′(τ) ) =
L∑ k′=1 t−1∑ τ=0 η(τ) 2 ∥∥∥∥∥ ∂L̃∂Wk′(τ) ∥∥∥∥∥ 2
F
a ≤ t−1∑ τ=0 η(τ) ∥∥∥∇L̃(W (τ))∥∥∥2
b ≤ 2 t−1∑ τ=0 η(τ) [ L̃(W (τ))− L̃(W (τ + 1)) ] c = 2L̃(W (0))− 2L̃(W (t)) ≤ 2L̃(W (0)), (38)
where a is because η < 1; b is due to Eq. (29); summing up from τ = 0 to t − 1 and noting that L̃ > 0 give us c. For any two layers k < j, taking trace of both sides of (36) and summing from k to j, we have that the differences between the Frobenius norms for any two layers∣∣∣‖Wk(t)‖2F − ‖Wj(t)‖2F ∣∣∣ = ∣∣∣tr (Aj(t)) + ‖Wj(0)‖2F − tr (Bk(t))− ‖Wk(0)‖2F ∣∣∣
≤ 2L̃(W (0)) + ∣∣∣‖Wj(0)‖2F − ‖Wk(0)‖2F ∣∣∣
are always bounded. Since max1≤k≤L ‖Wk‖F → ∞, the above result implies that ‖Wk‖F → ∞ for all k.

heading: A.2.1 PROOF OF THEOREM 2
text: Intuitively, Wk can be decomposed as
Wk(t) = Uk(t)Σk(t)V T k (t).
For Wk, denote the first singular value, the corresponding left singular vector and right singular vector by σk, uk and vk. Since σk →∞, the initialization becomes negligible as t→∞. According to Eq. (36), this will lead to
Uk(t)Σk(t)Σ T k (t)U T k (t)→ Vk+1(t)ΣTk+1(t)Σk+1(t)V Tk+1(t)
as t→∞. On the other hand, since WLWTL has rank 1 for WL being a row vector, all layers have rank 1 because they get aligned with WL and Wk‖Wk‖F → ukv T k .
To further elaborate the above reasoning, we provide a more exact proof starting with the definition of the alignment phenomenon. Definition 2 (Alignment phenomenon for deep linear networks.). For deep linear network f(x;W ) = WL · · ·W1x, the alignment phenomenon is defined as
∀k ∈ {1, . . . , k} : | 〈uk, vk+1〉 | → 1 (39)
and Wk/‖Wk‖F → ukvTk as t → ∞ along the training trajectory, where uk, vk 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 is as follows.
Proof. Note that
〈uk, vk+1〉2 σ2k+1 = uTkWTk+1Wk+1uk + uTk (vk+1σ2k+1vTk+1 −WTk+1Wk+1)uk, (40)
we have uTkW T k+1Wk+1uk
σ2k+1 + ‖Wk+1‖22 − ‖Wk+1‖2F σ2k+1 ≤ 〈uk, vk+1〉2 ≤ 1 (41)
by utilizing the definition of matrix norm and
‖Wk+1‖2F ≥ uTkWTk+1Wk+1uk. (42) According to Eq. (36), let
Γk = W T k+1(0)Wk+1(0)−Wk(0)Wk(0)T +Ak+1 −Bk, (43)
and replace WTk+1Wk+1 with Γk +WkW T k in Eq. (41), we have
〈uk, vk+1〉2 ≥ σ2k σ2k+1 + uTk Γkuk + ‖Wk+1‖22 − ‖Wk+1‖2F σ2k+1 . (44)
To prove the alignment phenomenon, we now bound the RHS of Eq. (44) with 1− α where α→ 0 when t→∞. We are going to bound 3 terms, namely uTk Γkuk, ‖Wk‖22 − ‖Wk‖2F and σ2k/σ2k+1.
1. Bound uTk Γkuk.
uTk Γkuk ≥ −uTkWk(0)Wk(0)Tuk − uTkBkuk ≥ −‖Wk(0)‖22 − tr (Bk) ≥ −‖Wk(0)‖22 − 2L̃(W (0)), (45)
where we used Eq. (38) in the third inequality.
2. Bound ‖Wk‖22 − ‖Wk‖2F . According to the definition of singular values, we have ‖Wk‖22 = σ2k ≥ vTk+1WkWTk vk+1
= vTk+1(W T k+1Wk+1 − Γk)vk+1
≥ σ2k+1 − vTk+1∆Wk(0)vk+1 − tr (Bk) (46) where ∆Wk(0) = Wk(0)Wk(0)T −WTk+1(0)Wk+1(0) and we used that tr (Bk) ≥ ‖Bk‖2 in the second inequality. On the other hand, by taking trace of both sides of Eq. (36), we have
‖Wk‖2F = ‖Wk+1‖2F − ‖Wk+1(0)‖2F + ‖Wk(0)‖2F − tr (Ak+1) + tr (Bk) . (47) Combined with Eq. (46), we have ‖Wk‖22 − ‖Wk‖2F ≥ ‖Wk+1‖22 − ‖Wk+1‖2F
+ (‖Wk+1(0)‖2F − ‖Wk(0)‖2F )− vTk+1∆W (0)vk+1 + (tr (Ak+1)− tr (Bk))− tr (Bk)
a ≥ ‖Wk+2‖22 − ‖Wk+2‖2F
+ (‖Wk+2(0)‖2F − ‖Wk(0)‖2F )− (vTk+1∆Wk(0)vk+1 + vTk+2∆Wk+1(0)vk+2) + (tr (Ak+2)− tr (Bk))− (tr (Bk) + tr (Bk+1)) . . .
b ≥ ‖WL(0)‖2F − ‖Wk(0)‖2F − L−1∑ k′=k vTk′+1∆Wk′(0)vk′+1 − L−1∑ k′=k tr (Bk′)
+ tr (AL)− tr (Bk) c ≥M − 2LL̃(W (0)), (48)
where a follows from Eq. (37); b follows from summing a from k to L − 1 and that ‖WL‖2 = ‖WL‖F ; c is because Eq. (38) and that
M = min ‖WL(0)‖2F − ‖Wk(0)‖2F − L−1∑ k′=k vTk′+1∆Wk′(0)vk′+1 (49)
is finite.
3. Bound σ2k/σ 2 k+1. Eq. (46) gives us that
σ2k σ2k+1 ≥ 1− vTk+1∆Wk(0)vk+1 − tr (Bk) σ2k+1 ≥ 1− vTk+1∆Wk(0)vk+1 + 2L̃(W (0)) σ2k+1 , (50)
where vTk+1∆Wk(0)vk+1 + 2L̃(W (0)) is finite.
Putting the bounds obtained from the above 1, 2 and 3 back to Eq. (44) will give us
〈uk, vk+1〉2 ≥ 1− ‖Wk(0)‖22 + 2(L+ 2)L̃(W (0))−M + vTk+1∆Wk(0)vk+1
σ2k+1 . (51)
Considering that σk →∞ and the numerator is finite, we thus conclude that the RHS of Eq. (51) will converge to 1. Therefore, we have that
〈uk, vk+1〉2 → 1 (52) as t → ∞. Furthermore, since ‖Wk+1‖2F − ‖Wk+1‖22 is finite (see Eq. (48)) and σk → ∞ (i.e., ‖Wk‖22/‖Wk‖2F → 1), we have Wk ‖Wk‖F → ukv T k because other singular values are negligible. We now have the alignment phenomenon.
Furthermore, we have WΠ
‖WL‖F · · · ‖W1‖F → v1uT1 · · · vLuTL → v1. (53)
We now move forward to prove the alignment phenomenon for the first layer. We assume that the support vectors span the data space Rd and denote the orthogonal complement of span(ū) by ū⊥. Let P⊥ denote the projection onto ū⊥. Under this assumption, Ji & Telgarsky (2019) showed the following lemma6
Lemma 7 (Lemma 3 in Ji & Telgarsky (2019)). Let S denote the set of indices of support vectors , then with probability 1,
κ := min |ξ|=1,ξ⊥ū max i∈S 〈ξ, xiyi〉 > 0 (54)
if the data is sampled from absolutely continuous distribution.
To begin with, we first introduce the following lemma. Lemma 8. For the logistic loss function ` = ln(1+e−x), if 〈WΠ, ū〉 ≥ 0 and ‖P⊥WΠ‖ ≥ 2n/eκ = ϕ, then 〈
P⊥W1, ∂L̃ ∂W1
〉 ≥ 0. (55)
Proof. We first decompose Eq. (55) as two parts:〈 P⊥W1,
∂L̃ ∂W1
〉 = 1
n n∑ i=1 ˜̀′ i [ yi 〈 P⊥W1, ∂f(xi;W ) ∂W1 〉 − 〈 P⊥W1, ∂ ‖WΠ‖ ∂W1 〉] , (56)
where 〈 P⊥W1,
∂ ‖WΠ‖ ∂W1
〉 = 1 ‖WΠ‖ 〈 P⊥W1,WT1 · · ·WTLWL · · ·W2 〉 = 1
‖WΠ‖ 〈P⊥WΠ,P⊥WΠ〉 ≥ 0.
Since ˜̀′ < 0, we have〈 P⊥W1,
∂L̃ ∂W1 〉 ≥ 1 n n∑ i=1 ˜̀′ iyi 〈 P⊥W1, ∂f(xi;W ) ∂W1 〉 = 1 n n∑ i=1 〈 P⊥WΠ, xiyi ˜̀′(WΠ) 〉 . (57)
6This lemma is based on Lemma 12 in Soudry et al. (2018).
Let xjyj ∈ arg maxi∈S 〈−P⊥WΠ, xiyi〉 which means that 〈−P⊥WΠ, xjyj〉 ≥ κ‖P⊥WΠ‖.
Then we have
1
n n∑ i=1 〈 P⊥WΠ, xiyi ˜̀′(WΠ) 〉 = 1
n n∑ i=1 e−〈WΠ,(xi+δi)yi〉 1 + e−〈WΠ,(xi+δi)yi〉 〈−P⊥WΠ, xiyi〉
= 1
n n∑ i=1 e−〈WΠ,(xi+δi)yi〉 1 + e−〈WΠ,(xi+δi)yi〉 〈−P⊥WΠ,P⊥xiyi〉
≥ 1 n n∑ i=1 e−〈WΠ,(xi+δi)yi〉 1 + e−〈WΠ,(xi+δi)yi〉 〈−P⊥WΠ,P⊥xiyi〉
≥ 1 n
e−〈WΠ,(xj+δj)yj〉
1 + e−〈WΠ,(xj+δj)yj〉 〈−P⊥WΠ,P⊥xiyi〉+
1
n ∑ k∈Ck e−〈WΠ,(xk+δk)yk〉 1 + e−〈WΠ,(xk+δk)yk〉 〈−P⊥WΠ,P⊥xkyk〉 ,
(58)
where Ck = {k : 〈−P⊥WΠ,P⊥xkyk〉 ≤ 0}. Considering that xjyj is a support vector, the first term of (58) can be bounded as follows:
1
n
e−〈WΠ,(xj+δj)yj〉
1 + e−〈WΠ,(xj+δj)yj〉 〈−P⊥WΠ,P⊥xiyi〉
≥ κ n ‖P⊥WΠ‖e−〈WΠ,γū〉e ‖WΠ‖
e−〈WΠ,xjyj−γū〉
1 + e−〈WΠ,(xj+δj)yj〉
= κ
n ‖P⊥WΠ‖e−〈WΠ,γū〉e ‖WΠ‖
e−〈P⊥WΠ,P⊥xjyj〉
1 + e ‖WΠ‖e−〈P⊥WΠ,P⊥xjyj〉e−〈WΠ,γū〉
≥ κ 2n ‖P⊥WΠ‖e−〈WΠ,γū〉e ‖WΠ‖, (59)
where we use that ‖WΠ‖, 〈WΠ, γū〉 , 〈P⊥WΠ,P⊥xjyj〉 > 0. Each term of the second part of (58) can be bounded by
e−〈WΠ,(xk+δk)yk〉
1 + e−〈WΠ,(xk+δk)yk〉 〈−P⊥WΠ,P⊥xkyk〉
≥ e ‖WΠ‖e−〈WΠ,xkyk〉 〈−P⊥WΠ,P⊥xkyk〉 = e ‖WΠ‖e−〈WΠ,γū〉e−〈WΠ,xkyk−γū〉 〈−P⊥WΠ,P⊥xkyk〉 ≥ e ‖WΠ‖e−〈WΠ,γū〉e−〈−P⊥WΠ,P⊥xkyk〉 〈−P⊥WΠ,P⊥xkyk〉
≥ e ‖WΠ‖e−〈WΠ,γū〉 ( −1 e ) , (60)
where the second inequality follows from
〈WΠ, xkyk − γū〉 = 〈WΠ,P⊥xkyk〉+ 〈WΠ, xkyk − P⊥xkyk − γū〉 ≥ 〈WΠ,P⊥xkyk〉 = 〈P⊥WΠ,P⊥xkyk〉
while the last inequality comes from f(x) = −xe−x ≥ −1/e for x ≥ 0. Finally, we have〈 P⊥WΠ, (xi + δi)yi ˜̀′(WΠ) 〉 ≥ e−〈WΠ,γū〉e ‖WΠ‖ ( κ‖P⊥WΠ‖
2n − 1 e
) . (61)
Therefore, 〈 P⊥WΠ, (xi + δi)yi ˜̀′(WΠ) 〉 ≥ 0 if
‖P⊥WΠ‖ ≥ 2n
eκ = ϕ. (62)
We are now ready to prove the alignment phenomenon for the first layer. Let P⊥W1 denote the projection of rows of W1 onto ū⊥. We start from exploring the asymptotic behavior of
‖P⊥W1‖F ‖W1‖F
when t→∞. The update of P⊥W1(t+ 1) can be written explicitly as ‖P⊥W1(t+ 1)‖2F
= ‖P⊥W1(t)‖2F − 2η (t) 〈 P⊥W1(t),P⊥
∂L̃ ∂W1(t)
〉 + η(t)2 ∥∥∥∥∥P⊥ ∂L̃∂W1(t) ∥∥∥∥∥ 2
F
≤ ‖P⊥W1(t)‖2F − 2η (t) 〈 P⊥W1(t),P⊥
∂L̃ ∂W1(t)
〉 + η(t)2 ∥∥∥∥∥ ∂L̃∂W1(t) ∥∥∥∥∥ 2
F
≤ ‖P⊥W1(t)‖2F − 2η (t) 〈 P⊥W1(t),
∂L̃ ∂W1(t)
〉 + 2 ( L̃(W (t+ 1))− L̃(W (t)) ) (63)
where the last inequality follows from Eq. (30). We define a large enough step t0 as follows: for any t ≥ t0, we have
‖W1(t+ 1)‖2F = ‖W1(t)‖ 2 F − 2η(t) 〈 W1(t),
∂L̃ ∂W1(t)
〉 + η(t) 2 ∥∥∥∥∥ ∂L̃∂W1(t) ∥∥∥∥∥ 2
F
≥ ‖W1(t)‖2F ,
(64) where ”large enough t0” means that
ϕ2 + L̃(t0) ‖W1(t0)‖F → 0 (65)
as ‖W1‖F →∞. Suppose that there exists a t1 ≥ t0 such that ‖P⊥WΠ(t1 − 1)‖F < ϕ and ‖P⊥WΠ(t1)‖F ≥ ϕ, (66) which is to say (recalling Lemma 8)〈 P⊥W1(t),
∂L̃ ∂W1(t)
〉 ≥ 0
=⇒ ‖P⊥W1(t+ 1)‖2F ≤ ‖P⊥W1(t)‖ 2 F + 2
( L̃(W (t))− L̃(W (t+ 1)) ) , (67)
for t0 ≤ t1 ≤ t ≤ t2 and t2 = ∞ if we never have ‖P⊥WΠ(t)‖F < ϕ after t1. If there does not exist such a t1, then we directly conclude that
‖P⊥W1‖F ‖W1‖F → 0 since ‖W1‖F → ∞. On the other
hand, for any t0 ≤ t1 ≤ t ≤ t2
‖P⊥W1(t)‖2F ‖W1(t)‖2F
≤ ‖P⊥W1(t1)‖2F + 2
( L̃(W (t1))− L̃(W (t)) ) ‖W1(t1)‖2F
≤ ‖P⊥W1(t1)‖ 2 F + 2L̃(W (t1))
‖W1(t1)‖2F
≤ ϕ 2 + 2µ(t1)ϕ+ µ 2(t1) + 2L̃(W (t1)) ‖W1(t1)‖2F
= Φ(ϕ, t1)
‖W1(t1)‖2F (68)
where the last inequality follows from Eq. (31) and Φ(ϕ, t1) is defined by
Φ(ϕ, t1) = ϕ 2 + 2µ(t1)ϕ+ µ 2(t1) + 2L̃(W (t1)) ≥ Φ(ϕ, t′) (69) for any t′ ≥ t1 because the loss and µ never increase. Therefore we can conclude that
‖P⊥W1(t)‖2F ‖W1(t)‖2F ≤ Φ(ϕ, t) ‖W1(t)‖2F ≤ Φ(ϕ, t1) ‖W1(t1)‖2F → 0 (70)
for any t ≥ t1. As a result, | 〈v1(t), ū〉 | → 1. (71)

heading: B PROOFS OF SECTION 3.2
text: We present some useful properties and proofs of Lemma 3 and Lemma 4 in Section B.1. Section B.2 focuses on the divergences of weight norms. Section B.3 is about the convergence to KKT points(Theorem 5).
Additional notations We use Wij;k to represent the i-th row j-th column entry of the k-th layer weight martrix.

heading: B.1 USEFUL PROPERTIES AND PROOFS OF LEMMA 3 AND LEMMA 4
text: For any m×n matrix A, we denote v(A), an mn-dimensional vector, as the vectorized version of it:
v(A) =  A11 A21 . . . Am1 . . . Amn  , (72) then the trace operator can be represented by
tr ( ATB ) = v(A)T v(B) = v(B)T v(A). (73)
We first introduce the Euler’s theorem on homogeneous functions. Lemma 9 (Euler’s theorem on homogeneous functions). If f(W1, . . . ,WL) is a positive multi-ckhomogeneous function
f(ρ1W1, . . . , ρLWL) = L∏ k=1 ρckk f(W1, . . . ,WL) (74)
for positive constants ρk’s and ck ≥ 1, then we have: tr ( ∂f(W1, . . . ,WL)
∂Wk Wk
) = ckf(W1, . . . ,WL). (75)
Proof. Taking derivatives of ρk on both sides of Eq. (74) for any given k ∈ {1, . . . , L}, we have〈 Wk, ∂f
∂Wk
〉 = tr ( Wk ∂f
∂Wk
) = L∏ k′ 6=k ρ ck′ k′ f(x;W )ckρ ck−1 k . (76)
Since ρk is arbitrary, we let ρL = · · · = ρk = · · · = ρ1 = 1, then the above equation becomes tr ( Wk ∂f(W1, . . . ,WL)
∂Wk
) = ckf(W1, . . . ,WL) (77)
for any k ∈ {1, . . . , L}.
Furthermore, we have 〈 ∂f(x;W )
∂W ,W
〉 = L∑ k=1 tr ( ∂f(x;W ) ∂Wk Wk ) = Kf(x,W ) (78)
where K = ∑L k=1 ck. 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 x,
• if yf(x;W ) is locally Lipschitz, then so does yf(x+ δ(W );W ) with perturbation δ(W ).
Proof. For fixed x, suppose yf(W ) is locally Lipschitz on Y , then for each W ⊂ Y there is a ZW containing W such that yf(W ) is Lipschitz on ZW :
‖yf(W )− yf(V )‖ ≤ LW ‖W − V ‖ for W,V ⊂ ZW . (79) For the adversarial perturbation, by definition δ(W ) and δ(V ) are solutions of the inner maximization for the adversarial training, in other words,
yf(x+ δ(W );W ) ≤ yf(x+ δ(V );W ) (80) yf(x+ δ(V );V ) ≤ yf(x+ δ(W );V ) (81)
because then we will have `(x + δ(W );W ) > `(x + δ(V );W ) since ` is non-increasing under Assumption 1. As a result,
yf(x+ δ(W );W )− yf(x+ δ(V );V ) ≤ yf(x+ δ(V );W )− yf(x+ δ(V );V ) ≤ LW ‖W − V ‖ (82)
for yf(x + δ(W );W ) > yf(x + δ(V );V ). The result for yf(x + δ(W );W ) < yf(x + δ(V );V ) is similar.
• if ∀i : yif(xi;W ) have locally Lipschitz gradients, then so do yif(xi + δi(W );W ).
Proof. For fixed x, suppose y∇f(W ) is locally Lipschitz on Y , then for each W ⊂ Y there is a ZW containing W such that y∇f(W ), δ(W ) are Lipschitz on ZW , for W,V ⊂ ZW :
‖y∇f(x;W )− y∇f(x;V )‖ ≤ LW ‖W − V ‖ (83) ‖y∇f(x+ δ(W );W )− y∇f(x+ δ(V );W )‖ ≤ LWx‖δ(W )− δ(V )‖
≤ LWxLWδ‖W − V ‖ (84) Then
‖yi∇f(xi + δi(W );W )− yi∇f(xi + δi(V );V )‖ ≤ ‖yi∇f(xi + δi(W );W )− yi∇f(xi + δi(W );V )‖
+ ‖yi∇f(xi + δi(W );V )− yi∇f(xi + δi(V );V )‖ ≤ (LW + LWxLWδ) ‖W − V ‖. (85)

heading: B.1.1 PROOF OF LEMMA 3
text: Proof. The proof can be done for multi-ck-homogeneous networks as defined in Lemma 9. We first note that
∇xf(x; ρ1W1, . . . , ρLWL) = L∏ k=1 ρckk ∇xf(x;W1, . . . ,WL) (86)
by taking derivatives with respect to x on both sides of Eq. (74). Therefore ∇xf(x;W1, . . . ,WL) is also positive homogeneous. Under Assumption 1, we prove Lemma 3 in the following cases:
1. `2-FGM perturbation. This perturbations is taken as
δFGM(W ) = ˜̀′∇xf(x;W1, . . . ,WL)∥∥∥˜̀′∇xf(x;W1, . . . ,WL)∥∥∥ = − ∇xf(x;W1, . . . ,WL) ‖∇xf(x;W1, . . . ,WL)‖
(87)
because ˜̀′ < 0. Invoking Eq. (86), we know that δFGM(ρ1W1, . . . , ρLWL) = − ∏L k=1 ρ ck k ∇xf(x;W1, . . . ,WL)∏L
k=1 ρ ck k ‖∇xf(x;W1, . . . ,WL)‖
= − ∇xf(x;W1, . . . ,WL) ‖∇xf(x;W1, . . . ,WL)‖
= δFGM(W1, . . . ,WL). (88)
2. FGSM perturbation.
δFGSM(W ) = sgn (∇xf(x;W1, . . . ,WL)) , (89)
where sgn() denotes the sign function. Then we have
δFGSM(ρ1W1, . . . , ρLWL) = sgn ( L∏ k=1 ρckk ∇xf(x;W1, . . . ,WL) ) = δFGSM(W ) (90)
since ρk > 0 for any k thus will not affect the sign operation.
3. `2 and `∞-PGD perturbation. We only prove the case for `2-PGD and the case for `∞-PGD is similar.
δj+1PGD(W ) = PB(0, ) [ δjPGD(W )− ξ
∇xf(x;W1, . . . ,WL) ‖∇xf(x;W1, . . . ,WL)‖
] , (91)
where PB(0, ) denotes the projection operator, B(0, ) is the perturbation set, j is the step indices of PGD and ξ is the step size. We prove by induction. For j = 0, we have
δ1PGD(ρ1W1, . . . , ρLWL) = PB(0, ) [ −ξ ∇xf(x;W1, . . . ,WL) ‖∇xf(x;W1, . . . ,WL)‖ ] = δ1PGD(W1, . . . ,WL). (92)
If we have δjPGD(ρ1W1, . . . , ρLWL) = δ j PGD(W1, . . . ,WL), then for j + 1, we have
δj+1PGD(ρ1W1, . . . , ρLWL) = PB(0, ) [ δjPGD(ρW )− ξ ∏L k=1 ρk∇xf(x;W1, . . . ,WL)∏L
k=1 ρk ‖∇xf(x;W1, . . . ,WL)‖
]
= PB(0, ) [ δjPGD(W )− ξ
∇xf(x;W1, . . . ,WL) ‖∇xf(x;W1, . . . ,WL)‖ ] = δj+1PGD(W1, . . . ,WL). (93)
Therefore, these four adversarial perturbations are all scale invariant adversarial perturbations by our definition.

heading: B.1.2 PROOF OF LEMMA 4
text: Proof. This can be easily proved by noting that, for any multi-ck-homogeneous functions,
f(xi+δi(ρ1W1, . . . , ρLWL); ρ1W1, . . . , ρLWL) = L∏ k=1 ρckk f(xi+δi(W1, . . . ,WL);W1, . . . ,WL) (94) because δ(W ) is a scale invariant adversarial perturbations. Then f(x+ δ(W );W ) is still a homogeneous function and Lemma 9 can be applied to f(x+ δ(W );W1, . . . ,WL) and we have
tr ( ∂L̃ ∂Wk Wk ) = 1 n n∑ i=1 ˜̀′ iyitr ( ∂f(xi + δi(W );W1, . . . ,WL) ∂Wk Wk )
= −ck n n∑ i=1 e−γ̃iyif(xi + δi(W );W1, . . . ,WL)
= −ck n n∑ i=1 e−γ̃i γ̃i. (95)
Taking c1 = · · · = cL gives us Lemma 4.

heading: B.2 DIVERGENCES OF FROBENIUS NORMS OF WEIGHT MATRICES

heading: B.2.1 DIVERGENCES OF ALL LAYERS
text: 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-ck-homogeneous DNNs
1
cL
d‖WL‖2F dt = 1
cL−1
d‖WL−1‖2F dt = · · · = 1 c1 d‖W1‖2F dt
(96)
Remark. Note that a similar conclusion as that of Lemma 11 exists for gradient flow of the standard training for multi-1-homogeneous networks Du et al. (2018). We generalize this property to the adversarial training of multi-ck-homogeneous neural networks. When c1 = · · · = cL, we have that all layer grow at the same rate.
Proof. For any Wk,
d‖Wk‖2F dt = ∑ i,j
d ( Wij;kW T ji;k ) dt = −2 ∑ i,j ( ∂L̃ ∂Wij;k )T WTji;k
= 2ck n n∑ i=1 e−γ̃i γ̃i, (97)
where we use dWdt = − ( ∂L̃ ∂Wk )T and Lemma 4. One can then immediately notice that the above equation does not depend on any specific k, thus we have
1
cL
d‖WL‖2F dt = 1
cL−1
d‖WL−1‖2F dt = · · · = 1 c1 d‖W1‖2F dt . (98)

heading: B.2.2 PROOF OF THEOREM 3
text: We prove this theorem by exploring the time evolution of ρ.
Proof. We start from a multi-ck-homogeneous function then take c1 = · · · = cL. Recalling f(x;W ) = ρf(x; Ŵ ) where Ŵk = Wk/ ‖Wk‖F and
ρ = L∏ k=1 ρckk = L∏ k=1 ‖Wk‖ckF , (99)
the adversarially trained predictor with scale invariant adversarial perturbation is still homogeneous (see Eq. (94)): f (x+ δ(W );W ) = ρf ( x+ δ(Ŵ ); Ŵ ) . (100)
For ρk = ‖Wk‖F , we have
dρk dt = ck nρk n∑ i=1 e−γ̃i γ̃i (101)
by invoking Eq. (97). The dynamical evolution of ρ will then be
dρ dt = L∑ k=1 ρc11 · · · dρckk dt · · · ρcLL = L∑ k=1 c2kρ 2 ρ2k
( 1
n ∑ i e−γ̃i γ̂i
) . (102)
Let t0 denote the time such that all worst case adversarial examples are correctly classified. We study the trends for ρ after t0. On one hand, the empirical adversarial loss does not increase:
−dL̃ dt = − ∂L̃ ∂W dW dt = ∥∥∥∥dWdt ∥∥∥∥2
2
≥ 0. (103)
On the other hand, recalling our definition of normalized adversarial margin, let
m = arg min i∈{1,...,n} γ̃i = arg min i∈{1,...,n} ργ̂i (104)
and note the definition of t0, we have
e−γ̃m ≤ 1 n ∑ i e−γ̃i = L̃ =⇒ γ̃m ≥ ln ( 1 L̃(t) ) ≥ ln ( 1 L̃(t0) ) > 0 (105)
because L̃ does not increase and L̃(t) ≤ L̃(t0) < 1. This also implies that γ̃m, thus γ̃i for all i ∈ {1, . . . , n}, can not be arbitrarily close to 0. Otherwise one would conclude that L̃(t) may be arbitrarily close to 1 which is a contradiction. Therefore we can immediately conclude that dρ/dt > 0 in Eq. (102), which implies that ρ may diverge as t → ∞. To have a clearer view about the convergence property of ρ, we study the following relation regarding the time evolution of eρyif(xi+δi(Ŵ )) after t0:∑
i
deρyif(xi+δi(Ŵ );Ŵ ) dt = ∑ i eργ̂i γ̂i dρ
dt︸ ︷︷ ︸ (a)
+ ∑ i eργ̂iρyi df(xi + δi(Ŵ ); Ŵ )
dt︸ ︷︷ ︸ (b)
. (106)
The term (a) can be computed by invoking Eq. (102)
(a) = L∑ k=1 c2kρ 2 nρ2k ∑ i eργ̂i γ̂i ∑ j e−ργ̂j γ̂j  =
L∑ k=1 c2kρ 2 nρ2k  n∑ i=1 γ̂2i + 1 2 n∑ i 6=j γ̂iγ̂j ( eρ(γ̂i−γ̂j) + e−ρ(γ̂i−γ̂j) ) ≥
L∑ k=1 c2kρ 2 nρ2k ( n∑ i=1 γ̂i )2 ≥ L∑ k=1 ρ2ζ2 nρ2k , (107)
where the first inequality follows from x+ 1/x ≥ 2 for x ≥ 0 and we denote the minimum of ∑ i γ̂i for t ≥ t0 as ζ > 0. The existence of such ζ has been discussed below Eq. (105).
The term (b) needs more analysis. For any fixed adversarial example xi + δ(Ŵ ), we have
yi df(xi + δi(Ŵ ); Ŵ )
dt = yi L∑ k=1 tr
( ∂f(xi + δi(Ŵ ); Ŵ )
∂Ŵk
dŴk dt
) , (108)
where dŴk/dt can be computed as follows
dŴjl;k dt = ∑ m,n ∂Ŵjl;k ∂Wmn;k dWmn;k dt
= ∑ m,n
∂
∂Wmn;k  Wjl;k√ tr ( WkWTk )  dWmn;k dt
= 1
ρk
( dWjl;k dt − Ŵjl;k nρk n∑ i=1 yie −γ̃i γ̃i ) . (109)
On the other hand, we note that
dWk dt = − ∑ i ∂L̃ ∂f(xi + δi(W );W ) ( ∂f(xi + δi(W );W ) ∂Wk )T
= ρ
nρk ∑ j yje −γ̃j
( ∂f(xj + δj(Ŵ ); Ŵ )
∂Ŵk
)T (110)
because ∂f(W )∂Wk = ρ ρk ∂f(Ŵ ) ∂Ŵk . Combing Eq. (109) and Eq. (110), we have
dŴk dt = ρ
nρ2k ∑ j yje −γ̃j (∂f(xj + δj(Ŵ ); Ŵ ) ∂Ŵk )T − Ŵkf(xj + δj(Ŵ ); Ŵ )  . (111) Therefore
v (dŴk dt )T = ρ nρ2k ∑ j yje −γ̃jAkv ( ∂f(xj + δj(Ŵ ); Ŵ ) ∂Ŵk ) , (112)
where
Ak = I − v ( WTk ) v ( WTk )T ‖Wk‖2F = I − v ( ŴTk ) v ( ŴTk )T (113)
can be seen as a projector operator. Putting Eq. (112) into Eq. (108) will give us the expression
yi df(xi + δi(Ŵ ); Ŵ )
dt = L∑ k=1 ρ nρ2k ∑ j e−γ̃jv
( ∂γ̂j(Ŵ )
∂Ŵk
)T ATk v ( ∂γ̂i(Ŵ )
∂Ŵk
) . (114)
Now the term (b) in Eq. (106) is, by putting Eq. (114) back into it,
(b) = L∑ k=1 ρ2 nρ2k ∑ i eργ̂i ∑ j e−ργ̂jv ( ∂γ̂j ∂Ŵk )T ATk v ( ∂γ̂i ∂Ŵk ) = 1
2 L∑ k=1 ρ2 nρ2k n∑ i,j=1 v ( ∂γ̂i ∂Ŵk )T ATkAkv ( ∂γ̂j ∂Ŵk )[ eρ(γ̂i−γ̂j) + e−ρ(γ̂i−γ̂j) ] ︸ ︷︷ ︸
(c)
. (115)
Rearranging eρ(γ̂i−γ̂j) + e−ρ(γ̂i−γ̂j) as follows
eρ(γ̂i−γ̂j) + e−ρ(γ̂i−γ̂j) = eρ(γ̂i+γ̂j) + e−ρ(γ̂i+γ̂j) − (eργ̂j − e−ργ̂j )(eργ̂i − e−ργ̂i)
will allow us to rewrite (c) as
(c) = ∥∥∥∥∥∑ i eργ̂iAkv ( ∂γ̂i ∂Ŵk )∥∥∥∥∥ 2
2
+ ∥∥∥∥∥∑ i e−ργ̂iAkv ( ∂γ̂i ∂Ŵk )∥∥∥∥∥ 2
2
− ∥∥∥∥∥∑ i ( eργ̂i − e−ργ̂i ) Akv ( ∂γ̂i ∂Ŵk )∥∥∥∥∥ 2
2
= ∥∥∥∥∥∑ i eργ̂iAkv ( ∂γ̂i ∂Ŵk )∥∥∥∥∥ 2
2
+ ∥∥∥∥∥∑ i e−ργ̂iAkv ( ∂γ̂i ∂Ŵk )∥∥∥∥∥ 2
2
− ∥∥∥∥∥∑ i eργ̂iAkv ( ∂γ̂i ∂Ŵk ) − ∑ i e−ργ̂iAkv ( ∂γ̂i ∂Ŵk )∥∥∥∥∥ 2
2
≥ 0. (116)
Combing Eq. (107) and Eq. (116) with Eq. (106), we will have
1
n ∑ i deρyif(xi+δi(Ŵ );Ŵ ) dt ≥ L∑ k=1 ρ2(t)ζ2 n2ρ2k(t) . (117)
According to Eq. (101), we know that ∀k : dρk/dt > 0 after t0, therefore ∀k : ρ2/ρ2k is lower bounded by its value at t0 for t ∈ [t0,∞) because
d
dt
( ρ2
ρ2k
) = d
dt ρ2ck−2k L∏ k′ 6=k ρ 2ck′ k′  = 2(ck − 1)ρ2ck−3k ρ̇k
L∏ k′ 6=k ρ 2ck′ k′ + ρ 2ck−2 k L∑ k′ 6=k 2ck′ρ 2ck′−1 k′ ρ̇k′  L∏ k′′ 6=k′,k ρ 2ck′′ k′′  > 0, (118)
where ρ̇k denotes dρk/dt > 0 for any k due to Eq. (101). Integrating both sides of Eq. (117) from t0 to t gives us
1
n ∑ i ( eρ(t)yif(xi+δi(Ŵ );Ŵ (t)) − eρ(t0)yif(xi+δi(Ŵ );Ŵ (t0)) ) ≥ L∑ k=1 ∫ t t0 ρ2(τ)ζ2 n2ρ2k(τ) dτ
≥ L∑ k=1 ρ2(t0)ζ 2 n2ρ2k(t0) (t− t0), (119)
where the last inequality follows from Eq. (118). Let t→∞ in the above equation, we will have ρ = Ω (ln t)→∞ (120)
since yif(xi + δi(Ŵ ); Ŵ ) is upper bounded, which can be easily deduced considering that all weights have norm 1, and ζ is lower bounded as discussed before. Taking c1 = · · · = cL gives us the conclusion.
Note that ρ = ρc11 · · · ρ cL L and ρk for any k grows at the same rate for multi-c-homogeneous functions (Lemma 11), we immediately have Corollary 1. ∀k ∈ {1, . . . , L} : ρk →∞ as t→∞.

heading: B.3 CONVERGENCE TO KKT POINT

heading: B.3.1 PROOF OF THEOREM 4
text: Proof. Most calculations needed for the proof of this theorem have been done in Section B.2.2. According to Eq. (114), we have∑ i e−γ̃iyi df(x+ δi(Ŵ ); Ŵ ) dt ∝ L∑ k=1 1 ρ2k ∑ i e−γ̃i ∑ j e−γ̃jv ( ∂γ̂j(Ŵ ) ∂Ŵk )T ATk v ( ∂γ̂i(Ŵ ) ∂Ŵk ) =
L∑ k=1 1 ρ2k ∥∥∥∥∥∑ i e−γ̃iAkv ( ∂γ̂i ∂Ŵk )∥∥∥∥∥ 2
2
≥ 0. (121)

heading: B.3.2 PROOF OF THEOREM 5
text: The KKT conditions for the optimization problem Eq. (19) are
∀k : 1 2 ∂ρ2k ∂Wk − n∑ i=1 λi ∂γ̃i ∂Wk = 0 (122)
∀i ∈ {1, . . . , n} : λi(γ̃i − 1) = 0. (123) Following Dutta et al. (2013); Lyu & Li (2020), we define the approximate KKT point in our settings
Definition 3 (Adapted from Definition C.4 in Lyu & Li (2020)). The approximate KKT points of the optimization problem (19) are those feasible points which satisfy the following condtions:
1. ∥∥∥ 12 ∂‖W‖2∂W −∑ni=1 λi ∂γ̃i∂W ∥∥∥
2 ≤ χ;
2. ∀i ∈ {1, . . . , n} : λi(γ̃i − 1) ≤ ξ,
where χ, ξ > 0 and λi ≥ 0. These points are said to be (χ, ξ)-approximate KKT points.
We now present the proof of Theorem 5.
Proof. Let
‖W‖ = √√√√ L∑ k=1 ρ2k, (124)
V = W
γ̃ 1/K m
, (125)
where K = ∑L k=1 c = cL. Since cf(x;W ) = cγ̃mf(x;V ) (126) according to the definition of the multi-c-homogeneous functions and
cf(x;W ) = 〈 Wk, ∂f(x;W )
∂Wk
〉 , cf(x;V ) = 〈 Vk, ∂f(x;V )
∂Vk
〉 , (127)
we have ∂f(x;V )
∂V =
1
γ̃ (K−1)/K m
∂f(x;W )
∂W . (128)
Specifically, in the following, we will show that V is a (χ, ξ)-approximate KKT points of the optimization problem (19) with χ, ξ → 0 along the training trajectory. Because the homogeneous property of the network trained with scale invariant adversarial perturbations, it satisfies the MFCQ condition by simply noting that
∀i ∈ {1, . . . , n} : tr ( ∂γ̃i ∂Wk Wk ) = cγ̃i > 0. (129)
This makes a point being a KKT point a necessary condition for it to be the optimal solution.
We now show that the limit point of V along the adversarial training trajectory is an (χ, ξ)-approximate KKT point with χ, ξ → 0 starting with the first condition. Let
λi = (∥∥∥∥∥ ∂L̃∂W ∥∥∥∥∥ )−1 ‖W‖γ̃(K−2)/Km e−γ̃i , (130)
then we have∥∥∥∥∥V −∑ i λiyi ∂f(xi + δi(V );V ) ∂V ∥∥∥∥∥ 2
2
a = ∥∥∥∥∥ Wγ̃1/Km − ∑ i λiyi γ̃ (K−1)/K m ∂f(xi + δi(W );W ) ∂W ∥∥∥∥∥ 2
2 = 2( ∑ k ρ 2 k)
( ∏ k ρ 2c k ) 1/K γ̂ 2/K m
1− 〈 W, ∂L̃∂W 〉 ‖W‖ ∥∥∥ ∂L̃∂W ∥∥∥2 
≤ 2Lρ 2 k′
ρ2k′′ γ̂ 2/K m
1− 〈 W, ∂L̃∂W 〉 ‖W‖ ∥∥∥ ∂L̃∂W ∥∥∥2  = χ(t) (131)
where a follows from (128); k′ = arg maxk ρk and k′′ = arg mink ρk. This is the first condition for the limit point of V being an approximate KKT point. We can further show that χ→ 0 as t→ 0 by noting the following alignment phenomenon which was originally observed by Ji & Telgarsky (2020) and intended for standard training with fixed training examples:
Lemma 12 (Adapted from Theorem 4.1 in Ji & Telgarsky (2020)). Under Assumption 2 and Assumption 4 for exponential loss and homogeneous deep neural networks, along the trajectory of adversarial training with scale invariant adversarial perturbations, we have
∀k ∈ {1, . . . , k} : lim t→∞
〈 W (t), ∂L̃∂W (t) 〉 ‖W‖
∥∥∥ ∂L̃∂W (t)∥∥∥ = −1. (132) The extension of Theorem 4.1 in Ji & Telgarsky (2020), which was intended for fixed training examples, to our settings is because, by our construction for adversarial training with scale invariant adversarial perturbations, the adversarial training margin are locally Lipschitz with locally Lipschitz gradients and the prediction function f(x+ δ(W );W ) is positively (multi)homogeneous with respect to W (see Lemma 10 and Eq. (4)). Invoking Lemma 12 and considering that γ̂m can not be arbitrarily close to 07 and ∀k : ρk →∞ at the same rate according to Lemma 11 thus ρk′ρk′′ can not be infinite, we have,
lim t→∞
χ(t)→ 0. (133)
On the other hand, the second condition for the limit point of V being an approximate KKT point is
n∑ i=1 λi( γ̃i γ̃m − 1) = n∑ i=1 ‖W‖ γ̃ 2/K m (∥∥∥∥∥ ∂L̂∂W ∥∥∥∥∥ F )−1 e−γ̃i(γ̃i − γ̃m)
a ≤
∑ k ρ 2 k
ρ2/K γ̂ 2/K m n∑ i=1 e−γ̃i(γ̃i − γ̃m)〈 W, ∂L̃∂W
〉 b ≤ ∑ k ρ 2 k
ρ2/K γ̂ 2/K m n∑ i=1 ne−γ̃i(γ̃i − γ̃m) Kρe−γ̃m ∑ j yjf(xj + δj(Ŵ ); Ŵ )
c ≤
n ∑ k ρ 2 k
Kρ1+2/K γ̂ 2/K m n∑ i=1 e−(γ̃i−γ̃m) γ̃i − γ̃m γ̂m
d ≤
n ∑ k ρ 2 k
Keρ1+2/K γ̂ 1+2/K m
≤ nLρ 2 k′
Keρρ2k′′ γ̂ 1+2/K m
= ξ, (134)
where a follows from 〈 W, ∂L̃∂W 〉 ≤ ‖W‖ ∥∥∥ ∂L̃∂W ∥∥∥; b is due to Lemma 4 and ∀i : γ̃i ≥ γ̃m; c uses ∀i : γ̃i ≥ γ̃m again; d is due to e−xx is upper bounded by its value at x = 1 for x ≥ 0. Since ∀k : limt→∞ ρk(t) → ∞ at the same rate, we conclude that limt→∞
ρ2 k′ ρ2 k′′ can not be infinite thus
limt→∞ ξ(t)→ 0 because γ̂m can not be arbitrarily close to 0 and limt→∞ ρ→∞. Therefore, the limit point of V is an (χ, ξ)-approximate KKT point of the mini-norm problem along the trajectory of adversarial training with scale invariant adversarial perturbations where limt→∞ χ(t), ξ(t)→ 0. Restating the theorem in Dutta et al. (2013) regarding the relation between (χ, ξ)-approximate 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 (2020)). Let {xt : t ∈ N} be a sequence of feasible point of the optimization problem 19. xt is an (χt, ξt)-approximate KKT poiint for all t with two sequences {χt > 0 : t ∈ N} and {ξt > 0 : t ∈ N} and χt, ξt → 0. If xt → x as t→∞ and MFCQ holds at x, then x is a KKT point of this optimization problem.
We then immediately conclude that the limit point of {W (t)/‖W‖ : t ≥ 0} of gradient flow for the adversarial training objective Eq. (6) is along the direction of a KKT point of the optimization problem (19).
7See Eq. (105). In fact, it keeps increasing after some time according to Theorem 4.

heading: B.4 GENERALIZATION TO NON-SMOOTH CASE
text: It 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 are 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 ∈ −∂L̃(W (t)) (135)
where ∂L̃(W (t)) is the sub-differential. Then one can follow similar procedures as our approach to make the generalization.
Proof. For simplicity, we only consider multi-1-homogeneous networks here, i.e., c1 = · · · = cL = 1, which include the deep ReLU neural networks. Lemma 9 can be generalized to non-smooth case according to Lemma C.1 in Ji & Telgarsky (2020) or Theorem B.2 in Lyu & Li (2020):
Lemma 13 (Lemma C.1 in Ji & Telgarsky (2020)). Suppose f : Rn → R is locally Lipschitz and L-positively homogeneous, then for any W ∈ Rn and any W ∗ ∈ ∂f(W ),
〈W,W ∗〉 = Lf(W ). (136)
The starting point of the proof for Lemma 3 is the homogeneity of f(x;W ) and can be easily promoted to handle the non-smooth case.
With generalizations of Lemma 3 and Euler’s theorem on homogeneous functions for non-smooth case, the proof of Lemma 4 can also be generalized to non-smooth case accordingly because it is based on the Euler’s theorem on homogeneous functions and Lemma 3 for adversarial training. Specifically, it will become 〈
dWk dt ,Wk
〉 = 1
n n∑ i=1 e−γ̃i γ̃i. (137)
The proof of Theorem 3 adopts Lemma 4 and can be generalized to non-smooth case by combining the chain rule (Clarke, 1983) for gradient flow to ensure Eq. (103)
−dL̃ dt
= − 〈 ∂L̃(W (t)), dW
dt
〉 = ∥∥∥∥dWdt ∥∥∥∥
2
≥ 0 (138)
with similar approach as in Lemma B.9 in Ji & Telgarsky (2020) or Lemma 5.2 in Davis et al. (2018). Then generalizing the rest of the proof of Theorem 3 is straightforward.
Finally, the generalization of Theorem 5 to non-smooth case can also be done because it adopts Theorem 3, Lemma 4, the chain rule, and the gradient alignments Lemma 12 which holds for non-smooth case.

heading: B.5 DEEP LINEAR NETWORKS ADVERSARIALLY TRAINED WITH `∞ PERTURBATIONS
text: Following the settings of Section 3.1, the `∞-perturbation for deep linear networks f(x;W ) = WL · · ·W1x can be given exactly as
δ(W (t)) = − yisgn(WΠ(t)). (139)
According to Theorem 5, the adversarial training solution is formulated from solving the following optimization problem:
max 1
2 ‖W‖22 (140)
s.t. min i∈{1,...,n}
yiWΠxi − ‖WΠ‖1 ≥ 1. (141)
It can be seen that this optimization problem, a mixed-norm optimization problem, will have different solutions when compared to the margin-maximization problem of the original data, which will lead to a different decision boundary distinguishing adversarial training methods from the standard ones.
Besides, the constraint on (Eq. (8) for `2 perturbation) should also be changed accordingly such that the adversarial training examples are still linear separable:
≤ γm,1 (142) where γm,1 is the max-`1-norm margin:
γm,1 = max ‖u‖1=1 min i∈{1,...,n} yiuxi. (143)

heading: C SUPPLEMENTED EXPERIMENTS

heading: C.1 ADVERSARIAL TRAINING WITH DIFFERENT LOSS FUNCTIONS, ARCHITECTURES AND VARYING PERTURBATION SIZES
text: We present the results for adversarial training with different loss functions, architectures and varying perturbation sizes in this section to further verify our theorems and assumptions. We use two different models: one is a 3-layer neural network with the same architecture as in the Section 4; the other is a CNN with architecture Input-Conv-ReLU-Pooling-Conv-ReLU-Pooling-FC-FC, where Conv stands for convolution layer, FC stands for fully connected layer and Pooling is max-pooling layer.
For the 3-layer network, we conduct adversarial training using both FGSM and `∞-PGD perturbations with perturbation sizes = 8/255, 12/255 and 24/255 to perform binary classification where we choose all examples with labels ”3” and ”8” from MNIST to be our dataset. The loss function is logistic loss. Fig. 2(a) shows that for both FGSM and `∞-PGD 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 CNN, we conduct adversarial training using both FGSM and `∞-PGD perturbations with perturbation sizes = 16/255 and 32/255 to perform multi-classification 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. 3(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. 3(b) clearly shows that the adversarial traininig accuracy can reach 100% for all perturbation types and sizes, even the large size = 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 `2-FGM PERTURBATIONS
In the MNIST dataset, we adversarially trained a 3-layer neural network with the same architecture as in Section 4 using 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 `2-FGM perturbation with = 8 since even the standard model can fit `2-FGM adversarial examples easily in the MNIST dataset when the perturbation size is not large. As a comparison, we also standardly trained a model with the same architecture to evaluate the normalized margin for adversarial examples by attacking it with `2-FGM during its training process.
As showed in Fig.5(b), the adversarilly training accuracy reaches 100% very quickly, which supports Assumption 4. It can be seen in Fig.5(a) that the adversarial normalized margin keeps increasing during the adversarial training process while the standardly trained model maintains a lower adversarial normalized margin.
C.2.1 EXPERIMENTS ABOUT BINARY CLASSIFICATION FOR `2-FGM PERTURBATION
For the multi-classification task, let f(x;W )[j] denote the j-th output. Then the margin for an adversarial example xi + δi corresponding to the original example xi is defined by
γ̃i = f(xi + δi;W )[yi]−max j 6=yi f(xi + δi;W )[j],
and the margin for the adversarial data is defined to be
γ̃m = min i∈{1,...,n} γ̃i.
For completeness, we also conduct experiment about the binary classification where the model is adversarially trained with exponential loss (Fig.4) for `2-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−5. The hidden layer is of size 10000 and the activation function is
ReLU. The normalized margin for adversarial data is defined exactly as in Section 3.2. The adversarial perturbations during the adversarial training are given by `2-FGM with = 3. As showed in Fig.4, although extremely slowly, the normalized margin for adversarial data gradually increases during the adversarial training.

heading: C.3 DIVERGENCE OF WEIGHT NORMS FOR DEEP LINEAR NETWORKS DURING ADVERSARIAL TRAINING
text: We conduct adversarial training of deep linear networks with `2 perturbation on a linearly separable dataset. The loss function is logistic loss. Specifically, we use deep linear networks with layers 2, 3 and 4, respectively. Since the divergence is slow (∼ ln t), it is hard to observe that ‖Wk‖F → ∞. However, as showed in Fig. 6(a), Fig. 6(b) and Fig. 6(c), the trends that ‖Wk‖F for all layers of deep linear networks with different layers keep increasing are clear. Furthermore, we can see that the ratios ‖Wk‖2/‖Wk‖F for all layers of deep linear networks with different layers also keep increasing, as showed by Fig. 7(a), Fig. 7(b) and Fig. 7(c).

Review summaries:
*Implicit Bias of Adversarial Training for Deep Neural Networks* explores how minimizing the exponential loss (i.e., $l(x) = e^{-x}$) of a homogeneous neural network (i.e., a neural network such that $$ f = a_L W_L \circ \sigma_L \circ \cdots \circ \sigma_2 \circ a_1 W_1 = \prod^L_{k=1} a_k^c (W_L \circ \sigma_L \circ \cdots \circ \sigma_2 \circ W_1 $$ for activation functions $\sigma_L, \ldots, \sigma_2$, weights $W_L, \ldots, W_1$, $a_L, \ldots, a_1 > 0$, and $c \geq 1$) on samples with perturbations that maximizing the loss influences the optimized neural network's weights. Specifically, this paper proves that, for an exponential loss and a multi-c-homogeneous neural network, the limit point for $\frac{W}{\lVert W \rVert}$ with respect to the gradient flow  $$ \frac{dW}{dt} = - \left( \frac{d\tilde{\mathcal{L}}}{\partial W} \right)^T $$ of the adversarial training objective $$ \tilde{\mathcal{L}} = \frac{1}{n}\sum^n_{i=1}\ell(x_i + \delta_i(W), y_i) $$ under $\ell_2$-FGM, FGSM, $\ell_2$-PGD, and $\ell_\infty$-PGD is along the Karush-Kuhn-Tucker (KKT) point  of the constrained minimization problem $$ \min_{W_1, \ldots, W_L} \frac{1}{2} \lVert W \rVert^2_{\ell_2} \text{ s.t. } \tilde{\gamma_i} \geq 1 $$ where $\tilde{\gamma_i} = y_i f(x_i + \delta_i(W))$ and $W = (W_1, \ldots, W_L)$.  This theorem demonstrates that---for a class of neural networks and adversarial perturbations---adversarial training has an implicit bias that can be expressed in closed form. This result provides an important contribution to understanding  how adversarial training improves adversarial robustness. 

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.

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.