Robust Training through Adversarially Selected Data Subsets
Authors: Hitvarth Diwanji
Divyanshu Shende
Rishi Agarwal
Swaprava Nath
Abir De
Venue: Submitted to ICLR 2023 (2023)
Keywords: Subset selection
Robust learning

Abstract: Robustness to adversarial perturbations often comes at the cost of a drop in accuracy on unperturbed or clean instances. Most existing defense mechanisms attempt to defend the learner from attack on all possible instances, which often degrades the accuracy on clean instances significantly. However, in practice, an attacker might only select a small subset of instances to attack, $e.g.$, in facial recognition systems an adversary might aim to target specific faces. Moreover, the subset selection strategy of the attacker is seldom known to the defense mechanism a priori, making it challenging to attune the mechanism beforehand. This motivates designing defense mechanisms which can (i) defend against attacks on subsets instead of all instances to prevent degradation of clean accuracy and, (ii) ensure good overall performance for attacks on any selected subset. In this work, we take a step towards solving this problem. We cast the training problem as a min-max game involving worst-case subset selection along with optimization of model parameters, rendering the problem NP-hard. To tackle this, we first show that, for a given learner's model, the objective can be expressed as a difference between a $\gamma$-weakly submodular and a modular function. We use this property to propose ROGET, an iterative algorithm, which admits approximation guarantees for a class of loss functions. Our experiments show that ROGET obtains better overall accuracy compared to several state-of-the-art defense methods for different adversarial subset selection techniques.

Under review as a conference paper at ICLR 2023
ROBUST TRAINING THROUGH ADVERSARIALLY SELECTED DATA SUBSETS
Anonymous authors Paper under double-blind review
ABSTRACT
Robustness to adversarial perturbations often comes at the cost of a drop in accuracy unperturbed or clean instances. Most existing defense mechanisms attempt defend the learner from attack on all possible instances, which often degrades the accuracy clean instances significantly. However, in practice, an attacker might only select a small subset of instances to attack, e.g., in facial recognition systems adversary might aim target specific faces. Moreover, the subset selection strategy of the attacker is seldom known to the defense mechanism priori, making it challenging to attune the mechanism beforehand. This motivates designing defense mechanisms which can (i) defend against attacks on subsets instead of all instances to prevent degradation of clean accuracy and, (ii) ensure good overall performance for attacks on any selected subset. In this work, we take a step towards solving this problem. We cast the training problem as a min-max game involving worst-case subset selection along with optimization of model parameters, rendering the problem NP-hard. To tackle this, we first show that, for a given learner's model, the objective can be expressed and a modular function. We use this property to propose ROGET, an iterative algorithm, which admits approximation guarantees for class of loss functions. Our experiments show that ROGET obtains better overall accuracy compared to several state-of-the-ard defense methods for different adversarial subset selection techniques.
difference between 7-weakly submodular
INTRODUCTION
Recent years have witnessed a dramatic improvement in the predictive power of the machine learning models across several applications such as computer vision, natural language processing, speech processing, etc. This has led to their widespread usage in several safety critical systems like au- tonomous car driving (Janai et al. 2020 Alvarez et al., 20100] Sallab al. (017). face recognition (Hu)
et al. 2015 Seannelmacher-SShieemmaa et al. 2016: Wang & Deng 2021). ). voice recognition (Myers]
2000 Yuan et al.] 2018), etc., which in turn requires the underlying models to be security complaint.
However, most existing machine learning models suffer from significant vulnerability in the face of
adversarial attacks (Szegedy et al., 2014; Carlini & Wagner 2017: Goodifllw et al. [2015] Baluja
& Fischer 2018, Xiao et al., 2018 Kurakin et al.) 2017] Xie & Yuille [ Kannan al. [0188]
Croce & Hein 2020 Yuan et al. 2019 Tramer et al. 2018), where instances are contaminated with
small and often indiscernible perturbations delude the model at the test time. This may result in
catastrophic consequences when the underlying ML model is deployed in practice.
Driven by this motivation, flurry of recent works (Madry et al. 2017 Zhang et al. 2019b 2021b Athalye et al. 20188 Andriushchenko & Flammarion 20200 Shatahi et al.) (019)] Rice et al. 2020)
have focused on designing adversarial training methods, whose goal is to maintain the accuracy of ML models in presence of adversarial attacks. In principle, they are closely connected to robust machine learning methods that seek to minimize the worst-case performance the MI. models with adversarial perturbations. In general, these approaches assume equal likelihood of adversarial attack across each instance. However, in several applications, an adversary might selectively wish to attack specific subset of instances, which may be unknown to the learner. For example, adversary can only be interested in perturbing images of specific persons to evade facial recognition systems (Xiao) eet al. 2021 Vakhshiteh al. [021 Zhang et al.) 2021b Sarkar et al. [021] /enkaaesh et al. 2021); in traffic signs classification, the adversary may like to perturb only the stop signs, which can have more adverse impact during deployment. Therefore, the existing adversarial training methods can be

---

Under review as a conference paper at ICLR 2023
overly pessimistic in terms of their predictive power, since they consider adversarial perturbation for each instance. We discuss the related works in more detail in Appendix B
1.1 OUR CONTRIBUTIONS
Responding to the above limitations, we propose novel robust learning framework, which is able to defend adversarial attacks targeted at any chosen subset of examples. Specifically, we make the following contributions.
Learning in presence of perturbation on adversarially selected subset. We consider an attack model, where the adversary selectively perturbs a subset of instances, rather than drawing them uniformly at random. However, the exact choice of the subset or its property remains unknown the learner during training and validation. Consequently, a learner cannot adapt to such specific attack well in advance through training or cross-validation. To defend these attacks, we introduce a novel adversarial training method, where the learner aims at minimizing the worst-case loss across all the data subsets. Our defense strategy is agnostic to any specific selectivity of the attacked subset. Its key goal is to maintain high accuracy during attacks on any selected subset, rather than providing optimal accuracy for any specific subset.
To this end, posit our adversarial training task an instance of min-max optimization problem, where the inner optimization problem seeks the data subset that maximizes the training loss and, the outer optimization problem then minimizes this loss with respect to the model parameters. While training the model, the outer problem also penalizes the loss on the unperturbed instances. This allows us optimize for the overall accuracy across both perturbed and unperturbed instances.
Theoretical characterization of our defense objective. Existing adversarial training meth- ods (Madry et al. [017 Zhang et al., [0199 Robey et al.) (02II) involve only continuous optimization variables- the model parameters and the amount of perturbation. In contrast, the inner maximization problem our proposal searches over the worst-case data subset. This translates our optimization task into parameter estimation problem in conjunction with a subset selection problem, which renders it Na-hard. We provide useful characterization of the underlying training objective that would help us design approximation algorithm to solve the problem. Given fixed ML model, we show that the training objective can be expressed as the difference between a monotone 7 --weakly submodular function and modular function (Theorem 2). This allows to leverage distorted greedy algorithm (Harshaw et al. 2019) to optimize the underlying objective.
Approximation algorithms. We provide ROGET (RObust aGainst adversarial subsETs), family of algorithms to solve our optimization problem, by building upon the proposal of (Adibi et al. 2021). that admits approximation guarantees. In each iteration, ROGET first applies gradient descent (GD)
or stochastic gradient descent step to update the estimate of the model parameters and then applies distorted greedy algorithm to update the estimate of attacked subset of instances. We show that ROGET admits approximation guarantees for convex and non-convex training objective (Thoerem [ where in the latter case we require that the objective satisfies (Theorem 4 Our analysis can be applied in any min-max optimization setup where the inner optimization problem seeks to maximize the difference between a monotone 7 -weakly submodular and modular function and therefore, is of independent interest.
(PL) condition
Finally, we provide comprehensive experimental evaluation of ROGET, by comparing them against seven tate-off-the-art defense methods. Here, in addition to hyperparameter set by the baselines in their papers, we also use new hyperparameter selection method, which is more suited in our setup. Unlike our proposal, the baselines are not trained to optimize for the worst case accuracy. To reduce this gap between the baselines and our method, we tune the hyperparameters of the baselines, which would maximize the minimum accuracy across large number of subsets chosen for attack. We observe that, ROGET is able to outperform the state-of-the-re defense methods in terms of the overall accuracy across different hyperparameter selection and different subset selection strategies.
PROBLEM FORMULATION
Instances, learner's model and the loss function. We consider classification setup where z e X' = Rd are the features, y E y are the discrete labels. We denote [ y:) to be the training instances where D denotes the training dataset. We use ho H to indicate the learner's model,
2

---

Under review as a conference paper at ICLR 2023
where H. is the hypothesis class and 0 E θ is the parameter vector of the model. We use the cross entropy loss ((he(z)) (2)).) y) in the paper.
Adversarial perturbation selected subset. We assume that the adversary's ' goal is to selectively attack specific subset of instances Slatent instead of every possible instances in the data or drawing instances uniformly at random. The adversary then uses adversarial perturbation method to generate ","" using I; for all for i E şlatent such that at? is close to 2;, but the model misclassifies 2, Now. it is important to note that neither the strategy behind selecting Slatent nor the adversarial perturbation method is known to the learner. Hence, during training, we use as X' X as the learner's belief about the adversarial network or the perturbation method with parameter vector Φ + similar (Baluja & Fischer 2018: Xiao al. 2018 Mopuri et al., 2018), where + is domain of Φb Many popular attacks like FGSM (Goodfellow et al., [2015), PGD (Madry et al.) (201)) are un-parameterized and they induce perturbation of one point independently of others. Still, we assume a parameterized adversary model (Baluja & Fischer 2018 Xiao et al. 2018 Mopuri et al. 2018)) to make the formulation more generalized as one can always overparameterize such a model to induce enough capacity and mimic pointwise attacks.
Proposed adversarial training problem. Let us assume, for instance, that the subset selection strategy of the adversary is revealed to the learner. Following this strategy, the learner can easily compute the underlying subset 5 C D to mimic the adversary and minimize the sum of the loss on the perturbed instances E S and the unperturbed instances E D'.S However, in practice, the learner may not have any knowledge about the underlying subset selection strategy. In such a case, the goal of a defense algorithm should be to ensure high overall accuracy in the face of attacks all possible subsets. To this end, we design an adversarial training framework, which attempts to minimize the worst case loss across all subsets, described below.
Given a set of training instances {(x,, y:) he we defend the attacks on selected subset of instances by training& new model ho which minimizes the highest possible loss the perturbed instances ag (z:; with i E S across subsets C D of size at most i, while ensuring that the new predictions he (2t))) and the labels y/j remain close the unperturbed instances j & S. Given the the learner's belief about the adversarial network ag, we define the learner's s loss function as follows:
S (1a))= = DD|
((ho(ap(zi)) u:) + Σ p((ho(zz))
(1)
IES
JEDYS
The parameter is a regularization parameter which gives additional flexibility to control the trade-off between accuracy on clean examples and perturbed examples. Then, we formulate our adversarial training problem as the following bi-level discrete-continunn optimization task.
minimize maximize S:|8|ıb
F(he, S| (pp((.s)))
AE6
where, o' (0, = argmax Σ
[(((ho(asxx)) (CCCo/(()c))))))CC(((((())))))))
The optimization problem is min-max game where the inner optimization problem aims find the subset S of size which provides the highest loss and the outer minimization problem aims to find the model he that minimizes this loss.
The optimization problem 3 is the learner's belief about the adversary's 's strategy. It need not be true in practice. In Section we perform experiments when the true adversary's 's models differ from as during test. Eq. (3) provides the learner's s estimate about the parameters of the adversarial network.
Here, (Tas( (z,), 2x.) cost of perturbing I; to (2;)) often measured using different notions of distances, e.g., normed differences or their squares, etc. In such case, this optimization problem (3) can also be seen as the dual of the constrained optimization problem (Madry et al., [017]] Robey 34) such that C(as(x)), 2;)) S. {(4) where is
ct al. 2021) given by maxę Eies dependent on μ..
Note that, the adversary can select the subset S in both deterministic or probabilistic manner. For example, it can attack images of specific persons in facial recognition systems, perturb the instances with stop-signs in traffic signs classification system, etc. On the other hand, it can select instances with probability proportional to the uncertainty of a classifier. Similar to the optimization problems (2) (3). one derive continuous min-max optimization problem when S is drawn from a probability
3

---

Under review as a conference paper at ICLR 2023
distribution. We show the connection between this continuous optimization problem and our discrete continuous optimization problem in Appendix C
Hardness analysis. The inner optimization problem in Eq. (2) involves combinatorial search over S for a fixed 0. However, while doing so, it requires to compute o (0, This makes our adversarial training problem NP-Hard (see Apppendix [ for proof).
PROPOSED APPROACH
In this section, we provide algorithms to solve the optimization problem (2). We first characterize it as a difference between a 7-weakly submodular function and a modular function. Next, we design ROGET, family of algorithms solve adversarial training problem (
3.1 SET FUNCTION THEORETIC CIARACCERIEATTINN OF F
Here, we provide a characterization of the objective function F(he. S as) using the notions of monotonicity and weak submodularity, which would lead to design approximation algorithm to solve our training problem 2 To do so, we first formally state the definitions of these notions.
Definition 1. Given set function Q :22 ..D-R. R. we define the marginal gain of as [(k ==
Q(S {k}) - Q(S). The function Q is monotone (non- (nonddecreasing) if Q[k () 2 ffr all l E DAS. The function Q is called y-weakly submodular if for some ? E (0, 1}, we have ExETYs Q () Z C D. Here, y is called the submodularity ratio of Q. The function Q is modular if ifQ(k) 5) - Q() all S S.T. T C D and k D.T.
(Q(T U S) Q(S) whenever S C CTCCT
Alternative representation of F(he, S ( (g=(oes)) Given a regularization function R(0) and regularization parameter À > O, we define two set functions G(O, S) and m(0,5) as follows:
Gx(0,5)= [D]
Σ iES
[AR(O) + ((h((a + Σ p p((ho(zz)):)))
(4)
JED
m) = D
[AR()) + p((ho(z,))
(5)
iES
Then, we represent F(ho. S ((0)) as the difference between the above functions, i.e.,
F(ho, S ( = Gx mx (0,
(6)
Here, my is modular function. Note that the above equality holds for any value of À > 0. However, as we shall see next, the submodularity ratio of G depends on À which affects the performance of the approximation algorithm designed in Section 3.2 Next, we present some assumptions which would be used to characterize the above representation of F.
Assumptions 1. (1) Lipschitz continuity: (a) The loss function ((h(2), y) is Li-Lipschitz with respect to h, (b) he (xx is L..Lipschitz with respect to x, (c) the adversarial network as a is Lø- Lipschitz with respect to Φ. (2) Stability of d (O,S): The learner's estimate about the parameter for
the adversarial network is stable (Bousquet & Elisseefi 2002 Charles & Papailiopoulos/ 2018 Hardi
et al. 2016), í.e., the solution Φ² "000, S)
the optimization (3) satisfies (0, SUk) (0, S)
3715 for some 3 > O and all 0. Stability holds for a wide variety of loss functions including (PL)
convex losses looseoooousueeeeee Bousquet& & Elisseeff (2002). a class of neural models called
losses Charles & Papailiopoulos (018). etc.. (3) Metric property of the cost of perturbation C:
The cost of perturbation C' used in Eq. 3 is a distance metric. Specifically, it follows the triangle inequality, i.e,, C(x', xx) < C(x', x" C(x", xx). (4) Norn-boundedness of C: The cost of perturbation C' is bounded by an lg norm, i.e., C( x)) < g||xx æ||. In the context of several prior works (Goodfellow et al. 2015 Madry et al., (017)) use Eoo distance which is bounded by & norm. (5) Boundeness of θ and Φ: We assume that the parameter space of both the learning model and adversarial network are bounded, i.e., ||0||2 I 8 6max and | S Φmax-
Monotonicity and --weakly submodularity of Gy, We now present our results on monotonicity and 7-weak submodularity of GA (see Appendix F. for a proof).
Theorem 2. Given Assumptions let there be a value of minimum non-zero constant Amin > 0 such that 8 = min y ming! Rmmin + ((hg(z), y) 2qp3La] > 0 where q and / are given in Assumptions 7 Then, for X > Amino we have the following statements:
4

---

Under review as a conference paper at ICLR 2023
(1) Gx(S) is monotone in S.
(2) Gx(5) 7-weakly submodular with Y > 7 = (0 + 2T TogT D + 3qu3L.)
3.2 ROGET: PROPOSED ALGORITHM TO SOLVE THE ADVERSARIAL TRAINING PROBLEM
In this section, we develop ROGET to solve optimization problem by building upon the proposal of Adibi et (202T). However, they design algorithms to solve the min-max problem on those functions that are submodular in S and convex in 9. In contrast, ROGET applies to the proposed objective F(hg.St (e.().)) ① which is the difference between 7-weakly submodular function and modular function, and may also be non- convex in 0. In the following, we describe them in details beginning with an outline of the pro- posed algorithm.
Algorithm 1 ROGET Algorithm
Require: Training set D, regularization parameter A, budget 6. # of iterations T, learning rate 1).
1: INIT(ho). So +
Development of ROGET. Our key goal is to optimize ming maxş F(hg. S| (0.().))) Now, we aim to develop an algorithm which would it- erate over the inner and outer optimization prob- lem and gradually refine S and 0.
2:
for ( 0 to T' do
3: O + TRAIN Se, mp)
4: Se+1 < SDG (Gx, my, b,+1,b).
5: 0 Or
6: return 0,
Iterative method for the inner optimization on
1: procedure SDG (G ma, 0.b)
S: Now, given a fixed 0, the inner maximiza- tion problem becomes set function optimiza- tion problem.
2:
S
3:
for
8 E [b] do
were a monotone sub-
4:
+ (1--/)/)
modular function, then could have applied
5:
Randomly draw subset B from
the well known greedy algorithm (Nemhauser 6:
M [ (0. e (S) m0 {c})eEB
et al., 1978). At each step, such a greedy algorithm would seek for an element e that would maximize the marginal gain F(eg, U el ((u)) FF S as (0) and update S (ee
7:
= argmax [(e
CEB if (S) (0, (c'))² then St (U(e)
8:
9:
10:
return $
1: procedure (R,
However, in our context, the function F may neither be monotone nor submodular and thus, we cannot apply the greedy algorithm for it- crating over the inner optimization loop Nev- ertheless, we note that can be expressed as difference between the 7--eaklly submodular function (0, S) and the modular function (0 S), as suggested by Eq. (6). As result, we can adopt the stochastic distorted greedy al- gorithm (Harshaw al. 2019) which, instead of maximizing exact marginal gain, maximizes a distorted marginal gain (1
2:
//SGD for h steps
3:
for i E [k] do
4:
Draw i ~ D uniformly at random
5:
if S then
8e(ha (a M.).)))))))))))
6:
0 + 0 n
00
0-
7:
else
8:
θ + 0 n
00
0=0
9: return 0
mx(0. (0, (e) for all & S at each step (procedure SDG in Algorithm [p. If this distorted marginal gain is positive, we update S - S U (e). This method gives an approximation guarantee for the inner optimization problem (due to Harshaw al. (2019)).
Theorem 3 (Harshaw et al. (2019). Given fixed O and that the size of the set B [B] = (ID)/b) log( (175) in line 5 of the procedure SDG. If the procedure SDG returns S as the output, then we have
m (x E[Gx(0,S) (0,))) -1=xp((=)] OPT) mm
(7)
where OPT is the optimal solution of the inner optimization problem. Here, expectation is carried out over the randomness of selection of B.
Iterative routine for outer optimization on 0: Having updated S using the distorted greedy algorithm described above, we minimize the F(he,S (e.)().)) with respect to 0 using few steps of gradient descent (called as k-SGD) per each round of update.
Outliee of ROGET: We sketch the pseudocode of ROGET in Algorithm [ It updates 0 and S in an iterative manner. During iteration f, ROGET updates 0 + 0.+1 by running few steps of gradient descent (line 3)- where we fix S at S, and attempt reduce the loss F(ho, Se (o)(0,))) with
5

---

Under review as a conference paper at ICLR 2023
respect to 9. In the next step, fix 0 and update S, - Se41 using stochastic distorted greedy algorithm (SDG, line 4). Note that during each time t, we compute St for a fixed 0 sequentially in b steps. Having obtained S at 8 < b, we update it such that it has highest positive distorted marginal gain (1 7) Gx
(2 {e}) and then, it is included into the set S to have S (c).
Approximation guarantees. In general, F is highly non-convex function of 0 and therefore, obtaining an approximation guarantee for any general F is extremely challenging. Hence, we derive approximation guarantee for a restrictive class of loss functions, called Polyak-L.ojasiewice (PL) loss functions. A function f is Tolyak-LLjjssiwieez if [[Vo](0)]] 2 alf(0) ming f(0') In Appendix E.2) we also present our results when F is convex in 0. Next, we initiate our discussion with a few more assumptions in addition to Assumptions [
Assumptions 2. (1) L-smoothness of F. For all 0 O and for all S E 2", we have IIV (ha.. S1 0.- (e) - Ve F(hgr, S ( S L|l0 0'll- (2) Boundedness of gradi-
ents of F. We have F(oa. S (0-(0.)) II I V max for all 0 E θ and for all S E 2". (3) Boundedness of loss E and model hg. For all 0 E + (x; (..))..)) v/) < Lmax and ||al| < hmax- (4) Size of B in SDG procedure. The size of the set By is B&| = (DI/b) log(1/0) (line 5 in procedure SDG used in Algorithm
(5) Adversarial network always perturbs feature. The cost of
perturbation C(a (0.5) (0:) 2,,) > Cmin > 0. Moreover, Cmin > 10 max (e_ + +8)/(1-e
where 7 is the submodularity ratio (Theorem 2
We provide justification for all the assumptions in Appendix D. Now we state the approximation guarantee of A for Polyak- Lojysk--ojssiewiezz (PL) loss (see Appendix E.2 for proof).
Theorem 4. Given the conditions of Theorem 2 and Assumptions
let F(h,, S (0.(0.)))
be a PL. function in 0 for all S, i.e., I|Vo (ha, S1 (<)<(0,)))
[F(ho, S us (0.s))
some ming F S) (0r(0r (o)rs)))) for some constant a. If we set the learning rate 17 = 1/KT in Algorithm
then for T Ol)/kE) iterations, 5 < (1-c->) and p (Cmin((e) (c= +5) 1) X02
maxl// maxx
we have the following approximation guarantee for Algorithm 7
min min (hh, I (z, S max min (( S $la0- (
[ (e + [x/x]] [x)====]]0((0000 (OPT + 21 / +e)
(8)
where O₂ is the iterate in Line in Algorithm| 7 OPT the value the optimum solution of our adversarial training problem (2) Cuin / (A02. max p + Cmin). Here 0max is defined in Assumption ann maxx; Cuin are defined in Assumptions
Note that, due to non-convexity, we do not provide guarantee on final Ø = 0r, but on the iterates 0j: and, the approximation factor suffers from an additional offset 2 hm2 a., even as + 0. In we present our results when F' is convex, where this bound becomes stronger.
Appendix E.2
EXPERIMENTS
In this section, we conduct experiments with real world datasets which show that ROGET achieves a better overall accuracy than the stateoo-thh--a methods for both bhox and black-box attacks. Appendix H contains additional results.
4.1 EXPERIMENTAL SETUP
Datasets and state-of-the art competitors. We experiment with CIFARIO (Krizhessky et al. 2014 and Fashion MNIST (Xiao et al.) (017) (FMNIST) this section. In Appendix H we also report results on CIFAR100. We consider seven state-of-the-art methods to compare our method- they
are: GAT (Sriramanan et al., 2020), FBF (Wong et al., 2019). TRADES (Zhang et al. 2019b),
Nu-AT (Sriramanan et al. 202 1). MART (Wang et al. 2019). PGD-AT (Madry et al. 2017) and RFGSM-AT (Tramèr et al. 2018). [ppendix|G]conaanee
more details about the baselines.
Evaluation protocol. We split the datasets into training (Dr), validation (Dva), and test set (Dres) in the ratio of 4:1:1 and 5:1:1 for CIFARIO and FMNIST respectively. We use the validation set for hyperparameter selection (mentioned later), early stopping (See Appendix Gor for details), etc. We report three types of accuracies, viz., (i) accuracy on clean examples Aclean= = F(y = 9 a: is not chosen for attack), (ii) robustness to adversarial perturbations measured using the accuracy

---

Under review as a conference paper at ICLR 2023
on the perturbed examples Arobust= P(y i x is chosen for attack) and (iii) overall accuracy
A= PP = 9))
Models for the learner. We consider two candidates for as. which model the learner's belief about the adversary during training. Specifically, we set either as = PGD Madry et al. 2017) or a AdvGAN (Xiao et al.] 2018). This gives rise to two variants of our model, vžz., ROGET
(ag
PGD) and ROGET (as AdvGAN), We use R (He al. (2016) and LeNet-5
(eCunn
al.
2015) architectures for CIFARIO and FMNIST datasets respectively.
Model for the adversarial perturbation. We consider two white-box attacks, viz., PGD (Madry
al. 2017) and Auto Attack (AA) (Croce & Hein 2020) well three black-box attacks, viz., Square (Andriushchenko et al. (2020) and black-box MI-FGSM (Dong et al. 2018 and Ad- vGAN (Xiao et al. 2018) perturb test samples. The exact details of the attacks are given in
Appendix G
The subset selection strategy of the adversary. In addition the adversarial perturbation mech- anism, the adversary also has strategy to select a subset Slatent of test instances to attack on. We experiment with two latent subset selection mechanisms. (1) Uncertainty bused subset selection: Here, the adversary selects the top-10% instances in terms of the prediction uncertainty of a classifier trained on clean examples from DT- Here, the prediction uncertainty for an instance x is computed as u(x) 1 max, h(=))()) (2) Label based subset selection: Here, the adversary selects instances who have specific label y E J' to perform attack, e.g., Slatent {il y = aeroplane) J. Note that, the underlying subset selection strategy is realized only during test- it is not revealed to the learner during training and validation, in practice. Appendix H also presents other strategies.
Hy perparameter selection. Suppose. for instance, that the adversary's 's latent strategy of selecting subset to perform attack is known during validation stage. Then one could easily simulate such strategy to create the perturbed instances in the validation set and use the resulting validation set to cross validate the underlying hyperparameters. However, the subset selection strategy is never revealed to the learner during both training and validation stage. Thus, the selection of hyperparameters becomes challenging and it completely depends on the underlying assumption about the adversary. In such a situation, we experiment with two methods for hyperparameter selection. (1) Default selection: Here, we use the hyperparameters of the baselines directly used in their original papers and codes (details in Appendix G. (2) Worst case selection: The key goal of ROGET is to learn a model which minimizes the worst case loss across all data subsets. In a similar spirit, here we aim to select the hyperparameters which would maximize the minimum accuracy across large number of subsets that underwent attacks. Formally, if we denote A(B, S) to be the overall accuracy of the trained model on the subset S, with hyperparameters B, we aim to estimate 3 argmax ming A(B, S).
To this aim, we draw R = 10000 subsets |= uniformly at random from Dval having size |S (.05|Daar and search over the hyperparameters 33 that maximizes the minimum accuracy across these R subets. In our case as well, we tune p similar manner to obtain p". Hence, the goal of this type of hyperparameter selection is same as the key goal of ROGET. Thus, it will provide fair comparison between all the methods.
4.2 RESULTS
Uncertainty based subset selection with default hyperparameters. Here we compare our method against all the state-of-thh-ar defense methods under the default hyperparameter selection on CI- FARIO and FMNIST, where all the hyperparameters of the baselines are set as what is reported in their respective work and for our method, we experiment with different values of p. Moreover, the adversary adopts uncertainty based subset selection, where it selects top 10% of the test set based on the uncertainty of a classifier trained on all clean examples. We report the results in Table and make the following observations. (1) ROGET (ap = PGD) and ROGET (ag = AdvGAN) achieve better overall accuracy A than the existing methods for all attacks on both the datasets (except for Square attack on CIFAR10). Among the two variants of ROGET, ROGET (as AdvGAN) is the predominant winner. (2) On CIFARIO, ROGET outperforms the baselines (except RFGSM-AT) in terms of the clean accuracy Aclean- This is because, ROGET is trained to defend much better when the adversary plans to attack a subset of instances rather than every instance. In contrast, the baselines are often trained in a pessimistic manner- they assume attack on every possible instance and consequently show sub-optimal accuracy on the clean examples. (3) There is no consistent winner among the baselines in terms of the robustness Arobust- Robust accuracy of ROGET is often
7

---

Under review as a conference paper at ICLR 2023
CIFARIO
FGD
AA
Square
MIFGSM
AdvCAN
Aciaan
A
Acabust
A
Auauus
A
A
Auahuse
A
GAT
78.76
59, 65
76.85
46,80
75.56
59,47
76.83
49.82
75.86
82.04
79.08
FBF
74.92
72.04
74.54
31.10
70.54
31.59
70.59
36.09
71.04
37.22
71.15
TRADES
80.25
64.68
78.69
53.37
77.56
63.06
78.53
54.82
77.70
83.82
80.60
Nu-AT
83.12
57.15
80.53
47.44
79.56
61.78
80.99
50.14
79.83
86.82
MART
81.30
65.04
79.68
52.21
78.39
63.78
79.55
54.15
78.59
84.75
81.65
PGD-AT
83.36
57.33
80.76
48.50
79.88
62.71
81.30
50.00
80.03
87.13
83.74
RFGSM-AT
89.10
33.25
26.37
82.83
57.68
85.96
23.21
ROGET P p= 1.0)
85.27
55.79
82.32
17.72
8179
63.18
83.06
47.90
81:33
55.96
85.64
ROGET (AN p 1.0)
87,86
47.97
83.87
39.97
83.07
62.21
85.29
40.27
83,10
91.53
88. 22
ROGET (AdvGAN, p 1.5)
88.23
83.83
36.48
83.05
61.01
85.51
83.15
91.96
88.60
FMNIST
Actsan
Aupouet
A
Auatust
A
Auntur
Square
A
Aupinue
A4
Auatue
Ad+GAN
A
GAT
91.47
3.18
82.64
0.000
82.52
0.01
82.32
8.32
83.15
29:09
85 24
14.29
66.74
TRADES
85.97
65.95
83.97
54.58
82.83
57.88
83.16
81.47
85.52
70.15
84.39
Nu-AT
903.41
5.13
81.88
0.000
81:37
0.06
81.38
18.24
83.19
15:72
82.94
77.72
59.73
77.02
61.46
77.19
70.10
PGD-AT
83.77
79.62
83.
53.62
80.76
57.05
81.10
83.73
83.77
72.88
RAGSM-AT
89.11
14.51
81.65
0.00
80,20
0.04
80.20
33.26
83.52
21.13
82.31
ROGET p
83.25
85.20
(AdiGAN, p 1.0)
87.85
35.95
82.66
37.08
82.78
43.25
83.39
81.17
87.19
71.46
86.22
ROGET ROGET (AdvGAN, 0.01)
86.23
72.61
84.87
54.86
83.10
58.19
83.43
83.97
86.01
74.30
85.04
Table I: Performance comparison under default hyperparameter setting for two white box attacks (PGD and AA) and three black box attacks (Square, MIFGSM, and AdvGAN). Here, the hyperpa- rameters are set what the baselines mentioned in their papers. We report (percentage) (i) accuracy on the clean examples Aclean (ii) robustness to the adversarial perturbations Arobust and (iii) overall accuracy A. Here, the adversary adopts uncertainty based subset selection to perform attack- the true subset chosen for attack glatent consists of top 10% test instances in terms of the uncertainty of a classifier trained on all the clean examples. (Yellow) Green indicate the (second) best performers.
CIFAR10
PGD
AA
Square
MIFGSM
AdyGAN
Adauu
Aralus
A
77.55
49.73
74.77
75.80
52.91
73.09
77.91
FBF
74.92
72.04
74.64
31.10
70.54
31.59
70.59
36.09
71.04
37.22
71.15
TRADES
83.63
51.43
80.41
42.55
79.52
58.60
81.13
48.00
80.07
87.37
84,02
Nu-AT
84.66
54.64
81.66
45.79
80.77
61.34
82.33
47.41
80.93
88.18
85.01
MART
$0.49
61.30
78.57
49.32
77.37
61.26
78.57
51.13
77.56
84.25
80.87
PGD-AT
83.36
79.55
50.00
REGSM-AT
85.84
45.94
81.85
39.49
81.00
60.25
83.28
37.91
81.04
89.42
86.20
ROGET (FGD)
36.63
31.16
83.09
43.06
82.28
62.33
14.20
42.20
82.19
90.15
86.99
ROGET (AdvGAN)
87,86
47.97
83.87
39.97
83:07
62.21
85.29
40.27
83.10
91.53
88.22
Table 2: Performance comparison under worst case hyperparameter setting on CIFARIO. Numbers in green (yellow) indicate the best (second best) performers.
competitive, e.g., in CIFARIO, ROGET (ag = AdvGAN) is the best performer for AdvGAN attack and ROGET (ag PGD) is the second best performer for Square attack. In FMNIST, ROGET (a& = AdvGAN) is the second best performer for MIFGSM and AdvGAN attack.
Uncertainty based subset selection with worst case hyperparameter setup. Next, we tune the hyperparameters of all the methods using the worst case hyperparameter tuning, where we select the hyperparameters that would maximize the minimum accuracy across a large number of subsets of the validation set. For ROGET, we tune in the same manner to obtain p². We present the results in Table 2 for CIFAR100 and make the following observations. (1) ROGET (as PGD, p = p²) and ROGET (as = AdvGAN, = p¹) outperform all the basclines in terms of the overall accuracy A. (2) In most of the cases, the overall accuracy A of ROGET with the worst case hyperparameter & == p" is better than A with the default hyperparameter p = 1. In contrast, the worst case hyperparameter selection improves A only for Nu-AT and TRADES among the baselines, from its performance with the default hyperparameter setup (Table [ vs. Table 2.
Evaluation on label based subset selection strategy. We now consider label based subset selection strategy of the adversary. We report the results for AA attack in Table where we also consider class focused online learning (CFOL) (Anonymous) 2022) as an additional baseline which provides guarantee on worst class loss in presence of adversarial attack. We observe that ROGET (a. AdvGAN) performs the best followed by ROGET (a& = PGD) for all classes. Additional results can be found in Appendix H
Impact of revealing the true subset selection strategy during validation. In practice, the learner does not know the adversary's true (uncertainty based) subset selection strategy during training and
8

---

Under review as a conference paper at ICLR 2023
validation. Here, we leak this information to the learner during validation. Then, we mimic the adversary's 's true strategy to select the subsets from the validation set and perform attack on them.
Airplane
Dog
Truck
Default
Worst
Oracle
GAT
75.19
75.06
75,28
GAT
76.85
76.12
81.13
FBF
72.39
71.77
67.11
FRF
74.64
74.64
74.64
TRADES
80.17
79.52
80.44
TRADES
78.69
80.41
81.33
No-AT
81.32
80.54
81.68
Nu-AT
80.53
81.66
83.85
MART
77.69
77.34
78.02
MART
79.68
78.57
79.94
PGD-AT
REGSM-AT
80.38
81,80
79.60
80,84
81.46
80.45
PGD-AT
80,76
80.76
80,76
CFOL
70.10
69.61
70.63
REGSM-AT
83,51
81.85
81.85
ROGET (PGD)
82.97
84.19
83.68
ROGET (PGD)
82.32
83.09
83.65
ROGET (Ad+GAN)
84.24
85.63
84.03
ROGET (AdeGAN)
83.87
83.87
83.83
Table 3: A for label based subset selection with AA attack CIFARIO. Green (Yellow) indicates the (second) best method.
Table 4: Revealing the oracle subset selection strat-
egy (uncertainty) A for PGD attack CI- FARIO.
Next, we select the hyperraaaameters resulting in highest overall validation accuracy. Table pares this strategy ("oracle") with previous hyperparameter selection strategies (default and worse). We make the following observations. (1) ROGET shows very stable performance across different hyperparameter selection methods. (2) GAT, TRADES, Nu-AT and MART significantly improve the performance and Nu-AT outperforms ROGET by small margin.
(3) ROGET'S focus is to maintain good accuracy across all subsets. Hence, the performance of ROGET, in absence of any knowledge about the adversary's 's selected subset, becomes very close to even better than the baselines having full knowledge of oracle selection.
Variation of A vs | The leamer's estimate about | the number of instances chosen for perturbation, can indeed be heavily inaccurate. In this context, train both the variants of ROGET using = 0.1| 0 and evaluate using different number of instances [ perturbed during test. In Figure we observe that the performances of all the models deteriorate; and our model performs better than the baselines for | |/ S 30%.
ROGEDAG
REGSM--X XT
PGD-AT
MARI
NE-AT
TRADES
2 (/P
D C 3F D0
Figure 5: A S
Comparing robustness subject to a minimum overall accuracy. In Tables 1 3 we reported robust and overall accuracy for fixed set of hyperparameters. By tuning these hyperparame- ters, one can improve robust accuracy by sacrificing overall accuracy. Therefore, here we aim to compare the robust accuracy, subject to the condition that the overall accuracy for all meth- ods crosses some threshold. Specifically, we first tune the hyperparameters of all the methods to ensure that the overall accuracy of all methods reaches given threshold and then compare their robust- ness. If indicates the hyperparameters, then we find maxp Arobust (P) such that A(P) a for some given a. Results on CIFARIO for a = 0.81 are shown in Ta- ble 6 We observe that ROGET (PGD) is the best per- former in terms of robust accuracy and ROGET (AdvGAN) is the best performer in terms of overall accuracy. Ro- GET (AdvGAN) is the second-best performer in terms of robust accuracy. More related results are Appendix H
CIFARIO
PGD
Square
Arauus
GAT
35.68
81.13
62.05
81.30
TRADES
53.78
81.74
Nu-AT
54.64
81.66
61.34
82.33
POD-AT
35.35
81.88
RFGSM-AT
45.94
81.85
60.25
83.28
ROGET (GD))
64.73
82.60
ROGET (AdvGAN)
55.73
82.85
63.93
83.67
Table 6: Comparison of Arobust, subject to
Aclean > 0.81.
CONCLUSION
In this paper we motivated a novel setting in adversarial attacks-whert an attacker aims to perturb only a subset of the dataset instead of the entire dataset. We presented defense strategy, ROGET which trains a robust model as a min-max game involving worst-case subset selection along with optimization of model parameters. To solve the optimization problem designed framework of loss
efficient algorithms, which admits approximation guarantees for convex and functions. Finally, experiments showed that ROGET achieves better overall accuracy as compared to several state-of-the-art defense methods across several subset selection strategies. Our work opens several avenues of future research. We can extend our work a slightly different setting where each instance has some importance score assigned to it. Another extension is to design a differentiable method for computing the worst-case attacked set, instead of using a greedy selection algorithm.

---

Under review as a conference paper at ICLR 2023
ETHICS STATEMENT
Our work tries to help ML. models in achieving better trade-off between robustness against ad- versarial attacks and performance on unperturbed/clean instances. Due the vulnerability ML models against adversarial perturbations, they have not been widely used in high-stake real world scenarios. Furthermore, the defense methods proposed so far to achieve robustness against attacks, face considerable drop in aceuracy clean (unperturbed) instances. Here, our framework takes step towards improving the performance on clean instances, while being robust against attacks on any subset of the dataset.
On the flip side, our method discusses a different type of adversarial attack, where the attacks are made on subset of instances. If one uses such attacks in practice, the attacked ML systems can become vulnerable. However, these systems can use the defense method proposed in this paper, which can provide notable defense irrespective of the subset selection strategy of the adversary. The capability of our method to achieve good performance without being aware of adversary's strategy makes suitable to be applied wide range of applications.
7
REPRODUCIBILITY STATEMENT
We have provided our code in supplementary material and provide the implementation details in Appendix G
REFERENCES
Arman Adibi, Aryan Mokhtari, and Hamed Hassani. Minimax optimization: The case of convex- submodular. arXiv preprint vrXiv:2111.01266 2021.
Jose M Alvarez, Theo Gevers, and Antonio M Lopez. 3d scene priors for road detection. In 2010 IEEE Computer Society Conference on Computer Vision and Puttern Recognition, pp. 57-64. IEEE, 2010.
Maksym Andriushchenko and Nicolas Flammarion. Understanding and improving fast adversarial training. Advances in Neural Information Processing Systems (NeurIPS), 33:16048-16059, 2020.
Maksym Andriushchenko, Francesco Croce, Nicolas Flammarion, and Matthias Hein. Square attack: query-efficieet black-box adversarial attack via random search. In European Conference on Computer Vision (ECCV), pp. 484-501. Springer, 2020.
Anonymous. Revisiting adversarial training for the worst-performing class. Submitted to Transac- tions of Machine Learning Research, 2022. URL
forum wtt.eewwwweeeeooommmeemmm
net nwt/
wkecsslYxII
Under review.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In International Conference on Machine Learning (ICML), pp. 274-283 PMLR, 2018
Shumeet Baluja and Ian Fischer. Learning to attack: Adversarial transformation networks, In AAAI Conference on Artificial Intelligence, 2018
Kush Bhatia, Prateck Jain, Parameswaran Kamalaruban, and Purushottam Kar. Consistent robust regression. In Advances in Neural Information Processing Systems, pp. 21 10-2119 2017.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 526,9552222222 2002.
Trevor Campbell and Tamara Broderick. Bayesian coreset construction via greedy iterative geodesic ascent. In International Conference on Machine Learning, pp. 698-706, 2018.
Nicholas Carlini and David Wagner. Towards evaluating the robustness neural networks. In /EEE Symposium Security and Privacy (SP), pp. 39-57. IEEE, 2017.
10

---

Under review as a conference paper at ICLR 2023
Zachary Charles and Dimitris Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In International Conference on Machine Learning, pp. 745-754. PMLR. 2018.
Pin-Yu Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In ACM Workshop on Artificial Intelligence and Security (AlSec CCS), pp. 15-26, 2017.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, pp. 1310-1320. PMLR, 2019.
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In International Conference on Machine Learning (ICML), pp. 2206-2216 PMLR, 2020.
Abir De, Paramita Koley, Niloy Ganguly, and Manuel Gomez-Rodriguez. Regression under human assistance. AAAI, 2020.
Abir De, Nastaran Okati, Ali Zarezade, and Manuel Gomez-Rodriguez. Classification under human assistance. AAAI, 2021.
Yinpeng Dong, Fangzhou Liao, Tianyu Pang, Hang Su, Jun Zhu, Xiaolin Hu, and Jianguo Li. Boosting adversarial attacks with momentum. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 9185-9193, 2018.
S Durga, Rishabh lyer, Ganesh Ramakrishnan, and Abir De. Training data subset selection for regression with controlled generalization error. International Conference on Machine Learning. pp. 9202-9212. PMLR, 2021.
Marwa El Halabi, Francis Bach, and Volkan Cevher. Combinatorial penalties: Which structures are preserved by convex relaxations? In International Conference on Artificial Intelligence and Statistics, pp. 1551-1560. PMLR, 2018.
Zhitao Gong, Wenlu Wang, and Wei-Shinn Ku. Adversarial and clean data are not twins. arXiv preprint DrrXiv:/704 1704.04960, 2017.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and hamnssiigg adversarial examples. In International Conference on Learning Representations, 2015. URL. http://
arxiv. www.or////bssaao 1422.572
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability stochastic gradient descent. In International conference on machine learning, pp. 1225-1234. PMLR, 2016.
Chris Harshaw, Moran Feldman, Justin Ward, and Amin Karbasi. Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications. In International Conference on Machine Learning, pp. 2634-2643 PMLR, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778. IEEE Computer Society, 2016.
Guosheng Hu, Yongxin Yang, Dong Yi, Josef Kittler, William Christmas, Stan Z Li, and Timothy Hospedales. When face recognition meets with deep learning: an evaluation of convolutional neural networks for face recognition. In Proceedings of the IEEE international conference on computer vision workshops. pp. 142-150, 2015.
Andrew Ilyas, Ajil Jalal, Eirini Asteri, Constantinos Daskalakis, and Alexandros G Dimakis. The robust manifold defense: Adversarial training using generative models. arXiv preprint arXiv:1712.09199 2017.
Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In International Conference on Machine Learning, pp. 2137-2146. PMLR, 2018
11

---

Under review as a conference paper at ICLR 2023
Joel Janai, Fatma Güney, Aseem Behl, Andreas Geiger, et al. Computer vision for autonomous vehicles: Problems, datasets and state of the art. Foundations and Trends@ in Computer Graphics and Vision, 12(1-3):1-300 2020.
Harini Kannan, Alexey Kurakin, and Ian Goodfellow. Adversarial logit pairing, 2018.
Vishal Kaushal, Rishabh Iyer, Suraj Kothawade, Rohan Mahadev, Khoshrav Doctor, and Ganesh Ramakrishnan. Learning from less data: A unified data subset selection and active learning framework for computer vision. In 2019 IEEE Winter Conference on Applications of Computer Vision (WACV), pp. 1289-1299. IEEE, 2019.
Ira saaeemmachhr-Shhizermaa Steven M Seitz, Daniel Miller, and Evan Brossard. The megaface benchmark: 1 million faces for recognition at scale. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4873-4882, 2016.
Krishnateja Killamsetty, Durga Subramanian, Ganesh Ramakrishnan, and Rishabh Iyer. Glister: generalization based data selection framework for efficient and robust learning. In AAAI, 2021.
Hoki Kim, Woojin Lee, and Jaewook Lee. Understanding catastrophic overfitting in single-step adversarial training. In Thirty-Fiith AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty- Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pp. 8119-8127, AAAI Press, 2021. URLhttps://oje aaai wwwo/orgnneeeeeee php/
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. The cifar-10 dataset. In online: https///www.cc..orron/t
edu/-kkrisseffffrmmmm http://wwww....ooooot....drrdrdd
2014.
Alexey Kurakin, lan Goodfellow, and Samy Bengio. Adversarial machine learning at scale, 2017.
Alexey Kurakin, Ian J Goodfellow, and Samy Bengio. Adversarial examples in the physical world. In Artificial intelligence safety and security, pp. 99-112. Chapman and Hall/CRC, 2018.
Matthew L Leavitt and Ari Morcos. Linking average-and worst-case perturbation robustness via class selectivity and dimensionality. arXiv preprint arXiv:2010007699. 2020.
Yann LeCun al. Lenet-5, convolutional neural networks. URL: http://yann. lecun. com/exdb/lenet, 20(5):14, 2015.
Xin Li and Fuxin Li. Adversarial examples detection in deep networks with convolutional filter statistics. In Proceedings of the IEEE international conference on computer vision, pp. 5764-5772. 2017.
Xuanqing Liu, Yao Li, Chongruo Wu, and Cho-Jui Hsich. Adv-bnn: Improved adversarial defense through robust bayesian neural network. arXiv preprint arXiv:1810.01271 2018.
Yanpei Liu, Xinyun Chen, Chang Liu, and Dawn Song. Delving into transferable adversarial examples and black-box attacks, 2017.
Mario Lucic, Matthew Faulkner, Andreas Krause, and Dan Feldman. Training gaussian mixture models at scale via coresets. The Journal of Machine Learning Research, (8(1):5885-590) 2017.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 2017.
Dongyu Meng and Hao Chen. Magnet: two-pronged defense against adversarial examples. In ACM SIGSAC Conference on Computer and Communications Security, pp. 135-147, 2017.
Jan Hendrik Metzen, Tim Genewein, Volker Fischer, and Bastian Bischoff. On detecting adversarial perturbations, 2017.
Baharan Mirzasoleiman, Kaidi Cao, and Jure Leskovee. Coresets for robust training of deep neural networks against noisy labels. Advances in Neural Information Processing Systems, 33, 2020.
12

---

Under review as a conference paper at ICLR 2023
Konda Reddy Mopuri, Utkarsh Ojha, Utsav Garg, and R Venkatesh Babu. Nag: Network for adversary generation. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 742-751,
Marie Myers. Voice recognition software and a hand-held translation machine for second- laagua-l learning. Computer Assisted Language Learning, 13(1):29-41, 2000.
George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions-i. Mathematical programming, 1978.
Nicolas Papernot, Patrick McDaniel, and Ian Goodfellow. Transferability in machine learning: from phenomena to black-box attacks using adversarial samples, 2016.
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In ACM on Asia Conference on Computer and Communications Security (AsiaCCS), pp. 506-519, 2017.
Leslie Rice, Eric Wong, and Zico Kolter. Overfitting in adversarially robust deep learning. In International Conference on Machine Learning (ICML), pp. 1093-8104. PMLR, 2020.
Alexander Robey, Luiz Chamon, George Pappas, Hamed Hassani, and Alejandro Ribeiro. Adversarial robustness with semi-infinite constrained learning. Advances Neural Information Processing Systems, 34, 2021.
Ahmad EL Sallab, Mohammed Abdou, Etienne Perot, and Senthil Yogamani. Deep reinforcement learning framework for autonomous driving. Electronic Imaging, 2017(19):70-76, 2017.
Pouya Samangouei, Maya Kabkab, and Rama Chellappa. Defense-gans Protecting classifiers against adversarial attacks using generative models, 2018.
Esha Sarkar, Hadjer Benkraouda, Gopika Krishnan, Homer Gamil, and Michail Maniatakos. Facehack: Attacking facial recognition systems using malicious facial characteristics. IEEE Transactions on Biometrics, Behavior, and Identity Science, 2021.
Ali Shafahi, Mahyar Najibi, Mohammad Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry S Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! Advances in Neural Information P Processing Systems (NeurIPS), 32, 2019.
Gaurang Sriramanan, Sravanti Addepalli, Arya Baburaj, al. Guided adversarial attack for evaluating and enhancing adversarial defenses. Advances in Neural Information Processing Systems, 33: 20297-20308, 2020.
Gaurang Sriramanan, Sravanti Addepalli, Arya Baburaj, et al. Towards efficient and effective adversarial training. Advances in Neural Information Processing Systems, 34, 2021.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In Yoshua Bengio and Yann LeCun (eds.). 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014. URL http:/ httt:///rxiv.. www./ii..rr......ooo org.org/gaa abs/ 1312. 6199
Qi Tian, Kun Kuang, Kelu Jiang, Fei Wu, and Yisen Wang. Analysis and applications of class-wir wise robustness in adversarial training. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1561-1570, 2021.
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick D. McDaniel. Ensemble adversarial training: Attacks and defenses. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3. 2018, Conference Track Proceedings. OpenReview.net, 2018. URL /
net/
Forum?1d=rk2v5e
Fatemeh Vakhshiteh, Ahmad Nickabadi, and Raghavendra Ramachandra. Adversarial attacks against face recognition: comprehensive study. IEEE Access, 9:92735-92755 2021.
13

---

Under review as a conference paper at ICLR 2023
Sushma Venkatesh, Raghavendra Ramachandra, Kiran Raja, and Christoph Busch. Face morphing attack generation & detection: A comprehensive survey, IEEE Transactions on Technology and Society, 2021.
Mei Wang and Weihong Deng. Deep face recognition: A survey. Neurocomputing, 429:215-244, 2021.
Wentao Wang, Han Xu, Xiaorui Liu, Yaxin Li, Bhavani Thuraisingham, and Jiliang Tang. Imbalanced adversarial training with reweighting, arXiv preprint arXiv:2107.13639 2021.
Yisen Wang, Difan Zou, Jinfeng Yi, James Bailey, Xingjun Ma, and Quanquan Gu. Improving adversarial robustness requires revisiting misclassified examples. In International Conference on Learning Representations, 2019.
Kai Wei, Rishabh lyer, and Jeff Bilmes. Submodularity in data subset selection and active learning.
In International Conference on Machine Learning, pp. 1954-1963, 2015.
Eric Wong, Leslie Rice, and Zico Kolter. Fast is better than free: Revisiting adversarial training. In International Conference on Learning Representations (ICLR), 2019.
Chaowei Xiao, Bo Li, Jun-Yan Zhu, Warren He, Mingyan Liu, and Dawn Song. Generating adversarial examples with adversarial networks. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI' 18, pp. 3905-3911. AAAI Press, 2018. ISBN 9780999241127.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image fenchhmahhhaa machine learning algorithms. CoRR, abs//708.077 077407774, 2017. URL http:://axiiv.rrgg//////
1708.077 07747
Zihao Xiao, Xianfeng Gao, Chilin Fu, Yinpeng Dong, Wei Gao, Xiaolu Zhang, Jun Zhou, and Jun Zhu. Improving transferability of adversarial patches on face recognition with generative models. In Proceedings of the IEEE/CVF Conference Computer Vision and Puttern Recognition, pp.
11845-11854, 2021.
Cihang Xie and Alan Yuille. Intriguing properties of adversarial training at scale. In International Conference on Learning Representations (ICLR), 2019.
Cihang Xie, Jianyu Wang, Zhishuai Zhang, Zhou Ren, and Alan Yuille. Mitigating adversarial effects through randomization, 2018
Xiaoyong Yuan, Pan Hc, Qile Zhu, and Xiaolin Li. Adversarial examples: Attacks and defenses for deep learning. IEEE Transactions on Neural Networks and Learning Systems, 20(5):2805-2824 2019. doi: 10. 109//NN1NNNN S.20 8.1 8. 2886017.
Xuejing Yuan, Yuxuan Chen, Yue Zhao, Yunhui Long, Xiaokang Liu, Kai Chen, Shengzhi Zhang, Heqing Huang, Xiaofeng Wang, and Carl A Gunter. [CommanderSongl:: A systematic approach for practical adversarial voice recognition. 27th USENIX security symposium (USENIX security 18), pp. 49 49-64, 2018.
Dinghuai Zhang, Tianyuan Zhang, Yiping Lu, Zhanxing Zhu, and Bin Dong. You Only Propagate Once: Accelerating Adversarial Training via Maximal Principle. Curran Associates Inc., Red Hook, NY, USA, 2019a
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, 2019b.
Ping Zhang, Rishabh Iyer, Ashish Tendulkar, Gaurav Aggarwal, and Abir De. Learning to select exogenous events for marked temporal point process. Advances in Neural Information Processing Systems, 34, 2021a.
Xingwei Zhang, Xiaolong Zheng, and Wenji Mao. Adversarial perturbation defense on deep neural networks. ACM Comput. Surv., 54(8), oct 2021b. ISSN 0360-0300. doi: 10.1 10.1145/3465397. URL https://dol wwwoooo..............oooo......o 1et..11453333335
Zhihao Zheng and Pengyu Hong. Robust detection of adversarial attacks by modeling the intrinsic properties of deep neural networks. Advances Neural Information Processing Systems, 31, 2018.
14

---

Under review as a conference paper at ICLR 2023
Robust Training through Adversarially Selected Data Subsets (Appendix)
A
FUTURE WORK
Our method selects a worst-case subset and trains the model parameters in an end-to-end manner to output a robust defense model. However, it might be more interesting to take into account an importance score for each instance to decide which instances need more protection against attacks. A Additionally, it will be interesting to design a completely differentiable training method for computing the worst-case subset of attacked instances, instead of using a greedy selection algorithm along with gradient descent.
B RELATED WORK
Adversarial attacks. The attack methods (Szegedy al. 2014 Kurakin et al. 2018 Madry et al. 2017, Goodfellow et al.] 2015 Kurakin et al.) 2017: Carlini & Wagner 201 discussed in the main paper can be broadly classified in three different settings white-box attacks, ii) black-box attacks, and iii) transfer-based attacks. In white-box attacks, the attacker assumes full knowledge about the defense model, and hence can access the gradients of the defense model. This led the
design of several gradient-based based attacks (Szegedy et al. [014] Madry et al.) 2017; Goodfellow et al. 2015). Specifically, [Szegedy et al. (2014) use constrained optimization, Carlini & Wagner (2017) use special regularization in the optimization. However, in black-box setting the attacker can only query the defense model being attacked (Iyaas et al.] 2018). This led to the design of score-based attacks (Chen al. 2017) which use the scores output by the defense model to approximate gradients, and craft adversarial perturbations. Additionally, to tackle this setting, researchers came up with transfer-basee attacks (Papernot et al. [2017: 2016: Liu et al. 2017) where the attacker computes adversarial examples on a completely different model, in order to attack the defense model.
Sperifically,Azeeedy
Defense methods. Apart from Adversarial training methods (Wang al. 2019 Zhang et al. 2019b Robey et al., 2021] Shafahi et al.) 2019); Zhang et al., [2019]] Kim et al. [021]] Andriushchenko & Flammarion| 2020) already discussed in the main paper, there are several other approaches to designing robust defense models. One of them leverages randomness to defend against adversarial examples (Xie et al. 2018 Cohen et al. 2019 Liu al. 2018). These works introduce randomness either in the inputs or in the model parameters which makes the model robust against
Yet another line of work (Iyaas et al. 2017 Meng Chen 2017 (Samangouei et al. 2018) tries to use generative models to first project the input using an encoder, and then use the output of the encoder for classification. The projection step claimed to reduce the impact of adversarial perturbations. Another popular approach (Gong et al. 2017 Metzen et al. 2017 Li & Li 2017 Zheng & Hong 2018) to detect the presence of adversarial perturbations, before attempting to classity the input. The idea motivated by the assumption that adversarial perturbed instances follow a different distribution as compared to natural (unperturbed) instances. Recent works have considered assigning different weights to different classes based on the underlying loss ensure robustness against adversarial perturbation [Anonymous] 2022 Tian et all 2002 Wang et al. 2021 Leavitt & Morcos (020)) Tian al. (2021) pointed out that accuracy across different classes significantly vary during adversarial training. Leavitt & Morcos (2020) showed that increasing class selectivity improves worst case perturbation while decreasing class selectivity improves average case perturbation. |Wang al. 2202 proposed Separable Reweighted Adversarial Training (SRAT) assign weights to different instances to learn separable features for imbalanced dataset. Recent work (Anonymous) 2022) develop adversarial training approaches that attempt to control the worst possible loss across different classes.
Data subset selection. There a rich literature of work proposed for data subset selection in conjunction with model training (Campbell & Broderick 20088] [ucic et al., [017 DDugaa et al.) 2021] Killamsetty et al., 2021 De et al. 2020 2021). As mentioned the main paper, these existing works Tocus more towards efficient learning (Durga et al. 2021 Mirzasoleiman al.] (2020). human-centric learning (De et al. 2020 202T) and active learning (Wei et al., 2015 Kaushal et al. 2019). As results these works operate solution techniques. For example, De et al. (2020) employ data subset selection in order to distribute instances between human and machine to generate semi-automated MI. models. Also, the works
completely different setting, and consequently require different
15

---

Under review as a conference paper at ICLR 2023
in (Durga et al. 2021 Mirzasoleiman et al. 2020) uses subset selection to reduce training time of ML models by reducing the size of the effective training dataset.
C ILLUSTRATION OF OUR ADVERSARIAL TRAINING SETUP AND THE HARDNESS ANALYSIS
Probabilistic generation of S. Let us assume that the adversary follows a probabilistic strategy, i.e. ( 36) Pii E S). Thus (x., Mt) indicates the probability that the instance æ; chosen for attack. Here, one may wish to minimize the following loss:
min max 0 (m) BED)
Σ RED
π (a,, yi (i) (as (z;) (.)))))))) vi) + (1- < (())
(9)
such that,
Σ (Z, y:) S b, (,,, vi) E [0, 1].
(10)
ED
The inner optimization problem is a linear optimization problem in each Ta w.). so ((;, u) {0, 13. Then, if define S = {il i (2,, 1}.
min max Si
(ho(as((a))) (2))). Σ pl(ho((z))
(11)
JEDYS
Hardness analysis. Let consider specific instance of the problem where y E (0, +1,-1111 -1) and hg is fixed function independent given as
if. y (+1,-1)
(x)
(12)
1 Eve(-1,t)) Ae 1 m)²
if, y =0
where, A << 1, 0, is constant vector, x is bounded such that 1 Eve(-114)) A x)
v.0
0.
Similar (not exact) distributions were also used for instantiating anecdotal examples in (Zhang et al. 2021a). Let us further assume that the training set consists of only instances with E -1,--1 and no instance with y 0. Additionally, let (x))) = & @ æ, where denotes element-wise multiplication operation. Here, & is restricted to a set, such that - Eyet- Ae(1-v (x))) > 0. Also, consider that 0 and C = 0 in this specific setting. Since he is independent of 0, the optimization problem 2 in this setting reduces
max S5
E(he(as(x:)) 31)
(13)
iES
max &
log(Ae (1-21 (z.
(14)
EE
min
log(A) + y: 0 as (x;)))
(15)
#ES
20
min
log(A) + +(1 - Yi 0 as (xx))
(16)
S
min
(og(A) Σ yi 0 a (xx)))
(17)
Thus, the solution of above optimization 17 equal the following optimization problem:
min S
(1 - Di 0g (x:))²
(18)
$E.
which is equivalent to the following optimization problem:
min S.
Σ V: & (T 1 xx))²
(19)
The next steps follow directly from (De 202T) Proof of Theorem 1). We describe the steps
below to make the proof self-contained.. Assume that X = [(0 @ æ1)T;... ;.,...: (6, @ )) has full rank DD]. Now, let y [V).- [y:...,, .i..... MIp]) Mpp]l
DR be arbitrary vector of real
16

---

Under review as a conference paper at ICLR 2023
numbers and R (Xx²)² ( ④ n: =e,, where e; is column vector with entry position i, and 0 elsewhere.
1 be the right inverse of X (exists because X has full row rank). By definition,
Further, let Ø' - Φ x (3 r). We rewrite the objective of the optimization [9 in terms of ø' to obtain
Σ (1 yi (Ø' X ly (y (0. + xx))²
(20)
Σ Yi Φ (0g 0 22
y: (y r)² e,)²
(21)
E(1 (1
yi Φ (00 23)
yi +ys r2)²
(22)
Σ (r: x 00 x.))
(23)
EES
Hence, our optimization problem reduces to the following optimization problem: o" (0o @x)))
min d'SS
Enr -
(24)
iES
Since the above optimization is known to be NP-hard (Bhatia et al. 2017), we have successfully proven that our optimization problem is also NP-hard.
17

---

Under review as a conference paper at ICLR 2023
D EXPLANATION OF THE ASSUMPTIONS
In this section, we justify the assumptions mentioned in Sections 3.1 and 3.2
ASSUMPTIONS I
(I, 5) Lipschitz continuity and boundedness of the parameters: We think that Lipschitz continuity of loss and models are very prevalent. In most practical and well behaved ML algorithms, these assumptions hold. For any differentiable networks that have bounded parameters and no singularity. we usually have these conditions. If we do not have such conditions, gradients may blow during training.
(2) Stability: Algorithmic stability is also desirable property in MI.. It ensures that if we make changes in one instance, the parameters do not change. 1,2 Regularization, drop-out and even SGD) algorithm itself encourages stability.
(3, 4) Metric property and norm boundedness of cost of perturbation: Most existing works have used Loe distance as the cost of perturbation. Our method considers general set of metrics which not limited to L. distances. L. space norms are bounded by each other by a factor, i.e., k Le Lo L2 We bounded our metric norm by the L2 norm for standardization of analysis. We do not foresee the deviation of such a condition in a practical scenario.
ASSUMPTIONS
(1) L-smoothness of F: This just ensures that gradients of F are Lipschitz too. Indeed this is bit stronger condition than Lipschitzness of F itself. A wide variety of smooth activation functions like Linear, Sigmoid are L-smooth. Even the discontinuous functions like ReLU are often L-smooth almost everywhere.
(2,3) Boundedness of F, h and f: As long as there is inherent singularity in the interior of these functions (c.g., unlike 1/(x-a)), this is redundant condition, given the boundedness of 0. We simply keep it to make our notations simple during analysis. But this condition does not put any additional restriction, if the underlying function does not have a singularity in the interior.
(4) Size of B: This is a parameter used in our algorithm it does not put any restriction of the underlying setup. neither the loss function nor the models.
(5) Adversarial network always perturbs feature: This imposes the notion of very strong adversary. Even if we deviate, the theoretical bounds would be stronger. We keep this condition for the sake of brevity.
18

---

Under review as a conference paper at ICLR 2023
E PROOFS OF THE TECHNICAL RESULTS IN SECTION 3
E. MONOTONICITY AND 7-WEAK SUBMODULARITY OF Gx: THEOREM 2
Theorem Given Assumption 7 let there be a value of minimum non-zero constant Amin > 0 such that 8 m N ming| (mmin + ((ho(x), y) 2quBLø] > 0 where q and 3 are given in Then, for À > Amins we have the following statements:
Assumption 7
(1) (X(S) is monotone in S
(2) (x( --wakkly submodular with > 77" = [e + 2I Log Dmxx + 3qu3Btal
Proof sketch. To prove monotonicity, we first show that Gx(A) S) > ((s) (2) )) yk + æ;) p (() (zx)). yk) - Bp]S]|| (0, (0, (0, S)ll Next, we use Assumptions to show ((h (0,s) that this quantity is more than E"
+ AR(O) which more than XR(O)
To prove y-weak submodularity, we first show that GA(k T) I
20max 3qu To that aim, we show that Gx(k I AR(0) + ((ho(as (0, TUK) (x+)), [ex)).ue. uk) + q/3 S XR(0) (he ( (0 (xx)), yx) + Next we use the Lipschitzness of different functions show that it is less than tr +L L L Pmax +3qu3 This, together with the fact that (A S) l derived during the proof of monotonicity, results in the inequality Gx (k: ( /)>//>/ T) [E + 2 Tog Tng Omax + 3qu -1, Finally, we use the result of Proposition 0 (in Appendix F to complete the proof.
(e.))
yk.) (1 (1(((h(aap-(ee.)) (a (*t)), yk)
Proof. Monotonicity of Gx. Let c D and let k D S.S. For any O, Gx SUK) - ()
Σ AR(0) + ((he (x:))) vi)
1
AR + (0.)(((
[D]
D
FESUK
iES
AR(O)=
Σ (O.SL))) Hi)
Σ SS
E(he ((eee(a--0.s)((
(25)
DDi
VESUK
We now derive bound on Eiesuk (holas (O.S)) (2:)), vi) (ess Us- ing the definition of (SLA) from Eq. (3, we obtain:
Σ [( vi)
- (X00p)/))))))()))ssssss))).l)))
RESUR
(()))) (a0 RES
(26)
[( (2:)) vi) (0
iESUR
Σ
IC(as- (o.se))))) -
(27)
AESUK
Substituting inequality
27 in Eq.
25
we obtain:
-A0,,SUA-GG(00,55
O + ((ho(ag-(e.s)
(28)
D
Σ
(29)
VESUK
1
XR(O) + + ((ho(as
D
Σ
- -ete:///e..eee-)o---///rrs/seeed (30)
KESUK
19

---

Under review as a conference paper at ICLR 2023
A + l(halas (0.)(()))
Σ
(lag- (0.5)
(31)
iESUK
1.5 kg
AR(O) + ((ho (0.9) yk) quoL
(32)
D
|S|
(AR(0) ((ho (0.5) (2x) yk) 2.p D
(33)
Here, inequality (31) follows from using triangle inequality of Assumption | and inequality (32 follows from the stability assumption Assumption We use the assumption on l to conclude that the right hand side of inequality (33) is non-negative. This shows that GA is monotone in S.
[
w-we submodularity of Gx. We first provide an upper bound Cx G),
Gx T B) ())
Σ
AR(O) + ((ho (QTT)))))))))))) v4))
XR(O) + (0 v.)
D
DD]
VETUk
ET
AR(O))
Σ
((oo( (x:)),
Σ (0oo(00r007(
(34)
[D]
iETUK
SET
AR(O)= + Σ
- (eTU)
D
-
iET
Σ (x.)) m) (())
ET
me)) + 11 Σ
-
(a))))))))
NET
(35)
AR(0) + (hho (O.TUA) (xx)) yk) + 9o3
(36)
D
Here, the last inequality is due the fact that:
Σ
(x;)) yi) - (C0(0
(37)
iET
Σ (0m) yi) pC (0.7) (x)), 5
(38)
iTT
since (0, provides the maximum of the second term and the fact that:
Σ
(1))) x.)) S qu
(o.TUst))) (0.7) (0.77 (x:))
(39)
S 17 (Stability of
(40)
T
Lower bounding the ratio. Using inequality (33) and inequality
36).
we get the following
Gx -
(0,TTU - (O,T)) (O,
XR(0) ((ho(a (())(a))(0.)))())) (xw)) vr) 2qp L.
XR(0) + E(he as (O.TUR) (xx)), yx) + qH3L
AR +
2q14B16
XR(0) E(hha (a. (0.9) (xx) (xx)), wx) + Ehho (as- (as- (xx) ys. E(ho (coo(ass0000 (0.) uk) qu3Lo
8 2L Lo + 3quBLB %
(41)
20

---

Under review as a conference paper at ICLR 2023
Above inequality 411 follows from Lipschitz continuity assumption, and upper boundedness of + mentioned in Assumptions This together with Proposition us the result.
E.2 APPROXIMATION GUARANTEES
Theorem 4 Given the conditions of Theorem and Assumptions let F(hg, S (..
be a PL junction in for all S, i.e., o (he. S S ( z a a(F(hg. S (o,5) ming S as (S)) some some constant a. If we set the learning rate lj = 1/kT in Algorithm
then for T O(1kke) iterations, 5 < (1-e-h') and
(Cmin((e) ((e +5) 1-5)-1 1) X02 max mmax-
we have the following approximation guarantee for Algorithm
min E[ STla "0.(0.,37)) max min E(F S
- (e +0//k| 66))/(((()P)) (OPT +
+ t)
(42)
where O2 is the iterate in Line in Algorithm OPT is the value at the optimum solution of our adversarial training problem ( Cunin/ (10 max
paxx + Cuin). Here mmax is defined in
Assumption 7 and max: Cuin are defined in Assumptions
Proof. Under the assumptions, Lemmas and 14 hold. Using Lemma 13 we have that for all S,
(1--Xx
+ F(hā, S s- (ō. s)) (l S. as (o. S 4 max
(43)
where the expectation above taken over randomness in stochastic distorted greedy algorithm. Now, taking expectation over the randomness in k-SGD gives us,
+ e 1
1
E E[ Sla (o.s).))))) (F Se a (0. & 4 max
(44)
K6
where the expectation is computed over all the total randomness of the algorithm. We now sum the above equation over all T get,
E E S ()-((.,))) (| S. (s.
< 44 max (45)
Using Lemma we have that for all 0,
( Se-1 a (0. ( Fhe, S.-1 aalllapseee (0.(00.._.))1
4L02 4L0
)o
L max
< V max
(46)
2a
where the expectation is w.rtt the total randomness the algorithm. Summing over all T, we obtain:
E E[F(he, (0. I.lase..llas..... (as-
4T 1o
2T
< V max +
max
max
(47)
2a
Combining inequality
45
and inequality
47 and then dividing by T throughout we obtain:
e- +8
T
F(F(hg $1a s),))
K
T
4L.2
no)
Ln max
< maxxE[((ho, S 1 (0.))) 6
max max + max
2a
21

---

Under review as a conference paper at ICLR 2023
Taking min over 0 both sides and noting that all terms except independent of 9, get
1 e- + E Fh S|a ((.)) )!
T
4T.02 max
L max
min max B[F S\ (0)(0,)) + 6kn max c knj
(48)
2a
Putting
KT we obtain:
e + T
(
S
4L02 max
6
LV max
< OPPT +e
max
T
T
2kTo
0-0/T"
42.0
T
[F S 1la0 [,,
OPT
+
(49)
1
1
e- +
This gives us the statement in the proof of the theorem.
22

---

Under review as a conference paper at ICLR 2023
Algorithm ROGET Algorithm (with additional
variants of gradient descent for convex F?)
Require: Training instances regularization param- iterations T, learning rate y
eter X, budget
METHODE [GD, BGD, SGD)
procedure TRAIN(0, MRTHOO))
1: INIT(ha). S. 4 0
2: //deterministic gradient
2: for L= to T
do
descent
3: Oc+1 <- TRAIN S., th, жетнст)
3: dMMETHO is GD then
S.11 SDG (G,, 1,
return (0 Slag (a)r(0.s))/00)).
5: 0 = Σ n..
//stochaszic gradient descent нEтноо is SGD
return 0, Sr
1: procedure SDG MA,, 0.
Draw ~ D uniformly at random if S then F ((hp(as(w))) vc)
2:
5++
3:
for [6] do
9:
4:
Thh, t (1
10:
else
5:
Randomly draw subset B from D
II:
F - return 8
p((aa(
6:
argmaax Ga(e G () mx((e))
12:
7:
if Gxle (e () mx({e")) 2 0 then
8:
S f- SUte)
return
Approximation guarantee for convex F. Next consider the unlikely when F is convex. Here, we present the approximation guarantees of our algorithm, again copied here in Algorithm 2 specifically with two different variants of stochastic gradient descent, viz., simple gradient descent (GD) and one-step stochastic gradient descent (SGD) (instead of k-SGD) that allows us to derive approximation guarantees for convecity. These guarantees generalize the results from Adibi al. (2021).
Theorem 5. Given the conditions of Theorem and Assumption 2 let F(oo. S (o,(),)) be convex in θ for all S. the learning rate r = 1/VT. Now, suppose we set either method GD or method SGD in line 3 in Algorithm 2 i.e.. use either step gradient descent stochastic gradient descent during training O for fixed S, then for T = O(1/e²) iterations, 8 < (1 e->") and
-20 m/xx)/emaa we have the > (1 )/E""""" (1- 5)Cs) p < [Cmin((e->" + + 1oj---11 -
following approximation guarantee.
(
1aFx Sla (6,5) s (1- - +8/h]] [ +c)
(50)
where OPT is the value at the optimum solution of our adversarial training problem 2 Cmin/ (X02 max + plmax + Cmin). Here, 0max is defined in Assumption 1 and Lmaxs Cmin are defined in Assumption
Proof. Under the Assumptions and convexity of F, Lemma II holds. Hence, have that O O
20
Σ B[F(hg, S.
B[F S, (e.() S 2T
V max +
(51)
Under Assumptions Tand
Lemma also holds, which gives us, for all S,
11- e T" + F(ha. S 5lass11ss00 (G.s)) R[F(ha, S. 1 (0.(0..3)) 2
(52)
max
We note that in Lemma greedy algorithm. We now include the randomness due to stochastic gradient descent and take the total expectation to obtain.
9 the expectation was taken over the randomness stochastic distorted
(1 1- -- +
E B[F(ha, Slas (0.s;) E(F Se Selad "o0(0,,3))) V max
(53)
23

---

Under review as a conference paper at ICLR 2023
Summing the above equation over t 1 to T gives us, for all 0 E G,
Σ
e
+
E F 0. S (la (0..)) - E[F S. (el001(0.3)))) - 2T max (54)
1=1
Summing inequality 51 and inequality (54) and dividing by T, we obtain:
1 e
(h slab-(0,s))
BhF S. (.3,))
28 max
4r V
T
T1
Since the above holds for all S, we take the maximum over all possible S, on both sides to obtain,
e e-
+
T [ S $10 $100-(0,,)))
T max ((F (0.s)]
20
max
+ V max
max
T
T
Tn
28 max
I max Fho, S as (0.s)) + V max
In
Since F is convex in 0, we get that for all S and for 0 = Σt=1 a
T F(hg, S aa.
Sla (.9))
(55)
T
Along with linearity of expectation, this gives us that for 0 E e
e-
max 1
B (h S a (6.s))
K
202
S max F(ho, S ap-(e.s)) + V max +
max
(56)
Tn
Finally, we take the minimum over 0 on both sides. Noting that the LHS is independent of 0, we obtain:
e- +
max E F( S Sla (
202
min max F(ho, S $1 (s)(o,))) + V2 max +
max
Tn
202
OPT + V max
max
(57)
Tn
1. Setting 7) / we obtain:
1 T +
1
max max (F S o (..5) OPT +
2
max + 202
(58)
vT
max
OPT +
(59)
Rearranging, we get the statement in the theorem. This completes the proof.
24

---

Under review as a conference paper at ICLR 2023
F AUXILIARY LEMMAS
Proposition 6. functio Q satisfies a-submodularity, i.e. () aQ(k) all k D with S C C. then Q satisfies 7-weak submodularity (El Halabi el al. 2018 Proposition 8, Appendix)
Lemma 7. (Guarantees from Stochastic Distorted Greedy) Let, 9, 2 B&+ be two non-negalive, monotone set functions, such that g is 7--eakly submodularfor some 7 E (0, 1] and is modular (see Definition 7 Furthermore, suppose that for all S, S,c(S)/g(S) & for some K. E 1).
Suppose we wish to solve the following problem:
max
(g() - S9
(60)
for some fixed K. Let S denote the value of set for which the maximum in optimization (60) is attained. Then, for given value of i > O such that ó + e < 1, Stochastic Distorted Greedy Algorithm makes (Dlog(1) (1/6) evaluations of g and returns a set S' of size |S'| S which satisfies,
g(S*) - -(55)= S R Big(S') - c(S'))
(61)
As a corollary, we observe that for all S such that |S] S K, it holds that,
2(S) - (cs) -
k -
(62)
Proof. We begin with the approximation guarantee on Stochastic Distorted Greedy Algorithm as stated in (Harshaw et al., 2019), Theorem 3. (Harshaw et al.) (209)) show that on running Distorted
Greedy with K iterations for optimization problem (60), the output is set S" with size |s'| S K and,
(1 - -1- -))((()) < Elo(S") - c(S)]
(63)
((S*) S E[g(S") - c(S'))
c(S")
(64)
(1-e - - 8)
(1 (1-0-7-0)
- -(5') < Elg(S") c((s))
777
(1 (1-e-7-0) c(5*)
(65)
(1 - --- - 8)
-
(e) - -(()))
g(S*) - -(5)) < (1-6-7-6)
(66)
(1- 8)K
where in the last inequality we use definition of k. Collecting the terms involving g(S") c(S*) on the left, g c(S') on the right and then simplifying gives us the result of the lemma.
Lemma 8. (Derivation of x) Let Gx S) and mx mx(0, (0, S) be as defined in definition and re-
spectively. Let Assumption 7 hold and suppose max R(O) 0 and for all O E θ and let
(maxy Cmin Omax be defined as in Assumption 7 Then, for all 0, VS, it holds that
()
X0 maxx + plaaxx
(67)
(0,
X02 max + pl + pCmin
Proof. We first note that:
(0 S)
XR + (ho(oz)) v.)
(68)
(0,)
(ho((ap(0.s)) AR(O)SS| + Eies ((ha (0.5) (x:)), ) + PEjeD ((ha(z,).
Using the definition of (0,(),)) from Eq. we have, for all & = +b
Σ
2 Σ [((he(a((z:))) vi) (C(as(x.). xx)
S
ES
(69)
25

---

Under review as a conference paper at ICLR 2023
In partieular, this also holds for Φ such that for all a, az(x)) x. This gives,
[e(halas- (x:)): vi) pC(ap- (0,5) (m:;), a.)] 2
[e(ho(a:), ui) (x;;) (70)
iES
Σ (e0holao mi)] N (x;)) vi) + pCCmul] iES
(71)
The last line uses the definition of Cmin from Assumption 1 and the fact that for all æ, C(xx, x) 0.
Plugging inequality (11 back into inequality.
68
wc obtain:
mx(0,S) (0,
XR(O)S + Eies ((o( Wk)
$ AR(O) - Eies [e (z:), Ub) + mCmin + +p +E ((ho(a)).
(72)
AR(O) S + p Eies (2a) Vi)
(73)
AR(O)SI Eies (e( Mo) + pCmin] + + (ho(s)))))
AR(O)|S| + pl SS
(74)
AR(O)SS) - +1Cmin |8| + P >jes ((:)(
AR(O)]S| + plmax|s]
(75)
AR(O)SS 4CCminn |8| plmax| |
XR(0) + pl
(76)
XR(0) + pf +pCmin
Here inequalities 73 and 74 follow from non-negativity of f. Finally, substituting R(0)= < 02 we get the statement in the lemma.
max
Lemma 9. Suppose the assumptions of Lemma S and Theorem 2 hold. Let K == pC (AP
max
plaa + pCmin), where the symbols are the same defined in the statement of Lemma Land ? defined in Theorem 2 Furthermore, let X02 / /unxx- Then for any S such that |S| S b.
(1 e->") and let [Cmiul(e + 8)
(1- + 8)/kk))F( Fl)g) S S/a ( ( E[F(hg, S. a (0, S V max where the expectation w.r.l. the randomness in Stochastic Distorted Greedy.
(77)
Proof. To obtain our guarantees, we require T0 +6 2 0. Substituting K = /CCmia/ AdCmin/(AA22 (A02
max
plmax + jCmiin) ) and simplifying gives p luCmin ((e
-602 / /mmxx To ensure 7 + -00-1111
that the this bound is positive, we require 5 < (1 --)
In our algorithm, we obtain Se by applying Stochastic Distorted Greedy using θ Therefore, by our characterization of F as stated in Eq. (6) and using Lemma 7 we have that for any S,
F(h S1a a 00 ( 1.5)) 5
K
E El 1 3. 3: 13,,)
a0-
(78)
Using the max Lipshhiiscssss of F, we get
|F(h,, S| ((.))) F(ha_,,. S 10 (0.1.)))
S V |maxl10 0. -
(79)
V Vmax"/ /1 Vo. F F(hg. a (0, ..5)
(80)
2 max
(81)
Now, using the Lipschitz condition, from inequality F(hg, S $1as.(0..9)
81 we get that for / and S
S F(hg_.. S|
(0........
+ v V max
(82)
TE
E
((F
Su a 1.),) 2 max
(83)
K c p-
26

---

Under review as a conference paper at ICLR 2023
(1 e +0 F F(hg. S1 ())s)) S B[F(ha,..
$ a (1 (1- 1- +
max
(84)
Here, inequality is obtained by using inequality from both sides of inequality (84, we obtain:
78
Subtracting El Se a (o....)
e- +8 (1- (1-0-x
F F( S ala0 FFFF 3e $ B1))
(85)
K
(1- e- + 1
< <B|F(ha Se S 00)
F(hg. Se a (..3))
max (86)
Using incquality [T we conclude that the above quantity is less than
+ (1- e- +
2 e_ +
V
V max
V max S V
(87)
max
max
This completes the proof of the lemma.
Lemma 10. Suppose Assumption and hold. Let VoF S (0-(0,))) denote the stochastic gradient of at hep S such that IE F S 1 (o)() = Fha (0-(0,))), for all 0, S. Furthermore, suppose that for all 0, S. have, F(e, (0.s) )l I V maxx. For any S. let 0' V (ho, S a. (0.s). Then, for any EE +
1 2n
BhF S a .)) F S (0,s)
(Lm + 1)V max +
10 0|| - - - 01 01210)
2
where the expectation is over the randomness in computing the stochastic gradient Fob S (0,5))
Proof. In what follows, we fix and denote F(he, S (o,(), = F(ho). We do this for brevity and succinctness. Using first L-smoothness and then 0'
0 VoF S (p)(),))) we obtain:
L 110' 01I
F(hor) S F(ho) (VoF(ho)) 0' 0) +
(88)
LAd F(ho)ll
F(ho-) F(ho) < ( A (ho))) +
(89)
2
Taking expectations on both sides over the randomness in computing SGD, we obtain:
Tap²
El F(ho)) 0] - Vo 0 FllloF((ho)1 (90)
2
Tap²
( 01) + E[F((h))) F(ho) - (v.
(91)
2
Ln² 2
Vo
Ell FoF
(92)
Since F is convex in 0, we have:
F(he) F(ha) I (VoF(ho). 0 0)
(93)
Adding the inequality 93 and inequality 922 we obtain:
Lnp
E[F(ho 0
F(hg) < (o + 2
(Voo()))))) 0) (94)
(VoF(ho),
We derive a value for (he)) 0 - 0) using the following:
||0 - 0 = =110' - -0+0 0 0112
(95)
||0' 2 0 0
+
2
0,0 0
(96)
27

---

Under review as a conference paper at ICLR 2023
(l-nvoF(hh)))
+ 110 + (ho), 0 - |0 - 011 - (
(97)
= 17 oF
(98)
Taking expectation on both sides, given 0 (noting that 0 does not depend 0), get
E
|10'
0||2
|00 011 = . F [ 0 2ny (VoF(ho) 0/10
(99)
= (
Vo (ho)), 0 0)
(100)
Rearranging, we obtain:
(VoF(ho), 0 0) = F
B|ll0' - 0| 0 10 011
(101)
2n
Plugging inequality (TOT) back into the inequality
94 we get
B[F(har)) F(hh))
17 (Tn 1) (oF 0) 10- VoFool
|0 0 [||
@|
2
27
! (Ln 1)
max
1
10 10-01 011 Ell 0' 01|3100
(102)
2
21
Lemma 11. Suppose the assumptions of Lemma 10 hold. Furthermore, let θ Se denote the iterates of our algorithm. Then, for any O,
262
Σ [[FF(ha, Se a (.. EhF(hg. Se Selo 1 (...),))]] < V max
max
(103)
Here the expectation is laken w.r.t. the total randomness of the algorithm. randomness in stochastic gradient descent as well as stochastic distorted greedy.
This includes the
Proof. Putting = 0,,0=0 and S,-1, in the statement of Lemma 10 we obtain: that for any E E(F S--1 a (6. (0,))) Flgg. S
(LI) - 1) max +
1
0
0112-E 0112 0
(104)
27
We now take the expectation w.r.t 0, 0 expectation and noting that given 01-1, 0, is independent of 0, for # -- 1, get
0.
Let Our = Ou....,...
0.. Using law of total
I.. [F(hg. S--1le 10 (0..0......))
E
E On.t On.c-1
[F 10.1aa0(00...10 10: .......... 0 0-11
0o.s
0a.e
(105)
E
F( 00.1 0.11]
Onc
Onse
(106)
E
E. 10.0.
[F(hg. So-1 1 (o.. 10 (0.1),)))).
(107)
0o.
Finally, we note that E [F Por iterations cannot impact previous iterations. We finally take the expectation w.r.t the randomness in stochastic distorted greedy as well. Thus, obtain:
3,-1
IE [F(ha 3 I (0.))....,)))) as later
Do.:
28

---

Under review as a conference paper at ICLR 2023
: 3 10.-1la00000000000 (0.00.....))l - -BFF 1 (0.(0.)..1)) B 01 E[ 01:²)
" (1x) 1)V max + 21)
where E now denotes the expectation w.r.f. the randomness in the entire procedure (stochastic gradient descent and stochastic distorted greedy). Using Lipschitzness of F, we get that
| S o (..))
F( S (6. V max 0. 0.-1
F(hō.-, S a -.)-11))))1)) - F(hō, S (0. + V
Plugging this the equation above, we get
Bi S as
F(hg. S (0, 2 (Ln 1)V max +
5 Vn max 2
01 110]-E100--- 0113
21
Setting < 1/L and simplifying gives us the following.
E[F Se (.
B[ a (...))))))
s V max
B1100 0117 - 11100-1 017]
2n
Summing over all gives us a telescoping sum on the right. Simplifying, we obtain:
ElF Se a (0.))))))) - E(F S. - < 2TT +
Bll@0 0113
2n
(108)
We give an upper bound on 00 0 as follows
||0 0| < ||0 + [[01]] < (20max) 402
(109)
max
Substituting upper bound from inequality 1009 in inequality (108) gives us the statement of the
Lemma:
202
E [ Se (e110-((0,3), FEFFF..F Se l (0.(0.))))) < 2 max
max
(110)
F.1 AUXILIARY LEMMAS FOR THEOREM
Lemma 12. (k-SCD guarantee for a fixed S) Suppose Assumption
aadd
hold and F is a non- Ouk) are obtained using
convex function that satisfies the PL condition. Fix S and suppose 0
k-step stochastic gradient descent, for the fixed S, starting from (0)) Then, for any O O have,
4L02 m - n1-
L max
(h S (g)((11))s)) ( (0)) 0(k 0(=-1) F(hg. StagsSSaaapee (l...((0)))
20
where the expectation w.r.f. randomness in computing the stochastic gradient.
Proof. Since fixed, we drop the second argument and denote Fs S as (0,s)) Fs( for succinctness and brevity. For O...., T-smoothhess, we obtain:
........... k- 1, we have, g(++1) = = - V o.n Fs(hor)). Using
L (h(gg))) < (s(hau-))) + (Vor (shgm)) ((k) ((k-1)) + | ( (kk
Taking expectation (given ( (ih-1) 11) on both sides w.r.t. randomness in stochastic gradient descent, we obtain:
29

---

Under review as a conference paper at ICLR 2023
((Fs(how) | 0(h-1)) & Fs(hou-n) - Vin-1 Fs (o
Fs(hhcc-u)) (111)
L1j +
Blll g(. Fs (hhoc)))
(112)
2
Lnd²
Fs(hgu-n) 7/l V Fs
V
(113)
2
max
The PL condition implies that,
|| oV Fis---F(((h 2 ((Fs((ou-))) Fs (høg)]
(114)
where 03- ming F(hgr, S al (0r,s)) Substituting this in the inequality (113 we obtain:
Laf 2
E ((s(g)))) [(k-1)1 - Fs(hgu-)) - no [Fs - Fs(hoa))
(115)
2
Subtracting (s(ho from both sides and simplifying gives us,
Lifa
(hgr() (x-11)1- (he(o))) s (Fshgh(( Fs(ho;))
max
(116)
2
Now, we take expectation given (*- and get,
((Fs(hag)) 0(k-11 ( Fs(
2 max
$ (1 - no [B[Fs ( 1)) (0)k -Fs(ke;))) )
(117)
2
Note that E[Fs (hFu)) @(k-1) 2)k-2)] = (h [@(k- because @(k), is conditionally in- dependent of ((k-2) when ((k- is given. Moreover, the term E[F's (hout-))) 0(k-2)j F's(hog) can be simplified the same manner as above get,
L1j max
E[F's (hote-))) 10tk-2) Fsogg S [1-no)][[[ss(() -
(118)
Let ((0):(T) denote ((0) ..... .(+) Then, repeating the above procedure and simplifying yields,
Eguxa- 1) (sshhoe-))) (s
Laj²
V2
k
$ (1 -1- not B (h - Fs(hog)
max
Σ (1 - n))
(119)
2
Ln 2
< (1 nor " (F - Es(hog)) )1
+
max
(120)
2
1)0
)
V
Voi (s((h )1
max
(121)
20
L(1 )²)
V
110(0) 03
max
(122)
2a
4T.02 max (1
n
Va
max
(123)
σ
2x
where, in inequality 121 we have used the PL condition and in inequality (122) we have used the fact that o (s gradients).
V (s(ho)))) Vo, Fs(ho))) Il [ 0 (using Lipschitz
Finally, we note that by the definition of 03. ()( Ps(hoz). Thus, we replace (s(h)) by Fs (hoz) in the LHS to get the statement of the lemma. This completes the proof of the lemma. [
30

---

Under review as a conference paper at ICLR 2023
Lemma 13. (K-SGD guarantee) Suppose Assumption aand AssumptionnandDhollle and F is non-convex non-convexfuncttoon that satisfies the PL condition. Let 0₂, St denote the iterates of algorithm and suppose method k-SGD is used. Then, for any 0 E 6
E S a 1
)1 (h Se-1 (0-(0...
4LO 4L0 no)
L
S 2kn max
(124)
0 where the expectation is taken w.rl. the total randomness of the algorithm (stochustic gradient descent and stochastic distorted greedy).
2a
Proof. In our algorithm with method k-SCD 0, derived from 0 using i steps of SGD
with fixed set S,-1. In this case, 0,-1 = 0(0), 0, O(k), 5 = S.- and 0(1) , ((=-1), denote
the intermediate k-SGD iterates. In this case, Lemma 12 holds and obtain:
B[F(hg, S (s-(0.....)) 10-1,,00) 0())
1 01 F St_1 (0,
4T02 max (1 1100**
L
mAx
(125)
2a
Taking total expectation on both sides, w.r.t ((1), g(...... (k--1), 1), using law total expectation and observing that the other terms in the equation independent of these random variables, we obtain:
4T62 max (1
no)*
Lay V
(( S.-1 (0.3. .)) 010-1] F S--1 a (0-11a0-00..-11) (0-(0....))
max
2x
(126)
Using Lipschitzness of F from Assumption 1 we obtain:
, ".0 (0.10 1.) F(hg, S 1 1)
S V max 0 0,- 0.1
= max 0z- ((1) + +0) ( 0.1l
- 2km max
(127)
Adding and subtracting
(th,,,,.3111 00.01.3.. ..3))))
from inequality (26 gives us,
F(hg_,, a (0. ( Fh S--1 a (0.(0.....)
I F(ha (ho S 0 (0. - FFFF(hg F - 10 1.......1)) 0001
4L02 max (1 ) +
L max
+
20
Now, using inequality F(hg.,,, S.-1 ass (0.........))) Flg 3 a (
127 we obtain:
4L02 max no)*
L Max
< 2kv V max
max
(128)
o Finally, taking expectation w.r.t. the total randomness of the algorithm (stochastic gradient descent and stochastic distorted greedy), we obtain:
2a
BiF(ha_,,, S--1 u 10 (.,,)))_)))))
-BFF((h S.m1 I (..(0.8...)))
4T.02 max
no)*
L
< 2kn max
+
+
max 20
(129)
Lemma 14. Suppose the assumptions of Lemma & and Theorem holdd Let 50Cmin//////
(202
max
plaax + pCmon)) where the symbols are the same as defined the statement of Lemma & and 7 defined in Theorem 2
e-
1
F( S Sl00 (0.))) B[ St Sela (. S V max
(130)
K
31

---

Under review as a conference paper at ICLR 2023
where the expectation is w.E.. the randomness in Stochastic Distorted Greedy.
Proof. To obtain our guarantees, we require (1 e- +6 2 0. Substituting K = /Cmiu// (A0tl//Ammmm max
plmax + pCmin)) and simplifying gives p |uC ((E 7 +6)
-1) 1) 10 20 m/ //xx- To ensure
that the this bound is positive, require d < e->)
In our algorithm, we obtain S, by applying Stochastic Distorted Greedy using 0.-1. 1. Therefore, by our characterization of F as stated in Eq. (6) and using Lemma] 7 we have that for any S,
F F(h Sla (0-(0-1.))) S
El 0 Se . 00
(131)
Since O, is derived from 0,_1 using method SGG, we cannot use Lipschitzness directly. Instead, we use inequality 127 Doing so, we get that for all t, S,
F(ha. S $1000 (0.))
S F F(ha. S a0 (..)) + 2km max
(132)
<
R e- B[F(ha St "0 V
k
(133)
max
(1 1-
e- (1=-7+ +6) F F(ha.> S (
S FF S, (0.00_1))))) (1 e_ +0
2k
V
max
(134)
where in inequality (33) we use inequality 131 Subtracting E[F Se (a/apr (o.. from both sides, we obtain:
F F( 51 $1a0-(0.99) 18 E 3e Selas- (0.
K
s B[ 3e (0.))))))))) - F(ha. S. (0 (1- -- + 2kg V2
max
(135)
Using Lipschitzness of F' from Assumption ! we obtain:
| Fh 1 (0.(0...
F F(hg. S 4 S,
- max 1 02-1 0.1
V max 0,- ((1) + (
(k--1) -0.1l
2km 2 max
(136)
We use inequality (136
into the inequality 135 to have:
e
F(hō. S $100-(0..5) - B(F(hh, Se aas (0..)))
2 max (1 (1- e- +0
2km)
2km 22 max
-(2 x +
2hm V2 max
k
< V2 max
(137)
32

---

Under review as a conference paper at ICLR 2023
G ADDITIONAL DETAILS ABOUT THE EXPERIMENTAL SETUP
G.1 DATASET SPLIT INTO TRAIN, VALIDATION AND TEST
We split the datasets into training, validation, and test set in the ratio of 4:1:1, 5:1:1 and 4:1:1 for CIFARIO, FMNIST and CIFAR 100 respectively. For CIFARIO, 10, we use 40000 training examples, 10000 validation examples and 10000 test examples. For Fashion MNIST, we use 50000 training examples, 10000 validation examples, and 10000 test examples. For CIFARIOO, we use 40000 training examples, 10000 validation examples and 10000 test examples. The same train, validation and test split it used for the baselines as well. In all cases, unless otherwise mentioned, we consider |S| S 0.1|2] during training. Similarly, during test we use 10% test instances for attack. The exact nature of drawing this 10% test instances varies across experiments and is mentioned therein.
G.2 DETAILS ABOUT THE BASELINES
In all baselines, we used ResNet18 architecture for CIFARIO and ResNet9 for CIFARI00, with the last layers having 10 and 100 neurons respectively. For FMNIST, we use LeNet architecture. For all the methods (including ours) which use PGD attack during training, we keep the PGD attack parameters to be the same as ROGET (as = PGD) (details in the following subsection). Similar to p in our method, GAT, TRADES, Nu-AT and, MART also offer specific hyperparameters which can control the tradeoff between Aclean and Ayobust- For all methods (including Ours), we use PGD attack the assumed adversarial perturbation method during hyperparameter selection on the validation set.
GAT (Sriramanan et al., 2020). We used the code from the official repository They provide two different codebases for CIFAR10 10 and MNIST. We used their MNIST code for experiments with FMNIST dataset. For default hyperparameter selection (Table D we refer the official repository in which they provide the value of 2_reg- = 10 for CIFAR10 and 12_reg 15 for MNIST (which we use for FMNIST). For worst-case hyperparameter selection (Table [2). we train GAT on a range of 12_reg values: 12.5, 5.0, 10.0. 15.0, 20.0, 30.0) for CIFARIO 10 and FMNIST, and {2.0, 5.0, 10.0, 20.0, 30.0} for CIFAR 100. In their official code, they train GAT for 100 epochs on CIFAR 10 and for 50 epochs on MNIST. Hence we train GAT for 100, 50 and 100 epochs CIFARIO, FMNIST and CIFAR100 respectively.
FBF WWogg et al. 2019). For CIFARIO used the code from the official repository For FMNIST and CIFARIOO, we implemented their code parallel to CIFARIO. The only changes (other than the architecture) were the mean and standard deviation that we computed for FMNIST and CIFARIO0 100 separately. FBF does not have any tunable parameter and hence it does not undergo any hyperparameter selection. For CIFARIO and CIFAR 100, we train FBF for 80 epochs (as used in the official code for CIFARIO). For FMNIST, we train FBF for 10 epochs (as used in the official code for MNIST).
TRADES Zhang et al. 2019b). We used the code from the official repository They provide two different codebases for CIFARIO and MNIST. We used their MNIST code for experiments with FMNIST dataset. For default hyperparameter selection (Table 1.. we refer to the official repository (6] in which they use 3 = 6.0 for CI and 1.0 for MNIST (which we use for FMNIST). For worst-case hyperparameter selection (Table 2). we train TRADES on a range of 3 values: (0.1, 0.2. 0.4, 0.6, 0.8, 2.0, 4.0, 6.0) for CIFARIO, 10, {0.4, 0.6, 0.8, 1.0, 2.0, 4.0, 6.0) for FMNIST, and ( (1.0, 2.0, 4.0, 6.0, 8.0) for CIFARI00 Optimizer, batch size and learning rate are same as those used in the official repository. We train TRADES for 120, 100, and 120 epochs on CIFAR1O, FMNIST and, CIFAR 100 respectively.
5
We collect the datasets from http::/wwww.cstoorooo.ooo edu/ kriz/cifar.html (CIFAR-10), and http:://ghhbb.ccm//aiiii//AAAAAa
(FMNIST).
33

---

Under review as a conference paper at ICLR 2023
Nu-AT (Sriamaanan et al. 2021). We used the code from the official repository | code for CIFARIO hence for running it on FMNIST, we modify the PGD parameters to the one we used in FMNIST and the number of epochs to 100. For default hyperparameter selection (Table I we refer to the supplementary material of Nu-AT, in which the authors mention that "We use a Amaz of 4.5 for CIFAR- 10 on ResNet-18 architecture and 4 for WideResNet-344
They only provide
For MNIST use Amaz of I...". Hence we use Amaa=4.5 for CIFAR 10 and Amaz=1.0 for FMNIST. For worst-case hyperparameter selection (Table 2) we train Nu-AT on a range of Xmaz values: {2.0, 2.5, 3.0, 3.5, 4.0, 4.5, 5.0) for CIFAR 10 and FMNIST, and {1.0, 2.0, 4.5, 6.0, 8.0] for CIFAR100. Optimizer, batch size and learning rate are same as those used in the official repository. We train Nu-AT for 120, 100, and 120 epochs on CIFARIO, FMNIST and, CIFAR 100 respectively.
MART Wang et al., 2019). We used the code from the official repository They only provide code for CIFARTO hence for running it on FMNIST, we modify the PGD parameters and the number of epochs. For default hyperparameter selection (Table 1. we refer to the official repository
i in which they use 3 = 5.0 for CIFARIO. 10. We were not able to find any mention of their hyperparameter values for MNIST either in their paper or their code. Hence using Figure 2(d) of their paper as reference, we trained MART on FMNIST for 3 = (0.5, 1.0, 2.5, 5.0, 7.5, 10.0) and found that only / = 1.0 undergone effective training and gave Actean above 50%. Hence we chose 3 = 1.0 as the default value for FMNIST. For worst-case hyperparameter selection (Table 2) we train MART on range of 3 values: (0.5, 1.0, 2.5, 5.0, 7.5, 10.0) for CIFAR 10 and FMNIST, and (0.5, 1.0, 2.5, 5.0, 10.0) for CIFARI00. We train MART for 120, 100, and 120 epochs on CIFARIO. FMNIST and, CIFARI00 respectively.
PGD-AT (Madry et al. 2017). We could not find any official Pytorch implementation for PGD-AT. Therefore, we implemented it ourselves using the architecture mentioned above, for each dataset. We use SGD optimizer along with batch size of 128 was used for both datasets. For FMNIST, initial learning rate 0.01 and momentum 0.9 was used. For CIFARIO and CIFAR100, we use initial learning rate of 0.1 and momentum 0.9. PGD-AT has no tunable parameter and hence undergoes no hyperparameter selection. We train PGD-AT for 100 epochs on all three datasets.
RFGSM-AT (Tramer et al., 2018). We could not find any official Pytorch implementation for RFGSM-AT. Therefore, we implemented it ourselves using the architecture mentioned above, for each dataset. RFGSM-AT also does not have any tunable parameter that controls the tradeoff between Arobust and Aelean but it has parameter a which does affect its robust accuracy to a significant extent. We refer to their paper in which they use a = =/2 for ImageNet and MNIST. Hence, for default hyperparameter selection (Table T) we use a = e/2 for CIFARIO and FMNIST. This value however gives very low robust accuracy for all the attacks. Hence for worst-case hyperparameter selection (Table p. we tune a such that achieves Arobust above 40% PGD attack which gives us the value of a = 0.05e. Optimizer, batch size and learning rate are same as those used in the official repository. We use SGD optimizer along with batch size of 128 was used for both datasets. For FMNIST, initial learning rate 0.01 and momentum 0.9 was used. For CIFAR10 10 and CIFAR I 100, we use initial learning rate of 0.1 and momentum 0.9. We train REGSM-AT for 100 epochs on all three datasets.
G.3 IMPLEMENTATION DETAILS OF OUR METHON
Hy Hyperparameters of our method. For default hyperparameter selection (Table [ simply use
= for all the datasets. For worst-case hyperparameter selection (Table 2 we train ROGET (ap PGD) on range of p values: (0.01, 0.05, 0.5. 1.0, 2.0, 5.0, 8.0, 10.0) for CIFAR10, (0.01,
0.1. 0.5, 1.0, 1.5, 2.0, 4.0, 8.0} for FMNIST, and [2.0. 5.0, 10.0, 20.0, 30.0) for CIFAR100. For ROGET (a. AdvGAN), we train for P values: (0.01, 0.25, 0.5, 1.0, 1.5, 2.0) for CIFARIO, (0.001, 0.005, 0.01, 0. 0.5, 1.0, 1.5, 2.0] for FMNIST and (0.005, 0.01, 0.25, 0.5, 1.0) for CIFAR100. Batch size was set to 128 in all the datasets. We use k-SGD to train our method. Moreover, we use early stopping as follows. While running multiple training epochs for fixed S we use early stopping to determine when to stop. In SGDGD, we stop training for the current S if on the validation set, the attacked set accuracy, Arohust, drops.
https://ggituub.oo/aaaisssssssss $ "https//githuu.com// www..//wwwww..w.//m/....... 9 http:///gggiuiccoo////////naaa//
34

---

Under review as a conference paper at ICLR 2023
Details about ag. For ROGET (ag PGD), set 0.031, number of steps 20 and step size = 0.007 for CIFARIO and CIFARIO0 while for FMNIST, we use = 0.3, number of steps = 40 and step size 0.01.
For ROGET (aæ = AdvGAN), we used the Pytorch implementation available in an online reposi- tory 10 The same architecture was used for all the datasets with only changes to the number of input channels. No changes to the generator discriminator architecture were made besides the number of input channels which was set to 1 for FMNIST and for CIFARIO 10 and CIFARI00. At the end of every iteration, retrain AdvGAN on set S output by stochastic distorted greedy algorithm, for 15 epochs. Retraining AdvGAN every time we add a point to the set S in stochastic distorted greedy (SDG) algorithm increases the running time of SDG to such an extent that becomes infeasible. For this reason, we instead choose to retrain AdvGAN after SDG outputs a set S, for the current iteration. This is equivalent to fine-tuning AdvGAN attack the set S, output by SDG.
G.4 DETAILS ABOUT ADVERSARIAL PERTURBATION
For PGD attack, we used same specifications used to train ROGET (0g = PGD). More specifically, we set c = 0.031, number of steps 20 and step size 0.007 for CIFAR10 and CIFAR while for FMNIST, we use = 0.3, number of steps 40 and step size 0.01. For Auto Attack, we use the standard version which consists of untargeted APGD-CE, targeted APGD-DLR, targeted FAB and Square attacks each with the default parameters. For square attack. set number of queries to 1000 and e same as that for PGD attack above. For applying MI-FGSM in black box setting, we take source model trained on the chosen dataset, get the perturbed sample by computing gradients using the source model and then test the method on this obtained perturbed sample. Transfer based black box attacks weaker than white-box attacks. Hence we set the parameters of MI-FGSM to be stronger than those for PGD attack. We set e = 0.2, number of steps 60, step size 0.007 for CIFARIO and CIFAR 100 and 0.305, number of steps 80, step size 0.01 for FMNIST. For Square attack, we use loo norm with e = 0.031 for CIFAR10 and e = 0.3 for FMNIST.
G.5 INFRASTRUCTURE DETAILS
We implement ROGET using Python 3.8 and PyTorch 1.10.1. The experiments were run on servers equipped with 2.9GHz CPUs, NVIDIA Quadro (48GB), NVIDIA RTX A6000 (48 GB), NVIDIA A40 (46 GB), NVIDIA Quadro RTX 8000 (49 GB) and NVIDIA TITAN RTX (24 GB) GPUs.
G.6 LICENSE
We collect the datasets from https://wwww.c..orrontt wttps//wwwooooo.o..oooiiiaaaaaaa (CIFARIO and CI- FAR100), and These sources allow the use of datasets for research purposes. Furthermore, use the following publicly available repositories- (GAT), http://ggghub..coo/oo/esaat aaaasaaabaaastaadeessraiaall (FBF), https///gthubbommmyyyooogg/////u (TRADES),
(Fashion-MNIST),
http://ggiubb..oomalllii//AAA.A
httpgghwww..ooooaallss/A/AATTTT (Nu-AT), https//githubbcomm/iiiaaaaaaaaa
(MART) to implement the baselines, https://gttuu..com// http:////w....acccaaaaaaa.a implement AdyGAN, and http://submoddibb.aadttheeee htwp:/hhhwooccoooo/meeeeeeeeeeee hoteelaatsttuucctooo//iiillillaa html solve the Facility Location problem in one of our additional experiments mentioned in section
(AdvGAN) to
H
below.
35

---

Under review as a conference paper at ICLR 2023
H ADDITIONAL EXPERIMENTS
H.1 RESULTS ON LOSS BASED HYPERPARAMETER SELECTION TECHNIQUE ON CIFARTE 10 AND FMNIST
We also explore another hyperparameter selection technique in which the learner assumes subset selection strategy of the adversary. More specifically. the learner assumes a distribution across validation samples which is inversely proportional to the loss of classifier trained on clean samples. Based on this strategy an attack simulated on validation set and the hyperparameter giving the best overall accuracy is selected. We present the results for CIFARIO and FMNIST in Table For CIFARIO, we observe that our method achieves the highest overall accuracy for all attacks. For FMNIST, TRADES has better overall accuracy AA and Square attack by small margin.
CIFARTO
PCD
AA
Square
MIFGSM
AdvGAN
Ackan
Acotost
Arabuss
Arobust
Arolust
Avobustt
GAT
77.55
63.26
76.12
49.73
74.77
60.07
75.80
52.91
75.09
81.07
77.91
FBF
74.92
72.04
74.64
31.10
70.54
31.59
70.39
36.09
71.04
37.22
71.15
TRADES
83.63
42.55
58.60
81.13
80.07
Nu-AT
84,66
54,64
81.66
45.79
80.77
61.34
82.33
47.41
80.93
88.18
85.01
MART
80.49
61.30
78.57
49.32
77.37
61.26
78.57
51.13
77.56
84.25
80.87
PGD-AT
83.36
57.33
80.76
48.50
81.30
50.00
80.03
83.74
REGSM-AT
85.84
45.94
81.85
37.49
81.00
60.25
83.28
37.91
81.04
89.42
86,20
ROGET (PGD)
86.63
31.16
83.09
43.06
82.28
62.33
84.20
42.20
82.19
90.15
86.99
ROGET (AdvGAN)
39.97
83.07
85.29
91.53
88.22
FMNIST
PGD
Square
MIFGSM
AdvGAN
Aclenn
Arabus
Arobust
AA
AA
Avobrutt
GAT
91.47
3.18
82.64
0.00
82.32
0.01
82.32
8.32
83.15
29.09
85.24
FBF
80.47
14.29
73.85
66.74
79.10
68.43
79.27
84.81
80.90
85.94
81.02
TRADES
86.85
62.90
84.45
53,37
83.50
57.37
83.90
81.43
86,30
70.42
85,20
Nu-AT
90.21
5.11
81.70
0.00
81.19
0.11
81.20
19.77
83.17
11.35
82.32
MART
78.94
77.72
78.82
59.73
77.02
61.46
77.19
79.03
70.10
78.06
PGD-AT AT
83.77
79.62
K3.36
53.62
80.76
57.05
81.10
83.73
83.77
72.88
82.69
REGSM-AT
89.46
13.49
0.00
80.51
80.51
24.88
83.00
21.85
82.70
ROGET (PGD)
87.01
63.24
84.63
49.63
83.27
54.29
83.74
86.40
69.16
85.22
ROGET (AdvGAN)
87.08
49.62
83.33
47.32
83.10
51.99
83.57
82.49
86.62
73.44
85.71
Table 7: Performance comparison under Loss based hyperparameter selection. Here, the adversary adopts uncertainty based subset selection to perform attack, where the true subset chosen for attack Glatent consists of top 10% test instances in terms of the uncertainty of classifier trained on all the clean examples. Numbers in green (yellow) indicate the best (second best) performers.
36

---

Under review as a conference paper at ICLR 2023
H.2 EVALUATION ON LABEL BASED SUBSET SELECTION STRATEGY
We present the complete set of results for label based subset selection strategy on CIFARIO in Table 8 aand Note that we use the worst case hyperparameter setting for all the methods. We observe that our method achieves the highest overall accuracy for all classes and for all attacks.
PGD
Airplane
Automobile
Cat
Deer
Dog
Frog
Horse
Ship
Truck
GAT
76.37
76.17
76.71
76.36
75.46
76.69
75.48
76.18
75.71
76.19
FBF
74.43
74,66
74.59
74.96
74.54
74.51
74.40
74.91
74.48
74,64
TRADES
80,92
81.30
80.25
80.06
78.85
81.12
79.45
81.03
80.44
81.04
Nu-AT
82.12
82.63
81.50
80.96
80.22
81.94
80.71
82.36
81.61
82.36
MART
78.49
79.02
78.68
78.45
78.15
78.91
78.09
78.99
77.96
78.73
PGI-AT
81.11
81.53
80.53
80.88
79.17
80..8
80.
81.03
80.97
81.03
REGSM-AT
82.45
83.19
81.72
81.63
80.48
82.08
80.39
82.31
82.06
82.33
ROGET
PGD)
83.76
84,68
82.94
82.84
80.73
83.63
81.38
83,53
83.16
84.23
ROGET (ap AdvGAN)
84.98
86.02
83.41
83.70
81.32
84.30
82.01
84.40
83.86
84.87
AA
Airplane
Automobile
Bird
Cat
Deer
Dog
Frog
Horse
Ship
Truck
GAT
75.19
75.41
74.76
73.76
72.92
75.116
74,20
75.21
74.85
75.28
FBF
72.39
66.43
74.21
71.38
72.71
71.77
68.54
69.59
73.29
67.11
TRADES
80.17
80.79
78.75
78.31
77.47
79.52
78.41
80.14
79.94
80.44
Nu-AT
81.32
82.06
79.97
79.36
78.76
80.54
79.71
81.62
81.00
81.68
MART
77.69
78.43
76.31
75.57
77.34
76.85
78.01
77.17
78.02
PGD-AT
80.38
80.89
79.15
79.08
77.83
79.60
79.15
80.31
80.28
80.45
REGSM-AT
81.80
82.58
80.37
80.08
79.19
80.84
79.54
81.53
81.42
81.46
ROGET (og PGD)
82.97
84.19
81.07
79.73
82.05
80.67
82.79
82.49
ROGET (ne AdvGAN)
84,24
85.63
82.01
81.96
80.45
82,93
81.14
83.71
83.19
84,03
Table A on label based subset selection strategy on CIFARIO under white box (PGD, AA) attacks. Here, the attacked subset selection is based the uncertainty of vanilla classifier (h,) the test samples. For all the methods, we perform worst-case hyperparameter selection.
Square Deer
Airlane
Automobile
Bird
Cat
Dog
Frog
Horse
Ship
Truck
GAT
76.06
76.39
75.42
74.80
74.15
75.9%
75.48
76.20
75.98
76.27
FBF
72.44
66.44
71.44
72.75
71.80
68.59
69.65
73.35
67.12
TRADES
81.39
82.23
80.26
79.44
79.16
80.90
80.60
81.70
81.65
82.05
Nu-AT
82.78
83.28
81.52
80.63
80.31
81 21.83
81.67
83.06
82.81
83.23
MART
78.40
79.10
PGD-AT
81.57
82.02
80.39
80.01
79.62
80.90
81.04
81.71
81.79
81.86
REGSM-AT
83.49
84.39
82.15
81.74
81.64
82.59
83.07
83.51
83.95
83.90
ROGET (og PGD)
84.42
85.57
83.14
82.55
81.96
83.51
83.47
84.67
84.77
85.47
ROGET (a. AdvGAN)
85.92
87.01
83.88
83.61
82.96
84,70
84.00
85.95
85.79
86.33
MIFGSM
Airplane
Automobile
Bird
Deer
Dog
Frog
Horse
Ship
Truck
GAT
74.43
74.64
75.33
74.58
73.03
75.40
77.23
75.76
74.23
76.42
FBF
72.65
66.42
76.14
71.73
74.71
71.92
68.81
69.81
73.52
67.10
TRADES
78.63
Nu-AT
80.19
80.56
80.91
79.74
79.67
80.62
83.33
82.36
79.25
82.75
MART
76.98
77.26
77.35
76.94
76.23
77.40
80.54
78.29
75.78
78.98
PGI-AT
79.90
78.80
78.69
REGSM-AT
80.35
80.58
81,72
80.60
79.79
79.99
84.34
81.72
80.28
81.74
ROGET tog PGD)
81.27
82.37
82.36
81.42
80.35
80.97
85.20
83.04
81.20
83.88
ROGET (a. AdvGAN)
82.53
83.57
83.58
82.21
80.93
81.87
85.59
84.31
Table 9: A on label based subset selection strategy on CIFAR10 under black box (Square, MIFGSM) attacks. Here, the attacked subset selection based on uncertainty of vanilla classifier (h,,) on the test samples. For all the methods, we perform worst-case hyperparameter selection.
37

---

Under review as a conference paper at ICLR 2023
H.3 DISCLOSING THE SUBSET SELECTION STRATEGY TO THE BASELINES
In this experiment, we reveal the advsersary's 's subset selection strategy (uncertainty based) to the baselines during hyperparameter selection. We select the hyperparameter of the baseline which has the best overall accuracy on the validation set using the revealed subset selection strategy. The results are presented in Table IO Comparing with results Table 2 we see that GAT, TRADES, Nu-AT and MART have improved Le., all the baselines which had tunable hyperparameter have become better, More importantly, our method still achieves the best overall accuracy across all attacks except PGD.
CIFARIO
PGD
Square
MIFGSM
AdvGAN
Agtean
Arooouat
Archust
Avalust AA
Arouunt
GAT
86.18
35.68
81.13
11.80
78.
48.92
82.45
38.47
81.41
89,66
86.52
FBF
74.92
72.04
74.64
31.10
70.54
31.59
70.59
36.09
71.04
37.22
71.15
TRADES
84.70
50.98
81.33
39.58
80.19
60.29
82.26
41.97
80.43
88.27
85.06
Nu-AT
87.88
47.54
83.85
18.87
80.98
53.01
84.40
39.15
83.01
91.28
88.22
MART
82.12
60.29
79.94
48.73
78.78
61.92
80.10
51.21
79.03
85,42
82.46
PGD-AT
83.36
57.33
80.76
48.50
79.
62.71
81.30
50.00
80.03
87.13
83.74
REGSM-AT
85.84
45.94
81.85
37.49
81.00
60.25
83.28
37.91
81.04
89.42
86.20
87.40
42.14
62.45
84,91
41.53
82.82
ROGET (AdvGAN)
88.23
44.24
83.83
36.48
83.05
61.01
85.51
37.42
83.15
91.96
88.60
Table 10: Performance under revealed hyperparameter selection, where for the basclines, select the hyperparameters which would maximize the overall accuracy using the adversary's 's true subset selection strategy (uncertainty based). Numbers in green (yellow) indicate the best (second best) performers.
H.4 WORST CASE OVERALL ACCURACY
In this experiment choose R- 10000 subsets { uniformly at random from Drest and report the minimum A along with the corresponding Actean and Arohust. We use default hyperparameter selection and report the results for CIFARIO and FMNIST in Table IT] We make the following observations: (1) method achieves the best min A for PGD, AA, and MIFGSM attacks CIFAR 10 and PGD, Square and MIFGSM attacks on FMNIST. (2) There is no clear winner among the baselines. RFGSM-AT has good A on CIFAR10 but poor Arobust- For FMNIST, GAT achieves
the highest A for AA. However it is purely because of its Aclean as it has 0% Arobust-
CIFARTO
PGD
AA
Square
MIRGSM
Asies
Arobast
Azhenn
Auolust
Actes
Arotust
Astam
.Acoburt
GAT
78.96
50.60
76.12
78.56
38.70
74.93
78.96
51.70
76.23
78.95
42.90
75.37
FBF
75.02
65.50
74.10
75.18
25.20
70.16
75.18
25.70
70.23
75.09
30.70
70.65
77.94
Nu-AT
83
49.
79. 90
83.49
37.20
78.85
83.36
$3.30
80.35
83.40
42.60
79.32
MART
81.58
54,90
73.91
81.57
42,50
77.66
81.57
54.90
78.90
81.47
46.80
78.00
PGD-AT
47.70
80.58
RFGSM-AT
89.19
26.70
82.94
89.39
18.10
82.26
89.
48.00
85.07
89.14
18:70
82 10
(0, PGD)
47.30
ROGET (0g Ad+GAN)
88.12
39.40
83.25
88.09
31.40
82.42
88.37
49.20
84.45
87.98
33.30
82.51
FMINIST
PGD
AA
Square
MIPGSM
Avteum
Apdbast
Aetrus
Andust
min
Aghuu
Auobust
GAT
91.54
3.30
82.72
91.54
0.000
91.55
0.00
82.39
91.57
3.50
82.77
FBF
80.68
13.60
73.97
80.97
52.70
78.14
80.97
511.0
78.29
80.73
75.60
80.22
Nu-AT
90.56
4,20
81.92
90.52
0.00
81.47
90.54
0.00
81.49
90.74
10.50
82.72
MART
79.63
65.70
75.24
79.48
47.30
76.26
79.48
48.80
76.41
79.71
68.00
78.54
PGD-AT
84.17
63
84.32
80
79.67
84.32
41.50
80.04
84.39
73.20
RFGSM-AT
89.33
9.80
81.35
89.24
0.00
80.32
89.24
0.00
$0.32
89.34
20.70
82.48
(0L PGD)
87
83.48
RoGET(e, (eg Ad+GAN)
88.06
26.90
81.94
88.30
23.10
81.78
88.23
29.20
82.33
88.38
68.20
86.36
Table 11: Min A across R = 10000 random subsets along with the corresponding Aelean and Arobust for CIFAR and FMNIST, For all the methods, we use default hyperparameter selection.
38

---

Under review as a conference paper at ICLR 2023
H.5 TRADE OFF BETWEEN Aclean AND Arobust
In this experiment, we evaluate various hyperparameters of the baselines and plot their Aclean vs Arobust in Table 12 and 13 Each point on the plot represents hyperparameter of the method. Here the adversary uses uncerfainty based subset selection where the true subset chosen for attack Slatent consists of top 10% test instances in terms of the uncertainty of classifier trained on all the clean examples. We observe that our method forms a pareto optimal front for all the attacks and hence achieves better trade off between Aclean and Arobust- We also notice that the baselines do not follow regular trend and show high sensitivity with their tunable parameter. In that aspect, our method is relatively stable with respect to p.
ROGEr (AdvGAN)
ROGET (PGD)
PGD-AT
MART
Ni-AT
TRADES
GAT
1
clean
clean
35
40
60
60
85
40
robust
robust (a) AA
(a) PGD
Figure 12: Trade off between Aelean Arobust for all methods for whitebox attacks (PGD, AA) on CIFARIO. Here, the adversary adopts uncertainty based subset selection to perform attack, where the true subset chosen for attack glatent consists of top 10% test instances in terms of the uncertainty of classifier trained on all the clean examples.
ROGEE (AdvGAN)
ROGET (PGD)
PGD-AT
MART
Nu-AT
TRADES
GAT
clean
clean
40
Arouust
Arobust
(a) Square
(a) MIFGSM
Figure 13: Trade off between Aclean vs Arobust for all methods for blackbox attacks (Square,
MIFGSM) on CIFARIO. Here, the adversary adopts uncertainty based subset selection to perform attack, where the true subset chosen for attack glatent consists of top 10% test instances terms of the uncertainty of classifier trained on all the clean examples.
39

---

Under review as a conference paper at ICLR 2023
6.6 VARIATION OF Arobust, Aclean AND A VS p
On CIFARIO dataset, we try out different values of for two variants of our methods, ie., ROGET (ag PGD) and ROGET (a, AdvGAN). We probe the variation of Aclean Arohust and A vs for two attacks- AA (standard) and black-box MI-FGSM. The plot for ROGET (ag = PGD) is shown in Figure 14 For each value of p. we test using 5 random attack-clean (1:9) splits on the test set and report the mean accuracy with standard deviation. The plot for ROGET (ag = AdvGAN) is shown Figure 15| We make the following observations: (1) For white box attack (AA), the standard deviation from the mean is 1.07% across all values of and across all models. In case of black box MI-FGSM attack, the standard deviation rises to 3..3%%. (2) For ROGET (ag = PGD), Arobust. accuracy decreases as p increases (except p 8). (3) For ROGET (as AdvGAN), we observe that Arobust rises slightly before decreasing as p increases.
Assss
Astua
Asaa
A
70
60
60
50
40
P
P-
(a) AA
(b) MI-FGSM
Figure 14: Variation of Arobust, Arlean and A vs p of ROGET (ap PGD) CIFAR10 dataset for two attacks viz, Auto Attack and MI-FGSM. For each value of p. test using uncertainty based subset selection and report the mean accuracy with standard deviation. We show the mean of Arobust. Acleau and A, along with enror bars show the standard deviation.
Adan
A
A
70
70
60
60
50
50
40
p
p->
(a) AA
(b) MI-FGSM
Figure 15: Variation of Arobusts Aelean and A vs p of ROGET (ap AdvGAN) CIFAR10 dataset for attacks viz., Auto Attack and MI-FGSM. For each value p. we using uncertainty based subset selection and report the mean accuracy with standard deviation. We show the mean of Arobust Aclean and A, along with error bars show the standard deviation
40

---

Under review as a conference paper at ICLR 2023
H.7 RUN-TIME AND MEMORY ANALYSIS
In this section, we present details about the training time and the maximum GPU memory required for all methods while training CIFARIO. Note that the time mentioned for our method includes both, the time taken for gradient step and a stochastic greedy step. Here, the size of the attacked subset was |S| 0.1|D]. where D denotes the training set. The results are presented Table 16
CIFARIO
Time Time@SXepoch
Memory (GB)
GAT
86.80
2.0
FBF
87.36
2.7
TRADES
578.61
4.0
Nu-AT
74.29
3,2
MART
284.52
2.8
PGD-AT
290.18
2.7
RFGSM-AT
39.07
2.7
ROGET (PGD)
479.05
5.1
(AdvGAN)
Table 16: Run-time and memory analysis for all the methods on CIFARIO.
H.8 ATTACK ON THE MOST VULNERABLE SET
In this experiment, we take the final set Sr from our algorithm for CIFAR-10 and find b 0.1 D number of samples with highest loss. Then, we compute the corresponding nearest samples from the test set to get the most vulnerable test set. We attack on this set for all the methods and show the results in Table I7 We observe that our method makes good trade-off between accuracy and robustness. Although RFGSM-AT is best in terms of overall accuracy, its robustness is very poor.
Aclean
Arobust
TRADES
80.1
24.4
74.5
Nu-AT
41.3
0.0
37.2
MART
78.1
24.1
72.7
PGD-AT
82.6
23.2
76.7
REGSM-AT
91.0
6.6
82.5
ROGET (ag PGD)
88.1
19.0
81.2
Table 17: Performance under AA (white-box) on the most vulnerable test set of CIFAR-10 under worst case hyperparameter selection, when Glatent was chosen using uncertainty based subset selection strategy.
H.9 WORST-CASE HYPEPAARAMETER SETTING FOR FMNIST
We present the results of worst-case hyperparameter selection for FMNIST in Table [8] Here, achieve the best overall accuracy A for three attacks and second-best overall accuracy for the rest.
PGD
AA
Square
MIFGSM
AdvGAN
EMNIST
Achan
A
Arobust
Arcbur
A
A1
0.00
8.32
FBF
$0.47
14.29
73.85
66.74
79.10
68.43
79.27
84.81
$0..0
85.94
$1.02
TRADES
86.85
62.90
84.45
53.37
83.50
57.37
83.90
81.43
86.30
70.42
85.20
Na-AT
90.37
5.92
81.92
0.00
81.33
0.07
81.34
20.26
83.36
14.01
82,73
MART
78.94
77.72
78.82
59.73
77.02
61
77.19
79.81
79.03
70.10
78.06
REGSM-AT
89.46
13.49
81.86
0.00
80.51
0.02
80.51
24.88
83.00
21.85
82,70
ROGET (PGD)
87.01
63.24
84.63
49.63
83.27
$4.29
83.74
80.92
86.40
69.16
85.22
ROGET (AIoGAN)
87.08
49.62
83.33
47.32
83.10
51.99
83.57
82.49
86.62
73.44
85.71
Table 18: Performance comparison under worst case hyperparameter setting for two white box attacks (PGD and AA) and three black box attacks (Square, MIFGSM, and AdvGAN) on FMNIST. Numbers in green (yellow) indicate the best (second best) performers.
41

---

Under review as a conference paper at ICLR 2023
H. EXPERIMENTS ON CIFAR 100
Here, we present results on CIFAR-100 100 dataset. Here, the model is Resnet-9. In default hyperparame- ter setting, use p p= 0.5 for ROGET (ag PGD) and p 2.0 for ROGET (ag AdvGAN). For the baselines, we choose the same default hyperparameters as in CIFAR1O. The results can be seen in Table 19. We also report the results of worst-case hyperparameter setting in Table 20 We observe
that our method outperforms all the baselines in terms of clean, robust (except on PGD attack), and overall accuracies.
PGD
AA
Square
MIFGSM
AdvGAN
CIFARI00
Acban
Arbhust
Avebrac
A
Arohmet
A
Auabuse
Arobmntt
GAT
45.05
43,37
44.88
21.50
42.69
24,03
42.95
21.75
42.62
31.48
43.69
TRADES
43.71
47.56
44.10
32.50
42.59
35.04
42.84
35.44
42.88
43.91
43.73
Nu-AT
32.64
33.15
32.70
8.03
30.37
24.84
31.86
8.24
30.39
15.72
31.14
MART
33.66
32.49
33.55
17.41
32,06
19.72
32.27
22.89
32.59
26.45
32.94
RFGSM-AT
44.55
44.26
9.20
41.02
10.34
41.13
8.10
14.71
41.57
ROGET (PGD, 0.5)
51.65
47.65
51.25
40.75
50,56
45,52
51.04
44.03
50.89
57,57
52.24
ROGET(Ad+GAN, 2.0)
53.29
45.02
52.46
39.76
51.92
44.93
52:45
41.65
52.11
57.52
53.70
Table 19: Performance comparison under default hyperparameter setting on CIFAR 100. We report (percentage) (i) accuracy on the clean examples Actsann (ii) robustness to the adversarial perturbations Arobust and (iii) overall accuracy A. Here, the adversary adopts uncertainty-bet bbsed subset selection to perform attack, where the true subset chosen for attack Slatenn consists top 10% test instances in
terms of the uncertainty of classifier trained on all the clean examples.
PGD
AA
Square
MIFGSM
AdvGAN
CIFARI00
Adcan
Arohrst
Archunt
Avobust
Arabues
Aratont
GAT
47.23
44.11
46.92
18.54
44.36
21.56
44.66
16.63
44.17
28.30
45.36
TRADES
49.37
47.95
49.23
26.54
47.09
29.13
47.34
25.40
46.97
38.00
48.23
32.64
24.84
31.86
8.24
30.39
MART
33.66
32.49
33.55
17.41
32.06
19.72
32.27
22.89
32.59
26.45
32.94
RFGSM-AT
44.55
41.66
44.26
9.20
41.02
10.34
41.13
8.10
40.91
14.71
41.57
(PGD)
52.71
51.52
51.97
$7.20
(Ad-GAA)
53,29
45.02
52.46
39.76
51.92
44.93
$2.45
41.65
52.11
57.52
53.70
Table 20: Performance comparison under worst-case hyperparameter setting on CIFAR100. We report (percentage) (i) accuracy the clean examples Aclean, (ii) robustness the adversarial perturbations Arobust and (iii) overall accuracy A. Here, the adversary adopts uncertainty-basee subset selection perform attack, where the true subset chosen for attack Slatent consists of top 10% test instances in terms of the uncertainty of a classifier trained on all the clean examples.
H.11 COMPARISON OF ROBUST ACCURACY SUBJECT TO A MINIMUM OVERALL ACCURACY
Here, we produce more results related to Table 21 Specifically, we first tune the hyperparameters of all the methods to ensure that the overall accuracy of all methods reaches given threshold and then compare their robustness. If P indicates the hyperparameters, then we find maxp Arobust (P) such that A(P) 2 a for some given We present the results of CIFAR 10 for 0.81 and FMNIST for a = 0.83 in Table 2T for different attacks. For CIFAR1O, we find that ROGET (ag = PGD) is the best performer in terms of robust accuracy and ROGET (aæ AdvGAN) is the best performer in terms of overall accuracy (except for MIFGSM attack). Moreover, ROGET (as = AdvGAN) the second-best performer in terms of robust accuracy. For FMNIST, ROGET (a. AdvGAN) achieves the highest robust accuracy Arabust (except for PGD attack).
42

---

Under review as a conference paper at ICLR 2023
PGD
AA
Square
MIFGSM
AdvGAN
CIFARIO
Apeluae
Arobust
Arabust 62.05
AA
Aroimet 38.47
Arolvant
GAT
35.68
81.13
81.56
81.41
89.66
86.52
FBF
TRADES
$3.78
81.01
61.13
81.74
0.04
81.90
88.27
85.06
Nu- AT
54.64
81.66
61.34
82.33
39.15
83.01
91.28
88.22
MART
PGD-AT
35.35
81.64
55.84
81.88
92.66
88.82
RFGSM-AT
45.94
81.85
37.49
81.00
60.25
83.28
37.91
81.04
89.42
86.20
ROGET (PGD)
59.42
81,40
50.60
81.19
64,73
82,60
49.05
81.03
91.12
87.78
ROGET (AdvGAN)
35.73
82.85
47.66
82.03
63.93
83.67
45.04
81.78
91.96
88.60
PGD
AA
Square
MIFGSM
AdvGAN
FMNIST
Arebus
Acobus
Acobut
Arobun
Aroboant
GAT
9.43
83.07
29.09
85.24
FRF
TRADES
75.30
83.35
53.37
83.50
57.37
83.90
82.05
87.32
70.60
86.18
Nu-AT
20.26
83.36
MART
AT
70.50
89.66
4.42
83.05
37.74
86.38
80.55
90.66
54.32
88.04
REGSM-AT
ROGET (PGD)
64.10
84.62
49.67
83.25
54.29
83.74
81.59
86,99
69.47
85.78
ROGET (AdvGAN)
72.61
84.87
54.86
83.10
58.19
83.43
83.97
86.01
75,00
85.28
Table 21: Performance comparison for two white-box attacks (PGD and AA) and three black- box attacks (Square, MIFGSM, and AdvGAN). We report (percentage) (i) accuracy on the clean examples Acleau. (ii) robustness the adversarial perturbations Arobust and (iii) overall accuracy A. Here, we apply a threshold on and then compare the best possible Arobust. for all the methods. Also, the adversary adopts uncertainty- -hased subset selection perform the attack, where the true subset chosen for attack Glatent consists of top 10% test instances in terms of the uncertainty of a classifier trained on all the clean examples. Numbers in green (yellow) indicate the best (second best) performers. indicates that we could not find the hyperparameter that satisfies the condition applied on A
H. 12
PERFORMANCE VARIATION WITH [SLATETT
Here, we train both the variants ROGET using b 0.1 Dre and evaluate using different number of instances [Slatent perturbed during test. We already reported the results for CIFARIO in the main. In
Figure 22 we report the results for FMNIST, which show that ROGET (a.p = AdvGAN) and ROGET (ap PGD) outperform the baselines the smaller values [ For larger value of S our methods are only being outperformed by the PGD-AT.
ROCETWAGIN
ROGETINI
40
RECSM-AT
20
MART
20 40
80
100
THADES
|s ssltent 1/| (%)
Figure 22: vs.
Slatent for FMNIST
In the experiments, i.e., in Figures and 22 we kept the value of same across different values of [Slateni] set by worst case hyperparameter selection with 6 0.1[2rl We observed that our method performed better for smaller values of [Slatent] Next, we adjust for different |Staten with b | 1Dall Du]. i.e., we provide little information about the proportion of instances that are going to be attacked. Figure [gguure2]summarizze the results which show that ROGET (a. = AdvGAN) outperforms the baselines for wide range of the size of attacked test instances.
43

---

Under review as a conference paper at ICLR 2023
t
70
AAGGN
4%
60
ROGETIN
Y
RFCSM-AT
20
40
80
100
TRADIS
|glatent//
L/|Dtest
Figure 23: AA vs. |Slatent for CIFARIO after tuning P based on the size of number of instances being attacked.
H.13 PLUGGING OTHER MODELS INTO OUR FRAMEWORK
Here, we performed experiments where plugged TRADES loss in the proposed algorithm. Results are as follows for CIFARIO for PGD and Square attack.
Aclean
Arohust
A
Arobust
A
TRADES
80.25
64.68
78.69
78.53 63.06
63.06
TRADES- 84.50
56.08
81.62
82.32
Table 24: Effect of plugging Trades into our algorithm improves its performance.
We observe that plugging TRADES in our algorithm improves the performance of TRADES in terms of the overall accuracy.
H.14 EXPERIMENTS WITH LOSS BASED ATTACK
Here, performed the experiments where the adversary chooses instances based on the predicted accuracy. The following table summarizes the results for PGD and Square Attacks which show that methods outperform the existing method in terms of the overall accuracy well as robust
accuracy.
PGD
Square
CIFARIO
Aclean
Arohust
A
Arobust
A
GAT
78.85
46.33
75.60
37.32
74.70
FBF
76.49
54.62
74.30
21.65
71.01
TRADES
84.63
32.36
79.40
32.77
79.44
Nu-AT
85.62
34.00
80.46
36.35
80.70
MART
81.86
42.29
77.90
36.41
77.32
PGD-AT
84.92
37.07
80.14
34.54
79.88
REGSM-AT
86.76
27.06
80.79
34.13
81.50
ROGET(PGD)
86.23
37.64
81.38
38.18
81.43
ROGET(AdyGAN)
86.75
33.98
81.47
38.24
81.90
Table 25: Performance on loss-based attack.
44


Reviews:
[{"review_id": "roIV0j4z1G_", "reviewer": "Reviewer_iAPp", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper tackles the robust training problem of neural networks. In usual scenarios, the adversary chooses a single data point and perturbs it to be misclassified. On the other hand, the adversary in this study chooses a subset of data points and perturbs them to be misclassified. The goal is to minimize the average loss for all the perturbed and non-perturbed data points. The authors present an algorithm that alternately finds a subset to be perturbed via the greedy algorithm and minimizes the average loss via SGD. This algorithm is validated to be perform well both theoretically and empirically.", "summary_of_the_review": "This paper proposes a new robust training framework and an algorithm with a theoretical performance guarantee. The concept is novel and practically useful, but the theoretical results are not so strong and the proposed algorithms do not always outperform the existing algorithms.", "strength_and_weaknesses": "Strengths:\nSince deep neural networks are practically used in our society, everyone acknowledges the importance of robust training of neural networks. However, as the authors say, the existing frameworks for robust training are too pessimistic, and often sacrifice its average performance for non-perturbed data. To overcome this issue, this paper considers a setting in which the adversary can perturb a small subset of data points. The proposed algorithm is an alternating method with greedy subset selection and loss minimization, which is not so surprising, but its performance is supported by theory.\n\nWeaknesses:\nAlthough the problem setting is novel and the algorithmic idea is nice, the theoretical and empirical results are not so outstanding. \nOn the theory side, the main theorem (Theorem 4) is not always meaningful. Theorem 2 states that $\\lambda R(\\theta)$ must be large to make the submodularity ratio $\\gamma^*$ sufficiently large. On the other hand, if $\\lambda R(\\theta)$ is large, then $\\kappa$ becomes small, and then $[1 - (e^{-\\gamma^*}+\\delta) / \\kappa]^{-1}$ might be negative, which makes Theorem 4 meaningless. However, the problem is motivated by practice and I do not think the theoretical weakness is so problematic.\nAs the experimental results show, the proposed algorithm does not always outperform the existing algorithms. However, I think the authors sufficiently discuss the advantages of the proposed algorithm.\nIt would be better to revise the proofs since they contain small mistakes such as:\n- $q \\mu \\beta \\frac{|S \\cup k|}{|S|}$ in the inequality (32) should be multiplied by $L_\\phi$.\n- $\\sum_{i \\in S \\cup k}$ should be added before the last $\\mu$ in (35).\n- $q \\mu \\beta$ in the inequality (36) should be multiplied by $L_\\phi$.\n- $-\\delta$ in the numerator should be replaced by $+\\delta$ and $+\\delta$ in the denominator should be replaced by $-\\delta$ in the right-hand side of (63).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "qoYZmt-JmP", "reviewer": "Reviewer_SByk", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper considers a threat model where an attacker attacks a subset of the test data of a classification system. To develop a defense, the formulate the learning problem for the classier as a min-max optimization where the loss is minimized over the most adversarial subset of a particular cardinality. The authors show that the inner optimization that requires a subset selection (for a given $\\theta$) us NP-hard. To solve this efficiently, they leverage a stochastic distorted greedy algorithm by (Harshaw et. al. 2019) and is able to give an approximation guarantee for the overall adversarial learning function for a particular class of loss functions. The authors then conduct a suite of experiments to showcase the effectiveness of their approach against existing defenses in the threat model they consider.", "summary_of_the_review": "See above.", "strength_and_weaknesses": "### Things I liked\n\n- The paper addresses an interesting problem, clearly explains the difficult of the problem and proposes a solution with guarantees when certain assumptions hold.\n\n- The authors conduct a reasonable set of experiments and provide logical choices of the baselines, attack methods, etc.\n\n- The mix max over the hyper-parameter choice is nice little trick.\n\n### Things that need clarification / improvement\n\n- The empirical results are weak in several aspects. \n  - The proposed method, ROGET, mostly outperforms other defenses (which are designed for the entire test-set) on clean test-data accuracy. It is at times the worst performing method of perturbed test data. There are also sentences like \"Tuning ρ would easily improve the robustness, as shown in additional experiments in Appendix H\" which surprises me on why would the authors not show their best results as part of the main paper?\n  - If there is some knowledge about the true subset selection strategy at validation time, other methods (designed for all test attacks) outperforms ROGET.\n  - As the amount of test data poisoned grows, the accuracy gains become minimal.\n\n- Given the inner optimization is itself a difficult problem that admits an approximation, the authors should highlight the time/resource costs incurred by their defense vs. existing defenses. Beyond accuracy, this is an important metric to consider.\n\n- There is no clear association between the assumptions made in proofs and the function used in practice. For example, is categorical-cross entropy a Polyak-Lojasiewicz Loss function? If not, the approximation guarantees do not hold here. This disrupts the flow of the paper somewhat.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "U_8RnPa1X6", "reviewer": "Reviewer_gdCM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers a new type of adversary that chooses to only perturb a subset of data. The authors propose a defensive strategy that is formulated as a minimax problem that involves a worst-case subset selection procedure. This paper uses a greedy algorithm to realize the worst-case subset selection. The empirical results demonstrate the proposed method can gain the best overall accuracy on the selected adversarial data and unselected benign data in most scenarios. ", "summary_of_the_review": "This paper investigates a novel attack where the adversary only chooses to perturb a subset. The authors propose a defensive method that makes the model robust against adversarial subset attacks.  This paper is well-written and novel. Thus, I would like to accept this paper though I have some minor questions.", "strength_and_weaknesses": "Strength\n+ The new attack setting that adversarially selects a subset as an adversarial set is interesting and novel. The experimental results show that previous adversarial training methods are vulnerable to this adversarial subset attack. The proposed method can achieve the best performance even under the adaptive attack (subset selection with worst-case hyperparameter setup).\n+ The proposed iterative greedy algorithm is well motivated by the theorem. The proposed method is compatible with variants of adversarial training methods.\n\nWeaknesses (Questions)\n- It could be better to show the results of the proposed method with variants of adversarial loss such as ROGET with TRADES loss to validate the compatibility of the proposed method.\n- I have a concern regarding the adversarial subset attack. The adversary can choose to adversarially perturb those incorrectly-predicted data. This seems to be a realistic attack and could be viewed as the lower bound of the robust accuracy under the adversarial subset attack. It would be better to present the results of this type of attack.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "92thpilOn87", "reviewer": "Reviewer_H4So", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Defending against all perturbed instances is the target of the most current defense mechanisms, and yet in practice only a subset of instances might be selected by the attacker. This paper aims at a new defense mechanism to minimize the worst case loss across all subsets. To solve this optimization problem, the authors design a group of algorithms that admits approximation guarantees for both convex and non-convex (under Polyak-Lojasiewicz condition) objectives. The paper also gives some theoretical analysis of the proposed method. In experiments, the paper shows that the proposed method outperforms SOTA methods on both FMNIST and CIFAR-10.", "summary_of_the_review": "The paper is well-motivated. However, I have concerns on the empirical significance, which makes the paper marginally below the threshold.", "strength_and_weaknesses": "Strength:\n- The paper is clearly motivated.\n- The paper is well written and easy to follow.\n\nComments:\n- I am a bit worried about the empirical significance.\n   1) As in both Table 1 and Table 2, the proposed method is not the best performer in terms of perturbed robustness. \n   2) As in Table 18-20, on CIFAR-100 the proposed method, although achieved second best in most cases, the gap to the best performer is pretty large around 5% in terms of overall accuracy. I have concerns about the scalability issue, that is the proposed method only perform well on small datasets? Does it have the ability of scaling to harder dataset, e.g., Tiny-ImageNet?\n- I would suggest the authors to provide more related work. I checked the appendix, however, I didn't see the related work of worst-class problem and its application in adversarial robustness. The authors are also suggested to compare with those in Table 3.\n- Fig 5 shows the percentage of instances chosen for perturbation, from 5% to 25%, I would suggest to extend axis all the way to 100%, to clearly show the transition power point of the proposed method. If possible, comparing more figures over different datasets would be even more interesting.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject