| # 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. | |
| ----- | |