Finding Actual Descent Directions for Adversarial Training
Authors: Fabian Latorre
Igor Krawczuk
Leello Tadesse Dadi
Thomas Pethick
Volkan Cevher
Venue: ICLR 2023 poster (2023)
Keywords: Adversarial Training
Adversarial Examples
non-convex optimization
robustness

Abstract: Adversarial Training using a strong first-order adversary (PGD) is the gold standard for training Deep Neural Networks that are robust to adversarial examples. We show that, contrary to the general understanding of the method, the gradient at an optimal adversarial example may increase, rather than decrease, the adversarially robust loss. This holds independently of the learning rate. More precisely, we provide a counterexample to a corollary of Danskin's Theorem presented in the seminal paper of Madry et al. (2018) which states that a solution of the inner maximization problem can yield a descent direction for the adversarially robust loss. Based on a correct interpretation of Danskin's Theorem, we propose Danskin's Descent Direction (DDi) and we verify experimentally that it provides better directions than those obtained by a PGD adversary. Using the CIFAR10 dataset we further provide a real world example showing that our method achieves a steeper increase in robustness levels in the early stages of training, and is more stable than the PGD baseline. As a limitation, PGD training of ReLU+BatchNorm networks still performs better, but current theory is unable to explain this.


Published as a conference paper at ICLR 2023
FINDING ACTUAL DESCENT DIRECTIONS FOR ADVER- SARIAL TRAINING
Fabian Latorre', Igor Krawezuk", Leello Dadi", Thomas Pethick and Volkan Cevher EPFL, Switzerland
firstname, lastname@epll...
ABSTRACT
Adversarial Training using strong first-order adversary (PGD) is the gold stan- dard for training Deep Neural Networks that are robust to adversarial examples. We show that, contrary to the general understanding of the method, the gradient at optimal adversarial example may increase, rather than decrease, the adversari- ally robust loss. This holds independently of the learning rate. More precisely, we provide counterexample to corollary of Danskin's Theorem presented in the seminal paper of Madry et al. (2018) which states that a solution of the inner max- imization problem can yield descent direction for the adversarially robust loss. Based on a correct interpretation of Danskin's Theorem, we propose Danskin's ss Descent Direction (DDi) and we verify experimentally that it provides better di- rections than those obtained by a PGD adversary. Using the CIFARI0 dataset we further provide a real world example showing that our method achieves a steeper increase in robustness levels in the early training stages of amooth-activation net- works without BatchNorm, and is more stable than the PGD baseline. As a lim- itation, PGD training of ReLU+BatchNorm networks still performs better, but current theory is unable to explain this.
INTRODUCTION
Adversarial Training (AT) (Goodiellow et al. 2013 Madry et al. 2018) has become the de-facto algorithm used train Neural Networks that robust to adversarial examples (Szegedy et al., 2014). Variations of AT together with data augmentation yield the best-performing models in public benchmarks (Croce al., 2020)). Despite lacking optimality guarantees for the inner-maximization problem, the simplicity and performance of AT are enough reasons to embrace its heuristic nature.
From an optimization perspective, the consensus is that AT is sound algorithm: based on Dan- skin's Theorem, Madry et al. (2018, Corollary C.2) posit that by finding maximizer of the inner non-concave maximization problem. i.e., an optimal adversarial example, one can obtain a descent direction for the adversarially robust loss. What if this is not true? are we potentially overlooking issues in its algorithmic framework?
As mentioned in (Dong et al., 2020, Section 2.3), Corollary C.2 in Madry et al. (2018) can be consid- ered the theoretical optimization foundation of the non-convex non-concave min-max optimization algorithms that we now collectively refer to Adversarial Training. It justifies the two-stage struc- ture of the training loop: first we find one approximately optimal adversarial example and then we update the model using the gradient (with respect to the model parameters) at the perturbed input.
The only drawbacks of a first-order adversary seem to be its computational complexity and its ap- proximate suboptimal solver nature. Ignoring the computational complexity issue, suppose we have access to a theoretical oracle that provides a single solution of the onner-mxximizttin problem. In such idealized setting, we safely assume AT is decreasing the adversarially robust loss the data sample? According to the aforementioned theoretical results, would appear so.
In this work, scrutinize the optimization paradigm which Adversarial Training (AT) has been founded, and we posit that finding multiple solutions of the innermmaximization problem is necessary
Thheee authors contributed equally this work

---

