Implicit Bias of Gradient Descent based Adversarial Training on Separable Data
Authors: Yan Li
Ethan X.Fang
Huan Xu
Tuo Zhao
Venue:  (2020)
Keywords: implicit bias
adversarial training
robustness
gradient descent

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 L2 norm,  the classifier learned by gradient descent based adversarial training converges in direction to the maximum L2 norm margin classifier at the rate of $O(1/\sqrt{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 Lq norm, the resulting classifier converges in direction to a maximum mixed-norm margin classifier, which has a natural interpretation of robustness, as being the maximum L2 norm margin classifier under worst-case bounded Lq norm perturbation to the data.  Our findings provide theoretical backups for adversarial training that it indeed promotes robustness against adversarial perturbation.

Published as a conference paper at ICLR 2020
IMPLICIT BIAS OF GRADIENT DESCENT BASED AD- VERSARIAL TRAINING ON SEPARABLE DATA
Yan Li, Huan Xu, Tuo Zhao
H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA 30318 (yli939, huan.xu, tourzhao] @egeeegatthh.ce edu
Ethan X.Fang
Department of Statistics Pennsylvania State University University Park, PA 16802
xxf13@psu.edd
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 gradi- ent descent based adversarial training by studying its computational properties, specifically on its implicit bias. We take the binary classification task on linearly separable data 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 f2-norm, the classifier learned by gradient descent based adversarial training converges direction to the maximum l2- no-norm margin classifier at the rate of ((I/VT). significantly faster than the rate O (1/ log T) of training with clean data. In addition, when the adversarial perturbation during training has bounded -n-ormm with 2 1, the resulting classifier converges in direction to maximum mixed-norm margin classifier, which has a natural inter- pretation of robustness, as being the maximum Ez fn-mrrm margin classifier under worst-case 6 -norm perturbation to the data. Our findings provide theoretical back- ups for adversarial training that it indeed promotes robustness against adversarial perturbation.
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 ct al. 2012). One salient feature of deep models is its overparameterizatton,, with the number of parameters several orders of magnitude larger than the training sample size. As a consequence of such overparameterizztion, it is likely that the empirical loss function, addition to being non-convex, have substantial amount of global minimizers (Choromanska et al. 2015), while only small subset of global minimizers have the desired generalization properties (Brutzkus et al. (018).
Contrary to the worst-case reasoning above, researchers have observed that simple first-order algo- rithm such as Stochastic Gradient Descent (SGD) | performs surprisingly well in practice, even without any explicit regularization terms in the objective function (Zhang al.) 2017). Inspired by classical computational learning theories, one plausible explanation of such a remarkable phe- nomenon 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.) 20155) and SGD converges to low-capacity solutions with the desired generalization property (Brutzkus al. 2018). Recently, some exciting works have related the implicit bias to specific first-order algorithms (Wilson et al.)
In conjunction with Dropout Srrvastavaa et al. 2014 and Batch Normalization Ioffe and Szegedy 2015

---

Published as a conference paper at ICLR 2020
2017),
stopping time (Hoffer et al. 2017). and optimization geometry (Gunasekar al. 2018a Keskar et al.] 2017). Some practical suggestions based on these findings have also been proposed to further improve the generalization ability of deep networks (Neyshabur et al. 2015a).
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 al., 20155 Gloosavi-Dezfoode
al., 2016; Carlini and Wagner 2017 7,
Athalye et al. [018] et al.] 2018 Papermot et al.] [016]. 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. (2013); Madry et al. (2018) formalize the notion of achieving adversarial robustness (i.e.,
having small adversarial risk) as solving the following minimax optimization problem
min L (0) min ((a))) max E(0,x 6. 8.
(1)
#ER
where A 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
N
min Caav(0) = min BERd
Σ
max
E(0, xi + 6, M1). E,
BER4
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 (approxi- mately) for adversarial perturbations, and then uses the gradient of the loss function evaluated at the perturbed samples to perform gradient descent step the parameter 0. 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 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 f2-norm, i.e., A (8 E n : ||08|2 S c). with proper choice of c, the gradient descent based adversarial training is directionally convergent that lim,- T u2, where u2 is the maximum f2-norm margin hyperplane (i.e., standard SVM) of the training data. In addition, when the perturbation level e is set according to T appropriately, the rate of convergence is O(1/VT) which is exponentially faster than the rate O (1/ log T) when we use standard clean training, i.c., 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.
g²
2 hides logarithmic factor.
2

---

Published as a conference paper at ICLR 2020
Our second part of result shows that adversarial training adapts the implicit bias of gradient descent for different adversarial perturbation geometty. Specifically, when the perturbation is bounded by b norm for 2 1, i..., A {8 E R 1661, S c), with proper choice of c, the gradient 0² descent based adversarial training is directionally convergent that lim ||04||2 U224 where U2.9 is the maximum mixed-norm margin hyperplane of the training data. We further reveal natural interpretation of robustness that we obtain the maximum fn-norm margin classifier under worst-case l e--norm perturbation.
j-n1 uJy; denotes their Euclidean inner product. For vector 0 E RR ||0|p defined by 101 Σド= 0,1² denotes its p-norm for E [1, oo), and ||0| ma 00)] where [d] (1,.... ..... d}. For any general norm || |1. we denote its dual norm by ||=||| = | (xr v). The sign function is sign(u) = L (v20) (v<o). For a linear subspace
Notations. For two vectors y E Rd (ar, v) = >
L E Rd we denote its orthogonal subspace by L+.
2 BACKGROUND
We consider a binary classification problem using a dataset S = b.) C ( +1}. We aim to learn a linear decision boundary [(x) (0, æ) and its associated classifier 7(x) = sign (f))),
by solving the empirical risk minimization problem:
min (): BER
min 6ER4
{(yar, 0), where E(-) is some loss function.
In what follows, we suppress the explicit presentation of S when the context 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 ū such that min.e x]] ye > 0. Under this assumption, one notable feature of problem (3) is that there is no finite minimizer, and C()) + 0 only if ||0||2 for any u E C, we have lim L(au)
along certain directions. In fact, there is a polyhedral cone C, such that
Several recent results have studied the implicit bias of gradient descent algorithm on separable dataset. Soudry et al. (2018) study the implicit bias of the gradient descent algorithm (GD) on (3) and show that lim [00 2| oc, while O' converges in direction to the maximum fn-nrrm margin classifier (i.e., the standard SVM). Di and Telgarsky| (2018) further study the convergence of risk and parameter without separability condition. (Ji and Telgarsky 2019) and (Gunasekar al.. 2018b) study the implicit bias for training deep linear network and linear convolutional networks, respectively. Gunasekar et al. 2a) also analyze the implicit bias of steepest descent in general norm ||- 11, and show that ( converges in direction to the maximum || ||--norm margin hyperplane.
Throughout this paper, assume the perturbation set is 6,- norm ball with radius c, i.e., A (ō Rd 1|001, < c). Under the general framework of adversarial training in 2 we aim minimize the empirical adversarial risk
min Ladv min PER
max exp (-y:(z; 0.) TO). S.EA
(4)
DER"
1=1
Note that, given any 0, the inner maximization problem in 4 admits a closed form solution. Then the gradient descent based adversarial training (GDAT) algorithm runs iteratively that 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 5 cy, where 8 argmiin::jajl,, 51 (8, 8*). Then, letting each sample's perturbed counterpart be (I) vr = (z, + 5f v.). we take gradient of the loss function evaluated at the perturbed samples and perform gradient descent step, i.e., g++1 ge Vo (#': { yr) )>)))))) ()), where 17 > 0 is some prespecified stepsize. We present the outline of GDAT in Algorithm
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.
3

---

Published as a conference paper at ICLR 2020
Let start with some definitions. Con- sider a dataset S = [T,, y- C R x
Algorithm Gradient Descent based Adversarial Train-
1/9 {-1,+1}. Given p,
such that 1/p
ing (GDAT) with nnom Perturbation
the -n-norm margin of Hg on S is
Number of iterations T, perturbation level c, stepsizes {1 t= samples { yr Miler.
Input:
defined as 7/ (0) = g|] U:2: 0/| Note that for 2; E R 0 x / mea- sures the b distance between x; and the hyperplane Ha fxr E R ATx = 0}. Since yi {(11, when Hg correctly classifies all samples, 77(() measures the minimal b distance between the samples in S and Hg. Given that (0) is scale- invariant with respect to 0. without loss of generality, we restrict |00|p 1. We also identify the hyperplane Hg by its normal vector 0.
Initialize: 0 <
for 0, ................................ 1o
for i 1,... n do
Compute of cyi Argginnj11l,s. (ō, (")
Let (3), vi) t (z, 8% yı).
end for
(++1 t- 0c z Ei= exp (-ya 00) (-y,
end for
Definition 3.1. For P, 0 with 1/p + 1/q 1. the maximum noorr margin hyperplane us of = [E),, C IRd x {-1,+1} and its associated E -norm margin are defined as
dl argmax min yı 0, 7/ max min y.
(5)
|001, sE[n]
|10||=11
We denote SV(S) as the support vectors Sf i.e. SV(S) = (rgmmn (ug yz).
By the separability assumption, Ug is an optimal hyperplane that correctly classifies all samples with the maximal margin 7 > O. 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 O satisfy 1/p + 1/q
Given a nonnegative scalar c. where 4 has infimum 0 but does not admit a finite 0 o 74 = ma minje[n] y:u; 6. problem
minimizer. When Ng. problem (4) has a unique finite minimizer O(c), and is equivalent to the standard clean training with explicit f--norm regularization. That is, there exists X(e) >> O such that
0(c) = argmax
Σ exp(( exp(-yya +(c)100111
BER TI
It is not difficult that for e < "/g. any perturbed dataset 5 { ((),): ) with ||r;- & for all i, is still linearly separable, which directly follows from the definition of % above. On the other hand, when > Tg- by the definition of %/. there exists some perturbed dataset S {(T,, 3 with ||a; Talla < è for all i, such that S is no longer linearly separable.
3.1 ADVERSARIAL PERTURBATION WITH BOUNDED 22-NORM
In this subsection, analyze both the empirical adversarial risk convergence and the parameter convergence of the case when the perturbation set in is an fz-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 its non-smoothness, in the sense that (0) (0) is not differentiable the origin, and its Hessian V & (0) 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 0f and the maximum norm margin hyperplane u2 This gives lower bound on ||0||2
Lemma 3.1. Take L-V u2) (0) c) ffror any 0 Rdd
{6 E Rdd ||8||2 S c} in problem Given e < 72, we have that
We highlight that despite its simple proof, Lemma 3.1 and its generalization to -e-ertuurbation is a crucial step for analyzing both adversarial risk and implicit bias. In addition, techniques here can also be adapted to simplify the proof of Lemma 10 in (Gunasekar et al. (018a), which, in comparison, 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 adversarial examples at the first iteration of
4

---

Published as a conference paper at ICLR 2020
GDAT. From Lemma 3.1 we have the following simple corollary showing that our whole solution path {0 (0=) is bounded away from the origin.
Corollary 3.1. Let 0 = 0 in Algorithm with 2, we have: ||0'|/ 2 12 for all 1 2 1.
By Corollary 3.1 we bypass the non-differentiabbiity issue at the origin and also control the Hessian Ledv (0) throughout the entire training process. Similar to (Ji and Telgarsky 2018), in the next theorem, we show that the loss (0), although not uniformly smooth, is locally Ladv (0) -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 ||2/l22 S for all i = 1...n n. For GDAT (Alg.
7 with f--norm perturbation, 2a/e
i.e. A = {8 E Rd ||0112 & c}. we set < 72. n7 and n/¹ 77 S min (140))>920(11 1} for
t 2 I, then we have
(n)(22 ( log*1
mAx exp (-vi(T; + 6z) &EE
o
(6)
-c²
In comparison with the standard clean training using GD (Ji and Telgarsky 2018), this theorem states that we pay an extra (12 - c) -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 Corollary 3.2 we prove that the convergence of standard risk in GDAT is significantly faster than its counterpart the standard clean training using GD.
Parameter Convergence. We then show that if we set the perturbation level 72 in the GDAT algorithm, GDAT with fo-norm perturbation possesses the same implicit bias as the standard clean Intuitively, GDAT with 22-norm perturbation
training using GD, i.e., we have lim4,+00 T0 searches for decision hyperplane that is robust to l--norm perturbation. Since the learned decision hyperplane in the standard clean using GD converges to U2, which is already the most robust decision hyperplane against é- f--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 U2 their rates directional convergence are significantly different as shown later. Specifically, letting the perturbation level 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 0² onto the orthogonal subspace of (pan(u2) is bounded.
(x)(s))))) (S. yz), where we assume SV(S) spans Rdd Let 01 be the projection of vector 0 onto span (2)) " Then there exists constant K that only depends on (SS) and log n, such that ||0 ll2 & K for any t 2 0 in the GDAA algorithm.
Lemma 3.2. Define a(S) = min [E| 2= 2=11:
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 ||0'] 2l 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 Then all t 2 O, we have
3.1 and let a = a(S) defined in Lemma 3.2
tn1(2 c)2 11+1/a log" /(12 - c).
110'1/ 2 log
Lemma 3.3 provides the key insight to establish the acceleration of directional convergence. Specifi- cally, it allows us to set depending on the total number iterations T, so that ||02= 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 up of Parameter Convergence). Under same conditions in Theorem and let aS) and K be defined in Lemma 3.2 In GDAT with f--norm perturbation, let and total
5

---

Published as a conference paper at ICLR 2020
number of iterations T satisfy ?/2
c= (1"ll//n ToR 1/2
1/2
and define 8"
g² 10-
We have
n (1(t1/a)/22g K log
1- (0" u2)
VIVT
One might argue that the polynomial dependence on sample size n in ( 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 |10" - u2lle S for a given precision > O. Specifically, given e 0, achieve |1Ø" u2 # GDAT needs Ö (1(++1/a) number of iterations. In comparison, the standard clean training by GD needs exx (c (c-1)) number of iterations (ii and Telgarsky 2018), which has exponential dependence on precision c.
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 counterpart the standard clean training.
Corollary 3.2 (Speed-up of Clean Risk Convergence). Under the same conditions in Theorem 3.2 we have
C(0") O ( (ex ((xxT(((////))) (-uvT/logT))
where μi is constant dependent 1), n.
Note that the empirical clean risk decreases at the rate of (exp(-VT)) up to logarithmic factor in the exponent. In comparison, using standard clean training with GD, we only have L(77) = 0 (1/T)
(Soudry al. 2018).
3.2
ADVERSARIAL PERTURBATION WITH BOUNDED E2-NORM
In this subsection, we generalize our results to the case where the perturbation set is some bounded fy-norm ball. To facilitate our discussion, we first define robust version of SVM.
Definition 3.2. For given separable dataset S with noor margin "ig and e Ni. letting l/p+ + 1/q = L, the robust SVM against nn-rrrm perturbation parameterized by c is
min BER
10 _
S.t. ye 0 c||01|p + 1,...,
Remark 3.1 (Maximum Mixed-norm Margin). Note that problem (8 is equivalent to solving for a maximun mixed-norm margin hyperplane. Specifically, by the KKT condition of there exists m(c) > O, such that (8) is equivalent to the following problem:
min ||0||2 + n>())100lpp s.t. yos 0 2,,, Vi 1,..,,,,
BERd
Now define -1 1|2 n(()lll 1pp- it is clear that || || defines norm which is mixture of lg and Ep norm. Let 11. be its dual norm. Then we have that the solution to (9) is the maximum
|| Il=-norm margin hyperplane.
Note that the constraint in (8) is equivalent to 1l Mi( + T;) Vi =1 1, n. By a
simple scaling argument, in the following lemma, we see the robust nature of g
Lemma 3.4. Under the same notations in Definition 3 3.2 problem 8 is equivalent to:
(c) max min
min (2, + 8.) 0.
(10)
11,,11,
We denote the (unique) solution to problem TT presentation of e when the context clear.
(c). In what follows, we surpress explicit
The equivalent formulation (10) provides clear interpretation the robustness of (10). In particular, the robust SVM against E, -norm perturbation parameterized by e in fact the SVM problem on the the dataset S(c, q). which is generated from S by placing f--norm ball with radius around each samples, i.e., S(c, q) = {2, y) 3i E [n]. s.t., | xı lp & c, J.). In other words, U2.g is the l, norm perturbation bounded by
maximum &g norm margin classifier under worst
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 &, perturbation for (1). Our analysis

---

Published as a conference paper at ICLR 2020
for q {1, oo} is based on approximation argument. For ease of presentation, only discuss when q E (1) in the main text, and defer the discussion for E {1) in Appendix D
Adversarial Risk Convergence. Our analysis is similar to the analysis for GDAT with l perturba- tion, where we use similar techniques to address issues such as non-differentiabiiityy at the origin and Hessian explosion of Ladv (0) around the origin.
Theorem 3.3. Suppose ||æ:||2 I for = ,,..., n, and let + = 1. In the GDAT with no-nor
perturbation, setting < "ig and letting Mp= [11 + eva)² + c(p-1) 2 exp (-22 cv cva)
72.9
set no 1 and nf 1 S min M fo t 2 1. We have that
log²t tr
max exp (-vi(x; + +.) TO) - EE
(11)
We point out here that (6) is a special case of (TT). In particular, by the definition of (2.g(c), we have that (2,2(c) 7/2 which recovers bound 66) from [T].
Parameter Convergence. We show that if we set C < <g in the GDAT algorithm with stepsizes specified in Theorem 3.3 with bg perturbation, the algorithm still possesses implicit bias property, i.., 0f still has directional convergence, and the limiting direction depends on the perturbation set A. Theorem 3.4 (Implicit Bias of GDAT with b norm Perturbation). Under the same conditions in Theorem 3.3 define 8¹
g² | then we have:
1 (0' u2.0 -
log n log /
and and Lemma 3.4 we conclude that GDAT with fy-norm perturbation indeed promotes robustness against by perturbation. Using GDAT with 4--norm perturbation will result in a classifier which is the maximum fg- fo-mo margin classifier under worst case normo perturbations to the samples bounded by c. The learned classifier will have 4 -nnrm margin least c. As we increase perturbation level to 7q. the learned classifier will converge to maximum fg-norm margin classifier.
Combining Theorem 3.4
NUMERICAL EXPERIMENT
In this section, we first conduct numerical experiments on linear classifiers findings. We further empirically extend our method neural networks, where our numerical results demonstrate that our theoretical results can be potentially generalized.
to backup our theoretical
Linear Classifiers. We investigate the empirical performance the GDAT algorithm on linear classi- fiers, 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 & norm margin classifier u2 = (0, 1).
Considering 4 norm perturbations, we first run standard clean training with GD, and GDAT with f2-norm perturbation (c 0.95%)2). for 2.5 x 10 number of iterations. In both GD and GDAT we take constant stepsizes, with 17 1 and 7 = 0.1, respectively. By Figure 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 8 to U2 We also compare the norm growth ||@ [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 -nomm perturbation = 0.5). By Lemma 3.4 we have that t,2,00 (0, 1). Note that the Hausdorff distance between fg-norm ball and l -orm ball distance goes to zero as g goes to infinity. Thus, we have that (10) for g 1000 is close approximation of (10) for oc. We run two versions of GDAT, where one uses E, fn-oorm perturbation with = 1000, and the other uses -nom perturbation. We run both algorithms with stepsize v = 0.1 for 5.0 x 10 number of iterations, and we present the results in Figure [[b.. We find that the two training methods behave similarly. In addition, the empirical directional convergence rates of 0 just differ slightly.
Neural Networks. It is seen above that GDAT with norm perturbations converges significantly faster than GD for linear classifiers in adversarial training. A natural question is whether this is still the
7

---

Published as a conference paper at ICLR 2020
2.0
Clean Traiing
124
ty Pertimbation Perturbation
1.000 MEVITTANTT A0re
2g
Lo0n: Llatt dake
10-0
05
144
24
0.0
0.0
0.5
1.4
1.5
2.4
10
12
8:30
1:
110
30
Iterations
Therations
Torrations
165
Tterations
165
(8). Cleam Training v.s. GDAT (és perturbation)
(b). GDAT (4x, perturbation) v.s. GDAT (6, perturbation)
Figure I: GDAT of Linear Classifiers.
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 x 64, 128 x 128, 256 x 256}.
One major difference from the case of linear classifiers is that we cannot solve the inner maximization problem of (2) exactly it does not admits 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 f--norm perturbations (c 2.8), and the other uses foo- norm perturbations (c = 0.1). For standard clean training and the outer minimization problem in we use the stochastic gradient descent algorithm with batch size 128 and constant stepsize 10 5
We compare the loss and classification accuracy, which samples, of standard clean training and GDAT. By Figure 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 this case, larger perturbation level should be used. We conduct additional experiments with various perturbation level in Appendix E to empirically verify our argument.
evaluated using the clean training
Cleen Training
Pertuzhation Perturbation
Looe: clean data
0.8
0.6
100
200
100
400
102
250 Lterations
420
103
250
420
100
202
300
402
lserations
Iterations
Iterations
302%
905
80%
Accurargi
628
3250
100
300
400
300
400
100
400
100
200
350
40%
Ietrations
Iseratioons
(a). Width 64 x 64
(b). Width 128 x 128
(c). Width
256
256
(d). Width
512 x 512
Figure 2: GDAT of Neural Network on MNIST Dataset.
8

---

Published as a conference paper at ICLR 2020
5 DISCUSSIONS
We investigate the implicit bias of GDAT for linear classifier. There are several plausible natural extensions. For example, we can represent linear classifier using deep linear network, which 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 (Gnaaeeaar et al. 2018b), 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 chal- lenging direction: (1) For linear classifiers. adding adversarial perturbations during training 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 define to facilitate investigations on the effect of adversarial training in promoting robustness. (3) Ultrawide nonlinear networks have been shown to evolve similarly linear networks using gradient descent (Ghorbani al., 2019 Lee al. 2019). We shall further investigate if our results on linear classifiers can be extended to wide nonlinear networks.
6
ACKNOWLEDGEMENTS
Fang is partially supported by NSF DMS- 1820702 and NSF DMS-19531 1953196.
REFERENCES
ATHALYE, A., CARLINI, N. and WAGNER, D. (2018). Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In International Conference on Machine Learning.
BEN-TAL, A., EL GHAOUT, L. and NEMIROVSKI, A. (2009). Robust Optimization, vol. 28. Princeton University Press.
BRUTZKUS, A., GLOBERSON, A., MALACH, E. and SHALEY-SHWARTH S. (2018). SGD learns over-paramettrrized networks that provably generalize on linearly separable data. International Conference on Leurning Representations.
CARLINI, N. and WAGNER, D. (2016). Defensive distillation is not robust to adversarial examples. arXiv preprint arXiv: /607.0671...11..
CARLINI, N. and WAGNER, D. (2017). Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy.
CHOROMANSKA, A., HENAFF, M., MATHIEU, M., AROUS, G. B. and LECUN, Y. (2015). The loss surfaces of multilayer networks. In Artificial Intelligence and Statistics.
FEIGE, U., MANSOUR, Y. and SCHAPIRE, R. (2015). Learning and inference in the presence of corrupted inputs. In Conference on Learning Theory.
GHORBANI, B., MEI, S., MISIAKIEWICZ, T. and MONTANARI, A. (2019). Lincarized two-layers neural networks high dimension. arXiv preprint arXiv: 1904. 12191.
GOODFELLOW, I., SUILENS, and SZEGEDY, C. (2015). Explaining and harnessing adversarial examples. In International Conference Learning Representations.
GUNASEKAR, S., LEE, J., SOUDRY, D. and SREBRO, N. (2018a). Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning.
GUNASEKAR, S., LFF., J. D., SOUDRY, D. and SREBRO, N. (2018b). Implicit bias of gradient descent on linear convolutional networks. In Advances Neural Information Processing Systems.
HE, W., WEI, J., CHEN, X., CARLINI, N. and SONG, D. (2017). Adversarial example defense: Ensembles of weak defenses strong. In 1thh USENIX Workshop Offensive Technologies.

---

Published as a conference paper at ICLR 2020
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, 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.
JOFFE, S. and SZEGEDY, C. (2015). Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning.
J1, Z. and TELGARSKY, M. (2018). Risk and parameter convergence of logistic regression. arXiv preprint arXiv:1803.07300
J1, 7. and TELGARSKY, M. (2019). Gradient descent aligns the layers of deep linear networks. In International Conference Learning Reprexentations.
KESKAR, N. S., MUDIGERE, D., NOCEDAL, J., SMELYANSKIY, M. and TANG, P. T. P. (2017). On latge-batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations.
KRIZHEVSKY, A., SUTSKEVER, and HINTON, G. E. (2012). Imagenet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems.
LEE, J., XIAO, L., SCHOENHOLZ, S. S., BAHRI, Y., (2019). Wide neural networks of any depth evolve as linear models under gradient descent. arXiv preprint
J. and PENNINGTON, J.
MADRY, A., MAKELOV, A., SCHMIDT, L., TSIPRAS, D. and VLADU, A. (2018). Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations.
MOOsAVI-DEZFOOLL, S.-M., FAWZI, A. and FROSSARD, (2016). Deepfool: a simple and accurate method to fool deep neural networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.
NEYSHABUR, B., SALAKHUTDINOV, R. R. and SREBRO, N. (2015a). Path-SGD: Path-normalized optimization in deep neural networks. In Advances in Neural Information Processing Systems.
NEYSHABUR, B., TOMIOKA, R. and SREBRO, N. (2015b). In search of the real inductive bias: On the role of implicit regularization deep learning. In International Conference on Learning Representations.
NEYSHABUR, B., TOMIOKA, and SREBRO, N. (2015c). Norm-bases capacity control in neural networks. In Conference on Learning Theory.
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 Computer and Communications Security.
PAPERNOT, N., McDANIEL, P., WU, X., JhA, S. and SWAMI, A. (2016). Distillation defense to adversarial perturbations against deep neural networks. In 2016 IEEE Symposium on Security and Privacy.
SINHA, A., NAMKOONG, H. and DUCHI, (2018), Certifying some distributional robustness with principled adversarial training. In International Conference on Learning Representations.
SOUDRY, D., HOFFER, E., NACSON, M. S., GUNASEKAR, S. and SREBRO, N. (2018). The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research 19 2822-2878.
SRIVASTAVA, N.. HINTON, G., KRIZHEVSKY, A., SUTSKEVER, I. and SALAKHUTDINOV, R. (2014). Dropout: a simple way to prevent neural networks from overfitting. The Journal of Machine Learning Research 15 1959-1958.
10

---

Published as a conference paper at ICLR 2020
SZEGEDY, 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.
WALD, A. (1939). Contributions to the theory of statistical estimation and testing hypotheses. The Annals of Mathematical Statistics 10 299-326.
WILSON, A. C., ROELOFS, R., STERN, M., SREBRO, N. and RECHT, B. (2017). The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems.
XIE, C., WU, Y., VAN DER MAATEN, L., YUILLE, A. and HE, K. (2018). Feature denoising for improving adversarial robustness. arXiv preprint 1rXiv:1812.0344
ZHANG, C., BENGIO, S., HARDT, M., RECHT, B. and VINYALS, O. (2017). Understanding deep learning requires rethinking generalization. In International Conference on Learning Representa- tions.
ZHANG. H., YU, JIAO, J., XING, E. P., GIIAOU,, L. E. and JORDAN, M. I. (2019). Theoretically principled trade-off between robustness and accuracy. International Conference on Machine Learning.
A PROOF OF PROPOSITION 3.1
Proof. Suppose < To. Letting 0₂ - Orty for a > O, we have
Ladv (0.)
exp (-yir,
T 0a - cl10allp)
1=1
Σ
exp (-ayeet un + cco)
i=1
Σ
exp (-00gg + cox)
1=1
Letting - oc, we obtain lima-+o (0a) = 0. which implies infoers Ladv (0) = 0. Note that [()) does not admit any finite minimizer since (adv > O for any E Rdd
If > 7q. by the definition of maximum f--norm margin, for any 0 Rd, there exists (yi, 2:) S for some [n] such that y 0 & 7y]10]|p. Hence, (0) > exp (n- (c 11)) Then is easy to see that Cadv(8) (#) has bounded sublevel set and hence a finite minimizer Since Ladv (0) is convex, we examine its first-order KKT condition, given by
3 Ø cl001p) ( (-y;z, + cāl 0110)p))
exp
(12)
72
Consider the regularized problem with regularization parameter yy:
Σ exp y-, 0) + 1/|10ppp-
min BER4
Its first-order KKT condition is.
1
exp (- yau, N.TTT 8) (-y,2,, m0110111 0.
(13)
Looking at 12 and together, by taking 1) Σラ= exp (-via Sv Ø cl011p) have that the solution to the adversarial training problem 0 is also the solution to the regularized problem.
To facilitate our later discussions, we point out that by the conjugacy of lp -o-ormm and norm. has the following equivalent form that
min Ladv min BER
exp |,, 0 + <|1011p)
(14)
6E
1=1
In fact, verify that the GDAT algorithm equivalent gradient descent algorithm (14

---

Published as a conference paper at ICLR 2020
B PROOFS FOR SECTION 3.1
Proof of Lemma 3.7 Recall we have Ladv (0) = n Ei=1 max (-Bi(2; + +,)) For
each sample (3i4, vi)
S, given classifier 0, the worse case perturbation is 5;
jrgmax|jlllgee exp (-y6 Vi Va + 5) T) argmin v:d" No 0. The corresponding loss is Ladv (0)
1 D exp - (z;; + T.)T
Since for a fixed 6, the function exp
(a, + T0) is convex in 8, hence the gradient of Ladv (0)
Ladv (0) Σ exp (-yi(1; + T0) uo + ō.).
i=1
Then from the definition of u2
we have
(- V LLadd (0), u2)
Σ exp
Vela + T) ( (ui(os + oo),
(15)
(-ui(z; + T ((urz U2) -c)
exp
(16)
im
exp (-u((s + T.) 0) (72 -c = Cadv(0)( - c).
(17)
where in the second inequality holds since |1ō:1|2 < and |22122 = 1.
Proof of Corollary C.I Since (0) is not differentiable 60 O, subgradient (note that
Lad (0) is convex) at O. Specifically, we take VLav = Em= 2, E aLadv (89). Then we have (0', u2)
1h E, (zz, u2) 2 12. where the last inequality uses the definition 72.
By Lemma 3.1 we have (0', u2) 2 n7 7872 for all 2 1, which also implics (v, u2) 2 77 and hence ||0* 2 17 for v E [0t g++1].
Proof of Theorem 3.7 For simplicity, we let 2; = y where we have ||z:||2 S as we assume | $ 1. We have Ladv (0)
A
exp 2- + cc100122
(-24 +
'10112)
i=1
V L
1
Σ
n
exp (-2] 8 + +c10011)
(-2; +
0
(-+x
+
0
110112
110122
n
00
(-2, T 0 cl10112)
[10|]
/110
exp
100112
cz,
cxp ( (- T 0 + c110112)
2,2
+ 2000TT /110112 + cI/1101la c00 /
|10112
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, 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 @C-1 = 0t r Ladv (0'), we have
Ludv Cadv(8'+) (8*+1) < Ladv (0') n Cady ( )12 + (17'l/V Ladv (0* 11)2
max ((H())) (18) wE(0 0E(0",0t+]]
where X(H(U) (E)))aax max denotes the largest eigenvalue of H(v), where
Ho)) = Σ exx (-2,uv + c||u(12)
2े - c2, ||l//
+ dvv /|10||2 + cI/loo112 - cvv
/||011
7 iml
To upper bound Hv), we need a lower bound on ||0|]. which is readily given by Corollary C.1 That is, |//||2 2 v/ 7
12

---

Published as a conference paper at ICLR 2020
We now analyze 18 for t 2 1, where we show that (0') is locally smooth with parameter
proportional to Ladv (8'), and with proper stepsize, the risk is monotonely decreasing. Note that
2i2/ S I, -20 2, | S 2cI, 2v07 /ll=ll S c.1. Now since ||u*|12 2 72 we have cl c//||o||2 -
cvu /1|u113 - 72
2c
I. Plugging them in, we have
H(v) - - n
Σ exp (-z + d|lullz) (I (1+2c c² + 11/21/
( + 1+20++ +²+
2c
= (u)
I,
n70z2/
and (8)
reduces to Ladv (gl+1)
Sand (6+) - 1/ V/V (0')
+ (n'1lV (oVVad0('")) (8' 11)
2c
(19)
(1 + c)² + r2
max { Ladv fadv
2
Suppose Ladv > fadv (odrr(0'), and let M =
(1 + c)²
+
2c
We have
17"
(v7') V LL (0)))
(oav(O S Cadv(0)) 11'1 (0))) +
M Cadv (0++1),
2
which implies
Ladv (0)+1)= S (1-Mrr)² I1V Ladd (0') (00)11
M 2
(Ladv( La (0
(20)
Meanwhile, if we choose n/' satisfying
2c S
1/' M = 1/' Luav (1+ (1+ c)2² + ,70722
(21)
then we have the right hand side of (20) is upper bounded by Ladv (0'), and we have
(a (1 (ny')
LaV (0')1
(Cadv((') 7''11V Lad (0') Land (aad
which is clearly contradiction. Hence, if ny satisfies (11), by (9) we have
Ladv < LLnv - 1 Ladv (0))1 + (T/'l Lady (T)))
2c
(1+c)²²
(1 + c)² +
Laad
2
17022
xtc || Cadv (1))
Ladv (0')
(22)
2
where the last inequality holds by the choice of 1/" in 21
Note that if 21) holds for
for 17' 77. by induction it is easy see that with constant
stepsize Tf = for L 2 1, (1)
holds for all 2 1. Hence for t 2 1, we choose stepsize such
that n/Cadv (0') (1 c)² + 2c
< 1. Note that (adv(0') = 1
n Em exp (-z, T=TT'' 0' + cc10'112) s
exp ((1 + ))n since |011| S n7. Then we only require
1702
S exp (- + c)n²)
(1+ c) + 2c
(1 (1 c)
exp (- + c)n
()+ 2c
12/e
(1 + 3) +
where in the last inequality we take 1/0 = and use basic inequality exp(-x)r S -1 for x 2 1. In
7a/e summary, we choose 17" = and n/ 17 = min (140)rat204440 1) for t 2 1, then by previous
argument, we have 22 holds for all 2 1.
Now we are ready to apply the standard smoothness- based analysis of gradient descent using 22).
take any 8 Rd we have
| 011 = ||0t
0| 2n/ (V (0'), 0r 0) + (17*) (0')
5 |10e
0 2n' (Lady - Ludv (0)) +
S ||@e
0
2n' (f') Ladv (0)) + 2n (Gaav( Ladv (0*+1))
|10
2 2n'
(Lad (0++1) Ladv (0))
13

---

Published as a conference paper at ICLR 2020
where the first inequality holds by the convexity of Ladv(f), and the second inequality holds by 22
Now sum up the above inequality from $ = 1 to t - 1. By rf' = n S = =nf and Ladv (0
Ladv (6*), we have
1
(0)v Ladv (0) -
10_
(11012+ + 110
2tn
tn
Now since 0 is arbitrary, letting lox(()) -2-C
U2, we have
log²1 t
11013 + 110"11 v
(72 c)² +1 cc²
and
Ladv (0)
1 n
Σ
exp -2 U2
logt t
+c. log
$ 1 7
n2
7/2 - c
7/2 - c
which yields
( log"t
- c)2 + (1 +1+ =0 ( log²t t
Ladv S
(12 (12-
[t7(12 c)3
Proof of Lemma 3.2 For simplicity, we let 2; = yeu, and (0) = exp (-2 + cc(112)) Define
min |||| (éspanta)))))) iEVV(S)
max (E, 2i)
where SV(S) denotes the set of support vectors. It has been shown in Ji and Telgarsky (2019) (Lemma
2.) that > 0 with probability if the data is sampled from absolutely continuous distribution.
We have
(V'a 01)
1
Σ
n
exp (-z 0² + +cl00112)
(-z,
H
01
1100112 1
n
1
1 Σ
(1(0') ( 0e
1,(0)) (-21,"))
01
"110112"
n1
1=1
4,(0') 01
IV
e)(0') (-2), + Σ
1,(09) (-21, (-2)))=)))))))))))))))))))))))))
(23)
n
(2 )20ins
where z/J E S is arbitrary, by definition of a: (~2).09) 2 all09 1|2.
We bound the first term as
( (- 01)
exp (-(x)) 00 + +c|10112) (12) al169 ll2
= exp (-(=/) 0- (z/) 0% + 11) al1011la ll2
2 exp (- (0', )242)) exp (all0' l12) all0' ll2 exp (d 11))
where the second inequality uses (2/, u2) 2 72-
On the other hand, we can bound the second term in 23 as
Σ
(((0)) (-2, 01)
Σ
exp (-2, 0¹ + 111101112 (-zi, 09)
(z..0) (..0))22.. )20.i3j
(z.00) )20,0z5
1
Σ
exp (-,,] 0z, xT + +c|10%l12) (-zz, 01)
(..01)20;44)
2 exp
(- 100 (2nn exp(cl10111 (12) exp((22T00) ( 2,, 01)
(- (0', ((enn 2xp(c|00112] ||] )
2 exp
14

---

Published as a conference paper at ICLR 2020
where in the last inequality holds since (8", u2) 2 O, (2s, Ouna) 2, (ur (*) u2 2 72 (f',, u2) and
-x -xxex((-x)) 2 1 for 2 O.
Plugging the two bounds above into (3 we have
1
LVeadv (0'), 2 exp (- (0', (2222) exp(cl(0'1l))
exp (a1101 (0110111)))0000111111
which is non-negative when |10 ll2 2 K" 1+logn a
Supposing ||0 l2 K" by gradient descent update, we have,
110 - 11 - ||0 112 2n' <VLaav (0"C) 01) + (11)3
- 110 11 + Lav
I ||0 113 + 2 (Cdv((')) - Ladv
(24)
where the last inequality uses
22
Now let to satisfy
112 < K' and 1022-11222 2 K". Define t = min 2 to ||0 1l2 < K'}.
when ||0] l|2 2 K" for all 2 to we define 1 oc. That for any E (fa....,h) 1}. we have
||01 2 2 K' then for any such that to I < 41, summing (24) up from to to yields:
|10% 112 - 1011112 + 2 (Cadv(8"o) - (f))
|101 + exp(1 + cc)
< 11 + 18,
where use (0t) < Ladv (0))
I exp(1 1 + c) and < 1. This inequality shows that for
H E {ofo..... - (0: 111111
212
2 K').
||0 ll2 S ||0 18.
Then, we only need to bound |10'01 (0: |00 1a 2 K'). We have
la to conclude the proof, where to is the first time le enters
n
800-1
0¹ g + 17 1o- P
-
4 [2, - '10 1122
n
where (-) denotes the projection onto span (22)
Note that to is the first time Øf (re)-enters the
region {#: : [01112 1/2 2 ) and thus ||0---1
12
K'. We have
||0 2l I K'
+ 17 1
(1 + c) S K' K1+cc
where the last inequality we use < I 1.
In summary, we have shown that for any such that ||0| |la 2 K', we have 110 l12 S K" + 20, and
we conclude that |10 |12 K' + 20 K for all t 2 0. Note that K only depends aSS) and sample size n.
Proof of Lemma 3.3
To obtain lower bound |10" first denote 0f 0², + 01, where 0f denotes the projection of onto span (2)), and 0' denotes the projection of f onto span(u2) We have
n Σ
I
exp(-=
TTo 2, =TT0))= fn(11 - c)2 exp(e exp(-cil0*112).
log"! t
Let us assume that |10 is bounded that exp(I10* [I) < M, which will be verified immediately.
Choosing an arbitrary support vector 24 we have < (2,, 0%)) = (z.. u2) (0', uz) = 72 (0', u2) = 72 10 la S 721 (0/12,, hence the previous inequality becomes: n logg
exp(-72|10 <
exp(- exp(-c]0'||aM
br)(72 c)²
which is equivalent to
ttnl2 c)2)
110'11 log
/172 cc..
(25)
n. log" t
Now we only need to show that ||011| < M for all t for some M. Since we have shown in Lemma
3.2
that ||0|||2 < K, choose M ex < exp (20+logn) becomes
(n ). and the lower bound 25
tn c)2
|10' 2| 2 log
/(12 - c),
(26)
nI+1/a log
which concludes our proof.
n
15

---

Published as a conference paper at ICLR 2020
Proof of Theorem 3.2
We denote 6¹ 8 + 0% where 8y denotes the projection of onto span (u2).
and 0' denotes the projection of 0 onto span (22) Combine Lemma 3.2 and Lemma 3.3 have
(0 u2) + 10%,u2) 1
{0r
Uz U2)
K
1
|
2
U2
110111
||0
|
122
100
112
K
110 11
K
+
1
12
110912
110911
110912
10%
1
K
1009
2
||09|:
K2
K
10
|10 1
By our choice of and 7 that 7/2
n
+// log" 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 722 - c
a t log" T
1/2
we have:
nT
1/2
100 112
(2(+1/a)) log" T)
Together with Theorem 3.1 we have
L( = Laav (0") exp (-c|10²1k2)
log" T
1/2
Tn(12 - c]- exp -c
(3+1/a) log²1 T
= cxp (-c n((++/aa (n(tttaaa)
nT
1/2
log²11
where the last equality holds by the parameter choice 72 (n2t3/aa log" T) n/""
1/2
Finally, letting
c ( ( the claim follows immediately.
C PROOFS FOR SECTION 3.2
In this section, we consider general normr 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 by nnom perturbation the implicit bias of gradient descent algorithm changes to converging in direction to l nn-norm max margin solution Mg. We provide
counter example here. Consider S {21 (#1, y1), 22 (x2, y2)) with 21 (10, =
(-10,-1) and yı 1, 3/2 -1
easy to see that the form max margin solution U.e = (1, with You = 10, and the norm max margin solution u. = (or ) with 722 = /101.
Without perturbation, we have that the gradient descent initialized at the origin converges in direction to f2-norm max margin solution 22 with step. Now take -nrm perturbation with c 0.5, the negative gradient is given by: LLavv( = (0) (zı - c (0)) + fa(0) We initialize gradient descent at the origin with any constant step size. By the symmetry of the
2 (z2 c sign (0).
training data, we have that 8f always stays always inside quadrant I, and converges in direction to
T
362 /362 ). which is neither T.o or U2 but inside the interior of convex hull of To and Øg. In
361
fact, exactly equals to the 22,00 defined in 10
16

---

Published as a conference paper at ICLR 2020
Proof of Lemma 3.4 We prove that solutions to (T)) and the robust SVM against bg norm pertur- bation parameterized by c (8) are equal up to a constant factor. We first have that 72,9 (c) in (TO) is equivalent to
22.4
max min yı c/1011p- | se(m
(27)
We denote the unique solution
27 as u2.q. It is not difficulty see that
Di W2,9
<| el|u2,qll 2 12.0 Vi ,..
We define U2.q
#2.1 72.0"
then:
Mi U2.q T
Vi 1, .....
It is now clear that u2,g is feasible solution (8)
We denote the optimal solution (8) u, then
we have by the optimality of a that ||ا|| < 7| <
||w,ممl and feasibility of a that
72.8
Yo (22.0 πt) 72.0 l2 2 72.a Vi I..... ......
Then from previous two inequalities we have 72.22 a feasible solution to (27 with objective value
equal to the optimal objective value of (27). Since the optimal solution to 27 unique, this implies
that Ti u2.4 which concludes our proof.
72.9
We extend Lemmal 3.1 bounded nnomm perturbation set.
Lemma C.1. Recall the definition of Y2.g in (10.. For any c < "g- we have that (- V Lady (0), U2.9) 2
Ladv (2) all Rd.
EL maxi (-M((2; + +,)) For each sample (zt, y1) S. given classifier 0, the worst case perturbation is 8 argmax|18]1:55 exp (-yi(a; +5) T)) jrgm vho To The corresponding loss is then (0) = E exp
Proof. Recall that we have (0)
(- (is + TT).
Since for fixed 8, the function exp
(-ii + T)) is convex in 0, hence the gradient of Ladv (0)
-L (0) Σ exp
(-yi(1; 82) ya yo + ōz).
Then by the definition of U2.g. we have
(-Vaa =
Σ exp
-M(( + T)) ( (u( + +5,), u2.0)
(28)
exp
Yi + 5.) 72.0
(29)
1=1
where the second inequality holds by ||0 I c, and the definitions of u2.9 and Y2.g in Lemma 3.4
Note that for 2, by the fact that 72,2(c) = c, we immediately have Lemma 3.1 holds.
As direct corollary of Lemma C.I we have ||0*1l is bounded away from 0 for all 1. Corollary C.1. Let 6 = in Algorithm we have: ||0* ||2 2 27 72. for al t 2 1.
Proof. The proof is similar Corollary 3.1 omit the details here.
Proof of Theorem 3.3
For simplicity, we define = you, and have ||=:|22 S 1 since | S 1. We
have for #
V Ladv
exp (ap(== (-2, 0 cc1011p)) (-2 + c011011p).
i=1
n 2 Ladva(P) (0) = Σ
exp (-2, T. 0 -c|0))))) (-2 + cb)10)) (-2 + c011011p)
i=1
1 n
exp (-2, 2 0 + ((1
+ (p- -digo 2--)
11
17

---

Published as a conference paper at ICLR 2020
where Op-10 denotes taking element- (p - 1)-th power of 8.
Note that we have |0]ple = 1. By the conjugacy of lp ---norm and no-m with 1 + 1 = 1, we
p.
have||0|lp | (0, s). Hence we upper bound the first term in Hessian Lavv (0) above
by
exp (-z 0 + +c10)) (-z + c0 (-z + cd (
(30)
exp (- 0 + c (11)) (1 + cv
(31)
1
We further have:
diag( ( 20)
(p- 1) diag( 0 20) S (p - 1)
d=-
|10|100 18801
1
1 (p 1)d=
110
3p-2
S (p - 1)d
20
100
Together with the fact that p 2 1, we bound the Hessian L2Ld (0)
as:
2 Ludv (0) S Ladv (0) (1 + evd)2
c(p
1)d3
2p-2
3p-2
1
I.
||0||2
Note that the Hessian expression indicates that the objective is highly non-smoote around origin. However, as shown in Corollary C.I starting from origin, 0r always stays away from the origin with distance bounded below.
Using Taylor expansion, and by 0c+1 = Hr V (0', we have Laav (0*+1) < Cndv(0') - V >0) + (1) Ladv(()) 10)
A (H())) (32)
max or [0r -
2
where A (H())) max denotes the largest eigenvalue of Hvv), and
1 ||a||a
(vv) Ludv( (1) (1 ev c(p 1
I.
Since 17" 1, by Corollary C.I for any 2 I, we have 110* 1| e Y2.g Letting mp (1 + 2 3p-2
c(p 1)d 3pd "2.0"
and since that Ladv (0) is convex function, obtain that
Ladv (0(+1) < Caav 1/1lV (0') 112 + Laav my max max (0'+1, Ladv }
2
We then show by contradiction that we have Ladv < (fdv Assume this is not the case, then we have:
(aav( - ((1-((11111)))) M(nn)) (1-M(19) 1IV
Ladv (adr((1))) (8))12
(Cadv(0') - L
2
However, if we choose o7' satisfying 17¹ S (0C) we have the right hand side of previous inequality strictly smaller than Cadv(()) which is clearly a constradiction. Hence when we choose
2 n 1647. we have Ladv (frt1)) ) < (f'v and
Ladv (0(+1) S (0') - 17' V (0')12+ (L (09) mp
(33)
Now by induction, if we choose v/' = S 1nsa for t 2 1, then we have 333 holds for all
t 2 1. Note that we have an upper bound of Ladv (0'), which is
Ladv (82)
1 Σ
exp (-u((; + 8²)
n1
iml
1
n
(3i(I1; + +T,) 01, y1(2, TT)
exp
n1
1
exp
2 + (1 +1+ = exp (-12, + (1 + +Vdd). (77.99
(34)
71
1=1
18

---

Published as a conference paper at ICLR 2020
where 5, denotes the worst case perturbation F, and 0g denotes projection of 0' onto span(u2.g).
and 01 denotes projection of 0¹ onto span(
In summary, we have that 1
rf' = S min
t} for all 2 1, where M, = m exp (-12. + (1 +1+ +1
(35)
Mp
we have
Ladv 11 S (0d) - 1/1 L (oautv(())))))))))) (0))1 (1 (IIV(avv(''))))
MpCudv (0')
(36)
2
S Ladv - " V Ladv (0') 1/)
(37)
where the last inequality holds since pfy (0') S MyyLady (81) ) 1 1. Now for any E R we have
||0+t1
01 = ||0 8 2n' (VLaav ( 0r 0) + (l (6%)
I ||0 2 2n' (Ladv - Lad (6)) +
S ||0 0 2n' (fad Ladv + 2n' (Cadv(0") Ladv Ladv (0*
1 0 2n/' (0 Laav (0))
where the first inequality holds by the convexity of Ladv (0), and the second inequality holds by (37)
Summing up the above inequality from = to 1 and by nf n S = 17 together with Ladv (0x+)) S Ladv((") we have
1
L Ladv(() 1
|00
0 01 S tn
(110113 + 18)113)
(38)
2tn
Since 0 is arbitrary, by choosing
log(t)
U2 we have
72.9
log
2
110
12 + 110011
+ (1+ (V
22
and
1 Σ
log 1
1
Ladv (8)
exp
min (2+ + 6;) T 22.9 2214
n1 i=1
which yields
1 +
1
log²t t
+ (1 evaa2) - -o
( llog² t
Cadv(0))
(39)
1
In
22.9
1m72,
Parameter Convergence: Intuition. Before formally prove the implicit bias of GDAT, provide some intuitions here for better understanding. We claim that T lim same direction as the solution to
is in the
Tol
min 2 [10| 2 + n())1101pp s.t.
2, To2 1, I....n
(40)
Note that 6t is conic combination of {2; - call0 (1 and 010011 only depends on the direction of 0r Hence by normalizing the norm of 0t and using lim 1|0'11 = oc, if the limit
Uso lime- g² 1 exists, it satisfies the following condition under proper scaling that
Σ a.(2 c0 00110))p))
s.t. a, 2 1, 1,...
-1) - -1....n n.
Defining (ai,..., a.) and (0.a) = (01001>c + 1)0, (110)>cc + 1)a), it is easy see that (0,a) a)
a solution to the following system
Σ a,(2 - co0l
(41)
s.t.: 0 2 0, 2 0 2 c|1011p + 1, Vi = 1,...
(42)
a,(2, 0 <|00| 1) 0, Vi 1,...
(43)
19

---

Published as a conference paper at ICLR 2020
Notice that the above set of equations 411 43 following optimization problem
is exactly the first-order KKT condition of the
min 2 0012
s.t.
2,
0| + +1, I.....
(44)
44) has a robust reformulation as maximizing the 2--norm margin under the worse case fy-norm
perturbation bounded by that
min 2 001
s.t.
min (z + 6,) 2 1, I....n. Se
or equivalently
max min min yz( + T
(45)
i= 16 |00|,
We note that 45 is a Support Vector Machine problem over an uncoutable data set that is generated by norm-bounded perturbation Stc, q) = {(x,)) where 3i E [n]. | zilly I c, = y. By the separability and < Ty. we have that S g) is well defined.
By the first-order KKT condition we have that (44p is equivalent
min |00|2 + r<))1|01p> s.t. z 1, = 1,... n.
for some proper (c) that depends the same direction as the solution the mixed (l2, (1) -oom max margin solution of (40)
Hence in summary, if Uoe lim [|al| exists, it is in
Claim: In general, for by norm perturbation bounded by 0 converges in direction to the solution to min (2; + 6:) T 2 1, 1,...n. n2 16
min 2
|0112 s.t.
s.t. 2 2 1, Vi 1....n min |01| + (c)111112
for some proper n/(c) that depends on e.
Proof of Theorem 3.4 Recall that in Theorem 3.3 showed in 33 the following recursion
(n) V Ladv (0')
Ladv Laav(O 10
(0') 7// V (0')
mn Cadd (0')
V Ladv (8*) )
112
S exp
my
V LLdv (0)
Cadv((")
2
11²
A exp
7222 V Lady (2) + mp
V Ladv )1))
2
where the last inequality holds by Lemma C.I
Applying the previous incquality recursively from
1 to
1, we have
2/2
Ladv (0') exp
1274
L (0')
mp V Lady (0*)
Now since in the proof of Theorem 3.3
showed that mymp
35 combining the above inequality
this with 37 we have
7² VLad (0))
mp 2
Σ
V Cady (00)
Ludv Ladv((') S (otr(
2
Combining this inequality with the upper bound on Ladv( in (34). we have
(-1
Ladv < exp
- m/2.9
V Lady (8 - -2. + (1 + +ovo)
8=0
Now for all i E [ns], we have:
cxp (- min vı( T,) ) < nexp
-72,0 + toaaa
-
V Ladv
S1
20

---

Published as a conference paper at ICLR 2020
which yields
min Va(a; + 6,) 2 7/2, Σ |/ Lady ( (6') + +2200 (1 cvd) log n. |
Dividing both sides by |10|2. and since lim, Ludv Ludr( 0, we have lime 110 = cc. Hence,
lim min Vala + 6:) 0c (-00 16
Ladv (0")l2
1 cv + log (46)
2 lim 772,9 t0000
1101112
||0$|1
100 12
2 72.9:
where the last inequality holds by 110|12 12 S E
Lady (0
Hence in summary, we have
min (e + 6:) 1
72.9
|01|2
Hence, we have lim 0¹/ 00/1101/22 is solution to 10 but notice that the solution to (10) is unique
since multiple of its optimal solution would be the solution to (8) that
min 1101
min y1 T Vi 11. 6:E4:lg)
BER
which is convex program with strongly convex objective. By this fact, we conclude that lim;->o ||0*||2 = U2.4- To further get the rate of convergence, we use the convergence of ad-
versarial risk in (39). and establish the lower bound ||0'||: ||0'||2 Ω (log t). Combining this with (46), the claim follows immediately.
D Lo -NOMM PERTURBATION
Recall that the robust SVM against -nom perturbation parameterized by i formulated as 31(2; + 6,)
72,00 = max min
min
(47)
0
i= ==
|101|2
and its associated max--argin classifier is
U2 argmax min min y; 6z)
||0||==1 == Se
It is easy to see that for e Yao, both 72 and 02,00 are well defined, and 72,x0 0.
Before showing parameter convergence, we first prove that the adversarial risk goes to zero. To avoid analyzing -erttuuurbation directly, which can go messy. For À > O, we define a smooth approximation -nomr that
d
hx(0;) + and H^(0,) Σ (x,)))
Note that as À + 0, (a) + |101| uniformly. We then define a smoothified version of 44 that let perturbation set be (A) (ō Vjj [d], 18,1 Ax(0,) 0,1 ), and the corresponding 72.00 and
U2,00 become
22,A max min min Va + +5:)
(48)
1|0|12
U2. argmax min min ye(x, + 5,) To.
(49)
1101|==1 i=l.... (A)
Note that the Hausdorff distance between (A)A) and {8 || < converges to 0 as goes to O. It can be seen that when X - 0, the smoothified problem 448
reduces to (47) That is.
lim 72.x = 72.00 and limx- U2, = 42.00
Theorem D.1. Let perturbation set be A,(A) = {5 : Vj [d]. 15,1 -
Ax(0,) (0,)) }, and let its associated 10,1
adversarial risk be
1 Σ max exp -i +5,) (T))
Ladv (0)
ni 6.EA.(A)
For < 72 letting 7) (142cA 1/252, we have
Laav( < O (
log* ((1 2cA 2112222
tr/.,x
21

---

Published as a conference paper at ICLR 2020
Proof. By the definition of perturbation set that A, {6:V] [d],15g1 =
,,x(622) 18,
}. we have
Ladv(0)
exp
0 + cH (0)) y=y
t=1
By some simple calculation, we have
01
dd
A
(0) =
H²Hx(0) diag (10P A)3/2
Vo8+ +
V02
(03 + A)3/2
Then, it holds that
1
Ladd (0)
exp (- 2 0 cHx (-2+
Cadd (0)
exp - 2/ 0 + (0) (222 + HHH 22, (HH()) + +oV2Hx(0))
can be verified that V² Ladv (0) S (1 + vx Ladv (0) By Talyer expansion, we have
2c و2 n
Cadv(('t)) & Cadv 17) LLdv (0')11 + (1 +
CaaxfLadv( Laa) (0
V Ladv (0') 112
vX 2
(50)
Now we show that Ladv (0(+1)= 2 Ladv (0')
does not hold when vs (142c2-1/2)
Suppose
the contrary holds. By (50). we have
Ladv (1- " Lndv (0))
(1+ 20 )x
vX
(Ladv(0') VL < (adv(09)
2
where the last inequality holds by n 11+2cA-1/22 (/a Hence we obtain contradiction.
Note that Ladv (89) 1, and if n (1-2c2-1/3ja+ "1 (1+2cA-1/99$ (anv( holds for t 0, and Ladv(0' S 1. Consequently, we can inductively show that (0'r I 1 for all f, and 1) S (1+2cA-1/3y2 (or) always holds if we let 17 (14220-1/3j2-
-
By the choice of 17, we obtain the following recursion taht
2c n2? Ladv
Ladv (0++1) < Ladv (0") - n/ll ad (0') + (1 +
V LL (a))
(51)
2
= Ladv (8')
" Ladv 11)
(52)
2
Using the previous recursion we have that for any 0 Rdd
1100+1
011
||0 0| 2n (Vaadv (O'), 0r -0) + 1 (adv((0')11
< 10 0 [ 2n (Cad (0') (0)) + 2n (Cadv (0') Ladv (0(+)))
= 110 01 2n, (0't) Laav La))
where the second inequality holds by convexity and (5Ip. Summing up the previous inequality from
= 0 to = t - 1 and by Ladv Cadv(0 (@ut)) s Ladv(("), we have
Ludv - Ladv (0) S 2mn 1012
Taking 0 logt A2 we have 22,2
1
Ladv (0)
max exp (-) + TT))
(A)
logt U2,
1
max exp -yi(xs + +6,) (A)
s T.
n1
72,1
where the last inequality holds by maxs,EA, (1 + 6,) '22, 2 22,x Hence we obtain
1 log2t o loog² t(1 + 2c2 2cx-112232
Ladv (0') - - (y2,41)
172.1
22

---

Published as a conference paper at ICLR 2020
Before showing parameter convergence, need the following lemma which is a generalization of Lemma 10 Gunasekar et al. (2018a), but with much simpler proof.
Lemma D.1. Fix < Y2.x. for any E RRC, we have
V 2 Ludv (0)v(0))2.)) (2)
Proof.
Ladv = Σ exp (- you. nt i=1
1
where 5; = -argmin 2 M((x)) T Then by the definition of 72,x and U2,A (48 we have
(y 22 2 72,A
From which we obtain Ladv (0), (2, 2 Ladv (2,x the claim follows by Cauchy-Schward inequality.
Theorem D.2. Under the same setting in Theorem D.1 have
0f
lim 100 100112
W2.A-
Proof. Recall that in Theorem D.I we showed in (I)) that
2c 2 17
Lddr
Ladv (0++1) S (0'v( 7/ V Ladv (0') + +
V VLdd (0')
2
2c
11
exp
+ (1+
12
| Lady (0' )13
Ludv (0t)
VT
2
2c
"
exp
112 (0)) (1
| Lady (0 |13
VX
2
where the last inequality holds by Lemma D.I
Applying the previous inequality recursively from
8 = to t - 1, we have
(09) < exp
-27,
A
(
21+ ==0
2c
22 2
Ladv L (0*) 113
VX
t=
Now by 51 we have
1-1
2c 12
1-1 (8*)
Ia+
|
Σ
v Lady (0')112 ( - (atv S 11
VX
2
2
sm0
mm 0
which yields
Ladv(0') S exp
-1772,A
V Ladv (0 (0')
==0
Next for all E [n]. have
exp
min (EEA(A))
ye(2; + TT)
= exp (-y:z, To 1 (cH+((00))
1-1
|1 Lady (0t) )
I <nep
-1/72,
==0
which implies
min ye(2; + TO' 2 12221 (A)
V Ladv (0*) log n..
==0
Dividing both sides by ||0||2. and since lim
Ladv (8t)
0, we have lime 1|0112 = oc. Hence,
ge
| Ladv
1 + log 72.
lim min (z, + T.)
lim 772,
bx (
110|12
1100|2
10 1|2
where the last inequality holds by |10'
D Ludy Luddx(0))) (0²)
23

---

Published as a conference paper at ICLR 2020
In summary, we have
min &EA,(A)
y/ (2) + 6.)
lim 1-
2 72.A
10
Hence limg: |10 is solution to 48 to
Note that the solution to
(48 is unique since it is equivalent
min 1011 s.t.
min vilui + 5.) 1, Vi 1 n, (EA,(A)
We thus conclude that 1 1 To summarize, we have shown that for all À >> O. lim T 42 The -nomm perturbation corresponds the case when + O, is natural conclude that for loo perturbation, have
22
lim;- gr |00 U2 The discussion for q follows similar argument, hence we omit the
details here.
E ADDITIONAL EXPERIMENTS ON PERTURBATION LEVEL AND SPEED-UP
We provide additional experiments the connection of perturbation level and the speed-up effect of adversarial training for neural networkds. We run GDAT with loo -nom perturbation. The setup of the experiments is exactly the same the setup in Section 4 used GDAT algorithm in {0.1, 0.15, 0.23.
We will vary the perturbation level
From Figure B we could that GDAT indeed accelerates convergence of loss and accuracy 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 that the speed-up effects become stronger when
observed for GDAT. From Figure 4 use larger perturbation level, and this relationship is consistent across different width of hidden layer. Traditionally, the benefit of adversarial training is understood two fold: 1. it improves the robustness of the learning algorithm, i.e., the solution has better loss toward adversarilly perturbed seample; 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.
1.2
1.0
Loes: eloan data
0.8
0.6
Iterations
Iterations
Iterations
Iterations
Accuracy: cleaa data.
Cleam Training
0.15
100
200
305
400
100
200
300
400
150
20
20
65
20
Iterations
Iterations
Iterations
Iterations
(a). Width
(b). Width
128
(c). Width 256
(d). Width 512 512
Figure GDAT with Different Perturbation Level: Clean Training Loss
24

---

Published as a conference paper at ICLR 2020
1.4
1.0
Loss: clean data
Iterations
Iterations
Ierations
Iterations
Accuracy: clean data
70%
Clean Training
60%
0.15
0.20
50%
100
200
300
400
150
200
303
400
150
200
20
65
80
Iterations
Herations
Herations
Iteratious
(8). Width 61
(b). Width
128
Width 256
(d). Width 512 512
Figure 4: GDAT with Different Perturbation Level: Clean Test Loss
25


Reviews:
[{"review_id": "ryePl_e5Kr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper applies theory on implicit bias of gradient descent to an adversarial training toy example. It attempts to utilize the theoretical results for deriving insights on how adversarial training establishes robustness. The theoretical results are complemented with experiments on linear classifiers and small neural networks.\n\nThe key technical contributions look mostly like an application of the existing theory on implicit bias of gradient descent, thus I would rate the originality of this work as moderate. From the point of view of adversarial machine learning, I don't consider the results to be significant. In particular, there is a large discrepancy between the theoretical results on the toy example and the empirical convergence behaviour of adversarial training of neural networks (compare Figure 2 and 3). In particular, the theoretically derived exponential speed-up of adversarial training for the toy example is not reflected by empirical observations for practically relevant adversarial training tasks (e.g. consider the convergence behaviours reported by Goodfellow et al. (2014) or Madry et al. (2017)). Thus, the theory doesn't seem to be generally applicable beyond the linear toy model. A clear discussion of its limitations is missing.\n\nOverall, while this may be an interesting extension of the existing body of literature on the implicit bias of gradient descent, I find that from an adversarial machine learning perspective this paper does not meet its objective to derive generally applicable insights on how adversarial training works. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}, {"review_id": "SkeJiVQ0Fr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Contributions:**\nThis paper extends results on the implicit bias of gradient descent (GD) Soudry et al. (2018)[3] for the case of gradient descent based adversarial training (GDAT).\n\n**1) Theoretical result for L2 norm:** Convergence of standard risk in GDAT is significantly faster than its counterpart in the standard clean training using GD: For any fixed iteration T, when the adversarial perturbation during training has bounded l2-norm, the classifier learned by GDAT converges to the maximum l2-norm margin classifier at the rate of O(1/√T), exponentially faster than the rate O (1/ log T ) obtained when training with only cleaned data Soudry et al. (2018) [3].\n\n**2) theoretical result for Lq norm:** When the adversarial perturbation during training has bounded l_q-norm with q > 1, with a proper choice of c, the gradient descent based adversarial training is directionally convergent to a maximum mixed-norm margin classifier, which has a natural interpretation of robustness, as being the maximum $l_2$-norm margin classifier under worst-case $l_q$-norm perturbation to the data.\n\nThe paper is well written and easy to understand. I haven’t checked the proofs, but I focused on readability and motivations. \n\nI have the following questions.\n\n**Theoretical questions:**\n- Can you please explain the intuition of lemma 3.2 and 3.3 for convergence?\n**Experiments questions:**\nKeeping in mind that the core of the paper is about proving that GDAT enjoys the same implicit bias as GD and better convergence performance on clean data, I can’t help myself by asking you how these properties reflect in experiments with deep Neural Networks:\n    - Can you please clarify your motivation for the reduction of the performance gap when the with of the hidden layer increases (Figure 2)? It is not clear what do you mean by ...“as network width increases, the margin on the samples outputted by the hidden layer also increases”...\nMy personal interpretation of the results is that the inner maximization problem is much harder to solve and being approximated, the effect of the GDAT is much less prominent, meaning that PGD is not enough to benefit from adversarial training in this sense. What do you think about it?\n    - Take away message of the paper: adversarial training accelerates convergence. Theoretical results are for the training empirical loss.\nIs this also the case of the validation loss? You observe this behavior for the case of a single MLP on MNIST binary problem 2 vs 9 (appendix E) claiming that adversarial training improves generalization performance.\nThis is not observed in the literature, it is actually the opposite [1, 2]: it exists a tension between robustness and performance on the clean test set. Why do you think you are not observing this? My guesses:\n    - you are analysing a very simple binary problem\n    - your model is very simple and comparable to a linear classifier, so your theoretical results hold.\n\n[1][1805.12152 Robustness May Be at Odds with Accuracy](https://arxiv.org/abs/1805.12152)\n[2][1810.12715 On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models](https://arxiv.org/abs/1810.12715)\n[3][1710.10345 The Implicit Bias of Gradient Descent on Separable Data](https://arxiv.org/abs/1710.10345)\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "H1eIh4uhYB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The 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.\n\nFor 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))).\nFor 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.\nThese results are further illustrated by numerical experiments.\n\nThe 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.\n\nHere are some questions/comments that could be further discussed:\n* 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?\n\n* 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?\n\n* 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.\n\n* the analyzed algorithm considers optimal perturbations -- do you have a sense of how robust the theory is to errors in the inner optimization?\n\n\nminor comments/typos:\n* 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\n* 'polyhedral cone ...': bar{u} should be u?\n* after Theorem 3.2 'not an issue': not so clear, this should be discussed further (see comment above)\n* 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\n* 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?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides theoretical guarantees for adversarial training.  While the reviews raise a variety of criticisms (e.g., the results are under a variety of assumptions), overall the paper constitutes valuable progress on an emerging problem.
Decision: Accept (Poster)