Year: 2021

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.

heading: 1 INTRODUCTION
text: 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.
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.

heading: 1.1 RELATED WORK
text: 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 U(P0) and seeks to minimize the worst case 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.

heading: 2 PROBLEM FORMULATION AND PRELIMINARIES
text: Notation The underlying data distribution is denoted by D with examples x ∈ Rd and classes y ∈ [k]. A given iteration is characterized by t ∈ [T ], while pyt indicates the yth index of the tth 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)∼D[`(θ, x, y)] over our model parameters θ ∈ Rp, where ` is some loss function of θ and example x ∈ Rd 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 δ∈S `(θ, x+ δ, y) ] , (1)
where each x is now perturbed by adversarial noise δ ∈ S ⊆ Rd. 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:
min θ max y∈[k]
{ Ly(θ) := Ex∼pD(·|y) [ max δ∈S `(θ, x+ δ, y) ]} . (2)
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.

heading: 3 METHOD
text: 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 = ∑k y=1 |Ny|. Then, we are interested in minimizing the maximum empirical class-conditioned risk,
max y∈[k]
L̂y(θ) := 1 |Ny| ∑ i∈Ny max δ∈S `(θ, xi + δ, y). (3)
We relax this discrete problem to a continuous problem over the simplex ∆k,
max y∈[k] L̂y(θ) ≤ max p∈∆k k∑ y=1 pyL̂y(θ). (4)
Note that equality is attained when p is a dirac on the argmax over classes.
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):
wty = w t−1 y − ηL̂y(θt), pty = exp ( wty ) / k∑ y=1 exp ( wty ) . (Hedge)
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) 6= 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 L̂y(θ) 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 of Auer et al. (2002), we instead construct an unbiased estimator of the k dimensional loss vector L̂(θt) := (L̂1(θt), ..., L̂k(θt))> based on a sampled class yt from some distribution yt ∼ pt. This stochastic formulation further lets us estimate the class conditioned risk L̂yt(θ t) with an unbiased sample i ∼ unif(|Nyt |). This leaves us with the following estimator,
L̃ty =
{ Ly,i(θ t)/pty y = y t
0 otherwise (5)
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 w0 = 0 such that q0 and p0 are uniform. foreach t in 0..T do
yt ∼ pt ; // sample class it ∼ unif(|Nyt |) ; // sample uniformly from class θt+1 = ModelUpdate(θt, Lyt,it(θ
t)) ; // update model parameters L̃ty = 1{y=yt}Ly,it(θ
t)/pty ∀y ; // construct estimator wt+1y = w t y − ηL̃ty ∀y ; // update the adv. class distribution
qt+1y = exp ( wt+1y ) / ∑k y=1 exp ( wt+1y ) ∀y; pt+1y = γ 1 k + (1− γ)q t+1 y ∀y;
end foreach
where Ly,i (θ) := maxδ∈S ` (θ, xi + δ, y). It is easy to verify that this estimator is unbiased,
Ey∼p [ L̃ty ] = ( 1− pty ) · 0 + pty · L̂y(θ t)
pty = L̂y(θ
t). (6)
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 pt.
We could pick pt to be the learned adversarial distribution, but it is well known that this can lead to unbounded regret if some pty is small (see Appendix A for definition of regret). Auer et al. (2002) resolves this problem with Exp3, which instead learns a distribution qt, then mixes it with a uniform distribution, to eventually sample from pty = γ 1 k + (1 − γ)q t y 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 qt+1 with (Hedge) using the estimator L̃t with sample drawn from pt and subsequently plays pt+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 pt in Figure 2.
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

heading: 3.1 CONVERGENCE RATE
text: 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. For any sequence of classes (y1, ..., yT ) ∈ [k]T and class conditioned sample indices (i1, ..., iT ) with it ∈ Nyt the model enjoys the following bound for some C ′ < ∞ and C = max{k log k,C ′},
T∑ t=1 Lyt,it(θ t) ≤ C. (7)
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 least 1− δ,
max y∈[k]
1
n n∑ j=1 L̂y ( θtj ) ≤ 6C T + √ 4k log(2k/δ)√ T + (1 + 2k) log(2k/δ) 3T + √ 2 log(2k/δ)√ n + 2 log(2k/δ) 3n ,
(8) for an ensemble of size n where tj iid∼ 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 Õ(C + k) where usually k C. 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 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 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.

heading: 4 EXPERIMENTAL SETUP: OVERCOMING ROBUST OVERFITTING
text: 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.
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).

heading: 5 EXPERIMENTS
text: 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 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 minimization (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.

heading: 6 CONCLUSION
text: 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.

heading: A CONVERGENCE ANALYSIS

heading: A.1 PRELIMINARY AND NOTATION
text: Consider the abstract online learning problem where for every t ∈ [T ] the player chooses an action xt and subsequently the environment reveals the loss function l(·, yt). As traditional in the online learning literature we will measure performance in terms of regret, which compares our sequence of choices {xt}Tt=1 with a fixed strategy in hindsight u,
RT (u) = T∑ t=1 l(xt, yt)−min x T∑ t=1 l(u, yt). (9)
If we, instead of minimizing over losses l, maximize over rewards r we define regret as,
RT (u) = max x T∑ t=1 r(u, yt)− T∑ t=1 r(xt, yt). (10)
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
pty The y th index of the tth iterate
1{boolean} The indicator function
unif(n) Discrete uniform distribution over n elements
Ny Set of data point indices for class y ∈ [k] N = ∑k y=1 |Ny| The size of the data set
Ly,i (θ) := maxδ∈S ` (θ, xi + δ, y) Loss on a particular example
L̂y(θ) := 1 |Ny| ∑ i∈Ny Ly,i (θ) The empirical class-conditioned risk L̂ (θ) := (L̂1 (θ) , . . . , L̂k (θ)) > The vector of all empirical class-conditioned risks
Lty := Ly,i (θ t) Class-conditioned estimator at iteration t with i ∼ unif(|Ny|)

heading: A.2 CONVERGENCE RESULTS
text: We restate Algorithm 1 while leaving out the details of the classifier for convenience. Initialize w0 such that q0 and p0 are uniform. Then Exp3 proceeds for every t ∈ [T ] as follows:
1. Draw class yt ∼ pt
2. Observe a scalar reward Ltyt
3. Construct estimator L̃ty = L t yt1{y=yt}/p t y ∀y
4. Update distribution wt+1 = wt − ηL̃t qt+1y = exp ( wt+1y ) / ∑k y=1 exp ( wt+1y ) ∀y
pt+1y = γ 1 k + (1− γ)q t+1 y ∀y
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 − γ)qy it can easily be verified that,
1 py ≤ k γ and qy py ≤ 1 1− γ for all y. (11)
Lemma 1. If Exp3 is run on bounded rewards Ltyt ∈ [0, 1] ∀t with η ≤ γ/k then
RadvT (u) = T∑ t=1 〈u, L̃t〉 − T∑ t=1 〈qt, L̃t〉 ≤ log k η + ηk (1− γ)γ T∑ t=1 Lty (12)
Proof. We can write the estimator vector as L̃t = Lt yt
pt yt eyt where eyt is a canonical basis vector.
By assumption we have Ltyt ∈ [0, 1]. Combining this with the bound on 1/py in Equation 11 we have L̃ty ≤ k/γ for all y. This lets us invoke (Shalev-Shwartz et al., 2011, Thm 2.22) as long as the step-size η is small enough. Specifically, we have that if η ≤ 1/L̃ty ≤ γ/k
T∑ t=1 〈u, L̃t〉 − T∑ t=1 〈qt, L̃t〉 ≤ log k η + η T∑ t=1 k∑ y=1 qty(L̃ t y) 2. (13)
By expanding L̃ty and applying the inequalities from Equation 11 we can get rid of the dependency on q and p,
log k
η + η T∑ t=1 k∑ y=1 qty(L̃ t y) 2 ≤ log k η + η T∑ t=1 qtyt (ptyt) 2 (Ltyt) 2
≤ log k η + η T∑ t=1
k
(1− γ)γ (Ltyt) 2
≤ log k η + ηk (1− γ)γ T∑ t=1 Ltyt ,
(14)
where the last line uses the boundedness assumption Lty ∈ [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. For any sequence of classes (y1, ..., yT ) ∈ [k]T and class conditioned sample indices (i1, ..., iT ) with it ∈ Nyt the model enjoys the following bound for some C ′ < ∞ and C = max{k log k,C ′},
T∑ t=1 Lyt,it(θ t) ≤ C. (15)
Recall that we need to bound Lty := Ly,it(θ t), where y are picked adversarially and it 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∑ t=1 〈u, L̃t〉 ≤ 6C. (16)
Proof. By expanding and rearranging Lemma 1,
T∑ t=1 〈u, L̃t〉 ≤ log k η +
( ηk
(1− γ)γ + qtyt
ptyt ) T∑ t=1 Lty, (17)
as long as η ≤ γ/k. Then by using our favorite inequality in Equation 11 and under Assumption 1,
log k
η +
( ηk
(1− γ)γ + qtyt
ptyt ) T∑ t=1 Lty ≤ log k η + ( ηk (1− γ)γ + 1 1− γ ) C, (18)
To maximize (1− γ)γ) we now pick γ = 1/2 so that,
log k
η +
( ηk
(1− γ)γ +
1
1− γ
) C ≤ log k
η + (4ηk + 2)C. (19)
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,
log k
η + (4ηk + 2)C ≤ 2
√ 4kC log k + 2C. (20)
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)
This still only gives us a bound on a stochastic object. We will now relate it to the empirical class conditional risk L̂y(θ) 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 L̂y(θ). Following Shalev-Shwartz & Wexler (2016) we adopt their use of a Bernstein’s type inequality. Lemma 3 (e.g. Audibert et al. (2010, Thm. 1.2)). Let A1, ..., AT be a martingale difference sequence with respect to a Markovian sequence B1, ..., BT and assume |At| ≤ V and E [ A2t | B1, . . . , Bt ] ≤ s. Then for any δ ∈ (0, 1),
P
( 1
T T∑ t=1 At ≤ √ 2s log (1/δ)√ T + V log (1/δ) 3T ) ≥ 1− δ. (22)
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] we obtain have the following bound with probability at least 1− δ/k,
1
T T∑ t=1 L̂y ( θt ) ≤ 6C T + √ 4k log (k/δ)√ T + (1 + 2k) log (k/δ) 3T . (23)
Proof. Pick any y ∈ [k] and let u = ey in 〈u, L̃t〉. By construction the following defines a martingale difference sequence,
At = L̂y(θ t)− 〈ey, L̃t〉 = L̂y(θt)− 〈ey,
1
ptyt Lyt,it(θ
t)eyt〉. (24)
In particular note that it is uniformly sampled. To apply the Bernstein’s type inequality we just need to bound |At| and E [ A2t | qt, θt ] . For |At| we can crudely bound it as,
|At| ≤ |L̂y(θt)|+ |〈ey, 1
ptyt Lyt,it(θ
t)eyt〉| ≤ 1 + k
γ . (25)
To bound the variance observe that we have the following:
E [ 〈ey, L̃t〉 2 | qt, θt ] ≤ k∑ y′=1 pty′ (pty′) 2 E [ Ly′,i(θ t)2 | θt ] (ey)y′ (with i ∼ unif(|Ny′ |) ∀y′)
= 1 pty E [ Ly,i ( θt )2 | θt]
≤ 1 pty ≤ k γ . (by Equation 11)
It follows that E [ A2t | qt, θt ] ≤ k/γ
Invoking Lemma 3 we get the following bound with probability at least 1− δ/k,
1
T T∑ t=1 L̂y ( θt ) ≤ 1 T T∑ t=1 〈ey, L̃t〉+
√ 2 kγ log (
k/δ) √ T + (1 + kγ ) log ( k/δ) 3T (26)
By bounding the first term on the right hand side with Lemma 2 and taking γ = 1/2 we obtain,
1
T T∑ t=1 L̂y ( θt ) ≤ 6C T + √ 4k log (k/δ)√ T + (1 + 2k) log (k/δ) 3T (27)
This completes the proof.
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 least 1− δ,
max y∈[k]
1
n n∑ j=1 L̂y ( θtj ) ≤ 6C T + √ 4k log(2k/δ)√ T + (1 + 2k) log(2k/δ) 3T + √ 2 log(2k/δ)√ n + 2 log(2k/δ) 3n ,
(28) for an ensemble of size n where tj iid∼ unif(T ) for j ∈ [n].
Proof. If we fix y and let tj iid∼ unif(T ) , then the following is a martingale difference sequence,
Aj = L̂y ( θtj ) − 1 T T∑ t=1 L̂y ( θt ) , (29)
for which it is easy to see that |Aj | ≤ 2 and A2j ≤ 1 given boundedness of the loss. This readily let us apply Lemma 3 with high probability 1− δ/2k. Combining this with the bound of Lemma 4 with probability 1− δ/2k by using a union bound completes the proof.

heading: B CVAR
text: 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,
CVaRα (θ, P0) := sup p∈∆m { m∑ i=1 pi` (θ, xi) s.t. ‖p‖∞ ≤ 1 αm } . (30)
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 1αm mass per index until saturation.
Primal CVaR Whenm 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),
CVaRα (θ, P0) = inf λ∈R
{ λ+ 1
αm m∑ i=1 (` (θ, xi)− λ)+
} . (31)
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.

heading: B.1 RELATIONSHIP WITH CVAR
text: 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 = γ 1m + (1 − γ)q with an arbitrary distribution q ∈ ∆m and ∈ [0, 1] such that the distribution has a lower bound on each element pi ≥ γ 1m . Then an upper bound is implicitly implied on each element, ‖p‖∞ := maxi=[m] pi ≤ 1− (m−1)γm .
Proof. Consider pi for any i. At least (m − 1) γm of the mass must be on other components so pi ≤ 1− (m−1)γm . The result follows.
Corollary 1. Consider the uncertainty set of Exp3, UExp3 (P0) = { p ∈ ∆m | pi ≥ γ 1 m ∀i } . (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,
UCVaR (P0) = { p ∈ ∆m | ‖p‖∞ ≤ 1
αm
} (33)
with α = 1(1−γ)m+γ . This leaves us with the following primal formulation,
CVaRα (θ, P0) := sup p∈∆m { m∑ i=1 pi` (θ, xi) s.t. ‖p‖∞ ≤ 1 αm } . (34)
Proof. From Lemma 5 and since CVaR requires ‖p‖∞ ≤ 1αm we have,
‖p‖∞ ≤ 1− (m− 1)γ
m =:
1
αm (35)
By simple algebra we have,
α = 1
(1− γ)m+ γ , (36)
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 UCVaR does not imply the lower bound in UExp3). 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 α = 2m+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
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.

heading: C EXPERIMENTS
text: (a) ‖δ‖∞ = 1/255
(b) ‖δ‖∞ = 2/255

heading: C.1 HYPERPARAMETERS
text: 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.

heading: C.2 EXPERIMENTAL SETUP
text: 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 of 2/255. At test time we use 20 steps of PGD with a stepsize of 2.5 × 8/255
20 . For 12/255-bounded attacks we scale the training stepsize and test stepsize proportionally.

heading: C.3 TEMPORAL ENSEMBLING
text: Let fθ : Rd → Rk be a model parameterized by θ that assigns a probability distribution over the k classes for any x ∈ Rd. 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 predictions, vi ← τ · vi + (1 − τ) · fθ (xi), where τ is the momentum term. Let ` (fθ (x+ δ) , y) be the training objective. A regularizing term is added to the training objective that encourages predictions to stay close to vi,
min θ n∑ i=1 max δ∈S { ` (fθ (xi + δ) , yi) + ω(t) · ‖fθ (xi + δ)− vi‖22 } , (37)
where ω(t) is the balancing weight parameter. Usually ω(t) interpolates from 0 to some constant ω along a Gaussian rampup curve. That is, ω(t) = ω ·exp ( −5(1− t)2 ) where t = min{ epochmax 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.

Review summaries:
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. That is, instead of a min-max problem, there is another maximization component over the classes.  This is motivated by an example that shows a larger variance in losses between classes than in the standard setting.  The authors suggest a method from online learning - exponential weight in the bandit setting (that is - Exp3). 

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. 

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.

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)).   Motivated 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). The 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.  The authors show empirically that CFOL consistently improves the worst class accuracy on CIFAR-10, CIFAR-100, and STL10. Moreover, the authors provide high probability convergence guarantees for the worst class accuracy.