# 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 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), using techniques from the online learning 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 CIFAR10. We also observe consistent behavior across
CIFAR100 and STL10. Intriugingly, we find that minimizing the worst case can
even sometimes improve the average.

1 INTRODUCTION

The susceptibility of neural networks to adversarial noise (Goodfellow et al., 2014; Szegedy et al.,
2013) has been a grave concern over the launch of such systems in real-world applications. Several 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). In response, even stronger attacks have been proposed (Carlini & Wagner, 2016; Engstrom
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 an attacker can
pick the class adversarially in addition to the adversarial perturbation. It turns out that the worst
performing class can indeed be much worse than the average in adversarial training. This difference
is already present in 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 CIFAR10
where the accuracy across classes is far from uniform with 47% average robust accuracy while the
worst class is 14% (see Figure 1). The effect is even more prevalent when more classes are present
as in CIFAR100 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).

This dramatic drop in accuracy for the weakest classes begs for different approaches than the classical 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 we aim at becoming robust to an 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.


-----

Clean training


Adversarial training


1.0



1.0

0.8

0.6

0.4

0.2

0.0


0.8

0.6

0.4

0.2

0.0


Figure 1: The error across classes is already not perfectly uniform in clean training on CIFAR10.
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 a red and black line respectively.

Concretely, we make the following contributions:



-  We propose a simple solution which relies on the classical bandit algorithm from the online
learning literature, namely the Exponential-weight algorithm for Exploration and Exploitation (Exp3) (Auer et al., 2002). The method is directly compatible with standard adversarial 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 at risk (CVaR)
(Rockafellar et al., 2000) uncertainty set from the distributional robust optimization.

**Overview** We define our new objective in Section 2, followed by the description of the proposed
method in Section 3. In Section 3.1 we prove convergence guarantees. We then move to the empirical 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 5 and we conclude in Section 6.


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 are vulnerable to small adversarially perturbation
of the input. Since then, there has been a growing body of literature addressing this safety critical
issue, spanning from certified robust model (Raghunathan et al., 2018), distillation (Papernot et al.,
2016), input augmentation (Guo et al., 2017), to adversarial training (Madry et al., 2017; Zhang
et al., 2019). We focus on adversarial training in this paper. While certified robustness is desirable,
adversarial training remains one of the most successful defenses in practice.

In a concurrent work Tian et 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 a 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 of the number of examples N instead of the number of classes k for
which usually k ≪ _N_ . We compare in more detail theoretically and empirically in Section 3.1 and
Section 5 respectively.

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 et al., 2020; Lee et al., 2020).


-----

**Distributional robust optimization** The accuracy over the worst class can be seen as a 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 al., 2013; Shapiro, 2017). Instead of
attempting to minimizing the empirical risk on a training distribution P0, this framework considers
some uncertainty set around the training distribution (P0) and seeks to minimize the worst case
_U_
risk within this set, supQ∈U (P0) Ex∼Q[ℓ(x)].

A choice of uncertainty set, which has been given significant attention in the community, is conditional value at risk (CVaR), which aims at minimizing the weighted average of the tail risk (Rockafellar 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-weighting over class labels, namely labeled conditional value at
risk (LCVaR) (Xu et al., 2020). 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 a 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 subpopulations, which introduces significant complications. It is thus concerned with a different setting, an
example being training on a 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 k class-conditional risks. The precise definition is given in Appendix B.1. We further
establish a direct connection between the uncertainty sets of CFOL and CVaR that we make precise
in Appendix B.1, which also contains a summary of the most relevant related methods in Table 4.

2 PROBLEM FORMULATION AND PRELIMINARIES

**Notation** The underlying data distribution is denoted by D with examples x ∈ R[d] and classes
_y_ [k]. A given iteration is characterized by t [T ], while p[y]t [indicates the][ y][th][ index of the]
_t[th] ∈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 A.

In classification, we are normally interested in minimizing the population risk E(x,y) [ℓ(θ, x, y)]
_∼D_
over our model parameters θ ∈ R[p], where ℓ is some loss function of θ and example x ∈ R[d] with
an associated class y ∈ [k]. Madry et al. (2017) formalized adversarially training by modifying
this objective with an adversarial perturbation to each example. That is, we instead want to find a
parameterization θ of our predictive model which solves the following optimization problem:


min _L(θ) := E(x,y)_
_θ_ _∼D_


max _,_ (1)
_δ_ _[ℓ][(][θ, x][ +][ δ, y][)]_
_∈S_ 


where each x is now perturbed by adversarial noise δ ∈S ⊆ R[d]. Common choices of S include
norm-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 1, since we only know with certainty that max ≥ avg.

Instead, we will focus on a different objective, namely minimizing the worst class-conditioned risk:


max _._ (2)
_δ_ _[ℓ][(][θ, x][ +][ δ, y][)]_
_∈S_ 


_Ly(θ) := Ex_ _p_ ( _y)_
_∼_ _D_ _·|_


min max
_θ_ _y∈[k]_


This follows the philosophy that “a chain is only as strong as its weakest link”. In our particular
setting it models a 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 2 is a discrete maximization problem its treatment requires more care.
We will take a common approach and construct a convex relaxation to this problem in Section 3.


-----

Class sampling distribution


0.15

0.10

p

0.05

0.00

airplaneautomobilebird cat deer dog froghorseshiptruck

Figure 2: Contrary to ERM, which samples the examples uniformly, CFOL samples from an adaptive distribution. The learned adversarial distribution is non-uniform over the classes in CIFAR10
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 Ny be the set of data point indices for class y such that the total number
of examples is N = _y=1_
_class-conditioned risk,_ _[|N][y][|][. Then, we are interested in minimizing the][ maximum empirical]_

[P][k] 1

max _Ly(θ) :=_ max (3)
_y∈[k]_ _|Ny|_ _iX∈Ny_ _δ∈S_ _[ℓ][(][θ, x][i][ +][ δ, y][)][.]_
b


We relax this discrete problem to a continuous problem over the simplex ∆k,

_k_

max _Ly(θ)_ max _pyLy(θ)._ (4)
_y_ [k] _≤_ _p_ ∆k
_∈_ _∈_ _y=1_

X

Note that equality is attained when p is a dirac on the argmax over classes.b [b]

Equation 4 leaves us with a two-player zero-sum game between the model parameters θ and the
class distribution p. From the perspective of p it is just a linear objective, albeit adversarially picked
by the model. This immediately let us use a no-regret algorithm under simplex constraint, namely
Hedge (Freund & Schapire, 1997):


_wy[t]_ [=][ w]y[t][−][1] _−_ _ηL[b]y(θ[t]),_ _p[t]y_ [= exp] _wy[t]_ _/_ exp _wy[t]_ _._ (Hedge)

_y=1_

 
 X  


To show convergence for (Hedge) the loss needs to satisfy certain assumptions. In our case of
classification, the loss is the zero-one loss ℓ(θ, x, y) = 1[hθ(x) = y], where hθ( ) is the predictive
_̸_ _·_
model. Hence, the loss is bounded, which is a sufficient requirement.

Note that (Hedge) relies on zero-order information of the loss, which we indeed have available.
However, in the current form, (Hedge) requires so called full information over the k dimensional
loss vector. In other words, we need to compute _Ly(θ) 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.

[b]

Following the seminal work of Auer et al. (2002), we instead construct an unbiased estimator of the
_k dimensional loss vector_ _L(θ[t]) := (L[b]1(θ[t]), ...,_ _Lk(θ[t]))[⊤]_ based on a sampled class y[t] from some
distribution y[t] _∼_ _p[t]. This stochastic formulation further lets us estimate the class conditioned risk_
_Lyt_ (θ[t]) with an unbiased sample[b] _i_ unif( _yt_ )[b]. This leaves us with the following estimator,
_∼_ _|N_ _|_
b _L[t]y_ [=] _Ly,i(θ[t])/p[t]y_ _y = y[t]_ (5)

0 otherwise




-----

**Algorithm 1: Class focused online learning (CFOL)**
Algorithm parameters: a step rule ModelUpdate for the model satisfying Assumption 1,
adversarial step-size η > 0, uniform mixing parameter γ = [1]/2, and the loss Ly,i(θ).
Initialization: Set w[0] = 0 such that q[0] and p[0] are uniform.
**foreach t in 0..T do**

_y[t]_ _∼_ _p[t]_ ; // sample class
_i[t]_ unif( _yt_ ) ; // sample uniformly from class
_∼_ _|N_ _|_
_θ[t][+1]_ = ModelUpdate(θ[t], Lyt,it (θ[t])) ; // update model parameters
_L[t]y_ [=][ 1] _y=y[t]_ _y_ // construct estimator
_{_ _}[L][y,i][t]_ [(][θ][t][)][/p][t] _[∀][y][ ;]_
_wy[t][+1]_ = wy[t] _L[t]y_ // update the adv. class distribution
e _[−]_ _[η]_ [e] _[∀][y][ ;]_
_qy[t][+1]_ = exp _wy[t][+1]_ _/_ _y=1_ [exp] _wy[t][+1]_ _∀y;_
_p[t]y[+1]_ = γ _k[1]_ [+ (1] _[ −]
[γ][)][q]y[t][+1]_ _∀y;_  


**end foreach** [P][k]

where Ly,i (θ) := maxδ _ℓ_ (θ, xi + δ, y). It is easy to verify that this estimator is unbiased,
_∈S_


_Ly(θ[t])_
Ey∼p _L[t]y_ = 1 − _p[t]y_ _· 0 + p[t]y_ _[·]_ _p[t]y_ = _Ly(θ[t])._ (6)
h i  
 b
e [b]

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[t].

We could pick p[t] to be the learned adversarial distribution, but it is well known that this can lead to
unbounded regret if some p[t]y [is small (see Appendix A for definition of regret). Auer et al. (2002)]
resolves this problem with Exp3, which instead learns a distribution q[t], then mixes it with a uniform
distribution, to eventually sample from p[t]y [=][ γ][ 1]k [+ (1][ −] _[γ][)][q]y[t]_ [where][ γ][ ∈] [(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 γ = [1]/2 suffice in our setting.

Our algorithm thus updates q[t][+1] with (Hedge) using the estimator _L[t]_ with sample drawn from p[t] and
subsequently plays p[t][+1]. CFOL in conjunction with the simultaneous update of the minimization
player can be found in algorithm 1 with an example of a learned distribution p[t] in Figure 2.

[e]

Practically, the scheme bears negligible computational overhead over ERM since the softmax required 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 a hypothetical worst case
scenario. Imagine a classification problem where one class is much harder to model than the remaining 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 ERM might be slow. The algorithm would naively pass over the entire
dataset in order to improve the hard class using only the fraction of examples belonging that class.
In contrast, if we can adaptively focus on the difficult class, we can avoid spending time on classes
that are already improved sufficiently. As long as we can adapt fast enough, as expressed through
the regret of the adversary, we should be able to improve on the convergence rate for the worst class.

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 we will assume that the model parameterized
by θ enjoys a so called mistake bound of C (Shalev-Shwartz et al., 2011, p. 288). The proof is
deferred to appendix A.


-----

**Assumption 1.dices (i[1], ..., i[T] For any sequence of classes) with i[t]** _yt the model enjoys the following bound for some (y[1], ..., y[T]_ ) ∈ [k][T] and class conditioned sample in- C _[′]_ _<_ and
_∈N_ _∞_
_C = max{k log k, C_ _[′]},_ _T_

_Lyt,it_ (θ[t]) _C._ (7)
_≤_
_t=1_

X

_Remark 1. The requirement C ≥_ _k log k will be needed to satisfy the mild step-size requirement_
_η ≤_ 2k in Lemma 1. 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-conditioned empirical risk.

**Theorem 1. If algorithm 1 is run on bounded rewards Lyt,it** (θ[t]) ∈ [0, 1] ∀t with step-size η =

log k/(4kC), mixing parameter γ = [1]/2 and the model satisfies Assumption 1, then after T
_iterations with probability at leastp_ _n_ 1 − _δ,_

1 4k log(2k/δ) 2 log(2k/δ)
max _Ly_ _θ[t][j]_ [
] + [(1 + 2][k][) log(2][k/δ][)] + + [2 log(2][k/δ][)]
_y∈[k]_ _n_ _j=1_ _≤_ [6]T[C] [+] p _√T_ 3T p _√n_ 3n

X 

b (8)

_iid_
_for an ensemble of size n where tj_ unif(T ) for j [n].
_∼_ _∈_

To contextualize Theorem 1, let us consider the simple case of linear binary classification mentioned
in Shalev-Shwartz & Wexler (2016). In this setting SGD needs O(CN ) iterations to obtain a consistent hypothesis. In contrast, the iteration requirement of FOL decomposes into a sum _O(C + N_ )
which is much smaller since both C and N are large. When we are only concerned with the convergence of the worst class we show that CFOL can converge as (C + k) where usually[e] _k_ _C._
_O_ _≪_
Connecting this back to our motivational example in the beginning of this section, this sum decomposition exactly captures our intuition. That is, adaptively focusing the class distribution can avoid

[e]
the learning algorithm from needlessly going over all k classes in order to improve just one of them.

From Theorem 1 we also see that we need an ensemble of size n = Ω( log(k/δ)/ε[2]), which has

only mild dependency on the number of classes k. If we wanted to drive the worst class error ε to

p

zero the dependency on ε would be problematic. However, for adversarial training, even in the best
case of the CIFAR10 dataset, the average error is larger than [1]/2. We can expect the worst class error
to be even worse, so that only a small n is required. In practice, a single model turns out to suffice.

Note that the maximum upper bounds the average, so by minimizing this upper bound as in Theorem 1, we are implicitly still minimizing the usual average loss. In addition, Theorem 1 shows
that a mixing parameter of γ = [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
et al., 2020). 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 to the second step-size decay (e.g., in Madry et al. (2017); 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 confirming this problem and propose a 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 on 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 we 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.


-----

Table 1: Robust accuracy on CIFAR10 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 5.

**ERM-AT (75)** **ERM-AT (33)** **CFOL-AT (33)**

Average **0.47** 0.45 0.42
Worst class 0.14 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 to run CFOL-AT for a shorter time to get consistent performance
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. (2019) in Table 1.
Although we see a 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 a regularization technique that was shown to mitigate overfitting in adversarial training (Laine & Aila, 2016; Dong et al., 2021). This allows us to reliably run CFOL-AT
under exactly the same training configuration as ERM-AT and thus prevents further hyperparameter
tuning. Additionally, TE leads to a more fair comparison with ERM-AT, which enjoys an improvement in terms of the worst class robust accuracy from 14% to 21%. We make use of this additional
regularization in all subsequent experiments. In this work we focus on the robust accuracy. However, we add a cautionary note, since we observe that TE can lead to a reduction in clean accuracy
(see Table 6).

5 EXPERIMENTS

We consider the common adversarial setting where the constraint set of the attacker is ℓ -bounded
_S_ _∞_
attacks. We test on three datasets with different dimensionality, number of examples per class and
number of classes. Specifically, we consider CIFAR10, 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 a**
ResNet50 network (He et al., 2016) with a learning rate τ = 0.1, momentum of 0.9, weight decay
of 5 · 10[−][4], batch size of 128 (Madry et al., 2017) with a piece-wise 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 we similarly adopt the common
attack radius of 8/255 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 hardware. 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” to all methods to indicate
that the training examples are adversarially perturbed according to adversarial training of Madry
et al. (2017). We consider ERM-AT as the core baseline, while we also implement FOL-AT and
LCVaR-AT as alternative methods that can improve the worst performing class. For fair comparison, 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 Appendix C.1 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 as the 20% tail) for both clean (accclean) and robust accuracy (accrob). The


-----

mean and standard deviation in all tables are computed over 5 independent executions. We note that
the aim is not to be state-of-the-art but rather provide a fair comparison between the methods.

The first core experiment is conducted on CIFAR10. In Table 2 the quantitative results are reported 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 performs better than LCVaR-AT, so for the next experiments we simply consider FOL as the non-ERM
comparison method.

The results for the remaining datasets can be found in Table 3. The results exhibit similar patterns
to the experiment on CIFAR10, 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 7), larger attack radius (see Table 8), 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 a 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 CIFAR10 while having small variance, suggestion
that sometimes focusing on the worst cases can improve the average.

Table 2: Accuracy on CIFAR10. For both clean test accuracy (accclean) 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 FOLAT). CFOL-AT significantly improves the robust accuracy for both the worst class and the 20% tail,
while only incurring a 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.75 ± 0.01 **0.79 ± 0.01**
accclean 20% tail 0.52 ± 0.03 **0.66 ± 0.01** 0.54 ± 0.02 0.61 ± 0.03
Worst class 0.48 ± 0.04 **0.63 ± 0.02** 0.51 ± 0.03 0.56 ± 0.03

Average 0.47 ± 0.02 0.46 ± 0.00 0.46 ± 0.03 **0.50 ± 0.00**
accrob 20% tail 0.24 ± 0.02 **0.31 ± 0.02** 0.23 ± 0.02 0.28 ± 0.02
Worst class 0.21 ± 0.02 **0.30 ± 0.01** 0.20 ± 0.01 0.22 ± 0.03


ERM-AT


CFOL-AT




0.6

0.4

0.2

0.0


0.6

0.4

0.2

0.0


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 improvement in the minimum accuracy is notable when using CFOL-AT, while there is only marginal
difference in the average accuracy.


-----

Table 3: Clean test accuracy (accclean) and robust test accuracy (accrob) on CIFAR100 and STL10.
We compare our method (CFOL-AT) with standard adversarial training (ERM-AT) and two baselines (LCVaR-AT and FOL-AT). CFOL-AT consistently improves the worst class accuracy as well
as the 20% worst tail.

**ERM-AT** **CFOL-AT** **FOL-AT**


Average **0.54 ± 0.02** 0.52 ± 0.05 0.53 ± 0.01
accclean 20% tail 0.30 ± 0.04 **0.35 ± 0.06** 0.31 ± 0.04
Worst class 0.12 ± 0.04 **0.19 ± 0.04** 0.17 ± 0.04

Average **0.27 ± 0.00** 0.24 ± 0.02 0.26 ± 0.00
accrob 20% tail 0.07 ± 0.02 **0.09 ± 0.03** 0.07 ± 0.02
Worst class 0.01 ± 0.01 **0.03 ± 0.02** 0.01 ± 0.01

Average 0.55 ± 0.03 **0.55 ± 0.02** 0.54 ± 0.02
accclean 20% tail 0.25 ± 0.10 **0.42 ± 0.08** 0.27 ± 0.07
Worst class 0.23 ± 0.09 **0.38 ± 0.07** 0.22 ± 0.02

Average **0.35 ± 0.01** 0.34 ± 0.01 0.35 ± 0.01
accrob 20% tail 0.09 ± 0.03 **0.18 ± 0.03** 0.11 ± 0.04
Worst class 0.07 ± 0.03 **0.16 ± 0.03** 0.07 ± 0.01


CIFAR100

STL10

CONCLUSION


In this work, we have introduced a 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 a 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, it is interesting to understand why adversarial
perturbations leads to inhomogeneous accuracies over classes.

REFERENCES

Jean-Yves Audibert, S´ebastien Bubeck, and R´emi 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`o Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48–77, January 2002. ISSN 00975397, 1095-7111. doi: 10.1137/S0097539701398375.

Aharon Ben-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–357, 2013._

Nicholas Carlini. Is ami (attacks meet interpretability) robust to adversarial examples? _arXiv_
_preprint arXiv:1902.02322, 2019._

Nicholas Carlini and David Wagner. Defensive distillation is not robust to adversarial examples.
_arXiv preprint arXiv:1607.04311, 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._


-----

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.01606, 2021.

John Duchi and Hongseok Namkoong. Learning models with uniform performance via distributionally robust optimization. arXiv preprint arXiv:1810.08750, 2018.

John C Duchi, Tatsunori Hashimoto, and Hongseok Namkoong. Distributionally robust losses
against mixture covariate shifts. Under review, 2019.

Logan Engstrom, Andrew Ilyas, and Anish Athalye. Evaluating and understanding the robustness
of adversarial logit pairing. arXiv preprint arXiv:1807.10272, 2018.

Yanbo Fan, Siwei Lyu, Yiming Ying, and Bao-Gang Hu. Learning with average top-k loss. arXiv
_preprint arXiv:1705.08826, 2017._

Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an
application to boosting. Journal of computer and system sciences, 55(1):119–139, 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 input transformations. arXiv preprint arXiv:1711.00117, 2017.

Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp.
770–778, 2016.

Kenji Kawaguchi and Haihao Lu. Ordered sgd: A new stochastic optimization framework for empirical 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.12655, 2020.

Samuli Laine and Timo Aila. Temporal ensembling for semi-supervised learning. arXiv preprint
_arXiv:1610.02242, 2016._

Jaeho Lee, Sejun Park, and Jinwoo Shin. Learning bounds for risk-sensitive learning. arXiv preprint
_arXiv:2006.08138, 2020._

Daniel Levy, Yair Carmon, John C Duchi, and Aaron Sidford. Large-scale methods for distributionally robust optimization. arXiv preprint arXiv:2010.05893, 2020.

Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated
learning. arXiv preprint arXiv:1905.10497, 2019.

Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. Tilted empirical risk minimization.
_arXiv preprint arXiv:2007.01162, 2020._

Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Doll´ar. Focal loss for dense
object detection. In Proceedings of the IEEE international conference on computer vision, pp.
2980–2988, 2017.


-----

Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.
Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.06083,
2017.

Tianyu Pang, Xiao Yang, Yinpeng Dong, Hang Su, and Jun Zhu. Bag of tricks for adversarial
training. arXiv preprint arXiv:2010.00467, 2020.

Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. Distillation as a
defense to 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 examples. arXiv preprint arXiv:1801.09344, 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._

R Tyrrell Rockafellar, Stanislav Uryasev, et al. 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:1809.02104, 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 al. Online learning and online convex optimization. Foundations and trends
_in Machine Learning, 4(2):107–194, 2011._

Alexander Shapiro. Distributionally robust stochastic programming. SIAM Journal on Optimization,
27(4):2258–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.6199, 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.14240, 2021.

Ziyu Xu, Chen Dan, Justin Khim, and Pradeep Ravikumar. Class-weighted classification: Tradeoffs and robust approaches. In International Conference on Machine Learning, pp. 10544–10554.
PMLR, 2020.

Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan.
Theoretically principled trade-off between robustness and accuracy. In International Conference
_on Machine Learning, pp. 7472–7482. PMLR, 2019._


-----

A CONVERGENCE ANALYSIS

A.1 PRELIMINARY AND NOTATION

Consider the abstract online learning problem where for every t ∈ [T ] the player chooses an action
_x[t]_ and subsequently the environment reveals the loss function l(·, y[t]). As traditional in the online
learning literature we will measure performance in terms of regret, which compares our sequence of
choices {x[t]}t[T]=1 [with a fixed strategy in hindsight][ u][,]


_l(x[t], y[t])_ min _l(u, y[t])._ (9)
_−_ _x_
_t=1_ _t=1_

X X


_RT (u) =_


If we, instead of minimizing over losses l, maximize over rewards r we define regret as,


_r(u, y[t]) −_ _r(x[t], y[t])._ (10)
_t=1_ _t=1_

X X


_T (u) = max_
_R_ _x_


When we allow randomized strategy, as in the bandit setting, RT becomes a random variable that
we wish to upper bound with high probability. For convenience we include an overview over the
notation defined and used in Section 2 and Section 3 below.

_k_ Number of classes

_T_ Number of iterations

_p[t]y_ The y[th] index of the t[th] iterate

1{boolean} The indicator function

unif(n) Discrete uniform distribution over n elements


_y_ Set of data point indices for class y [k]
_N_ _∈_

_N =_ _y=1_ The size of the data set

_[|N][y][|]_

_Ly,i (θ) := maxδ_ _ℓ_ (θ, xi + δ, y) Loss on a particular example
_∈S_
_Ly(θ) :=[P][k]_ 1y _i_ _y_ _[L][y,i][ (][θ][)]_ The empirical class-conditioned risk

_|N_ _|_ _∈N_

_L (θ) := (L[b]1 (θP), . . .,_ _Lk (θ))[⊤]_ The vector of all empirical class-conditioned risks

b

_L[t]y_ [:=][ L][y,i] [(][θ][t][)] Class-conditioned estimator at iteration t with i unif( _y_ )

b [b] _∼_ _|N_ _|_

A.2 CONVERGENCE RESULTS

We restate Algorithm 1 while leaving out the details of the classifier for convenience. Initialize w[0]
such that q[0] and p[0] are uniform. Then Exp3 proceeds for every t ∈ [T ] as follows:

1. Draw class y[t] _∼_ _p[t]_

2. Observe a scalar reward L[t]y[t]

3. Construct estimator _L[t]y_ [=][ L]y[t] _[t]_ [1][{][y][=][y][t][}][/p]y[t] _[∀][y]_

4. Update distribution
_w[t][+1]_ = w[t] _−_ _ηL[e][t]_ [e]

_qy[t][+1]_ = exp _wy[t][+1]_ _/_ _y=1_ [exp] _wy[t][+1]_ _∀y_
_p[t]y[+1]_ = γ _k[1]_ [+ (1] _[ −]
[γ][)][q]y[t][+1]_ _∀y_  


[P][k]

We can bound the regret of Exp3 (Auer et al., 2002) in our setting, even when the mixing parameter
_γ 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 q throughout. From py = _[γ]k_ [+ (1][ −] _[γ][)][q][y][ it can]_

easily be verified that,
1 1

(11)

_py_ _≤_ _γ[k]_ [and][ q]p[y]y _≤_ 1 _γ_ [for all][ y.]

_−_


-----

**Lemma 1. If Exp3 is run on bounded rewards L[t]y[t][ ∈]** [[0][,][ 1]][ ∀][t][ with][ η][ ≤] _[γ/k][ then]_


_T_ _T_ _T_

_ηk_

_RT[adv](u) =_ _⟨u,_ _L[t]⟩−_ _⟨q[t],_ _L[t]⟩≤_ [log]η[ k] + (1 _γ)γ_ _L[t]y_ (12)

_t=1_ _t=1_ _t=1_

_−_

X X X

[e] [e]

_Proof. We can write the estimator vector as_ _L[t]_ = _Lp[t]y[t]y[t][t][ e][y][t][ where][ e][y][t][ is a canonical basis vector.]_

By assumption we have L[t]y[t][ ∈] [[0][,][ 1]][. Combining this with the bound on][ 1][/][p][y][ in Equation 11 we]

[e]

have _L[t]y_
step-size η[≤] is small enough. Specifically, we have that if[k][/][γ][ for all][ y][. This lets us invoke (Shalev-Shwartz et al., 2011, Thm 2.22) as long as the] η _/L[e][t]y_
_≤_ [1] _[≤]_ _[γ][/][k]_

[e] _T_ _T_ _T_ _k_

_u,_ _L[t]_ _q[t],_ _L[t]_ + η _qy[t]_ [(]L[e][t]y[)][2][.] (13)
_⟨_ _⟩−_ _⟨_ _⟩≤_ [log]η[ k]
_t=1_ _t=1_ _t=1_ _y=1_

X X X X

[e] [e]

By expanding _L[t]y_ [and applying the inequalities from Equation 11 we can get rid of the dependency]
on q and p,

[e] _T_ _k_ _T_

log k _qy[t]_ _[t]_

+ η _qy[t]_ [(]L[e][t]y[)][2][ ≤] [log][ k] + η _y[t]_ [)][2]
_η_ _t=1_ _y=1_ _η_ _t=1_ (p[t]y[t] [)][2][ (][L][t]

X X X

_T_

_k_

+ η _y[t]_ [)][2] (14)

_≤_ [log]η[ k] (1 _γ)γ_ [(][L][t]

_t=1_

_−_

X

_T_

_ηk_
+ _L[t]y[t]_ _[,]_

_≤_ [log]η[ k] (1 _γ)γ_

_t=1_

_−_

X

where the last line uses the boundedness assumption L[t]y □

_[∈]_ [[0][,][ 1]][ ∀][y][.]

It is apparent that we need to control the sum of losses. We will do so by assuming that the model
admits a mistake bound as in Shalev-Shwartz & Wexler (2016); Shalev-Shwartz et al. (2011).
**Assumption 1.indices (i[1], ..., i For any sequence of classes[T]** ) with i[t] _yt the model enjoys the following bound for some (y[1], ..., y[T]_ ) ∈ [k][T] _and class conditioned sample C_ _[′]_ _<_ _and_
_∈N_ _∞_
_C = max{k log k, C_ _[′]},_ _T_

_Lyt,it_ (θ[t]) _C._ (15)
_≤_
_t=1_

X

Recall that we need to bound L[t]y [:=][ L][y,i][t] [(][θ][t][)][, where][ y][ are picked adversarially and][ i][t][ are sampled]
uniformly, so the above is sufficient.
**Lemma 2. If the model satisfies Assumption 1 and algorithm 1 is run on bounded rewards**
_Lyt,it_ (θ[t]) [0, 1] _t with step-size η =_ log k/(4kC) and mixing coefficient γ = [1]/2 then
_∈_ _∀_

_T_

p

_⟨u,_ _L[t]⟩≤_ 6C. (16)
_t=1_

X

[e]

_Proof. By expanding and rearranging Lemma 1,_

_T_ _ηk_ _qy[t]_ _[t]_ _T_

_u,_ _L[t]_ + _L[t]y[,]_ (17)
_t=1_ _⟨_ _⟩≤_ [log]η[ k] (1 _γ)γ_ [+] _p[t]y[t]_ ! _t=1_

_−_

X X

as long as η ≤ _[γ]/k. Then by using our favorite inequality in Equation 11 and under Assumption 1,[e]_


_ηk_ _qy[t]_ _[t]_

(1 _γ)γ_ [+] _p[t]y[t]_
_−_


log k


_T_

_t=1_ _L[t]y_ _[≤]_ [log]η[ k]

X


_ηk_

(1 _γ)γ_ [+]
_−_


_C,_ (18)


1 − _γ_


-----

To maximize (1 − _γ)γ) we now pick γ =_ [1]/2 so that,

log k _ηk_ 1

+ _C_ + (4ηk + 2) C. (19)
_η_ (1 _γ)γ_ [+] 1 _γ_ _≤_ [log]η[ k]
 _−_ _−_ 

For η, notice that it appears in two of the terms. To minimize the bound respect to η we pick
_η =_ log k/(4kC) such that [log]η[ k] = 4ηkC, which leaves us with,
p


log k


4kC log k + 2C. (20)


+ (4ηk + 2)C ≤ 2


From the first term it is clear that since C ≥ _k log k by assumption then the original step-size_
requirement of η ≤ [1]/2k is satisfies. In this case we can additionally simplify further,

2 4kC log k + 2C ≤ 6C. (21)
p □

This still only gives us a bound on a stochastic object. We will now relate it to the empirical class
conditional risk _Ly(θ) by using standard concentration bounds. To be more precise, we want to_
show that by picking u = ey in ⟨u, _L[t]⟩_ we concentrate to _Ly(θ). Following Shalev-Shwartz &_
Wexler (2016) we adopt their use of a Bernstein’s type inequality.[b]
**Lemma 3 (e.g.** Audibert et al. (2010, Thm.[e] 1.2)). Let[b] A1, ..., AT be a martingale differ_ence sequence with respect to a Markovian sequence B1, ..., BT and assume |At| ≤_ _V and_
E _A[2]t_ _s. Then for any δ_ (0, 1),

_[|][ B][1][, . . ., B][t]_ _≤_ _∈_
 


2s log ([1]/δ)

+ _[V][ log (][1][/][δ][)]_

_√T_ 3T


_≥_ 1 − _δ._ (22)


_At_
_t=1_ _≤_

X


**Lemma 4. If algorithm 1 is run on bounded rewards Lyt,it** (θ[t]) ∈ [0, 1] ∀t with step-size η =

log k/(4kC), mixing coefficient γ = [1]/2 and the model satisfies Assumption 1, then for any y ∈ [k]

pwe obtain have the following bound with probability at least 1 − _[δ]/k,_


_T_

_Ly_ _θ[t][
]_
_≤_ [6]T[C] [+]
_t=1_

X 

b


4k log ([k]/δ)


+ [(1 + 2][k][) log (][k][/][δ][)] _._ (23)

3T


_Proof. Pick any y ∈_ [k] and let u = ey in ⟨u, _L[t]⟩. By construction the following defines a martingale_
difference sequence,

[e]

_At =_ _Ly(θ[t])_ _ey,_ _L[t]_ = _Ly(θ[t])_ _ey,_ [1] _Lyt,it_ (θ[t])eyt _._ (24)
_−⟨_ _⟩_ _−⟨_ _p[t]y[t]_ _⟩_

In particular note that i[t] is uniformly sampled. To apply the Bernstein’s type inequality we just need[b] [e] [b]
to bound _At_ and E _A[2]t_ . For _At_ we can crudely bound it as,
_|_ _|_  _[|][ q][t][, θ][t][]_ _|_ _|_

_|At| ≤|L[b]y(θ[t])| + |⟨ey,_ _p[1][t]y[t]_ _Lyt,it_ (θ[t])eyt _⟩| ≤_ 1 + _γ [k]_ _[.]_ (25)

To bound the variance observe that we have the following:


2
_t_ _t[i]_
_ey,_ _L[t]_ _q_ _, θ_
_⟨_ _⟩_ _|_

[e]


_k_ _p[t]y[′]_

_Ly′,i(θ[t])[2]_ _θ[t][]_ (ey)y′ (with i unif( _y′_ ) _y[′])_

_≤_ _y[′]=1_ (p[t]y[′] [)][2][ E] _|_ _∼_ _|N_ _|_ _∀_

X 

= [1] E _Ly,i_ _θ[t][
][2]_ _θ[t][i]_

_p[t]y_ _|_
h 

(by Equation 11)

_≤_ _p[1][t]y_ _≤_ _γ [k]_ _[.]_


It follows that E _A[2]t_ _/γ_
 _[|][ q][t][, θ][t][]_ _≤_ _[k]_


-----

Invoking Lemma 3 we get the following bound with probability at least 1 − _[δ]/k,_


2 _γ[k]_ [log (][k][/][δ][)]


(1 + _γ[k]_ [) log (][k][/][δ][)]

(26)
3T


1 _T_ _T_ 2 _γ[k]_ [log (][k][/][δ][)] (1 + _γ[k]_ [) log (][k][/][δ][)]

_Ly_ _θ[t][
]_ _ey,_ _L[t]_ + +

_T_ _t=1_ _≤_ _T[1]_ _t=1⟨_ _⟩_ q _√T_ 3T

X  X

By bounding the first term on the right hand side with Lemma 2 and takingb [e] _γ =_ [1]/2 we obtain,


_T_

1

_Ly_ _θ[t][
]_

_T_ _≤_ [6]T[C] [+]

_t=1_

X 

This completes the proof. b


4k log ([k]/δ)


+ [(1 + 2][k][) log (][k][/][δ][)] (27)

3T


We are now ready to state the main theorem.
**Theorem 1. If algorithm 1 is run on bounded rewards Lyt,it** (θ[t]) ∈ [0, 1] ∀t with step-size η =

log k/(4kC), mixing parameter γ = [1]/2 and the model satisfies Assumption 1, then after T
_iterations with probability at leastp_ 1 − _δ,_

_n_

1 4k log(2k/δ) 2 log(2k/δ)
max _Ly_ _θ[t][j]_ [
] + [(1 + 2][k][) log(2][k/δ][)] + + [2 log(2][k/δ][)]
_y∈[k]_ _n_ _j=1_ _≤_ [6]T[C] [+] p _√T_ 3T p _√n_ 3n

X 

b (28)

_iid_
_for an ensemble of size n where tj_ unif(T ) for j [n].
_∼_ _∈_

_iid_
_Proof. If we fix y and let tj_ unif(T ), then the following is a martingale difference sequence,
_∼_


_T_

_Aj =_ _Ly_ _θ[t][j]_ [
] _Ly_ _θ[t][
]_ _,_ (29)
_−_ _T[1]_

_t=1_

 X 

for which it is easy to see that _Aj_ 2[b] and A[2]j b
us apply Lemma 3 with high probability | _| ≤_ 1 − _[δ]/2k[≤]. Combining this with the bound of Lemma 4 with[1][ given boundedness of the loss. This readily let]_
probability 1 − _[δ]/2k by using a union bound completes the proof._ □

B CVAR


Conditional value at risk (CVaR) is the expected loss conditioned on being larger than the (1 − _α)-_
quantile. This has a distributional robust interpretation which for a discrete distribution can be
written as,

_m_

1

CVaRα (θ, P0) := sup _piℓ_ (θ, xi) s.t. _p_ _._ (30)
_p∈∆m_ ( _i=1_ _∥_ _∥∞_ _≤_ _αm_ )

X

The optimal p of the above problem places uniform mass on the tail. Practically we can compute
this best response by sorting the losses {ℓ(θ, xi)}i in descending order and assigning _αm1_ [mass per]

index until saturation.

**Primal CVaR** When m is large a stochastic variant is necessary. To obtain a stochastic subgradient
for the model parameter, the naive approach is to compute a stochastic best response over a minibatch. 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 et al., 2000),


(31)


CVaRα (θ, P0) = inf
_λ∈R_


_λ +_


(ℓ (θ, xi) _λ)+_
_−_
_i=1_

X


_αm_


In practice, one approach is to 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
a mini-batch (see e.g. (Xu et al., 2020, Appendix I.1)).


-----

In comparison CFOL acts directly on the probability distribution similarly to primal CVaR. However, instead of finding a best response on a uniformly sampled mini-batch it updates the weights
iteratively and samples accordingly (see algorithm 1). Despite this difference, it is interesting that
a direct connection can be established between the uncertainty sets of the methods. The following
section is dedicated to this.

To be pedantic it is worth pointing out a minor discrepancy when applying CVaR in the context
of deep learning. Common architectures such as ResNets incorporates batch normalization which
updates the running mean and variance on the forward pass. The implication is that the entire minibatch is 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.1 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 p be a uniform mixing p = γ** _m[1]_ [+ (1][ −] _[γ][)][q][ with an arbitrary distribution][ q][ ∈]_ [∆][m]

_and ϵ ∈_ [0, 1] such that the distribution has a lower bound on each element pi ≥ _γ_ _m[1]_ _[. Then an]_

_upper bound is implicitly implied on each element, ∥p∥∞_ := maxi=[m] pi ≤ 1 − [(][m][−]m[1)][γ] _._

_Proof. Consider pi for any i. At least (m −_ 1) _m[γ]_ [of the mass must be on other components so]

_pi_ 1 _m_ . The result follows. □
_≤_ _−_ [(][m][−][1)][γ]

**Corollary 1. Consider the uncertainty set of Exp3,**

(P0) = _p_ ∆m _pi_ _γ_ [1] _._ (32)
_U_ [Exp3] _∈_ _|_ _≥_ _m_
 _[∀][i]_

_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,_


_U_ [CVaR] (P0) = _p ∈_ ∆m | ∥p∥∞ _≤_



(33)

(34)


_αm_


_with α =_


1

(1 _γ)m+γ_ _[. This leaves us with the following primal formulation,]_
_−_

_m_

1

CVaRα (θ, P0) := sup _piℓ_ (θ, xi) s.t. _p_
_p∈∆m_ ( _i=1_ _∥_ _∥∞_ _≤_ _αm_

X


_Proof. From Lemma 5 and since CVaR requires_ _p_
_∥_ _∥∞_ _≤_

_p_ 1
_∥_ _∥∞_ _≤_ _−_ [(][m][ −]m[1)][γ]

By simple algebra we have,


1

_αm_ [we have,]


1

(35)
_αm_


=:


1

(36)
(1 _γ)m + γ [,]_
_−_


_α =_


which completes the proof.


So if the starting point of the uncertainty set is the simplex and the uniform mixing in Exp3 is
therefore only for tractability reasons, then we might as well minimize the CVaR objective instead.
This could even potentially lead to a more robust solution as the uncertainty set is larger (since the
upper bound in U [CVaR] does not imply the lower bound in U [Exp3]).

There are two things to keep in mind though. First, α should not be too small since the optimization
problem gets harder. It is informative to consider the case where γ = 1/2 such that α = _m2+1_ [.]

From this it becomes clear that the recasting as CVaR only works for small m. Secondly, despite
the uncertainty sets being related, the training dynamics, and thus the obtained solution, can be
drastically different, as we also observe experimentally in Section 5. For instance CVaR is known


-----

Table 4: Summary of methods where N is the number of samples and k 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)**

(P0) = _p_ ∆m _pi_ _ε_ _m[1]_ FOL (Shalev-Shwartz & Wexler, 2016) CFOL (ours)
_UU_ [Exp3][CVaR] (P0) = _p ∈ ∈_ ∆m | | ∥p ≥∥∞ _≤_ _[∀]αm[i]1_ 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.


EXPERIMENTS

(a) _δ_ = 1/255
_∥_ _∥∞_


(b) _δ_ = 2/255
_∥_ _∥∞_


1.0


1.0

|.0 .8 .6 .4 .2|Col2|Col3|
|---|---|---|


0.8

0.6

0.4

0.2

0.0


0.0


Figure 4: Robust test accuracy under different norm-ball sizes after clean training on CIFAR10. The
non-uniform distribution over class accuracies, even after clean training, indicates that the inferior
performance on some classes is not a consequence of adversarial training. Rather, the inhomogeneity
after perturbation seems to 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 on the test set. Notice that we 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 on the worst class while maintaining the average
robust accuracy. However, TE leads to a drop in terms of the clean accuracy.

**ERM-AT** **ERM-AT (TE)**


Average **0.82** 0.74
accclean Worst class **0.54** 0.51

Average 0.47 **0.47**
accrob Worst class 0.14 **0.23**


-----

Clean training


Adversarial training


1.0

0.8

0.6

0.4

0.2


1.0

0.8

0.6

0.4

0.2


0.0
Classes


0.0
Classes


Clean training


Adversarial training


1.0


1.0


0.8

0.6

0.4

0.2

0.0


0.8

0.6

0.4

0.2

0.0


Figure 5: Clean training and adversarial training on CIFAR100 (top) and STL10 (bottom) using
ERM-AT with PGD-7 attacks at train time and PGD-20 attacks at test time for the robust test accuracy. The CIFAR100 classes are sorted for convenience. Notice that CIFAR100 has a class with
zero robust accuracy with adversarial training.


ERM-AT


CFOL-AT


0.7

0.6

0.5

0.4

0.3

0.2

0.1

0.0
Classes


0.7

0.6

0.5

0.4

0.3

0.2

0.1

0.0
Classes


ERM-AT


CFOL-AT




0.6

0.4

0.2

0.0


0.6

0.4

0.2

0.0


Figure 6: Robust class accuracy for CIFAR100 and STL10 respectively. Vertical black error bars indicate 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.


-----

Table 7: 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 be modified
further.

**ERM-AT** **CFOL-AT** **FOL-AT**


Average 0.70 ± 0.05 0.73 ± 0.01 **0.75 ± 0.01**
accclean 20% tail 0.53 ± 0.04 **0.64 ± 0.04** 0.59 ± 0.02
Worst class 0.52 ± 0.03 **0.62 ± 0.03** 0.57 ± 0.01

Average 0.44 ± 0.04 0.46 ± 0.01 **0.48 ± 0.01**
accrob 20% tail 0.25 ± 0.01 **0.33 ± 0.03** 0.29 ± 0.02
Worst class 0.24 ± 0.01 **0.31 ± 0.02** 0.27 ± 0.02

Average **0.55 ± 0.01** 0.51 ± 0.04 0.55 ± 0.01
accclean 20% tail 0.33 ± 0.04 **0.34 ± 0.06** 0.33 ± 0.04
Worst class 0.18 ± 0.02 **0.19 ± 0.04** 0.17 ± 0.03

Average **0.27 ± 0.00** 0.24 ± 0.02 0.26 ± 0.01
accrob 20% tail 0.07 ± 0.02 **0.09 ± 0.03** 0.07 ± 0.02
Worst class 0.01 ± 0.01 **0.02 ± 0.02** 0.01 ± 0.00

Average 0.50 ± 0.05 **0.54 ± 0.03** 0.54 ± 0.02
accclean 20% tail 0.28 ± 0.11 **0.42 ± 0.08** 0.35 ± 0.10
Worst class 0.23 ± 0.09 **0.38 ± 0.09** 0.29 ± 0.09

Average 0.31 ± 0.03 **0.33 ± 0.01** 0.33 ± 0.03
accrob 20% tail 0.10 ± 0.04 **0.20 ± 0.02** 0.14 ± 0.03
Worst class 0.08 ± 0.04 **0.17 ± 0.05** 0.11 ± 0.02


CIFAR10

CIFAR100

STL10


Table 8: Comparison between different sizes of ℓ -ball attacks on CIFAR10. The same constraint
_∞_
is 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**
accclean 20% tail 0.51 ± 0.03 **0.66 ± 0.01**
Worst class 0.47 ± 0.03 **0.63 ± 0.02**

Average **0.47 ± 0.03** 0.46 ± 0.00
accrob 20% tail 0.24 ± 0.02 **0.31 ± 0.02**
Worst class 0.20 ± 0.02 **0.30 ± 0.01**

Average 0.63 ± 0.01 **0.63 ± 0.01**
accclean 20% tail 0.31 ± 0.02 **0.53 ± 0.01**
Worst class 0.26 ± 0.02 **0.51 ± 0.01**

Average **0.38 ± 0.00** 0.35 ± 0.00
accrob 20% tail 0.12 ± 0.01 **0.23 ± 0.02**
Worst class 0.09 ± 0.01 **0.22 ± 0.02**


_δ_ 8/255
_∥_ _∥∞_ _≤_

_δ_ 12/255
_∥_ _∥∞_ _≤_


-----

Table 9: Model performance on CIFAR10 under AutoAttack (Croce & Hein, 2020). The models
still uses 7 steps of PGD at training time with a ℓ -constraint of [8]/255. Only at test time is the attack
_∞_
exchanged with AutoAttack under the same constraint. CFOL-AT is robust to 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**
accclean 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
accrob 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 1 samples from the adversarial distribution
_p. Alternatively one can sample data points uniformly and instead reweight the gradients for the_
model using p. In expectation, an update of these two schemes are equivalent. To see why,
observe that in CFOL the model has access to the gradient _θLy,i(θ). We can obtain an un-_
_∇_
biased estimator by instead reweighting a uniformly sampled class, i.e. Ey _p,i [_ _θLy,i(θ)] =_
_∼_ _∇_
Ey unif(k),i [kpy _θLy,i(θ)]. With classes sampled uniformly the unbiased estimator for the ad-_
_∼_ _∇_
versary becomes _Ly′ = 1{y′=y}Lyk ∀y[′]. 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 update rule and that the immediate equivalence we get is only in expectation. We test the

[e]
reweighted variant of CFOL-AT on CIFAR10 and observe similar results as for CFOL-AT.

accclean accrob
Average 20% tail Worst class Average 20% tail Worst class

CFOL-AT (reweighted) 0.75 0.64 0.64 0.45 0.31 0.31

C.1 HYPERPARAMETERS

In this section we 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 2 degrees random rotations. For temporal ensembling (TE) we use the parameters
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.

For CFOL-AT we used the adversarial step-size η = 5 · 10[−][6] across all datasets and the same
parameters as for ERM-AT described in Section 5. CFOL-AT seems to be reasonable robust to stepsize choice as seen in Table 11. Similarly for FOL-AT we use the same parameters as 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.

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 1 is not satisfied for any sequence.
Instead we rely on the sampling process to be only mildly adversarial initially as implicitly enforced
by the small adversarial step-size. It is an interesting future direction to incorporate this implicit
tempering directly into the mixing parameter γ instead.

For LCVaR-AT we first optimized over the size of the uncertainty set by adjusting the parameter α.
Despite getting reasonable performance for some run with α = 0.2 the method turned out to have
large variance. For this reason we explored reducing the model learning rate τ for which we found
that τ = 0.05 gave better performance while having much smaller variance. It is not surprising that


-----

the method requires smaller step-sizes given how CVaR methods assign higher weight to a fraction
of the batch at every iteration as explained in Appendix B. Maybe unnecessarily meticulous, we
also ensure that temporal ensembling indeed improves model performance for LCVaR-AT by also
running the method without the regularization. Our instantiation of LCVaR-AT used for comparison
thus uses α = 0.2 and τ = 0.05.

The hyperparameter exploration can be found in Table 11.

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 10[−][6] -  0.49 0.30 0.76 0.61

CFOL-AT _×_

Yes 0.1 5 × 10[−][6] -  0.47 0.30 0.76 0.65
Yes 0.1 5 × 10[−][5] -  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

LCVaR-AT

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 5 × 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 we provide additional details for the experimental setup specified in Section 5. 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 × 32 dimensional images and 100 classes.**
**STL10 5000 training examples of 96 × 96 dimensional images and 10 classes.**

As noted in Section 5 we use the average robust accuracy to early stop the model. In contrast with
common practice though, we use a validation set instead of the test set to avoid overfitting to the
test set. The class accuracies across the remaining two datasets, CIFAR100 and STL10, can be
found in Figure 6. We also include results when the model is early stopped based on the worst class
accuracy on the validation set in Table 7. The mean and standard deviation in all tables and figures
are computed over 5 runs. However, for CIFAR100 we conduct 6 experiments and pick the top 5 to
compute the statistics since all methods had one outlier with significantly worst performance.

A radius of [8]/255 is used for the ℓ -constraint attack unless otherwise noted. For training we use 7
_∞_
steps of PGD and a stepsize of8/255 [2]/255. At test time we use 20 steps of PGD with a stepsize of 2.5 ×

20 [. For][ 12][/][255][-bounded attacks we scale the training stepsize and test stepsize proportionally.]

C.3 TEMPORAL ENSEMBLING

Let fθ : R[d] _→_ R[k] be a model parameterized by θ that assigns a probability distribution over the k
classes for any x ∈ R[d]. Temporal ensembling (Laine & Aila, 2016; Dong et al., 2021) computes
a so called ensemble prediction for a given data example xi by maintaining an average over past
be the training objective. A regularizing term is added to the training objective that encouragespredictions, vi ← _τ · vi + (1 −_ _τ_ ) · fθ (xi), where τ is the momentum term. Let ℓ (fθ (x + δ), y)
predictions to stay close to vi,


_ℓ_ (fθ (xi + δ), yi) + ω(t) _fθ (xi + δ)_ _vi_ 2 _,_ (37)
_· ∥_ _−_ _∥[2]_
o


min


max
_i=1_ _δ∈S_

X


-----

where ω(t) is the balancing weight parameter. Usually ω(t) interpolates from 0 to some constant ω
epoch
along a Gaussian rampup curve. That is, ω(t) = ω · exp _−5(1 −_ _t)[2][
]_ where t = min{ max epoch _[,][ 1][}][.]_


C.4 IMPLEMENTATION

We provide pytorch pseudo code for how CFOL can be integrated into existing training setups in
Listing 1. FOL is similar in structure, but additionally requires associating a 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 λ, since this was observed to be both faster and more stable in their work.

**from torch.utils.data import DataLoader**

sampler = ClassSampler(dataset, gamma=0.5)
dataloader = DataLoader(dataset, ..., sampler=sampler)

...

_# Training loop:_
**for img,y in iter(dataloader):**

_# attack img_
_# compute gradients and update model_
_# compute logits_

adv_loss = logits.argmax(dim=-1) != y
sampler.batch_update(y, eta * adv_loss)

Listing 1: Pseudo code for CFOL.


-----