Published as a conference paper at ICLR 2023
POD
F5D
Tilroe
Inreato
(a)
(b)
(C)
Figure 1:
(a) and (bc comparison of our method (DDi) and the aaaale-dvvesarrll-eeeeeee
method
(PGD) on synthetic min-max problem. Using a single example may increase the robust loss. DDi
computes 10 examples and can avoid this. (c): similar improvement over PGD training shown on
CIFARIO, where DDi with 10 examples speeds up convergence. More details in Section 5
find good descent directions of the adversarially robust loss. In doing so, we hope improve our understanding of the non-convex/non-connen min-max optimization problem that underlies the Adversarial Training methodology, and potentially improving its performance.
Our contributions: We present two counterexamples to MolMady et al. (2018, Corollary C.2), the mo- tivation behind AT. They show that using the gradient (with respect to the parameters the model) evaluated at single solution of the inner-maximization problem, can increase the robust loss, i.e., it can harm the robustness of the model. In particular, in coountreexaaple 2 many descent directions exist, but they cannot be found if we only compute single solution of the maner-maimization prob- lem. In in(Section 2) we explain that the flaw in the proof due to a misunderstanding of the directional derivative notion that is used in the original work of Danskin 1966).
Based on our findings, we propose Danskin's 's Descent Direction (DDi, Algorithm I). aims to overcome the problems of the single adversarial example paradigm of AT by exploiting multiple adversarial examples, obtaining better update directions for the network. For a data-label pair, DDi finds the steepest descent direction for the robust loss, assuming that (1) there exists finite number of solutions of the imner-maxmizattin problem and (ii) they can be found with first-order methods.
In Section we verify experimentally that: (i) unrealistic assume a unique solution of the imnermmxiiiiation problem, hence making a case for our method DDi, (ii) our method can achieve more stable descent dynamics than the vanilla AT method synthetic scenarions and (iid) on the CIFAR10 dataset DDi is more stable and achieves higher robustness levels in the early stages of traning, compared with a PGD adversary of equivalent complexity. This is observed in a setting where the conditions of Danskin's 's Theorem holds, i.e., using differentiable activation functions and removing BatchNorm. As limitation, PGD training of Rel.U+ BattchhNoor networks still performs better, but there is theory explaining this. The code to reproduce results will be available at https: http//tttttt wiggtuu.b.... cww/coonsss....... LIONS EPFL/ddi at
Remark. The fact that (adrr et al. 2018 Corollary C.2) is false, might be well-known in the optimization field. In the convex setting it corresponds to the common knowledge that a negative subgradient of non-smooth convex function might not be descent direction c.f., (Boyd) 2014
Section 2.1) 2). However, we helieve this is not well-known in the AT community given that (7) its practical implications i.e., methods deriving steeper descent updates using multiple adversarial examples, have not been previously introduced, and (ii) the results in Madry et al. (2018) have been central in the development of AT. Hence, our contribution can be understood as raising awareness about the issue, and demonstrating its practical implications for AT.
2 A COUNTEREXAMPLE TO MADRY ET AL. (2018 COROLLARY C.2)
Preliminaries. Let 0 E Rd be the parameters of a model, (x. y) ~ D a data-label distribution, perturbation in a compact set Sn and L a loss function. The optimization objective of AT is:
min p(0), where p(0) == B(za))
max T( x +5, BES0
(1)
2

---

and Vog(O, 8) is continuous on Published as a conference paper at ICLR 2023
In this setting p(0) is referred to the adversarial loss robust loss. In order to optimize Eq. via iterative first-order methods, we need access to an stochastic gradient of the adversarial loss p or at least, the weaker notion of stochastic descent direction i.c., a direction along which the function
1 k = 1: >
((0) = max $
g(0,5)
I(0, xs 66,
+
decreases in value. We have collected the perturbations d; E So on the batch {(T), ) as the columns of matrix = jō1...., ōu] E S == St which is also a compact set. To obtain a descent direction for partial maximization functions like & we resort to Danskin's 's Theorem:
Theorem 1 (Danskin (1966)). Let S be a compact topological space, and let g R x S be continuous function such that g(,6) is differentiable for all
R x S. Let
(0) = max g(0, 8), aES
(0) = arg max g(f,6)
(3)
BES
Let Y E Ie with 11 = an arbitrary unit vector. The directional derivative (20(0) of á in the direction at the point 0 exists, and is given by the formula
Dy0(0)=
max (% Veg(0, 8))
(4)
(e)
Remark. 7 * is called descent direction of & at 0 if and only if D20(0) < 0. i.c., if the directional derivative strictly negative.
Corollary 1 is an equivalent rephrasing of Madry et al. 20118 Corollary C.2.), and was originally claimed to be a consequence of Theorem I] Unfortunately counterexample shows that the corollary is false. As 'Theorem (Danskin's Theorem) is true, this means that there is some mistake in the proof of the corollary provided in Madry et al. (2018).
Corollary 1. Let 8" E (B). If (G 5*) + 0, then it is a descent direction for & at 6 Counterexample 1. Let S = [-1,1] 1] and g(0, clearly hold in this case, and
06. The conditions of Danskin's 's theorem
(00) = max 86 = |0). 6,1-
(5)
Note that 0 0, we have S* [1,, Choosing 8 = e (0) we have that g(0, 1)
and so V (0, 1 f 0. Hence, Corollary 1 would imply that -1 is a descent direction for o(0) [... However. 8 = 0 is global minimizer of the absolute value function, which means that there exists no descent direction. This is contradiction.
To cast more clarity on why Corollary ilis false, we explain what the mistake in the proof provided in Madry et al. (2018). The main issue is the definition of the directional derivative, concept in multivariable calculus that is defined in slightly different ways in the literature.
Definition 1. Let Φ IRd + R. For a nonzero vector E IRd, the one-sided directional derivative of o in the direction 7 at the point @ defined as the one-sided limit:
@(0 + 17) (0))
D D,0(0)= = lim l-2-
11/7112
The Iwo-sided directional derivative is defined as the two-sided limit:
6(0 + try - x(0)
D20(0) = lim C-0
Unfortunately, it is not always clear which one of the two notions is meant when the term directional derivative is used. Indeed, as our notation suggests, the one-sided definition [Eq. (6) the one used
in the statement of Danskin's 's Theorem (Danskin] 1966). However, the proof Corolllyyyy provided in Madry et al. (2018) mistakenly assumes the two-sided definition [qq (7) and inadvertently uses the following property that holds for (0) (Eq. (7)) but not for D.,(() (6)):
Lemma 1. For the two-sided directional derivative definition 7 it holds that -D,0(0) =
D_,,0(0) provided that D., exists. In particular, D(0) > 0 then D_,o(0) < 0. However this is not true for the one-sided directional derivative (6), as the example ((0) = 10) at = shows (both directional derivatives strictly positive).
3

---

Published as a conference paper at ICLR 2023
We provide proof of this fact infAppediix El The (flawed) proof of Corollary 1 provided in Madry et al. 2018) starts by noting that for solution 8 of the inner-maximization problem, the directional
derivative in the direction 7 = Vog(O, 8) is positive, as implied by Danskin's Theorem:
D,
max (r. Veg(O. 0. 6)) 2 (Veg(0,5), Vog(O, 8)) = V oog( 0, 8) > 0 6ES*
(8)
assuming that V (0g 5) is non-zero. The mistake in the proof lies in concluding that D ( < 0. Following Lemma this property does not hold for the one-sided directional derivative definition Eq. (6)
the one used in Danskin's Theorem.
A COUNTEREXAMPLI AT A POINT THAT NOT LOCALLY OPTIMAL
The question remains whether slightly modified version of Corollary holds true: it might be the case that by adding some mild assumption, we exclude all possible counterexamples. In the particular case of [coutereexampee 1 0 0 is a local optimum of the function 6(0) = 0). At such points, descent directions do not exist. However, in the trajectory of an iterative optimization algorithm we are mostly concerned with non-locally-optimal points. Hence, explore whether adding the assumption that is not locally optimal can make Corollary true. Unfortunately, we will show that this is not the case.
To this end we construct a family of counterexamples to Corollary I with the following properties: point 0 (that is, 0 is not locally optimal) and (ii), it does coincide with (0, 6). for any optimal 5 E S* (0). Moreover, all the directions -egg(A, 6) are in fact ascent directions i.e., they lead to an increase in the function o(0).
(i) there exists a descent direction
Counterexample 2. Let S = [0, 1] and let That is, u and v form an obtuse angle. Let
E IR2 be unit vectors such that -1 < {u, v) < 0.
g(0, 5) 8(0,, u) + () v) + 8(5 -1)
Clearly, the function satisfiey all conditions of Theorem Ar O, we have that S* arg max 8 1) {0, 1}. Ar 5 0 have Veg(O, (),00
and at 8 = We compute the value of the directional derivatives in the
Vo(0,
have (og 1) = Vo u) negative direction of such vectors. According to Danskin's 's Theorem we have
D (0) max (-v, Veg(O, ā)) $E(0.1)
(-v, u}) 2 - -wu, u) > 0 (10)
where- -(v, u) 0 holds by construction. Analogously, D-,o(0) > 0. This means that all such directions are ascent directions. However, for the direction y = - (u v) we have
D=0(() x max (-(u + v). Veg(O,
6E(0.1)
(11)
= max((-2) (-u - v, u), (-u - v. u}) = -1 (u, v) < 0
where the last inequality also follows by construction. Hence, - -(u + v) is descent direction.
As counterexample 2 shows, Adversarial Training has the following problem: even if we are able to compute one solution of the inner-maxee maximizaaiiniio problem 3 E S can be the case that moving the direction - Vegg( (0, 5) increases the robust training loss i.e., the classifier becomes less, rather than more, robust. This can happen at any stage, independently of the local optimality of 0.
For non-locally-optimal 0 IRd, the construction of the counterexamples relies on the following: if for any gradient computed at one inner-max solution, there exist another gradient (at different inner-max solution) forming an obtuse angle, then no single inner-max solution yields a descent direction. Consequently, it suffices to ensure that for any gradient that can be found by solving the inner problem, there exists another one that has negative inner product with it. Precisely, our counterexample 2 is carefully crafted so that this property holds.
4 DANSKIN'S DESCENT DIRECTION
Danskin's Theorem implies that the directional derivative depends on all the solutions of the inner- max problem S* (0) c.f., Eq.. (4) One possible issue in Adversarial Training is relying on single
4

---

Published as a conference paper at ICLR 2023
solution, as it does not necessarily lead to descent direction c.f. counterexample 2 To fix this, we design an algorithm that uses multiple adversarial perturbations per data sample. In theory, we can obtain the steepest descent direction for the robust loss batch {(z,, y:) i 1, ................................ k) by solving the following min-max problem:
1 K. Σ
>* E arg min max (7: Vog(0,5)), 000,0) >0lli::==
I(0, xi 8,, Mk)
(12)
On the one hand, if the set of maximizers (0) is infinite, Eq. (12) would be out of reach for computationally tractable methods. On the other hand, the solution is trivial if there is a single maximizer, but we verify experimentally in Seccion 5hth such assumption is wrong in practice. In conclusion, a compromise has to be made in order devise an tractable algorithm that is relevant in practical scenarios. First, we assume that the set of optimal adversarial perturbations is finite:
(+) = arg max g(0, 6) = S (0) -
8(m)),
m 2 1, m E Z
(13)
EES
Under such assumption, it is possible to compute the steepest descent direction in Eq. (12) efficiently.
Theorem 2. Let A be the m-dimensional simplex i.e,, a 2 0, Ex= 0 = 1. Suppose
that (*)() = Sn ...()).... and denote by Veg(O, S (6)) the matrix with columns Veg(0, (()) for i = , m. As long as is not a local minimizer of the robust loss 6(0) =
maxies g(0, 6), then the steepest descent direction of & at 0 can be computed as:
Veg(O, Sth (0))
at E arg mrgmin (og(), "EAm
(14)
Vog St (0))a=
We now relax our initial finiteness assumption Eqq (13) as it might not hold in practice. We show that it might suffice to approximate the (possibly infinite) set of maximizers (*))) with a finite set S (0). If the direction 7 defined in Eq. (14) satisfies an additional inequality involving the finite set S (0), it will be certified descent direction.
We present the proof of Theorem 2 in Appendix C
Theorem 3. Suppose that Vog(O. 8) is I.-Lipschitz as function of ö, i.e., 1[Vog(0, 8)
Vog(O, 5')l22 S L|lō 8' 122- Let (+) be the set of solutions of the inner maximization prob- lem, and let St (0) (8())..., ,..... ..m.)))m)) be a finite set that e-approximates S+) in the following sense: for any E (0) there exists 8(6) E St, (0) such that ||ō 860112 S c. Let 7 be as in Eq. (14) If (o) Vog(O, 0)) < Lc then y is a descent direction for e at O.
The Lipschitz gradient assumption in Theorem 3 is standard in the optimization literature. We provide a proof of Theorem 3 in AApendix D This results motivate Danskin's 's Descent Direction (Alorritmm 1J. We assume an oracle providing a finite set of adversarial perturbations S; (0) that satifies the approximation assumption in Theorem 3 In particular, this does not require solving the maner-maximizztion problem to optimality. which is out of reach for computationally tractable methods and requires expensive branch-and bound or MIP techniques (Zhang et al.) 2022; Tieng et al. 20119 Palma et al., 2021 : which corresponds to Line of Algorithm
Wang et al., 2021). Given S,, we compute X as in Eq. (14) the values of L. and in Theorem 3 are not available (they might be hard to compute), we cannot certify that 7* is a descent direction. However, note that given a set of adversarial examples (0), ()),) y* is still the best choice as it ensures we improve the loss on all elements of S (0).
The optimization problem defining a* and 7- can be solved to arbitrary accuracy efficiently: It corresponds to the minimization of a smooth objective subject to the convex constraint E A We use the accelerated PGD algorithm proposed in (Parikh et al. 2014 section 4.3) and pair it with the efficient simplex projection algorithm given in Duchi et al. (2008). As the problem is smooth, a fixed step-size choice guarantees convergence. We set it as the inverse of the spectral norm of Veg(O, (*)) Veg(0, (0)) and run the algorithm for fixed number of iterations. Alternatively, one can consider Frank-Wolfe with away steps (Lacoste-Julie & Jaggi 2015)).
In practice, the theoretical oracle algorithm that computes the set S (0) is replaced by heuristics like performing multiple runs of the Fast Gradient Sign Method (FGSM) or Iterative FGSM (Ku- rakin et al.; (007)) (referred as PGD in Madry et al. (2018)). The complexity of an iteration in Algorithm Iddepedds on this choice. In In(eection we explore different choices and how it affects the the performance of the method.
5

---

Published as a conference paper at ICLR 2023
Algorithm Danskin's 's Descent Direction (DDi)
1: Input: Batch size k 2 1, number of adversarial examples m, initial iterate 0g Rd number of iterations T 2 1, step-sizes (Be)t=1-
2: for 0 to T
3: Draw (21 1/1 v1)..................... (It,, y&) from data distribution D
4: g(o. () - Σ L(0, 64, y/)
5:
8(1) ......tm)) g(m) + MAXIMIZEA (0,,5)
b. Using a heuristic like PGD
6:
- [eg )(()) : 1...., m E Rm
7:
a' & MINIMIZE M
To e-suboptimality
8:
Y" + [Ma-lla
Ma.
9:
01+1 + O, + B87
10:
end for
11: return Or
EXPERIMENTS
5.1 EXISTENCE OF MULTIPLE OPTIMAL ADVERSARIAL SOLUTIONS
This section provides evidence that the set of optimal adversarial examples for a given sample not singleton. The hypothesis is tested by using ResNet-18 pretrained on CIFARIO and computing multiple randomly initialized PGD-7 attacks for each image with & 255 & We compute all pairwise
fg-distances between attacks for given image and plot a joint histogram for 10 examples in Fig- ure 2. There is clear separation away from zero for all pairwise distances indicating that the attacks plot histogram for each image. An example is provided in Figure 2] which is corroborated by similar results for other images (see Figure B). We find that the adversarial losses all concentrate with low variance far away from the clean loss. This confirms that all perturbations are in fact both strong and distinct.
indeed distinct in the input space. Additionally,
the adversarial losses
1000
2.1
Dicalty
030
85
300
08
1 d'1
Figure 2: Non-uniqueness of an optimal adversarial perturbation. (left) Pairwise la-distances be- tween PGD-based perturbations are bounded away from zero by large margin, showing that they are distinct. (right) The losses multiple perturbations on the same sample concentrate around value much larger than the clean loss (see Fig. 7 for zoomed-in version).
5.2 EXPLORING THE OPTIMIZATION LANDSCAPE OF DDI AND STANDARD ADVERSARIAL. TRAINING
Having established that there exist multipe adversarial examples, we now show that the gradients computed can exhibit the behaviors discussed in [Section 3] first synthetic example we borrow
from (Orabona 2019 Chapter 6). we consider the function g(f, 5) = 5 (0} + (0, + 1)2) + (1
[0. 1]. As be from Figure la and Figure 1b following a gradient computed at a single example leads to a increase in the objective and an unstable optimization behavior despite the of decaying step-size.
5) [0} (02 1)²) where 0 E R and

---

Published as a conference paper at ICLR 2023
In second synthetic examples, we consider robust binary classification with feed-forward neural network on a synthetic 2-dimensional dataset, trained with batch gradient descent. We observe that during training, after initial phase where all gradients computed at different perturbations point roughly in the same direction, we begin to observe pairs gradients with negative inner- products (see (Figure 3 (left)). That means that following one of those gradients would lead to an increase of the robust loss, as shown by the different optimization behavior (see FFigure 3 (center)). Therefore, the benefits DDi kick in later in training, once the loss has stabilized and the inner- solver starts outputting gradients with negative inner products. Indeed, we see that in the middle of training (iteration 250), DDi finds descent direction of the (linearized) robust objective, whereas all individual gradients lead to an increase.
Sig dogg somaliad diseiken
Figure 3: Count of negative inner products pairs among the 10 gradients computed per (leration(left), corresponding robust loss behavior along optimization (center). At iteration 250, comparison of the direction obtained by DDi and individual gradients, (right)..
5.3 ACCURACY/ROBUSTNERR COMPARISON OF DDI VS ADVERSARIAL TRAINING
We compare the robust test and training error of Adversarial Training vs our proposed method DDi, on the CIFARIO benchmark. As bascline we use x PGD with e = 8/255 a = 2/255, Rinner = 7. We train ResNet18 with SGD, using the settings from Pang al. (2021) Table except for some modifications noted below. This means SGD with hyperparameters 1r= 0.1, momentum=0.0 (not the default 0.9, we explain why below), bat ch_schhssie =ez 128 and weight_decay= 5e We run for 200 epochs, no warmup, decreasing r by factor of 0.1 at 50% and 75% of the epochs.
Satisfying theoretical assumptions: Real world architectures are often not covered by theory while simple toy examples are often far removed from practice. To demonstrate the real world impact of our results, we therefore study a setting where the conditions of Danskin's 's Theorem hold, but which also uses standard building blocks used by practitioners, specifically replacing ReLU with CELU(Barron) 2017). replacing BatchNorm (BN) (loffe & Szegedy) (0155) with GroupNorm (GN) (Wu & He 2018) and removing momentum. This ensures differentiability, removes intra- batch dependencies and ensures each update depends only on the descent direction found at that step respecively. We present more detailed justification in [Appendix B.2 due to space constraints and additionally show an ablation study on the effect of our modifications in (Section 5.3)
Our main results be seen Section 5.3 The robust accuracy of the DDi-trained model increases much more rapidly in the early stages, it increases more after the first drop in the learning rate, and more stable when compared to the baseline. [Section 5.3 also gives evidence that our method has (generally positive or neutral) effects in all settings. Using ReLU instead of CELU re-introduces the characteristic hump in robust accuracy that has led to early stopping becoming standard practice in robust training. It also diminishes the benefit of DDi, but DDi remains on par with PGD in terms of training speed and decays slightly less towards the end of the training. Adding momentum does not help either method in terms of training speed and makes them behave almost identically.
Finally, BN seems to significantly ease the optimisation for both methods, raising overall perfor- mance and amplifying the bump both methods. Here, PGD actually reaches higher maximum robust accuracy and rises faster initially, but then converges to a lower value. This implies that some benefits of DDi remain even outside the setting covered by the theory.
It is worth noting that the early stopping robust accuracy we achieve in ablations approximately matches that reported in Engstrom et al. (209 on resnet50
7

---

Published as a conference paper at ICLR 2023
0.50
DDtt
0.43
0.40
0.1
0.33
0,30
Ioloue 0.3
PGD--Teory
NouSmpooth
0.25
DI0 NucSnooli
DD, NunSuaotia Monn Monn
PCD- NatBooothh
PGD-NiaRannni
PCD NoaSaroolh Mom
175 300
125
Figure 4: (left) Evolution of the robust accuracy on the CIFARIO validation set, using a standard PGD-20 adversary for evaluation and DDi/PGD-7 during training. (right) an ablation testing the effect of adding the elements not covered by theory BeN. back into our setting.
Although these are promising results indicating that DDi can give real world benefits in terms of iterations and reduce the need for early stopping. it is worth asking whether once could get the same benefit with simpler or cheaper method. The final robust accuracies obtained are very close, and the increased convergence rate in terms of steps comes at a more than 10x slowdown due to having to perform 10 independent Additionally, it could be argued that these results are to be expected and trivial: we spending 10x the compute to get 10x the gradients.
heward-backwarr passes and then solving an additional inner problem.
One might even say there is need to solve the inner product and simpler method to select the best adversary would suffice. In Fig. 5a we address these concerns by comparing Section 5.3 to the results of the following variants attempting to match the computational complexity: PGD-70 runs single PGD adversary for 10x the number of steps, PGD-70
runs single PGD adversary for 10x the number of steps, using 1/t learning rate decay after leaving the "standard" PGD regime (i.e. after 8 adversary steps) to converge closer to an optimal adversarial example, PGD-max-Ie 10 runs ten parallel, independent PGD adversaries for each image and select the adversarial example that induces the largest loss. Finally, PGD-min-10 runs ten parallel, independent PGD adversaries for each image, then computes the gradients and selects the one with the lowest norm. This is an approximation of DDi that avoids solving Line 7in Algorith
In Fig. 5b we create a DDi variant based on the FAST adversary (Wong et al., 2020) (using E 8/ 8/255, a 10/255). Using PGD for the evaluation attack, we compare against vanilla FAST in our setting (no BN, momentum and using CELU) as well as a FAST-max-11 variant analoguous to PGD-max-10. As none of the PGD variants achieving the fast initial rise robustness. PGD-70 reach higher final robust accuracy, which we attribute to the higher quality adversarial example and informed selection respectively. This is corroborated in Fig. 5b) Using a single step adversary is sufficient to speed up convergence in the early stages of training, but does not reach the same final robust accuracy.
see in Fig. 5a every step of the pipeline of DDi seems to be necessary, with
and PGD-min-Il 10
PGD and DDi seem behave similarly in the later stages of training. We would suggest a compu- tationally cheaper DDi variant which uses single ascent steps (FAST) in the beginning of training and PGD in the later stages. In any case, the bulk of the overhead lies in the subroutine in Line of Algoriithm A faster approximate solution could also speed up the method significantly. Such incremental improvements are left for future work Neverthelss, in Appendix B.4 we explore some modifications that can reduce the runtime of Algorithm by at least 70% while retaining its benefits.
RELATED WORK
Wang al. (2019) derive suboptimality bounds for the robust training problem, under locally strong concavity assumption on the imnemmaxxiizotionn problem. However, such results do not extend to Neural Networks, the inner-maximization problem is not strongly concave, in general.
8

---

Published as a conference paper at ICLR 2023
0.50
0.50
DDI FAST
0.43
0.45
0.40
0.43
0.35
0.33
0.30
0.33
PGD
0.25
PGID-70-
7
PGDD-mne
DGDD-20
PGD-ssin-
30
175
900
170
1000
(b)
Figure 5: (a) Ablations comparing PGD-variane matching the number of adversarial gradients/steps used for DDi. (b Ablation over single-step adversaries (FAST/DDi-FAST)
In contrast, do not make unrealistic assumptions like strong concavity, and we deal with the existence multiple solutions of the inner-maximizatio problem.
In Nouiched al. (2019), it is shown that if the inner-maxinization problem is unconstrained and differentiable, and the gradient can be computed after obtaining a
satisfies the PL-condition, single solution of the problem. However, in the robust learning problem the adversary is usually constrained to a compact set, and the PL condition does not hold generically. This renders such assumptions hard to justify in the AT setting.
Tramer & Boneh (2019) Maini et al. 2020) study robustness to multiple perturbation types, which might appear similar our approach, but not. Such works strike train models that are simul- taneously robust against ex-- and fz-bounded perturbations, for example. In contrast, we focus on single perturbation type, and we study how use multiple adversarial examples of the same sample to improve the update directions of the network parameters.
Finally, we back our claim that the falseness of Madry al. (2018 Corollary C.2.) is not well- known in the literature Adversarial Training. For example, such result is included in the textbook (Vorobeychik et al.] 2018 Proposition 8.1). has also been either reproduced or mentioned in conference papers like Liu et al. 2020) Section 2), Viallard et al. (2021, Appendix B), Wei & Ma (2020) Section 5) and possibly many others. This supports our claim that raising awareness about the mistake in the proof is important contribution.
CONCLUSION
In this paper we presented a formal proof, counter examples and evidence about the real world im- pact of the fact that a foundational corollary of the Adversarial Training literature is in fact false. Raising awareness about an incorrect claim that has been present in the Adversarial Training lit- erature may provide opportunities to develop improved variants of the method. Indeed, we some improvents in an implementable algorithm that align with our theoretical arguments: DDi exploits multiple approximate solutions of the inner-mant maximizaaio problem, yields better updates for the parameters of the network and improves the optimization dynamics. However, it is impor- tant to remember the limitations and opportunities for future work: our algorithm requires multiple borward-backwer passes and additional optimization problem. Reducing the overhead over the vanlla PGD method would certainly make our results truly practical.
Non-smooth activations and the use of Batch Normalization or momentum still falls outside the scope of existing theory but might achieve better performance in benchmarks. To date, this requires using precise hyperparameters and tricks like carly-stopping that have only been found to work a- posteriori through extensive trial and error. Since we observe lower decay even in such setting, future work extending the analysis to cover this case might help alleviate this cost.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This work is funded (in part) through a PhD fellowship of the Swiss Data Science Center, a joint venture between EPFL and ETH Zurich. Igor Krawczuk, Leello Dadi, Thomas Pethick and Volkan Cevher acknowledge funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement n 725594 time- data). This work was supported by the Swiss National Science Foundation (SNSF) under grant number 200021 2200111.
This work is licensed under Creative Commons "Attribution 3.0 Un- ported" license.
cc
REFERENCES
Jonathan T. Barron. Continuously differentiable exponential linear units, 2017. URL https:
7/arxiv.
07483 14
Philipp Benz, Chaoning Zhang, and In So Kweon. Batch normalization increases adversarial vulner-
ability and decreases adversarial transferability: A non-robust feature perspective. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 7818-7827, 2021.
[4
Nils Bjorek, Carla P Gomes, Bart Selman, and Kilian Q Weinberger. Understanding batch normal- ization. Advances in neural information processing systems. 31, 2018. [4
Stephen Boyd. Subgradient methods.
https: /ttt:::/wwbb... wtw.s/oodd.eeee/casseeeeeeeeeeee
leetuuree/uuugrrrddeeettd.do..dd pd 2014. [Online; accessed 27-September-20222]
Andy Brock, Soham De, Samuel L Smith, and Karen Simonyan. High-performance large-scale image recognition without normalization. International Conference on Machine Learning, pp- 1059-1071. PMLR, 2021. 14
Francesco Croce, Maksym Andriushchenko, Vikash Sehwag, Edoardo Debenedetti, Nicolas Flam- marion, Mung Chiang, Prateek Mittal, and Matthias Hein. Robustbench: a standardized adver- sarial robustness benchmark. arXiv preprint arXiv:2010.090 2020.
John M. Danskin. The theory of max-min, with applications. SIAM Journal on Applied Mathe- matics, 14(4):641 1966. doi: 10.1137/0114053 URL
0114053 3
Yinpeng Dong, Zhijie Deng, Tianyu Pang, Jun Zhu, and Hang Su. Adversarial distributional train- ing for robust deep learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 8270- 8283. Cur- ran Associates, Inc., 2020. URL http:tts///roccednggggg .eerreddddinnnn.nnssseee.e..ee wttp:ipps..pppppe///2220
file
pdf
Shiv Ram Dubey, Satish Kumar Singh, and Bidyut Baran Chaudhuri. Activation functions in deep learning: A comprehensive survey and benchmark. Neurocomputingg 503:92-108, 2022. ISSN 2312- doi: http::/dbb.orr/1100066....eeo 212.0.000......2221111111.1.1 URL https: //tt:::::ww.. www..
sciencedirect com/ http://ww......a.aocacc.acaaaaaa
John Duchi, Shai Shalev-Shwartz, Yoram Singer, and Tushar Chandra. Efficient projections onto the 1 1-ball for learning in high dimensions. In Proceedings of the 25th international conference
on Machine learning, pp. 272-279, 2008. 5
Logan Engstrom, Andrew Ilyas, Hadi Salman, Shibani Santurkar, and Dimitris Tsipras. Robustness (python library), 2019. URL
com/ Mad Maadrlabb/rbbsstessss 7
robusttessssss
Ian Goodfellow. Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA. USA. May 7-9, 2015, Conference Track Proceed- ings, 2015. URL http:://axxiiii http:////aawi..oorra////a////
6572 T
10

---

Published as a conference paper at ICLR 2023
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 1448-566 PMLR. 2015.
7 14
Jonas Kohler, Hadi Daneshmand, Aurelien Lucchi, Thomas Hofmann, Ming Zhou, and Klaus Neymeyr. Exponential convergence rates for batch normalization: The power of length-direction decoupling in non-convex optimization. In The 22nd International Conference on Artificial Intel- ligence and Statistics, pp.
PMLR, 2019.
14
Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. Adversarial machine learning scale. In International Conference Learning Representations, 2017. pttttps://operreett
net fert/forum33 3==3J4444kk
Simon Lacoste-Julin and Martin Jaggi. On the global linear convergence of frank-wolfe opti- mization variants. In Proceedings of the 28th International Conference on Neural Information Processing Systems Volume 1, NIPS' 15, pp. 496-504, Cambridge, MA, USA, 2015. MIT Press.
Sijia Liu, Songtao Lu, Xiangyi Chen, Yao Feng, Kaidi Xu, Abdullah Al-Dujaili, Mingyi Hong, and Una-May O' Reilly. Min-max optimization without gradients: Convergence and applications to black-box evasion and poisoning attacks. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 6282 6293. PMLR, 13 13-18 Jul 2020. URL https: pettps://proceedinng
mlr.press/v119/Li222 html
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.
Pratyush Maini, Eric Wong, and Zico Kolter. Adversarial robustness against the union of mul- tiple perturbation models. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learn- ing Research, pp. 6640-6650. PMLR, 13-18 Jul 2020. URLattps: http:tpppp/ppcceeinnnnie .mw.............mmmmmm.........m gress/vv19/nane press//119/main1200r html
Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving class of non-convex min-max games using iterative first order methods. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alche Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates. Inc.. 2019. URL ht https///pprcceeiiss...e... 25048eb6a 9cb wtt.:5aa81150fffofffeeeeo
pdf
Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv: 191.
2019. 6
Alessandro De Palma, Harkirat Behl, Rudy R Bunel, Philip Torr, and M. Pawan Kumar. Scaling the convex barrier with active sets. In International Conference Learning Representations, 2021.
URL htt.hs://oppnreeiiieeeeee
Tianyu Pang, Xiao Yang. Yinpeng Dong, Hang Su, and Jun Zhu. Bag of tricks for adversarial training. In International Conference on Learning Representations, 2021. URL https://
Xb8xvrtB8Ce 7
Neal Parikh, Stephen Boyd. al. Proximal algorithms. Foundations and trends()) in Optimization, 1(3):127-23,, 2014.
Shibani Santurkar, Dimitris Tsipras, Andrew Ilyas, and Aleksander Madry. How does batch malization help optimization? Advances in neural information processing systems, 31, 2018.
Maurice Sion. On general minimax theorems. Pacific Journal of Mathematics, 8(1):11 176, 1958. doi: pjm/1 103040253. URL httpt/tt///d/ot
16
11

---

Published as a conference paper at ICLR 2023
Christian Szegedy, Wojeiech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, lan J. Good- fellow, and Rob Fergus. Intriguing properties of neural networks. In Yoshua Bengio and Yann LeCun (eds.), 2nd International Conference Learning Representations, ICLR 2014, Banff. AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014. URL. http:
//arxiv.org baarg//bb//35 /1312 1199
T
Vincent Tjeng, Kai Y. Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In International Conference on Learning Representations, 2019.
URL httts::/
net/ piet/for Sooormmiid-yyGiiiiie.
Florian Tramer and Dan Boneh. Adversarial training and robustness for multiple perturba- tions. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. Fox, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL https: httts:://proceedinngg htwp:e/eeeddinn....ee..es...e.ee www.inuuii..... http://s......rss....p////////// cc/pappe//211//iille 5d4ae 7 0al.aaee666001181220oo.l.2222232 6ad1
Paper pdf
Paul Viallard, Pascal Germain, Amaury Habrard, and Emilie Morvant. Self-bounding majority vote learning algorithms by the direct minimization of tight pac-bayesian c-bound. In Nuria Oliver, Fernando -ruzz,Cruz, Stefan Kramer, Jesse Read, and Jose A. Lozano (eds.), Machine Learning and Knowledge Discovery in Databases. Research Track, pp. 167-183, Cham, 2021. Springer International Publishing. ISBN 978-3-030-86520-7, 2
Yevgeniy Vorobeychik, Murat Kantarcioglu, and Ronald Brachman. Adversarial Machine Learning.
Morgan & Claypool Publishers, 2018. ISBN 1681733951, 9
Haotao Wang, Aston Zhang, Shuai Zheng, Xingjian Shi, Mu Li, and Zhangyang Wang. Removing batch normalization boosts adversarial training. In International Conference on Machine Learn-
ing. pp. 2-445.. PMLR, 2022. 14
Shiqi Wang. Huan Zhang, Kaidi Xu. Xue Lin, Suman Jana, Cho-Jui Hsich, and Zico Kolter. Beta-CROWN: Efficient bound propagation with per-neuron split constraints for neural network robustness verification. In A. Beygelzimer, Y. Dauphin, Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL hittps://openreett
met//orummid=ahhY...
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 on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6586-6595. PMLR, 09-15 Jun 2019. URL
https::/prroeedings mlr press wttress//37/wwgg1133 html
g
Colin Wei and Tengyu Ma. Improved sample complexities for deep neural networks and robust classification via an all-layer margin. International Conference on Learning Representations,
2020. URL http:://pppeeeeeeeeeeeee net. ftr.m/ooummmiiiii Baeaa-Heee____e_ee yR4F 9
Eric Wong, Leslie Rice, and J. Zico Kolter. Fast is better than free: Revisiting adversarial training. In
International Conference on Learning Representations, 2020. URL/https::/oppnrerviee
g
Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European conference on
computer vision (ECCV), pp. 3-19, 2018. 7 14
Yan Yan, Tianbao Yang, Zhe Li, Qihang Lin, and Yi Yang. A unified analysis of stochastic
momentum methods for deep learning. In Proceedings of the Twenty-Sevnnth International Joint Conference on Artificial Intelligence, IJCAI-18, pp. 2955-2961. International Joint Con- doi: 10. 10.2496//jcai.211884410 URL
ferences Artificial Intelligence Organization, 7 2018.
https://doi. httpp://aaa..ooog0..2243/3//3//3
14
Huan Zhang, Shiqi Wang, Kaidi Xu, Yihan Wang, Suman Jana, Cho-Jui Hsich, and Zico Kolter. A branch and bound framework for stronger adversarial attacks of ReLU networks. In Ka- malika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.). Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 226044. PMLR, 17-23 Jul 2022. URL https:://roceee ngs. ml www.ss.prssseee.. 62. 29. html
5
12

