Title: IMPLICIT BIAS OF GRADIENT DESCENT BASED AD-VERSARIAL TRAINING ON SEPARABLE DATA

Abstract: Adversarial training is a principled approach for training robust neural networks. Despite of tremendous successes in practice, its theoretical properties still remain largely unexplored. In this paper, we provide new theoretical insights of gradient descent based adversarial training by studying its computational properties, specifically on its implicit bias. We take the binary classification task on linearly separable data as an illustrative example, where the loss asymptotically attains its infimum as the parameter diverges to infinity along certain directions. Specifically, we show that for any fixed iteration T , when the adversarial perturbation during training has proper bounded 2 -norm, the classifier learned by gradient descent based adversarial training converges in direction to the maximum 2 -norm margin classifier at the rate of O(1/ √ T ), significantly faster than the rate O (1/ log T ) of training with clean data. In addition, when the adversarial perturbation during training has bounded q -norm with q ≥ 1, the resulting classifier converges in direction to a maximum mixed-norm margin classifier, which has a natural interpretation of robustness, as being the maximum 2 -norm margin classifier under worst-case q -norm perturbation to the data. Our findings provide theoretical backups for adversarial training that it indeed promotes robustness against adversarial perturbation.

1. INTRODUCTION:

Deep neural networks have achieved remarkable success on various tasks, including visual and speech recognitions, with intriguing generalization abilities to unseen data (Krizhevsky et al., 2012; Hinton et al., 2012) . One salient feature of deep models is its overparameterization, with the number of parameters several orders of magnitude larger than the training sample size. As a consequence of such overparameterization, it is likely that the empirical loss function, in addition to being non-convex, can have substantial amount of global minimizers (Choromanska et al., 2015) , while only a small subset of global minimizers have the desired generalization properties (Brutzkus et al., 2018) .

Contrary to the worst-case reasoning above, researchers have observed that simple first-order algorithm such as Stochastic Gradient Descent (SGD)1 , performs surprisingly well in practice, even without any explicit regularization terms in the objective function (Zhang et al., 2017) . Inspired by classical computational learning theories, one plausible explanation of such a remarkable phenomenon is that the training algorithm enjoys some implicit bias. That is, the training algorithm tends to converge to certain kinds of solutions (Neyshabur et al., 2015b; c) , and SGD converges to low-capacity solutions with the desired generalization property (Brutzkus et al., 2018) . Recently, some exciting works have related the implicit bias to specific first-order algorithms (Wilson et al., Despite the aforementioned phenomenal success achieved by deep neural networks, it is observed that adversarially constructed small perturbation to the input can potentially fool the network into making wrong predictions with high confidence (Szegedy et al., 2014; Goodfellow et al., 2015) . This issue raises serious concerns about using neural network for some security-sensitive tasks (Papernot et al., 2017) . Researchers have devised various mechanisms to generate and defend against adversarial perturbations (Goodfellow et al., 2015; Moosavi-Dezfooli et al., 2016; Carlini and Wagner, 2017; Athalye et al., 2018; Xie et al., 2018; Papernot et al., 2016) . However, most of the defense mechanisms are heuristic or ad-hoc, which lack principled theoretical justification (Carlini and Wagner, 2016; He et al., 2017) . Inspired by literatures in robust optimization (Wald, 1939; Ben-Tal et al., 2009) , Feige et al. (2015) ; Madry et al. (2018) formalize the notion of achieving adversarial robustness (i.e., having small adversarial risk) as solving the following minimax optimization problem

EQUATION

)

where ∆ is the set that each sample could be contaminated by arbitrary perturbation chosen within this set. As a common practice, adversarial training refers to the finite-sample empirical version of (1) without access to the underlying distribution D that min

EQUATION

A commonly adopted approach to solving (2) is the the Gradient Descent based Adversarial Training (GDAT) method. At each iteration, GDAT first solves the inner maximization problem (approximately) for adversarial perturbations, and then uses the gradient of the loss function evaluated at the perturbed samples to perform a gradient descent step on the parameter θ. A natural question is then how adversarial training helps the trained model in achieving adversarial robustness. Some recent theoretical results partially answer this question, such as deriving adversarial risk bound (Athalye et al., 2018) , relating it to the distributionally robust optimization (Sinha et al., 2018) , and characterizing trade-offs between robustness and accuracy via regularization (Zhang et al., 2019) .

Yet, all existing results neglect the algorithmic effect during the training process in promoting adversarial robustness. Inspired by the significant role of algorithmic bias in the generalization of neural networks, it is natural to ask Does gradient descent based adversarial training enjoy any implicit bias property? If so, does the implicit bias provide insights on how adversarial training promotes robustness?

Motivated by these questions, in this paper, we study the algorithmic effect of adversarial training by investigating the implicit bias of GDAT. Due to current technical limits in directly analyzing deep neural networks, we analyze a simpler model, with the key characteristics that the model overfits the training data while being able to generalize well. Specifically, we take the binary classification with linearly separable data as an example. This helps us focus on the effect of implicit bias without dealing with complicated structures of neural networks.

Main Contributions. We summarize our main theoretical findings below.

• Our first part of result shows an interesting interplay between adversarial perturbation and implicit bias of the gradient descent (GD). By exploiting this interplay, we show a property of adversarial training that is not known in the literature before: adversarial training accelerates convergence. Specifically, when the perturbation is bounded by 2 -norm, i.e., ∆ = {δ ∈ R d : ||δ|| 2 ≤ c}, with proper choice of c, the gradient descent based adversarial training is directionally convergent that lim t→∞ θ t ||θ t ||2 = u 2 , where u 2 is the maximum 2 -norm margin hyperplane (i.e., standard SVM) of the training data. In addition, when the perturbation level c is set according to T appropriately, the rate of convergence is O(1/ √ T )2 , which is exponentially faster than the rate O (1/ log T ) when we use standard clean training, i.e., training with clean data using gradient descent. Based on this, we establish that the convergence of training loss on clean data using GDAT is almost exponentially faster than standard clean training using GD.

• Our second part of result shows that adversarial training adapts the implicit bias of gradient descent for different adversarial perturbation geometry. Specifically, when the perturbation is bounded by q -norm for q ≥ 1, i.e., ∆ = {δ ∈ R d : ||δ|| q ≤ c}, with proper choice of c, the gradient descent based adversarial training is directionally convergent that lim t→∞ θ t ||θ t ||2 = u 2,q , where u 2,q is the maximum mixed-norm margin hyperplane of the training data. We further reveal natural interpretation of robustness that we obtain the maximum 2 -norm margin classifier under worst-case q -norm perturbation.

Notations. For two vectors x, y ∈ R d , x, y = 

2. BACKGROUND:

We consider a binary classification problem using a dataset

S = {(x i , y i )} n i=1 ⊂ R d × {-1, +1}.

We aim to learn a linear decision boundary f (x) = θ, x and its associated classifier y(x) = sign (f (x)), by solving the empirical risk minimization problem:

min θ∈R d L(θ; S) = min θ∈R d n i=1

(y i x i θ), where (•) is some loss function.

(

EQUATION

In what follows, we suppress the explicit presentation of S when the context is clear, and we focus on the exponential loss (r) = exp(-r). We point out that our analysis can be further extended to other smooth loss functions with tight exponential tail such as logistic loss.

We assume the dataset S is linearly separable, i.e., there exists u such that min i∈[n] y i x i u > 0.

Under this assumption, one notable feature of problem (3) is that there is no finite minimizer, and

L(θ) → 0 only if ||θ|| 2 → ∞ along certain directions.

In fact, there is a polyhedral cone C, such that for any u ∈ C, we have lim a→∞ L(au) = 0.

Several recent results have studied the implicit bias of gradient descent algorithm on separable dataset. Throughout this paper, we assume the perturbation set is an q -norm ball with radius c, i.e., ∆ = {δ ∈ R d : ||δ|| q c}. Under the general framework of adversarial training in (2), we aim to minimize the empirical adversarial risk min

EQUATION

Note that, given any θ, the inner maximization problem in (4) admits a closed form solution. Then the gradient descent based adversarial training (GDAT) algorithm runs iteratively that at the t-th iteration, we first solve the inner maximization problem by deriving the worst adversarial perturbation of each sample. It is not difficult to see that for each sample, the worst perturbation is δ t i = cy i δ * t , where δ * t = argmin δ:||δ||q≤1 δ, θ t . Then, letting each sample's perturbed counterpart be ( x t i , y i ) = (x i + δ t i , y i ), we take gradient of the loss function evaluated at the perturbed samples and perform a gradient descent step, i.e.,

θ t+1 = θ t -η t ∇ θ L (θ t ; {( x t i , y i )} n i=1 ))

, where η t > 0 is some prespecified stepsize. We present the outline of GDAT in Algorithm 1.

3. THEORETICAL RESULTS:

In this section, we show that the GDAT algorithm possesses implicit bias, which depends on the perturbation set during training. We provide explicit characterization of the implicit bias, and further conclude that such implicit bias indeed promotes robustness against adversarial perturbation.

Algorithm 1 Gradient Descent based Adversarial Training (GDAT) with q -norm Perturbation

Input: Number of iterations T , perturbation level c, stepsizes {η t } T t=0 , samples {x i , y i } n i=1 . Initialize: θ 0 ← 0. for t = 0, . . . , T -1 do for i = 1, . . . , n do Compute δ t i = cy i argmin ||δ||q≤1 δ, θ t Let ( x t i , y i ) ← (x i + δ t i , y i ). end for θ t+1 ← θ t -η t n n i=1 exp -y i x i θ t (-y i x i ). end for

Let us start with some definitions. Consider a dataset S = {(x i , y i )} n i=1 ⊂ R d × {-1, +1}. Given p, q > 0 such that 1/p + 1/q = 1, the q -norm margin of H θ on S is defined as γ q (θ) = min i∈[n] y i x i θ/||θ|| p . Note that for x i ∈ R d , |θ x|/||θ|| p measures the q distance between x i and the hyperplane H θ = {x ∈ R d : θ x = 0}. Since y i ∈ {-1, +1}, when H θ correctly classifies all samples, γ q (θ) measures the minimal q distance between the samples in S and H θ . Given that γ q (θ) is scaleinvariant with respect to θ, without loss of generality, we restrict ||θ|| p = 1. We also identify the hyperplane H θ by its normal vector θ. Definition 3.1. For p, q > 0 with 1/p + 1/q = 1, the maximum q -norm margin hyperplane u q of S = {(x i , y i )} n i=1 ⊂ R d × {-1, +1} and its associated q -norm margin γ q are defined as

EQUATION

)

We denote SV(S) as the support vectors of S, i.e., SV(S) = argmin (x,y)∈S u q , yx .

By the separability assumption, u q is an optimal hyperplane that correctly classifies all samples with the maximal margin γ q > 0. Next, by the notion of margin defined above, we characterize the landscape of empirical adversarial risk in (4) based on the perturbation level c. Proposition 3.1. Let p, q > 0 satisfy 1/p + 1/q = 1. Given a nonnegative scalar c, where 0 ≤ c < γ q = max ||θ||p≤1 min i∈[n] y i x i θ, problem (4) has infimum 0 but does not admit a finite minimizer. When c > γ q , problem (4) has a unique finite minimizer θ(c), and is equivalent to the standard clean training with explicit p -norm regularization. That is, there exists λ(c) > 0 such that

θ(c) = argmax θ∈R d 1 n n i=1 exp(-y i x i θ) + λ(c)||θ|| p .

It is not difficult to see that for c < γ q , any perturbed dataset S = {( x i , y i )} n i=1 , with ||x ix i || q c for all i, is still linearly separable, which directly follows from the definition of γ q above. On the other hand, when c > γ q , by the definition of γ q , there exists some perturbed dataset S = {( x i , y i )} n i=1 , with ||x ix i || q c for all i, such that S is no longer linearly separable.

3.1. ADVERSARIAL PERTURBATION WITH BOUNDED 2 -NORM:

In this subsection, we analyze both the empirical adversarial risk convergence and the parameter convergence of the case when the perturbation set ∆ in ( 4) is an 2 -norm ball with radius c.

Adversarial Risk Convergence. We first analyze the convergence of empirical adversarial risk (4) using GDAT. One substantial roadblock of minimizing ( 4) is its non-smoothness, in the sense that L adv (θ) is not differentiable at the origin, and its Hessian ∇ 2 L adv (θ) explodes around the origin. To address the challenge, our key observation is that, by the next lemma, at each iteration, there exists an acute angle between the update on θ t and the maximum 2 -norm margin hyperplane u 2 . This gives a lower bound on ||θ t || 2 . Lemma 3.1.

Take ∆ = {δ ∈ R d : ||δ|| 2 ≤ c} in problem (4). Given c < γ 2 , we have that -∇L adv (θ), u 2 ≥ L adv (θ)(γ 2 -c) > 0 for any θ ∈ R d .

We highlight that despite its simple proof, Lemma 3.1 and its generalization to q -perturbation is a crucial step for analyzing both adversarial risk and implicit bias. In addition, our techniques here can also be adapted to simplify the proof of Lemma 10 in (Gunasekar et al., 2018a) , which, in comparison, is more technically involved.

Since we initialize GDAT (Alg. 1) using θ 0 = 0, any perturbation inside ∆ will have no effect on the adversarial loss. Hence we take clean samples as adversarial examples at the first iteration of GDAT. From Lemma 3.1, we have the following simple corollary showing that our whole solution path {θ t } T t=1 is bounded away from the origin. Corollary 3.1. Let θ 0 = 0 in Algorithm 1 with q = 2, we have: ||θ t || 2 ≥ η 0 γ 2 for all t ≥ 1.

By Corollary 3.1, we bypass the non-differentiability issue at the origin and also control the Hessian ∇ 2 L adv (θ) throughout the entire training process. Similar to (Ji and Telgarsky, 2018) , in the next theorem, we show that the loss L adv (θ), although not uniformly smooth, is locally L adv (θ)-smooth. Consequently, by the smoothness based analysis of the gradient descent algorithm, we establish the convergence of the empirical adversarial risk.

Theorem 3.1. Suppose ||x i || 2 ≤ 1 for all i = 1 . . . n. For GDAT (Alg. 1) with 2 -norm perturbation, i.e., ∆ = {δ ∈ R d : ||δ|| 2 c}, we set c < γ 2 , η 0 = 1 and η t = η ≤ min{ γ2/e (1+c) 3 γ2+2c(1+c) , 1} for t ≥ 1, then we have

EQUATION

)

In comparison with the standard clean training using GD (Ji and Telgarsky, 2018) , this theorem states that we pay an extra (γ 2c) -2 factor in the risk convergence of adversarial training. However, this direct comparison is too pessimistic since we compare the adversarial risk with the standard risk (corresponding to ∆ = {0}). Interestingly, as seen later in Corollary 3.2, we prove that the convergence of standard risk in GDAT is significantly faster than its counterpart in the standard clean training using GD.

Parameter Convergence. We then show that if we set the perturbation level c < γ 2 in the GDAT algorithm, GDAT with 2 -norm perturbation possesses the same implicit bias as the standard clean training using GD, i.e., we have lim t→∞ θ t ||θ t ||2 = u 2 . Intuitively, GDAT with 2 -norm perturbation searches for a decision hyperplane that is robust to 2 -norm perturbation. Since the learned decision hyperplane in the standard clean using GD converges to u 2 , which is already the most robust decision hyperplane against 2 -norm perturbation to the data, GDAT retains the implicit bias of standard clean training using GD. Surprisingly, even though both GDAT in the adversarial training and GD in the standard clean training converge in directions to u 2 , their rates of directional convergence are significantly different as shown later. Specifically, letting the perturbation level c depend on the total number of iterations T in the GDAT algorithm, the directional error after T iterations in GDAT algorithm can be significantly smaller than the error of GD in the standard clean training.

We first show that the projection of θ t onto the orthogonal subspace of span(u 2 ) is bounded.

Lemma 3.2. Define α(S) = min ||ξ||2=1,ξ∈span(u2) ⊥ max (x,y)∈SV(S) ξ, yx , where we assume SV(S) spans R d . Let θ ⊥ be the projection of vector θ onto span(u 2 ) ⊥ . Then there exists a constant K that only depends on α(S) and log n, such that ||θ t ⊥ || 2 ≤ K for any t ≥ 0 in the GDAT algorithm.

Note that the same α(S) is defined in (Ji and Telgarsky, 2019) and proved to be positive with probability 1 if the data is sampled from absolutely continuous distribution. We then show in the next lemma that ||θ t || 2 goes to infinity, where we provide a refined analysis to establish the acceleration of the directional convergence in comparison with the standard clean training.

Lemma 3.3. Under the same conditions in Theorem 3.1, and let α = α(S) defined in Lemma 3.2. Then for all t ≥ 0, we have

||θ t || 2 ≥ log tη(γ 2 -c) 2 n 1+1/α log 2 t /(γ 2 -c).

Lemma 3.3 provides the key insight to establish the acceleration of directional convergence. Specifically, it allows us to set c depending on the total number of iterations T , so that ||θ T || 2 is sublinear in T , in comparison with being logarithmic in T in standard clean training as in Ji and Telgarsky (2018) .

We are now ready to present the main theorem for parameter convergence.

Theorem 3.2 (Speed-up of Parameter Convergence). Under same conditions in Theorem 3.1, and let α = α(S) and K be defined in Lemma 3.2. In GDAT with 2 -norm perturbation, let c and total

number of iterations T satisfy γ 2 -c = n 1+1/α log T ηT 1/2

, and define θ T = θ T ||θ T ||2 . We have

EQUATION

One might argue that the polynomial dependence on sample size n in ( 7) is too pessimistic, making the GDAT unfavorable in comparison with the standard clean training. We show that this is not an issue by a direct comparision of iteration complexity to achieve ||θ Tu 2 || 2 ≤ for a given precision 

> 0. Specifically, given > 0, to achieve ||θ T -u 2 || 2 ≤ , GDAT needs O n (1+1/α) -

L(θ T ) = O exp -µ √ T /log T ,

where µ is a constant dependent on η, α, n.

Note that the empirical clean risk decreases at the rate of O exp(-√ T ) up to a logarithmic factor in the exponent. In comparison, using standard clean training with GD, we only have

L(θ T ) = O (1/T ) (Soudry et al., 2018). 3.2 ADVERSARIAL PERTURBATION WITH BOUNDED q -NORM

In this subsection, we generalize our results to the case where the perturbation set is some bounded q -norm ball. To facilitate our discussion, we first define a robust version of SVM. Definition 3.2. For a given separable dataset S with q -norm margin γ q and c < γ q , letting 1/p + 1/q = 1, the robust SVM against q -norm perturbation parameterized by c is

EQUATION

Remark 3.1 (Maximum Mixed-norm Margin). Note that problem (8) is equivalent to solving for a maximum mixed-norm margin hyperplane. Specifically, by the KKT condition of (8), there exists η(c) > 0, such that (8) is equivalent to the following problem: min Note that the constraint in ( 8) is equivalent to min ||δi||q≤c y i (x i + δ i ) θ ≥ 1, ∀i = 1, . . . , n. By a simple scaling argument, in the following lemma, we see the robust nature of (8). Lemma 3.4. Under the same notations in Definition 3.2, problem (8) is equivalent to:

θ∈R d ||θ|| 2 + η(c)||θ|| p s.t. y i x i θ ≥ 1, ∀i = 1, . . . , n. (9) Now define || • || = || • || 2 + η(c)|| • || p , it is clear that || • || defines a norm

EQUATION

)

We denote the (unique) solution to problem (10) as u 2,q (c). In what follows, we surpress explicit presentation of c when the context is clear.

The equivalent formulation (10) provides a clear interpretation on the robustness of (10). In particular, the robust SVM against q -norm perturbation parameterized by c is in fact the SVM problem on the the dataset S(c, q), which is generated from S by placing a q -norm ball with radius c around each samples, i.e., S(c, q) = {(x, y)

: ∃i ∈ [n], s.t., ||x -x i || p c, y = y i }.

In other words, u 2,q is the maximum 2 -norm margin classifier under worst case q -norm perturbation bounded by c.

In the remaining part of this section, we first analyze the convergence of the empirical adversarial risk, and then establish the implicit bias of GDAT with q perturbation for q ∈ [1, ∞]. Our analysis for q ∈ {1, ∞} is based on approximation argument. For ease of presentation, we only discuss when q ∈ (1, ∞) in the main text, and defer the discussion for q ∈ {1, ∞} in Appendix D.

Adversarial Risk Convergence. Our analysis is similar to the analysis for GDAT with 2 perturbation, where we use similar techniques to address issues such as non-differentiability at the origin and Hessian explosion of L adv (θ) around the origin. Theorem 3.3. Suppose ||x i || 2 ≤ 1 for i = 1, . . . , n, and let 1 p + 1 q = 1. In the GDAT with q -norm perturbation, setting c < γ q and letting

EQUATION

)

We point out here that ( 6) is a special case of (11). In particular, by the definition of γ 2,q (c), we have that γ 2,2 (c) = γ 2c, which recovers bound ( 6) from ( 11).

Parameter Convergence. We show that if we set c < γ q in the GDAT algorithm with stepsizes specified in Theorem 3.3, with q perturbation, the algorithm still possesses implicit bias property, i.e., θ t still has directional convergence, and the limiting direction depends on the perturbation set ∆. Theorem 3.4 (Implicit Bias of GDAT with q -norm Perturbation). Under the same conditions in Theorem 3.3, define θ t = θ t ||θ t ||2 , then we have:

1 -θ t , u 2,q = O log n log t

Combining Theorem 3.4 and Lemma 3.4, we conclude that GDAT with q -norm perturbation indeed promotes robustness against q perturbation. Using GDAT with q -norm perturbation will result in a classifier which is the maximum 2 -norm margin classifier under worst case q -norm perturbations to the samples bounded by c. The learned classifier will have q -norm margin at least c. As we increase perturbation level c to γ q , the learned classifier will converge to maximum q -norm margin classifier.

4. NUMERICAL EXPERIMENT:

In this section, we first conduct numerical experiments on linear classifiers to backup our theoretical findings. We further empirically extend our method to neural networks, where our numerical results demonstrate that our theoretical results can be potentially generalized.

Linear Classifiers. We investigate the empirical performance of the GDAT algorithm on linear classifiers, with training set S = {((-0.5, 1), +1) , ((-0.5, -1), -1) , ((-0.75, -1), -1) , ((2, 1), +1)}.

It is straightforward to verify that the maximum 2 -norm margin classifier is u 2 = (0, 1).

Considering 2 -norm perturbations, we first run standard clean training with GD, and GDAT with 2 -norm perturbation (c = 0.95γ 2 ), for 2.5 × 10 4 number of iterations. In both GD and GDAT we take constant stepsizes, with η = 1 and η = 0.1, respectively. By Figure 1 (a), we see that the convergence rate of adversarial loss using GDAT is similar to the convergence rate of clean loss using GD. However, when we directly compare the clean losses of GDAT and GD, GDAT clearly demonstrates an exponential speed-up in comparison with GD, which is consistent with Corollary 3.2. Additionally, as pointed out by Theorem 3.2, GDAT also enjoys significant speed-up in terms of the directional convergence of θ t to u 2 . We also compare the norm growth ||θ t || 2 , and observe that the norm generated by GDAT grows much faster than the norm generated by GD, which is also in alignment with our discussions in Section 3.1.

We further run GDAT with ∞ -norm perturbation (c = 0.5). By Lemma 3.4, we have that u 2,∞ = (0, 1). Note that the Hausdorff distance between q -norm ball and ∞ -norm ball distance goes to zero as q goes to infinity. Thus, we have that (10) for q = 1000 is a close approximation of (10) for q = ∞. We run two versions of GDAT, where one uses q -norm perturbation with q = 1000, and the other uses ∞ -norm perturbation. We run both algorithms with stepsize η = 0.1 for 5.0 × 10 5 number of iterations, and we present the results in Figure 1 (b). We find that the two training methods behave similarly. In addition, the empirical directional convergence rates of θ t just differ slightly. case on adversarial training of more complicated neural networks. We conduct experiments on neural network with one hidden layer. We take the two classes from MNIST dataset with label "2" and "9" to form our training set S. We also vary the width of the hidden layer in {64×64, 128×128, 256×256}.

One major difference from the case of linear classifiers is that we cannot solve the inner maximization problem of (2) exactly as it does not admits a closed-form solution. Instead, we solve the inner problem approximately using projected gradient descent with 20 iterations and stepsize 0.01. We test two versions of GDAT, where one adopts 2 -norm perturbations (c = 2.8), and the other uses ∞norm perturbations (c = 0.1). For standard clean training and the outer minimization problem in (2), we use the stochastic gradient descent algorithm with batch size 128 and constant stepsize 10 -5 .

We compare the loss and classification accuracy, which are evaluated using the clean training samples, of standard clean training and GDAT. By Figure 2 , we see that GDAT indeed accelerates the convergence of both loss and classification accuracy on clean training samples. The performance gap is most obvious when the width of the hidden layer is small, and reduces gradually as we increase the width of the hidden layer. We argue that such reduction comes from the fact that as network width increases, the margin on the samples outputted by the hidden layer also increases. As suggested by Theorem 3.2, in this case, a larger perturbation level c should be used. We conduct additional experiments with various perturbation level in Appendix E to empirically verify our argument. 

5. DISCUSSIONS:

We investigate the implicit bias of GDAT for linear classifier. There are several plausible natural extensions. For example, we can represent a linear classifier using a deep linear network, which is significantly overparameterized. Some recent results characterize the implicit bias of gradient descent for training deep linear networks (Ji and Telgarsky, 2019) and linear convolutional networks (Gunasekar et al., 2018b) A PROOF OF PROPOSITION 3.1

Proof. Suppose c < γ q . Letting θ α = αu q for α > 0, we have

L adv (θ α ) = 1 n n i=1 exp -y i x i θ α + c||θ α || p = 1 n n i=1 exp -αy i x i u q + cα ≤ 1 n n i=1

exp (-αγ q + cα) .

Letting α → ∞, we obtain lim α→∞ L adv (θ α ) = 0, which implies inf θ∈R d L adv (θ) = 0. Note that L(θ) does not admit any finite minimizer since L adv (θ) > 0 for any θ ∈ R d .

If c > γ q , by the definition of maximum q -norm margin, for any θ ∈ R d , there exists (y i , x i ) ∈ S for some i ∈ [n] such that y i x i θ γ q ||θ|| p . Hence, L adv (θ) exp n -1 (cγ q )||θ|| p . Then it is easy to see that L adv (θ) has bounded sublevel set and hence a finite minimizer θ. Since L adv (θ) is convex, we examine its first-order KKT condition, given by

EQUATION

)

Consider the regularized problem with regularization parameter η:

min θ∈R d 1 n n i=1 exp -y i x i θ + η||θ|| p .

Its first-order KKT condition is

EQUATION

)

Looking at (12) and ( 13) together, by taking η = c n n i=1 exp -y i x i θ + c|| θ|| p , we have that the solution to the adversarial training problem θ is also the solution to the regularized problem.

To facilitate our later discussions, we point out that by the conjugacy of p -norm and q -norm, (4) has the following equivalent form that

EQUATION

In fact, one can verify that the GDAT algorithm is equivalent to gradient descent algorithm on (14).

B PROOFS FOR SECTION 3.1:

Proof of Lemma 3.1. Recall we have L adv (θ) = 1 n n i=1 max ||δ||2≤c exp -y i (x i + δ i ) θ . For each sample (x i , y i ) ∈ S, given a classifier θ, the worse case perturbation is

δ i = argmax ||δ||2≤c exp -y i (x i + δ) θ = argmin ||δ||2≤c y i δ θ. The corresponding loss is L adv (θ) = 1 n n i=1 exp -y i (x i + δ i ) θ .

Since for a fixed δ i , the function exp -y i (x i + δ i ) θ is convex in θ, hence the gradient of L adv (θ) is

-∇L adv (θ) = 1 n n i=1 exp -y i (x i + δ i ) θ y i (x i + δ i ).

Then from the definition of u 2 (5), we have

EQUATION

where in the second inequality holds since || δ i || 2 c and ||u 2 || 2 = 1.

Proof of Corollary C.1. Since L adv (θ) is not differentiable at θ 0 = 0, we use subgradient (note that L adv (θ) is convex) at 0. Specifically, we take ∇L adv (θ

0 ) = 1 n n i=1 z i ∈ ∂L adv (θ 0 ). Then we have θ 1 , u 2 = η 0 n i z i , u 2 ≥ η 0 γ 2 ,

where the last inequality uses the definition of γ 2 . By Lemma 3.1, we have θ t , u 2 ≥ η 0 γ 2 for all t ≥ 1, which also implies v, u 2 ≥ η 0 γ 2 and hence ||v t || 2 ≥ η 0 γ 2 for v ∈ θ t , θ t+1 .

Proof of Theorem 3.1. For simplicity, we let z i = y i x i , where we have ||z i || 2 ≤ 1 as we assume x i 2 ≤ 1. We have

∇L adv (θ) = 1 n n i=1 exp -z i θ + c||θ|| 2 -z i + c θ ||θ|| 2 , ∇ 2 L adv (θ) = 1 n n i=1 exp -z i θ + c||θ|| 2 -z i + c θ ||θ|| 2 -z i + c θ ||θ|| 2 + 1 n n i=1 exp -z i θ + c||θ|| 2 c ||θ||I - θθ ||θ|| 2 /||θ|| 2 2 = 1 n n i=1 exp -z i θ + c||θ|| 2 z i z i -2 cz i θ ||θ|| 2 + c 2 θθ /||θ|| 2 2 + cI/||θ|| 2 -cθθ /||θ|| 3 2 .

Note that the Hessian expression indicates that the objective is highly non-smooth around origin, and the loss is not even differentiable at origin. However, we shall prove that starting from origin, every iteration generated by GADT stays away from the origin with distance bounded below.

Using Taylor's expansion, and by definition θ t+1 = θ tη t ∇L adv (θ t ), we have

EQUATION

where λ(H(v)) max denotes the largest eigenvalue of H(v), where

H(v) = 1 n I i=1 n exp -z i v + c||v|| 2 z i z i -2 cz i v ||v|| 2 + c 2 vv /||v|| 2 2 + cI/||v|| 2 -cvv /||v|| 3 2 .

To upper bound H(v), we need a lower bound on ||v||, which is readily given by Corollary C.1. That is, ||v|| 2 ≥ η 0 γ 2 .

We now analyze (18) for t ≥ 1, where we show that L adv (θ t ) is locally smooth with parameter proportional to L adv (θ t ), and with proper stepsize, the risk is monotonely decreasing. Note that z i z t i ≤ I, -2c

z i v ||v||2 ≤ 2cI, c 2 vv /||v|| 2 2 ≤ c 2 I. Now since ||v t || 2 ≥ η 0 γ 2 , we have cI/||v|| 2 - cvv /||v|| 3 2 ≤ 2c η 0 γ2 I. Plugging them in, we have H(v) ≤ 1 n i exp -z i v + c||v|| 2 1 + 2c + c 2 + 2c η 0 γ 2 I = L adv (v) 1 + 2c + c 2 + 2c η 0 γ 2 I,

and ( 18) reduces to

EQUATION

)

Suppose L adv (θ t+1 ) > L adv (θ t ), and let M = (1 + c) 2 + 2c η 0 γ2 . We have

L adv (θ t+1 ) ≤ L adv (θ t ) -η t ||∇L adv (θ t )|| 2 2 + (η t ||∇L adv (θ t )||) 2 2 M L adv (θ t+1 ),

which implies

EQUATION

)

Meanwhile, if we choose η t satisfying

EQUATION

then we have the right hand side of ( 20) is upper bounded by L adv (θ t ), and we have

L adv (θ t+1 ) ≤ 1 - M (η t ) 2 2 ||∇L adv (θ t )|| 2 2 -1 L adv (θ t ) -η t ||∇L adv (θ t )|| 2 2 < L adv (θ t

), which is clearly a contradiction. Hence, if η t satisfies (21), by ( 19) we have

EQUATION

)

where the last inequality holds by the choice of η t in (21).

Note that if (21) holds for t = 1 for η 1 = η, by induction it is easy to see that with constant stepsize η t = η for t ≥ 1, (21) holds for all t ≥ 1. Hence for t ≥ 1, we choose stepsize η such that ηL adv (θ

1 ) (1 + c) 2 + 2c η 0 γ2 ≤ 1. Note that L adv (θ 1 ) = 1 n n i=1 exp -z i θ 1 + c||θ 1 || 2 ≤ exp (1 + c)η 0 since ||θ 1 || ≤ η 0 . Then we only require η ≤ exp -(1 + c)η 0 • η 0 γ 2 (1 + c) 2 η 0 γ 2 + 2c = exp -(1 + c)η 0 • η 0 (1 + c)γ 2 /(1 + c) (1 + c) 2 η 0 γ 2 + 2c ≤ γ 2 /e (1 + c) 3 γ 2 + 2c(1 + c) ,

where in the last inequality we take η 0 = 1 and use basic inequality exp (-x) x ≤ e -1 for x ≥ 1. In summary, we choose η 0 = 1 and η t = η = min{ γ2/e (1+c) 3 γ2+2c(1+c) , 1} for t ≥ 1, then by previous argument, we have ( 22) holds for all t ≥ 1. Now we are ready to apply the standard smoothness-based analysis of gradient descent using ( 22), take any θ ∈ R d , we have

||θ t+1 -θ|| 2 2 = ||θ t -θ|| 2 2 -2η t ∇L adv (θ t ), θ t -θ + (η t ) 2 ||∇L adv (θ t )|| 2 2 ≤ ||θ t -θ|| 2 2 -2η t L adv (θ t ) -L adv (θ) + (η t ) 2 ||∇L adv (θ t )|| 2 2 ≤ ||θ t -θ|| 2 2 -2η t L adv (θ t ) -L adv (θ) + 2η t L adv (θ t ) -L adv (θ t+1 ) = ||θ t -θ|| 2 2 -2η t L adv (θ t+1 ) -L adv (θ) ,

where the first inequality holds by the convexity of L adv (θ), and the second inequality holds by ( 22). Now sum up the above inequality from s = 1 to t -1. By η t = η ≤ 1 = η 0 and L adv (θ s+1 ) ≤ L adv (θ s ), we have

L adv (θ t ) -L adv (θ) ≤ 1 2tη ||θ 1 -θ|| 2 2 ≤ 1 tη ||θ|| 2 2 + ||θ 1 || 2 2 .

Now since θ is arbitrary, letting θ = log(t) γ2-c • u 2 , we have

||θ|| 2 2 + ||θ 1 || 2 2 ≤ log 2 t (γ 2 -c) 2 + (1 + c) 2 , and L adv (θ) = 1 n n i=1 exp -z i u 2 • log t γ 2 -c + c • log t γ 2 -c ≤ 1 t ,

which yields

L adv (θ t ) ≤ 1 t + log 2 t (γ 2 -c) 2 + (1 + c) 2 = O log 2 t tη(γ 2 -c) 2 .

Proof of Lemma 3.2. For simplicity, we let

z i = y i x i and i (θ) = exp -z i θ + c||θ|| 2 . Define α = min ||ξ||2=1,ξ∈span(u2) ⊥ max i∈SV(S)

ξ, z i

where SV(S) denotes the set of support vectors. It has been shown in Ji and Telgarsky (2019) (Lemma 2.10) that α > 0 with probability 1 if the data is sampled from absolutely continuous distribution.

We have

EQUATION

where z j ∈ S is arbitrary, by definition of α: -z j , θ t ⊥ ≥ α||θ t ⊥ || 2 . We bound the first term as

j (θ t ) -z j , θ t ⊥ ≥ exp -(z j ) θ t + c||θ t || 2 α||θ t ⊥ || 2 = exp -(z j ) θ t ⊥ -(z j ) θ t u2 + c||θ t || 2 α||θ t ⊥ || 2 ≥ exp -θ t , γ 2 u 2 exp α||θ t ⊥ || 2 α||θ t ⊥ || 2 exp c||θ t || 2

, where the second inequality uses z j , u 2 ≥ γ 2 .

On the other hand, we can bound the second term in (23) as

1 n zi,θ t ⊥ ≥0,i =j i (θ t ) -z i , θ t ⊥ ≥ 1 n zi,θ t ⊥ ≥0,i =j exp -z i θ t + c||θ t || 2 -z i , θ t ⊥ = 1 n zi,θ t ⊥ ≥0,i =j exp -z i θ t u2 -z i θ t ⊥ + c||θ t || 2 -z i , θ t ⊥ ≥ exp -θ t , γ 2 u 2 exp(c||θ t || 2 ) exp(-z i θ t ⊥ ) -z i , θ t ⊥ ≥ exp -θ t , γ 2 u 2 exp(c||θ t || 2 )(- 1 e ),

where in the last inequality holds since θ t , u 2 ≥ 0, z i , θ t u2 = z i u 2 θ t u 2 ≥ γ 2 θ t , u 2 and -x exp(-x) ≥ -1 e for x ≥ 0. Plugging the two bounds above into (23), we have

∇L adv (θ t ), θ t ⊥ ≥ exp -θ t , γ 2 u 2 exp(c||θ t || 2 ) 1 n exp α||θ t ⊥ || 2 α||θ t ⊥ || 2 - 1 e ,

which is non-negative when

EQUATION

where the last inequality uses (22) .

Now let t 0 satisfy ||θ t0-1 ⊥ || 2 < K and ||θ t0-1 ⊥ || 2 ≥ K . Define t 1 = min{s ≥ t 0 : ||θ s ⊥ || 2 < K }, when ||θ s ⊥ || 2 ≥ K for all s ≥ t 0 we define t 1 = ∞.

That is for any t ∈ {t 0 , . . . , t 1 -1}, we have ||θ t ⊥ || 2 ≥ K . then for any s such that t 0 ≤ s < t 1 , summing (24) up from t 0 to s -1 yields:

||θ s ⊥ || 2 2 ≤ ||θ t0 ⊥ || 2 2 + 2 L adv (θ t0 ) -L adv (θ s ) ≤ ||θ t ⊥ || 2 2 + 2 exp(1 + c) ≤ ||θ t ⊥ || 2 2 + 18

, where we use L adv (θ t ) ≤ L adv (θ 1 ) ≤ exp(1 + c) and c < 1. This inequality shows that for

θ t ∈ {θ t0 , . . . , θ t1-1 } ⊂ {θ : ||θ ⊥ || 2 ≥ K }, ||θ t ⊥ || 2 ≤ ||θ t0 ⊥ || 2 + 18.

Then, we only need to bound ||θ t0:

⊥ || 2 to conclude the proof, where t 0 is the first time θ t enters {θ : ||θ ⊥ || 2 ≥ K }. We have

θ t0 ⊥ = θ t0-1 ⊥ + η t0-1 P ⊥ 1 n n i=1 i (θ t0-1 )(z i -c θ t0-1 ||θ t0-1 || 2 ) ,

where P ⊥ (•) denotes the projection onto span(u 2 ) ⊥ . Note that t 0 is the first time θ t (re)-enters the region {θ : ||θ ⊥ || 2 ≥ K }, and thus ||θ t0-1

⊥ || 2 < K . We have ||θ t0 ⊥ || 2 ≤ K + η t0-1 (1 + c) ≤ K + 1 + c < K + 2

, where the last inequality we use c < γ 2 ≤ 1.

In summary, we have shown that for any t such that ||θ t ⊥ || 2 ≥ K , we have ||θ t ⊥ || 2 ≤ K + 20, and we conclude that ||θ t ⊥ || 2 = K + 20 = K for all t ≥ 0. Note that K only depends α(S) and sample size n.

Proof of Lemma 3.3. To obtain a lower bound on ||θ t || 2 , we first denote θ t = θ t u + θ t ⊥ , where θ t u denotes the projection of θ onto span(u 2 ), and θ t ⊥ denotes the projection of θ onto span(u 2 ) ⊥ . We have

1 n n i=1 exp(-z i θ t u -z i θ t ⊥ ) ≤ log 2 t tη(γ 2 -c) 2 exp(-c||θ t || 2 ).

Let us assume that ||θ t ⊥ || is bounded so that exp(||θ t ⊥ ||) ≤ M , which will be verified immediately. Choosing an arbitrary support vector z i , we have 0

EQUATION

Now we only need to show that ||θ t ⊥ || ≤ M for all t for some M . Since we have shown in Lemma 3.2 that ||θ t || 2 ≤ K, we choose M = e K ≤ exp 20+log n α = O(n 1 α ), and the lower bound (25) becomes

EQUATION

which concludes our proof.

Proof of Theorem 3.2. We denote θ t = θ t u + θ t ⊥ , where θ t u denotes the projection of θ onto span(u 2 ), and θ t ⊥ denotes the projection of θ onto span(u 2 ) ⊥ . Combine Lemma 3.2 and Lemma 3.3, we have

1 - θ t ||θ t || 2 , u 2 = 1 - θ t u2 , u 2 + θ t ⊥ , u 2 ||θ t || 2 ≤ 1 - θ t u2 , u 2 ||θ t || 2 + K ||θ t || 2 = 1 - ||θ t u2 || 2 ||θ t || 2 + K ||θ t || 2 ≤ 1 - ||θ t u2 || 2 2 ||θ t || 2 2 + K ||θ t || 2 = ||θ t ⊥ || 2 2 ||θ t || 2 2 + K ||θ t || 2 ≤ K 2 ||θ t || 2 2 + K ||θ t || 2 .

By our choice of c and

T that γ 2 -c = n 1+1/α log 2 T ηT 1/2

, together Lemma 3.3, the Theorem holds as desired.

Proof of Corollary 3.2. By Lemma 3.3 and the the choice of parameters that γ

2 -c = n 1+1/α log 2 T ηT 1/2

, we have:

||θ T || 2 ≥ ηT n (1+1/α) log 2 T 1/2 .

Together with Theorem 3.1, we have

L(θ T ) = L adv (θ T ) exp -c||θ T || 2 log 2 T T η(γ 2 -c) 2 exp -c ηT n (1+1/α) log 2 T 1/2 = O exp -c ηT n (1+1/α) log 2 T 1/2 .

where the last equality holds by the parameter choice γ

2 -c = n 1+1/α log 2 T ηT 1/2 . Finally, letting µ = c η n 1+1/α)

1/2 , the claim follows immediately.

C PROOFS FOR SECTION 3.2:

In this section, we consider general q -norm perturbations. In short, we show that no matter how small the perturbation is, adversarial training changes the implicit bias of standard clean training using gradient descent, and adapt it to specific norm we choose for adversarial training.

Intuitively, we might expect that under the q -norm perturbation the implicit bias of gradient descent algorithm changes to converging in direction to q -norm max margin solution u q . We provide a counter example here. Consider S = {z 1 = (x 1 , y 1 ), z 2 = (x 2 , y 2 )} with x 1 = (10, 1), x 2 = (-10, -1) and y 1 = 1, y 2 = -1.

It is easy to see that the ∞ -norm max margin solution is u ∞ = (1, 0) with γ ∞ = 10, and the

2 -norm max margin solution is u 2 = ( 10 √ 101 , 1 √ 101 ) with γ 2 = √ 101.

Without perturbation, we have that the gradient descent initialized at the origin converges in direction to 2 -norm max margin solution u 2 with one step. Now we take l ∞ -norm perturbation with c = 0.5, the negative gradient is given by: -∇L adv (θ

) = 1(θ) 2 (z 1 -c • sign(θ)) + 2(θ) 2 (z 2 -c • sign(θ)

). We initialize gradient descent at the origin with any constant step size. By the symmetry of the training data, we have that θ t always stays always inside quadrant I, and converges in direction to u = (

√ 361 √ 362 , 1 √ 362 ), which is neither u ∞ or u 2 ,

but inside the interior of convex hull of u ∞ and u 2 . In fact, u exactly equals to the u 2,∞ defined in (10).

where p-1 θ denotes taking element-wise (p -1)-th power of θ.

Note that we have ||∂||θ|| p || q = 1. By the conjugacy of p -norm and q -norm with 1 p + 1 q = 1, we have||θ|| p = max ||s||q≤1 θ, s . Hence we upper bound the first term in Hessian ∇ 2 L adv (θ) above by

EQUATION

)

We further have:

(p -1)||θ|| p-1 p diag( p-2 θ) ≤ (p -1) diag( p-2 θ) d p p-1 ||θ|| p-1 ∞ ≤ (p -1)d p p-1 I ||θ|| ∞ ≤ (p -1)d 3p-2 2p-2 I ||θ|| 2 .

Together with the fact that p ≥ 1, we bound the Hessian ∇ 2 L adv (θ) as:

∇ 2 L adv (θ) ≤ L adv (θ) (1 + c √ d) 2 + c(p -1)d 3p-2 2p-2 1 ||θ|| 2 I.

Note that the Hessian expression indicates that the objective is highly non-smooth around origin. However, as shown in Corollary C.1, starting from origin, θ t always stays away from the origin with distance bounded below.

Using Taylor expansion, and by θ t+1 = θ tη t ∇L adv (θ t ), we have

EQUATION

where λ (H(v)) max denotes the largest eigenvalue of H(v), and

H(v) = L adv (v) (1 + c √ d) 2 + c(p -1)d 3p-2 2p-2 1 ||v|| 2 I.

Since η 0 = 1, by Corollary C.1, for any t ≥ 1, we have ||θ t || 2 γ 2,q . Letting m p = (1 + c √ d) 2 + c(p -1)d 3p-2 2p-2 1 γ2,q , and since that L adv (θ) is a convex function, we obtain that

L adv (θ t+1 ) ≤ L adv (θ t ) -η t ||∇L adv (θ t )|| 2 2 + (η t ||∇L adv (θ t )||) 2 2 m p max{L adv (θ t+1 , L adv (θ t )}.

We then show by contradiction that we have L adv (θ t+1 ) < L adv (θ t ). Assume this is not the case, then we have:

L adv (θ t+1 ) ≤ 1 - M (η t ) 2 2 ||∇L adv (θ t )|| 2 2 -1 L adv (θ t ) -η t ||∇L adv (θ t )|| 2 2

However, if we choose η t satisfying η t ≤ 2 mqL adv (θ t ) , we have the right hand side of previous inequality strictly smaller than L adv (θ t ), which is clearly a constradiction. Hence when we choose η t ≤ 2 mqL adv (θ t ) , we have L adv (θ t+1 ) < L adv (θ t ) and

EQUATION

Now by induction, if we choose η t = η ≤ 1 mqL adv (θ 1 ) for t ≥ 1, then we have (33) holds for all t ≥ 1. Note that we have an upper bound of L adv (θ 1 ), which is

EQUATION

where δ i denotes the worst case perturbation to x i , and θ 1 u denotes projection of θ 1 onto span(u 2,q ), and θ ⊥ denotes projection of θ 1 onto span(u 2,q ) ⊥ .

In summary, we have that if

EQUATION

we have

L adv (θ t+1 ) ≤ L adv (θ t ) -η||∇L adv (θ t )|| 2 2 + (η||∇L adv (θ t )||) 2 2 m p L adv (θ t ) (36) ≤ L adv (θ t ) - η 2 ||∇L adv (θ t )|| 2 2 (37)

where the last inequality holds since ηm p L adv (θ t ) ≤ ηm p L adv (θ 1 ) ≤ 1. Now for any θ ∈ R d , we have

||θ t+1 -θ|| 2 2 = ||θ t -θ|| 2 2 -2η t ∇L adv (θ t ), θ t -θ + (η t ) 2 ||∇L adv (θ t )|| 2 2 ≤ ||θ t -θ|| 2 2 -2η t L adv (θ t ) -L adv (θ) + (η t ) 2 ||∇L adv (θ t )|| 2 2 ≤ ||θ t -θ|| 2 2 -2η t L adv (θ t ) -L adv (θ) + 2η t L adv (θ t ) -L adv (θ t+1 ) = ||θ t -θ|| 2 2 -2η t L adv (θ t+1 ) -L adv (θ)

, where the first inequality holds by the convexity of L adv (θ), and the second inequality holds by (37). Summing up the above inequality from s = 1 to t -1 and by η t = η ≤ 1 = η 0 together with L adv (θ s+1 ) ≤ L adv (θ s ), we have

EQUATION

)

Since θ is arbitrary, by choosing θ = log(t) γ2,q • u 2,q , we have

||θ|| 2 2 + ||θ 1 || 2 2 ≤ log 2 t γ 2 2,q + (1 + c √ d) 2 ,

and

EQUATION

)

Parameter Convergence: Intuition. Before we formally prove the implicit bias of GDAT, we provide some intuitions here for better understanding. We claim that u ∞ = lim 

a i (z i -c∂||θ t || p ), s.t. a i ≥ 0, z i θ ≥ 1, ∀i = 1, . . . n,

a i (z i θ -1) = 0, ∀i = 1, . . . n. Defining a = (a 1 , . . . , a n ) and ( θ, a) = (||θ|| p c + 1)θ, (||θ|| p c + 1)a , it is easy to see that ( θ, a) is a solution to the following system

EQUATION

s.t.:

EQUATION

)

EQUATION

)

or min

θ ||θ|| 2 + η(c)||θ|| p s.t. z i θ ≥ 1, ∀i = 1, . . . n.

for some proper η(c) that depends on c.

Proof of Theorem 3.4. Recall that in Theorem 3.3 we showed in (36) the following recursion

L adv (θ t+1 ) ≤ L adv (θ t ) -η||∇L adv (θ t )|| 2 2 + (η||∇L adv (θ t )||) 2 2 m p L adv (θ t ) ≤ exp -η ||∇L adv (θ t )|| 2 2 L adv (θ t ) + m p η 2 2 ||∇L adv (θ t )|| 2 2 ≤ exp -ηγ 2,q ||∇L adv (θ t )|| 2 + m p η 2 2 ||∇L adv (θ t )|| 2 2 .

where the last inequality holds by Lemma C.1.

Applying the previous inequality recursively from s = 1 to t -1, we have

L adv (θ t ) ≤ exp -ηγ 2,q t-1 s=1 ||∇L adv (θ s )|| 2 + t-1 s=1 m p η 2 2 ||∇L adv (θ s )|| 2 2 .

Now since in the proof of Theorem 3.3 we showed that ηm p < 1 (35), combining the above inequality this with (37), we have

t-1 s=1 m p η 2 2 ||∇L adv (θ s )|| 2 2 = t-1 s=1 η 2 ||∇L adv (θ s )|| 2 2 = L adv (θ 1 ) -L adv (θ t ) ≤ L adv (θ 1 ).

Combining this inequality with the upper bound on L adv (θ 1 ) in (34), we have

L adv (θ t ) ≤ exp -ηγ 2,q t-1 s=0 ||∇L adv (θ s )|| 2 -γ 2 2,q + (1 + c √ d) .

Now for all i ∈ [n], we have:

exp -min ||δi||q≤c y i (x i + δ i ) θ t ≤ n exp -ηγ 2,q t-1 s=0 ||∇L adv (θ s )|| 2 -γ 2 2,q + (1 + c √ d) , which yields min ||δi||q≤c y i (x i + δ i ) θ t ≥ ηγ 2,q t-1 s=0 ||∇L adv (θ s )|| 2 + γ 2 2,q -(1 + c √ d) -log n.

Dividing both sides by ||θ|| 2 , and since lim t→∞ L adv (θ t ) = 0, we have lim t→∞ ||θ t || 2 = ∞. Hence,

EQUATION

≥ γ 2,q , where the last inequality holds by

||θ t || 2 ≤ η t-1 s=0 ||∇L adv (θ s )|| 2 .

Hence in summary, we have

min ||δi||q≤c y i (x i + δ i ) lim t→∞ θ t ||θ t || 2 ≥ γ 2,q .

Hence, we have lim t→∞ θ t /||θ t || 2 is a solution to (10), but notice that the solution to ( 10) is unique since a multiple of its optimal solution would be the solution to (8) that min 

θ∈R d 1 2 ||θ|| 2 2 s.t. min δi∈∆i(q) y i (x i + δ i ) θ ≥ 1, ∀i = 1, . . . ,

i (x i + δ i ) θ.

It is easy to see that for c < γ ∞ , both γ 2,∞ and u 2,∞ are well defined, and γ 2,∞ > 0.

Before showing parameter convergence, we first prove that the adversarial risk goes to zero. To avoid analyzing ∞ -perturbation directly, which can go messy. For λ > 0, we define a smooth approximation of 1 -norm that

h λ (θ j ) = θ 2 j + λ, and H λ (θ j ) = d j=1 h λ (θ j ).

Note that as λ → 0, H λ (θ) → ||θ|| 1 uniformly. We then define a smoothified version of (47) that we let perturbation set be ∆

EQUATION

EQUATION

Note that the Hausdorff distance between ∆ i (λ) and {δ : ||δ|| ∞ ≤ c} converges to 0 as λ goes to 0. It can be seen that when λ → 0, the smoothified problem (48) reduces to (47). That is, lim λ→0 γ 2,λ = γ 2,∞ and lim λ→0 u 2,λ = u 2,∞ .

Theorem D.1. Let perturbation set be ∆

i (λ) = {δ : ∀j ∈ [d], |δ j | ≤ c h λ (θj )

|θj | }, and let its associated adversarial risk be

EQUATION

Proof. By the definition of perturbation set that

∆ i = {δ : ∀j ∈ [d], |δ j | ≤ c h λ (θj ) |θj | }, we have L adv (θ) = 1 n n i=1 exp -y i x i θ + cH λ (θ) .

By some simple calculation, we have

∇H λ (θ) = θ 1 θ 2 1 + λ , . . . , θ d θ 2 d + λ , ∇ 2 H λ (θ) = diag λ (θ 2 1 + λ) 3/2 , . . . , λ (θ 2 d + λ) 3/2 . Then, it holds that ∇L adv (θ) = 1 n n i=1 exp -z i θ + cH λ (θ) (-z i + c∇H λ (θ)) , ∇ 2 L adv (θ) = 1 n n i=1 exp -z i θ + cH λ (θ) z i z i + c 2 ∇H λ (θ)∇H λ (θ) -2z i ∇H λ (θ) + c∇ 2 H λ (θ) . It can be verified that ∇ 2 L adv (θ) ≤ (1 + 2c √ λ ) 2 L adv (θ)I.

By Talyer expansion, we have

L adv (θ t+1 ) ≤ L adv (θ t ) -η||∇L adv (θ t )|| 2 2 + (1 + 2c √ λ ) 2 η 2 2 max{L adv (θ t ), L adv (θ t+1 }||∇L adv (θ t )|| 2 2 . (50) Now we show that L adv (θ t+1 ) ≥ L adv (θ t ) does not hold when η ≤ 1 (1+2cλ -1/2 ) 2 L adv (θ t )

. Suppose the contrary holds. By (50), we have

L adv (θ t+1 ) ≤ 1 - η 2 ||∇L adv (θ t )|| 2 2 2 (1 + 2c √ λ ) 2 -1 L adv (θ t ) -η||∇L adv (θ t )|| 2 2 < L adv (θ t ).

where the last inequality holds by η =

1 (1+2cλ -1/2 ) 2 L adv (θ t ) .

Hence we obtain a contradiction.

Note that L adv (θ 0 ) = 1, and if η ≤

1 (1+2cλ -1/2 ) 2 , η ≤ 1 (1+2cλ -1/2 ) 2 L adv (θ t )

holds for t = 0, and L adv (θ 1 ) ≤ 1. Consequently, we can inductively show that L adv (θ t ) ≤ 1 for all t, and η ≤ 1 (1+2cλ -1/2 ) 2 L adv (θ t ) always holds if we let η = 1 (1+2cλ -1/2 ) 2 . By the choice of η, we obtain the following recursion taht ) -L adv (θ) , where the second inequality holds by convexity and (51). Summing up the previous inequality from s = 0 to s = t -1 and by L adv (θ s+1 ) ≤ L adv (θ s ), we have

L adv (θ t+1 ) ≤ L adv (θ t ) -η||∇L adv (θ t )|| 2 2 + (1 + 2c √ λ ) 2 η 2 L

L adv (θ t ) -L adv (θ) ≤ 1 2tη ||θ|| 2 2 .

Taking θ = log t γ 2,λ u 2,λ , we have

L adv (θ) = 1 n n i=1 max δi∈∆i(λ) exp -y i (x i + δ i ) θ = 1 n n i=1 max δi∈∆i(λ)

exp -y i (x i + δ i ) log t γ 2,λ u 2,λ ≤ 1 t .

where the last inequality holds by max δi∈∆i y i (x i + δ i ) u 2,λ ≥ γ 2,λ . Hence we obtain L adv (θ t ) ≤ 1 t + log 2 t tγ 2,λ η = O log 2 t(1 + 2cλ -1/2 ) 2 tγ 2,λ .

Before showing parameter convergence, we need the following lemma which is a generalization of Lemma 10 in Gunasekar et al. (2018a) , but with much simpler proof. Lemma D.1. Fix c < γ 2,λ , for any θ ∈ RR d , we have ||∇L adv (θ)|| 2 ≥ L adv (θ)γ 2,λ .

Proof.

-∇L adv (θ) = 1 n n i=1 exp (-y i x i ) y i x i .

where x i = argmin x i -xi∈∆i(λ) y i (x i ) θ. Then by the definition of γ 2,λ and u 2,λ (48), we have

y i x i , u 2,λ ≥ γ 2,λ

From which we obtain -∇L adv (θ), u 2,λ ≥ L adv (θ)γ 2,λ , the claim follows by Cauchy-Schwarz inequality.

Theorem y i (x i + δ i ) θ ≥ 1, ∀i = 1, . . . , n.

We thus conclude that lim t→∞ θ t ||θ t ||2 = u 2,λ . To summarize, we have shown that for all λ > 0, lim t→∞ θ t ||θ t ||2 = u 2,λ . The ∞ -norm perturbation corresponds to the case when λ → 0, it is natural to conclude that for ∞ perturbation, we have lim t→∞ θ t ||θ t ||2 = u 2,∞ . The discussion for q = 1 follows similar argument, hence we omit the details here.

E ADDITIONAL EXPERIMENTS ON PERTURBATION LEVEL AND SPEED-UP:

We provide additional experiments on the connection of perturbation level c and the speed-up effect of adversarial training for neural networkds. We run GDAT with ∞ -norm perturbation. The setup of the experiments is exactly the same as the setup in Section 4. We will vary the perturbation level c used in GDAT algorithm in {0.1, 0.15, 0.2}.

From Figure 3 we could see that GDAT indeed accelerates convergence of loss and accuracy on clean training samples. Moreoever, the acceleration effect is stronger when we use larger perturbation level, and this relationship is consistent across different width of hidden layer.

Similar speed-up effects on the test loss and test accuracy evaluated on clean test samples are also observed for GDAT. From Figure 4 , we see that the speed-up effects become stronger when we use larger perturbation level, and this relationship is consistent across different width of hidden layer. Traditionally, the benefit of adversarial training is understood as two fold: 1. it improves the robustness of the learning algorithm, i.e., the solution has better loss toward adversarilly perturbed seample; 2. it has better generalization ability. Our experiments demonstrate a third property of adverserial training that is not known in literature before, i.e., adversarial training accelerates convergence. 

:

In conjunction withDropout (Srivastava et al.,

2014) and Batch Normalization(Ioffe and Szegedy, 2015)

O hides logarithmic factor.

Figures and Tables:

j=1 x j y j denotes their Euclidean inner product. For a vector θ ∈ R d , ||θ|| p defined by ||θ|| p p = d j=1 |θ j | p denotes its p-norm for p ∈ [1, ∞), and ||θ|| ∞ = max j∈[d] |θ j |, where [d] = {1, . . . , d}. For any general norm || • ||, we denote its dual norm by ||x|| * = max ||y||≤1 x, y . The sign function is sign(v) = 1 (v≥0) -1 (v<0) . For a linear subspace L ∈ R d , we denote its orthogonal subspace by L ⊥ .

which is a mixture of 2 and p norm. Let || • || * be its dual norm. Then we have that the solution to (9) is the maximum || • || * -norm margin hyperplane.

Figure 1: GDAT of Linear Classifiers.

Figure 2: GDAT of Neural Network on MNIST Dataset.

Figure 3: GDAT with Different Perturbation Level: Clean Training Loss

2 number of iterations. In comparison, the standard clean training by GD needs O n exp -1 number of iterations (Ji and Telgarsky, 2018), which has exponential dependence on precision . Finally, by Theorem 3.1 and Lemma 3.3, we show that the empirical clean risk after T iterations of GDAT is almost exponentially smaller than its counterpart in the standard clean training. Corollary 3.2 (Speed-up of Clean Risk Convergence). Under the same conditions in Theorem 3.2, we have

Table content: <table/>

. Motivated by these results, investigating the implicit bias of GDAT in training deep linear networks worths future investigations.Meanwhile, investigating implicit bias in deep nonlinear networks is a more important and challenging direction: (1) For linear classifiers, adding adversarial perturbations during training can be understood as a form of regularization, which explains the faster convergence in training. Although observed empirically, the potential acceleration of adversarial training is not yet understood in the current literature, to the best of our knowledge. (2) The notion of margin for neural networks still lacks proper definition, which we need to define to facilitate investigations on the effect of adversarial training in promoting robustness. (3) Ultrawide nonlinear networks have been shown to evolve similarly to linear networks using gradient descent(Ghorbani et al., 2019; Lee et al., 2019). We shall further investigate if our results on linear classifiers can be extended to wide nonlinear networks.6 ACKNOWLEDGEMENTSFang is partially supported by NSF DMS-1820702 and NSF DMS-1953196. HINTON, G., DENG, L., YU, D., DAHL, G., MOHAMED, A.-R., JAITLY, N., SENIOR, A.,VAN-HOUCKE, V., NGUYEN, P. and KINGSBURY, B. (2012). Deep neural networks for acoustic modeling in speech recognition. IEEE Signal Processing Magazine 29. HOFFER, E., HUBARA, I. and SOUDRY, D. (2017). Train longer, generalize better: closing the generalization gap in large batch training of neural networks. In Advances in Neural Information Processing Systems. IOFFE, S. and SZEGEDY, C. (2015). Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning. JI, Z. and TELGARSKY, M. (2018). Risk and parameter convergence of logistic regression. arXiv preprint arXiv:1803.07300 . JI, Z. and TELGARSKY, M. (2019). Gradient descent aligns the layers of deep linear networks. In International Conference on Learning Representations. KESKAR, N. S., MUDIGERE, D., NOCEDAL, J., SMELYANSKIY, M. and TANG, P. T. P. (2017). On large-batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations. KRIZHEVSKY, A., SUTSKEVER, I. and HINTON, G. E. (2012). Imagenet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems. PAPERNOT, N., MCDANIEL, P., GOODFELLOW, I., JHA, S., CELIK, Z. B. and SWAMI, A. (2017). Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security. PAPERNOT, N., MCDANIEL, P., WU, X., JHA, S. and SWAMI, A. (2016). Distillation as a defense to adversarial perturbations against deep neural networks. In 2016 IEEE Symposium on Security and Privacy. , C., ZAREMBA, W., SUTSKEVER, I., BRUNA, J., ERHAN, D., GOODFELLOW, I. and FERGUS, R. (2014). Intriguing properties of neural networks. In International Conference on Learning Representations.

Table content: <table><tr><td>WALD, A. (1939). Contributions to the theory of statistical estimation and testing hypotheses. The</td></tr><tr><td>Annals of Mathematical Statistics 10 299-326.</td></tr><tr><td>WILSON, A. C., ROELOFS, R., STERN, M., SREBRO, N. and RECHT, B. (2017). The marginal</td></tr><tr><td>value of adaptive gradient methods in machine learning. In Advances in Neural Information</td></tr><tr><td>Processing Systems.</td></tr><tr><td>XIE, C., WU, Y., VAN DER MAATEN, L., YUILLE, A. and HE, K. (2018). Feature denoising for</td></tr><tr><td>improving adversarial robustness. arXiv preprint arXiv:1812.03411 .</td></tr><tr><td>ZHANG, C., BENGIO, S., HARDT, M., RECHT, B. and VINYALS, O. (2017). Understanding deep</td></tr><tr><td>learning requires rethinking generalization. In International Conference on Learning Representa-</td></tr><tr><td>tions.</td></tr><tr><td>ZHANG, H., YU, Y., JIAO, J., XING, E. P., GHAOUI, L. E. and JORDAN, M. I. (2019). Theoretically</td></tr><tr><td>principled trade-off between robustness and accuracy. In International Conference on Machine</td></tr><tr><td>Learning.</td></tr><tr><td>SINHA, A., NAMKOONG, H. and DUCHI, J. (2018). Certifying some distributional robustness with</td></tr><tr><td>principled adversarial training. In International Conference on Learning Representations.</td></tr></table>

Note that θ t is a conic combination of {z i -ca||θ t || p } i∈[n] , and ∂||θ t || p only depends on the direction of θ t . Hence by normalizing the norm of θ t and using lim t→∞ ||θ t || 2 = ∞, if the limit u ∞ = lim t→∞

Table content: <table><tr><td>same direction as the solution to min θ 1 2 ||θ|| 2 + η(c)||θ|| p , s.t. z i θ ≥ 1, ∀i = 1, . . . n.</td><td>t→∞</td><td>θ t ||θ | |2 is in the (40)</td></tr><tr><td colspan="3">θ t ||θ t ||2 exists, it satisfies the following condition under proper scaling that n</td></tr><tr><td>θ =</td><td/><td/></tr><tr><td>i=1</td><td/><td/></tr></table>

n, which is a convex program with strongly convex objective. By this fact, we conclude that lim t→∞ θ t ||θ t ||2 = u 2,q . To further get the rate of convergence, we use the convergence of adversarial risk in (39), and establish the lower bound on ||θ t || 2 : ||θ t || 2 = Ω (log t). Combining this with (46), the claim follows immediately.D ∞ -NORM PERTURBATIONRecall that the robust SVM against ∞ -norm perturbation parameterized by c is formulated as

Table content: <table><tr><td colspan="2">γ 2,∞ = max θ and its associated max-margin classifier is min i=1,...,n</td><td colspan="2">min ||δi||∞≤c</td><td colspan="2">y i (x i + δ i ) θ ||θ|| 2</td><td>,</td><td>(47)</td></tr><tr><td>u 2,∞ = argmax ||θ||2=1</td><td colspan="2">min i=1,...,n</td><td colspan="2">min ||δi||∞≤c</td><td>y</td></tr></table>

Using the previous recursion we have that for anyθ ∈ R d , ||θ t+1 -θ|| 2 2 = ||θ t -θ|| 2 2 -2η ∇L adv (θ t ), θ tθ + η 2 ||∇L adv (θ t )|| 2 2 ≤ ||θ t -θ|| 2 2 -2η L adv (θ t ) -L adv (θ) + 2η L adv (θ t ) -L adv (θ t+1 ) = ||θ t -θ|| 2 2 -2η L adv (θ t+1

Table content: <table><tr><td/><td/><td>adv (θ t ) 2</td><td>||∇L adv (θ t )|| 2 2</td><td>(51)</td></tr><tr><td>= L adv (θ t ) -</td><td>η 2</td><td>||∇L adv (θ t )|| 2 2 .</td><td/><td>(52)</td></tr></table>

D.2. Under the same setting as in Theorem D.1, we havelim t→∞ θ t ||θ t || 2 = u 2,λ .Proof. Recall that in Theorem D.1 we showed in (51) thatL adv (θ t+1 ) ≤ L adv (θ t ) -η||∇L adv (θ t )|| 2 ≤ exp -ηγ 2,λ ||∇L adv (θ t )|| 2 + (1 + 2c √ λ ) 2 η 2 2 ||∇L adv (θ t )|| 2 2 ,where the last inequality holds by Lemma D.1. Applying the previous inequality recursively from s = 0 to t -1, we haveL adv (θ t ) ≤ exp -ηγ 2,λ ||∇L adv (θ s )|| 2 2 = L adv (θ 0 ) -L adv (θ t ) ≤ 1, which yields L adv (θ t ) ≤ exp -ηγ 2,λ ||∇L adv (θ s )|| 2 + 1 . i (x i + δ i ) θ t = exp -y i x i θ + cH λ (θ t ) i (x i + δ i ) θ t ≥ ηγ 2,λ ||∇L adv (θ s )|| 2 -1log n.Dividing both sides by ||θ|| 2 , and since lim t→∞ L adv (θ t ) = 0, we have limt→∞ ||θ t || 2 = ∞. Hence, i (x i + δ i ) lim t→∞ θ t ||θ t || 2 ≥ γ 2,λ .Hence lim θ t ||θ t || 2 is a solution to (48). Note that the solution to (48) is unique since it is equivalent to

Table content: <table><tr><td colspan="5">In summary, we have</td><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>min δi∈∆i(λ)</td></tr><tr><td/><td/><td/><td colspan="2">min θ∈R d</td><td colspan="2">1 2</td><td>||θ|| 2 2 s.t.</td><td>min δi∈∆i(λ)</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>2 + (1 +</td><td>2c √ λ</td><td>) 2 η 2 L adv (θ t ) 2</td><td>||∇L adv (θ t )|| 2 2</td></tr><tr><td/><td/><td/><td/><td colspan="4">≤ exp -η</td><td>||∇L adv (θ t )|| 2 2 L adv (θ t )</td><td>+ (1 +</td><td>2c √ λ</td><td>) 2 η 2 2</td><td>||∇L adv (θ t )|| 2 2</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>t-1 t=0</td><td>||∇L adv (θ s )|| 2 +</td><td>t-1 s=0</td><td>(1 +</td><td>2c √ λ</td><td>) 2 η 2 2</td><td>||∇L adv (θ s )|| 2 2 .</td></tr><tr><td colspan="5">Now by (51), we have</td><td/><td/></tr><tr><td>t-1 s=0</td><td colspan="2">(1 +</td><td>2c √ λ</td><td colspan="2">) 2 η 2 2</td><td colspan="2">||∇L adv (θ s )|| 2 2 =</td><td>t-1 s=0</td><td>η 2</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>t-1</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>s=0</td></tr><tr><td colspan="8">Next for all i ∈ [n], we have</td></tr><tr><td/><td colspan="7">exp -min δi∈∆i(λ)</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>t-1</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>≤ n exp -ηγ 2,λ</td><td>s=0</td><td>||∇L adv (θ s )|| 2 + 1 ,</td></tr><tr><td colspan="3">which implies</td><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>t-1</td></tr><tr><td/><td/><td/><td colspan="5">min δi∈∆i(λ)</td><td>s=0</td></tr><tr><td colspan="2">lim t→∞</td><td colspan="2">min δi∈∆i(λ)</td><td colspan="4">y i (x i + δ i )</td><td>||θ t || 2 θ t</td><td>≥ lim t→∞</td><td>ηγ 2,λ</td><td>t-1</td></tr></table>

Peer review (iclr2020):
The paper studies the implicit bias of gradient based adversarial training for linear models on separable data with the exponential loss. Both l2 and general lq perturbations are studied. For l2, the authors show that for small enough perturbations, the algorithm converges in direction to the max l2 margin solution, with faster convergence rates compared to standard gradient descent, both for the clean loss and the parameter direction (O(1/sqrt(T)) instead of O(1/log(T))). For lq, convergence to a different max-margin direction is shown, given according to a mixture of the l2 and lp norms, though the parameter convergence is slower. These results are further illustrated by numerical experiments. The topic of the paper is novel and interesting, in particular the finding that adversarial training can lead to benefits in terms of optimization in addition to robustness, as well as the characterization of the inductive bias obtained when using lq perturbations in adversarial training (i.e. a mixture of lp and l2 norms, rather than just lp). Granted, the setting of linear models is a bit limited, but it provides a first step for more realistic models. The paper is also well written, and also has a nice numerical validation of the results. Overall, I am in favor of acceptance. Here are some questions/comments that could be further discussed: * for l2, while the obtained rates for parameter convergence are better in their dependence on T, they depend on a data-dependent quantity alpha in contrast to standard GD, suggesting that the rate could be worse for small alpha: is there a trade-off here? would standard GD be preferable if alpha is small, or could the current rate (7) automatically adapt to such settings? * in Theorem 3.4, how does the choice of c come into play? can you obtain better rates by optimizing it (ideally this should happen when q=2)? Regarding the comment on tending to the lq-norm margin for c -> gamma_q, is this at the cost of poorer convergence? * for lq perturbations, while I agree that the studied algorithm is interesting since that*s what*s used in practice for deep networks, I do wonder if in this specific setting you could get better convergence (and with the right norm lp instead of the mixture) by optimizing using the appropriate geometry, e.g. with mirror descent. * the analyzed algorithm considers optimal perturbations -- do you have a sense of how robust the theory is to errors in the inner optimization? minor comments/typos: * second bullet in *main contributions*: *mixed-norm margin* could be further explained, or at least point to the definition. The terminology is also confusing as it sounds like a matrix mixed-norm * *polyhedral cone ...*: bar{u} should be u? * after Theorem 3.2 *not an issue*: not so clear, this should be discussed further (see comment above) * section 3.2, *defer discussion for 1, infty*: you could provide a flavor of the results for these cases in the main text, given their prominence in practice * figure 1(b): for the direction plot, is it actually u_2? how should this plot be interpreted given that the two curves converge to a different direction?