Doubly Robust Instance-Reweighted Adversarial Training
Authors: Daouda Sow
Sen Lin
Zhangyang Wang
Yingbin Liang
Venue: ICLR 2024 poster (2024)
Keywords: adversarial training
distributionally robust optimization
bilevel optimization
instance reweighting
Primary area: optimization
TL;DR: We propose a novel doubly robust instance reweighted adversarial training framework based on DRO

Abstract: Assigning importance weights to adversarial data has achieved great success in training adversarially robust networks under limited model capacity. However, existing instance-reweighted adversarial training (AT) methods heavily depend on heuristics and/or geometric interpretations to determine those importance weights, making these algorithms lack rigorous theoretical justification/guarantee. Moreover, recent research has shown that adversarial training suffers from a severe non-uniform robust performance across the training distribution, e.g., data points belonging to some classes can be much more vulnerable to adversarial attacks than others. To address both issues, in this paper, we propose a novel doubly-robust instance reweighted AT framework, which allows to obtain the importance weights via exploring distributionally robust optimization (DRO) techniques, and at the same time boosts the robustness on the most vulnerable examples. In particular, our importance weights are obtained by optimizing the KL-divergence regularized loss function, which allows us to devise new algorithms with a theoretical convergence guarantee. 
Experiments on standard classification datasets demonstrate that our proposed approach outperforms related state-of-the-art baseline methods in terms of average robust performance, and at the same time improves the robustness against attacks on the weakest data points. Codes can be found in the Supplement.

Published as a conference paper at ICLR 2024
DOUBLY ROBUST INSTANCE-REWEIGHTED ADVERSARIAL TRAINING
Daouda A. Sow Department of ECE The Ohio State University sow. 53@osu.
Sen Lin Department of CS University of Houston s 2lin50@centra central............m .ub edu
Zhangyang Wang
Visual Informatics Group
University of Texas at Austin a a st.lasaan@uutexss .ecaaassede edu
Yingbin Liang
Department of ECE The Ohio State University
liang. 88 aecoss.eet edu
ABSTRACT
Assigning importance weights to adversarial data has achieved great success training adversarially robust networks under limited model capacity. However, existing instance-reweighted adversarial training (AT) methods heavily depend on heuristics and/or geometric interpretations to determine those importance weights, making these algorithms lack rigorous theoretical restiicaatin/guaraanie over, recent research has shown that adversarial training suffers from severe non-uniform robust performance across the training distribution, e.g., data points belonging to some classes can be much more vulnerable to adversarial attacks than others. To address both issues, in this paper, we propose a novel doubly-robuse instance reweighted AT framework, which allows obtain the importance weights via exploring distributionally robust optimization (DRO) techniques, and at the same time boosts the robustness on the most vulnerable examples. In particular, our importance weights are obtained by optimizing the KL-divergence regularized loss function, which allows us devise new algorithms with a theoretical convergence guarantee. Experiments on standard classification datasets demonstrate that our proposed approach outperforms related state-of-the-an baseline methods terms of average robust performance, and at the same time improves the robustness against attacks on the weakest data points.
More-
INTRODUCTION
Deep learning models are known to be vulnerable malicious adversarial attacks Nguyen al. (2013), i.c., small perturbation added to natural input data can casily fool statc-of-the-ee networks. Given that these deep neural networks are being heavily deployed in real-life applications, even in safety-critical applications, adversarial training (AT) Madry et al. (2017): : (Athalye et al. (2018a);
Carmon et al. (2019) has been proposed for training networks to be robust adversarial attacks
Athalye et al. 8b)18b); Szegedy et al. (2013); Goodfellow et al. (2014); Papernot et al. (2016); Nguyen al. (2015); Zhang al. (202 Ibj 2020a). In particular, most existing delense strategies based on the recipes similar to AT Madry et al. (2017), where the goal is to minimize the average loss of the worst-case adversarial data for the training distribution via solving a minimax optimization problem.
Despite its success, the traditional AT method Madry et al. (2017) has some major limitations. First, even though existing overparameterized neural networks seem to be good enough for natural data, highly adversarial data consumes much more model capacity compared to their clean counterpart, making the minimization of the uniform average adversarial loss a very pessimistic goal, as argued in Zhang et al. (2020b). To overcome this limitation, recent works Zhang et al. (202b)); Liu et al. (2021a): Zeng et al. (2021); Ding et al. (2018) assign an importance weight to each data point in the training distribution, in order to emphasize the ones that are critical to determining the model's decision boundaries. By allowing more careful exploitation of the limited model capacity, such a simple reeeghhe scheme combined with traditional adversarial training has yielded

---

Published as a conference paper at ICLR 2024
significant boost in the robust performance of current adversarially trained models. Yet, existing methods for sataace-reweighted AT mostly adopt heuristic techniques and/or geometric intuitions in order to compute the instance weights, which makes these algorithms lack a principled and rigorous theoretical uustiiicationguurantee This hence motivates the following question we ask:
How to systematically determine the importance weights via a principled approach, rather than resorting to heuristice/nterppetttions which are often sub-optimal?
Moreover, observed in Tian al. (02I), another critical limitation of the transitional AT method is that it suffers severe non-uniform performance across the empirical distribution. For example, while the average robust performance of the AT method on the CIFARIO 10 dataset can be high as 49%, the robust accuracy for the weakest class is as low as 14%, which depicts huge disparity in robust performance across different classes. We note that such non-uniform performance across classes is also slightly observed in the standard training with clean data, but its severity is much worsened in adversarial training (see Figure I Indeed, this is a critical limitation that requires special attention as, in real-world situation, more intelligent attacker can, in fact, decide which examples to attack so as to achieve much higher success rate (e.g., 86% when attacking the most vulnerable class). This non-uniform robust performance is even worsened in the case of imbalanced training distributions Wu et al. [2021;; Wang et al. (2022). where the robust performance for the most vulnerable class can be as low 0%. This motivates our second question given below:
Can such an issue of non-uniform performance particularly over imbalanced datasets be addressed at the instance level simultaneously as we design the importance weights to address the first question?
In this paper, we propose a novel doubly robust instance reweighted optimization approach to address both of the above questions.
1.1 OUR CONTRIBUTIONS
(A novel principled framework for instance reweighted AT) In order to determine the instance
weights for AT in a theoretically grounded way, we propose novel doubly robust instance reweighted optimization framework, based on distributionally robust optimization (DRO) Rahimian & Mehrotra
(2019): : Qian et al. (219)) and bilevel optimization (Zhang et al.] 2022, Pedregosa [0166] Grazzi al., 2020b). Through building model that is robust not only to the adversarial attacks but also to the worst-case instance weight selections, our framework (a) enjoys better robust performance than existing instance-reweighted schemes based on heuristic/geometric techniques /Zhang al.) (2020b); Liu et al.] (202Ta): Zeng et al.] (202T) as well as tradtional AT baselines Madry et al. (2017); and (b) addresses the non-uniform issues Tian et al. (2021): I; Pethick et al.) (2023) of traditional AT by carefully optimizing the instance weights so
boost the robust performance of the most vulnerable examples. Moreover, the proposed framework can be reformulated into a new finite-sum
compositional bilevel optimization problem (CBO), which can be of great interest to the optimization community on its own.
(A novel algorithm with theoretical guarantee) Solving the proposed doubly robust optimization problem is technically challenging, including the non-differentiabiiiyy of the optimizer for the constrained inner level problem and the biased hypergradient estimation for the compositional outer level problem. To tackle these challenges, we first propose a penalized reformulation based on the log-barrier penalty method, and then develop a novel algorithm which exploits the implicit function theorem and keeps track of running average of the outer level composed function values. Our algorithm not only leads to a robust model for the proposed instance reweighted optimization problem but also provides solution to the generic compositional bilevel optimization problem. Under widely adopted assumptions in the bilevel (Grazzi et al. 2020a [Ji et al. [202T] Rajeswaran et al., 2019, [i] & Liang 2021) and compositional optimization Wang et al. (2017); 7): Chen et al. (2021b); Lian et al. (2017); Blanchet et al. (2017); Devraj & Chen (2019) literature, we further establish the convergence guarantee for the proposed algorithm.
(Strong experimental performance) Experiments on several balanced and imbalanced image recognition datasets demonstrate the effectiveness of our proposed approach. In particular, on CIFARIO our approach yields +3.5% improvement in overall robustness against PGD attacks Madry et al. (017) with most of it coming from boosting robustness vulnerable data points.
2

---

Published as a conference paper at ICLR 2024
1.2 RELATED WORK
Adversarial training for robust learning Adversarial training (AT) Madry et al. (2017); Athalye et al.
(2018a); Carmon et al. (2019) was proposed for training deep neural networks robust malicious adversarial attacks Goodfellow et al. (2014); Tramer et al. (2017). In particular, Madry et al. (2017)
introduced a generic AT framework based on minimax optimization with the goal of minimizing the training loss of the worst-case adversarial data for the training distribution. However, despite AT method being still considered as one of the most powerful defense strategies, |ice et al. (2020)
highlights severe decrease in robust performance of traditional AT when training is not stopped early, a phenomenon they dubbed robust overfitting. Several extensions of the standard AT method have been proposed to mitigate this intriguing problem, such as data augmentation- based techniques Rebuffi et al. 2021); (0021)/Gowel Gowal et al. 2021). or smoothing-based methods Chen et al. (202 Yang al. (2020a b). Zhang et al. (2019) proposed a theoretically grounded objective for AT to strike a balance between robust and natural performance. However, those methods suffer a severe non- uniform performance across classification categories. as observed in TTan et al. (202I). Our proposed framework helps mitigate this drawback by carefully optimizing for the most vulnerable data points.
Instance reweighted adversarial training Another line of works Zhang et al. (2020b); Liu et al. 2 Zeng et al.] (2021): Ding et al. (2018) assign an importance weight to each data point in the empirical distribution and minimize the weighted adversarial losses. This has been shown to significantly boost the performance of AT due to more careful exploitation of the limited capacity of large deep neural networks to fit highly adversarial data, and helps overcome robust overfitting to some Satent[Zhang et al. (2020b). For example, in the geometry-aware adversaris instance reweighted adversarial training (GAIRAT) Zhang et al. (2020b) method, the instance weight is computed based on the minimum number of PGD Madry al. (2017) steps required generate mis-classified adversarial example. Liu et al. (2021a) leverages probabilistic margins to compute weights. Existing approaches for instance reweighted AT are, however, all based on heuristics/geometric intuitions to determine the weights. In this paper, we propose a principled approach to instance-reweighted AT by
exploiting robust optimization techniques Qian et al. (2019): RRahmiian & Mehrotra 2019).
Instance reweighting has also been used in the context of domain adaptation Jiang & Zhai (007))
data augmentation Yi et al. (202I). and imbalanced classification Ren et al.) (2018). By determining
the instance weights in a more principled way, our method also has the potential to be applied to these contexts, which we leave as future work.
Due to space limitation, more discussions about related literature in Bilevel Optimization and Stochastic Compositional Optimization is deferred to Appendix
PRELIMINARY ON AT
Traditional AT. The traditional adversarial training (AT) Madry al. (017)) framework is formulated as the following minimax optimization problem over the training dataset D {(x;, M.M
M Σ
min
max 8(x, 0,y);
(1)
M
where ((z; + 5, 3/::: 6) is the loss function on the adversarial input 2; + 5, C is the treat model that defines the constraint on the adversarial noise 8, and 0 E Id corresponds to the model parameters. Thus, the traditional AT builds robust models by optimizing the parameters 0 for the average worst- case adversarial loss E(z, + 8, yı: 0) over the training dataset 'D. A natural solver for the problem in Equation (T) is the AT algorithm Madry et al. (2017), where 1) the projected gradient descent (PGD) Madry et al. (2017) method is first adopted to approximate the worst-case adversarial noise 8 and 2) an outer minimization step is performed on the parameters 0 using stochastic gradient descent (SGD) methods. However, the traditional AT is known to consume tremendous amount of model capacity due to its overwhelming smoothing effect of natural data neighborhoods Zhang et al. (2020b). In other words, the traditional AT robustifies models by making decision boundaries far away from natural data points so that their adversarial counterparts are still correctly classified (i.e., do not cross the decision boundary), and thus requires significantly more model capacity compared to the standard training on clean data.
Instance Reweighted AT. The geometry-awan approach in Zhang et al. (020b) introduces new line of methods that reweights the adversarial loss on each individual data point in order to address
3

---

Published as a conference paper at ICLR 2024
the drawback of traditional AT. The key motivation is that distinct data points unequal by nature and should be treated differently based on how important they participate the selection of decision boundaries. Hence, the learning objective of the geometry-aware instance-reweighted adversarial training (GAIRAT) method as well as its variants Zhang et al. (2020b); Liu et al. (2021a); Zeng et al. (2021)
can be written as
M
min Σ
Wi max E(Tr + 0) with Σ SEC,
w = and wy 2 0,
(2)
where the constraints on the weights vector w (wr) WM T are imposed in order to make Equation (2) consistent with the original objective in Equation T This framework assumes that the weight vector w = (Wi,..., Wx) can be obtained separately and the goal is only to optimize for 0 once an off-the-shelf technique/heuristie can be used to compute w. Intuitively, the key idea driving the weight assignments in instance reweighted methods is that larger weights should be assigned to the training examples closer the decision boundaries, whereas the ones that are far away should have smaller weights because they are less important in determining the boundaries. The major difference among the existing instance reweighted AT methods lies in the heuristies used to design/compute the instance weights wi, i == I..,, ... However, none of those methods adopt a scheme that is theoretically grounded, nor does the formulation in Equation (2) provide way of determining those weights.
Bilevel Optimization Formulation for AT. Along a different line, bilevel optimization has recently been leveraged to develop more powerful framework for adversarial training MaainingZZhngg et al. (2022):
min M Σ f(., + 6, 0s
s.t. (0) arg min (2. + 6, O); sgc,
(3)
where for each data point (x.,, 31). 67 (0) represents some worst-case/optimal adversarial noise under the attack loss function (-; 0). Such a bilevel optimization formulation of AT has key advantages over the traditional framework in Equation (T). First, the traditional AT can be recovered by setting the attack objective to be the negative of the training objective, i.e., (((:;)) = -((:; (). Second, the bilevel formulation gives one the flexibility to separately design the inner and outer level objectives, l' and f, respectively. These key advantages make the formulation in Equation (3) more generic and powerful framework than the one in Equation (T. As we will see next, this enables us to independently construct a new outer level objective that also solves for the instance weights w, and an inner level objective for regularized attack.
PROPOSED FRAMEWORK FOR INSTANCE REWEIGHTED AT
3.1 DONE: DOUBLY ROBUST INSTANCE REWEIGHTED AT
Using the bilevel formulation for AT in Eq. equation B we can incorporate the instance reweighted idea as
min
w. w.l(x, (0)) s.t. 6, (0) = arg min E ((,, + ő, 01: with w. = 1 and w. 2 0. (4)
sec,
Based on bilevel optimization and distributionally robust optimization (DRO), next propose new framework for AT which determines the weights heuristic methods, Specifically, by letting w maximize the weighted sum of the adversarial losses l(z; + 8 (6), ye; f). 1,.., M, we seek to build a model in the outer level problem that is robust not only to the adversarial attacks but also to the worst-case attack distribution:
more principled way rather than using
min max 0 WEP
Σ
wella; + (0).
wi (Mg(M S.1.
8 (0) = arg min (z, + 6, (5) sEC,
where P represents the probability simplex, i..., P= (= RM
Σ M
- w; = and w; 0}. and
the term r EM w; log(M in the outer level objective captures the KL-divergence between w and the uniform weight distribution, which is widely adopted choice of regularizer in the DRO literature Rahimian & Mehrotral (2019). Note that the regularization parameter r > 0 controls the tradeoff between two extreme cases: 1) 0 leads un-regularized problem (as comment
4

---

Published as a conference paper at ICLR 2024
below), and 2)r oo yields u; - M and hence, recover the average objective in Equation Ip. Such a regularizer is introduced to promote the balance between the uniform and worst-case weights w; otherwise the outer level objective in Equation (5) becomes linear in weights vector w, which makes the solution of the 'max' problem to be trivially a one-hot vector w (where the only 'I' is at index i with the largest adversarial loss), and in practice, such trivial one-hot vector makes the optimization routine unstable and usually hurts generalization to the training distribution Qian et al. (009)) Wang et al. (202T)
1
Overall, the formulation in Equation ( becomes a doubly robust bilevel optimization: (a) the inner level finds the worst-case noise o in order to make the model parameters 0 robust to such adversarial perturbation of data input; and (b) the outer level finds the worst-case reweighting first so that the optimization over the model 0 can focus on those data points with high loss values, i.e., the optimization over 0 is over the worst-case adversarial losses.
3.2 AN EQUIVALENT COMPOSITIONAL BILEVEL OPTIMIZATION PROBLEM
An important consequence of choosing the KL-divergence the regularizer is that the max problem
in the outer objective of Equation (5) admits a unique solution w" (0) (see Qi et al. (022)) for
proof), which has its i-the entry given by w (0) exp (+(0,55 /E, exp 3,,,, (0))
Here
denote 1, 57 (0)) f(E; + (0), yı: 0). Substituting this optimal weights vector w" (0) back
in Equation ( yields the following equivalent optimization problem
1
exp (000)
min log
s.t. (0) = arg min arg (0,
(6)
sec,
Problem (6) is, in fact to the best of our knowledge, a novel optimization framework, which we
define as compositional bilevel optimization problem. Without the inner level problem, stochastic algorithms with known convergence behaviors have been devised for the single-level compositional problem. Nevertheless, directly solving problem (6) suffers from several key technical challenges. In particular, the fact that the minimizer of the inner level constrained problem in Equation (6) may not be differentiable w.r.t. to the model parameter prevents the usage of implicit differentiation for solving the bilevel optimization problem.
To tackle this challenge, we propose a penalized reformulation based on the log-barrier penalty method. More specifically, we consider -nom based attack constraint given by = {6 E R'
|| X S x + 8 E 1]") for radius e > and input x E I.. In this case, the constraint set can be written in the form of linear constraint Aő S b with A
-p)) E 222px and b (minnelp. 1p z), min(elp::)) T E 2 With this, we can reformulate the inner problem in Equation (6) as 67 (0) arg minn(,,,50..) (,, 5). where A, and 6, are realizations of aforementioned A and b for input 2,. By using the log-barrier penalty method to penalize the linear constraint into the attack objective, the optimization problem (6) becomes
M
C, (((1))((0)) ))
min [()) = =rlog rlog "
Σ
exp
s.t. (0) = arg min bba (0,8),
(7)
M
seC;
where phar (0, = (, 8) c> 2n log(by - - as denotes the k-th row of matrix A, and by
the k-th entry of vector by. Note that now the constraint {6 E C.) is never binding in Equation because the log- barrier penalty forces the minimizer of tharr 6)) to be strictly inside the constraint
set. Based on this, we show that the minimizer d; (0) becomes differentiable, i.e.,
0b:10) exists when de
() is twice differentiable and under some mild conditions. With the smoothness of 87 (0), also provide the expression of the gradient (L( in the following proposition.
Proposition 1. Let ((, 5) be twice differentiable. Define 7hk = 1/ af 67 (6)) , h: = 1,.... 2p and diagonal matrix C,(0) ediag (n + "ppt1, 12 7pt2 ..., 7pp + 72p)) V/ (0, (( (0)) (0))
invertible, then the implicit gradient 85; (0) exists and we have
0e
VC(0) AM g00, Vos (, 87 (0)) (V3 (10, +(())
(0, (()))
EN (0, (0))
where (,(),)((0) = exp (4(0,57(0))
5

---

Published as a conference paper at ICLR 2024
Proposition provides the expression of the total gradient VC)).. which is useful for practical implementation of implicit differentiation based algorithms for problem (6). Moreover, as in Zhang et al. (2022), when (0()..) is modeled by a ReLU-based deep neural network, the hessian V3 2, 6) w.r.t. imput 6 can be safely neglected due to the fact that ReI.U network generally lead to piece-wise linear decision boundaries w.r.t. its inputs Moosavi-Dezfoolii al. (20T9); AAlfrrra et al. (2022). i.e.,
V (((,,)) 8) R O. Further, the diagonal matrix (,))) can be efficiently inverted. Hence, in order to approximate VC()), we only need Jacobian-vector product computations which can be efficiently computed using existing automatic differentiation packages.
3.3
COMPOSITIONAL IMPLICIT DUPFERENTIATION (CID)
To solve our reformulated problem ( for AT, we consider the following generic compositional bilevel optimization problem, which can be of great interest to the optimization community:
min F(0) = f (a (0,60 0
1 M
Σ (0)))(0))
(8)
s.t. (0) (5,
arg min
1
Σ 1=1
h2 (0, 6,),
( ( x... Var M
which can immediately recover problem 7 by setting 9i = exp
(010
h1 = ((0.8)
>ie log(be- -0 a)) and the constraint set V/ C. Here the outer functions 0: 5) x
R. and f(z) Imm + IR are generic nonconvex and continuously differentiable functions. The inner function (0, 6) Ha x V; + IR is a twice differentiable and admits a unique minimizer in 5, V; is a convex subset of I2 that is assumed to contain the minizers o7 (0). We collect all inner loop minimizers into a single vector 8" (0). The goal to minimize the total objective function F(0): Id - R. which not only leads to a robust model for our instance reweighted optimization problem 7 but also provides a solution to the generic compositional bilevel optimizution problem.
As alluded earlier, solving the compositional bilevel optimization problem is nontrivial. More specifi- cally, it can be shown that the gradient of the total objective is V 0g(0,5 V f (g (0, 8 (0)) by applying the chain rule. Due to the fact that V.(-) needs to be evaluated at the full value g (0, 80)),, standard stochastic gradient descent methods cannot be naively applied here. The reason is that even if we can obtain the unbiased estimates 9s (0, 57 (0)), the product (0,( ff (gi (9, 52 (0))) would still be biased, unless f()) is linear function. This key differ- 09
ence makes problem (8) particularly challenging and sets it apart from the standard finite-sum bilevel optimization problem in which the total objective is linear w.r.t. the sampling probabilities /
To design theoretically grounded algorithm for problem (8) note that the stochastic compositional gradient descent (SCGD) Wang et al. (2017) algorithm for the single-level compositional optimization problem keeps track of a running average of the composed function evaluations during the algorithm running. Inspired by SCGD, we propose a novel algorithm (see Algorithm|] TT that exploits the implicit differentiation technique to deal with the bilevel aspect of problem g Using the implicit function theorem, can obtain
dg (0, (0))
Vegi (0)) - a0
(9)
00
with each of being the solution of the linear system V (0, (0)) v= Vag, (0, (0)).
Specificallyy, at each step f, the algorithm first samples a batch B of cost functions {(gi, h:) and applies K steps of projected gradient descent to obtain 6.5 (6:) as estimate of the minimizer (0.) of each h., in B. Then, the algorithm computes an approximation g (0,, 8K (0.) )) of the stochastic gradient sample 09:(0,.5 (0.)) by replacing each 8, (6,) with 5. (0.) in Equation ( The
09
running estimate us of 0g(0.5 (0)) and the parameters will be next updated as follows
60
[8]
[8]
3r
Me+1= = (1 - M/e Ju +
Σ (i, 8 (0:) and oc+1 = 0e
gl, 8tth (0:)) (10)
Note that we will refer the instantiation of Algorithm I for solving the instance reweighted problem as DONE (which stands for Doubly Robust Instance Reweighted AT).

---

Published as a conference paper at ICLR 2024
Algorithm I Compositional Implicit Differentiation (CID)
1: Input: stepsizes a, (.Se). {1p ), imitializations 8u IR" 8 R², and uo R.
for = 0, 1, ....,
do
3: Draw minibatch of cost functions B = ((9.,.))
4: for each (gi, h,) E B (in parallel) do
5: for k:
...., K do Update 6t, = Ile (8%, Vohh, 8),
7: end for
8:
Compute sample gradient estimate & (0z, o,t,) as in Equation (9 by replacing 8, (0c) with 8,
9:
end for
10:
Compute g(0,, 6: 13) [ El gi ( and Vg(Oe, 8 :)) - Σ | g o%,
11:
Update Me+1 = (1 - 1): Yus + (0 of ;
12:
Update o.+1 3e g(0e, 8t ((u41)
13:
end for
3.4
CONVERGENCE ANALYSIS OF CID
In the following, we establish the convergence rate of the proposed CID algorithm under widely adopted assumptions in bilevel and compositional optimization literatures (see Appendix F for the statement of assumptions and proof Theorem D.
Theorem Suppose that Assumptions I (which are given in Appendix) hold. Select the stepsizes
as B. 7 and E (2,1) 1), and batchsize as O(T). Then, the iterates o,, == O,... T 1 of the
CID algorithm satisfy
E EVFON ( (1)))))))))
+(1 +
The proof can be found in the Appendix. Theorem ! indicates that Algorithm | can achieve an e-accurate stationary point by selecting T O(c-2) 2) and K Olog 2). The dependency on the batchsize can be reduced (cc-l) ) by selecting n, T - which would also lead higher iteration complexity of (ee=)).
EXPERIMENTS
4.1 EXPERIMENTAL SETUP
Datasets and Baselines. We consider image classification problems and compare the performance of our proposed DONE method with related baselines on four image recognition datasets CIFARIO SOLiOCoates Coates al. (201I), and GTSRB Stallkamp et al. (0122) More details about the datasets can be found in the appendix. We compare against standard adversarial training methods AT Madry et al. (2017) and FAT Zhang et al. (2020a). and three other state-of-tt -fate-of-thh-arr instance re-weighted adversarial training methods GAIRAT "Zanng jtt al. (2020b), WMMR Zeng et al. (202T), and MAIL Liu et al. (2021a). We use official publicly available codes of the respective baselines and their recommended training configurations. For our algorithm DONE, we consider three implementations based on how we solve the inner loop optimization: (i) DONE-GD uses simple non-sign projected gradient descent steps; (ii) DONE- ADAM employs the Adam optimizer; and (iii) DONE-PGD adopts the projected gradient sign method. We run all baselines single NVIDIA Tesla V100 GPU.
Krizhevsky & Hinton 2009). SVHN Netzer
Netzer al. (2011), STL10
More details about the training and hyperparameters search can found in Appendix B
Evaluation. For all baselines, report their standard accuracy clean data (SA), the robust accuracy against 20 steps PGD attacks (RA-PGD) Madry et al. (2017), the robust accuracy against AutoAttacks (RA (AA-AA)Crre) (RA-Tail-30) as a measure of robustness against attacks on the most vulnerable data points.
Hein (2020). and the RA-PGD of the 30% most vulnerable classes
4.2 BETTER DISTRIBUTION OF ROBUST PERFORMANCE
We first demonstrate that our proposed doubly robust formulation can indeed achieve robust per- formance in more balanced way across the empirical distribution. Figure shows the per class
7

---

Published as a conference paper at ICLR 2024
CURS
OURS W
00
20
Nove
Ioak
Ind
Figure I: Per-class robust accuracy comparisons between our method and traditional AT method on balanced and imbalanced (0.2 imbalance ratio) CIFAR10.
Table Performance evaluations on balanced and imbalanced (0.2 imbalance ratio) CIFARIO.
Method
Balanced CIFARIO
Unbalanced CIFARIO
SA
RA-PGD
RA-Tail-30
RA-AA
SA
RA-PGD
RA-Tail-30
RA-AA
45.22
69.74
6,25
FAT
86.21
46.59
27.12
43.71
WMMR
81.6
49.53
31.24
40.9
MAIL
83.47
55.12
37.30
44,08
72.01
45.64
9.8
37.17
GAIRAT
83.22
54.81
37.45
41.10
73.87
45.18
16.9
35.43
DONE-GD
83.41
57.46
40.11
45.66
74,22
48.29
17.19
40.06
DONE-PGD
82.62
$8.54
40.18
44.49
74.58
48.13
15.83
38.69
DONE-ADAM
82.25
58.51
40.36
44.20
74.56
48.15
17.10
39.46
robust accuracy (RA-PGD) of the standard AT method and our doubly-robus approach (i.e., vanilla DONE-GD method) for both balanced and imbalanced (with an imbalance ratio of 0.2) CIFARIO 10 dataset. For balanced case, our algorithm improves the robustness on classes, meanwhile with more significant boost on the weakest classes (cat, deer, and bird). On the other hand, for the imbalanced data case, the classes with more examples (last five categories) heavily dominate the robust training dynamic. This consequently leads to very high robustness those classes, but nearly zero robustness on the vulnerable classes (such as car). However, our method can still boost the per class RA-PGD the weak classes (+11% % average the 3 most vulnerable classes) and at the same time maintain superior average RA-PGD. Overall, the results for both balanced and imbalanced settings clearly demonstrate that our doubly-robust approach can, in fact, improve worst-case robustness and hence achieve superior average robust performance.
4.3 MAIN RESULTS
Comparisons under CIFAR10. The overall performance the compared baselines un- der both balanced and imbalanced CIFAR 10 are reported in Table We highlight the fol- lowing important observations. First, overall our methods outperform all other baselines in terms of all three robustness metrics (RA- PGD, RA-Tail-30, and RA-AA), meanwhile also maintaining a competitive standard acur- racy (SA). In particular, our algorithms can improve the RA-PGD of the strongest baseline (MAIL) by over 3% with most of the gain coming from improvement on the weakest classes, as is depicted on the RA- RA-Tail-30 column. This shows that our doubly robust approach can mitigate the weak robustness on the vulnerable data points while also keeping the robust performance on well guarded examples (i.e., easy data points) at the same level. Second, note that the instance reweighted baselines consistently outperform the methods without reweighting on the RA-Tail-30 metric, which indicates that reweighting in general boosts the robustness on weak examples. This advantage is even clearer on the imbalanced data case. Yet. algorithms still outperform the other instance reweighted methods by around 3% in terms of RA-Tail-30 in the balanced data setup due to their doubly-robut nature, which clearly is helpful both for average and worst-case robust performance. Third, note that the other methods that employ
Table 4: Comparisons with fast AT methods.
Method
SA
RA-PGD
RA-Tail-30
Fast-AT
82.44
45.37
23.3
Fast-AT-GA
79.83
47.56
25.01
Fast-BAT
79.91
49.13
26.05
DONE
79.17
55.17
37.13
8

---

Published as a conference paper at ICLR 2024
Table 2: Performance evaluations on balanced and imbalanced (0.2 imbalance ratio) SVHN.
Balanced SVII
Unbulanced SVIIN (0.2)
Method
SA
RA-PGD
RA-Tail-30
RA-AA
SA
RA-PGD
RA-Tail-30
RA-AA
93.21
57.82
47.21
46.27
88.46
51.08
33,67
41,13
MATI
93.11
65.56
52.23
41.38
86.62
48.48
31.91
34.46
GAIRAT
91.56
64.74
52.15
39.41
86.73
53.79
36.46
33.25
DONE PGD
92.80
66.20
55.84
48.32
88.05
54.85
39.91
41.44
DONE-ADAM
92.58
65.72
53.79
49.13
88.98
55.90
41.10
42.38
Table 3: Performance evaluations STL10 and GTSRB (originally imbalanced) datasets.
STL.10
GTSRB
Method
SA
RA-PGD
RAiTail:30
RA-AA
SA
RA MGD
RA Tail
RA-AA
AT
67.11
36.28
10.07
32.58
88,13
59.65
27.03
57.83
MAIL
68.06
38.20
13,33
32,86
88:47
53.96
20.73
53.44
30.42
86.67
22.10
DONE-POD 66.98
40.23
17.87
33.71
89.34
60.16
27.41
57.25
DONE-ADAM
66.92
39.70
17.62
34.59
88.76
60.05
28.35
57.70
heuristies to compute the instance weights achieve worst RA-AA performance compared to the standard AT method. In contrast, our algorithms, which also fall in the instance reweighted paradigm, can still attain competitive performance for RA-AA compared to the standard AT method. This highlights the suboptimality of using heuristics which could be geared towards improving one metric (such as the RA-PGD) but may not be necessarily beneficial to the overall robustness of the model.
Performance Comparisons the other datasets. Table 2 shows the evaluations of the compared baselines on the SVHN dataset. As depicted, our algorithms (DONE-PGD and DONE-ADA significantly outperform the standard AT method on the RA-PGD metric and at the time achieve better robustness against AutoAttacks (RA-AA). Compared with the instance reweighted baselines (MAIL& & GAIRAT), the advantage of our methods is even more important on the RA-AA metric (e.g., up to around +8% on RA-AA VS +1.5% on RA-PGD for the balanced data setting). We also note considerable improvements on the GTSRB and STL10 datasets Table 3 Similarly the CIFAR10 dataset, our approach yields an important boost on the RA-Tail-30 robustness metric compared to all other baselines and the advantage is more significant on the imbalanced data case. These results consistently demonstrate that our doubly-robust approach can indeed improve worst-case robust performance meanwhile also maintanning/mmrooingg the overall robustness.
Evaluations under Fast AT Setting. We also compare approach with fast adversarial training methods. For this setup, we generate the adversarial attacks during training with only 1 GD step after initialization with PGD warm-up up step Zhang al. (2022) and train all baselines for 25 epochs. We compare our method with Fast- BAT Zhang et al. 2022), Fast-AT Wasg et al. (2020), and Fast-AT-GA Andriushchenko & Flammarion (2020) on CIFARIO The evaluations of the compared methods are reported in Table Our algorithm achieves a much better robust performance and at the same time keeps competitive SA. In particular, note significant boost (+1 1 11) in RA-Tail-30, which is mainly the cause of the improvement in the overall RA-PGD.
CONCLUSIONS
In this paper, we proposed novel doubly robust instance reweighted adversarial training framework based on DRO and bilevel optimization, which not only determines the instance weights for AT in a theoretically grounded way but also addresses the non-uniform issues of traditional AT by boosting the robust performance of the most vulnerable examples. To address the technical challenges in solving the doubly robust optimization problem, we proposed a penalized reformulation using the log- barrberrerr penalty method, and developed a novel algorithm based on implicit function theorem and tracking a running average of the outer level function values. Our proposed framework also leads to new finite-sum compositional bilevel optimization problem, which can be of great interest to the optimization community and solved by our developed algorithm with theoretical guarantee. In the experiments standard benchmarks, our doubly-robust approach (DONE) outperforms related state-of-the tf-the---te--tt baseline approaches in average robust performance and also improves the robustness against attacks the weakest data points.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
The work of D. Sow and Y. Liang was supported in part by the U.S. National Science Foundation under the grants CCF-1900145,, ECCS-2113860 and CNS-2112471.
REFERENCES
Motasem Alfarra, Adel Bibi, Hasan Hammoud, Mohamed Gaafar, and Bernard Ghanem. On the decision boundaries of neural networks: A tropical geometry perspective. IEEE Transactions Pattem Analysis and Machine Intelligence, 2022.
Maksym Andriushchenko and Nicolas Flammarion. Understanding and improving fast adversarial training. Advances in Neural Information Processing Systems, 33:16048 160166600999 2020.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of
security: Circumventing defenses to adversarial examples. In International conference machine learning, pp. 274-283, PMLR, 2018a.
Anish Athalye, Logan Engstrom, Andrew Ilyas, and Kevin Kwok. Synthesizing robust adversarial examples. In International conference on machine learning, pp. 284-293. PMLR, 2018b.
Luca Bertinetto, Joao F Henriques, Philip Torr, and Andrea Vedaldi. Meta-learning with differentiable closed-form solvers. In International Conference on Learning Representations (ICLR), 2018.
Jose Blanchet, Donald Goldfarb, Garud Iyengar, Fengpei Li, and Chaoxu Zhou. Unbiased simulation for optimizing stochastic function compositions. arXiv preprint arXiv: 2017.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Percy Liang. Unlabeled data improves adversarial robustness. Advances in neural information processing systems, 32,
2019.
Tianlong Chen, Zhenyu Zhang, Sijia Liu, Shiyu Chang, and Zhangyang Wang. Robust overfitting may be mitigated by properly learned smoothening. In International Conference Learning Representations, 202
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Solving stochastic compositional optimization is nearly as easy as solving stochastic optimization. IEEE Transactions on Signal Processing, 69:4937-4948,, 2021b.
Adam Coates, Andrew Ng. and Honglak Lee, An analysis single-layer networks in unsupervised feature learning. In Geoffrey Gordon, David Dunson, and Miroslav Dudík (eds.), Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume of
Proceedings of Machine Learning Research, pp. 215 223,, Fort Lauderdale, FL, USA, 11-13 Apr 2011. PMLR. URL httph::tt//tt h/tt:::://proceedngggs mir
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-fe attacks. In International conference on machine learning, pp. 2206-2216. PMLR, 2020.
Adithya M Devraj and Jianshu Chen. Stochastic variance reduced primal dual algorithms for empirical composition optimization. Advances in Neural Information Processing Systems, 32, 2019.
Gavin Weiguang Ding, Yash Sharma, Kry Yik Chau Lui, and Ruitong Huang. Mma training: Direct input space margin maximization through adversarial training. arXiv preprint arXiv: 1812.02637, 2018.
Justin Domke. Generic methods for optimization-bast modeling. International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 318-326, 2012.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. agnostc meta-leaming for fast adaptation of deep networks. Proc. International Conference on Machine Learning (ICML), pp. 1126-1135, 2017.
10

---

Published as a conference paper at ICLR 2024
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient- based hyperparameter optimization. In International Conference on Machine Learning (ICML), pp. 1165-1173, 2017.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-leaming. In International Conference on Machine Learning (ICML), pp. 1568-1577, 2018.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572, 2014.
Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, and Edison Guo. On diffcrentiating parameterized argmin and argmax problems with application to bi-level optimization. arXiv preprint AXXiv:607.004477 2016.
Sven Gowal, Sylvestre-Alvise Rebuffi, Olivia Wiles, Florian Stimberg, Dan Andrei Calian, and Timothy Mann. Improving robustness using generated data. Advances in Neural Information Processing Systems, 34:4218 42333, 2021.
Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration com- plexity of hypergradient computation. International Conference Machine Learning (ICML),, 2020a.
Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration com- plexity of hypergradient computation. In Proc. International Conference on Machine Learning (ICML), 2020b.
Wenqing Hu, Chris Junchi Li, Xiangru Lian, Ji Liu, and Huizhuo Yuan. Efficient smooth non-convex stochastic compositional optimization via stochastic recursive gradient descent. Advances in Neural Information Processing Systems, 32, 2019.
Kaiyi Ji and Yingbin Liang. Lower bounds and accelerated algorithms for bilevel optimization. arXiv preprint (tti::2002.0392220 2021.
Kaiyi Ji, Jason D Lee, Yingbin Liang, and H Vincent Poor. Convergence of meta-learning with task-specific adaptation over partial parameter. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Kayi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. International Conference on Machine Learning (ICML)), 2021.
Jing Jiang and ChengXiang Zhai. Instance weighting for domain adaptation in nlp. ACL, 2007.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. 2009.
Xiangru Lian, Mengdi Wang, and Ji Liu. Finite-sum composition optimization via variance reduced gradient descent. In Artificial Intelligence and Statisties, pp. 1159-1161 PMLR, 2017.
Renjie Liao, Yuwen Xiong, Ethan Fetaya, Lisa Zhang. Xaq Yoon, KiJung Pitkow, Raquel Urtasun, and Richard Zemel. Reviving and improving recurrent pack-propagation. International Conference on Machine Learning (ICML)), 2018
Tianyi Lin, Chengyou Fan, Mengdi Wang, and Michael I Jordan. Improved sample complexity for stochastic compositional variance reduced gradient. In 2020 American Control Conference (ACC), pp. 126- 131. JEEE, 2020.
Feng Liu, Bo Han, Tongliang Liu, Chen Gong, Gang Niu, Mingyuan Zhou, Masashi Sugiyama, et al. Probabilistic margins for instance reweighting in adversarial training. Advances in Neural Information Processing Systems, 34:23258-23222 2021a.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint arXiv: 1806 090550 2018.
11

---

Published as a conference paper at ICLR 2024
Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton. In International Conference Machine Learning (ICML), 2020.
Risheng Liu, Jiaxin Gao, Jin Zhang, Deyu Meng, and Zhouchen Lin. Investigating bi-level opti- mization for learning and vision from unified perspective: A survey and beyond. arXiv preprint MrXiv:2101115517 2021
Risheng Liu, Yaohua Liu, Shangzhi Zeng, and Jin Zhang. Towards gradient-based bilevel optimization with non-convex followers and beyond. Advances in Neural Information Processing Systems (NeurlPS), 34, 2021c.
Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. International Conference Artificial Intelligence and Statistics (AISTATS), pp. 1540-1552, 2020.
Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient-barse hyperparameter optimization through reversible learning. In International Conference on Machine Learning (ICML), pp. 2113- 2122, 2015.
Aleksander Madry. Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 106.::170..6000 2017.
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Jonathan Uesato, and Pascal Frossard. Robust- ness via curvature regularization, and vice versa. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.
2019.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011.
Anh Nguyen, Jason Yosinski, and Jeff Clune. Deep neural networks are easily fooled: High confidence predictions for unrecognizable images. In Proceedings of the IEEE conference on computer vision and patlern recognition, pp. 427-436, 2015.
Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredrikson, Z Berkay Celik, and Ananthram Swami. The limitations of deep learning in adversarial settings. In 2016 IEEE European symposium on security and privacy (EuroS&P), pp. 372-387. IEEE, 2016.
Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In International Conference on Machine Learning (ICML), pp. 737-746, 2016.
Thomas Pethick, Grigorios G Chrysos, and Volkan Cevher. Revisiting adversarial training for the worst-performing class. arXiv preprint arXiv:2302.0888 08872, 2023.
Qi Qi. Zhishuai Guo, Yi Xu, Rong Jin, and Tianbao Yang. An online method for a class of distributionally robust optimization with non-convex objectives. Advances in Neural Information Processing Systems, 34: 14:10007700000, 2021.
Qi Qian, Shenghuo Zhu, Jiasheng Tang, Rong Jin, Baigui Sun, and Hao Li. Robust optimization over multiple domains. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 477394776,.. 2019.
Hamed Rahimian and Sanjay Mehrotra. Distributionally robust optimization: A review. arXiv preprint arXiv:1908.0566 2019.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with implicit gradients. In Advances in Neural Information Processing Systems (NeurIPS), pp. 113-124, 2019.
Sylvestre- Alvise Rebuffi, Sven Gowal, Dan Andrei Calian, Florian Stimberg, Olivia Wiles, and Timothy A Mann. Data augmentation can improve robustness. Advances in Neural Information Processing Systems, 34:29935-29948, 2021.
12

---

Published as a conference paper at ICLR 2024
Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning. In International conference on machine learning, pp. 4334 4343. PMLR, 2018.
Leslie Rice, Eric Wong, and Zico Kolter. Overfitting in adversarially robust deep learning. In International Conference on Machine Learning, pp. 8093-8104. PMLR, 2020.
Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated pack-propagation
for bilevel optimization. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1723-1732, 2019.
Johannes Stallkamp, Mare Schlipsing, Jan Salmen, and Christian lgel. Man computer: Bench- marking machine learning algorithms for traffic sign recognition. Neural networks, 32:323-332, 2012.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties neural networks. arXiv preprint arXiv: 13 132.v19312.61999 2013.
Qi Tian, Kum Kuang, Kelu Jiang, Fei Wu, and Yisen Wang. Analysis and applications of class-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, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick McDaniel. The space of transferable adversarial examples. arXiv preprint arXiv: 1704.03453, 2017.
Rasul Tutunov, Minne Li, Alexander fowen-Rivers, Jun Wang, and Haitham Bou-Ammar, Compo- sitional adam: An adaptive compositional solver. arXiv preprint arXiv:2002.033: 03.55500..35........... 2020.
Jingkang Wang, Tianyun Zhang, Sijia Liu, Pin- Yu Chen, Jiacen Xu, Makan Fardad, and Bo Li. Ad- versarial attack generation empowered by min-max optimization. Advances in Neural Information Processing Systems, 34: 1620--1003, 2021.
Mengdi Wang, Ji Liu, and Ethan Fang. Accelerating stochastic composition optimization. Advances in Neural Information Processing Systems, 29, 2016.
Mengdi Wang, Ethan X Fang, and Han Liu. Stochastic compositional gradient descent: algorithms for minimizing compositions of expected value functions. Mathematical Programming. 161:419-449, 2017.
Wentao Wang, Han Xu, Xiaorui Liu, Yaxin Li, Bhavani Thuraisingham, and Jiliang Tang. Imbalanced adversarial training with reweighting. In 2022 IEEE International Conference on Data Mining (ICDM), pp. 1209-1214. IEEE, 2022.
Eric Wong, Leslie Rice, and J Zico Kolter. Fast is better than free: Revisiting adversarial training. arXiv preprint arXiv:2001.03994 2020.
Tong Wu, Ziwei Liu, Qingqiu Huang, Yu Wang, and Dahua Lin. Adversarial robustness under long-tailed distribution. In Proceedings of the IEEE/CVF conference on computer vision and pattem recognition, pp.
2021.
Yua-Yuan Yang, Cyrus Rashtchian, Hongyang Zhang, Ruslan Salakhutdinov, and Kamalika Chaud- huri. Adversarial robustness through local lipschitzness. arXiv preprint arXiv:2003.02466 20, 2020a.
Yao- Yuan Yang, Cyrus Rashtchian, Hongyang Zhang, Russ R Salakhutdinov, and Kamalika Chaud- huri. A closer look at accuracy vs. robustness. Advances in neural information processing systems, 33:8588 8601, 2020b.
Mingyang Yi, Lu Hou, Lifeng Shang, Xin Jiang, Qun Liu, and Zhi-Ming Ma. Reweighting augmented samples by minimizing the maximal expected loss. arXiv preprint arXi::2103.08933 2021.
Huimin Zeng, Chen Zhu, Tom Goldstein, and Furong Huang. Are adversarial examples created equal? a learnable weighted minimax risk for robustness under non-une non-uniform attacks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 10815-10822 2021.
13

---

Published as a conference paper at ICLR 2024
Hongyang Zhang. Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International conference on machine learning, pp. 7472-7482. PMLR, 2019.
Jingfeng Zhang, Xilie Xu, Bo Han, Gang Niu, Lizhen Cui, Masashi Sugiyama, and Mohan Kankan- halli. Attacks which do not kill training make adversarial learning stronger. In International conference on machine learning, pp. 11278-1111 1287. PMLR, 2020a.
Jingfeng Zhang, Jianing Zhu, Gang Niu, Bo Han, Masashi Sugiyama, and Mohan Kankanhalli. Geometry-aware instance-reweighted adversarial training. arXiv preprint arXiv:2010.01736, 2020b.
Miao Zhang, Steven Su, Shirui Pan, Xiaojun Chang, Ehsan Abbasnejad, and Reza Haffari. idarts: Dif- ferentiable architecture search with stochastic implicit gradients. arXiv preprint ar arXiv:2106.10755 2021a.
Yihua Zhang, Guanhua Zhang, Prashant Khanduri, Mingyi Hong, Shiyu Chang, and Sijia Liu. Revisiting and advancing fast adversarial training through the lens of bi-level optimization. In International Conference on Machine Learning. pp. 26693-26711 PMLR, 2022.
Yonggang Zhang, Mingming Gong, Tongliang Liu, Gang Niu, Xinmei Tian, Bo Han, Bernhard Schölkopf, and Kun Zhang. Causaladv: Adversarial robustness through the lens causality. arXiv preprint arxi 106.060060 196, 2021b.
14

---

Published as a conference paper at ICLR 2024
SUPPLEMENTARY MATERIAL
We provide the details omitted in the main paper. The sections are organized as fellows:
Appendix A
We discuss related literature about bilevel optimization and stochastic compositional
optimization.
Appendix B We provide more details about datasets, training setups, hyperparameters search, and implementations.
We provide the distributions of the robustly learned instance weights and models' confusion matrices for the considered datasets.
Appendix C
Appendix D
We provide the proof of Proposition
We present the convergence analysis of our proposed CID algorithm including the statements of assumptions and the full proof of Theorem T
Appendix
A MORE RELATED WORK DISCUSSIONS ABOUT BILEVEL OPTIMIZATION AND STOCHASTIC COMPOSITIONAL OPTIMIZATION
Bilevel optimization Bilevel optimization is a powerful tool to study many machine learning applica-
tions such as hyperparameter optimization (Franceschi al. 2018 Shaban et al. 2019), meta-learning
(Bertinetto et al. 2018 Franceschi et al.) 2018: Rajeswaran et al. 2019 Ji et al. 2020 Liu et al.
2021b), neural architecture search (Liu al. 2018 Zhang et al. 202 a). etc. Existing approaches
usually approximate implicit differentiation (AID)
based (Donke 20 Pedregosa 2016 Gould
al.
2016; Liao et al.
2018
Lorraine et al.
2020),
or iterative differentiation (ITD) based (Domke
2012
Maclaurin et al.
2015
Franceschi et al.
2017 Finn et al. 2017 Shaban et al. 2019 Rajeswaran
al.
2019 Liu et al.
2020).
The convergence rates of these methods have been widely established
(Grazzi et al. 2020a]] Ji et al. 2021 Rajeswaran et al. 2019 Di & Liang, 2021). Bilevel optimization
has been leveraged in adversarial training very recently, which provides a more generic framework by
allowing independent designs of the inner and outer level objectives Zhang et al. (2022). However, none of these studies investigated bilevel optimization when the outer objective is in the form of compositions of functions. In this work, we introduce the compositional bilevel optimization problem as a novel pipeline for instance reweighted AT, and establish its first known convergence rate.
Stochastic compositional optimization Stochastic compositional optimization (SCO) deals with the minimization of compositions of stochastic functions. [Wang et al. (2017) proposed the compositional stochastic gradient descent (SCGD) algorithm a pioneering method for SCO problems and established its convergence rate. Many extentions of SCGD have been proposed with improved rates, including accelerated and adaptive SCGD methods Wang al. (2016): Tutunov al. (2020).
and variance reduced SCGD methods Lian et al. (0017); Blanchet et al. 2017 0) Lin et al. 2020);
Devraj & Chen (2019); Hu et al. (2019) A SCO reformulation has also been used solve nonconvex distributionally robust optimization (DRO) Rahimian & Mehrotra (2019); Qian et al. (2019) problems. The problem studied in this paper naturally falls into new class problems but with an additional
inner loop compared to the existing single-level SCO problem, which we refer to as compositional
bilevel optimization (CBO).
B MORE EMPIRICAL SPECIFICATIONS
B. MORE DETAILS ABOUT TRAINING AND HYPERPARAMETERS SEARCH
Following the standard practice in adversarial training Madry et al. (2017) 7 ; Liu et al. 2021a): Zhang et al. (2020b), we train our baselines using stochastic gradient descent with a minibtach size of 128 and a momentum of 0.9. We use ResNet- 18 as the backbone network as in Madry et al. (2017) and train our baselines for 60 epochs with cyclic learning rate schedule where the maximum learning rate is set to 0.2 Zhang et al. (2020b): Liu et al. (2021c) (please see fig. (). We consider &oc noom bounded adversarial perturbations with maximum radius of e = 8/255 both for training and testing.
15

---

Published as a conference paper at ICLR 2024
For the KL-divergence regularization parameter in algorithms, where we initially set to and decay it to and 0.1, respectively at epochs 40 and 50 (see fig. (2) This setting allows methods start with an instance-weight distribution close to uniform the beginning training where the weights are less informative, and progressively emphasize more on learning weight distribution that boosts worst-case adversarial robustness. All hyperparameters were fixed by holding out 10% of the training data as validation set and selecting the values that achieve the best performance on the validation set. For the reported results, we train on the full training dataset and report the performance on the testing set Zhhng et al. (2020b): Liu et al. (221
decayed schedule
KL regularizer
Learning rate
6
0.1
0.05
0
5k
10k
20k
10k
15k
20k
25k
Training
Training
60
40
20
10
Step
Step
5k
15k
20k
25k
10k
20k
25k
SA
RA-PGD
80
50
40
20
20
10
Stop
5k
10k
15k
20k
5k
10k
15k
20k
Figure 2: Learning process our method DONE- ADAM for the balanced CIFARIO experiment. The SA and RA-PGD in third row evaluated on the test set. The plots are obtained by averaging three different runs.
B.2 FURTHER DESCRIPTIONS ABOUT DATASETS
We consider image recognition problems and compare the performance of the baselines on four datasets: CIFAR 10 Krizhevsky Hinton (2009), SVHNNNetzer et al. () STL10 Coates et al.
STL1O[Coates
(2011), and GTSRB Stallkamp al. (2012). For CIFARIÓ, SVHN, and STL10 use the training and test splits provided by Torchvision. For GTSRB, we use the splits provided in Zhang et al. (2022). STL10 has 10 categories that are similar those in CIFAR10 10 but with larger colour images (96 96 resolution) and less samples (500 per class for training and 800 per class for testing). The German Traffic Sign Recognition Benchmark (GTSRB) contains 43 classes of traffic signs, split into 39,209
16

---

Published as a conference paper at ICLR 2024
104
73
57
1231
52
12
32
9
1000
139
31
167
06.
60
51
170
800
0.6
31
168
48
1096
28
19
27
20
600
112
942
25
0.4
123
79
51
74
123
78
840
32
78
22
254
106
20
9
16
126
75
138
0.2
135
105
99
69
107
55
34
826
Predicted
SVHN (divide by 1500 to obtain accuracies)
GTSRB
airplane
automoblle
bind
600
bird
22
429
3316
110
1.
39
5
493
15
11
10
:1
43
167
400
D3t
53
31
74
344
315
114
139
49
31
51
15
129
75
269
94
79
17
21
doer
56
14
59
70
4:7
36
1-4
83
35
20
400
300
42
14
63
156
6G
4-2
94
91
15
26
dog
14
120
64
207
110
333
307
22
304
28
horse
16
25
10
28
1.39
95
35
92
6
36
200
200
monkey
84
220
89
stip
12
436
truck
truck
66
8
218
18
10
10
86
354
airptanet
hatomobble
bidd
tttck
arplane
bind
deg
monkey
ship
CIFAR 1O (divide by 1000 obtain accuracies)
STL10 (divide by 800 to obtain accuracies)
Figure 3: Confusion matrices of models robustly trained using our approach. The annotations
correspond to the raw number of adversarial examples from class that were classified class j. Per-class robust performance are depicted in the diagonals. Axis labels are provided in first plot only.
training images and 12,630 test images. The images are 32 x 32 resolution colour. The dataset is highly class-imbalanced with some classes having over 2000 samples and others only 200 samples.
B.3 FURTHER IMPLEMENTATION SPECIFICATIONS
use the official publicly available codes of the respective baselines and their recommended training configurations. Pytorch codes for our method are provided in the supplementary material of our submission. Our implementation is built upon the codebase accompanying the paper Zhang et al. (2022). We thank the authors for making it publicly available. All codes tested with Python 3.7 and Pytorch 1.8.
For example, to following command:
DONE-ADAM algorithm on the balanced CIFARIO dataset, please the
python main py --mode ours++ -ddataset CIFARIO --ir 1. -kkl_coef 10 --epochs 60 --cycliccmilestueee 25 --kccmmilestone 40 -klccmilletoone" 50 -- attack
-=attcckrs_tess rs_tess__ttt --attack_ ---aatacckstep_tes__ 20
For example the argument 'ir' can used to control the imbalance ratio. The argument 'mode' can be set 'ours' or 'ours++', and selects among different implementations of same approach.
17

---

Published as a conference paper at ICLR 2024
hore
Ji ha and
F- OF DVL
Ei an SPAA App
lEd p0a UKe
nutto pood suzen on budk loned tuoe
at. alai send
ara pP0
morte pad mote
F- gmd
J- CL. SAC
Pc here pood ner
drol prud.
g ruck pred bus
gelene hrec
(a) STL10 dataset
(b) CIFAR10 dataset
Figure 4: Samples with small weights from STL10 and CIFAR1O datasets. These are generally 'easy' images with the true objects well centered and clear/non -aarr/oon-ambiguuuss backgrounds.
Both implementations perform similarly. Please check the file 'train.py" for more details about the arguments and the possible options.
We run all baselines single NVIDIA Tesla V100 GPU.
C DISTRIBUTIONS OF LEARNED WEIGHTS
Figure Souree]shoor shows the distributions of the learned weights per-class for CIFARIO, SVHN, and STL10 datasets. The distributions are obtained on testing sets using PGD steps. Further per-class insights are also provided in Figure depicted in the diagonals). Comparing the two figures, we note a negative correlation between the magnitude of weights and the per-class robust performance, i.c., classes which the model achieve high robustness are usually associated with weights that are closer to 0. For example, the class automobile in CIFARIO datset, in which the model achieves the highest adversarial robustness of 74.5% also has around 70% of its associated weights less than 0.001. As a comparison, the most vulnerable class (i.e., cat, in which the model achieves robustness of 34.4%) 4.) has more than 90% of its associated weights larger than 0.001. We note similar correlation of the weights distributions and the robust performance STL10 dataset. Interestingly, the robust performance is more uniformly distributed across classes in the SVHN dataset (as depicted in the corresponding confusion matrix in Figure 3) and our method was able to automatically discover very close weights distributions across classes for this dataset. This further demonstrates the generality/robustness of our approach, which can perform well no matter instance re- weightting is advantageous or less important.
confusion matrices (where per-class robust accuracies are
Figures 4 and 6 provides examples of images from CIFARI0 and STL10 datasets with low/high associated weights. Examples with low weights are usually "easy" images which objects are well centered with ddear/non-ambiguon backgrounds. Our algorithm was able to correctly classify the adversarial examples crafted from these images. In contrast, examples with high weights are generally 'hard' samples with only parts of the objects appearing or/and backgrounds that can lead to ambiguity. For example, the true label of the second image in the first row of Figure ( iss deer but the image also contains car in its background, which may easily lead to confusion. Also note the first image in the third row of Figure 6, where only part of the tires of the car appears in the image.
18

---

Published as a conference paper at ICLR 2024
airpione
automobile
bird
COR
door
800
600
200
0
0.00
00g
frog
horse
ship
truck
800
600
Dunoity
CIFARIO dataset
airplane
bird
deer
125
100
Dondat
0.0
dog
monkkyy
ship
125
100
Dondty
2.0
STL10 dataset
3
200
ponsty
100
2.00
0.24
0.00
0.54
0.02
9.00
0.04
0.00
0.04
150
Dondt
1.00
0.00
0.04
SVHN dataset
Figure Distributions of the learned weights per class on the testing sets. Classes on which the model achieve high robustness usually associated with weights that closer 0. For example, the class automobile in CIFARIO datset, in which the model achieves the highest adversarial robustness of 74.5% also has around 70% of its associated weights less than 0.001. As comparison, the class cat (in which the model achieves a robustness of 34.4%) has more than 90% of its associated weights larger than 0.001. We note similar correlation of the weights distributions and the robust performance in STL10. The robust performance is better uniformly distributed across classes in the
SVHN dataset (see fig. 3 and our method was able to obtain similar weights distribution across classes for this dataset.
19

---

Published as a conference paper at ICLR 2024
arsil
Mird
prod
prad:
sf thakk prest
home pred thoa
an deer (oredt
3i home peed:
or arpi pard auton
gt cal pore dry.
S:ahpp prect airt
mancel prod truck
20 pha pred. sar
0::000 prect cat
de ahis anod: dog
buue prod nome
ge prod: sty
(a) STL10 dataset
(b) CIFAR1O dataset
Figure 6: Samples with large weights from STL10 and CIFARIO datasets. These are 'hard' examples with only parts of the objects appearing or/and complex backgrounds that easily lead to ambiguity. For example, the true label of the second image in the first row of figure (a) is deer but the image also contains car in its background, which leads to ambiguity. Also note the first image in the third row of figure (a), where only part of the tires of the car appears in the image.
D PROOF OF PROPOSITION
Recall the reformulated problem
which we rewrite as
M
(e (0))
min L()) = ʃ
M
s.t. (0) arg min el (0, (,(,,) sEC,
log(bu - ox); -aa))
1=
where (0, (0))
exp
(410,5 (0)) and f(z) = r 1og(22 for z 2 1.
Applying the chain rule to the outer function, we have
M
M
(0,
V2 -vi
Σ g: 8;(())
Σ
M
M
00
1=1
06;
r
Vogi(0, 8 (0) +
(0 (0
(11)
1 87 (0))
ae
Also, note that V Vathar (0, (0, = V (,, + Σ1 2p
Using the implicit differentiation
k= be
w.r.t 0 of equation V Valhar (0, (0)) = 0, i.c.
2p
Vel (0)))
a
0,
by
a. 8, (0))
we obtain
( (0))
V3C (0)) + (0)
a. T
Σ
0.
00
00
R=
by
a 3;1))
20

---

Published as a conference paper at ICLR 2024
Therefore, obtain
(0) 00
3p V)((0,8;(0) + Σ nakaz = Vost (0)).
(12)
1=1
where we define Yhe
(be- (9
Further, note that A = (Ip, -Ip) Thus the first rows of A (i.e., 0g. 1,... p) correspond to the basis vectors of IRP, and hence a = diag(ex), where ej is the k-th basis vector of R2. Thus, considering the first rows we obtain ER-1 naaa = diag(?)..., 7p). Similarly, the bottom rows yields Σ 2k=p+1 Yadaaa
diag(% 72p). Therefore, have
2p
RO = = edia((1 + 7pt1,... 7p + 72p) = C;(0).
(13)
Substituting eq.
13
in eq.
yields
a6; (0)
(8 + C.() -- (0 - (0,8; (0))
00
V3 (;() (0) is invertable, the above equation further implies
( Vosl (0))
(14)
00
Now, combining eq. 14 and eq.
we obtain
(())
Vo (0))
M Σ
- (0, 8;
(0, (1 (0)) (0) +000)] 5g (0,
which completes the proof.
E
CONVERGENCE ANALYSIS OF THE CID ALGORITHM
We provide the convergence analysis of the CID algorithm for solving the generic compositional bilevel optimization problem which we rewrite as follows:
1 M
min F(0) = f (0,00
(0,5((0)
(15)
arg min st. 8 (5, (61 b x......v X
hy (0, 6.).
M
Challenge and Novelty. We note that although bilevel optimization and compositional optimization have been well studied in the optimization literature, to our best knowledge, there have not been any theoretical analysis of compositional bilevel optimization. The special challenge arising in such problem is due to the fact that the bias eπrоr caused by the stochastic estimation of the compositional function in the outer-loop is further complicated by the approximation error from the inner loop. Our main novel development here lies in tracking such an error in the convergence analysis.
To proceed the analysis, we w (0,8) denote all optimization parameters. We denote by || the E norm for vectors and the spectral norm for matrices.
We adopt the following assumptions for our analysis, which are widely used in bilevel and compo- sitional optimization literature (Grazzi et al. 2020a Ji et al. 2021 Ji & Liang 2021 Wang et al. 2017 Chen et al. 2021b).
Assumption 1. The objective functions gb. and h4 for any i 1, 1,... M satisfy
21

---

Published as a conference paper at ICLR 2024
is Cy-Lipschitz continuuuss and Ly-smooth, i.e., for any and 2',
[f(=) - f(=)) < Cy|l2 -0---111 2/11- [V ( S L z'11. is Cg-Lipschitz continuous and b -moothh, i.e. any and w',
(16)
[[a(w) ge(w")] - Cg Cyll w'll: V[ Vsi(w')l S Lo - w'll w- h4 is Li-smooth, i.c., for any and w',
(17)
[[hh(w)> - Vha(w')ll & Ln w w'
(18)
The function (., 5) for any : M is p-strongly convex w.r.t. and its second-order derivatives VoVsh and (w) are Les- and L8s- Lss-Lipschitz i.e., for any and w',
Assumption 2.
VoVahu(w) VoV s Las| wallwwvll w'll [| (ih,(w') Lan | w' ||-
(19)
Assumption 3. The stochastic sample gi for any i = I,.... .....,M. M has bounded variance, i.e.,
M
E. (=
Σ 95 0, Soz
(20)
M
The following theorem (as restatement of Theorem characterizes the convergence rate of our designed CID algorithm.
Theorem 2 (Re-statement of Theorem Suppose that Assumptions 2 2 hold. Select the stepsizes
as Br = J and nh E 13 1), and batchsize as [B] = OTT). Then, the iterates Oz, = 0, ..., T of the CID algorithm satisfy
E VF((0)) I 10 / 1 (1-ap1)
T
In the following two subsections, we first establish number of useful supporting lemmas and then (which a restatement of Theorem
provide the proof of Theorem 2
E. SUPPORTING LEMMAS
For notational convenience, we let L max(Ly, Lg Ln}. max(Cy,, and max Los, L88).
Lemma 1. Suppose that Assumptions and hold. Then, the total objective F F(6) (defined at the outer level of problem [15) is Lp-smooth, i.e., for any 0'
|VF - VF(0)) < LF LF 0'
(21)
where LF C2L (1+ + CLa
Proof. Applying the chain rule, we have
VF(0) 0g (00,55
V (g (0
(22)
00
Therefore, using triangle inequality. we obtain
0g (0. 8 (0)
V (g (0,5 0g (0' (0')8'(0))
|VF(0) - VF(O)
00
20
0g (0, 8" (0))
(Vi 8" (0)) (g'
00
0g (0, 8* (0))
0g (6', 8" (0)))
+||
00
00
22

---

Published as a conference paper at ICLR 2024
0g (00,88()
08
0g (0. 8 (0)
0g (6' (8))
(0 (0))
00
00
|ا 0g (0, 6
|| (0) 9 (0'))(0))))
00
+ Cyll Og (0, (0) 0g (0', 8
(23)
00
00
The chain rule yields
dg: (0,6] (0))
067 (0)
og: (0, 50 (0) + =Vogi
Vag. (0, (0)
00
00
=Vog: (0. (0)) Vo Vah, (0. (0) Vigh (0)
Vagi (0)
where the last equality follows from the implicit differentiation result for bilevel optimization Pedregosa (2066 al. (202T).
Thus, we obtain
Og. (0, 81 (0))
00
( < Vog (0, (0)) |0 || (0. (0) [ith, (0)) Vog. 'o9, (0,) ||
I.
SCg + p
Cg.
(24)
Therfore, 9 |0, (0)) =
1 M E 9: (0, (0))) is Lipschitz with constant CG = Cg (1+
Further, following from Lemma 2 in Ji et al. 2021) we obtain that 001),5- is Lipschitz with the constant L.- Thus, combining with eq. (23 we obtain
8e
|VF(0) (F sT, - 0'll + Cylallo 0'll
(25)
Rearranging the above equation completes the proof.
Lemma 2. Suppose that Assumptions 7 and hold. Then, we have
2n 02
C²
Es| [1l1u+1-99(00 6th >1( s (1 (000l1l49((001,06600 1111+1+++++
(1+x2)]10,-0
(26)
B
1/c
06 09 is x-Liscchitz. To explicitly write the dependency of 6,, on dc. we
Proof. We first show that
define 65 (0c) = 8% Then we have
1 (0) 8. [0')
[Ix (0th (5k-1(() (0) Vah (0,0 - IIx (0th (ok<-((0) - aVsh; (0' ((0)) ||
8 3k-1((0) - sh, (0, 10. (0)) - (0') + s/,
6, -1 (()) 6th 100)) + (vsh, (0', 8, (10)) Voh. (0' 8,th (6)))
2.
+ +all Voh, (0', ((, - Vah. (0, 8k (())
L 1- 14
|,.0K (() 5t (0)) || aT. 0 0'|l
L+
where we upper-bound the term Ti using the fact that the operator y + y - Vh(y) is a contraction mapping with the constant L- for an L-smooth and p-stongly convex function h when the stepsize
L+u is set to ,t Hence, telescoping the previous inequality over & from K 1 down to 0 yields
K |,]((0) - 550 + - 8'
K
L p k
||0 (8')) s 1)
Σ
L + p
k=0
23

---

1-th Published as a conference paper at ICLR 2024
aL 0 0'| x 0'I1,
<0
(27)
L-
L+4
where the second inequality follows because 8, (0) equality follows by setting the stepsize a to L+#-
60") as the same initial point, and the last
Denote d, (1-n)) ne) 0 g(0c-1,0 We can then obtain
M Σn (g: (g: (,, 9:(00-1, 8 o1)
2 (1 - 1/.22
de
Σ
(Ot, 05:) 0,00)1,00(=211
M
i=1
(1 1/
M
02 (10=. - 00-111- + + kkK
- 1l²))
M
(1 n1)
M
C2 + n²)]|0r - -0.-1l'
M
i=1
-(1 N1) 310 + n² )² -0--112
(28)
Recall W++1 = (1 - -1)) + m (0,, :k; B). Thus combining with the definition of de, we have
Es |||| [c+1 - g(0,, 8,²) + de ||
-Eg| (1 111 (u+ g( 1, 6th 1) + no (g(0), ; g(O,, o8 )) ||
=(1 n |1 g(0 _ .) || + | 8t B) g(O,, 6f |
21 n1)n (ux g(0 1, 1)
; E3 (g( 8t B) g(O,, 5, )))
n² E, 9i 85) g(O,, 8,55 )|²
=(1 no 1 g( 8 1>1 +
[
<(1 || - 0(0--1,8 1)
+
(29)
[
Based on the inequality ||a+ + bb1² s (1 + |||||| we have
+ (1 + |)|b|1* for any c O, by letting c nec
EB ur41 - g(0,, 8 )|² <(1 + 1)) u++1 - g(0,, 8, ) + dell + (1+ + - [dlllddl?
(1 (1+
<(1 + me n1) - t/ ) U1 g 110-1 1, 8k 1|
[B] oz
1 + nle (1- x3 c 10, 01-
+
2n
C2 - (1+
<(1 - mc 11 g(0 101 +
02 +
1/
B
m/.
(30)
Hence, the proof is complete.
Lemma 3. Suppose that Assumptions 7 Iandd 2 hold. Then we have
0g (f,, (0,,5* (8.)) - gg(0,, /| S Ss1 az1) Do.
(31)
00
where Ag = maxi, (0.) - 60 2 and 52 = 0 ( 222
+ T. (K+ x )3)
Proof. The proof follows the steps similar to those in the proof of Lemma 3 in Ji et al. (021).
In the following, we define A 2( aqj) K Ao
24

---

Published as a conference paper at ICLR 2024
Lemma 4. Suppose that Assumptions / 2 hold. Then, we have
(g((()+))) - F((.) - -
= + 3.1' - axp)
+ +m0e:lo(0,,0"') r+tll/ + 2
Lp
0a
(1+
1 2
_)
(32)
p
where 04 = 2 1 -. C² (1 (1+ 11) 1
Proof. Based on the Lipschitzness of V (0)) in Lemma 1 we have
1(0(+1)- - F(0.) s (VFF 0++1 0z) + Lp 00+1 - -0112
< 3. 3. VF + B. ( (VF(O)): VF(O.) ; V (wnt1))
3e
| : B)
+ 2
s - 3, VF(()|| + Be (VF())) VF(O) -F(0))))(())))000 (F
A + 3: (T7(0)).9(00.0 ) VS (0(0,, (0,0, ()V
A2
3e |5 8x; ()++((+)))))
+ 2
(33)
Next, we upper-bound the inner product terms A₁ and A2, respectively. Using Young's inequality, we obtain
81
8t (VF(.)) Vg ot /V (000, 1|
A
[F((0)]
81
[F(())] + + Og (0c, (0:)) | (0,. 8" (6:))) Vf (9(0r, |2
00
f (9(0,, )) |//1 Og (0,, 8" (0.) pg( 8.h )|²
00
|/(())] 2 + 3.13L311 1|9 (0,, 80 (0.)) g(0,, )1 8
- Og (0,, 5" (0.)
Ag(lr. 8 )|
00
2L M M
VF(0))]
19s (0., (0,)) - g::00 o%)) + 3,02A
2
8
C. |F((0))1
M
Σ (0.) - +.B.2AA
M
8 |V1(O)11 + +3.131200 (1 =pp) M
M Σ (10((0.)) - -60l2 + 3,02A
8 |F(0N)12 1...3,2222000 Ao - + B,C au) Do
81 [F( ( +.31.o (1)))k
(34)
where r = 12 + C2Ω, Ao max:, (10)(0) - -boll and A = -2(11 -ap))
Further, we have
EgA,- =B (V.())) Vg(O,, ,K; (g(0,, - gg(0,, 8k (BBVBB((HH)))
25

---

Published as a conference paper at ICLR 2024
[F E8 [g ";; 13) V (g(0). vf(u++)]]]
[ Es | s5: B3)
| ((; of -++1ll]
L
Sn1Es|19(88 (0c. 8 - ut+1 112 +
VF((:) BB| V g( o5 /3
T
SmEBBs (acEEs|l((0e00 (Oc, 8th) u++1
|1
(1 + (²
(35)
where the last inequality uses the upper-bound (0,, 8 S c c. which can be obtained similarly to eq. (24.
Therefore, taking the conditional expectation Eg in both sides of eq. (33) applying the bounds
for A, and EgAz in eqs. (34) and (35). and noting that Es (g o. (u)))(+ I
C² |g(0,, ok; B] S Ca
+
L
we obtain
Br
EgF((0+1) - F(O.) S
V
(O.))
+ 3T - aaN) mmEBsllg00: 8/6 ue+1 11?
2
L C²
[1 4t)
||]F(0)]]2= + LESE 0t
(1+
L)
+
2
1
1
BiL?
(1+ 11 11))) ||F(())]] + +TrDD - axp)
< - 81
C²
2
1/1
+ Eg laca|g(0,,, 5 - -e+tll + Lr
(1+
T. 2
2
Then, the proof is complete.
E.2 PROOF OF THEOREM 2 (I.E., THEOREM 1
Denote Vi2 = F(:)) + ,, uz 1.. Then, using eq.
32
we obtain
EgV441 - V/2 ك - 3,00 VF( [ +
51.T -ax)*
(gg(0- 5k - uel 1
L 2
uetill 11 2 8 (L+
+
11
< - 3,01 VF( 11 ay1) K - -19 8 well 2|
+ (1 (1 -1 9 -uell uell²+ 2(1 + m1)
m
[B|
(1+
2
1
Ca (1 (1+
(++))
L 2
+ +1++m
+
(36)
1/1
where the last inequality follows from lemma 2 Further, following from the fact that (1-7))(1+ (1++))
=
1 Tie < we obtain
2(1 + m)
3. -auu)* + EgV411 V - 2F))
[B]
1 th 8C (1+ 11) +
2
1
(1+
L (37)
+ 2
tte
Now, select 7/ E 1) and 3e such that ot i.e. Br 21+09
Hence, taking total
expectation of eq. yields
EV - EV, < - - [ + (1 -ap) +
402 [
26

---

Published as a conference paper at ICLR 2024
+48,0 (1+x2) (1 1+ (1+
11) 4)²² + 1 I (1+
11
A: | + 3. ap)x + 40
+ B.
(38)
4
B
where we define Dx (1C + x²) bト) (1 x)²² Ct Therefore, telescoping eq. from to T - 1 yields
38
over L
T
TT +1 (ap))
T-1
EV Vo S
E (0.)l
+
K Be
Σ 1=0
+ Dr
Σ
B
B
t=0
1=0
Thus, rearranging terms, we obtain
3,
160 + BC B
ΣT- T-1 8
AVo
4r - ap) + +DD,
0=
+
(39)
Σ
3
Σ 3.
Σ1
Br
Hence, the proof is complete by choosing the batchsize [3] = O(T) and stepsize 3,
1
/T
27


Reviews:
[{"review_id": "Xe2xrHh8ov", "reviewer": "Reviewer_u17N", "summary": "This paper proposes a instance reweighting based adversarial training (AT) framework. Consequently, the authors follow the setting of Zhang et al. 2022  (bilevel optimization formulation for AT) and add the instance reweighting mechanism into it. Moreover, the authors seek to  build a model in the outer level problem that is robust not only to the adversarial examples but also to the worst-case attack distribution.  Compared with the exisiting instance reweighting AT methods, the proposed method  obtain the importance weights by distributionally robust optimization (DRO). The DRO is a more sophisticated choice than the heuristic/geometric schemes of instance rewweighting. Furthermore, the authors propose an equivalent compositional optimization problem (Eq. (6)) and adopt the log-barrier penalty function to drop the challenging $\\ell_{\\infty}$ norm constraint. The final optimization problem is Eq. (7) and the authors modify SCGD into the compositional implicit differentiation (CID) algorithm to solve it. With some common used assumptions, the authors establish the convegence result for CID. \nIn the experimental studies, the authors compare three instance re-weighted adversarial training methods with the proposed method on four small-scale datasets. The proposed method show promising improvement on RA-PGD, RA-Tail-30 and RA-AA metric.", "questions": "1. In Eq. (7)，is the constraint $\\delta\\in\\mathcal{C}_i$ correct? The author claim that \"Note that now the constraint $\\{\\delta\\in\\mathcal{C}_i\\}$ is never binding in Equation (7), because the log-barrier penalty forces the minimizer of $\\ell^{bar}_{i}$ to be strictly inside the constraint set.\" Moreover, in Algorithm 1 Line 5-7, why need the projected operator to keep $\\delta_{i,t}^{k}$ in $\\mathcal{C}$?\n\n2. It is better to discuss the justifiability  of Assumption 1-3 for AT problem. \n\n3. The SA performance is a weaknness of the proposed method. It is better to explain this limitation. \n\n4. It is better to add some statistical analyses like  P-values, CIs, effect sizes, and so on.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and easy to follow. \n2. The motivation is clear and the equivalent compositional optimization problem is reasonable. \n3. The proposed CID method has convergence guarantee.", "weaknesses": "1. The empirical studies is not sufficient. Only small-scale datasets is adopted in the experiment. \n2. The computational analysis is missing. \n3. The justifiability of the assumptions is not discussed.", "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": "", "extra_scores": {}}, {"review_id": "iz3ZbCusQK", "reviewer": "Reviewer_bEW4", "summary": "This paper addressed the challenge of adversarial robustness on most vulnerable samples. The existing approaches adopt a instance-reweighted strategy towards improving the worse case robustness. However, there is no principled way to estimate the per-sample weight. This work combines instance-reweighting with bi-level optimization for adversarial robustness. The min-max problem for instance-reweighting optimization was solve with a equivalent compositional bilevel optimization problem.", "questions": "It is encouraged to make comparisons with more recent adversarial training methods.\n\nExperiments on more diverse imbalance degrees are necessary for more comprehensive evaluation.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Strength:\n\n1. The mathematical formulation of instance-reweighted bilevel optimization is solved in an elegant manner.\n\n2. The evaluation on imbalanced dataset suggest the worst case adversarial robustness can be improved.", "weaknesses": "Weakenss:\n\n1. The improvements on PGD and AutoAttack seem to be less significant. The more significant improvements are observed from RA-Tail-30. Therefore, it is necessary to provide more details of the evaluation protocol for RA-Tail-30.\n\n2. Since the advantage is mainly demonstrated at the imbalanced dataset, the current evaluations on Imbalanced datasets (CIFAR10 and SVHN imbalanced) are not enough for analyzing the performance breakpoint.\n\n3. Comparisons with more recent adversarial training methods are missing.", "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": "", "extra_scores": {}}, {"review_id": "LsJCnj0NRj", "reviewer": "Reviewer_6nnk", "summary": "This paper proposes a novel framework called Doubly Robust Instance-Reweighted Adversarial Training to address the issues of heuristics and non-uniform robust performance in adversarial training. The approach utilizes distributionally robust optimization techniques to obtain importance weights and boost robustness on vulnerable examples. The experiments show that the proposed method outperforms state-of-the-arts on standard classification datasets.", "questions": "See the above.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed framework addresses the issues of heuristics and non-uniform robust performance in adversarial training. The authors use a doubly robust optimization (DRO) approach that is theoretically grounded. It provides a principled way to reweight the training examples based on their vulnerability to adversarial attacks. \n\n2. Even the algorithm falls under the category of iteratively-reweighted adversarial attack, this paper has a more principled optimization formulation than previous works because its DRO approach combines two different models to estimate the importance weights of each training example, and to estimate the importance weights, which is more robust to model misspecification and can handle a wider range of distributional shifts compared to traditional optimization methods. The obtained weights are optimal for the DRO optimization problem defined in Eq. 5 (with the closed-form exact solution for the weights), rather than being ad-hoc picked. This is the most important difference form previous instance-wise or iterative attacks.\n\n3. The bilevel optimization formulation of AT gives one the flexibility to separately design the inner and outer level objectives. This enables the authors to independently construct a new outer level objective that also solves for the instance weights w, and an inner level objective for regularized attack. This flexibility allows for a more generic and powerful framework than the traditional AT formulation, which is limited to a single objective function.\n\n4. The proposed method outperforms several state-of-the-art baselines on standard classification datasets, in terms of robustness against multiple adversarial attacks. They also show that their method can improve the robustness of the weakest (worst-case) data points, which is an important property for real-world applications.", "weaknesses": "Since the algorithm requires computing Jacobian inner products to perform parameter updates in the bi-level optimization, could the authors comment on the incurred time complexity? I am wondering if the algorithm runs much slower than vanilla AT (but only improves the robust accuracy moderately).\n\nIn their experiments, the authors have compared with AutoAttack which is good, but not with other SOTA methods such as TRADES or Diffusion-based Defense (ICML 2023). Adding some more comparison method would be good.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)