---

Published as a conference paper at ICLR 2023
A
MORE ON COUNTEREXAMPLES
Here we give more details on the construction the counterexamples. First observe that for a given point fu, and direction if there exists óu S* (Bu) such that (7, Veg(Ou. 8)) 0, then is not a descent direction since D,0(f)) 2 0.
In order to ensure that descent directions suffices to guarantee that for any 5 E (*n),, there exists d' E (*0)) such that (Vog(Os, 8'), Vog(Oo, 8)) < 0. This way, neither - Vog((0, 5) - Vog 8') would be descent directions.
be recovered by solving the inner-maximizenn
It easy generate instances verifying the above using linear functions. More formally, by taking any family of vectors V = {ui,..., Vn such that for any i E {1..... nh there exists j E (1...., ,.) construct the objective g00, 6) Σ 6,u, (0 0g) H()), where 8 is
such that (v,, 03) in the n-dimensional Simplex and H is the Shannon entropy. Solving the inner- maximization would yield any one of the vectors {Ui...., ). and by construction, none them are descent directions.
B EXPERIMENTS
B.1 MULTIPLE ATTACKS
6.5
Figure 6: The losses of multiple perturbations 9 different example all concentrate around a value much larger than the clean loss. See Section 5. for experimental details. The histograms have been enlarged in Figure
13

---

Published as a conference paper at ICLR 2023
Figure 7:
The losses of multiple perturbations on 9 different example all concentrate around value much larger than the clean loss (see Figure 6 for comparison with the clean loss).
B.2 JUSTIFYING OUR MODIFICATIONS
For Danskin's Theorem Theorem to hold, require the function be differentiable. To satisfy differentiability, we replace ReLU with CELU (Barron 2017) which has been found to have comparable performance and sometimes outperform ReLU (Dubey et al. 2022).
To operate individual images and remove the batch-wise correlations across samples replace BatchNorm (BN) [Ioffe & Szegedy 2015) with GroupNorm (GN) (Wu & He 2018
Finally, make each update depend only on the current state, momentum is standard practice in the CV community and works like Yan et al. (2018) argue that can improve generalisation, we rely on our ablation show that removing it safe.
momentum 0.0. Since
B.3 FURTHER DETAILS ON SYNTHETIC EXPERIMENTS
The synthetic experiment in Fig. la is conducted with the following settings. The inner- maximization is approximated with steps of projected gradient ascent in order to match the tradi- tional AT setting. The outer iterations have decaying 0.5 step-size schedule. We observe the same erratic behavior for PGD with fixed outer stepsize, while DDi consitently remains well-behaved.
The synthetic experiment in Fig. 3 is conducted on dataset of size 100 in dimension 2 where the coordinates are standard Gaussian. The neural network is 2-layer network with ELU activation with hidden layer of width 2. The inner solver is PGD with 10 steps with stepsize 0. and optimizes
There are whole lines of work studying the effects of BN BBoorck et al. 2018 Santurkar et al. 2018 Kohler et al. (2019) as well as removing it altogether/ et al. 2021). It has also been found to interact with adversarial robustness in Wang al. (2022) and Benz al. 2021). the latter also finds GN to be well performing alternative, justifiing choice.
14

---

Published as a conference paper at ICLR 2023
the unit cube. The outer step-size is 0.01 and the weights are optimized with full batch gradient descent.
The linear approximation iteration 250 of the robust loss consits of taking the 10 adversarial examples computed at iteration 250 and approximating it with
5(0)
max ((0250) (Vog(O250 (0250 6z), 61...100
0250)
Interestingly we do observe the same drastic improvement over PGD when observing the non- linearized loss at iteration 250.
0176
INGY
PGD
1GU
PGD
Hobvuct L.res
07775
12:99
PGD
02290
Step along normalized dirrction
B.4 IMPROVING THE RUNNING TIME
0.40
0.43
0.30
0.30
0.25
Theees
0.25
PUDD-Thess
DEN-FAST -op--bo----o
SA--AAST E-doop--ooni
DOX DOX-FAST-dON
DON-PAS PAST- PAST-JosD
DDD-PDD
DDKPPGD P.DD-craay-ooot
0.10
D2X-2GD-Gose
0.15
D.N-PGD-ombh
80
100
120
340
20200
40000
00000
50000
100000
120000
Epochs
Walliaack
Figure 8: (a Epoch evolution of a more efficient implementation of DDi. of the same methods.
Wallclock evolution
While the focus of this paper is not obtain state-of-the-an method, does matter whether is feasible to efficiently capture the benefit of DDi. The naive implementation has about 10 12 times overhead compared PGD, mainly due to three bottlenecks (in descending impact)
1. for k-DDi, generating k adversarial examples with PGD as the base attack involves a A- times overhead
2. then & separate gradient samples need to be computed on these adversarial examples, which involes & forward- backward passes
3. finally, one additional optimization problem needs to be solved.
While steps and 2) be somewhat parallelized, they still cause massive increase in com- pute and memory. We therefore adopt two heuristic approaches to speed up the algorithm while (hopefully) maintaining it's benefits:
since later in training the benefits of DDi appear to diminish, we linearly decay the number of gradients sampled from 10 down along the 200 epochs (referred decay)
15

---

Published as a conference paper at ICLR 2023
2. also adopt method of creating & unique batches from only 2 independent adversarial attacks (described below in Appendix B.4.1 referred to as comb).
We evaluate this method using both PGD and FAST as base attacks and show the results in Fig. 8a and Fig. 8b. As be seen, DD-PGD-decay-io speedup in wallclock time (reducing the 12x overhead to about 3x) while retaining the improved per-step progress of base Di.
and DA-PGD- both enjoy massive
B.4.1 COMBINATORIAL BATCH CONSTRUCTION
Suppose have batch of data-label pairs (Ia; ys) of size B. In order to construct & 2 different gradients by computing only 2 adversarial examples per data sample 2; in the batch we do the following:
1. for each i 1, ..... B compute os,, σ,,1 two adversarial examples using the data-label pair (Ii, M/i the batch.
2. for each j ..... & repeat the following steps:
3. Define A as empty list.
4. generate random bitvector C 1) of length B
5. when b; is 0 we append 6,,0 to A, otherwise when b; is 1 we append 6,, to A.
6. compute the gradient w.rt. the network parameters using the perturbations in A
While this still incurs overhead of computing k gradients, gready reduces running time seen in Fig. 8b and could further improved by e.g. reusing gradients from past epochs to construct the examples.
C PROOF OF THEOREM
The steepest descent direction is computed, following Eq. (4)
as:
E arg min (0)( arg min
(7, Vog(O.5))
(15)
>:Ib>ll- SES; (0)
Whenever is not a local optimum, there exists a non-zero descent direction. In this case we can relax the constraint that || = 1 to ||a/|2 I without changing the solutions optimal value of 15 which is strictly negative:
max (7, Vog(O, < min max (7, Vog(O, >il dES; (0) >ilhlll=1ées;
min
(16)
We can now transform compact constraints:
15 into bilinear convex-concave min-max problem, subject to convex and
E arg min Dy0(0) = arg min max (r, Vog(H,
11
11 (6St
arg min max
V Vog (60)
(17)
a1ll il....
arg min max Y Veg(O, (8))a
x1 m
By Sion's minimax Theorem Sion 1958), can solve Eq. (17) by swapping the operator order:
min 7 S (8))a min max 7 Veg(O, (0))a a 7:llllas1 DEE
VV S (0))a |a|12
(18)
min "
Vog S ( a <
Finally, by noting that squaring the objective function in the right-hand side of Eq. (18) does not change the set of solutions, arrive the formula for a in Eq. (14) Indeed for solution a² to
16

---

Published as a conference paper at ICLR 2023
this problem have
arg min max (0)(a xlllss 9E
arg min 7 Vog(O, S (0))a*
(19)
Vog(O, Sm (0))a*
Veg(O S (0)
where the denominator is nonnegative as the optimal objective value is nonzero c.f. Eq. (18)
D PROOF OF THEOREM
For any (0) let i(6) E {I....,m) m be such that [])(((6) - 8|12 I c. That is, we map any maximizer 8 to an index [l....,m} m3 such that the corresponding perturbation 86) the finite set St (0) is most an distance. This map be constructed by the assumption S% (0).
For any y such that l| = we have
(7, (og(O, 8)) (7, V Ve - Vog(O, ((00)))))))) + (7, Veg(O, Veg(0,0((18)))
1rlle Veg(8, 5) Veg(o, ((16))))))) +(,, Vog(O, (og(0,8(166))
$c1b6-ttioMisee
(20)
(y, Veg(O, 8 (((6)))) + Le
sup {,, Vog(O, )()) Le (0)
Taking the supremum over d E S (0) the left-hand-side we obtain
Dy0(0)= = sup (ES
(,, Vog(O. 8))
sup (7, Vog(O, 5(0) + Le 6ES;, (0)
(21)
Hence if the supremum the right- sehht-hand-side is strictly smaller than -C we have that D, 0, which yields the desired result.
E
PROOF OF LEMMA
Assume the limit that defines (0) exists (and is finite).
Φ(0 + ((-x)) - (0))
D_0((0) = lim r+
||] - 7
Φ(0 + (11)) x0)
lim
- 1-ttll7/a
@ + (-1))) ((0)
(-
11-1)
(22)
@0 s7) ((0)
lim
(Iet s = (-t))
s-0
8 8|17/2 l2
@(0 + 37) ((0)
-lim
50+
s|||||
-D,g(0)
17


Reviews:
[{"review_id": "o1sO26Ek0A", "reviewer": "Reviewer_FpN3", "summary": "", "questions": "", "limitations": "", "rating": 10, "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": "The starting point for this paper is the observation that one of the key theorems in (Madry et al., 2018) is incorrect.  In particular, the authors show that the interpretation of Danskin's theorem in (Madry et al., 2018) uses the incorrect form of the directional derivative.  They provide several counterexamples to demonstrate this flaw, which yield interesting insights on the problem of adversarial training.\n\nBased on these observations, the authors propose Danskin's Descent Direction (DDD), an algorithm that is designed to solve the standard minimax formulation of adversarial training.  They show that their method is more stable than PGD on several benchmarks, although the empirical gains are somewhat modest at convergence.  ", "summary_of_the_review": "Overall, I thought this was a really solid paper.  It makes some interesting insights, and the result is an algorithm that seems to have some nice empirical properties.  There are a few drawbacks, such as the increased computation time.  Most of the weaknesses listed above are relatively minor.  Therefore, I think this paper should be accepted.\n\n---\n\n**Post rebuttal comments.**  The authors have addressed each of my concerns.  Therefore, I will raise my score, as I believe that the additional clarifications and theoretical results improve the paper. ", "strength_and_weaknesses": "### Strengths\n\n**Soundness.**  This paper seems to be technically quite sound.  It is certainly the most rigorous paper that I have reviewed in my batch of papers this year at ICLR.  The analysis of Danskin's theorem and of the result in (Madry et al., 2018) appears to be correct, which indeed calls into question one of the foundational assumptions underpinning adversarial training.  \n\nThe counterexamples shed new light on the problem as well.  I particularly appreciated the fact that after disproving the theorem from (Madry et al., 2018), the authors took it one step forward.  They ask: In the case when I'm not at a locally optimal point, is the result of (Madry et al., 2018) still incorrect.  And via a more intricate, although still pleasingly elementary, construction, they show that another counterexample exists.  This is thorough work, and I believe that it should be commended.\n\n**Algorithm.**  The algorithm proposed by the authors seemed relatively natural.  While it is clearly up for debate whether the set of maximizers is finite, I think it's not an unreasonable assumption to make.  And the authors provide some nice empirical evidence that at the very least, the set is not a singleton.  Given this, Thm. 2 makes sense given the context of the paper, and it leads to a relatively practical algorithm.  Nice!\n\n**Well written.**  This paper is relatively well written.  The related work was thorough.  And in general, the logic and flow of the paper was solid.  I really enjoyed reading it!\n\n### Weaknesses\n\n**Minor inconsistencies in notation.**  One point of confusion: if $\\delta\\in\\mathbb{R}^p$, then $\\mathcal{S}\\subset\\mathbb{R}^p$ in (1).  In (2), we have $\\delta_i\\in\\mathbb{R}^p$, and therefore $\\delta$ seems to be an element of $\\mathbb{R}^{p\\times k}$, meaning that $\\mathcal{S}\\subset \\mathbb{R}^{p\\times k}$ (or perhaps of $\\mathbb{R}^{pk}$).  This is a bit inconsistent, as it would be nice to think of $\\mathcal{S}$ as belonging to a particular space.\n\n**Confusing presentation of the key theorem.**  One key step of this paper is to present the theorem of (Madry et al., 2018), which is done in Corollary 1.  Before presenting this result, the authors say that\n\n> \"Corollary 1 is an equivalent rephrasing of Madry et al. (2018, Corollary C.2.), and is derived as a consequence of Theorem 1. \n Unfortunately counterexample 1 shows that it is false:\"\n\nLet Thm. 1 (Danskin's theorem) be A and let Cor. 1 be B.  Based on my reading, this sentence says that A implies B, since \"derived\" (to me) means \"correctly derived.\"  The authors then say that B is false.  By the contrapositive, this would imply that A is false.  Based on the rest of the paper, I know that this is not what the authors are trying to say.  So I would suggest rewording this part to emphasize that A does not imply B, as some readers may get confused by this point, and that is quite undesirable given that this is one of the most important points in the paper.\n\nI would also recommend defining a \"descent direction\" before it is mentioned in Cor. 1.  This would make it easier to understand the result in Cor. 1 without having to read on until a later section.  \n\n**A minor recommendation.**  I would recommend removing the phrase: \"a basic concept in multivariable calculus.\"  This may only be my opinion, but I feel that this phrase may be perceived by some readers as a little bit disrespectful to (Madry et al., 2018), especially given that (Madry et al., 2018) is a relatively influential paper.  Yes, this idea is often introduced in a college-level calculus course.  But it took until now for anyone to notice this subtle distinction. \n\n**Explain Madry et al.'s results in more detail.**  I think it's well worth spending more time on the results of the original paper.  The discussion at the bottom of page 3 is relatively terse.  In particular, I believe that it would be beneficial for the authors to expand on the sentence:\n\n> \"However, we cannot guarantee that the function will decrease if we move in the opposite direction...\"\n\nDuring my first pass through the paper, I didn't understand this part.  Underscoring the fact that Madry et al. assume that $D_\\gamma \\phi(\\theta) > 0$ *implies that* $D_{-\\gamma} \\phi(\\theta) < 0$ is essential here, because it is at the heart of why the original result was not correct.  It may be worth proving that for the two-sided directional derivative, this property does hold.  Although elementary, I think this would help build intuition for the reader.\n\n**Oracle?**  I didn't understand what the authors meant by a \"heuristic oracle.\"  The word \"heuristic\" seems to defeat the purpose of an oracle.  Could the authors explain more here?\n\n**Computation time.**  A downside of the proposed method is obviously the computation time.  It seems clear that at convergence, DDD doesn't offer a significant improvement over PGD given that it seems to get 10x more steps.  I may have missed this, but did the authors compare PGD-100 to DDD-10, which would constitute a comparison where each algorithm got roughly the same computational budget?", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "lEro0UqyznM", "reviewer": "Reviewer_UVpf", "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 points out an issue in a recent theoretical result that motivates the adversarial training algorithm. The authors construct counter examples and provide explanations about the issue they identify, and then further propose a Danskin's Descent Direction for training robust neural networks.", "summary_of_the_review": "This paper points out an important issue in adversarial training. The paper is well written and the claims seem solid. However, the proposed method is still questionable and more justification is needed to demonstrate its advantage over existing methods.", "strength_and_weaknesses": "Strengths: \n\nThe claims of the paper seem solid, and the paper is well written. \n\nThe proposed method is backed up by experiments.\n\nWeaknesses: \n\nTheorem 2 is based on the assumption that the set of optimal adversarial perturbations is finite. This is a strong and sometimes unrealistic assumption.\n\nAccording to the authors' discussion, it seems that Madry et al. (2018, Corollary C.2) could be made rigorous by adding an assumption such as \"$\\phi(\\theta)$ is differentiable at $\\theta$\". Even with this additional assumption, this result seems sufficient to motivate the adversarial training algorithm. \n\nBecause of the above reasons, the advantage of the proposed DDD method over the adversarial training method is not very clear. After all, the theoretical guarantee for the proposed DDD method (Theorem 2) is also based on an unrealistic assumption. The DDD method also seems to be computationally more expensive than adversarial training. ", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "gxqVuUZJpC", "reviewer": "Reviewer_wzJU", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The authors point out that the interpretation of Danskin's Theorem that was used to motivate the Adversarial Training paradigm in the seminal paper from Madry et al. (2018) relies on a misunderstanding of the notion of directional derivative employed in the theorem. As a consequence, PGD, the most commonly employed adversarial training scheme, might not follow descent directions. The authors present a solution to this, assuming finitely-many global optimizers of the inner maximization, and show that it helps in practice in setttings where Danksin's Theorem would hold.", "summary_of_the_review": "The authors point out an interesting problem in the adversarial training literature: while the practical effectiveness of the presented method is limited at best, and the presented solution is never used in the setting for which it is motivated (the inner maximization is never run to convergence, as that would require running formal neural network verification), I believe the paper is a first step towards more principled adversarial training algorithms.\nNevertheless, the authors should be more direct about the limitations of the proposed solution and its empirical relevance, from the beginning of the paper. I will be willing to increase my score after this and the other weaknesses I pointed out are addressed.", "strength_and_weaknesses": "The authors raise awareness about a mistaken interpretation of Danskin's Theorem when motivating adversarial training, and demonstrate its relevance through counter-examples and empirical evidence. A solution to this problem is presented (DDD), and its relative effectiveness on smooth networks (without BatchNorm) is shown. \nAt this stage, the contribution is purely technical: the practical relevance of the presented method is limited because of its inferior performance in the setting that attains the maximal robust accuracy (ReLU + BatchNorm). Furthermore, DDD greatly increases the runtime per iteration, making its practical employability limited.\nNevertheless, I believe the findings to be of great interest to the community. \n\nIn my opinion, the strength of the paper could benefit if the authors addressed the following limitations:\n- Typically, in the context of adversarial training, the inner maximization is not run to convergence. Indeed, this holds also for the presented experiments. Therefore, DDD is not guaranteed to yield a descent direction for the robust loss even when the conditions of Danksin's Theorem hold. It would be important for the authors to comment on why DDD helps in this setting. Indeed, getting to a guaranteed global optimum of the inner maximization would require running a complete verification algorithm based on Branch and Bound (it would be nice if the authors touched on this, and mentioned relevant methods in the literature). \n- Practical limitations (in practice the overall best-performing method remains PGD) should be stated in intro and abstract (as the authors do in the conclusions) . The statement on the early stages should be limited to the smooth setup (the difference in Figure 4b seems to be too small to be statistically reliable).\n\nAs a minor point: why not Frank-Wolfe for the smooth simplex-constrained optimization problem that arises from DDD?\nFinally, the fact that the inner maximization in AT is not run to global optimality would be visibile if the authors provided a magnified version of the high-loss region of Figure 2.", "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": "FuXQN3OwFn_", "reviewer": "Reviewer_gFkW", "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 pays attention to the computation of adversarial training, by pointing out that even in the simple case (nonsmooth), the descent direction is not given by the worst-case perturbation, as opposed to common practice in the AT community. The paper then proposes a method that, under the assumption of a finite number of worst-case perturbations, computes the correct descent direction. ", "summary_of_the_review": "This paper focuses on the bring forward the issue that (a single) adversarial example might not give the descent direction, challenging a common belief adopted in the practice of this field. It did this with simple examples making its arguments. This is the strongest point of this paper. The proposed method, on the other hand, is computationally expensive compared to the original AT, and the final performance is comparable to AT, which is to some extent surprising given the fact that AT is supposedly not a correct method, the main theoretical claim made by this paper. The practical side of the claim and method proposed in this paper seems a little bit limited by its current shape. ", "strength_and_weaknesses": "Strength:\n\nI appreciate the conceptual idea of this paper a lot. The starting point of the paper is the observation that the descent direction not necessarily corresponds to the worst-case perturbation. Given the fact that this is typically assumed always be the case in the AT community, this paper has provided a refreshing perspective on how should we do AT correctly. The constructed counterexamples are also easy to understand. \n\nWeakness:\n\nThe potential downside of this paper is that the proposed method (DDD) is inherently computationally expensive. As the authors advocate the usage of multiple worst-case perturbations, adopting DDD would require at least several times of computational effort compared to the already expensive standard AT procedure. \n\nAnother concern that I have is the similar final performance achieved by both AT and DDD. It seems that their performance differs by some margin only in the initial stage of the training, but is getting much closer to the final stage. This to some extent, has limited the potential practical impact of the proposed method. \n\n\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster