Robustness Guarantees for Adversarially Trained Neural Networks
Authors: Poorya Mianjy
Raman Arora
Venue: Submitted to ICLR 2023 (2023)

Abstract: We study robust adversarial training of two-layer neural networks with Leaky ReLU activation function as a bi-level optimization problem. In particular, for the inner-loop that implements the PGD attack, we propose maximizing a 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 and precise iteration complexity results for end-to-end adversarial training, which hold for any width and initialization in a realizable setting.

Under review as a conference paper at ICLR 2023
ROBUSTNESS GUARANTEES FOR ADVERSARIALLY TRAINED NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We study robust adversarial training of two-layer neural networks with Leaky ReLU activation function as bi-level optimization problem. In particular, for the inner-loop that implements the PGD attack, we propose maximizing a lower bound on the 0/1-loss by reflecting surrogate loss about the origin. This allows us to give convergence guarantee for the inner-loop PGD attack and precise iter- ation complexity results for end-to-end adversarial training, which hold for any width and initialization in realizable setting. We provide empirical evidence to support our theoretical results.
INTRODUCTION
Despite the tremendous success of deep learning, neural network-based models are highly suscep- tible small, imperceptible, adversarial perturbations of data at test time (Szegedy et al., 2014). Such vulnerability to adversarial examples imposes severe limitations on the deployment of neural networks-based systems, especially in critical high-stakes upplications such 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-Dezfooe et al., 2016; Carlini & Wagner, 2017) has led to renewed focus robust learning goal of robust learning is to find models that yield reliable predictions on test data notwithstand- ing adversarial perturbations. A principled approach training models that are robust adversarial examples that has emerged in recent years is that of adversarial training (Madry et al., 2018). Adver- sarial training formulates learning as min-max optimization problem wherein the 0-1 classification loss is replaced by convex surrogate such as the cross-entropy loss, and alternating optimization techniques are used to solve the resulting saddle point problem.
active area of research within machine learning. The
Despite empirical success of adversarial training, our understanding of its theoretical underpinnings remain limited. From practical standpoint, remarkable that gradient based techniques can effi ciently solve both inner maximization problem to find adversarial examples and outer minimization problem to impart robust generalization. On the other hand, theoretical analysis challenging be- cause (1) both the inner- and outer-level optimization problems non-convex, and (2) it is unclear a- a-priori if solving the min-max optimization problem would even guarantee robust generalization.
In this work, seek to understand adversarial training better. In particular, under margin separa- bility assumption, we provide robust generalization guarantees for two-layer neural networks with Leaky ReLU activation trained using adversarial training. Our key contributions
follows.
1. We identify disconnect between the robust learning objective and the min-max formulation of adversarial training. This observation inspires simple modification of adversarial training 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.
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 ReLU activation function. Notably, our guarantees hold for any bounded initialization and any width a property that not present in the previous works in the neural tangent kernel (NTK) regime (Gao al., 2019; Zhang al., 2020).

---

Under review as a conference paper at ICLR 2023
4. We provide extensive empirical evidence showing that reflecting the surrogate loss in the in- ner loop does not have a 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 (c.g. X, x, 2, and X). For any integer d, we represent the set (1,- (1,-...d d} by [d]. 'he f--norm of vector and the Frobenius norm of matrix X are denoted as ||x|| and ||X][r respectively. Given a set set the operator 1c((x) = miny'ec ||x xxx||
projects onto the set C with respect to the f2-norm.
1.1 RELATED WORK
Linear models. Adversarial training of linear models was recently studied by Charles al. (2019); Li et al. (2020); Zou 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 gener- alization 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 guaran- tees for the PGD attack. Nonetheless, the Leaky ReLU activation function can also realize the identity map for a = I, our results also provide robust generalization error guarantees for training linear models.
Non-linear models. Wang al. (2019) propose first order stationary condition to evaluate the convergence quality of adversarial attacks found in the inner loop. Zhang et al. (2021) study ad- versarial training 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-linear neural networks. Under specific initialization and width requirements, these works guarantee small robust training error with respect to the attack that used in the inner-loop. without explicitly ama- lyzing 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 et 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 is 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 initializa- tion 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 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 com- putational learning guarantees on the robust generalization error.
The rest of the paper is organized 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, 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.
2 PRELIMINARIES
We focus on two-layer networks with hidden nodes computing f(x; a, W) = aTo (Wx), where W E mxd and a E m are the weights of the first and the second layers, respectively, and (2)) = maxfoz, 2) is the Leaky ReLU activation function. We randomly initialize the weights and W such that ||a/| < i and |[[]| I 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 fx; W). suppressing the dependence on the top layer weights. Further, with slight abuse of notation, we denote the function by fw(x)
2

---

Under review as a conference paper at ICLR 2023
Algorithm Atk PGD Attack
Input: Sample (x, y), Weights W, Stepsize Matk. Iters Tack
1: Initialize 61 6-
2: for = to T do
3: 8t+1 (x) Matk Va Vol- Vzl((ufw(6.))
4: end for
Output: 6,, where arg [ e- (ufw(()))
when optimizing over the input adversarial perturbations, and by fx(W) when training the network weights.
Formally, adversarial learning is described as follows. Let X S Rd and {+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 X, we consider norm-bounded adversarial perturbations the set (xx) = {6: ||ō x|| S v), for some fixed noise budget v.
Given a training sample S == {(x; y:)] D drawn independently and identically from the underlying distribution D, the goal is to find network with small robust misclassification error
Eybh () Ep max (0) < 0], 8EA(x)
where W := W/|WW|| 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 what- soever.
In adversarial training, the 0 loss inside the expectation is replaced with convex surrogate such as cross entropy loss {(z) = log(1 + e e=*), and the expected value is estimated using a sample average:
gob (W) = max (()ff((6)) 6.E(())
(2)
n
Notwithstanding the conventional wisdom, adversarial training entails muximizing an upper bound as opposed lower bound on the 0 1 loss. In contrast, we pro- pose using concave lowerbound on the 0 1 loss to solve the inner maximization problem. Let
2 0 {(=)
log(1 + c
2) +
- - = log(1 + c*)
denote the reflected loss. In Figure 1, we plot the 0-1 loss, the cross-entropy loss, and the reflected cross-entropy loss. Starting from &1 = x, the PGD attack updates it- erates via
8,41 1ui=1laxx((
11x(x) (6. + Tatkl- (yfw(()))(
as described in Algorithm 1. We emphasize that the only difference between standard adversarial training and what propose in Algorithm 2 and Algorithm I is that we reflect the loss (about the origin) in Algorithm 1.
The (red). its convex sur- rogate, the cross-entropy loss (bluc), and the reflected cross-entropy loss (green).
Figure 1:
3 MAIN RESULTS
We consider a slightly weaker version of the robust error. In particular, we are interested in adver- sarial attacks that can fool the learner with margin for some small, non-negative constant 8, define the 3-robust misclassification error as: E (W) = IP (minsea(x) (6) < -3} In particu- lar, as 3 tends to zero, (g( > Exob Esob(WW (W). When is a small positive constant bounded away from zero, (x, contributes Eg (W) (W) only if there exists attack 5 A(x) such that fw confidently makes a wrong prediction on In other words, 3-robust misclassification error is the probability that for (x,y) D. B-effective atlack exists:
3

---

Under review as a conference paper at ICLR 2023
Algorithm 2 AdvTr Adversarial Training
Input: Stepsize TT.., # Iters Tir
1: Initialize a and W, such that ||a|lx S is and || Sw
2: for = 1 to T do
3: Draw (Xe, M/) D
4: 6, 4 Atk Kt, Me)
5: W1+1 4 We Vhr Vw Wwe(ytss,
6: end for
Definition 3.1 (Effective Attacks). Given a neural networks with parameters (a, W) and data point (x, v) and some constant | > O, we say that d, E A(x) is 8-effective attack if y yfw (6.) S -3, where 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. i and w are the bounds on the norm of the parameters and W at the initialization. Finally, is the Leaky-ReLU parameter. Our first result stated in the following theorem' gives convergence rates for Algorithm in terms of the and the negated loss derivative --"(-) under the assumption that effective attack exists. The negative derivative, -." of the loss function has been used in several previous works to give upper bound on the error Cao & Gu (2019); here, we borrow similar ideas from Frei et al. (2021). In particular, as it will become clear later, we will use positivity and monotonicity of -f'(-) to give upper bound the 3-robust loss using Markov's inequality.
Theorem 3.2. Let d. be a B-effective attack for a given network with weights (a, W) and given example (x. y), with 2 2v(11 a)m./m. Then, after T Ta iterations, PGD with step size Mack S W.. generates an attack datk such that (w (ō.) )) < -26' (2fw(60cc +
4u
Tack Tack
Theorem 3.2 establishes that under proper initialization (k = 1/ //m,), when 3-effective attack ex- ists, Algorithm I finds a e-suboptimal attack vector in O /e) iteration. We next study convergence of Algorithm 2 under the following distributional assumption.
Assumption 3.3. Samples (x, y) are drawn i.i.d. from an unknown joint distribution D that satisfies:
|x|| s R with probability 1.
There exists a unit norn vector v. E Rd, ||v. = 1, such that for (x. y) ~ D, we have with probability 1 that y(v.- x) 22 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 > O. Of course, do not need a non-linear neural network robustly learn predictor under such a distributional assumption. But can we even guarantee robust learnability of neural networks for such simple settings? Nothing known as far as we know. We note that even for 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., 2018). The following theorem establishes that adversarial training can efficiently find a network with small 8-robust error.
Theorem 3.4 (Convergence of Algorithm 2). For any <> O, in at most Tex S 64 (1 iterations, Algorithm 2 with step-size The moaekfops finds iterate (y-1)aa²2
that, in expectation over ((x, TT satisfies EB(W,) S for any B 2 2v(1 a)m.m/m pro- vided that for all E [T]. Mack I 2m]...l and Talk 2 "ura""
A few 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 pa- rameter v is smaller than the distribution margin 7. Furthermore, the iteration complexity increases
Proofs are deferred to the appendix.
4

---

Under review as a conference paper at ICLR 2023
gracefully O(v2/(< -)) the attacks become stronger, i..,, the size of adversarial pertur- bations tends to the margin. Intuitively, as V + O, the attack becomes trivial, and the adversarial training reduces to the standard aon-adversarial training. This is fully captured by results as V + 0, the number attack iterates Tatx goes to zero, and we recover the overall runtime of 2())) in the previous work (Brutzkus et al., 2018; Frei et al., 2021).
Computational Complexity, To guarantee e-suboptimallity in the 3-robust misclassification error, we require Tt. = 2{- iterations of Algorithm 2. Each iteration invokes the PGD attack in Algorithm I, which itself requires Tatk = O /E) gradient updates. Therefore, the overall com- putational cost of adversarial training to achieve e-suboptimality is O (7-1)4, ). Note that Tatk is purely computational requirement, and the statistical complexity of adversarial training is fully cap- tured by Ti.. Remarkably, there is only a mild O(>² ((>->/()) statistical overhead for B-robustness,
and the computational cost increases gracefully by a multiplicative factor of O
( (リ-1)zz)
Learning Robust Linear Halfspaces. When a 1, the Leaky ReLU activation equals the iden- tity map, and the network reduces to linear predictor. In this case, we retrieve strong robust generalization guarantees for learning halfspaccs, 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/ym, w 1/% and n== (R + = For any 0. in at most
128(R++2) Ter < (5-1)er iterations, Algorithm 2 finds an iterate т, that in expectation over {(x,, (ek,,b))e ve)
satisfies emb emb (W,) < 2e, provided that for all & E [T], Matk < || and Tark 2 Su?
Dependence on the Norm of Iterates. The iteration complexity of Algorithm 1 is inversely proportional to the learning rate Matk. and therefore increases with Well?. Thus, when cal- upper bound on the
culating the overall computational complexity, norm of the iterates. As we show in Equation (6) in the appendix, it holds for all iterates that [[W++1ll I < [| + 3m.st. Therefore, if we K 1//mm and 2² = 3/ (R + v)², we have the following worst-case weight-independent bound on the overall computational cost:
needs to compute
8y
Ter
81 Well
Ter 8v2 (w² 31), - 1))
T
MatKC
t=1
t=1
t=1
Tuc
24v2t
12v2T2
196608v2 (R v)2
$
RR + 11}e
(R + v)ze
( aa
Therefore, the worst-case overall computational cost of order O(() 90 We note again that this cost is purely computational the statistical complexity is still in the order of O -))=
Adversarial Robustness for any 3. As we discussed earlier, as 3 + 0, the 3-robust error tends the robust error, i.e., Eg (W) Exob (W). Although Theorem 3.4 does not hold for / (except for the linear case discussed above), it is possible to guarantee robust generalization with arbitrarily small 3, as stated in the following corollary.
B Corollary 3.6. For any desirable 3 > 0. let 2m
For any >> O, in at most Ter S (1-(1- ((aaa iterations, Algorithm with step-size nu. < "P[H40) finds an iterate (y-D)aa2e
7 that, expectation over ((x,, Mc)) T= satisfies (W(W)) S 2e provided that for all E [T],
())) and Tack 2 32 F.
2(1-a) =
Mack S 3I..
3.1 PROOF SKETCH
In this section, we highlight the key ideas and insights based our analysis, and give sketch of the proof of the main result. Using Definition 3.1, the proof Theorem 3.4 crucially depends on the following two facts. First, whenever there exists a 3-effective attack, Algorithm will efficiently find a sufficiently good attack (in the sense of Theorem 3.2). Second, as long as the attack size is smaller than the margin 7, robust training is not much harder than standard training. In particular,
5

---

Under review as a conference paper at ICLR 2023
the following Lemma establishes that the expected value of the negative loss derivative eventually becomes arbitrarily small.
Lemma 3.7. For any e > Algorithm with stepsize fer S 5mm 2 =)= finds an iterate T that, in expectation over {(xx, yt) satisfies ED]- (6 (x))) S at most Ter S [Lll]/Wllleaaxy/ iterations.
We remark that the result in Lemma 3.7 holds for any attack algorithm At as long as it respects the condition (x) E (xx) for all x. We are now ready to present the proof of the main result.
Proof of Theorem 3.4. Recall, that 8-robust misclassification error is defined as:
cg -P
min vfw < -3 =P (EA(x))
min vff( < -31Wil))) (E
(Homogeneity of f)
A key step in the proof is to give an upper bound on in terms of the attack returned by PGD. i.e., dar((x). rather than the optimal attack minse (f) 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 can use Markov's inequality to bound the probability above. In order to address the conditional nature of the result in Theorem 3.2, we introduce a truncated version of the negative loss derivative. In particular, for any Note that I implies that (2) 2 - (c) - therefore, Pf $ c) S (() 2 [c) Let 3, == 3|[W>lle, where Wr
let (2) E' (=) I c] be the loss derivative thresholded
the iterate guaranteed by Lemma 3.7. We have
Ea(W: (W = P min vfw, (8) $ - STP -K_ min yfw, yfw,(0)) 2 - - 6EA(x)
3r
dEa(x)
ED
- B. (minse yfaeeax())WwwW..u. vfw- (0))
(Markov's inequality)
- (-
< 2
-h min y/w. (6))
(-6 2- (=) 1/2 2 20)
bEA(x)
Given W, for any (x,y)= D. one of the two following cases can happen:
There exists a B-effective attack. In this case, by Definition 3.1. it holds that minsea(x) yfw, (ō) S -BllWlll
- Therefore, by definition of the truncated nega- tive loss derivative, it also holds that -l,, (minsea(s) yfw, (6)) -(((minseA(s) ufw, (0)) Now, using Theorem 3.2, we get that
402
L.
min yfw. S 22 (6.LK (x)) + Taux SEA(X)
(3)
2. There does not exist a 3-effective attack. In this case, by Definition 3.1, it holds that minsea(x) yfw. (6) > W = -3, Therefore, by definition of the truncated nega- tive loss derivative, also holds that -f'. (minsea(s) yfw. (f)) O, which is trivially bounded by the upper bound in the first case above, given by Equation (3).
Putting back the above cases the upper bound on the 3-robust error, we arrive at:
4v2
4u2
5 (W+) < 3Epl-L(yywv (6acx (x))xxxx)))))))))) +
Tark 2
2
where the first inequality follows from Theorem 3.2, the second inequality follows from Lemma 3.7 given the proper choice of Tt., and the final inequality holds by setting Tacx 2
8
EMPIRICAL RESULTS
Adversarial training is widely used in training robust models and has been shown to be fairly effec- tive in practice. The goal of this section is not to attest or reproduce previous empirical findings. Instead, since the focus in this paper is on the theoretical analysis of adversarial training in non- linear networks, the goal of this section is merely to empirically study the effect of using reflected loss in Algorithm 1.

---

Under review as a conference paper at ICLR 2023
-russ Enerapy
Refieete Cross Enirogy
Number of Outern Araaoka
Number Octmall
Top 10 Attoks, Sorted by the Cornsponding Lose
Top 100 Attoks Sorted by Cormesoncing Loss
Top 1000 Attokss Sorted by the Comnoponcing Loss
Figure 2: Number of the top-k attack vectors that optimal, i.e., can induce label flip, for the cross entropy loss (blue) and the reflected version (red), for different values of k: Left: = 10, Middle: k 100, and Right: k = 1000.
The experimental results are organized as follows. First, in Sec. 4.1, we compare the optimal attacks found by a grid search on the surrogate loss and its reflected version. In Sec. 4.2, we empirically study adversarial training with reflected loss the binary classification setting. Finally, in Sec. 4.3, we generalize the reflected loss, which is key to our theoretical analysis, to multi-class classification setting. We then report the results on the CIFAR-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, I] and
1. We focus the simplest non-trivial function, i.c., the identity mapping, given by f(x) = x. Obviously, f correctly assigns x to the first class because the first dimension is larger than the others. Also, perturbation of the form 5 [-0.501, 0.5, 0] with ||o|| = 0.7078 can flip the label, since f = [2.499, 2.5, incorrectly predicts the second class.
We restrict the attack to the set {6 E (-0.51, +0.51) || S 0.7078). We look at every possible attack vector on a grid of size 800 x 800 x 800. We then sort these vectors 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 label flip. We take this as a measure of how effective is the corresponding loss maximization problem finding a good attack vector. As we 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 and 1 from the MNIST dataset (LeCun et al., 1998), which provides a (almost) separable distribution, consistent with our theoretical setup. The dataset contains 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 adversar- ially 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 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 et al. (2017), and the PGD attack with te constraint (PGD-2) and fo constraint (PGD-oe). For each of these attack strategies, corresponding approach that involves reflecting the surrogate loss we denote the resulting methods as R-FGSM, R-BIM, R-PGD-2, and R-PGD-30. respectively. The perturbation size for FGSM, PGD-co, and BIM (and their corresponding reflected version) is set to v = 0.1. For PGD-2 and R- PGD-2, we let larger perturbation size of v 2 as recommended in the Adversarial ML Tutorial.
have
In the inner-loop, if the attack is iterative, we use a step-decay scheduler with initial step-size of 10, which decreases the step-size every 10 steps by a multiplicative factor of 0.2. Table 1, we report the standard test accuracy 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.

---

Under review as a conference paper at ICLR 2023
Atk.
FGSM
R-FGSM
PGD-00
R-PGD-co
BIM
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)-2
0.004
0.004
0.005
0.005
0.005
0.005
0.003
0.05
R-PGD-o0
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-PGID-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-x,, R-PGD-cc, PGD-2, R-PGD-2), for different attack benchmarks (FGSM, R-FGSM, PGD-oc, R-PGD-oo, BIM, R- R-BIM, PGD-2, and R-PGD-2).
Analysis. We make the following observations in Table 1. First, reflecting the loss has mini- mal effect on FGSM and BIM attacks, in terms of robust test accuracy of the trained models. In particular, the columns and 2 (similarly columns 5 and 6) are identical up to the third decimal point.
Second, in PGD-2 attacks, reflecting the loss generally yields stronger attack note the striking differences in the last two columns between PGD-2 and R-PGD-2. We observe a milder trend for PGD-co attacks, where R-PGD-co attacks turns to be only slightly stronger, except for the standard training setting where reflecting the loss has a huge impact on the robust error.
Third, would like to remark on the performance of adversarially trained models. We can 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-00 and R-PGD-2), respectively.
Finally, it is notable that even though PGD-2 and PGD-X: 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 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 an attack that minimizes the log- likeeiod of the correct class. Using the reflected loss, instead, we aim at maxi- mizing the log-likelihood of the wrong class. multiclass classification scenario, there are mul- tiple such wrong classes. Therefore, be targeted in the attack phase? Here, we focus on the most natural choice: we target the wrong class with the highest log-likelihood. This greedy approach is easy implement, and has minimal computational overhead over standard adversarial training.
important design question is which wrong class should
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 with the logits for the most likely wrong class, the greedy approach fails. In partieular, consider the following 3-class classification problem in R22. Let fw = Wx, where W [201, C1, 10cg] E R332 Here, e; denotes the i-th standard basis. Consider the point x []. Clearly, class and have the highest and the smallest likelihoods, respectively. Given a perturbation size ||x 1xx'-x/ the likelihood the second class will never dominate that of the first class:
x|| S 0.3,
wT (x + 8) 2e_ (x + 8) 2zx1 51) (x1 + 51) of (x + 8) W (x+
where the inequality follows by using the fact that æ1 = and [61 < 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 8 = (0.0.3). the point x' = [1, 0.3) will be assigned to the third class, because w.J x = w x = 2 > w. 1.
We use adversarial training with and without reflected loss (denoted by R-PGD and PGD, respec- tively) to train a PreActResNet (PARN) He et al. (2016) on the CIFAR- dataset Krizhevsky et al. (2009). In the training phase, we conduct experiments for attack size и E {2, 4, 8, 16) /255. We build on the PyTorch implementation in Zhang et al. (2021), and we follow their experimental setup, which is described next. We use SGD optimizer with momentum parameter of 0.9 and weight decay parameter of x 10-4, 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
8

---

Under review as a conference paper at ICLR 2023
Attack Size
2/255
Steps =
2
Steps
Steps = 16
Steps = 32
RA
SA
RA
SA
RA
SA
RA
SAA
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 Size
4/255
PGD R-PGD
17.764
90.748
30.344
88.
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
8/255
PGD R-PGD
20.064
90.478
34.21
87.746
48.916
78.402
48 15.936
77.920
20.1
90.564
34.19
87.852
48.792
78.382
48.828
77.982
Attack Size
16/255
PGD R-PGD
16.19
85.908
21.524
86.816
48. 722
68.37
45.292
58.526
15.986
89.708
21.362
86.83
48.742
68.456
14.778
58.486
Table 2: Robust test accuracy (RA) of adversarially trained models with and without reflecting the loss, for dif- ferent values of the attack size y E {2, 4, 165/255 and number steps in the attack Steps E {2, 4, 16, 32}. We report the results for test-time attack size V = 8/255; the better performance is highlighted in gray, where the intensity corresponds to difference in performance.
10 epochs and then reduces it back to 0 in the remaining 10 epochs. We report robust test accuracy (RA) of an adversarially-traan trainne model against PGD attacks Madry et al. (2018) (RA-PGD), where we take 50-step PGD with 10 restarts. We report the results for test-time attack size = 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.
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. In 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). Max- imizing the reflected loss then corresponds simple modification enables us to guarantee the convergence of PGD-2 attacks, and yield stronger attacks 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 wrong class seems to provide competitive performance in terms of standard/adwersariaa test error. Is there a simple, principled approach to obtain lower- bound for the misclassification error in the multiclass setting? It would be interesting to explore theoretical and empirical aspects of such possible extensions.
maximizing the likelihood of the wrong class. This
Beyond 3-robustness. The notion of (3-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 an adversarial example if there exists one regardless of whether the attack is 3-effective challenging to establish for itcrative attacks such as PGD, because they can only guarantee getting sufficiently close 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 is an interesting research direction for future work.
not. This is, in particular,
Optimization geometry. In our theoretical results, we focus on PGD-2 attacks, which are based on steepest descent with respect to the l geometry. In experiments, we also provide empirical results for steepest descent attacks with respect to foc geometry (including FGSM and BIM) on the reflected loss. We leave the theoretical analysis of such attacks to future work.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shward SGD learns over- parameterized networks that provably generalize on 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, 32: 10:10866-0084, 2019.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In /EEE symposium security and privacy, pp. 39-57. IEEE, 2017.
Zachary Charles, Shashank Rajput, Stephen Wright, and Dimitris Papailiopoulos. Convergence and margin of adversarial training separable data. arXiv preprint arXiv:1905.09200 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 /52, 2021.
Ruiqi Gao, Tianle Cai, Haochuan Li, Cho-Jui Hsieh, Liwei Wang, and Jason D Lee. Convergence of adversarial training in overparametrized neural networks. Advances in Neural Information Processing Systems, 32:13029-13040 2019.
lan Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference Learning Representations, 2015. URL http:// arxiv. org/ abs 412.6572.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572, 2014.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European conference on computer vision, pp. 630-645. Springer, 2016.
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- learning applied to document recognition. Proceedings of the IEEE, ((11))2228-22221 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 https:/ wpwp/eeeewwww.ee//////// net / forum?iddee ii-.rmmmi--kkKTThThFF0F
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-Dezfoolli Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method to fool deep neural networks. In Proceedings of the IEEE conference on com- puler vision and pattern recognition, pp. 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 Learning Representations, ICLR 2014, 2014.
Yisen Wang. Xingjun Ma, James Bailey, Jinfeng Yi, Bowen Zhou, and Quanquan Gu. On the convergence and robustness of adversarial training. In Kamalika Chaudhuri and Ruslan Salakhut- dinov (eds.), Proceedings of the 36th International Conference of Proceedings of Machine Learning Research, pp. 6586 6595. PMLR, 09-15 Jun 2019. URL https: / ttttps://prrcee proceed i ngs ml press / v97 wang1 91 html.
Machine Learning, volume 97
10

---

Under review as a conference paper at ICLR 2023
Yi Zhang, Orestis Plevrakis, Simon S Du, Xingguo Li, Zhao Song, and Sanjeev Arora. Over- parameterized adversarial training: An analysis overcoming the curse of dimensionality. In NeurIPS, 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:2
2021.
Difan Zou, Spencer Frei, and Quanquan Gu. Provable robustness of adversarial training for learning halfspaccs with noise. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 13002-13011. PMLR, 18-24 Jul 2021. URL https: http://poccciicieecececooooo mlr press/ /ttess/v1199 zou2la html.


Reviews:
[{"review_id": "x-yaFjdz94i", "reviewer": "Reviewer_zEHs", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes to reflect the surrogate loss about the origin for the inner maximization of adversarial training. This paper proves convergence guarantees for the PGD attack under a margin separability assumption on such a surrogate loss with two-layer neural networks with the Leaky ReLU activation function.", "summary_of_the_review": "This paper proves convergence guarantees for the PGD attack under a linearly separability assumption with two-layer neural networks. Although it's technique was impressive, I'm not sure what the point of robustness of neural networks models for linearly separable data is.", "strength_and_weaknesses": "Strengths :\n\n- The paper is well written.\n\n- A novel technique was used for proof.\n\nWeaknesses :\n\n- (critical) It considers two-layer neural networks with the Leaky ReLU activation function under a linearly separability assumption. But what is the point of robustness of neural networks models for linearly separable data? Since some works already showed robust generalization error guarantees for adversarially trained linear models under a linearly separability assumption, I wonder what are the new contributions.\n\n- The results of the experiment are not significantly good.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "uf5RS_-JmB", "reviewer": "Reviewer_6erv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the robust adversarial learning problem for a binary classification task, where the standard adversary's logistic loss function is reflected around the origin. Specifically, the classifier is chosen to be a one-hidden layer neural network with leaky-ReLU activation, and the two classes are assumed to be linearly separable. Under these assumptions, the paper proves a convergence guarantee for the projected gradient descent optimization algorithm. The paper presents some numerical results on binary and multi-class classification problems to support the proposed bi-level adversarial training approach and the shown convergence results. ", "summary_of_the_review": "This paper proposes a new approach to robust adversarial training by proposing a novel bi-level optimization problem based on reflecting the maximization surrogate loss function around the origin. While the analysis is restricted to binary classification problems with linearly separable classes, I think the paper contributes interesting ideas for analyzing adversarial training problems.  ", "strength_and_weaknesses": "Strengths:\n\n1) The paper is well-written and the presentation is satisfactory.\n\n2) The idea of reflecting the surrogate logistic loss around the origin sounds highly interesting to me, since it resolves the non-concavity of the surrogate loss in the adversary's maximization problem. The idea seems to be potentially useful for other theoretical analyses of adversarial training problems as well. \n\nWeaknesses:\n\n1) The paper's convergence analysis is based on two relatively strong assumptions: 1) the analysis targets a binary classification problem and its extension to multi-class classification problems looks challenging, 2) the two classes are supposed to be linearly separable.\n\n2) While I very much like the reflection idea for the inner maximization problem, this change leads to a different bi-level optimization problem from the standard min-max adversarial training problem. Therefore, while the paper's introduction sets the goal of understanding the convergence properties of robust adversarial training, the proposed framework deviates from standard robust training approaches. \nI am wondering what the results of the paper could imply about the convergence of standard min-max adversarial training. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "sZiCYDVJ7Nd", "reviewer": "Reviewer_VXHq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "This paper focuses on convergence analysis of adversarial training for finite-width two-layer Leaky ReLU networks. Convergence guarantees are given for both inner-loop PGD-style adversarial attack (in deterministic form) and end-to-end adversarial training with imperfect attack (in expectation form). To ease the analysis, the framework focuses on binary classification setting with only first-layer weights updatable. Moreover, in the inner-loop attack, authors propose a lower bound of 0-1 loss as the surrogate and the training gradients use the classical binary sigmoid loss as the surrogate. Lastly, the lower bound surrogate loss is demonstrated to be effective in practice (on MNIST, CIFAR-10).", "summary_of_the_review": "Though I got lost in some steps of the proofs, assuming that the proofs are all correct and will be revised clear, and the related work is discussed comprehensively (I'm not working in DL theory so cannot evaluate this aspect), I think the contribution is sufficient, of interest to the community, and worth acceptance - the results further our theoretical understanding of adversarial training.", "strength_and_weaknesses": "Strengths:\n- Strong theoretical guarantees of adversarial training under loose assumptions. Theorem 4 establishes the convergence of adversarial training in terms of a small expected error of large-margin adversarial examples, for finite-width two-layer Leaky-ReLU networks. These results seem to be the first of this kind. Technically, the proof relies on the monotonicity of gradients - a specific mathematical property of the well-designed surrogate loss along with telescoping cancellation, which is not straightforward.\n\n- The paper also establishes the deterministic convergence guarantee for adversarial training.\n\n- The proposed lower bound surrogate loss for the adversarial attack is effective in practice which may of independent interests.\n\n- The writing quality in the main text is great and it is easy to follow.\n\nWeaknesses:\n- The analysis is limited in the following aspects: (1) The analyzed two-layer neural network does not allow the weight evolvement in the second-layer, which is different from the adversarial training practice. (2) The latent assumption of linear separation (second point of Asumption 3.3) seems strong. (3) Extension of the analysis to multi-class settings may be hard.\n\n- The proof can be made more rigorous. For instance, I got lost in the following places:\n\n  1. Proof of Thm 3.2: Let $G := ||W||_F$ and $\\kappa \\sqrt m ||W||_F =: G$ seem to be contradicting.\n  2. Proof of Thm 3.2, page 13 upper part: how does average case guarantee $\\frac{1}{T} \\sum_{t=1}^T -\\ell_- (yf_W(\\delta_t)) \\le ...$ lead to single instance guarantee $-\\ell_-(yf_W(\\delta_{att})) \\le ...$? From the bottom of page 13, it seems to be because $-\\ell_-(yf_W(\\delta_{att})) = \\min_{t\\in[T]} -\\ell_-(yf_W(\\delta_t))$. However, why is this guaranteed? Since it is a project GD, when the step size is sufficiently small I can see it holds, but does it hold generally?\n  3. Proof of Lemma 3.7, page 14: why is it an equality in $y_t \\sum_{r=1}^m \\langle a_r \\sigma'(w_r \\cdot \\delta)\\delta, \\frac{1}{\\sqrt m} \\mathrm{sgn}(a_r)v_* \\rangle = \\frac{\\kappa}{\\sqrt m} \\sum_{r=1}^m \\sigma'(w_r\\cdot \\delta) y_t\\langle \\delta, v_*\\rangle$? We only know $||a||_{\\infty} \\le \\kappa$ but does it lead to $a_r = \\kappa$ for any $r$?\n  4. Proof of Lemma 3.7, bottom of page 15: how does $\\tau \\le ...$ connect to $T \\le ...$? If I understand correctly, we need $T \\ge \\lceil \\tau \\rceil + 1$ to lead to contradiction. But here, RHS of $\\tau \\le ...$ seems to be squared which may not imply $T \\ge \\lceil \\tau \\rceil + 1$.\n\n- How does this convergence-guaranteed adversarial training of two-layer DNN compare to exact-convex-opt-solving-based adversarial training (e.g., [1])?\n\n[1] Bai, Yatong, Tanmay Gautam, and Somayeh Sojoudi. \"Efficient global optimization of two-layer relu networks: Quadratic-time algorithms and adversarial training.\" arXiv preprint arXiv:2201.01965 (2022).\n\n\nMinor:\n1. After Definition 3.1, \"in terms of the and the negated loss derivative\": missing noun\n2. After Theorem 3.2, $O(\\beta^2 / \\epsilon)$ iteration may need further justification\n3. Section 4.1 may be moved to appendix to gain space for proof sketching of Thm. 3.2 and Lemma 3.7\n4. Table 2's result is hard to parse. Why larger attack steps for RA columns can lead to significantly larger robust accuracy? Also, what does SA mean? When attach size $\\nu$ is specified in the table, how is it different from caption of Table 2 which says $\\nu = 8/255$?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Biq5efgjoEB", "reviewer": "Reviewer_KemA", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper analyzes theoretically the robustness of adversarial training of two layer neural network.\nThe analysis is done on a linearly separable dataset through slightly modifying the objective of PGD attacks.\nExperimental analysis of the proposed modification of PGD attacks are carried our on small scale problems.", "summary_of_the_review": "My main concerns about this work are: (1) The limited experimental analysis. (2) The mismatch between the theoretical results and the experimental setup. (3) The usefulness of the theoretical results under the stated assumptions. \nPlease refer to the review for more details.", "strength_and_weaknesses": "The main strength of this paper is the theoretical analysis presented in section 3. It is very useful to analyze the convergence of such popular approach in building robust models to allow theoretically supported robustness enhancements. However, there are key concerns about the effectiveness of this work:\n\n- First, the experimental results are very limited to very small scale problems. The argument of this work would have been much stronger if it was demonstrated on standard robustness benchmarks showing robustness improvements.\n\n- The analysis presented in sections 2 and 3 assumes Leaky ReLU activation function, while the experiments are carried out on ReLU-based networks. However, substituting $\\alpha \\rightarrow 0$ in Theorem 3.4 would yield $T_{tr} \\leq \\infty$. That is, if I understood correctly, Theorem 3.4 does not bring useful conclusions about adversarial training  under the experimental setup even when using a two-layer network. Please correct me if I am missing something in the previous argument.\n\n- The assumptions in the theoretical analysis limit the usefulness of the results. For instance, why is the weights of the second linear layer, $i.e.$ are kept fixed? In Assumption 3.3, the input space is assumed to be bounded. However, $R$ could be extremely large in reality $e.g. R=(255)\\sqrt{d}$ for images where $d$ is the number of pixels. This would result in an extremely small learning rate as per Theorem 3.4.\n\nMinor concerns:\n\n- The writing of the paper can be further improved. There are few typos such as: \"in terms of the and...\" in page 4. \n\n- Table 1 is hard to read. Please consider highlighting main number in the table with stating the main message in the caption.\n\n- The proof sketch in section 3.1 seems a bit disconnected from the rest of the paper. Please consider moving it to the appendix.\n\n- The main result of this work (Theorem 3.4) is about the convergence guarantees of adversarial training. Please consider reflecting that into the title as robustness guarantees usually refers to some sort of certified robustness.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject