Protect the weak: Class focused online learning for adversarial training
Authors: Thomas Pethick
Grigorios Chrysos
Volkan Cevher
Venue: ICLR 2022 Submitted (2022)
Keywords: Adversarial training
Adversarial examples
Minimax
Robustness

Abstract: Adversarial training promises a defense against adversarial perturbations in terms of average accuracy. In this work, we identify that the focus on the average accuracy metric can create vulnerabilities to the "weakest" class. For instance, on CIFAR10, where the average accuracy is 47%, the worst class accuracy can be as low as 14%. The performance sacrifice of the weakest class can be detrimental for real-world systems, if indeed the threat model can adversarially choose the class to attack. To this end, we propose to explicitly minimize the worst class error, which results in a min-max-max optimization formulation. We provide high probability convergence guarantees of the worst class loss for our method, dubbed as class focused online learning (CFOL), which  can be plugged into existing training setups with virtually no overhead in computation. We observe significant improvements on the worst class accuracy of 30% for CIFAR10. We also observe consistent behavior across CIFAR100 and STL10. Intriugingly, we find that minimizing the worst case can even sometimes improve the average.

Under review as a conference paper at ICLR 2022
PROTECT THE WEAK: CLASS-FOCUSED ONLINE LEARNING FOR ADVERSARIAL TRAINING
Anonymous authors Paper under double-blind review
ABSTRACT
Adversarial training promises a defense against adversarial perturbations in terms of average accuracy. In this work, we identify that the focus on the average ac- curacy metric can create vulnerabilities to the "weakest" class. For instance, on CIFAR10, where the average accuracy 47%, the worst class accuracy can be as low as 14%. The performance sacrifice of the weakest class can be detrimental for real-world systems, if indeed the threat model can adversarially choose the class attack. To this end, propose to explicitly minimize the worst class er- ror, which results a min-max-man max optimization formulation. We provide high probability convergence guarantees of the worst class loss for method, dubbed as class focused online learning (CFOL), using techniques from the online learn- ing community. CFOL can be plugged into existing training setups with virtually no overhead in computation. We observe significant improvements on the worst class accuracy of 30% for CIFARIO. We also observe consistent behavior across CIFAR 100 and STL10. Intriugingly, we find that minimizing the worst case can even sometimes improve the average.
INTRODUCTION
The susceptibility of neural networks to adversarial noise (Goodfellow al. 2014 Szegedy al. 2013) has been a grave concern over the launch of such systems in real-world applications. Sev- eral techniques defending such attacks that optimize the average performance have been proposed (Papernot et al., 2016 Raghunathan et al. 2018 Guo et al. 2017 Madry et al., 2017 Zhang et al.) 2019). response, even stronger attacks have been proposed (Carlini & Wagner| 2016) Engssrom et al. 2018, Carlini 2019). Indeed, recent studies demonstrate that regardless of the defense there exists an attack that can lower the average performance of the system (Shafahi et al. 2018).
In this work, we argue that the average performance is not the only criterion that is of interest for real-world applications. For classification, in particular, optimizing the average performance provides no guarantees for the "weakest" class. This is critical in scenarios where attacker can pick the class adversarially in addition to the adversarial perturbation. performing class can indeed be much worse than the average in adversarial training. This difference is already present clean training but we critically observe, that the gap between the average and the worst, is greatly exacerbated in adversarial training. This gap can already be observed on CIFARIO 10 where the accuracy across classes is far from uniform with 47% average robust accuracy while the worst class 14% (see Figure D.. The effect is even more prevalent when more classes are present as in CIFAR 100 where we observe that the worst class has zero accuracy while the best has 70% (see Appendix C where we include multiple other datasets). Despite the focus on adverarial training, we note that the same effect can be observed for robust evaluation after clean training (see Figure 4
turns out that the worst
This dramatic drop in accuracy for the weakest classes begs for different approaches than the clas- sical empirical risk minimization (ERM), which focuses squarely on the average loss. We suggest a simple alternative, which we dub class focused online learning (CFOL), that can be plugged into existing adversarial training procedures. Instead of minimizing the average performance over the dataset we sample from an adversarial distribution over classes that is learned jointly with the model parameters. In this way aim at becoming robust to attacker that can adversarially choose the class. The focus of this paper is thus on the robust accuracy of the weakest classes instead of the average robust accuracy.

---

Under review as a conference paper at ICLR 2022
Clean training
Adversarial training
1.0
Clean test Scurac
0.8
0.0
0.6
0.6
Robust test
0.4
0.2
0.0
0.0
airplane
automebile
bird
cat.
dleer
dog
trog
horse
ship
truck
airplane
autumebile
cat
dier
dog
frog
horse
ship
track
Figure The error across classes is already not perfectly uniform in clean training on CIFAR1O. However, this phenomenon is significantly worsened in adversarial training when considering the robust accuracy. That is, some classes perform much worse than the average. The worst class accuracy and average accuracy is depicted with red and black line respectively.
Concretely, we make the following contributions:
We propose simple solution which relies on the classical bandit algorithm from the online learning literature, namely the Exponential-wwiggh algorithm for Exploration and Exploita- tion (Exp3) (Auer et al.) 2002). The method directly compatible with standard adversar- ial training procedures (Madry et al. 2017). by replacing the empirical distribution with an adaptively learned adversarial distribution over classes.
We carry out extensive experiments comparing CFOL against three strong baselines across three datasets, where we consistently observe that CFOL improves the weakest classes.
We support the empirical results with high probability convergence guarantees for the worst class accuracy and establish direct connection with the conditional value risk (CVaR) (Rockafellar et al. 2000) uncertainty set from the distributional robust optimization.
Overview We define our new objective in Section followed by the description of the proposed method in Section 3 In Section we prove convergence guarantees. We then move to the empiri- cal work in Section 4 where we observe and resolve the issue of robust overfitting in the context of the worst class. Our main empirical findings are covered in Section and we conclude in Section
1.1 RELATED WORK
Adversarial examples Goodfellow et al. 2014); Szegedy et al. (2013) are the first to make the important observation that deep neural networks vulnerable to small adversarially perturbation of the input. Since then, there has been growing body of literature addressing this safety critical issue, spanning from certified robust model (Raghunathan al. 2018). distillation (Papernot al.) 2016). input augmentation (Guo et al., 2017). to adversarial training (Madry et a 2011 Zhang al. 2019). We focus adversarial training in this paper. While certified robustness is desirable, adversarial training remains one of the most successful defenses in practice.
In concurrent work Tian al. (2021) independently observe the non-uniform accuracy over classes in adversarial training, further strengthening the case that lack of class- wise robustness is indeed an issue. However, they mainly focus on constructing an attack that can enlarge this disparity.
Minimizing the maximum Connected to our method is that of focused online learning (FOL) (Shalev-Shwartz & Wexler 2016), which similarly takes bandit approach, but instead re-weights the distribution over the N training examples, independent of the class label. This naturally leads to a convergence rate in terms the number of examples N instead of the number of classes & for which usually is < N. We compare in more detail theoretically and empirically in Section 3.1 and Section respectivel
Interpolations between average and maximum loss have been considered in various other settings:
for class imbalanced datasets (Lin et al.) 2017), in federated learning (Li et al. 2019). and more generally the tilted empirical risk minimization (Li al. 2020 Lee al. 2020).
2

---

Under review as a conference paper at ICLR 2022
Distributional robust optimization The accuracy over the worst class can be seen particular re-weighing the data distribution which adversarially assigns all weight to a single class. Worst case perturbation of the data distribution have more generally been studied under the framework of distributional robust stochastic optimization (DRO) (Ben-Tal et 2013) Shapiro 2017). Instead of attempting minimizing the empirical risk training distribution Po. this framework considers some uncertainty set around the training distribution ((Pb) and seeks to minimize the worst case risk within this set, SUPQEu(P)) Ex [[[=]]
A choice of uncertainty set, which has been given significant attention in the community, is condi- tional value at risk (CV,R), which aims at minimizing the weighted average of the tail risk (Rock-)
afellar et al.] 2000 Levy et al., 2020 Kawaguchi & Lu. 2020 Fan et al. 2017 Curi et al. 2019).
CVaR has been specialized to a re- ne-weighting over class labels, namely labeled conditional value at
risk (LCVaR) (Xu et al. (020). This was originally derived in the context of imbalanced dataset to re-balance the classes. It is still applicable in our setting and we thus provide a comparison. The original empirical work of (Xu et al., 2020) only considers the full-batch setting. We complement this by demonstrating LCVaR in stochastic setting.
In Duchi et al. (2019); Duchi & Namkoong (2018) they are, similarly to our setting. interested in uniform performance over various groups. However, these groups are assumed to be latent subpop- ulations, which introduces significant complications. It is thus concerned with a different setting, an example being training dataset implicitly consisting of multiple text corpora.
CFOL can also be formulated in the framework of DRO by choosing an uncertainty set that can re-weight the & class-conditional risks. The precise definition is given in Appendix [B.] We further establish a direct connection between the uncertainty sets of CFOL and CVaR that we make precise in Appendix B.I which also contains summary of the most relevant related methods in Table 4
2 PROBLEM FORMULATION AND PRELIMINARIES
The underlying data distribution is denoted by D with examples x E Id and classes y E [k]. A given iteration is characterized by E [T], while Ph indicates the ythh index of the 1th iterate. The indicator function is denoted with 1 [boolean) and unif(n) indicates the uniform distribution over n elements. An overview of the notation is provided in Appendix
Notation
normally interested in minimizing the population risk [I((), y) over our model parameters 0 IRP, where f is some loss function of 0 and example Rd with an associated class E [A)) Madry et al. (011 formalized adversarially training by modifying this objective with an adversarial perturbation each example. That is, we instead want to find a parameterization 0 of our predictive model which solves the following optimization problem:
In classification,
min L(0) == Exzg)>>
max max x 6. BES
(1)
where each æ is now perturbed by adversarial noise 5 E S C Rd.. Common choices of S include nolm-ball constraints as in Madry et al.] (2017) or bounding some notion of perceptual distance (Laidlaw et al.] 2020). When the distribution over classes is uniform this is implicitly minimizing the average loss over all class. This does not guarantee high accuracy for the worst class as illustrated in Figure I since we only know with certainty that max 2 avg.
Instead, we will focus on a different objective, namely minimizing the worst class risk:
min max vE[R]
[y( (2-pp((a)) max ((0, x + +5,
JES
This follows the philosophy that "a chain is only as strong as its weakest link". In our particular setting it models scenario where the attacker can adversarially choose what class the model is evaluated on. In safety critical application, such as autonomous driving, modeling even just a single class wrong can still have catastrophic consequences.
As the maximum in Equation is a discrete maximization problem its treatment requires more care. We will take common approach and construct convex relaxation to this problem in Section 3
3

---

Under review as a conference paper at ICLR 2022
Class sampling distribution
0.10
0.05
0.00
alr parplane
automnattte
bird
Cat
deer
dog
frog
hurne
ship
truck
Figure 2: Contrary to ERM, which samples the examples uniformly, CFOL samples from an adap- tive distribution. The learned adversarial distribution non-uniform over the classes in CIFARIO when using adversarial training. As expected, the hardest classes are also most frequently sampled.
3 METHOD
Since we do not have access to the true distribution D, we will instead minimize over the provided empirical distribution. Let,N, be the set of data point indices for class y such that the total number of examples N = Ey [NGl- Then, we are interested in minimizing the maximum empirical class-conditioned risk,
I.y (0)
1
Σ K,,
max (0,,r; 8,9)-
(3)
WE
W
dES
We relax this discrete problem to continuous problem over the simplex As.
max
(0)
max (0).
(4)
yE[k]
PE A y=1
Note that equality is attained when is a dirac on the argmax over classes.
Equation 4 leaves us with two-player zero-sum game between the model parameters 0 and the class distribution p. From the perspective of it is just a linear objective, albeit adversarially picked by the model. This immediately let us use no-regret algorithm under simplex constraint, namely Hedge (Freund & Schapire 1997):
wt w/ (0', = exp (w!)
Σ exp (wt)
(Hedge)
To show convergence for (edgee) the loss needs to satisfy certain assumptions. In our case of classification, the loss is the zero-one loss 2(0, y) [hha + y]. where ha(-) is the predictive model. Hence, the loss is bounded, which is sufficient requirement.
Note that (Hedge) relies zero-order information of the loss, which indeed have available. However, in the current form, (Hedge) requires so called full information over the & dimensional loss vector. In other words, we need to compute (,) for all y [k] at every iteration. When accessing the data through mini-batches, it is strictly not possible to compute even an estimate for each y if the number of classes is larger than the batch size.
Following the seminal work Auer et al. (2002). we instead construct an unbiased estimator of the dimensional loss vector L((²)= == (L, (6'), ..., (+)) based on a sampled class y from some distribution y p². This stochastic formulation further lets estimate the class conditioned risk y (0*) with an unbiased sample unif(( (). This leaves us with the following estimator,
T. = {
L (0))
y y=y²
(5)
0
otherwise
4

---

Under review as a conference paper at ICLR 2022
Algorithm 1: Class focused online learning (CFOL)
Algorithm parameters: step rule ModelUpdate for the model satisfying Assumption adversarial step-size 7) > O, uniform mixing parameter y = 1/2, and the loss (0). Initialization: Set wt = 0 such that gd and p" are uniform.
foreach t in 0..T do
yf p²
sample class // sample uni from class // update model parameters // construct estimator 11 update the adv. class distribution
i ~ miir((N):+1)
gr+1 ModelUpdato(O%, Iy
T [(v='') Ty (pp, Vy:
by w/y -nIy vy;
9 .+1 exp (w) EEy= exp (wott) fy;
P3 V + (1 - g) )t Vy;
end foreach
where L (0) maxses (0, + ò, v). It easy to verify that this estimator is unbiased,
1, = (0).
Bygup [i]] =1 (1-p%) pt) - pyy
(6)
pty
For ease of presentation the estimator only uses a single sample but this can trivially be extended to a mini-batch where classes are drawn i.i.d. from p².
We could pick p' to be the learned adversarial distribution, but it is well known that this can lead to unbounded regret if some pt is small (see Appendix A for definition of regret). AAurr al. (2002) resolves this problem with Exp3, which instead learns a distribution q', then mixes it with uniform distribution, to eventually sample from py 7 + (1 7)4; where E (0, 1). Intuitively, this enforces exploration. In the general case this needs to be picked carefully and small enough, but similarly to Shalev-Shwartz & Wexler (2016). we show that y 1/2 suffice in setting.
Our algorithm thus updates g with (Hedge) using the estimator L' with sample drawn from and subsequently plays p²+1 CFOL in conjunction with the simultaneous update of the minimization player can be found in algorithm | with an example of a learned distribution p' in Figure 2
Practically, the scheme bears negligible computational overhead over ERM since the softmax re- quired to sample is of the same dimensionality as the softmax used in the forward pass through the model. This computation is negligible in comparison with backpropagating through the entire model. For further details on the implementation we refer to Appendix C.4
3.1 CONVERGENCE RATE
To understand what kind of result we can expect, it is worth entertaining hypothetical worst case scenario. Imagine a classification problem where one class is much harder model than the re- maining classes. We would expect the learning algorithm to require exposure to examples from the hard class in order to model that class appropriately otherwise the classes would not be distinct. From this one can see why FRM might be slow. The algorithm would naively pass over the entire dataset order to improve the hard class using only the fraction of examples belonging that class. In contrast, if that are already improved sufficiently. As long as we can adapt fast enough, as expressed through the regret of the adversary, should be able to improve on the convergence rate for the worst class.
-ttheriielyy-oeeeiiiie
adaptively focus the difficult class,
avoid spending time classes
We will now make this intuition precise by establishing a high probability convergence guarantee for the worst class loss analogue to that of FOL. For this will assume that the model parameterized by enjoys a so called mistake bound of (Shalev-Shwartz et al.) 201T p. 288). The proof is deferred to appendix
5

---

Under review as a conference paper at ICLR 2022
Assumption 1. For any sequence of classes (y'...,,"" y²) ) E [A]" and class conditioned sample in- dices (i' ...., ( with it Ng. the model enjoys the following bound for some C³ 20 and C = maxfh log C
T E L (0*) S.
(7)
Remark 1. The requirement C > k log k will be needed to satisfy the mild step-size requirement y S 2k in Lemma In most settings the smallest C' is some fraction of the number of iterations T, which in turn is much larger than the number of classes k, so C C².
With this at hand we are ready to state the convergence of the worst class condiioond empirical risk.
Theorem 1. If algorithm 7 is run on bounded rewards Ly (0*) E [0, Vt with step-size = / /log k/ (AkC), mixing parameter Y 1/2 and the model satisfies Assumption iterations with probability at least 1 8,
I then after TT'
60
V4k log(2k/0) (1 2k) log(2k/6) v log 2k//)) 2 12g(2k/6)
Σ by (0%) s T
max WE(k]
VT
3T
3n
j=1
for an ensemble of size n where tj sid unif(T)) for E [m].
To contextualize Theorem let us consider the simple case of linear binary classification mentioned in Shalev-Shwartz & Wexler (2016). In this setting SGD needs (CCN) iterations to obtain a con- sistent hypothesis. In contrast, the iteration requirement of FOL decomposes into a sum Õ + N) which is much smaller since both C and N are large. When are only concerned with the con- vergence of the worst class we show that CFOL can converge Õ + k) where usually k < C. Connecting this back to our motivational example in the beginning of this section, this sum decom- position exactly captures our intuition. That is, adaptively focusing the class distribution can avoid the learning algorithm from needlessly going over all k classes in order to improve just one of them.
From Theorem we also see that we need an ensemble of size n ? v log(k/8) (t//)/e))) (e2), which has only mild dependency on the number of classes k. If we wanted to drive the worst class error E to would be problematic. However, for adversarial training, even in the best
zero the dependency case of the CIFAR 10 dataset, the average error is larger than 1/2. We can expect the worst class error to be even worse, so that only small is required. In practice, single model turns out to suffice.
Note that the maximum upper bounds the average, so by minimizing this upper bound as in The- orem [ we implicitly still minimizing the usual average loss. In addition, Theorem shows that a mixing parameter of y = 1/2 is sufficient for minimizing the worst class loss. Effectively, the average loss is still directly being minimized, but only through half of the sampled examples.
4 EXPERIMENTAL SETUP: OVERCOMING ROBUST OVERFITTING
Robust overfitting is a well-documented challenge in adversarial training (Rice et al. 2020 Pang al., (020)). This phenomenon is characterized by a rapid drop in the validation accuracy shortly after the first piecewise step-size decay. The reported models in the literature are indeed early stopped prior the second step-size decay (e.g., Madry al. (017); Zhang et al. (2019). This is particularly problematic when interested in the worst class accuracy, which might not be aligned with the average performance across training epochs. Below, we conduct preliminary experiments on CIFAR10 10 confirming this problem and propose solution. We adopt the setup for adversarial training with PGD in Madry et al. (2017) with the stepsize scheduling from Zhang et al. (2019). We consider adversarial training the empirical distribution (ERM-AT) and adversarial training on the jointly learned adversarially class distribution (CFOL-AT).
With ERM-AT the worst class has only 14% robust test accuracy when early stopping based on the average accuracy. Early stopping based on the worst class can improve on the worst class accuracy, but only marginally, as show in the supplementary (see Table 5). This minor improvement comes at a huge cost for the average accuracy which drops from 47% to 38%. Ideally both metrics should instead increase monotonically.

---

Under review as a conference paper at ICLR 2022
Table 1: Robust accuracy on CIFARIO under early stopping without temporal ensembling. The number in parenthesis indicates the epoch of piecewise constant step-size decay, For CFOL-AT to consistently converge it was necessary to decay earlier than the usual decay at epoch 75. Fortunately, known regularization techniques mitigate this problem which leads to our main results in Section
ERM-AT (75)
ERM-AT (33)
CFOL-AT (33)
Average
0.47
0,45
0.42
Worst class
0.
0.13
0.27
For CFOL-AT the problem of robust overfitting presents itself differently. The worst class accuracy improves much more rapidly, reaching 27% even when early stopped based on the average accuracy. Note that this is not surprising and is in line with the convergence rate derived in Section 3.1 The implication is that we are required run CFOL-AT for a shorter time to get consistent pertormance and carefully select the step-size decay point. This limited training time, due to the earlier overfitting, unfortunately restricts the expressivity of the model. We show comparison with both ERM-AT with similar early step-size decay and also more standard step-size decay of Zhang et al. (019) in Table Although we see significant improvement from 14% to 27% in terms of the worst class we ideally want the method be stable for more iterations.
To avoid the root problem of overfitting, we regularize the training objective. We adopt temporal ensembling (TE) which is regularization technique that was shown to mitigate overfitting in ad- versarial training (Laine & Aila 2016 Dong et al. (02T). This allows us to reliably run CFOL-AT under exactly the same training configuration
ERM-AT and thus prevents further hyperparameter tuning. Additionally, TE leads to a more fair comparison with ERM-AT, which enjoys an improve- ment in terms of the worst class robust accuracy from 14% 21%. We make use of this additional regularization in all subsequent experiments. In this work we focus on the robust accuracy. How- ever, we add cautionary note, since we observe that TE can lead reduction in clean accuracy (see Table 6).
5 EXPERIMENTS
We consider the common adversarial setting where the constraint set of the attacker S is -bounded attacks. We test on three datasets with different dimensionality, number of examples per class and number of classes. Specifically, we consider CIFAR1O. CIFAR100 and STL10 (Krizhevsky et al. 2009 Coates et al. 2011) (see Appendix C.2
for further details).
Hyper-parameters Unless otherwise noted, we use the standard adversarial training setup of ResNet50 network (He et al., 2016) with a learning rate t = 0.1, momentum of 0.9, weight decay of 5 5 batch size of 128 (Madry et al. (017)) with piece-wisst constant weight decay of 0.1 at epoch 75 and 90 for a total of 100 epochs according to Zhang et al. (2019), as well as regularizing with temporal ensembling as explained in Section 4 For the attack similarly adopt the common attack radius of 8 /55 using 7 steps of projected gradient descent (PGD) with a step-size of 2/255 (Madry et al. 2017). For STL10 we adopt the learning rate т 0.01 and use a batch-size of 64 to fit it inside our hard ware. For evaluation we use the stronger attack of 20 step PGD.
Baselines With this setup we compare our proposed method, CFOL, against empirical risk mini- mization (ERM). labeled conditional value at risk (LCVaR) (Xu et al. 2020) and focused online learning (FOL) (Shalev-Shwartz & Wexler 2016). We add the suffix "AT" all methods to indicate that the training examples are adversarialyy perturbed according to adversarial training of Madry al.] (2017). We consider ERM-AT as the core baseline, while we also implement FOL-AT and LCVaR-AT alternative methods that can improve the worst performing class. For fair compar- ison, and to match existing literature, we do early stopping based on the average robust accuracy on the hold-out set. More details on hyperparameters and implementation can be found in Ap- pendix C.T and Appendix C..4 respectively. In Table 10 we additionally provide experiments for a variant of CFOL-AT which instead reweighs the gradients.
Metrics We report the average accuracy, the worst class accuracy and the accuracy across the 20% worst classes (referred to the 20% tail) for both clean (acCelean) and robust accuracy (acczob). The
7

---

Under review as a conference paper at ICLR 2022
mean and standard deviation in all tables computed over 5 independent executions. We note that the aim is not to be state-of-the-arr but rather provide a fair comparison between the methods.
The first core experiment is conducted CIFARIO. In Table 2 the quantitative results ported with the accuracy per class illustrated in Figure 3 The results reveal that all methods other than ERM-AT improve the worst performing class with CFOL-AT obtaining higher accuracy in the weakest class than all methods in both the clean and the robust case. Interestingly, FOL-AT per- forms better than LCVaR-AT, for the next experiments we simply consider FOL the non-ERM comparison method.
The results for the remaining datasets be found in Table The results exhibit similar patterns to the experiment on CIFARIO, where CFOL-AT improves both the worst performing class and the 20% tail. In the supplementary, we also provide results for early stopped models using the best worst class accuracy from the validation set (see Table larger attack radius (see Table (), and a different test time attack (see Table 9.. In all cases, we observe that CFOL-AT has consistently improved accuracy with respect to the weakest class (and the 20% tail). We note that early stopping based on the worst class is not sufficient to make ERM-AT competitive with CFOL-AT.
We find that CFOL-AT consistently improves the accuracy for both the worst class and the 20% tail across the three datasets. At the same time, the average performance only suffers minor reduction. The improvement seem to be even more noticeable in terms of the clean accuracy. Interestingly, FOL-AT improves even the average accuracy on CIFARIO 10 while having small variance, suggestion that sometimes focusing on the worst can improve the average.
Table 2: Accuracy on CIFARIO. For both clean test accuracy (aCCelean) and robust test accuracy (accrob) we report the average, 20% worst classes and the worst class. We compare our method (CFOL-AT) with standard adversarial training (ERM-AT) and two baselines (LCVaR-AT and FOL- AT). CFOL-AT significantly improves the robust accuracy for both the worst class and the 20% tail, while only incurring small reduction in the average robust accuracy in comparison with ERM-AT.
ERM-AT
CFOL-AT
LCVaR-AT
FOL-AT
Average
0.74 + 0.01
0.75 0.00
0.05
0.79 + 0.01
aCCclean
20% tail
0.52 + 0.03
0.66 0.01
0.02
0.61 0.03
Worst class
0.48 + 0.04
0.63
0.56 0.03 0.03
Average
0.47 0
0.00
0,50 0.00
acCrob
20% tail
0.24 + 0.02
0.31
0.02
0.28 + 0.02
Worst class
0.21 + 0.02
0.30 +
0.20
0.22 + 0.03
ERM-AT
CFOL-AT
Robust test accuraty
0.6
0.6
0.4
0.4
Robust
0.2
0.2
0.0
airplane
autonabble
bird
cat
deer
dog
frog
herae
ship
truck
airplans
autommisie
bird
frog
herse
ship
truck
Figure 3: The robust test accuracy for CFOL-AT and ERM-AT over classes. The horizontal black and red line depicts the average and worst class accuracy over the classes respectively. The im- provement in the minimum accuracy is notable when using CFOL-AT, while there only marginal difference in the average accuracy.
8

---

Under review as a conference paper at ICLR 2022
Table Clean accuracy (aCCelean) and robust test accuracy (aCC)ob) on CIFARI00 and STLIO. We compare our method (CFOL-AT) with standard adversarial training (ERM-AT) and two base- lines (LCVaR-AT and FOL-AT). CFOL-AT consistently improves the worst class accuracy well as the 20% worst tail.
ERM-AT
CFOL-AT
FOL-AT
Average
0.54 + 0.02
0:52
0.53 + 0.01
aCCclean
20% tail
0.30 0.04
0.35 0.06
0.31 0.04
Worst class
0.12
0.19 + 0.04
0.17
CIFAR100
Average
0.24 0.00
0.26
acCrob
20% tail
0.02
0.09
0.03
0
Worst class
0.01 0.01
0.03 + 0.02
0.01 0.01
Average
0.55 0.03
0.02
aCCclean
20% tail
0.42 0.25 0.10
0.27 +
Worst class
0.09
0.38 0.07
0.22
STL10
Average
0.05
0.04
0.05
acCrob
20% tail
0.09 0.03
0.18
0.11
Worst class
0.07 0.03
0.16 + 0.03
0.07 + 0.01
CONCLUSION
In this work, we have introduced method for class focused online learning (CFOL), which samples from an adversarial learned distribution over classes. We establish high probability convergence results of the worst class for CFOL through specialized regret analysis. In the context of adversarial examples this is motivated by an adversarial threat model in which the attacker chooses what class to evaluate on in addition to the perturbation. We conduct a thorough empirical validation on three datasets. The empirical results for adversarial training consistently demonstrate the improvement over the weakest classes. The work opens up for multiple interesting research avenues. Firstly, our method can also be applied in non-adversarial settings, and in the future we intend to look further into the challenging cases of non-uniform distribution over classes. Secondly, it remains open to establish generalization bounds for CFOL. Finally, is interesting to understand why adversarial perturbations leads to inhomogeneous accuracies over classes.
REFERENCES
Jean-Yves Audibert, Sébastien Bubeck, and Rémi Munos. Bandit view on noisy optimization. In Optimization for Machine Learning, chapter 1. MIT Press, optimization for machine learning edition, January 2010.
Peter Auer, Nicolò
Yoav Freund, and Robert E. Schapire. The nonstochastic multi- armed bandit problem. SIAM Journal on Computing, 32(1):48-77, January 2002. ISSN 0097- 5397, 1095-7111. doi: (0.11377/009733977199877
Aharon Ben-Tal, Tal, Dick Den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Management Sci- ence, 59(2):341 2013.
Nicholas Carlini. Is ami (attacks meet interpretability) robust to adversarial examples? preprint 1wXXiv:/002.02:.. 2019.
arXiv
Nicholas Carlini and David Wagner. Defensive distillation is robust to adversarial examples. arXiv preprint NEXXv1660..03111 2016.
Adam Coates, Andrew Ng. and Honglak Lee. An analysis of single-layer networks in unsupervised feature learning. In Proceedings of the fourteenth international conference on artificial intelli- gence and statistics, pp. 215-223. JMLR Workshop and Conference Proceedings, 2011.

---

Under review as a conference paper at ICLR 2022
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter- free attacks. In International conference on machine learning, pp. 2206- 2216. PMLR. 2020.
Sebastian Curi, Kfir Levy, Stefanie Jegelka, Andreas Krause, et al. Adaptive sampling for stochastic risk-averse learning. arXiv preprint arXiv:1910.12511 2019.
Yinpeng Dong, Ke Xu, Xiao Yang. Tianyu Pang, Zhijie Deng, Hang Su, and Jun Zhu. Exploring memorization in adversarial training. arXiv preprint arXiv:2106.01666 2021.
John Duchi and Hongseok Namkoong. Learning models with uniform performance via distribution- ally robust optimization. arXiv preprint arXiv:18/0.08750, 2018.
John C Duchi, Tatsunori Hashimoto, and Hongseok Namkoong. Distributionally robust losses against mixture covariate shifts. Under review, 2019.
Logan Engstrom, Andrew Ilyss, and Anish Athalye. Evaluating and understanding the robustness of adversarial logit pairing. arXiv preprint arXiv: 2018.
Yanbo Fan, Siwei Lyu, Yiming Ying, and Bao-Gang Hu. Learning with average top-k loss. arXiv preprint Xiv: 000.170050.882 2017.
Yoav Freund and Robert E Schapire. A decision-theereete generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1): 1997.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572, 2014.
Chuan Guo, Mayank Rana, Moustapha Cisse, and Laurens Van Der Maaten. Countering adversarial images using imput transformations. arXiv preprint 1711007111.01 17, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Kenji Kawaguchi and Haihao Lu. Ordered sgd: A stochastic optimization framework for em- pirical risk minimization. In International Conference on Artificial Intelligence and Statistics, pp. 669-679. PMLR, 2020.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Cassidy Laidlaw, Sahil Singla, and Soheil Feizi. Perceptual adversarial robustness: Defense against unseen threat models. arXiv preprint arXiv:2006. /2655, 2020.
Samuli Laine and Timo Aila. Temporal ensembling for semi-supervised learning. arXiv preprint 1:X1::611000222. 2016.
Jaeho Lee, Sejun Park, and Jinwoo Shin. Learning bounds for risk-sensitive learning. arXiv preprint wwXiv:2006.08/338 2020.
Daniel Levy, Yair Carmon, John C Duchi, and Aaron Sidford. Large-scale methods for distribution- ally robust optimization. arXiv preprint arXiv:2010.08893. 2020.
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning, arXiv preprint 1xXiv:1905.10497 2019.
Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. Tilted empirical risk minimization. arXiv preprint arXiv:2007.011 162, 2020.
Tsung- Yi Lin, Priya Goyal, Ross Girshick. Kaiming He, and Piotr Dollár. Focal loss for dense object detection. Proceedings of the IEEE international conference on computer vision, pp- 2980-2988, 2017.
10

---

Under review as a conference paper at ICLR 2022
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.06080 2017.
Tianyu Pang, Xiao Yang, Yinpeng Dong, Hang Su, and Jun Zhu. Bag of tricks for adversarial training, arXiv preprinl arXiv:2010.00467 2020.
Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. Distillation as defense adversarial perturbations against deep neural networks. In 2016 IEEE symposium on security and privacy (SP), pp. 582-597. IEEE, 2016.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples. arXiv preprint arXiv: 2018.
Leslie Rice, Eric Wong, and Zico Kolter. Overfitting in adversarially robust deep learning. In International Conference on Machine Learning, pp. 8093-8104, PMLR, 2020.
Tyrrell Rockafellar, Stanislav Uryasev, et Optimization of conditional value-at-risk.. Journal of risk, 2:21-42, 2000.
Ali Shafahi, W Ronny Huang, Christoph Studer, Soheil Feizi, and Tom Goldstein. Are adversarial examples inevitable? arXiv preprint arXiv:180.002144, 2018.
Shai Shalev-Shwartz and Yonatan Wexler. Minimizing the maximal loss: How and why. In Inter- national Conference on Machine Learning, pp. 793-801. PMLR, 2016.
Shai Shalev-Shwartz et Online learning and online convex optimization. Foundations and trends in Machine Learning, 4(2):107-114, 2011.
Alexander Shapiro. Distributionally robust stochastic programming. SIAM Journal Optimization, 27(4):2258-22 2275, 2017.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 1312.619, 2013.
Qi Tian, Kun Kuang, Kelu Jiang, Fei Wu, and Yisen Wang. Analysis and applications of class wise robustness in adversarial training. arXiv preprint arXiv:2105. 142400 2021.
Ziyu Xu, Chen Dan, Justin Khim, and Pradeep Ravikumar. Class-weighter classification: Trade- offs and robust approaches. In International Conference on Machine Learning, pp. 10544-10554. PMLR, 2020.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent EI Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International Conference on Machine Learning, pp. 7472-7482. PMLR, 2019.

---

Under review as a conference paper at ICLR 2022
A CONVERGENCE ANALYSIS
A.1 PRELIMINARY AND NOTATION
Consider the abstract online learning problem where for every [I]] the player chooses action x' and subsequently the environment reveals the loss function v"). As traditional in the online learning literature will measure performance in terms of regret, which compares sequence of choices {x² )z=1 with fixed strategy in hindsight u,
T
Rr(u)= Σ
Ux ,y') min Σ I(u, v')-
(9)
t=1
we, instead of minimizing over losses maximize over rewards r we define regret as,
RT(u)= max Σ Er(u,y') Er(at."))
(10)
When we allow randomized strategy, as in the bandit setting, Rr becomes a random variable that wish upper bound with high probability. For convenience include an overview over the notation defined and used in Section 2 and Section below.
k
Number of classes
T
Number of iterations
3S [boolenn))
The 1/th index of the iterate
The indicator function
unif(n)
Discrete uniform distribution over elements Set of data point indices for class y E [k:]
N2
N Σx=1 Wyl
The size of the data set
Ly (0) = maxses l (0, 24 + 6,
Loss particular example
(0) = [No1
1, ΣiEN, Ly (0)
The empirical class-conditioned risk
ī (0) = (In (8) Lg (0))
The vector of all empirical class-conditioned risks
1 Ly,s (8t)
estimator at iteration t with ~
A.2 CONVERGENCE RESULTS
We restate Algorithm| I while leaving out the details classifier for convenience. Initialize w such that qd and pd are uniform. Then Exp3 proceeds for every t [T] as follows:
1. Draw class y' ~ p'
2. Observe scalar reward L'y
3. Construct estimator Σt = LY 1 \ Vy
4. Update distribution =++1 n0= .TT."
d4 exp (w / E exp (wt+1) Vy
p 1+ = + (1 7), Vy
We can bound the regret of Exp3 Auer et al. 2002 in setting, when the mixing parameter y is not small as otherwise usually required, by following a similar argument as Shalev-Shwartz &
Wexler (2016).
For this we will use the relationship between p and & throughout. From Py = - + +1 7)4y it can easily be verified that,
4y <
1
< and
for all y-
(11)
Py
7 Py 1 1
12

---

Under review as a conference paper at ICLR 2022
Lemma 1. If Exp3 is run on bounded rewards Lig E [0, 1] vt with 17 S 7/k then
T
log k
n/
T
Rgd (u)
Σ
(u,
E 49. L
(12)
1
(1
7)n
Proof. We write the estimator vector as L' Eyy where eyt is canonical basis vector. By assumption we have Lig E [0. Combining this with the bound on 1/pv in Equation I] wc
py
have T, S */7 for y. This lets us invoke Shalev-Shwardd et al. step-size 1) is small enough. Specifically, we have that 17 S 1/4,
2011
Thm 2.22) as long as the
7/K
T (u. 1
T
T &
Σ
Σ
ig',
log l
+ 7
(1,). y=1
o
(13)
By expanding ž and applying the inequalities from Equation on q and p.
we can get rid of the dependency
T
k
k log
log ls
Bn (T,))
+
11
(pt p )
(L
7
17
t=1
t=1
log k
T
k
+ 11
11 - 117 (Tige)
(14)
log k
1/K
Tigl
17
(1 1)7
t=1
where the last line uses the boundedness assumption Lg E [0. 10 Vy.
is apparent that we need to control the sum of losses. We will do so by assuming that the model admits mistake bound as in
& Wexler (2016); Shalev-Shwartz et al. (2011).
Assumption 1. For any sequence of classes (y'..., y²) E 1kj and class conditioned sample indices (i....,,?" ) with it Nig the model enjoys the following bound for some C' oo and C' = max log k. C"}.
.....
T Σ
Ly (0') S.
(15)
Recall that we need to bound L Ly (f'), where y are picked adversarially and i' are sampled uniformly, so the above sufficient.
Lemma 2. If the model satisfies Assumption 7 and algorithm is run bounded rewards L (0t) E [0, 1] vt with step-size n Vlog kt/ (/(4kC) and mixing coefficient yy 1/2 then
Σ lu Lu, 6C.
(16)
Proof. By expanding and rearranging Lemma
log k
d y!
(u,
+
(17)
(1
as long as E 7/k. Then by using our favorite inequality in Equation 11 and under Assumption
log + (11 11-7)
ni
Ly pyy
T Σ
log k +
(n nik
1
1
(パ-
+ 1
(18)
"
t=1
13

---

Under review as a conference paper at ICLR 2022
To maximize (1 - (1- now pick 7 1/2 so that,
log k
+ (a1 nk
(1- 1 1- ) c
log k + (4nk + C.
(19)
7
"
For 7/, notice that it appears two the terms. To minimize the bound respect to we pick Vlgg (4kCC) such that logk = 4nkC, which leaves us with,
log l + (4nk + 2)C 2/ 4oC'log k 2C,
(20)
log by assumption then the original step-size requirement of 1 S 1/28 is satisfies. In this case we can additionally simplify further,
From the first term it clear that since
2 4kCllg 2C S 6C.
(21)
This still only gives us a bound on a stochastic object. We will now relate it to the empirical class conditional risk (0) by using standard concentration bounds. To be more precise, we want to By in (u, Σ concentrate to (0). Following Shalev-Shwartz & Wexler (016) we adopt their use of a Bernstein's 's type inequality.
show that by picking
Lemma (e.g. Audibert et al. (2010) Thm. 1.2)). Let A1.... Ar a murtingale differ- sequence with respect to Markovian sequence B1,... Br and assume |Asl S V and E [[4 BI..... Bi] S Then for any 8 E 1).
/2s log (1/6 VT
Vlog (4/6) 3T
A
2 1 8.
(22)
T
Lemma 4. If algorithm is run on bounded rewards Lig ,a (f*) E [0, Vt with step-size 1) Vog k/ (AKC), mixing coesficient = 1/2 and the model satisfies Assumption then for any y E [k] obtain have the following bound with probability at least 8/2,
T 7 Ly (0)) I
6C T
/ log (4/6) VT
(1 2k) log (4/8)
(23)
3T
Proof. Pick any E [k] and let Ey in (u, Lt). By construction the following defines martingale difference sequence,
A, = (o)( (ey: F.4y (0') (ee:
1 pye T.y', (0)) )ey:)
(24)
In particular note that it is uniformly sampled. To apply the Bernstein's 's type incquality we just need to bound |A,] and E [A] ot, "0 For |Ael we can crudely bound it as,
1 Ad < (0') Kev. py.
k
Ly L. (0' (00)ev)))) <
(25)
To bound the variance observe that we have the following:
(Enr I'p² 19 <
E [Ly (00)) 001 (ew)rr
(with i ~ unif( Vy
(p',
y==
1
Lyni (0²)² 0r)
E
< 1ty
<
(by Equation III
It follows that I. [A] 9-, 00
< 4/7
14

---

Under review as a conference paper at ICLR 2022
Invoking Lemma 3
get the following bound with probability least 1 0/k
2 log (4/6)
A (1 + 7 1og log (K/A)
1
E egy Σ2)
(26)
T
VT
37
By bounding the first term on the right hand side with Lemma
2 and taking 1/2 we obtain,
T
6C
v 4k
log (4/8)
(1 + 2k) log (+/A)
Σ Lg
(0')
+
+
(27)
T
T
VT
3T
This completes the proof.
We ready to state the main theorem.
Theorem 1. If algorithm 7 is run on bounded rewards Ly E [0, Vt with step-size = /log k// (4kC), mixing parameter 7 1/2 and the model satisfies Assumption | then after T iterations with probability at least
max Σ by (0%) WE(K]
60 +
4k (2g(2k/0) (1 (1+2 (og(22/0)))
(2ggg)))
(2k/6)
2 llg(2k/0))
T
VT
3T
Vn
3n
1=1
(28)
for an ensemble of size n where tj sid unif(T))or E [n]]
Proof. If we fix and let rid unif(T). then the following a martingale difference sequence,
T
A, = Ly (ft:)
by (0*)
(29)
T
for which easy to see that |A,| < and A? < given boundedness of the loss. This readily let us apply Lemma with high probability 6/2k. Combining this with the bound Lemma 4 with probability 6/2k by using union bound completes the proof.
B CVAR
Conditional value at risk (CVaR) is the expected loss conditioned on being larger than the (1 - a)- quantile. This has a distributional robust interpretation which for discrete distribution can be written as,
m
CVaRR (0, = sup
Σ
p.e (0, x.) s.t. 10
(30)
pEAm
The optimal p of the above problem places uniform this best response by sorting the losses {E(0, k in descending order and assigning 1 index until saturation.
the tail. Practically we can compute
mass per
Primal CVaR When m is large stochastic variant is necessary. To obtain a stochastic subgradient for the model parameter, the naive approach to compute stochastic best response over mini- batch. This has been studied in detail in (Levy et al. 2020).
Dual CVaR An alternative formulation relies on strong duality of CVaR originally showed in (Rockafellar al, 2000).
m
CVaR, (0,
inf XER
Σ (e(0)xz)) - 2)+
(31)
am
In practice, approach is jointly minimize À and the model parameters by computing stochastic gradients as done in (Curi et al. 2019). Alternatively, we can find a close form solution for under mini-hatch (see e.g. (Xu et al.
2020
Appendix I.1)).
15

---

Under review as a conference paper at ICLR 2022
In comparison CFOL acts directly the probability distribution similarly to primal CVaR. How- ever, instead of finding a best response on uniformly sampled mini- it updates the weights iteratively and samples accordingly (see algorithm D. Despite this difference, it is interesting that a direct connection can be established between the uncertainty sets of the methods. The following section dedicated to this.
To be pedantic it is worth pointing out a minor discrepancy when applying CVaR the context of deep learning. Common architectures such ResNets incorporates batch normalization which updates the running mean and variance on the forward pass. The implication is that the entire mini- batch used to update these statistics despite the gradient computation only relying on the worst subset. This makes implementation in this setting slightly more convoluted.
B. RELATIONSHIP WITH CVAR
Exp3 is run with a uniform mixing to enforce exploration. This turns out to imply the necessary and sufficient condition for CVaR. We make this precise in the following lemma:
Lemma 5. Let be uniform mixing 7 + (1 7)g with an arbitrary distribution E Am and e E [0 such that the distribution has lower bound each element p.
Then [m-1)]
upper bound is implicitly implied on each element, ||p||so == max Ps S
Proof. Consider Pt for any i. At least (m - 2 of the mass must be on other components so P: S (m-1)n The result follows.
m
Corollary 1. Consider the uncertainty set of Exp3,
_Exp3 (Po) = p (
pp 2
Vi
(32)
Given that the above lower bound is only introduced for practical reasons, we might as well consider an instantiation of CVaR which turns out to be a proper relaxation,
CVaR (Po) = (p0==pAAnm
1 cm
Ilpl
S
(33)
with a (1-7)m+7' This leaves us with the following primal formulation,
T pel (0, x.)) s.t. |plloc
OVaRa (0, (0. = sup pe
(34)
am
Proof. From Lemma 5 and since CVaR requires
l/p|io0 S we have,
|p 5 (m 1)7
(35)
By simple algebra we have,
1
(36)
1-77mm= +
which completes the proof.
So if the starting point the uncertainty set is the simplex and the uniform mixing in Exp3 is therefore only for tractability reasons, then might as well minimize the CVaR objective instead. This could even potentially lead to a more robust solution as the uncertainty set larger (since the upper bound in CVVR does not imply the lower bound in Expx3..
There are two things to keep in mind though. First, a should not be too small since the optimization problem gets harder. It is informative consider the case where > 1/2 such that a m+I From this it becomes clear that the recasting as CVaR only works for small the uncertainty sets being related, the training dynamics, and thus the obtained solution, can be drastically different, we also observe experimentally in Section 5 For instance CVaR is known
2
Secondly, despite
16

---

Under review as a conference paper at ICLR 2022
Table 4: Summary of methods where is the number of samples and is the number of classes.
The discrete distribution p either governs the distribution over all N samples or over the k classes depending on the algorithm (see columns).
Uncertainty set
Over data point (m N)
Over class labels (m k)
Exxá (Po) {pE Am 4oVaR (Po) = {p Am
Pi
2 vi 1pll0c S
FOL
& Wexler 2016)
CFOL (ours)
CVaR (Levy et al. 2020)
LCVaR (Xu et al. 2020
for having high variance (Curi et al. 2019) while the uniform mixing in CFOL prevents this. It is worth noting that despite this uniform mixing we are still able to show convergence for CFOL in terms of the worst class in Section 3.1
In Table 4 we provide an overview of the different methods induced by the choice of uncertainty set.
C EXPERIMENTS
(a) |00 1/255
(b) ||0| = 2/255
1.0
1.0
Robust Taxt accuracy
Robbutt accuracy
0.6
0.6
0.4
0.4
0.0
0.0
aurilme
automobile
bird
deer
dog
sbip
buck
aurllane
automabile
cat
dog
keg
home
truck
Figure 4: Robust test accuracy under different norm-ball sizes after clean training on CIFARIO. The non-uniform distribution over class accuracies, even after clean training, indicates that the inferior performance on some classes is not consequence of adversarial training. Rather, the inhomogeneity after perturbation seems be an inherent feature of the dataset.
Table 5: Robust accuracy after early stopping ERM-AT based on different metrics of the validation set. The indicated performance is the test set. Notice that only improve the worst class marginally while suffering significantly in terms of average accuracy if we early stop based on the worst class.
Early stopping metrics
Average robust accuracy Worst class robust accuracy
Average
0.47
0.38
Worst class
0.14
0.18
Table 6: Comparison between standard adversarial training (ERM-AT) with and without temporal ensembling (TE). TE improves the robust accuracy the worst class while maintaining the average robust accuracy. However, TE leads to drop in terms of the clean accuracy.
ERM-AT
ERM-AT (TE)
Average
0.82
0.74
aCCylean
Worst class
0.54
0.51
Average
0.47
0.47
acCrobb
Worst class
0.14
0.23
17

---

Under review as a conference paper at ICLR 2022
training
training
1.0
Clain test 3ccursy
Rohust TAIE arcuracy
0.6
0.4
0.2
Casses
Classes
Clean training
Adversarial training
1.0
1.0
Clain tet tstaacurgg
Robust tast accumcy
0.8
0.6
0.4
0.4
0.0
0.0
airplane
dog
Horte
mankey
alriaae
bld
deer
dag
herse
monkay
stip
tuuh
Figure 5: Clean training and adversarial training CIFARIO0 100 (top) and STL10 (bottom) using ERM-AT with PGD-7 attacks train time PGD-20 attacks at test time for the robust test ac- curacy. The CIFARI00 classes sorted for convenience. Notice that CIFAR100 has class with zero robust accuracy with adversarial training.
ERM-AT
CFOL-AT
Robus 125t SICURESY
0.6
Robust text accumry
0.6
0.4
0.4
0.2
0.2
0.0
0.0
Casses
ERM-AT
CFOL-AT
Robust accuoo accurry
Robust taxt acruney
0.6
0.4
0.4
0.2
aitplane
bad
car
Jeer
deg
torn
monley
ship
incc
sinllan
Car
deeer
dog
hone
monkey
ship
buck
Figure 6: Robust class accuracy for CIFAR 100 and STL.10 respectively. Vertical black error bars dicate one standard deviation. The red and black horizontal line indicates the minimum and average respectively. The classes on both ERM-AT and CFOL-AT are ordered according to the accuracy on ERM to make comparison easier.
18

---

Under review as a conference paper at ICLR 2022
Table For fair comparison we also consider early stopping based on the worst class accuracy on the hold-out set. As can be observed the results for CFOL-AT do not differ significantly from early stopping using the average robust accuracy, so standard training setups do not have to modified further.
ERM-AT
CFOL-AT
FOL-AT
Average
0.70 0.05
0.73
0.75
aCCclean
20% tail
0.53 0.04
0.64
0.59 0.02
Worst class
0.52
0.62
0.57
CIFAR10
Average
0.44
0.00
0.48
acCrob
20% tail
0.25 0.01
0.33 0.03
0.29
Worst class
+
0.31 0.02
0.27 +
Average
0.55
0.04
0.55
aCCclean
20% tail
0.33 0.04
0.34
0.04
Worst class
0.18 0.02
0.19 + 0.04
0.17
CIFAR100
Average
0.24 0.00
0.26
acC
20% tail
0.07 0.02
0.09 0.03
0.07
0.02
Worst class
0.01
0.02 0.02
0.01 0.00
Average
0.54 0.05
0.04
aCCclean
20% tail
0.42 0.11
0.35
Worst class
0.38 0.23 0.09
0.29
STL10
Average
0.31 0.03
0.33
0.33
aCCrob
20% tail
0.04
0.20
0.02
0.14
Worst class
0.08 0.04
0.17
0.11
Table 8: Comparison between different sizes of -bal attacks CIFAR10. The constraint used at both training and test time. When the attack size is increased beyond the usual 8/255 constraint we still observe that CFOL-AT increases the robust accuracy for the weakest classes while taking a minor drop in the average robust accuracy. Interestingly. the gap between ERM-AT and CFOL-AT seems to enlarge. See Appendix C.2 for more detail on the attack hyperparameters.
ERM-AT
CFOL-AT
Average
0.73 0.01
0.75 + 0.00
aCCelean
20% tail
0.51 + 0.03
0.66 + 0.01
Worst class
0.47 0.03
0.63 0.02
110||00 88/255
Average
0.47 + 0.03
0.46
acCyob
20% tail
0.24 0.02
Worst class
0.20 + 0.02
0.30 0.30
Average
0.63 0.01
0.63 1.63:00011
aCCelean
20% tail
0.31 + 0.02
Worst class
0.26 0.02
0,51
||0||o0 < 12/255
Average
0.38 0.00
0.35
acCroh
20% tail
0.12 + 0.01
0.23 +
Worst class
0.09 + 0.01
0.22 + 0.02
19

---

Under review as a conference paper at ICLR 2022
Table 9: Model performance on CIFARIO under AutoAttack (Croce Hein 2020 The models still uses 7 steps of PGD at training time with a f -constrain of $/255. Only at test time is the attack exchanged with AutoAttack under the same constraint. CFOL-AT is robust AutoAttack in the sense that the worst class performance is still improved. However, as expected, the performance is worse for both methods in comparison with their respective 20-step PGD based attacks at test time.
ERM-AT
CFOL-AT
Average
0.74 = 0.01
0.75 + 0.00
aCCelean
20% tail
0.52 0.03
0.66 = 0.01
Worst class
0.48 = 0.04
0.63 0.02
Average
0.41 0.03
0.40 0.00
aCCrab
20% tail
0.17 = 0.02
0.21 + 0.02
Worst class
0.12 = 0.01
0.20 = 0.01
Table 10: Reweighted variant of CFOL. Algorithm [ [samples from the adversarial distribution p. Alternatively one sample data points uniformly and instead reweight the gradients for the model using In expectation, an update of these two schemes are equivalent. To see why, observe that in CFOL the model has access to the gradient Vo).,,(0). We can obtain an un- biased estimator by instead reweighting a uniformly sampled class, i.e. Ey-p, (VeLg. = E, Ey-umit(()), [kp, Vo (.)). With classes sampled uniformly the unbiased estimator for the ad- versary becomes T. 1 [t'= Iiyh Vyy. Thus, one update of CFOL and the reweighted variant are equivalent in expectation. However, note that we additionally depended on the internals of the model's 's update rule and that the immediate equivalence we get is only in expectation. We test the reweighted variant of CFOL-AT on CIFAR1O and observe similar results as for CFOL-AT.
aCCclean 20% tail
acCrob 20% tail
Average
Worst class
Average
Worst class
CFOL-AT (reweighted) 0.75
0.64
0.64
0.45
0.31
0.31
C.I HYPERPARAMETERS
In this section provide additional details to the hyperparameters specified in Section 5
For all experiment we use data augmentation in the form of random cropping. random horizontal flip, color jitter and degrees random rotations. For temporal ensembling (TE) in (Dong et al.) 2021)) and set the momentum to 0.9, balancing weight parameter to 30 along a Gaussian ramp-up curve until epoch 50. See Appendix C.3 for precise definition of the regularization technique.
the parameters
For CFOL-AT used the adversarial step-size parameters as for ERM-AT described in Section 5 CFOL-AT seems to be reasonable robust to step- size choice as seen in Table []] Similarly for FOL-AT we use the same parameters for ERM-AT and set = 5 10-7 after optimizing based on the worst class robust accuracy. With both methods we make an exception with STL10, where, due to the fewer iterations induced by the 5 times smaller dataset, we scale the adversarial step-size linearly by the dataset ratio 5, such that an equally strong attack can be obtained.
5 10-6 across all datasets and the same
The adversarial step-size picked for both FOL-AT and CFOL-AT is smaller in practice than theory suggests. This suggests that the mistake bound in Assumption is not satisfied for any sequence. Instead rely the sampling process be only mildly adversarial initially implicitly enforced by the small adversarial step-size. It is an interesting future direction to incorporate this implicit tempering directly into the mixing parameter y instead.
For LCVaR-AT we first optimized over the size of the uncertainty set by adjusting the parameter a. Despite getting reasonable performance for some with 0.2 the method turned out to have large variance, For this reason we explored reducing the model learning rate 7 for which we found that 0.05 gave better performance while having much smaller variance. It is not surprising that
20

---

Under review as a conference paper at ICLR 2022
the method requires smaller step-sizes given how CVaR methods assign higher weight to fraction of the batch at every iteration as explained Appendix B Maybe unnecessarily meticulous, we also ensure that temporal ensembling indeed improves model performance for ACT by also running the method without the regularization. Our instantiation of LCVAR-AT used for comparison thus uses a 0.2 and 0.05.
The hyperparameter exploration can found in Table I1
Table 11: Hyperparameter exploration for CFOL-AT, LCVaR-AT and FOL-AT.
Parameters
acCrob
aCCclean
TE
Average
Worst class
Average
Worst class
Yes
0.1
1 10-6
0.49
0.30
0.75
0.56
Yes
0.1
2 x 10-6
0.49
0.30
0.76
0.61
CFOL-AT
Yes
0.1
5 x 10-6
0.47
0.30
0.76
0.65
Yes
0.1
5 10
0.46
0.31
0.75
0.64
No
0.1
0.2
0.44
0.15
0.81
0.56
Yes
0.01
0.2
0.48
0.20
0.75
0.49
Yes
0.05
0.2
0.48
0.22
0.74
0.52
ACV
Yes
0.1
0.1
0.34
0.16
0.59
0.34
Yes
0.1
0.2
0.46
0.20
0.73
0.50
Yes
0.1
0.5
0.48
0.19
0.76
0.49
Yes
0.1
2.5 10-7
0.50
0.19
0.77
0.48
FOL-AT
Yes 0.1
5x 10-7
0.50
0.24
0.79
0.60
Yes
0.1
1 10-6
0.50
0.22
0.80
0.55
C.2 EXPERIMENTAL SETUP
In this section provide additional details for the experimental setup specified in Section The experiments are conducted on the following three datasets:
CIFAR10 50,000 training examples of 32 32 dimensional images and 10 classes.
CIFAR100 50,000 training examples of 32 x 32 dimensional images and 100 classes.
STL10 5000 training examples of 96 96 dimensional images and 10 classes.
As noted in Section we use the average robust accuracy to early stop the model. In contrast with common practice though, use validation set instead of the test set to avoid overfitting to the test set. The class accuracies across the remaining two datasets, CIFARIO 100 and STL10, can be found in Figure 6 We also include results when the model early stopped based on the worst class accuracy on the validation set in Table 7 The mean and standard deviation all tables and figures computed
5 However, for CIFAR compute the statistics since all methods had one outlier with significantly worst performance.
conduct 6 experiments and pick the top 5 to
A radius of 8/255 is used for the fxx -onstrait attack unless otherwise noted. For training steps of PGD and a stepsize of 2/255. At test time we use 20 steps of PGD with a stepsize of 2.5 x 8/255
For 12/2ss-bounded attacks scale the training stepsize and test stepsize proportionally.
20
C.3 TEMPORAL ENSEMBLING
Let fo Rd + & be a model parameterized by that assigns a probability distribution over the classes for any Rd Temporal ensembling (Laine & Aila 2016 Dong al. 2021) computes a so called ensemble prediction for given data example æ; by maintaining an average over past predictions, V f- 7 v, (1-7) be the training objective. A regularizing term is added to the training objective that encourages predictions to stay close v.
(7) So (æx), where is the momentum term. Let é (Ja (x: (x=+0) 8),
max {e (fo (z, + +0),80 91) + w(t) Ilfo (x; + 5) - -val13] SE3
min 8
(37)
21

---

Under review as a conference paper at ICLR 2022
where (t) is the balancing weight parameter. Usually (t) interpolates from 0 to constant along Gaussian rampup eurve. That is, w(t) wxexp (-5(1 t)?) where min epoch max epoch? 1).
C.4 IMPLEMENTATION
We provide pytorch pseudo code for how CFOL can be integrated into existing training setups in Listing | FOL is similar in structure, but additionally requires associating unique index with each training example. This allows the sampling method to re-weight each example individually.
For LCVaR we use the implementation of (Xu et al. 2020), which uses the dual CVaR formulation described in Appendix B More specifically. LCVaR uses the variant which finds a closed form solution for X, since this was observed to be both faster and more stable in their work.
from torch. wtw.stttllsccomm data import DataLcader
sampler ClassSampler (dataset,, gamma=0.5) dataloader DataLoader (dataset, sampler-samplen
Training loop:
for img,y y in iter (dataloader)
attack img compute gradients and update model
compute logits
adv_loss = logits. argmax (dim=-1) !=
sampler campler.batch_uuee batch_update (y, eta adv_loss)
Listing 1: Pseudo code for CFOL.
22


Reviews:
[{"review_id": "wlTIEW7FEqy", "reviewer": "Reviewer_mvco", "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": "# Strengths\n- Although the proposed method builds on existing works (Shalev-Shwartz & Wexler, 2016; Auer et al., 2002), the novelty is relatively high: to my knowledge, there exists no AT method that focuses on the class with the worst accuracy, nor combines online learning for this purpose. \n- The paper is well written (best writing in my batch), precise, and I enjoyed reading it. I like that the authors (where convenient) first give intuition and then present the result, which helps to follow more easily. \n- It does a nice balance between theoretical analysis and empirical evaluation.\n----\n# Weaknesses\n- The paper does a very nice trade-off between theory and empirical analysis. However, as a potential direction for improvement, the empirical evaluation could be more on par with AT literature, for example:\n   - analysis with different radius of the ball, i.e. plots with varying $\\epsilon$ \n   - how robust is the method to other attacks (e.g. AutoAttack), is the catastrophic overfitting improved, etc.\n- The main result (Thm 1) is for an ensemble of size n, while (if I understood well) the experiments are with one model. The authors mention that a single model suffices, but if I am correct there are no results with an ensemble. Verifying Thm 1 empirically, e.g. showing how $n$ impacts final performances would connect better the result with the experiments. \n----\n# Recommendations\n- Since Tian et al. (2021) is a very recent work I do not take this into account for my rating, but other than that it might be helpful for the audience to include a comparison with it (either theoretical insight about advantages/disadvantages, or empirical comparison on CIFAR-10).\n- The abstract leaves it somewhat unclear what is the online learning aspect of the method (included in the title), maybe adding a sentence would be nice. \n- Write the requirement $C \\geq k \\log k $ in Thm 1 more explicitly as a separate assumption before stating Thm 1.\n- Typo: Fig.3 noteable $\\rightarrow$ notable \n- Since the main empirical results use temporal ensembling (TE) add a detailed description of it in the App. for completeness\n\n----\n# Questions\n1. Fig. 1: Does the robust test accuracy of clean training (left) follow a non-uniform trend across the classes? It would be interesting to see if this observation from Fig.1 is (not) a result of AT.\n2. If I am correct, temporal ensembling (TE) is used for all methods. This raises the question if the proposed method works well only in this setup with TE, and for completeness, it would be nice to point out this to the readers. Could the authors provide results without TE on CIFAR-10?\n", "summary_of_the_paper": "This paper points out that there could be applications where the worst class accuracy could be critical -- for example, the class with the worst class accuracy can be the main target for the attacks and that the difference between the worst robust test accuracy of a class and the average robust test accuracy can be large (also pointed out independently in Tian et al. (2021)). \n\nMotivated by this, the paper proposes a solution to use the Exponential-weight algorithm (Auer et al., 2002), where, as the empirical distribution is taken the adversarial distribution over classes, resulting in a method called Class Focused Online Learning (CFOL).\nThe proposed CFOL method is based on the Focused Online Learning (FOL) (Shalev-Shwartz & Wexler, 2016) method, which does not take the class label into account.\n\nThe authors show empirically that CFOL consistently improves the worst class accuracy on CIFAR-10, CIFAR-100, and STL10.\nMoreover, the authors provide high probability convergence guarantees for the worst class accuracy.", "summary_of_the_review": "The paper has several advantages \n(i) points out an overlooked problem in AT (to my knowledge), \n(ii) proposes a novel method for the problem with guarantees\n(iii) does a nice trade-off between theoretical analyses and empirical evaluation, and\n(iv) it is well written.\nThere are two main directions for improvement theoretically and empirically, e.g. better connection between the theoretical result and the empirical analyses, more exhaustive empirical evaluation on par with AT literature. Nonetheless, I found the paper very interesting and I think it is relevant for the ICLR audience.\nI am happy to raise my score if I misunderstood and the above comments are arguable, or if the authors provide improvements (see questions and comments above).", "strength_and_weaknesses": "", "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": {}}, {"review_id": "hkqyH4Q9ljG", "reviewer": "Reviewer_wi3v", "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": "Strengths:\n- Easy to understand writing\n- Straightforward, well-motivated method\n- Experimental results correspond with claims\n- Appropriate baselines\n- Experimental results outperform baselines\n\nWeaknesses:\nClarity: \n- \"ERM\" generally refers to algorithms that perform empirical risk minimization and adversarial training does not perform empirical risk minimization. Canonically ERM also refers to the standard training regime. The standard adv training regime should therefore not be referred to as ERM (this a problem throughout the text).\n- Table 2/3: $\\mathcal{A}$ canonically refers to an algorithm, so $\\mathcal{A}_{\\text{rob}}$ is confusing notation (one would assume it refers to a robust training algorithm); this should be renamed to another symbol and perhaps labels could be added to the table for further clarity.\n- In Table 2/3 it would be good to cite the methods/name them as they are not standard acronyms people use.\n- The writing can is often overly verbose or disorganized. For example, in the DRO section of the related work, other seemingly unrelated techniques are sandwiched between paragraphs specifically about DRO. Section 4 could also be considerably condensed (and renamed, as the section describes an experimental setup choice not an application of the algorithm).\n- What do the bounds in Table 2/3 represent exactly?\n\nRelated work/baselines: \n- It would be good to compare with relevant DRO literature: in [0] the authors propose an online learning technique for optimizing worst-case subgroup error (one instantiation of this could be subgroups = labels). \n\nSmall fixups:\n- Missing space after (2)\n\n[0] https://arxiv.org/abs/1911.08731", "summary_of_the_paper": "In this work, the authors present a method for maximizing minimum class-wise accuracy in the $\\ell_p$-adversarial setting. The proposed method uses an online learning algorithm (exponential weights) to choose classes adversarially at train-time to sample examples from (in place of randomly choosing examples from the given data distribution). The authors find their algorithm can effectively increase the class-wise worst-case accuracy on a number of standard datasets (CIFAR-10/100, STL10) in the $\\ell_\\inf, \\epsilon=8/255$ threat model.", "summary_of_the_review": "The paper is easy to understand, presents a straightforward/well-motivated method, and backs claims with corresponding experimental results. The presented methods also outperform the baselines. However, the paper has relatively minor issues with clarity and incomplete related work.", "strength_and_weaknesses": "", "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": "bK5zOnlC6Gt", "reviewer": "Reviewer_85vN", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "While the proposed method is intuitively reasonable for the main purpose of “protecting the weak”, I have several concerns regarding the motivation of the paper and the empirical results. \n\n1. In terms of the motivation, I do not see a strong motivation to protect the weakest class, given the fact that the average robust accuracy is less than 50%. That said, from the perspective of an adversary, arbitrary picking any class can suffice its attack goal. Perhaps, if we assume attacking difference class incurs a different benefit or cost for an attacker, there may exist a particular user case for protecting the weakest class.\n\n2. The performance of the baseline methods presented in this paper is not the state-of-the-art in adversarial robustness literature. In particular, the baseline method (ERM) for CIFAR-10 presented in Table 2 only achieves around 0.74 in clean accuracy and 0.47 in robust accuracy, whereas the state-of-the-art clean accuracy and robust accuracy are over 0.85 and 0.55, respectively [1, 2]. Even the original method of TRADES [3] you implemented should achieve a much higher accuracy than what you presented in Table 2. \n\n[1] Uncovering the Limits of Adversarial Training against Norm-Bounded Adversarial Examples, Sven Gowal, Chongli Qin, Jonathan Uesato, Timothy Mann, Pushmeet Kohli\n\n[2] Reliable Evaluation of Adversarial Robustness with an Ensemble of Diverse Parameter-free Attacks, Francesco Croce, Matthias Hein\n\n[3] Theoretically principled trade-off between robustness and accuracy, Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. \n\n3. Compared with Focused Online Learning (FOL), I do not see an obvious improvement of using your proposed CFOL method. Both the average clean and robust accuracies of CFOL are less than those of FOL by 0.04. Could you clarify why there is an average performance drop?\n\nOther comments:\n1. Theorem 1 provides a convergence guarantee for the worst class loss. Theoretically, if we have enough empirical samples, the proposed method should achieve a very small loss (correspondingly, a high accuracy) if T is sufficiently large. Can you clarify why the empirical results provided in Section 5 seem not reflect such theoretical claim?\n", "summary_of_the_paper": "Observing that existing adversarially-trained classifiers have different class-wise model performance, this paper aims to protect the most vulnerable class against an adversary who can smartly pick which class to attack. Built upon on a classical Bandit algorithm and adversarial training method, it proposes an algorithm called “Class Focused Online Learning”, which adaptively reweights the class-wise loss function over the training epochs. In addition, the paper proves a convergence guarantee for the worst class loss and provides empirical evaluations of their method on benchmark datasets.\n", "summary_of_the_review": "\nThe proposed method combines an online learning algorithm and an adversarial training approach, which is intuitive and new. However, the motivation for protecting the weak in an adversarial setting is not well-explained and justified in my perspective. In addition, the baseline results presented in the paper are far below the state-of-the-art and there does not seem to be a clear advantage of the proposed method over existing approach. Therefore, I suggest a reject for this paper given the abovementioned concerns.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "TghEbmLCuZ", "reviewer": "Reviewer_MFgG", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "-I'm not sure what do you mean by saying that the adversary is \"choosing the class\". There is the magnitude of noise, and the adversary maximizes the average loss of the learner. It doesn't choose a specific class (although some might be more vulnerable than others)\n\n-The error across classes is not perfectly uniform in the adversarial training process, but this is the case (sometimes) in the standard setting. What makes the adversarial training process different?\n\n-In the suggested method, you can perform exponential weights with full information, I don't see the reason for using bandit feedback (and it is not explained).\n\n-The technical novelty is only marginally novel and quite straightforward.\n\n-What about the following baseline - you have the empirical error, so perform an ERM with that \"penalize\" more some classes.\n[I guess the Hedge should work better]", "summary_of_the_paper": "The setting is robust learning to perturbations at test time (adversarial examples), where instead of minimizing the average loss, the goal is to minimize the loss of the class with the lowest accuracy.\nThat is, instead of a min-max problem, there is another maximization component over the classes.\n\nThis is motivated by an example that shows a larger variance in losses between classes than in the standard setting.\n\nThe authors suggest a method from online learning - exponential weight in the bandit setting (that is - Exp3). ", "summary_of_the_review": "My vote is - reject.\nI mentioned my concerns. It is possible that I did not assess the contributions correctly, I am willing to read the other reviews and reconsider my score if they convince me otherwise. ", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper looks at the worst-class adversarial error for multi-class classification problems. The question is given a certain level of adversarial error on average, is it possible that some classes have adversarial error significantly worse than average? And if so, is this a problem? I agree with the authors that there are applications where such an imbalance could be problematic; other than the examples provided by the authors I can also think of this being important from a point of view of fairness, depending on what exactly the class labels represent. The reviewers have raised the question of low accuracies reported in the empirical results compared to the state of the art on those datasets for adversarial learning. I share these concerns -- especially it's worth understanding whether more accurate models also have such an imbalance, or whether this imbalance is a result of incomplete training or models that are not representationally powerful enough. While I agree with the authors that 'state of the art' results' are not required for ICLR submissions, especially those making conceptual contriubtions, in this case I think further experiments may be needed in addition to addressing the other questions raised in the reviews. The authors acknowledge that they have made significant revisions in response to the reviews, but I think that would require a fresh review cycle.
Decision: Reject