Adversarial Training Should Be Cast as a Non-Zero-Sum Game
Authors: Alexander Robey
Fabian Latorre
George J. Pappas
Hamed Hassani
Volkan Cevher
Venue: ICLR 2024 poster (2024)
Keywords: Adversarial training
two-player zero-sum
bilevel optimization
Primary area: societal considerations including fairness, safety, privacy

Abstract: One prominent approach toward resolving the adversarial vulnerability of deep neural networks is the two-player zero-sum paradigm of adversarial training, in which predictors are trained against adversarially chosen perturbations of data. Despite the promise of this approach, algorithms based on this paradigm have not engendered sufficient levels of robustness and suffer from pathological behavior like robust overfitting. To understand this shortcoming, we first show that the commonly used surrogate-based relaxation used in adversarial training algorithms voids all guarantees on the robustness of trained classifiers.  The identification of this pitfall informs a novel non-zero-sum bilevel formulation of adversarial training, wherein each player optimizes a different objective function. Our formulation yields a simple algorithmic framework that matches and in some cases outperforms state-of-the-art attacks, attains comparable levels of robustness to standard adversarial training algorithms, and does not suffer from robust overfitting.

Published as a conference paper at ICLR 2024
ADVERSARIAL TRAINING SHOULD BE CAST AS A NON -EN-ZERR-SUM GAME
Alexander Robey* University of Pennsylvania arobeyl @upenn edu
Fabian Latorre*
LIONS, EPFL fabian. btooiim..atoorreepll...c.
George J. Pappas University of Pennsylvania edu
Hamed Hassani
Volkan Cevher LIONS, EPFL
University of Pennsylvania hassan @upenn. edu
volkan..eeverr@epll.cc
ABSTRACT
One prominent approach toward resolving the adversarial vulnerability of deep neural networks is the two-player zero-sum paradigm of adversarial training, in which predictors are trained against adversarially chosen perturbations of data, Despite the promise of this approach, algorithms based on this paradigm have not engendered sufficient levels of robustness and suffer from pathological behavior like robust overfitting. To understand this shortcoming, we first show that the commonly used surrogate-baset relaxation used in adversarial training algorithms voids all guarantees on the robustness of trained classifiers. The identification of this pitfall informs novel non-zero-sum bilevel formulation of adversarial training, wherein each player optimizes a different objective function. Our formulation yields simple algorithmic framework that matches and in some cases outperforms state- of-the-art attacks, attains comparable levels of robustness to standard adversarial training algorithms, and does not suffer from robust overfitting.
INTRODUCTION
A longstanding disappointment in the machine learning (ML) community is that deep neural networks (DNNs) remain vulnerable to seemingly innocuous changes to their input data, including nuisances in visual data (Laidlaw et al., 2020; Hendrycks & Dietterich, 2019), sub-populations (Santurkar et al., 2021; Koh et al., 2021), and distribution shifts (Xiao et al., 2021; Arjovsky et al., 2019; Robey et al., 2021). Prominent amongst these vulnerabilities is the setting of adversarial examples, wherein perturbations can fool state-of- the-art classifiers parameterized by DNNs (Szegedy et al., 2013; Biggio al., 2013). In response, plethora of research has proposed so-called adversarial training (AT) algorithms (Madry et al., 2018; 8; Goodfellow et al., 2015), which are designed improve robustness against adversarial examples.
has been conclusively shown that imperceptible, adversarially-chose
AT is ubiquitously formulated as a two-player zero-sum game, where both players-often referred to as the defender and the udversary-respeeee error. However, this zero-sum game is not implementable in practice as the discontinuous nature of the classification error is not compatible with first-order optimization algorithms. To bridge this gap between theory and practice, it is commonplace to replace the classification error with smooth surrogate loss ge.g., the cross-entropy loss) which is amenable to gradient-based optimization (Madry al., 2018; 8; Zhang al., 2019). And while this seemingly harmless modification has a decades-lont tradition in the ML literature due to the guarantees it imparts on aon-adversarial objectives (Bartlett et al., 2006; Shalev-Shwarzz. & Ben-Davie 2014; Roux, 2017), there is a pronounced gap in the literature regarding the implications of this relaxation on the standard formulation of AT.
seek to minimize and maximize the classification
As the field of robust ML has matured, surrogate-basee based AT algorithms have collectively resulted in steady progress toward stronger attacks and robust defenses (Croce et al., 2020a). However, despite these advances, recent years have witnessed a plateau in robustness measures on popular leaderboards, resulting in the widely held beliefs that robustness and accuracy may be irreconcilable (Tsipras et al.,
"The first authors contributed equally.

---

Published as a conference paper at ICLR 2024
2019; Dobriban et al., 2020) and that robust generalization requires significantly more data (Schmidt et al., 2018; Chen et al., 2020). Moreover, various phenomena such as robust overfitting (Rice et al., 2020) have indicated that progress has been overestimated (Croce & Hein, 2020). To combat these pitfalls, state-of-the-ar algorithms increasingly rely on ad-hoc regularization schemes (Kannan et al., 2018; Chan et al., 2020), weight perturbations (Wu et al., 2020; Sun et al., 2021), and heuristics such as multiple restarts, carefully crafted learning rate schedules, and convoluted stopping conditions, all of which contribute to an unclear set of best practices and a growing literature concerned with identifying flaws in various AT schemes (Latorre et al., 2023).
Motivated by these challenges, we argue that the pervasive surrogate-bar -baed zero-sum approach to AT suffers from a fundamental flaw. Our analysis of the standard minimax formulation of AT reveals that maximizing a surrogate like the cross-entropy provides no guarantee that the the classification error will increase, resulting in weak adversaries and ineffective AT algorithms. In identifying this shortcoming, we prove that to preserve guarantees on the optimality of the classification error objective, the defender and the adversary must optimize different objectives, resulting in a non- zero-sum game. This leads to novel, yet natural bilevel formulation (Bard, 2013) of AT in which the defender minimizes an upper bound on the classification error, while the attacker maximizes continuous reformulation of the classification error. We then propose an algorithm based on our formulation which is free from heuristics and ad hoc optimization techniques. Our empirical evaluations reveal that our approach matches the test robustness achieved by the state-of- state-of-the-ary yet highly heuristic approaches such as AutoAttack, and that eliminates robust overfitting.
Contributions. Our contributions are as follows.
New formulation for adversarial robustness. Starting from the discontinuous minmax for- mulation of AT with respect to the 0-1 loss, we derive a novel continuous bilevel optimization formulation, the solution of which guarantees improved robustness against the optimal adversary. New adversarial training algorithm. We derive BETA, new, heuristic-free algorithm based on our bilevel formulation which offers competitive empirical robustness on CIFAR-10. Elimination of robust overfitting Our algorithm does not suffer from robust overfitting. This suggest that robust overfitting is an artifact of the use of improper surrogates in the original AT paradigm, and that the use of correct optimization formulation is enough to solve it.
-tate-of-the-art robustness evaluation. We show that our proposed optimization objective for the adversary yields simple algorithm that matches the performance of the state-of tatte-of-theaar the--rr-,t,, yet highly complex AutoAttack method, on state-of of-the-rrtttttt robust classifiers trained on CIFAR-
2 THE PROMISES AND PITFALLS OF ADVERSARIAL TRAINING
2.1 PRELIMINARIES: TRAINING DNNS WITH SURROGATE LOSSES
We consider a K- K-way classification setting, wherein data arrives in the form of instance-label pairs (X, Y) drawn i.i.d. from an unknown joint distribution D taking support over x y C Rd x [K], where [K] := {1, .., K). Given suitable hypothesis class F, one fundamental goal in this setting is to select an element f E which correctly predicts the label Y of a corresponding instance X. In practice, this hypothesis class F often comprises functions So Rd + RR which are parameterized by a vector f E O C RR, as is the case when training DNNs. In this scenario, the problem of learning a classifier that correctly predicts Y from X can written as follows:
min E arg max fe(X); # #V) OE
ZE[K]
Here (x(X); denotes the 7th component of the logits vector fo(X) E R and we use the no- tation {A) to denote the indicator function of an event A, i.e., (A) = T.(.). In this sense, (arg [e fX) + Y} denotes the classification error of fo on the pair (X,Y).
Among the barriers to solving (1) in practice is the fact that the classification error is a discontinuous function of 8 which in turn renders continuous first-order methods intractable. Fortunately, this pitfall can be resolved by minimizing surrogate loss function é [k] x [k] + E in place of the classification & Ben-David, 2014, $ $12.3). For minimization problems, surrogate losses are
error (Shalev-Shward chosen to be differentiable upper bounds of the classification error of fo in the sense that
arg max fo(X), # Y < {(f(())))) (E[K]
(2)
2

---

Published as a conference paper at ICLR 2024
This inequality gives rise to differentiable counterpart of (1) which is amenable to minimization via first-order methods and can be compactly expressed in the following optimization problem:
min E. {(Jo(X))Y) BEO
Examples of commonly used surrogates are the hinge loss and the cross-entropy loss. Crucially, the inequality in (2) guarantees that the problem in (3) provides a solution that decreases the classification error (Bartlett et al., 2006), which, as discussed above, is the primary goal in supervised classification.
2.2 THE PERVASIVE SETTING OF ADVERSARIAL EXAMPLES
For common hypothesis classes, it is well-knows that classifiers obtained by solving (3) are sensitive to adversarial examples (Szegedy et al., 2013; Biggio et al., 2013), i.e., given an instance label pair
(X, Y), it is relatively straightforward find perturbations vj E IRd with small norm ||vl| S for some fixed 6 > such that
arg max fx(X), =Y and <E[K]
arg max fe + +)) of arg max fo (X): <E(K)
(4)
(E(K]
The task of finding such perturbations 7) which cause the classifier to misclassify perturbed data points X - can be compactly cast as the following maximization problem:
11" E arg max mllaalsee
arg max fo(X + n)4 } [E[K]
Here, both of the expressions in (4) hold for the perturbation X + '7 is called adversarial example for fo with respect to the instance-label pair (X, Y).
'7",, then the perturbed instance
Due to prevalence of adversarial examples, there has been pronounced interest in solving the robust analog of (1), which is designed to find classifiers that are insensitive to small perturbations. This robust analog ubiquitously written as the following a two-player zero-sum game with respect the discontinuous classification error:
arg max fo(X + m)) + xx]] xE[K]
min E AEB
max villlls
An optimal solution 8* for (6) yields model fo- that achieves the lowest possible classification error despite the presence of adversarial perturbations. For this reason, this problem-wheree the interplay between the maximization over 1 and the minimization over 0 comprises two-player zero-sum game- the starting point for numerous algorithms which aim to improve robustness.
2.3 SURROGATE-BANE BASED APPROACHES TO ROBUSTNESS
As discussed in $ 2.1, the discontinuity of the classification error complicates the task of finding adversarial examples, in (5), and of training against these perturbed instances, as in (6). One appealing approach toward overcoming this pitfall is to simply deploy a surrogate loss in place of the classification error inside (6), which gives rise to the following pair of optimization problems:
17" arg max (fo(X 1Xx+00 Y) wllnllse
min 8E8
max E(fo(X + n),
(8)
Indeed, this searooate--assee approach is pervasive in practice. Madry al.'s seminal paper on the subject of adversarial training employs this formulation (Madry et al., 2018). which has subsequently been used as the starting point for numerous AT schemes (Huang et al., 2015; Kurakin et al., 2017).
Pitfalls of surrogate- based optimization. Despite the intuitive appeal of this paradigm, surrogate- based adversarial attacks known to overestimate robustness (Mosbach et al., 2018; Croce et al., 2020b; Croce & Hein, 2020), and standard adversarial training algorithms are known to fail against strong attacks. Furthermore, this formulation suffers from pitfalls such as robust overfitting (Rice et al., 2020) and trade-offs between robustness and accuracy (Zhang et al., 2019). To combat these shortcomings, empirical adversarial attacks and defenses have increasingly relied on heuristics such as multiple restarts, variable learning rate schedules (Croce & Hein, 2020), and carefully crafted initializations, resulting in a widening gap between the theory and practice of adversarial learning. In the next section, argue that these pitfalls can be attributed to the fundamental limitations of (8).
3

---

Published as a conference paper at ICLR 2024
3 NON-ZERO-SUM FORMULATION OF ADVERSARIAL TRAINING
From an optimization perspective, the surrogate-based approaches to adversarial evaluation and training outlined in $ 2.3 engenders two fundamental limitations.
Limitation Weak attackers. the adversarial evaluation problem of (7), the adversary maximizes an upper bound on the classification error. This means that any solution 7" to (7) is not guaranteed to increase the classification error in (5), resulting adversaries which are misaligned with the goal of finding adversarial examples. Indeed, when the surrogate is an upper bound on the classification error, the only conclusion about the perturbation vy" obtained from (7) and its true objective (5) is:
arg max fo(X 17"); ) (E[K]
max e(fo(X + +). Tllnlls
Notably, the RHS of (9) can be arbitrarily large while the left hand side can simultancously be equal to zero, i.e., the problem in (7) can fail to produce an adversarial example, even at optimality. Thus, while it is known empirically that attacks based on (7) tend to overestimate robustness (Croce & Hein, 2020), this argument shows that this shortcoming is evident priori.
Limitation I:: Ineffective defenders. Because attacks which seek to maximize upper bounds on the classification error are not proper surrogates for the classification error (c.f., Limitation I), training a model fe on such perturbations does not guarantee any improvement in robustness. Therefore, AT algorithms which seek to solve (8) are ineffective in that they do not optimize the worst-case classification error. For this reason, it should not be surprising that robust overfitting (Rice et al., 2020) occurs for models trained to solve eq. (8).
Both of Limitation and Limitation II arise directly by virtue of rewriting (7) and (8) with the surrogate loss l. To illustrate this more concretely, consider the following example.
Example 1. Let 0 be given, let K denote the number of classes in classification problem, and let denote the cross-entropy loss. Consider two possible logit vectors of class probabilities:
= = (1/K + c, - c. 1///K....,///))
BB (0.5 c, 0.5 + -,, e,O.....0)
(10)
Assume without loss of generality that the correct class is the first class. Then Z does not lead to an adversarial example, whereas 2B does. However, observe that E(ZA, 1) = - log + c), which (0.5 tends to oc as K > 20 and c - O. In contrast, E(zg. - log (0.5 - c) which remains bounded as c c- Hence, an adversary maximizing the cross-entropy will always choose A over zg and will therefore fail to identify the adversarial example.
Therefore, to summarize, there a distinct tension between the efficient, yet misaligned paradigm of surrogate- basee adversarial training with the principled, yet intractable paradigm optimization on the classification error. In the remainder of this section, we resolve this tension by decoupling the optimization problems of the attacker and the defender.
of minimax
3.1 DECOUPLING ADVERSARIAL ATTACKS AND DEFENSES
Our starting point is the two-player zero-sum formulation in (6). Observe that this minimax optimiza- tion problem can be equivalently cast as bilevel optimization problem':
min I
E arg max fo (X + 17" Y
(11)
xE[R]
subject to 17 E arg max
arg max fo + n): # iE(K)
(12)
While this problem still constitutes a zero-sum game, the role of the attacker (the constraint in (12)) and the role of the defender (the objective in (11)) are now decoupled. From this perspective, the tension engendered by introducing surrogate losses is laid bare: the attacker ought to maximize lower bound on the classification error (c.f., Limitation I), whereas the defender ought to minimize an upper bound on the classification error (c.f., Limitation II). This implies that to preserve guarantees
'To be precise, the optimal value 1)" in (17) is function of (X, Y). ie.. n) = 'X,,,,)) Y). and the constraint must hold for almost every (X, Y) D. We omit these details for ease of exposition.
4

---

Published as a conference paper at ICLR 2024
optimality, the attacker and defender must optimize separate objectives. In what follows, discuss these objectives for the attacker and defender in detail.
The attacker's objective. We first address the role of the attacker. To do so, we define the negative margin M,(X, (X, Y) of the classifier fa as follows:
Mg : x y + IR.,
(X), & f - fx(
(13)
We call M, ) the negative margin because a positive value (13) corresponds to misclassifica- tion. As show in the following proposition, the negative margin function (which is differentiable) provides an alternative characterization of the classification error.
Proposition 1. Given a fixed data pair (X, Y), let 1f" denote any maximizer of Ma + n, Y)₃ over the classes j E [K] (Y) and perturbations E R satisfying |lvll 6, i.e.
(i*.n"))
arg max jE(K)-(Y), [[v] Se
Ma + +. M),)
(14)
Then if Ma(X + 17", Y), > 0, T/" induces misclassification and satisfies the constraint in (12), meaning that X + 1f" is an adversarial example. Otherwise, if Ma(X + ,,,,,, Y)₂- S O, then any ||ll| < e satisfies (12), and no adversarial example exists for the pair (X, Y). In summary, if n* as eq. (14), then 1j" solves the lower level problem eq. (12).
We present a proof in appendix A Proposition implies that the non-differentiable constraint in (12) can be equivalently recast as an ensemble of K differentiable optimization problems that can be solved independently. This can collectively expressed as
arg max v. [l jE[K]-(Y)
Mo + n.
(15)
Note that this does not constitute a relaxation; (12) and (15) are equivalent optimization problems. This means that the attacker can maximize the classification error directly using first-order optimiza- tion methods without resorting to a relaxation. Furthermore, Appendix D, we give an example of a scenario wherein solving (15) retrieves the optimal adversarial perturbation whereas maximizing the standard adversarial surrogate fails do so.
The defender's objective. Next, we consider the role of the defender. To handle the discontinuous upper-level problem in (11), note that this problem is equivalent supervised learning problem in (I), As discussed in $ 2.1, the strongest results for problems of this kind have historically been achieved by means of surrogate-based relaxation. Subsequently, replacing the 0-1 loss with a differentiable upper bound like the cross-entropy principled, presartee-rreserving approach for the defender.
perturbed version of the
3.2 PUTTING THE PIECES TOGETHER: NON-ZERO-SUE ADVERSARIAL TRAINING
By combining the disparate problems discussed in the preceeding section, arrive novel non-zero-sum (almost-everyyhere) diffcrentiable formulation of adversarial training:
min lEe
E EE(so(X + t)
(16)
subject to
1)" E arg max In Se (E(K]-(Y)
Mx(X + n1,9),
(17)
Notice that the second level of this bilevel problem remains non-smooth due to the maximization over the classes j E [K] - (Y). To impart smoothness the problem without relaxing the constraint, observe that we can equivalently solve K distinct smooth problems the second level for each sample (X, Y), resulting in the following equivalent optimization problem:
min $eB
E E(fo(X + 7,)).
(18)
subject to
ni E arg max Mo (X + n,,)) n: Inllss
VJ K - (Y)
(19)
j arg max Me(a + 7), ]E(K]-(Y)
(20)
"This result is similar in spirit (Gowal al., 2019, Theorem 3.1). However, (Gowal et al., 2019, Theorem 3.1) only holds for linear functions, whereas Proposition holds for arbitrary function, fo-
5

---

Published as a conference paper at ICLR 2024
Algorithm 1: Best Targeted Attack (BETA)
Input: Data-label pair (a, y). perturbation size e, model fa. number of classes K, iterations Output: Adversarial perturbation 17"
function (ETA(Z, y, 6, So, for j E ,,..., K do
7) - max -,, 0), min(X + +e, e,
// Images are in [0,
for 1 1, ,..,, do
for j E I..... do Ui < OPTIM Vn. Ma(a +z.
// Optimization step
M < 11 (x((
// Project onto perturbation set
f- arg ja Mo(x n)
return M/
Algorithm 2: BETA Adversarial Training (BETA-AT)
Input: Dataset (X, Y = (I,;, yr) perturbation size e, model fe. number of classes K, iterations T, attack iterations T"
Output: Robust model fo- function BETA-AT(X, Y,,, Te ) for t E ,, "o'o do Sample ~ Unif[n]
"f" < (ET Mr, e, Jo, T") T.(0) + E(So(1, + "")),) 0 OPTIM(O, VL))))
Optimization step
return fo
Hence, in (20), we first obtain one perturbation 17, per class which maximizes the negative margin Ma(X- + 175 Y) for that particular class. Next, in (19), we select the class index j' corresponding to the perturbation vr that maximized the negative margin. And finally, the upper level, the surrogate minimization over 0 E θ is on the perturbed data pair (X + t/j/ Y). The result is non-zero-sum formulation for AT that amenable gradient-based optimization, and preserves the optimality guarantees engendered by surrogate loss minimization without weakening the adversary.
ALGORIHTS
Given the non-zero-sum formulation of AT, the next question is how one should solve this bilevel problem in practice. Our starting point the empirical version of this bilevel problem, wherein we assume access to a finite dataset {(z,, y:) of'n instance-label pairs sampled i.i.d. from D.
min eE0
(fo(a: + ny..) 1.8))
(21)
n
subject to
Mi arg max Mo (xt + n, +,
E [K] (Y)
(22)
wllallse
j E arg max Ma(#; + + y:);
Vi [n]
(23)
jE(R]-(xx
To solve this empirical problem, we adopt stochastic optimization based approach. That is, we first iteratively sample mini-batches from our dataset uniformly at random, and then obtain adversarial perturbations by solving the lower level problems in (22) and (23). Note that given the differentiability of the negative margin, the lower level problems can be solved iteratively with generic optimizers, e.g., Adam (Kingma& & Ba, 2014) or RMSprop. This procedure is summarized Algorithm 1, which call the BEst T Targeted Attack (BETA), given that it directly maximizes the classification

---

Published as a conference paper at ICLR 2024
Train Robust
Train Clean
Train Robasi
Train Clean
Test Robust
Test Clean
Test Robust
Test Clean
75
75
Accuracy
Accuracy
50
50
25
25
0
50
100
0
50
100
Epoch
Epoch
(a) PGD 10 learning curves.
(b) BETA-AT learning curves.
Figure 1: BETA does not suffer from robust overfitting, We plot the learning curves against a PGD20 adversary for PGD10 and BETA-AT Observe that although PGD displays robust overfitting after the first learning rate decay step, BETA-AT does not suffer from this pitfall.
After obtaining such perturbations, we calculate the perturbed loss in (21), and then differentiate through this loss with respect to the model parameters. By updating the model parameters A in the negative direction of this gradient, our algorithm seeks classifiers that are robust against perturbations found by BETA. We call the full adversarial training procedure based on this attack BETA Adversarial Training (BETA-AT),
it invokes BETA subroutine; Algorithm 2 for details. Also see Figures 2 and in the appendix for an empirical study of the computational complexity of BETA.
5 EXPERIMENTS
In this section, we evaluate the performance of BETA and BETA-AT on CIFAR-10 (Krizhevsky et al., 2009). Throughout, we consider range of AT algorithms, including PGD (Madry et al., 2018), FGSM (Goodfellow et al., 2015), TRADES (Zhang et al., 2019), MART (Wang et al., 2020), as well as a range of adversarial attacks, including APGI) and AutoAttack (Croce & Hein, 2020). We consider the standard perturbation budget of = 8/ //255, and all training and test-time attacks use a step size of a = 2/255. For both TRADES and MART, we set the trade-off parameter X = 5, which consistent with the original implementations (Wang et al., 2020; Zhang et al., 2019).
The bilevel formulation eliminates robust overfitting. Robust overfitting occurs when the robust test accuracy peaks immediately after the first learning rate decay, and then falls significantly in subsequent epochs as the model continues to train (Rice et al., 2020). This is illustrated in Figure la, in which we plot the learning curves (i.e., the clean and robust accuracies for the training and test sets) for a ResNet- 8 (He et al., 2016) trained using 10-step PGD against 20-step PGD adversary. Notice that after the first learning rate decay at epoch 100, the robust test accuracy spikes, before dropping off in subsequent epochs. On the other hand, BETA-AT does not suffer from robust overfitiing as shown in Figure lb. We argue that this strength of our method is a direct result of our bilevel formulation, in which we train against proper surrogate for the adversarial classification error.
BETA-AT outperforms baselines on the last iterate of training. We next compare the performance of ResNet-18 8 models trained using four different AT algorithms: FGSM, PGD, TRADES, MART, and BETA. BGDA TRADES, and MART used 10-step adversary at training time. At test time, the models were evaluated against five different adversaries: FGSM, 10-step PGD, 40-step PGD, 10-step BETA, and APGD. We report the performance of two different checkpoints for each algorithm: the best performing checkpoint chosen by early stopping on a held-out validation set, and the performance of the last checkpoint from training. Note that while BETA performs comparably algorithms with respect to early stopping, it outperforms these algorithms significantly when the test-time adversaries attack the last checkpoint of training. This owes to the fact that BETA does not suffer from robust overfitting, meaning that the last and best checkpoints perform similarly.
the baseline
BETA matches the performance of AutoAttack. AutoAttack is state-of-ther -ftth--rrttttttt attack which is widely used to estimate the robustness of trained models on leaderboards such as RobustBench (Croce
7

---

Published as a conference paper at ICLR 2024
Table 1: Adversarial performance on CIEAR-10. We report the test accuracies of various AT
algorithms against different adversarial attacks on the CIFAR-10 dataset.
Training algorithm
Test accuracy
Clean
FGSM
PGD
PGD
BETA
APGD
Best
Last
Best
Last
Best
Last
Best
Last
Best
Last
Best
Last
FGSM
75.43
94.26
94.22
42.64
42.66
1.62
40.30
41.56
0.00
PG
83.71
83.21
51.98
47.39
46.74
39.90
45.91
39.45
43.64
40.21
44.36
42,62
TRADES
81.64
81.42
52.40
51.31
47.85
42.31
47.76
42.92
44.31
40.97
43.34
41.33
MORT
78.80
77.20
53.84
53.73
49.08
41.12
48.41
41.55
44.81
41.22
45.00
42,90
BETA-ATS
87.02
86.67
51.22
51.10
44.02
43.22
43,94
42.56
42.62
42.61
41.44
41.02
BETA-AI A
85.37
85.30
51.42
45.67
45.39
45.22
45.00
44.54
44.32
44.12
BETA-AT
82.11
81.72
54.01
53.99
49.96
48.67
49.20
48.70
46.91
45,90
45.27
45.25
Table 2: Estimated & robustness (robust test accuracy). BETA+RMSprop (ours) APGD- targeted (APGD-T) vs AutoAttack (AA). CIFAR-10. BETA and APGD-T use 30 iterations + single restart. = 8/255. AA uses 4 different attacks with 100 iterations and 5 restarts.
Model
BETA
APGD-T
AA
BETA/AA gap
Architecture
Wang al. (2023)
70.78
70.75
70.69
0.09
WRN-70-16
Wang al. (2023)
67.37
67.33
67.31
0.06
WRN-28-10
Rebufli et al. (2021)
66.75
66.71
66.58
0.17
WRN-70-16
Gowal al. (2021)
66.27
66.26
66.11
0.16
WRN-70-16
Huang al. (2022)
65.88
65.88
65.79
0.09
WRN-A4
Rebulli et al. (2021)
64.73
64.71
64.64
0.09
WRN-106616
Rehuffi et al. (2021)
64.36
64,27
64,25
0.11
WRN-70-16
Gowal al. (2021)
63.58
63.45
63.44
0.14
WRN-28-10 10
Pang et al. (2022)
63.38
63.37
63.35
0.03
WRN-70-16
et al., 2020a; Croce & Hein, 2020). In brief, AutoAttack comprises a collection of four disparate attacks: APGD-CE APGD-T, FAB, and Square Attack. AutoAttack also involves several heuristics, including multiple restarts and variable stopping conditions. Table 2, we compare the performance of the top-performing models on Robustßench against AutoAttack,, APGD-T, and BETA with RMSprop. Both APGD-T and BETA used thirty steps, whereas we used the default implementation of AutoAttack, which runs for 100 iterations. We also recorded the gap between AutoAttack and BETA. Notice that the 30-step BETA-a heuristic-free algorithm derived from our bilevel formulation of AT-performs almost identically to AutoAttack,, despite the fact that AutoAttack runs for significantly more iterations and uses five restarts, which endows Auto/Atack with unfair computational advantage. That is, excepting for a negligible number of samples, BETA matches the performance of AutoeGDDtargetedd and AutoAttack,, despite using off-the-shelf optimizer.
RELATED WORK
Robust overfitting. Several recent papers (see, e.g., (Rebuffi et al., 2021; Chen et al., 2021; Yu al., 2022; Dong et al., 2022; Wang et al., 2020; Lee et al., 2020)) have attempted explain and resolve robust overfitting (Rice et al., 2020). However, none of these works point to fundamental limitation of AT as the cause of robust overfitting. Rather, much of this past work has focused on proposing heuristics for algorithms specifically designed to reduce robust overfitting, rather than to improve AT. In contrast, we posit that the lack of guarantees of the zero-sum surrogate-based AT paradigm Madry al. (2018) is fault, as this paradigm is not designed to maximize robustness with respect to classification error. And indeed, our empirical evaluations in the previous section confirm that our non-zero-sum formulation eliminates robust overfitting.
Estimating adversarial robustness. There is empirical evidence that attacks based on surrogates (e.g., PGD) overestimate the robustness of trained classifiers (Croce & Hein, 2020; Croce et al., 2020b). Indeed, this evidence served as motivation for the formulation of more sophisticated attacks like AutoAttack (Croce & Hein, 2020), which tend to provide more accurate estimates of robustmess. In contrast, we provide solid, theoretical evidence that commonly used attacks overestimate robustness due to the misalignment between standard surrogate losses and the adversarial classification error. Moreover, show that optimizing the BETA objective with standard optimizer (e.g., RMSprop)
8

---

Published as a conference paper at ICLR 2024
achieves the same robustness AutoAttack without employing ad hoc training procedures such as multiple restarts. convoluted stopping conditions, or adaptive learning rates.
One notable feature of past work is an overservation made in (Gowal et al., 2019), which finds that multitargeted attacks tend to more accurately estimate robustness. However, their theoretical analysis only applies to linear functions, whereas our work extends these ideas to the nonlinear setting of DNNs. Moreover, (Gowal et al., 2019) do not explore training using multitargeted attack, whereas we show that BETA-AT is an effective AT algorithm that mitigates the impact of robust overfitting.
Bilevel formulations of AT. Prior to our work, (Zhang et al., 2022) proposed a different pseudo- bilevel formulation for AT, wherein the main objective was to justify the FastAT algorithm introduced in (Wong et al., 2020). Specifically, the formulation in (Zhang et al., 2022) is designed to produce solutions that coincide with the iterates of FastAT by linearizing the attacker's objective. In contrast, our bilevel formulation appears naturally following principled relaxations of the intractable classifica- tion error AT formulation. In this way, the formulation in (Zhang al., 2022) applies only in the context of Fast AT, whereas our formulation deals more generally with the task of AT.
In the same spirit as our work, (Mianjy & Arora, 2024) solve a problem equivalent to a bilevel problem wherein the adversary maximizes a "reflected" cross-entropy loss. While this paper focuses on binary classification, the authors show that this approach leads to improved adversarial robustness and admits convergence guarantees. Our approach, while related, is distinet in its reformulation of the adversarial training problem via the negative margin loss. Moreover, our results show that BETA mitigates robustness overfitting and is roughly five times effective as AutoAttack.
Theoretical underpinnings of surrogate minimization. In this paper, we focused on the empirical performance of AT in the context of the literature concerning adversarial examples in computer vision. However, the study of the efficacy of surrogate losses in minimizing the target 0-1 loss is a well studied topic among theorists. Specifically, this literature considers two notions of minimizers for the surrogate loss also minimizing the target loss: (1) consistency, which requires uniform convergence, and (2) calibration, which requires the weaker notion of pointwise convergence (although (Bartlett et al., 2006) shows that these notions are equivalent for standard, i.e., non aoneaaler,, classification).
In the particular case of classification in the presence of adversaries, (Bao et al., 2020) and (Meunier et al., 2022) claimed that for the class of linear models, no convex surrogate loss is calibrated with respect to the 0-1 zero-sum formulation of AT, although certain classes of nonconvex losses can maintain calibration for such settings. However, in (Awasthi et al., 2021), the authors challenge this claim, and generalize the calibration results considered by (Bao et al., 2020) beyond linear models. One interesting direction future work would be to provide a thcoretical analysis of BETA with respect to the margin-based consistency results proved very recently in (Frank & Niles- Weed, 2023). We also note that in parallel, efforts have been made to design algorithms that are approximately calibrated, leading to among other things- the TRADES algorithm (Zhang et al., 2019), which we compare to in Section Our work is the same vein, although BETA does not require approximating a divergence term, which leads to non-calibration of the TRADES objective.
7 CONCLUSION
In this paper, we argued that the surrogate-based relaxation commonly employed to improve the tractability of adversarial training voids guarantees on the ultimate robustness of trained classifiers, resulting weak adversaries and ineffective algorithms. This shortcoming motivated the formulation of a novel, yet natural bilevel approach to adversarial training and evaluation in which the adversary and defender optimize separate objectives, which constitutes non-zero-sum game. Based on this formulation, we developed a new adversarial attack algorithm (BETA) and a concomitant AT algorithm, which call BETA-AT. In our experiments, overfitting and we showed that even when carly stopping based model selection is used, BETA-AT performs comparably to AT. Finally, we showed that BETA provides almost identical estimates of robustness to AutoAttack.
showed that BETA-AT eliminates robust
"In a strict sense, the formulation of (Zhang et al., 2022) is not a bilevel problem. In general, the most concise way to write bilevel optimization problem is mine f(, 8" (f)) subject to 8 (0) E arg max g(0, 8). In such problems the value 8* (6) only depends on 6, as the objective function g(o, -) is then uniquely determined. This not the case in (Zhang et al., 2022, eq. (7)), where an additional variable appears, corresponding to the random initialization of Fast-AT. Hence, in (Zhang et al., 2022) the function g(, -) is not uniquely defined by 0. but is random function realized each iteration of the algorithm.
9

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
FL is funded (in part) through a PhD fellowship of the Swiss Data Science Center, a joint venture between EPFL and ETH Zurich. VC is supported by the Hasler Foundation Program: Hasler Responsible Al (project number 21043), the Army Research Office under grant number W911NF- 24-1-0048, and the Swiss National Science Foundation (SNSF) under grant number 200021-205011. AR, HH, and GP are supported by the NSF Institute for CORE Emerging Methods in Data Science (EnCORE), AR is also supposed by an ASSET Amazon AWS Trustworthy Al Fellowship.
10

---

Published as a conference paper at ICLR 2024
REFERENCES
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprini arXiv: (00.::9907.229999 2019.
Pranjal Awasthi, Natalie Frank, Anqi Mao, Mehryar Mohri, and Yutao Zhong. Calibration and
consistency of adversarial surrogate losses. Advances in Neural Information Processing Systems, 34:9804 9815, 2021. 9
Han Bao, Clay Scott, and Masashi Sugiyama. Calibrated surrogate losses for adversarially robust classification. In Conference on Learning Theory, pp. 408-451. PMLR. 2020. 9
Jonathan Bard. Practical bilevel optimization: algorithms and applications, volume 30, Springer Science & Business Media, 2013. 2
Peter I. Bartlett, Michael Jordan, and Jon D McAuliffe. Convexity, classification,, and risk bounds. Journal of the American Statistical Association, 101(473): 2006. doi: 10.1198/ 0162145050000000007 URL /tttps:/ddo..oo/////// 3.9
1,
B. Biggio, I. Corona, D. Maiorca, B. Nelson, N. Smdic, P. Laskov, G. Giacinto, and F. Roli. Evasion attacks against machine learning test time. In ECML/PKKD, 2013. 1,3
Alvin Chan, Yi Tay, Yew Soon Ong, and Jie Fu. Jacobian adversarially regularized networks for robustness. ICLR, 2020. 2
Lin Chen, Yifei Min, Mingrui Zhang, and Amin Karbasi. More data can expand the generalization gap between adversarially robust and standard models. In International Conference on Machine Learning, pp. 1670-1680. PMLR, 2020. 2
Tianlong Chen, Zhenyu Zhang, Sijia Liu, Shiyu Chang, and Zhangyang Wang. Robust overfitting may be mitigated by properly learned smoothening. In International Conference Learning Representations, 2021. URL https: / opw.revieweeeeeeeeeeeeeee net/ foree//orummeae 2aa.ecuumiiiggggayuu2222222
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free free attacks. In International conference on machine learning, pp. 2206-2216. PMLR, 2020. 2, 3, 4, 7,8
Francesco Croce, Maksym Andriushchenko, Vikash Sehwag. Edoardo Debenedetti, Nicolas Flam- marion, Mung Chiang. Prateek Mittal, and Matthias Hein. Robustbench: standardized adversarial robustness benchmark. arXiv preprint arXiv:2010.09670 2020a. 1,
Francesco Croce, Jonas Rauber, and Matthias Hein. Scaling up the randomized gradient-fre adversarial attack reveals overestimation of robustness using established attacks. International 2020b. 3,
Journal of Computer Vision, 12881028-111
Edgar Dobriban, Hamed Hassani, David Hong, and Alexander Robey. Provable tradeoffs in adversar- ially robust classification. arXiv preprint arXiv:2006.05161 2020. 2
Yinpeng Dong, Ke Xu, Xiao Yang. Tianyu Pang. Zhijie Deng, Hang Su, and Jun Zhu. Exploring memorization in adversarial training. In International Conference on Learning Representations, 2022. URL https: / wwt.oopeervviiieeeee ew. n fo corum?i 775.mm/
Natalie Frank and Jonathan Weed. The adversarial consistency of surrogate risks for binary classification, arXiv preprint arXiv:2305.09956, 2023. 9
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In ICLR, 2015. 1,7
Sven Gowal, Jonathan Uesato, Chongli Qin, Po-Sen Huang, Timothy Mann, and Pushmeet Kohli. An alternative surrogate loss for pgd-based adversarial testing. arXiv preprint arXiv: 1x1.00990 2019. 5.
Sven Gowal, Sylvestre-Alvise Rebuffi, Olivia Wiles, Florian Stimberg, Dan Andrei Calian, and Timothy Mann. Improving robustness using generated data. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https:://////..... https://opeerevieeee net /fre/fooraee forum?i d= 16o... 8

---

Published as a conference paper at ICLR 2024
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CVPR, 2016.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. In International Conference Learning Representations, 2019. 1
Ruitong Huang, Bing Xu, Dale Schuurmans, and Csaba Szepesvari. Learning with a strong adversary. ArXiv, abs//511..00 151.0344,, 2015. 3
Shihua Huang, Zhichao Lu, Kalyanmoy Deb, and Vishnu Naresh Boddeti. Revisiting Resid- ual Networks for Adversarial Robustness: An Architectural Perspective. arXiv e-prints, art. arXiv:2212.1 1005, December 2022. doi: 10.48550/rXxi.2222210003 8
H. Kannan, A. Kurakin, and I. Goodfellow.
Adversarial logit pairing. arXiv preprint
MrXiv:1803.06377 2018. 2
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.698,, 2014.
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Bal- subramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, al. Wilds: A benchmark of wi-the-wild distribution shifts. In International Conference on Machine Learning.
pp. 5637-5664. PMLR, 2021. 1
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar datasets (canadian institute for advanced research). 2009. URL http: /www. cs www.cnttt.du//kriiiiia. ciffr .tml. 7
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial examples in the physical world. ICLR Workshop, 2017. URL https: http:////pppereeeeeeeeee/toooor nwt./orumm HUGHHGGU3-HHH- 3
Cassidy Laidlaw, Sahil Singla, and Soheil Feizi. Perceptual adversarial robustness: Defense against unseen threat models. arXiv preprint arXiv:2006. 1200006..6655. 12655, 2020.
Fabian Latorre, Igor Krawezuk, Leello Tadesse Dadi, Thomas Pethick, and Volkan Cevher. Finding ac- tual descent directions for adversarial training. In The Eleventh International Conference on Learn- ing Representations, 2023. URL https: : http:::://ppeevveeeeeeeee wwt.:entttoooeeee I 78H.
Sachyung Lee, Hyungyu Lee, and Sungroh Yoon. Adversarial vertex mixup: Toward better adversari- ally robust generalization. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), June 2020. 8
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018. 3, 7,8
Laurent Meunier, Raphaël Ettedgui, Rafael Pinot, Yann Chevaleyre, and Jamal Atif. Towards consistency in adversarial classification. Advances in Neural Information Processing Systems, 35: 8538-8549, 2022, 9
Poorya Mianjy and Raman Arora. Robustness guarantees for adversarially trained neural networks. Advances in Neural Information Processing Systems, 36, 2024.7
Marius Mosbach, Maksym Andriushchenko, Thomas Trost, Matthias Hein, and Dietrich Klakow, Logit pairing methods can fool gradient-basee attacks. arXiv preprint arXiv: 12042, 2018. 3
Tianyu Pang. Min Lin, Xiao Yang, Jun Zhu, and Shuicheng Yan. Robustness and accuracy could be reconcilable by (Proper) definition. In Kamalika Chaudhuri, Stefanic Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 17258-17277. PMLR, 17-23 Jul 2022. URL https: httppppeooeeeng/e///ee//e/ee/.tt mlr. www.ppresssleeeeee pang22a. html.
Sylvestre-Alvise Rebuffi, Sven Gowal, Dan A. Calian, Florian Stimberg, Olivia Wiles, and Tim- othy Mann. Fixing data augmentation to improve adversarial robustness. arXiv preprint ar3iv:2103.01946, 2021. 8
12

---

Published as a conference paper at ICLR 2024
Leslie Rice, Eric Wong, and J Zico Kolter. Overfitting in adversarially robust deep learning. In ICML, 2020. 2, 3, 7.8
Alexander Robey, George J Pappas, and Hamed Hassani. Model-based domain generalization. Advances in Neural Information Processing Systems, 34:20210- 20229, 2021. 1
Nicolas Le Roux. Tighter bounds lead to improved classifiers. In International Conference on Learn- ing Representations. 2017. URL https: cptpreveeeeeeeeeeee/eeeee htt.:eeww.eeetteureeeeeee Hy=HyAbMKwx..
Shibani Santurkar, Dimitris Tsipras, and Aleksander Madry. Breeds: Benchmarks for subpopulation shift. International Conference on Learning Representations, 2021.
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Ad- versarially robust generalization requires more data. Advances in neural information processing systems, 31, 2018. 2
Shai
and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014. 1,2
Xu Sun, Zhiyuan Zhang. Xuancheng Ren, Ruixuan Luo, and Liangyou Li, Exploring the vulnerability of deep neural networks: A study of parameter corruption. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 11648-11666, 2021.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Dumitru Erhan Joan Bruna, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In ICLR, 2013. 1,
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be odds with accuracy. In ICLR, 2019.
Yisen Wang, Difan Zou, Jinfeng Yi, James Bailey, Xingjun Ma, and Quanquan Gu. Improving adversarial robustness requires revisiting misclassified examples. ICLR, 2020. 7,8
Zekai Wang, Tianyu Pang, Chao Du, Min Lin, Weiwei Liu, and Shuicheng Yan. Better diffusion models further improve adversarial training. arXiv preprint arXiv:2302.04663, 2023. 8
Eric Wong, Leslie Rice, and J. Zico Kolter. Fast is better than free: Revisiting adversarial training. ICLR, 2020.
Dongxian Wu, Shu tao Xia, and Yisen Wang. Adversarial weight perturbation helps robust general- ization. NeurIPS, 2020. 2
Kai Xiao, Logan Engstrom, Andrew Ilyas, and Aleksander Madry. Noise signal: The role of image backgrounds in object recognition. International Conference on Machine Learning, 2021.
Chaojian Yu, Bo Han, Li Shen, Jun Yu, Chen Gong, Mingming Gong, and Tongliang Liu. Un- derstanding robust overfitting of adversarial training and beyond. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceed- ings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 25595-25610. PMLR, 17-23 Jul 2022. URL https: // //proceedings..ot mir www.sp.eea.......... vllll/l2/////// htt//yu22bbbbee html. 8
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing, Laurent El Ghaoui, and Michael I. Jordan. Theoretically principled trade-off between robustness and accuracy. In ICML, 2019. 3, 7,9
Yihua Zhang, Guanhua Zhang, Prashant Khanduri, Mingyi Hong, Shiyu Chang, and Sijia Liu. Revisiting and advancing fast adversarial training through the lens of bi-level optimization. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 26693-26712. PMLR, 17-23 Jul 2022. URL https:/ pttp///cceeiiccccccoooooo mlr. .presspesss............ / /vl/vv22/////// /2l6222hhag22a2l html. 9
13

---

Published as a conference paper at ICLR 2024
Appendices
Table of Contents
A Proof of propesition
15
B Smooth reformulation of the lower level
16
Running time analysis
C.I Speed-performant trade-off
19
C.2 Evaluation running time analysis
19
Utility of maximizing the surrogate loss
20
14

---

Published as a conference paper at ICLR 2024
A PROOF OF PROPOSITION 1
Suppose that there exists 1 satisfying |li Mc(X + Y), 0. That is, assume that
S e such that for some j E [K], j # Y we have
max
Ma(X + >) 0
(24)
S
and for some f and some j we have fo(X + f)} > fx( + f)r, which implies that arg [ax fo(X + -il Y. Hence, induces misclassification error, i.e.
f E arg max arg max fe(X + +1l # Y S jE[K]
(25)
1: 5l
In particular, if
("n)"))
arg max jE[K] (Y), milllse
MM X + 17. Y)
(26)
then it holds that Otherwise, if it holds that
1/ E arg max velle
arg max fo(X + +11 #Y jEIK]
(27)
max
Mx(X 77 Y); <
(28)
jE(K] (Y), s
then for all 77 |, < e and all j * Y, we have fo(X + 1) < folX + n)y. so that arg [aj] fo(x + n)j Y, i.e. there is no adversarial example in the ball. In this case, for any if it holds that
(i',m") E
arg max ve(llls mllnnlse
MX + m,, Y),
(29)
then
arg fo + + * jE[K]
max m mnllaae
arg max fo(X + m)) #Y jE[K]
(30)
In conclusion, the solution
(T"mn")
arg max xE(K]-Y)) mllllle
Mo(X + +n,
(31)
always yields maximizer of the misclassification error.
15

---

Published as a conference paper at ICLR 2024
Algorithm 3: Smooth BETA Adversarial Training (SBETA-AT)
Input:
Dataset (X, Y = (I,, y1) perturbation size c, model fe. number classes K. iterations T, attack iterations T", temperature μ 0
Output: Robust model Jo-
function SBETA-AT X, v,,, 7,11
for e L......2 do
Sample ~ Unif[n]
Initialize f)₃ ~ Unif[max(O, x; - E), min(x; + 6, 1jj Vj [K]
for j E 1, ...., do
for 1......' do t OPTIM Mo, + 755 m))j) [eg.,te.)njo.pp
(attack optimizer step, e.g., RMSprop)
> (Projection onto valid perturbation set)
K Compute L(0) Lj=1jAn E Dimi.o MoMolsttnnerr ((fo + nz), vs)
10
O VL(())
& (model optimizer step)
return 11
B SMOOTH REFORMULATION OF THE LOWER LEVEL
First, note that the problem in eqs. (21) to (23) is equivalent to
min 8EB n
Xye(Jolx (6y),
(32)
K Xi Mo(x; + T.g.
subject to Xij. ml E
arg max
Vi e [n]
Inells Nug |A 1,1, 1,y
This is because the maximum over X; in eq. (32) is always attained the coordinate vector e, such that Ma(a; + Mi Ut) is maximum.
An alternative is to smooth the lower level optimization problem by adding an entropy regularization:
Ma(x + nj 0), = max max (A, Mo(o + 7h ,)
max
max -
K
elllllse 120.I|A (A, Molo + Th w)
max
\ log(As)
1
K
max wllalsse μ
log
MMooX+
(33)
where μ > 0 is some temperature constant. The inequality here is due to the fact that the entropy of discrete probability À is positive. The innermost maximization problem (33) has the closed-form solution:
wuMolatnswhs
: # y,
X ==
(34)
16

---

Published as a conference paper at ICLR 2024
Hence, after relaxing the second level maximization problem following eq. (33), and plugging in the optimal values for we arrive at:
K
min BEE
((ooa: + n1))),))
n
Σ y== (aMoo
1=
1=1
(35)
jyy
37
subject Vii
arg max Ma (z; Mish 11 l
vi [m], E [K]
min 0EG
MlM ((folz; + ni.).1)
(36)
1
1=1
341
subject to
Mij arg max Mo(r; + m,))))
Vi E [n]]
(37)
vill
In this formulation, both upper- and lower-level problems are smooth (barring the possible of nonsmooth components like ReLU). Most importantly (I) the smoothing is obtained through a lower bound of the original objective in eqs. (22) and (23), retaining guarantees that the adversary will increase the misclassification error and (II) the adversarial perturbations obtained for each class now appear in the upper level (36), weighted by their corresponding negative margin. In this way, we make efficient use of all perturbations generated: if two perturbations from different classes achieve the same negative margin, they will affect the upper-level objective in fair proportion. This formulation gives rise algorithm 3.
17

---

Published as a conference paper at ICLR 2024
Model selection: Early stop
Model selection: Last step
50
20
20
48
820
46
10
10
Accuracy
Algorithm
e5
BETA
5
PGD
+5
TRADES
9920
42
20
10
38
200
400
600
200
400
600
Epoch time (s)
Epoch time (s)
Figure 2: Adversarial training performance-speed trade-off. Each point is annotated with the number of steps with which the corresponding algorithm was run. Observe that robust overfitting eliminated by BETA, but that this comes at the reveals an expected performance-speed trade-off for our algorithm.
of increased computational overhead. This
Adversarial Evaluation Timing Comparison
Wang2023Better, WRN-70-16
Algorithm
BETA
Viang2023Better: WRN-28-10
AutoAttack
Rebuffi2021Rxinng_ 70, 20_16_cutmix
Gowal2021lmproving___ ddpm,
Huang2022Revisitnnggg WRN-A4
Rebuffi2021fixing_uu cutmix, ddpm
Reburf20211iixnng_00 cutmixtttcoo ddpm
Gowal2021Imprroinng_ee ddpm_ 100m
Pang20ZZRobustness, R
1000
Time (s)
Figure Adversarial evaluation timing comparison. The running time for evaluating the top models on RobustBench using AutoAttack and BETA with the same settings as Table 2 are reported. On average, BETA 5,11 times faster than AutoAttack.
18

---

Published as a conference paper at ICLR 2024
C RUNNING TIME ANALYSIS
C.I. PEIEDD-PRFFRMNCCE TRADE-OFF
In Figure 2, analyze the trade-off between the rumning time and performance of BETA. Specifically. on the horizontal axis, we plot the running time (in seconds) of an epoch BETA, and on the vertical axis plot the performance measured via the robust accuracy with respect to 20-step PGD adversary. We compare BETA to PGD and TRADES, and we show the spred-performance trade-off' when each of these algorithms are run for 5, 10, and 20 iterations; the iteration count is labeled next each data point. The leftmost panel shows early stopping model selection, and the rightmost panel shows last iterate model selection. Notice that while BETA is significantly more resource intensive than PGD and TRADES, BETA tends outperform the baselines, particularly if one looks at the gap between early stopping and last iterate model selection.
C.2 EVALUATION RUNNING TIME ANALYSIS
We next analyze the running time of BETA when used as to adversarially evaluate otatc-of-the- art robust models. In particular, we return to the setting of Table 2, wherein we compared the performance of AutoAttack to BETA. In Figure 3, we show the wall-clock time of performing adversarial evaluation using both of these algorithms. Notice that AutoAttack takes significantly longer to evaluate each of these models, and as we showed in Table 2, this additional time does not yield better estimate of the robustness of these models. Indeed, by averaging over the scores in Figure 1b, we find that BETA is 5.1 faster than AutoAttack on average.
19

---

Published as a conference paper at ICLR 2024
D UTILITY OF MAXIMIZING THE SURROGATE LOSS
In this appendix, we show that there exists cases in which our margin- inner maximization retrieves the optimal adversarial perturbation while the standard inner max with the surrogate loss fails to do so. this example, we consider a classification problem in which the classifier f R - R3 is linear across three classes {1, 3... Specifically we define f in the following way:
0 -1 0
(38)
322
Furthermore, let c 0.8, let (I1, (0, -1), and assume without loss of generality that the correct class is y = 1. The solution for the maximization of cross-entropy loss is given by:
e'
max $0.8
t),
= max - log el-m 72 + E t1 I $0.8
(39)
e
where l denotes the cross entropy loss. Now observe that by the monotonicity of the logarithm function, this problem the right- sid- is equivalent to the following problem:
n + t
min In el 12 + + e
1
max Illl
(40)
el-12
+ e
max Im $0.8
max
(41)
e1-w
where in the final step split the problem that we optimize separately over ?n and 122- Observe that the inner problem, for which the numerator constant, satisfies the following:
max Im 0.88 of
min
min Ina Imlls 0.8 of
7/2
(42)
e 11-92
Inlss 0..8
As the objective is linear in the rightmost optimization problem, it's clear that no Now returning to (41), we substitute n/ and are therefore left to solve the following problem:
v
0.8
np
+
max (e-t 7h + e JeVo.82-n
max 00.8 e 0.8
(43)
20.8
e 0 t
max US 1--00.8-1f
(44)
where in the final step used the fact that the objective is symmetric in m. By visual inspection, this function achieves its maximum at 17 (see Figure 4). Hence, the optimal perturbation obtained via cross-entropy maximization is r7" = (0, 0.8). Therefore,
(I1, x2) (n/: 1/5 = (0, 1) + (0, 0.8) (0, -0.2)
Then, by applying the classifier f. we find that
0
1
0.2
S(0, 0.2)
-1
0 0
(45)
0.2
This shows that the class assigned to this optimally perturbed example is still the correct class y i.e., the attacker fails to find an adversarial example. In contrast, the main idea in the derivation the BETA algorithm is to optimize the margins separately for both possible incorrect classes y 2 and y = In particular, for the class y = 2, BETA solves the following problem:
max ([-1,0] - (0 1l) (x 77)
(46)
|/ 50.s
The point 7 = 1-0.8, V2 is optimal for this linear problem. On the other hand, for the class y 3, BETA solves the following problem:
max ([1,0) - [0 - 1J) (ar + n)
(47)
10.8
20

---

Published as a conference paper at ICLR 2024
-2
Figure Plot of function to be maximized in eq. (44). We subtract y = 2.5 for ease of viewing
The point 17 0.8...8/v2. is optimal for this problem. Observe that both achieve the same value of the margin, so BETA can choose either optimal point; without loss of generality, assume that BETA chooses the second point 17' [0.8, 0.8]/v2 / as the optimal solution. The corresponding classifier takes the following form:
0.8/V2
/008/V2.08//2-11)
-1
(48)
0.8/22
0.8/22
-08/v2
(49)
0.8/22
0.43
0.57
(50)
0.57
Hence, the classifier returns the incorrect class, i.e., the attack is successful. This shows that whereas the cross-entropy maximization problem fails to find an adversarial example, BETA succeeds in finding an adversarial example.
21


Reviews:
[{"review_id": "50MdplYHcX", "reviewer": "Reviewer_DH4f", "summary": "This paper proposed a robust training (AT) algorithm for deep neural networks. Different from most existing two-player zero-sum AT algorithms in which the attacker and defender simultaneously optimized the same objective, the proposed AT algorithm is formulated in a novel non-zero-sum fashion, where the attacker and defender optimized separate objectives. This separated scheme prevents the proposed AT algorithm from robust overfitting.", "questions": "1. In Table 1. Why does BETA-AT$^{20}$ have lower test accuracy than BETA-AT$^{10}$ for clean data?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed method resolves the issue of robust overfitting that is faced in existing zero-sum AT algorithms.\n2. The paper is very well-written. The presentation is clear and easy to understand.\n3. This paper points out the fundamental limitation in the popular zero-sum AT methods and provides a new non-zero-sum AT method, which would be an interesting future research direction for robust training.", "weaknesses": "1. The proposed AT algorithm has higher time complexity compared to zero-sum AT algorithms such as PGD, FGSM and TRADES.", "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": "", "extra_scores": {}}, {"review_id": "wUGmRTKYSe", "reviewer": "Reviewer_XrbP", "summary": "The paper attempts to show the standard zero-sum formulation of the adversarial training methods could lead to suboptimal results in practice. To resolve the issue, the authors propose a non-zero-game formulation of adversarial training problems where the classifier is trained using adversarial perturbations designed by optimizing a different margin-based loss function. This proposal results in the BETA-AT algorithm (Algorithm 2 in the paper). The numerical results in section 5 suggest improved results by applying the proposed BETA-AT method.", "questions": "1- What is the theoretical justification for applying the margin-based attack in (13) for designing adversarial examples over other adversarial attack methods? Does this attack scheme perform more effectively than other attack methods such as PGD or DeepFool? What is its fooling rate vs. the baseline attack methods when applied to standard image datasets?  \n\n2- (Weakness 3 above) The overfitted AT models usually achieve 100% training accuracy under any norm-bounded adversarial attack so they perform perfectly against any norm-bounded perturbation to training data. Does not their perfect training performance show that they have been trained against strong enough adversarial attacks on training data?\n\n3- Figiure 1 shows the training and test accuracy of the networks until epock 130~140. Does the same generalization comparison remain valid if the training continues for more epcohs (like 200 epochs)?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1- The paper discusses the potential drawbacks of the zero-sum game approach to adversarial training which I find interesting.\n\n2- The paper numerically shows that the BETA-AT algorithm could improve the robustness of the neural nets and alleviate the robust overfitting issue.", "weaknesses": "1- While I find the paper's discussion on the drawbacks of zero-sum game formulation of adversarial training very interesting, I think the paper's proposal of considering a non-zero-sum game formulation for AT is not novel. The non-zero-sum game formulation of AT in Section 3.2 can be viewed as \"applying an effective attack algorithm to generate adversarial examples for training the neural network\". In that sense, the paper's main point could be viewed as \"one should use effective attack algorithms to find adversarial examples in adversarial training\". While this idea makes sense, some known variants of AT, e.g. adversarial training with examples generated by DeepFool attack, follow the same non-zero-sum game strategy: we do not optimize the adversarial perturbation by fully maximizing the classification loss and instead use a more effective attack algorithm.\n\n2- Based on the point I discussed above, it seems that the paper's main contribution is to propose an adversarial attack scheme using the margin-based loss function (equation 13) and then use this attack scheme for adversarial training. While the proposed cost function makes sense, the paper does not demonstrate that the margin-based function possesses a desired property that sets it apart from other attack schemes. I think the paper would be much stronger if it theoretically showed what is unique about the specific margin-based attack scheme. Does this attack scheme help with the optimization or generalization of the AT method? At this point, it is not clear how the authors theoretically justify the choice of cost function (13) over other adversarial attack algorithms like DeepFool.\n\n3- The paper's claim that the BETA-AT method helps with the robust overfitting issue is not well justified. The authors mention that \"AT algorithms which seek to solve (8) are ineffective in that they do not optimize the worst-case classification error. For this reason, it should not be surprising that robust overfitting occurs.\" However, the overfitted AT models usually achieve 100% training accuracy under any norm-bounded adversarial attack so they perform perfectly against any norm-bounded perturbation to training data. Does not their perfect training performance show that they have been trained against strong enough adversarial attacks on training data?\n\nI look forward to the authors' responses to the above questions and comments to assign my final score.", "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": "", "extra_scores": {}}, {"review_id": "SUpjEH9Rs0", "reviewer": "Reviewer_hcTf", "summary": "The authors propose to use different surrogate loss for attacker and defender in adversarial training and formulate it as a non-zero-sum game and a bilevel optimization problem. A new adversarial training algorithm is proposed (BETA-AT), which is an extension of the TRADES method at high level. The authors claim that the algorithm eliminates robust overfitting and achieves state-of-the-art robustness. Numerical results on the CIFAR-10 dataset are reported.", "questions": "Please consider my questions in the previous section. I do not have additional questions in this section.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors discuss why traditional adversarial training suffers from the zero-sum-game formula with a shared objective function in details. Also, the numerical results show that the proposed method achieves equal or better performance than some existing methods.", "weaknesses": "1. I feel the contribution of this work is somewhat limited in the sense that the core idea of the algorithm is not very new. At high level, the proposed BETA-AT method is an extension of TRADES: in TRADES training, the attacker aims to maximize $\\max_{j\\neq f_\\theta(X)}M_\\theta(X+\\eta, f_\\theta(X))_j$, and BETA gives a try with each incorrect class. I am wondering if it is the usual case that the BETA-AT gives the same attack as from TRADES, given the classifier is correct?\n\n2. I expect more results for the experiments. Specifically, please consider the followings:\n\na) How does the training curve (as similar to Figure 1) of TRADES look like? Does it suffer robust overfitting in your setting?\n\nb) Does BETA-AT take significantly longer time to train? Can you provide numerical results comparing the training time of the methods considered in Table 1?", "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": "", "extra_scores": {}}, {"review_id": "lPWkDYDF0F", "reviewer": "Reviewer_NF3x", "summary": "The paper addresses the problem of training a classifier to be robust to adversarial attacks wherein an adversary can arbitrarily perturb a test data point $X$ a neighboring data point $X+\\eta$ within a small ball of radius $\\epsilon$. A popular way to train such a classifier is Adversarial Training (AT) with a min-max objective where the attacker solves the inner maximization of the loss function and the defender solves the outer minimization of the worst case loss. The paper identifies that solving the inner maximization by replacing the 0-1 misclassification with a surrogate loss can lead to suboptimal adversarial perturbations, and subsequently, the defenders trained on such weak attacks result in suboptimal robust accuracy. Building upon this observation, the paper proposes to solve the inner problem of finding an adversarial perturbation by maximizing the margin gap of the classifier. Through experiments, the paper demonstrates that performing AT with the proposed attack leads to competent robust accuracies. Through experiments, it is also shown that the proposed change to AT also prevents robust overfitting phenomenon.", "questions": "- I would really appreciate your comments on both the main weaknesses that I listed above. \n- It would be good to include a toy example where the proposed inner maximization retrieves the optimal adversarial perturbation while the standard inner max with surrogate loss does not do so. \n- How effective is BETA attack with a single PGD step, compared to FGSM?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper correctly identifies the problem of using improper surrogates for the inner maximization in AT. \n- The paper hypothesizes that robust overfitting (RO) may be due to this problem of using improper surrogates for solving inner maximization in AT. Experimentally, it shows that RO can be eliminated by fixing this issue. This, I think, is surprising and worth exploring more from a theoretical viewpoint. \n- The proposed modification to AT is simple, principled, and free of heuristics.", "weaknesses": "**Misleading presentation:**\n\nI don't think the paper substantiates the claim made in the title, \"AT should be cast as a non-zero sum game\". The proposed \"non-zero sum\" formulation of AT in equations (16)-(17) is simply a tractactable reformulation of the standard zero-sum formulation in (11)-(12). The change is only in how the inner maximization is solved i.e., how the worst-case adversarial perturbation is found. \n\nIn Section 2.3 the paper claims that the tradeoff between robustness and accuracy as studied in many papers (in particular, Tsipras et. al. ICLR 2019) is a pitfall of the zero-sum formulation. However, the paper does not discuss how their supposed non-zero sum formulation resolves / ameliorates this trade-off either in theory or through experiments. There is also some misrepresentation of the prior work. For example, the robustness-accuracy tradeoff shown in Tsipras et. al. holds for the 0-1 robust loss. Clearly, the tradeoff is not caused by the use of improper surrogate loss.\n\nAnother claim is that the non-zero sum formulation eliminates robust overfitting. However, there is again no discussion on how the proposed non-zero sum formulation helps with this. \n\nOverall, the paper repeatedly stresses on the non-zero sum property of their new AT formulation, and how it overcomes the pitfalls of the standard zero-sum formulation. But the main contribution of the paper is a tractable reformulation of the same old zero-sum game, by addressing the problems that occur through the use of surrogate losses. \n\nThere are other instances of misleading presentation in addition to the above. For instance, section 3.1 is titled \"decoupling adversarial attacks and defenses\". I don't think the proposed formulation (16)-(17) decouples the attacks and defenses any more than the standard formulation. The outer minimization still needs solution to the inner maximization. \n\n**Missing prior work:**\n\nWhile the main contributions of the paper (i.e. the reformulation of AT and the algo to solve the reformulated objective) stem from the core issue of using surrogate losses for AT, there is a surprising lack of any discussion on the many works that study surrogate losses for AT. See for instance Bao et. al. COLT 2020, Awasthi et. al. Neurips 2021 and the references therein. \n\nAnother surprising omission is any discussion on consistency. I quote from the paper, \"Crucially, the inequality in (2) guarantees that the problem in (3) provides a solution that decreases the classification error (Bartlett et al., 2006), which, as discussed above, is the primary goal in supervised classification.\" This quote misses the main point of Bartlett et al., 2006. The solution to the surrogate loss minimization guarantees a solution to the 0-1 error minimization *if* the surrogate loss is \"calibrated\" or \"consistent\". While calibration and consistency are equivalent notions in standard classification (as shown in Bartlett et al., 2006), they are two separate things when it comes to adversarial classification. See the discussion in Munier et. al. Neurips 2022, and more recently Frank and Niles-Weed Neurips 2023.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)