Robustness Guarantees for Adversarially Trained Neural Networks
Authors: Poorya Mianjy
Raman Arora
Venue: NeurIPS 2023 poster (2023)
Keywords: Adversarial training
neural networks
robustness
guarantees

Abstract: We study robust adversarial training of two-layer neural networks as a bi-level optimization problem. In particular, for the inner loop that implements the adversarial attack during training using projected gradient descent (PGD), we propose maximizing a \emph{lower bound} on the $0/1$-loss by reflecting a surrogate loss about the origin. This allows us to give a convergence guarantee for the inner-loop PGD attack. Furthermore, assuming the data is linearly separable, we provide precise iteration complexity results for end-to-end adversarial training, which holds for any width and initialization. We provide empirical evidence to support our theoretical results.

Robustness Guarantees for Adversarially Trained Neural Networks
Poorya Mianjy Johns Hopkins University
Raman Arora Johns Hopkins University arora0cs. ..a00ss.jhaa jhu edu
Abstract
We study robust adversarial training of two-layer neural networks as a bi-level optimization problem. In particular, for the inner loop that implements the adver- sarial attack during training using projected gradient descent (PGD), we propose maximizing lower bound on the 0/ 0/l-loss by reflecting surrogate loss about the origin. This allows us to give a convergence guarantee for the inner-loop PGD attack. Furthermore, assuming the data linearly separable, we provide precise iteration complexity results for end-to-end adversarial training, which holds for any width and initialization. We provide empirical evidence support our theoretical results.
Introduction
Despite the tremendous success of deep learning, neural network-basee models are highly suscep- tible small, imperceptible, adversarial perturbations of data test time [Szegedy et al., 201 2014]. Such vulnerability to adversarial examples imposes severe limitations on the deployment of neural networks-basee systems, especially in critical high-stakes applications such as autonomous driving, where safe and reliable operation is paramount.
An abundance of studies demonstrating adversarial examples across different tasks and application domains [Goodfellow et al., 2014, Moosavi-Dezfooli al., 2016, Carlini and Wagner, 2017] has led to renewed focus robust learning robust learning is to find models that yield reliable predictions on test data notwithstanding adversarial perturbations. A principled approach to training models that are robust to adversarial examples that has emerged recent years is that adversarial training [Madry et al., 2018], Adversarial training formulates learning min-max optimization problem wherein the 0-1 classification loss is replaced by a convex surrogate such as the cross cross-entrope entropy loss, and alternating optimization techniques are used to solve the resulting saddle point problem.
active area of research within machine learning. The goal of
Despite empirical success of adversarial training, our understanding of its theoretical underpinnings remain limited. From a practical standpoint, it is remarkable that gradient based techniques can efficiently solve both inner maximization problem to find adversarial examples and outer minimization problem to impart robust generalization. On the other hand, a theoretical analysis is challenging because (I) both the inner- and outer-level optimization problems are non-convex, and (2) unclear a-priori if solving the min-max optimization problem would even guarantee robust generalization.
In this work, we seek to understand adversarial training better. In particular, under a margin separability assumption, we provide robust generalization guarantees for two-layer neural networks with Leaky ReLU activation trained using adversarial training. Our key contributions are follows.
1. We identify a disconnect between the robust learning objective and the min-max formulation of adversarial training. This observation inspires simple modification of adversarial training
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

we propose reflecting the surrogate loss about the origin in the inner maximization phase when searching for an "optimal" perturbation vector attack the current model.
2. We provide convergence guarantees for PGD attacks on two-layer neural networks with leaky ReLU activation. This is the first of its kind result to the best of our knowledge.
3. We give global convergence guarantees and establish learning rates for adversarial training for two-layer neural networks with Leaky ReLUU activation function. Notably, our guarantees hold for any bounded initialization and any width a property that is not present in the previous works in the neural tangent kernel (NTK) regime [Gao et al., 2019, Zhang et al., 2020].
4. We provide extensive empirical evidence showing that reflecting the surrogate loss in the inner loop does not have significant impact on the test time performance of the adversarially trained models.
Notation. We denote matrices, vectors, scalar variables, and sets by Roman capital letters, Roman lowercase letters, lowercase letters, and uppercase script letters, respectively (e.g. X, x, æ, and 2). For any integer d, we represent the set {L..... df by [d]. The fn-norm of a vector x and the Frobenius norm of matrix X are denoted as ||x|| and || respectively, Given a set C, the operator Πc(x) =
minyee ||x - x'I projects onto the set C with respect to the fo-nor.
1.1 Related Work
Linear models. Adversarial training of linear models was recently studied by Charles et al. [2019], Li et al. [2020], Zou et al. [2021]. In particular, Charles et al. [2019], Li et al. [2020] give robust generalization error guarantees for adversarially trained linear models under a margin separability assumption. The hard margin assumption was relaxed by Zou et al. [2021] who give robust generaliza- tion guarantees for distributions with agnostic label noise. We note that the optimal attack for linear models has simple closed-form expression, which mitigates the challenge of analyzing the inner loop PGD attack. In contrast, one of our main contributions is to give convergence guarantees for the PGD attack. Nonetheless, as the Leaky ReLUU activation function can also realize the identity map for a = 1, our results also provide robust generalization error guarantees for training linear models.
Non-linear models. Wang et al. [2019] propose a first order stationary condition to evaluate the convergence quality of adversarial attacks found in the inner loop. Zhang et al. [2021] study adversarial training as a bi-level optimization problem and propose principled approach towards the design of fast adversarial training algorithms. Most related to our results are the works of Gao et al. [2019] and Zhang et al. [2020], which study the convergence of adversarial training in non-lincar neural networks. Under specific initialization and width requirements, these works guarantee small robust training error with respect to the attack that is used in the inner-loop, without explicitly analyzing the convergence of the attack. Gao et al. [2019] assume that the activation function is smooth and require that the width of the network, as well as the overall computational cost, is exponential in the input dimension. The work of Zhang al. [2020] partially addresses these issues. In particular, their results hold for ReLU neural networks, and they only require the width and the computational cost to be polynomial in the input parameters.
Our work different from that of Gao et al. [2019] and Zhang et al. [2020] in several ways. Here we highlight three key differences.
First, while the prior work analyzes the convergence in the NTK setting with specific initialization and width requirements, our results hold for any initialization and width.
Second, none of the prior works studies computational aspects of finding an optimal attack vector in the inner loop. Instead, the prior work assumes oracle access to optimal attack vectors. We provide precise iteration complexity results for the projected gradient method (i.e., for the PGD attack) for finding near-optimal attack vectors.
Third, the prior works focus on minimizing the robust training loss, whereas we provide computational learning guarantees on the robust generalization error.
The rest of the paper is organized as follows. In Section 2, we give the problem setup and introduce the adversarial training procedure with the reflected surrogate loss in the inner loop. In Section 3, we present our main results, discuss the implications and give a proof sketch. We support our theory with empirical results in Section 4 and conclude with discussion in Section 5.

---

Algorithm Atk PGD Attack
Input: Sample (x, y), Weights W, Stepsize Macx. # Iters Tatk
I: Initialize 61 6- X
2: for 1 1 to 7 do
3: 81-1 + (x) + Mack Vgl-(yf((6)))
4: end for
Output: 6,, where T E arg | e- (-f
2 Preliminaries
We focus on two-layer networks with m hidden nodes computing f(;; a, W) = aaa (Wx). where W mgd and a IR. are the weights of the first and the second layers, respectively, and a(2) = max 2} is the Leaky ReLU activation function. We randomly initialize the weights a, ~ Unif([-x, +x}) for all hidden nodes E [m]] and randomly initialize W such that || S w, for some positive real numbers and w. The top linear layer (i.e., weights a) is kept fixed, and the hidden layer (i.e., W) is trained using stochastic gradient descent (SGD).
For simplicity of notation, we represent the network as f(x: W), suppressing the dependence on the top layer weights. Further, with slight abuse of notation, we denote the function by fw (x) when optimizing over the input adversarial perturbations, and by (W) when training the network weights.
Formally, adversarial learning is described as follows. Let X' C R2d and y = {=1} denote the input feature space and the output label space, respectively. Let D be an unknown joint distribution on X' x y. For any fixed x E X, we consider norm-bounded adversarial perturbations in the set ((x {6: ||ō x|| v). for some fixed noise budget v.
Given a training sample S == {(x,, }/) ~ D" drawn independently and identically from the underlying distribution D, the goal is to find network with small robust misclassification error
(W) ED max (o) < 0). SEA(X)
where W : [|]
F is the weight matrix normalized to have unit Frobenius norm, Note that, due to the homogeneity of Leaky ReLU, such normalization has no effects on the robust error whatsoever.
In adversarial training, the 0- loss inside the expectation is replaced with convex surrogate such as cross entropy loss f(z) = log(1 + e e=)), and the expected value is estimated using a sample average:
1 1 Σ max (ynlw-(6.)) n &EA(())
To (W)
Notwithstanding the conventional wisdom, adversarial training entails maximizing an upper bound opposed to a lower bound on the - 1 loss. In contrast, we propose using concave lowerbound on the 0 1 loss solve the inner maximization problem. Let (z) = - {( 2) = - -log(1 e*) denote the reflected loss. In Figure
{())
log(1 +
x) +1
plot the 0-1 loss, the cross-entropy loss, and the reflected cross-entropy loss. Starting from 81 x, the PGD attack updates iterates via
8.+1 = (6 + Teexl-
as described Algorithm 1. We emphasize that the only difference between standard adversarial training and what we propose in Algorithm and Algorithm that we reflect the loss (about the origin) in Algorithm 1.
Figure 1: The (-1 lass (red), its convex sur- rogate, the cross-entropy loss (blue), and the reflected cross-entropy loss (green).
3

---

Algorithm 2 AdvTr Adversarial Training
Input: Stepsize Mr., # Iters Ttr
1: Initialize a ~ Unif{ -K, +*) and W1 such that ||ill S w
2: for t = 1 to T do
3: Draw (X,, y/.) ~ DD
4: ô, 4 Atk( ( Xe, We)
5: Wx+1 + W₂ Yer V
6: end for
3 Main Results
We consider a slightly weaker version of the robust error. In particular, we are interested in adversarial attacks that can fool the learner with a margin for some small, non-negative constant 3, we define the 3-robust misclassification error as: ea(W) = I (minses(s) (o) < - In particular, as B tends to zero, E (W) - Erbb Erbb(W) (W). When ,3 is a small positive constant bounded away from zero, (x, y) contributes e (W) only if there exists an attack 5 (xx) such that fw confidently makes wrong prediction on 8. In other words, B-robust misclassification error is the probability that for (x,, v) D, B-effective attack exists.
Definition 3.1 (Effective Attacks). Given a neural networks with parameters (a. W) and a data point (x. y) and some constant 3 > 0, we say that 8, Axx) 8-effective attack if yfw (6%) S -3, where W = W/|
Our bounds depend on several important problem parameters. Before stating the main results of the paper, we remind the reader of these important quantities. denotes the attack size. x and w are the bounds on the norm of the parameters a and W at the initialization. Finally, is the Leaky-ReLL parameter. Our first result stated in the following theorem' gives convergence rates for Algorithm I in terms of the and the negated loss derivative (-) under the assumption that an effective attack exists. The negative derivative, --' of the loss function has been used in several previous works to give an upper bound on the error Cao and Gu [2019]; here, we borrow similar ideas from Frei et al. [2021]. In particular, as will become clear later, we will use positivity and monotonicity of (-) to give upper bound on the B-robust loss using Markov's inequality.
Theorem 3.2. Let ö, be a B-effective attack for given network with weights (a, W) and given example (x,y), with 3 2 2v(1 a. Then, after Tau iterations, PGD with step size qatk S W generates an attack datk such that -(((y[((6.) < 22 (1(((((aa))))) + NesTT
4y²
Theorem 3.2 establishes that under proper initialization (n 1//mm,, when --effective attack exists, Algorithm finds a e-suboptimal attack vector in O(32/8 /t) iteration. We next study convergence of Algorithm 2 under the following distributional assumption.
Assumption 3.3. Samples (x. y) are drawn i..dd from an unknown joint distribution D that satisfies:
|x|| s R with probability 1.
There exists a unit norm vector v. E ERd, ; ||v = 1, such that for (z. y) ~ D, we have with probability 1 that y(v. xx 2 7 0.
The first assumption requires that the inputs bounded, which is standard in the literature and is satisfied for most practical applications. The second assumption implies that D is linearly separable with margin 7 > 0. Of course, we do not need non-linear neural network to robustly learn predictor under such a distributional assumption. But can we even guarantee robust learnability of neural networks for such simple settings? Nothing is known far standard (non-robust) training of two-layer neural networks using SGD, the convergence guarantees in the hard margin setting were unknown until recently [Brutzkus et al., 2018J. The following theorem establishes that adversarial training can efficiently find a network with small 3-robust error.
know. We note that even for
Proof's are deferred to the appendix.

---

Theorem 3.4 (Convergence of Algorithm 2). For any 6 >
in at most Ter S GA(R (1traa Gy-oPate
iterations, Algorithm with step-size 1/r S (K+22) finds an iterate that, in expectation over {(x,, yr) V:)) satisfies <=(WW>) I for any 3 2 20(1 - a)kym, provided that for all t E [T], and Tath 2 8y²
Math S w
"aret"
Some remarks are in order.
Beyond Neural Tangent Kernel. As opposed to the convergence results in the previous work [Gao al., 2019, Zhang al., 2020] which requires certain initialization and width requirements specific to the NTK regime, our results holds for any bounded initialization and any width m.
Role of the Robustness Parameter V. Our guarantee holds only when the desired robustness parameter is smaller than the distribution margin 7. Furthermore, the iteration complexity increases gracefully as O(v²/( / - 2²² as the attacks become stronger, i.e., as the size of adversarial perturba- tions tends to the margin. Intuitively, as -> 0, the attack becomes trivial, and the adversarial training reduces to the standard non-adversarial training. This is fully captured by our results - as v/ + 0, the number of attack iterates Tat goes to zero, and recover the overall runtime of O(? 22 ??- as in the previous work [Brutzkus et al., 2018, Frei et al., 2021].
Computational Complexity. To guarantee e-suboptimality in the 8-robust misclassification error, we require Tur (0((->))- 2=- iterations of Algorithm 2. Each iteration invokes the PGD attack in Algorithm which itself requires Tatz = Ovv² /E) gradient updates. Therefore, the overall computational cost of adversarial training to achieve e-suboptimality is O( ((T-op=))) ) Note that Tatk is a purely computational requirement, and the statistical complexity of adversarial training fully captured by Ttr. Remarkably, there only a mild 0(>2 /(> - 2)) statistical overhead for B-robustness, and the computational cost increases gracefully by multiplicative factor of
-
1222 (7-8)=E
O
Learning Robust Linear Halfspaces. When a = 1, the Leaky ReLU activation equals the identity map, and the network reduces to linear predictor. In this case, we retrieve strong robust generalization guarantees for learning halfspaces, as the lower bound required for 3 in Theorem 3.4 vanishes. The following corollary instantiates such robust generalization guarantee.
Corollary 3.5. Let 1//m, = 1/7, and mer (R + w)- For any O, in at most
Ter S 128(1e+w)² (1-1)²22 iterations, Algorithmm 2 finds an iterate t, that in expectation over {(x,, 1T
satisfies Enab (W,) < 2c, provided that for all t E [T], Mare S | and Tatk 2
Su² MaszE
Dependence the Norm of Iterates. The iteration complexity of Algorithm I is inversely proportional to the learning rate Tatk. and therefore increases with |/ Thus, when calculating the overall computational complexity, one needs compute an upper bound the norm of the iterates. As we show in Equation (5) in the appendix. it holds for all iterates that ||W 1 || S || 11 + 33 Therefore, if we set x 1/ /m and w² 3/(R + 2²²2. we have the following worst-case weight- independent bound on the overall computational cost:
812
Thr 8 W.
8y2 (w² + 31xx(t - 1))
NatkE
Te
24
12v212
196608 v22
R + u)ze
(R+ v)ze
(7- 1 u'
Therefore, the worst-case overall computational cost is of order (( - 16-). We note again that this cost is purely computational - the statistical complexity is still in the order of O ((7 D) 2
A Adversarial Robustness for any 3. As we discussed earlier, as 3 + 0. the 3-robust error tends to the robust error, i.c., (W) Eoob()) Although Theorem 3.4 does not hold for 3 0 (except
5

---

for the linear case discussed above), it is possible to guarantee robust generalization with arbitrarily small B. as stated in the following corollary.
Corollary 3.6. For any desirable B O, let 20(1-a)m For any > O, in at most Ter S
3
G1(R+w) -attt//aaaaaaaaa/aaaaaaaaaaaaaa iterations, Algorithm 2 with step-size TjSr S 4v (1-o)
BB(R finds an iterate
(y-w)aa=e
T that, in expectation over {(x,, y)) satisfies so(W,) S 2e provided that for all t E [T].
Nath <
(1-)²) and Tatx 2 3'I..
2(-aa)
3.1 Proof Sketch
In this section, we highlight the key ideas and insights based on our analysis, and give a sketch of the proof of the main result. Using Definition 3.1, the proof of Theorem 3.4 crucially depends the following two facts. First, whenever there exists a 3-effective attack, we show that Algorithm I will efficiently find sufficiently good attack (in the sense of Theorem 3.2). Second, leveraging the Perceptron analysis from the prior works of Frei et al. [2021], Brutzkus et al. [2018], we show that as long as the attack size smaller than the margin Y, robust training is not much harder than standard training. In particular, the following Lemma establishes that the expected value of the negative loss derivative eventually becomes arbitrarily small.
Lemma 3.7. For any O, Algorithm 2 with stepsize ner x
2(R v) finds iterate that, in expectation over {xx, Me ) satisfies ED( Bpl-('(( (yJW, (xeen(x)))] at most Ter S [[,]|W[]|l iterations.
remark that the result in Lemma 3.7 holds for any attack algorithm Atk, as long as it respects the condition (x) E Axx) for all x. We are now ready to present the proof of the main result.
Proof of Theorem 3.4. Recall, that B-robust misclassification error is defined as:
(B( TP min (d) < - = min vfw(6) -3I[ (EE(())
(Homogeneity of f)
(dE((x)
key step in the proof is to give an upper bound on 6g in terms of the attack returned by PGD, i.e., (ax((x) rather than the optimal attack minsea(x) y/w(0) (8). Theorem 3.2 does provide with such an upper bound; however, (1) it only holds in expectation, and 2) it is conditioned on existence of an effective attack at the given example (x, y) and the weights W. Naturally, we use Markov's inequality to bound the probability above. order to address the conditional nature of the result in Theorem 3.2, we introduce truncated version of the negative loss derivative. In particular, for any c, let (2(2) = (' (2) I cl be the loss derivative thresholded at c. Note that 2 S c implies that (2) 2 (c) therefore, p(2 c) < (2) 2 (c)) Let B, == B||W>lle, where W, is the iterate guaranteed by Lemma 3.7. We have
<w(W,) = PP min yfw. (8) - - s SP (EA(x))
-- min yfw, (6)) 2 -- bEA(x)
Ep
l' (minse ufw. (01)
(Markov's inequality)
- (-3r)
< 2ED -L
min yfw. (6))
1/2 2 5)
dED(x)
Given W,, , for any (x, y) D. one of the two following cases can happen:
There exists a 3-effective attack. In this case, by Definition 3.1. it holds that minsea(x) yfw. (6) S W-Ile -B,. Therefore, by definition of the truncated nega- tive loss derivative, it also holds that - e, (minseA(x) vfw, (6)) -f''minneenss v/w, (f)).
Now, using Theorem 3.2, we get that
4r2
-L_p,, min yfw. (6)) < -28 (y.f. (y.fw,(0axxxx)) Maxx Tack 6EA(X)

---

Cross Erioayy -Retected Crass Entroy
Number of strra Attoc
Number stme
501
5000
Top 10 Atadks, Sorted by Be Comesgonding Loss
Top 130 Atacss Sortad by the Comsponcing Loss
Top 1000 Atackss Sorted by the Comsspncing Loss
Figure 2: Number of the top-k attack vectors that are optimal, i.e., can induce label flip, for the cross entropy loss (blue) and the reflected version (red), for different values of k: Left: k 10, Middle: 100, and Right: h = 1000.
2. There does not exist 3-effective attack. In this case, by Definition 3.1, it holds that mill:4(x) wfw, (6) > - = -B, Therefore, by definition of the truncated nega- tive loss derivative, also holds that -f's, (minsea(x) y y/w. (6)) = O, which is trivially bounded by the upper bound in the first case above, given by Equation (3).
Putting back the above cases in the upper bound on the 3-robust error, we arrive at:
4v²
4v2
5 E (W,) S 2Epl- (x))) +
2 MaxxTes
latk Tata
where the first inequality follows from Theorem 3.2, the second inequality follows from Lemma 3.7
given the proper choice of Tir. and the final inequality holds by setting Tatk 2
8y²
Mass
4 Empirical Results
Adversarial training is widely used in training robust models and has been shown to be fairly effective in practice. The goal of this section since the focus in this paper on the theoretical analysis of adversarial training in non-linear networks, the goal of this section is merely empirically study the effect of using reflected loss in Algorithm 1.
attest reproduce previous empirical findings. Instead,
The experimental results are organized as follows. First, in Sec, 4.1, we compare the optimal attacks found by a grid search the surrogate loss and its reflected version. In Sec. 4.2, we empirically study adversarial training with reflected loss the binary classification setting. Finally, Sec. 4.3, generalize the reflected loss, which is key to theoretical analysis, to multi-class classification setting. We then report the results on the CIFAR-10 10 dataset using a deep residual network.
4.1 Grid Search Optimization
We look at the following simple 3-dimensional 3-class classification problem. Consider the point (x, y) where x [3. 2, 1] and 1. We focus the simplest non-trivial function, i.e., the identity mapping, given by fxx = x. Obviously, f correctly assigns x to the first class because the first dimension larger than the others. Also, a perturbation of the form 8 0.501, 0.5, 0) with ||o|| 0.7078 can flip the label, since f(x +xx+00 5) = [2.499, 2.5, incorrectly predicts the second class.
We restrict the attack the set {6 E (-0.51, +0 ||o|| < 0.7078). We look every possible attack vector on a grid of size 800 x 800 x 800. We then sort these vectors in descending order of the corresponding loss function, i.e., the cross entropy loss and its reflected version, and simply count how many of the top-k attack vectors actually induce a label flip. We take this as a measure of how effective is the corresponding loss maximization problem at finding good attack vector. As can see in Figure 2, the proposed method of maximizing the reflected cross entropy loss is far more effective way of generating the attacks than maximizing the cross entropy loss.
4.2 Binary Classification
Experimental Setup. We extract digits from the MNIST dataset [LeCun al., 1998), which provides (almost) separable distribution, consistent with our thcoretical setup. The dataset contains
7

---

Atk.
FGSM
R R-FGSM
PGD-00
R-PGD-00
BIM
R- R-BIM
PGD-2
R-PGD-2
Trg.
Standard
0.236
0.236
0.033
0.286
0.286
0.286
0.003
0.256
PGD-<o
0,004
0.004
0.005
0.005
0.005
0.005
0.003
0.05
R-PGD-c0
0.003
0.003
0.004
0.004
0.004
0.004
0.002
0.042
PGD-2
0,013
0.013
0.022
0.024
0.024
0.024
0.002
0.034
R R-PGD-2
0.004
0.004
0.005
0.006
0.006
0.006
0.0
0.008
Table I: Robust test error of several adversarially trained models with and without reflecting the loss
(Standard training, PGD-x0, R-PGD-oc, PGD-2, R-PGD-2), for different attack benchmarks (FGSM, R-FGSM, PGD-oc, R-PGD-o0, BIM, R-BIM, PGD-2, and R-PGD-2).
12665 training samples and 2115 test samples. We evaluate the generalization error as well as the robust generalization error of fully-connected two-layer neural networks which are adversarially trained with and without reflecting the loss. The network has 100 hidden nodes with ReLU activations.
The outer loop consists of 20 epochs over the training data with batch size equal to 64, randomly shuffled at the beginning of each epoch. The initial learning rate is set to 1, and is decayed by multiplicative factor of 0.2 every 5 epochs. We use several benchmark attacks with and without reflecting the loss. The benchmarks include the Fast Gradient Sign Method (FGSM) Goodfellow et al. [2015], the Basic Iterative Method (BIM) Kurakin al. [2017], and the PGD attack with Eg constraint (PGD-2) and l constraint (PGD-co). For each of these attack strategies, we have corresponding approach that involves reflecting the surrogate loss - we denote the resulting methods as R-FGSM, R-BIM, R-PGD-2, and R-PGD-oc, respectively. The perturbation size for FGSM, PGD-xx, and BIM (and their corresponding reflected version) is set to v = 0.1. For PGD-2 and R-PGD-2, we let a larger perturbation size of 2 as recommended in the Adversarial ML Tutorial.
In the inner-loop, if the attack is iterative, we use step-decay scheduler with initial step-size of 10, which decreases the step-size every 10 steps by a multiplicative factor of 0.2. In Table 1, we report the standard test accuracy as well as the adversarial test accuracy of the trained models over 10 independent random runs of the experiment. Different rows and columns correspond to different training algorithms and different attack models, respectively.
Analysis. We make the following observations in Table 1. First, reflecting the loss has a minimal effect on FGSM and BIM attacks, in terms of robust test accuracy of the trained models. In particular, the columns 1 and (similarly columns 5 and 6) are identical up the third decimal point.
Second, in PGD-2 attacks, reflecting the loss generally yields a stronger attack note the striking differences in the last two columns between 2GD-2 and R-PGD-2. We observe a milder trend for PGD-c0 attacks, where R-PGD-c0 attacks turns out be only slightly stronger, except for the standard training setting where reflecting the loss has a huge impact on the robust error.
Third, we would like remark on the performance of adversarially trained models. We can see that reflecting the loss in general helps robustness. In particular, second and fourth rows (PGD-oo and PGD-2) are completely dominated by the third and fifth rows (R-PGD-cc and R-PGD-2), respectively.
Finally, it is notable that even though PGD-2 and PGD-c0 are much weaker than their reflected counterparts, they are still competitive in terms of the robustness when used in adversarial training. Thissuggests that finding a "strong" attack is not a necessity for adversarial training to succeed.
4.3 Extension to multi-label setting
In binary classification using the logistic loss, in essence, adversarial training finds attack that minimizes the log-likelihood of the correct class. Using the reflected loss, instead, we aim at maximizing the log-likelihood of the wrong class. In a multiclass classification scenario, there are multiple such wrong classes. Therefore, an important design question is which wrong class should be targeted in the attack phase? Here, focus the most natural choice: we target the wrong class with the highest log-likelihood This greedy approach is easy to implement, and has minimal computational overhead over standard adversarial training.
We emphasize though that the greedy approach (described above) is sub-optimal, even in a simple linear setting. Intuitively, when the parameters are such that the logits for the true class correlate
8

---

with the logits for the most likely wrong class, the greedy approach fails. In particular, consider the following 3-class classification problem in IR?. Let fx( = Wx, where W [2e,, c1, 10ez] E R3x2 Here, denotes the i-th standard basis. Consider the point have the highest and the smallest likelihoods, respectively. Given a perturbation size xx x|| S 0.3,
[1, Oj. Clearly, class and 3
the likelihood of the second class will never dominate that of the first class:
w (x + 6) - 2e] (x + 6) = 2(x1 + + (11 + 01) = lo (x + 6) - w. (x+
where the inequality follows by using the fact that æ1 and |ô1 S 0.3. Therefore, the greedy approach fails here. Whereas, within the specified perturbation budget, maximizing the likelihood of the third class can indeed find a label-flipping attack. For example, with 6 = [0.0.3] the point
x' = [1, 0.3] will be assigned to the third class, because wi3 x' = 33 > w x 2 > Wiz
Attack Size
2/255
Steps
2
Steps =4
Steps
16
Steps 32
RA
SA
RA
SA
RA
SA
RA
SA
PGD R-PGD
14.182
91.254
20.702
90.424
21.014
90.132
20.848
90.09
14.338
91.208
20.726
90.384
20.958
90.06
20.746
89.992
Attack Sizc
4/255
PGD R-PGD
17.764
90.748
30.344
88.736
37.564
86.65
37.304
86.572
17.162
90.114
30.34
88.826
37.4
86.734
37.374
86.522
Attack Size 1 = 8/255
PGD R-PGD
20.064
90.178
31.21
87.746
18.916
78.402
48.936
77.926
20.1
90.564
31.19
87.852
18.792
78.382
48.828
77.982
Attack Size y = 16/255
PGD 16.19
85.908
21.524
86.816
48. 722
68.37
15.292
58.526
R-PGD
15.986
89.708
21.362
86.83
48.742
68.456
44.778
58.486
Table 2: Robust test accuracy (RA) of adversarially trained models with and without reflecting the loss, for different values of the attack size v E {2, 1, 8, 16) and number of steps in the attack Steps E {2, 4, 16, 32). We report the results for test-time attack size = 8/255; the better performance is highlighted in gray, where the intensity corresponds to difference performance.
We use adversarial training with and without reflected loss (denoted by R-PGD and PGD, respectively) to train a PreActResNet (PARN) He et al. [2016] on the CIFAR- 10 dataset Krizhevsky et al. [2009]. In the training phase, we conduct experiments for attack size v/ E {2, 8, 1655 We build on the Py PoTch implementation in Zhang et al. [2021]. and we follow their experimental setup, which is described next. We use a SGD optimizer with a momentum parameter of 0.9 and weight decay parameter of 5 10-1 We set the batch size to 128 and train each model for 20 epochs. We use cyclic scheduler which increases the learning rate linearly from 0 to 0.2 within the first 10 epochs and then reduces it back to O in the remaining 10 epochs. We report robust test accuracy (RA) of an dnvversarially-rrinee
model against PGD attacks Madry et al. [2018) (001) (RA-PGD), where we take 50-step PGD with 10 restarts. We report the results for test-time attack size v 8/ 8/255. Based on our empirical results, using the (greedy) reflected loss in adversarial training does not significantly impact the standard/robust generalization performance of the learned models.
5
Discussion
We study robust adversarial training of two-layer neural networks as a bi-level optimization problem. We propose reflecting the surrogate loss about the origin in the inner maximization phase when searching for an "optimal" perturbation vector to attack the current model. We give convergence guarantee for the inner-loop PGD attack and precise iteration complexity results for end-to-end adversarial training, which hold for any width and initialization under a margin assumption. We also provide an empirical study on the effect of reflecting the surrogate loss in real datasets. Next, we list few natural research directions for future work.
Extension to multiclass setting. binary classification, which is the focus of this paper, reflecting the loss about the origin provides a concave lower-bound for the zero one loss (see Figure 1). Maximizing the reflected loss then corresponds to maximizing the likelihood of the wrong class. This simple modification enables to guarantee the convergence of PGD-2 attacks, and yield stronger

---

attacks in our experiments. However, extending this idea to the multiclass setting is not trivial. In particular, the idea of maximizing the likelihood of the wrong class does not trivially generalize to the multiclass setting due to plurality of wrong classes. Nonetheless, as we show in the experimental section, naive greedy approach to choose a wrong class seems to provide competitive performance in terms of standard/adversariia test error. Is there simple, principled approach to obtain a lower-bound for the misclassification error in the multiclass setting? would be interesting to explore theoretical and empirical aspects of such possible extensions.
Beyond 8-robustness. The notion of B-robustness is crucial in our analysis. Although we provide robustness guarantees for arbitrarily small positive 3 (see Corollary 3.6), our current analysis does not allow for standard robustness guarantees (3 = 0) except for the linear setting (a = 1). At a high level, the main challenge here is to guarantee that the attack can always find adversarial example - if there exists one - regardless of whether the attack is ß-effective or not. This is, in particular, challenging to establish for iterative attacks such as PGD, because they can only guarantee getting sufficiently close to an optimal attack in finite time. Therefore, if the optimal attack can just barely flip the sign, the computational time for finding it can grow unboundedly. Therefore, providing robust generalization guarantees (3 = 0) is an interesting research direction for future work.
Optimization geometry. In our theoretical results, we focus on PGD-2 attacks, which are based on steepest descent with respect to the & geometry. In our experiments, we also provide empirical results for steepest descent attacks with respect fo geometry (including FGSM and BIM) on the reflected loss. We leave the theoretical analysis of such attacks to future work.
Acknowledgements
This research was supported, in part, by DARPA GARD award 12020004, NSF CAREER award 194-19,,,5,, funding from the Institute for Assured Autonomy (IAA) at JHU, and the Spring 22 workshop on "Learning and Games" at the Simons Institute for the Theory of Computing.
References
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. SGD learns over- parameterized networks that provably generalize linearly separable data. In International Conference on Learning Representations, 2018.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in Neural Information Processing Systems, 12:1063610886,, 2019.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In IEEE
symposium on security and privacy, pages 39-57. IEEE, 2017.
Zachary Charles, Shashank Rajput, Stephen Wright, and Dimitris Papailiopoulos. Convergence and margin of adversarial training separable data. arXiv preprint vrxivv/905.. 0920,, 2019.
Spencer Frei, Yuan Cao, and Quanquan Gu. Provable generalization of SGD-trained neural networks of any width in the presence of adversarial label noise. arXiv preprint arXiv:2101.01 152, 2021.
Ruiqi Gao, Tianle Cai, Haochuan Li, Cho-Jui Hsich, Liwei Wang, and Jason D Lee. Convergence of adversarial training in overparametrized neural networks. Advances in Neural Information 2019.
Processing Systems,
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015. URL http://arxiv.. hrg/abbs1442..66
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint 1116v:1412.6572, 2014.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European conference computer vision, pages 630-645. Springer, 2016.
10

---

Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images, 2009. Alexey Kurakin, Ian Goodfellow, and Samy Bengio, Adversarial examples in the physical world, 2017.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-bard based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-232) 1998.
Yan Li, Ethan X.Fang, Huan Xu, and Tuo Zhao. Implicit bias of gradient descent based adversarial training on separable data. In International Conference on Learning Representations, 2020. URL httpp::/oopenrevier net/
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
Seyed-Mohsen Moosavi-Dezfool Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method to fool deep neural networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 2574-2582, 2016.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In 2nd International Conference on Learning Reprexentations, ICLR 2014, 2014.
Yisen Wang, Xingjun Ma, James Bailey, Jinfeng Yi, Bowen Zhou, and Quanquan Gu. On the conver- gence and robustness adversarial training. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 6586-6595. PMLR, 09-15 Jun 2019. URL mlr. prwssressvvvee /rress/v7/// htt///9//////g/ //ang1 htmm..
sttts://proceeddiee wttpssarw..ppp.e.eeeeeeeeeeeeeee
Yi Zhang, Orestis Plevrakis, Simon S Du, Xingguo Li, Zhao Song, and Sanjeev Arora. Over- parameterized adversarial training: An analysis overcoming the curse dimensionality. In NeurlPS, 2020.
Yihua Zhang, Guanhuan Zhang, Prashant Khanduri, Mingyi Hong, Shiyu Chang, and Sijia Liu. Revisiting and advancing fast adversarial training through the lens of bi-level optimization. arXiv preprint arXiv:21 2021.
Difan Zou, Spencer Frei, and Quanquan Gu. Provable robustness of adversarial training for learning halfspaces with noise. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 13002-13011. PMLR, 18 24 Jul 2021. URL https:://// //procedd//.c..iinggg. mlr. wttppp/wsseeeeepppppppppps zou21a, html.

---

Table 3: Key terms, corresponding symbols, and descriptions.
Term
Symbol
Description
Net Function
f(x: (z), (W)
(,, x)
Leaky ReLUU
((2)
max (x2, 2
Binary Xent
((z)
log (1 + E
Mirrored Xent
8- (2)
log(1 c*)
Robust Error
Froh ( (W)
PlmaxseAis) 1 M/w(( (6) < 0
B-Robust Error
[,(W)
IP ((maxse((x) V/w(0) < <3 a, 1,''(w, x)x
Net Grad wrt Weights
Dw. fx(W)
Net Grad wrt Input
(x)
0, (w, x)W, (W) = (w),wx)). x)
Homogencity in Input
Homogeneity in Weights
[w(x) =
W)
A Appendix
For simplicity of the notation, in our analysis of the PGD attack, we drop the subscripts denoting the iterates. That is, the 1-th iterate of the outer loop, the weight matrix and the sample point denoted by W and x, y, instead of W, and X2, Vt- We can then use the same variable to measure the progress of the attack in the inner loop. PGD updates are therefore given by [Ia(x)]6, (yff
Proof of Theorem 3.2. We first bound the norm of the gradient of the iterates follows:
I fw((d)) Σ a (w, 8z) w
o (wr 5r)
m
K
||w/l
Kv W||== G
We analyze the distance of iterates from 8.:
|| 5.112 -116, 5.112-
|[] Natt ( 16, 5.11
< 110e + Natt -. 16. 6.11
21att (iaattVel-o - IVE (ufw (5.))
2 (w.w(())))(V//((())))) 5.) + v/ ll (yff (
S Marel' (www(())))))) - 5_) narl (y.f-
(e-(()) S max(1, (-)()
S 2 (ufw (8)) (6))( - vfw,((8.) Paate_(yfwi (6,)
(Natt S I/G2) < 2aat (e- (yfw(()) - e- (VSw. Matt (v(w(()))
(concavity)
3 Marl__ (vfw((6)) (
12

---

where fw,,(d.) == (V. 6.). Averaging over iterates, rearranging, and cancelling telescopic terms, we arrive at:
T
00: 8.11
16++1 - -
2
Σ
h (vfw(6))) 2
l (vfw,((6)))
T
Natt
T
|6
6,11
2 min f- (-(yfw,c(6o))
(Telescopic sum)
Matt
v²
2min f- (v.W,
(ō x,, E Ax)
laatt
n²
= -L
2 (-
MatiT
Next, we show that if 6, is an effective attack on fw, then it's also effective on fw... In other words, we have that:
vf.) = (Vt))
(6.), 6.) + fw(,w()))) - fw(()), = vfw(6.) + vVV (6.)),,
Let = [j E (m]lo'(w, 6,) o o'(w,- -6.) be the set of nodes whose pre-activation sign at time is different from the optimal 6.. The second term can be bounded as follows:
(V((( V
aj (o (w3 6t) o' (wj 8.)) w; d.
m
S |y/
aj (o (w; 8,) o'(,, 8.)) wj Sal
j=1
lo'(v (w, 5,) - o' (w, 8.)1 Iw, 8zl
k
JEI
(1
a)k
W3 8 w, del
G I,)
jæ
<1 a
Σ
|w5llllo_ Rell
(Cauchy-Sehwarz))
(1 \m/l
(Cauchy-Schwary
Given that there exist 3-effective, i.e. there exist o_ such that (6,) S -Bl we have:
(fw. - (6.) + (1 - mm) W||
3
< (fw( + 2 |
(u S 2(1 2(1-a)m/m
Together with the previous inequality on the average of instantaneous loss, we arrive at:
-k- -L-(w(((6sxx) min TE(T]
- (yfw(6:))
T
- l- (vfw(6))
T
12
2 (vfw(6)))))
T
Therefore, have
v²
28 (2fw(6./22) < (=(((((0atr)) +
(3)
Matt. T
13

---

Next, we show that for any z', and 6 > O, the inequality 2 (2/2) - l=(2") + e implies that
(2) - (2') + 4e. The following inequalities hold true:
2 (z/2) (=
2oo e² 1 -log(1 + )
+c
loog(
1+ S logg( lted
1
1 +222/2
Ited
e²
++e 2/2
1+e-0
e=
e=
21+e- S Ite-2
(2c 00=1/2$140 s1+
-((2) S -l'(z) 26
(definition of ('))
= [((=) S -L'2')2(1 + +6)
(e* S +1+22 for all E [0, 1)
(()) S (2') + 46'
(- 1)
Let = (fw().), Zatt == (datt) and d' == v² in terms of (-), as given in Equation (3), implies sub-optimality in terms of (.):
RM Using the above inequality, sub-optimality
2e (2./2) s l- (Zate) + é' ( S -26' (2att) + 4e'
That is, for any (x, v) ~ D, holds with probability one that
402
[((fw((6.)) -26 (2
(4)
Let [ denote the expectation over random draw of samples (x1, for Adversarial Training given in Algorithm 2. Let Ai (We, V.), G, ||Well and let H. == ELavTe [f].],
G == ELavTe G?] be their corresponding population version.
Proof of Lemma 3.7. The proof heavily builds the prior works of Frei et al. [2021]; include it here for completeness. Let V. E mRd be such that v, </m sgn(a,)v... We define the correlation between the iterates and V. as follows H, == (W,, V=). This correlation evolves as:
Å = (W4+1. V.)
(W, The Ve(yefa, V.) A. The (v. (W.)). (.)))..VV Wwfa, (W.), V.)
Recall that a fa( a,0'(w; 8)5. Therefore, we have that:
aw,
Ve (W.)), V.) = (a (w. 8)5, vm
sgn(ar)v.)
d'(w,. 8) v.)
Note that
ye (8, v.) = yr v.) + (6 - x, v.)
2 7 11, (6 x, v.)l
2 7 1|8 x x|Ilvv|1
2
14

---

On the other hand, for leaky ReLU, it holds that o'() 2 a. Therefore, we arrive at
ye (W.), V.) N Ki a(r - v)
=kaym(7-1)
Therefore, we have that
Hot1 2 H₂ nul' (y. (W (Wa))anm/(r v)
HroI 2 H1 (7 V) m Σ Exartel (y
(taking expection ELATY [-)
The gradient norm is bounded as follows:
V /s. (W.)l
Σ lazo (Wz, o.)5ell mnn v)²
Next, we analyze the norm of the iterates, i.., G7 = |W.l is also easy to verify that -2(2)² = ze- 1te==
lte= I 1. We have:
G 11W, - The Ve(yefo, (W.))
1|W l8:- + V (Wo)) 2mm fu (wJs,, We
C7 + = (v: (yt f8. ( (W.))l 2nm (Wi f6, (We))urfo,.W;
$ G + mx² 2 (R- 2)² + 27Trr
(-f(2)2 S 1)
G? + 37
Ghr S m <m'k x (R
Therefore, taking expectation EsAVT on both sides, we have that
T G 3
(5)
and using va+b S Va + Vb, we have GT < G1 + V.nTT. Also, we have that H? (Eaavr (W,, V.))² get:
Enavte II,.2 < G that Hel I G.. Putting all together,
-G1 T1rly x)ax m
Eravn E' (yt (W.)) Ho nn(7 v)aK m EnaYTe l' (Vr.o, (W:))
HT
$ Gr
< G + v V3nmT
-Puly v))a m
Exavn E' (wff((W)) 2G + 22 NTT
+2/1IT
We now argue that for any e, there exist an iterate / such that Exavtr ( (W.)) S.. Assume otherwise, then we get:
nal7 - V) S -1141 - V))RY m
E F C' (W,)
2G1 + +2/Tni Tht
mel7 v)akmmmrr - -2/THT - 5 0
v Th + v mhe + 2G yona
5
4 + Ginanyme)
T
(n 2)
15

---

Therefore, we have that - -Enavre ( fvr (W:)) = ERarT l' (vi (x)tt S. Moreover, (owrdi(((
EAdvTel fw. (Pate (x+)))] = BSWDi (-f (ve (xx)))
(independence from future samples)
BI--IND- B (x. Be )ND [- fw. (o (x)))
(Smoothing property of the conditional expectation)
(x.))=))) (yl,, (fatt (W, independent of (xt, y1) given St-1)
which completes the proof.
16


Reviews:
[{"review_id": "uznJSU1uVJ", "reviewer": "Reviewer_avt7", "summary": "This paper investigates the adversarial training of two-layer neural networks on linearly separable data. The authors propose to reflect the commonly used convex surrogate loss during the inner loop that generates adversarial attack via the PGD method, and derives guarantee on the convergence of the attack. Meanwhile, this paper also provides theoretical results on iteration complexity for the adversarial training on linearly separable data that holds for any width and initialization of the network. Numerical studies are conducted to show the performance.", "questions": "1.\tWhat feature of the reflected loss function enables the derivation of the theoretical results, or why the standard loss function make the analysis difficult? Can one replace the reflected loss function with a more general loss function? \n\n2.\tTheorem 3.4 says that \"in at most $T_{tr}\\cdots$ iterations, Algorithm 2 $\\cdots$ $\\textit{finds an iterate}$ $\\tau$” with certain property. What does that mean exactly? Is it guaranteed that the model at the end of iteration $T_{tr}$ maintain such property? Or, is any early-stopping criteria necessary in order to guarantee the property?\n", "limitations": "The authors have adequately addressed the limitations of the work.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1.\tThe investigated topic of adversarial training of neural networks is important and has many applications in real world, while the theoretical aspects have not been well-studied. The results presented in this paper are non-trivial contribution to the field, and might help with better understanding of adversarial training of neural networks in more complicated settings. \n2.\tThe theoretical analysis seems solid. The authors introduce some interesting terms such as $\\beta$-effective attack and $\\beta$-robust to help the analysis, which might help in other study.\n3.\tOverall, the paper is well-organized and easy to follow.\n", "weaknesses": "1.\tThe empirical results with MNIST and CIFAR-10 do not show significant difference between the performance of standard adversarial training and adversarial training using proposed reflected loss function.\n\n2.\tThere are some space of improvement regarding the experiments. Specifically, please consider the followings:\n\n(1)\tThe result presented in Figure 2 does not seem convincing to me because (a) the setting is too simple and hand-crafted, while the real data can behave very differently; (b) Only one specific data point ($x=[3,2,1]$) is considered. It is doubtful whether it is cherry-picked or not.\n\n(2)\tIn Table 1, the robust testing error for standard training model under standard PGD attack (0.033) is much smaller than FGSM (0.286), which is unlikely since PGD usually generates stronger attack through multiple iterations. Please double-check the correctness. \n\n(3)\tIn Table 1, please consider including the evaluation of different models over clean testing data (un-attacked) for better comparison. Also, for Tables 1 and 2, please consider including the evaluation under other attacks, e.g., CW attack [1] and AutoAttack [2].\n\nPlease also consider my questions in the next part.\n\n\n[1] Carlini, N., & Wagner, D. (2017, May). Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp) (pp. 39-57). ieee.\n\n[2] Croce, F., & Hein, M. (2020, November). Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In International conference on machine learning (pp. 2206-2216). PMLR.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "[W1] Regarding “*The empirical results with MNIST and CIFAR-10 do not show significant difference between the performance of standard adversarial training and adversarial training using proposed reflected loss function.*” That is actually what we were hoping for. \n\nThe goal here is not to improve upon standard adversarial training. We know that adversarial training is quite successful in practice. This is what we state in the opening paragraph of the experimental results section (**see lines 232 — 235**). However, we cannot hope to give convergence guarantees for adversarial training as it involves maximizing a convex function in the inner loop which is not tractable. This is why we use a concave lower bound on 0-1 loss. **The question that remains is whether changing the adversarial training in this way does worse in practice. The answer is no.** It does not change the practice in any significant way but we gain new insights by establishing computational learning guarantees. \n\n[W2] (1) Regarding “*improving experiments*”, we note that the point of experiment in Figure 2 was to help compare the utility of surrogate loss vs the reflected loss at finding the attack vectors. **It is meant to be a toy example so that we can carefully understand what is going on rather than simply report numbers that often are not very insightful. The goal is here not to have a leaderboard competition, but to unravel the inner workings of adversarial training.** \n\n[W2] (2) It is perhaps not very informative to compare performance across different attacks since the noise budget is not quite “calibrated.” In other words, it is unclear what the noise perturbation budget for an $\\ell_2$ attack be for a certain noise budget corresponding to $\\ell_\\infty$ attack or the FGSM attack. \n\n[W2] (3) Sure, we will be happy to do so. If you look at the code we provide, it is actually quite straightforward to run the corresponding experiments for other attacks and respective reflected losses. \n\n[Q1] The feature of reflected loss that allows our analysis is that it is a concave function that is a lower bound on the 0-1 loss. See, the technical challenge is that the inner loop of adversarial training for finding an adversarial attack amounts to maximizing a convex function which is computationally intractable. It is also unclear why one would use an upper bound on the 0-1 loss function if you were trying to maximize it. So, instead, we use a concave lower bound which is intuitive and computationally tractable. That is the key feature.\n\n[Q2] That is a poor way of writing. We should have written “after $T_\\textrm{tr}$ iterations”. In any case, what we mean is that after $T_\\textrm{tr}$ iterations we find a model that is guaranteed to have a small robust error. "}, {"review_id": "GgjpTwhAWr", "reviewer": "Reviewer_2oBp", "summary": "This paper studies the convergence of adversarial training of two layer neural network, with gradient descent ascent (GDA) type algorithm. The algorithm considered here solvies inner max problem on a surrogate concave loss, and solves outer minimization problem on log-exp loss. Finally, the authors show the convergence to $\\epsilon$ weaker robust error with no more than $O(1/\\epsilon^2)$ iterations. The proof contains two parts, first they show that, solving the surrogate concave loss will yield a pertubation, which is almost as good as the true optimal adversarial perturbation, and then they borrow the existing analysis of two layer classification neural network training, to show that under the solved perturbation, the outer minimization problem can converge to global minima. To the best of my knowledge, this is the first work towards analyzing behavior of GDA on adversarial neural network training.", "questions": "1. I notice that [Allen-Zhu and Li 2022] also studies adversarial training, where they consider Fast gradient method to solve inner max problem. Could the authors do some comparison with this paper?\n\n\n\nAllen-Zhu, Zeyuan, and Yuanzhi Li. \"Feature purification: How adversarial training performs robust deep learning.\" In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 977-988. IEEE, 2022.", "limitations": "One limitation as I mentioned is that the algorithm used here is not exactly consistent with what people use in practice. I do not see any societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": " The convergence of adversarial neural network training is a longstanding problem. The most relevant work is [Gao et al 2019], where they assume the inner max problem is solved by some oracle, not PGD, and hence they only need to perform minimization convergence analysis on the adversarial loss. This paper, for the first time, consider algorithm-based convergence, where they study the case that the inner max problem is solved by projected gradient ascent. \n\n", "weaknesses": "1. My main concern is that, the proof seems to be heavily depending on previous result, and the main technical novelty is the idea of running PGD on concave surrogate, and show the converegnce of PGD.\n\n2. Running PGD on concave surrogate loss is not widely used in practice. In practice, the gradient descent and ascent steps are usually performed on the same loss function.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "[W1] Regarding the “*main technical novelty is the idea of running PGD on concave surrogate, and show the converegnce of PGD*”. That is a fair characterization of the main contribution. The computational learning guarantee for the end-to-end adversarial training follows as a corollary once we have the result for the PGD attack. Note though that the result for the PGD attack is novel and it required us to rethink adversarial training. While, in hindsight, things look easy once you know the trick, it was not quite straightforward. We also believe that simple ideas are elegant and often powerful. \n\n[W2] Regarding the comment about “*Running PGD on concave surrogate loss is not widely used in practice. In practice, the gradient descent and ascent steps are usually performed on the same loss function.*” That is true. However, we can never hope to analyze that approach since maximizing a convex function is computationally intractable. What we do show is that running PGD on concave surrogate is principled and does not change the practice by much. This is evidenced by our empirical results. Both approaches are actually quite comparable. \n\n[Q1] Yes, we would be happy to add a discussion of how our approach and results compare with that of Allen-Zhu and Li. Note though that the two settings are somewhat incomparable as Allen-Zhu and Li make various distributional assumptions, e.g., the sparse coding model. Nonetheless, we do agree that some comparisons on how the two works handle the inner loop maximization are in order. \n\n"}, {"review_id": "guNB0SkBNJ", "reviewer": "Reviewer_Gmw4", "summary": "The paper studies robust training in 2-layer networks. This problem is studied as a 2-spet procedure - finding adversarial samples, and training over these samples. The main result is given a linearly separable dataset, then a 2-layer network with leaky-ReLU activation trained robustly with SGD converges to a robust network in polynomial time. Several experiments are given to support the theoretical results.", "questions": "- Will the proof work also on networks with bias terms?\n- Why is the reflection loss used in the analysis?\n", "limitations": "The authors adequately address the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- I think it is interesting to study robust optimization in a rigorous way, and the main result of this paper- namely that robust SGD converges to a robust network in polynomial time is nice.\n- The empirical result complements the theoretical results, while also generalizing to a multi-class setting.\n- I think the proof sketch gives a nice and intuitive explanation of the main result\n", "weaknesses": "- The use of the reflected loss seems like a crucial part of the proof, although I don’t think it is motivated enough. Is it used just for some technical part of the proof? or is there more to it? I think if it is indeed a crucial part, then there should be a more in-depth explanation of why it is used. \n- The model analyzed is a 2-layer network without biases.  It is not clear whether removing the bias is done just for simplicity, or it is indeed necessary. I think the proof uses homogeneity w.r.t x, which may be the cause for the bias-less network, but if so, can the results be generalized to networks with bias terms?\n- More of a suggestion: Are the convergence results of algorithms 1 & 2 can be decoupled? i.e. will Theorem 3.4 about the convergence of algorithm 2 will hold when instead of algorithm 1 we use any other attack? If so, I think it is good to mention it.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "[Q1] We think that the proof should go through even with bias terms as well, but it may require some extra work. In particular, some of the recent work (e.g., see https://arxiv.org/pdf/2102.11840.pdf and https://arxiv.org/pdf/2301.00327.pdf). The idea here is similar to how the proof goes through in the NTK setting — i.e., ensuring that the weights and the bias terms do not move too far from the initialization, which is indeed the case in many settings as these works show. \n\n[Q2] The reason that the reflected loss is used in the analysis is that it is a concave function that is a lower bound on the 0-1 loss. See, the technical challenge is that the inner loop of adversarial training for finding an adversarial attack amounts to maximizing a convex function which is computationally intractable. It is also unclear why one would use an upper bound on the 0-1 loss function if one were trying to maximize it. So, instead, we use a concave lower bound which is intuitive and computationally tractable. We will add a discussion to that effect. \n\nRegarding your suggestion of decoupling the results of the two algorithms, that is indeed the case. That is actually how we structured Section 3. Theorem 3.2 is for Algorithm 1 and Theorem 3.4 is for Algorithm 2 which involves Algorithm 1. It is also possible to use a different procedure other than PGD — as long as that algorithm returns a good enough attack vector in polynomial runtime, we can still give analogs of Theorem 3.4. We will think more about other alternatives. Thanks for your suggestion. "}, {"review_id": "eXZ3OKsGsQ", "reviewer": "Reviewer_8NN7", "summary": "This paper studies the optimization convergence of adversarial training in two-layer neural networks. This paper also proposes a reflecting loss which search for a better attack.", "questions": "Please try to address my major concern (the first paragraph).", "limitations": "No ethical concern.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is clear and easy to understand.", "weaknesses": "My major concern regarding this paper is that the condition on the attack strength $\\nu$ is too strong. The constraint $\\nu\\leq \\beta/(2(1-\\alpha)\\kappa\\sqrt{m})$ is exactly used in Page 13 (in the appendix) so that the attack on the current model $f_{W,t}$ is closed to the one for the model $f_{W}$. However, in such a scenario, there is almost no difference between clean training and adversarial training. The authors need to relax this condition and provide more insights on the role of the attack strength and the difficulty when it gets larger.\n\nBesides the major concern on the theoretical contribution, there are some issues in the experiments. First, the experiment in CIFAR-10 does not obtain a significant improvement. In Table 2, if counting the colored cells, PGD takes up 4, and R_PGD takes up 3, i.e., PGD may be even better than R-PGD in some cases. Second, there is no error bar information in this paper. Given that the difference between benchmarks and the proposed method is only of a small quantity, the authors need to run experiments for multiple times to obtain a standard error of the accuracies to verify that the improvements are statistically significant.\n\nFinally, in addition to the weakness of the assumption on the attack strength, there is also another gap between the theoretical study and the experiments: the authors may consider theoretical justification on the generalization performance of adversarial training in the linear separable data. I would suggest the authors to investigate the effect on $\\beta$ towards the generalization performance. In many existing literature, people study the generalization performance in simple models, e.g., Gaussian mixture model, linear regression model, but there is limited understanding on linear separable data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1.*Regarding attack strength*, the constraint $\\nu \\leq \\beta/(2 (1-\\alpha) \\kappa \\sqrt{m})$ is not too small since **$\\kappa = 1/\\sqrt{m}$; see line 134**. \n\nIn fact, it is exactly what we should hope for. Consider, for example, the setting with $\\alpha=0$ (i.e., linear unit). Then the constraint simplifies to $\\nu \\leq \\beta/2$. If we think of $\\beta$ as a hard margin between two classes and assume that the class conditional marginals are supported on hyperplanes that are a distance of $\\beta$ from each other, then any perturbation of size larger than $\\beta/2$ will result in robust test loss equal to one. We know that our results are tight since we recover several prior results when we set the parameters accordingly; see the remarks following Theorem 3.4.     \n\n\n\n2.*Regarding experiments*, the goal here is not to improve upon standard adversarial training. We know that adversarial training is quite successful in practice. This is what we state in the opening paragraph of the experimental results section (**see lines 232 — 235**). However, we cannot hope to give convergence guarantees for adversarial training as it involves maximizing a convex function in the inner loop which is not tractable. This is why we use a concave lower bound on 0-1 loss. **The question that remains is whether changing the adversarial training in this way does worse in practice. The answer is no.** It does not change the practice in any significant way but we gain new insights by establishing computational learning guarantees.    \n\n\n3.*Regarding linear separability*, we recall that the goal here is to give a bound on the computational complexity of adversarial training, i.e., how much time is needed to train a model that generalizes robustly. **Without linear separability, we know that empirical risk minimization is computationally hard even for simple models such as linear predictors.** So, if we cannot hope to say anything about the runtime of learning in a clean setting, there is little hope we can do so in the adversarial setting without assuming linear realizability. We know that it is a strong assumption, but unfortunately, there is not much to say in terms of runtime otherwise.    \n\n"}]

Author rebuttal:

Meta-review: This paper provides a theoretical analysis of robust adversarial training of neural networks using projected gradient descent for the inner maximization problem. The theoretical results demonstrating polynomial time convergence of this approach are novel and represent an important contribution. The reviewers found the paper to be technically solid, well-written, and easy to follow. The empirical results were viewed as complementary and helped validate the theory. Overall, the reviewers were positive about the paper and felt it provides new theoretical insights into an important problem. The main unaddressed concern was to better differentiate the approach from closely related work by Allen-Zhu and Li. However, the reviewers felt the paper makes a significant enough contribution as is. Considering the reviewers' overwhelmingly positive feedback, I recommend accepting this paper. The authors have advanced the theoretical understanding of adversarial training convergence and provided results that can inform future work in this area.
Decision: Accept (poster)