On the Adversarial Robustness of Out-of-distribution Generalization Models
Authors: Xin Zou
Weiwei Liu
Venue: NeurIPS 2023 poster (2023)
Keywords: Adversarial Robustness
Out-of-distribution Generalization

Abstract: Out-of-distribution (OOD) generalization has attracted increasing research attention in recent years, due to its promising experimental results in real-world applications. Interestingly, we find that existing OOD generalization methods are vulnerable to adversarial attacks. This motivates us to study OOD adversarial robustness. We first present theoretical analyses of OOD adversarial robustness in two different complementary settings. Motivated by the theoretical results, we design two algorithms to improve the OOD adversarial robustness. Finally, we conduct experiments to validate the effectiveness of our proposed algorithms.

On the Adversarial Robustness of Out-of-distribution Generalization Models
Xin Zou
Weiwei Liu"
School of Computer Science, Wuhan University
National Engineering Research Center for Multimedia Software, Wuhan University Institute of Artificial Intelligence, Wuhan University Hubei Key Laboratory of Multimedia and Network Communication Engineering, Wuhan University
Abstract
out-of-distribution (OOD) generalization has attracted increasing research attention in recent years, due to its promising experimental results real-world applications. Interestingly, we find that existing OOD generalization methods are vulnerable to adversarial attacks. This motivates us to study OOD adversarial robustness. We first present theoretical analyses of OOD adversarial robustness in two dif- ferent complementary settings. Motivated by the theoretical results, we design two algorithms to improve the OOD adversarial robustness. Finally, conduct experiments to validate the effectiveness of our proposed algorithms. Our code is available http:://gghau...oomm/x/////00000
Introduction
Recent years have witnessed the remarkable success of modern machine learning techniques in many applications. A fundamental assumption of most machine learning algorithms that the training and test data are drawn from the same underlying distribution. However, this assumption always violated in many practical applications. The test environment is influenced by range of factors, such as the distributional shifts across the photos caused by different cameras in image classification tasks, the voices of different persons in voice recognition tasks, and the variations between scenes in self-driving tasks [88. Therefore, there is now rapidly growing body of research with focus on generalizing unseen distributions, namely out-of-distribution (OOD) generalization [56].
Deep neural networks (DNNs) have achieved state-of-the. of-tte-arttt performance in many fields. However, several prior works (59 25 have demonstrated that DNNs may be vulnerable to imperceptibly changed adversarial examples, which has increased focus on the adversarial robustness of the models. Adversarial robustness refers the invariance of model small perturbations of its input (54), while ad adversarial accuracy refers to model's prediction performance on adversarial examples generated by an attacker. However, the adversarial robustness of OOD generalization models (OOD adversarial robustness) is less explored, despite its importance in many systems requiring high security such as self- self-driving cars. We evaluate the adversarial robustness of the models trained with the current OOD generalization algorithms (the detailed experimental settings can be found in Appendix C.3). and present the results Table []] Surprisingly, under the PGD-20 44) attack, the algorithms achieve nearly 0% adversarial accuracy on RotatedMNIST (2I), VLCS 15), PACS (38), and OfficeHome 62. and no more than 10% adversarial accuracy on ColoredMNIST 4. These results show that even if the OOD generalization algorithms generalize well in different scenes, they remain highly vulnerable to adversarial attacks.
Motivated by these limitations of existing algorithms, we provide theoretical analyses for OOD adversarial robustness in two different but complementary OOD settings. We then design two
"Corresponding author: Weiwei Liu (liwweiwei863 oatpa//iii..@@mmmm..mmmcmmo
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: The results (%) for some of the eurrent OOD generalization algorithms. We present the results in the form of a/b: here, a is the OOD adversarial accuracy under PGD-20 attack [44]; and b is the OOD adversarial accuracy under AutoAttack [[2]. We conduct the ls -orm attack. for We use the perturbation radius 0.1 for RotatedMNISTT and ColoredMNIST, and T and VLCCS. For the architecture, following [26], we use small CNN-architecture for RotatedMNIST ColoredMNIST, and ResNet-50 27 for VLCS, PACS and OfficeHome. Since (64 do not realize MAT and LDAT for RotatedMNIST, we use X denote the unrealized results. For more details about the algorithms, please refer to Appendix C.I We use RMM CM, and OH as the abbreviation of RotatedMNIST, ColOredMNIST, and OfficeHome, respectively.
Algorithm
RM
CM
VLCS
PACS
OH
Avg
ERM [6
0.6/0.0
5.8/X
0.0/0.0
0.3/0.6
0,4/0.0
1.4/X
MLDG 39
0.2/0.0
4.8/X
0.0/0.0
0.1/0.3
0.6/0.1
1.2/X
CDANN 42
0.9/0.0
8.2/X
3.0/0.0
1.5/0.3
0.1/0.0
2.7/X
VREx B3
0.2/0.0
6.4/X
0.0/0.0
0.0/0.3
0.4/0.1
1.4/X
RSC 28
1.0/0.0
3.9/X
0.0/0.0
0.1/0.4
0.7/0.0
1.1/X
MAT 64
X/X
10.7/X
0.0/0.0
0.7/1.4
0.8/0.1
X/X
LDAT
664
X/X
7.9/X
0.0/0.0
0.1/0.3
0,4/0.1
X/X
baseline algorithms improve the OOD adversarial robustness, based on the implications of our theory, and validate the effectiveness of our proposed algorithms through experiments.
Our contributions can be summarized follows:
1. We evaluate the adversarial robustness of current OOD generalization algorithms and experimentally verify that the current OOD generalization algorithms vulnerable to adversarial attacks.
2. We present theoretical analyses for the adversarial OOD generalization eтror bounds in the average case and the limited training environments case. Specifically, bounds in limited training environments involve a "distance" term between the training and the test environments. We further OOD adversarial robustness, which verified by the experimental results in Section [
toy example to illustrate how the "distance" term affects the
3. Inspired by our theory, we propose two algorithms to improve OOD adversarial robustness. Extensive experiments show that our algorithms are able to achieve more than 53% average adversarial accuracy over the datasets.
The remainder of this article structured as follows: $ introdduces related works. presents our main theory. $4 shows our two theory-driven algorithms. $5 provides our experimental results.
Finally, the conclusions are presented in the last section.
Related Work
2.1 Adversarial Robustness
show that DNNs are fragile to imperceptible distortions in the input space. One of the most popular methods used to improve adversarial robustness adversarial training (AT), The seminal AT work, the fast gradient sign method (25] FGSMJ, perturbs a sample towards its gradient direction to increase the loss, then uses the generated sample to train the model. Following this line research, propose iterative variants of the gradient attack with improved AT frameworks. investigates the adversarial robustness from the perspective of ordinary differential equations. Recently, [50] 66) utilize the data from generative models as data augmentation to improve adversarial robustness. Besides, [3 analyze the trade-off between robustness and faimnsss, [37 study the worst-class adversarial robustness in adversarial training.
59
44
47
34
[1]
70
30
For the theoretical perspective, 46 study the PAC learnability adversarial robust learning, extend the work of [46] to multiclass case, 72
give theoretical analyses to adversarial training by standard uniform convergence argumentation and giving bound of the Rademacher
31 5
18
67
complexity, and [65] 78 study adversarial robustness under self-supervised learning.

---

2.2 Out-of-distribution generalization
OOD generalization aims to train model with data from the training environments so that it is capable of generalizing to an unseen environment. A large number of algorithms have been developed that aim to improve OOD generalization. One series of works focuses on minimizing the discrepancies between the training environments [40] 17 42 [8 The most related work among them is [ which measures the discrepancy between the domains by (s, T). while we focus on adversarial robustness and use d (5, T). Meta-learning domain generalization [39 MLDG] leverages the
meta-learning approach and simulates train/test distributional shift during training by synthesizing virtual testing domains within each mini-batch.
[53 GroupDROJ studies applying distributionally 13 to learn models that instead minimize the worst-case
robust optimization (DRO) [9 36 77
training loss over a set of pre-defined groups. Another line of works 668 64 conducts adversarial training to improve the OOD generalization performance. In this work, we focus on improving the OOD adversarial robustness.
From the theoretical perspective, [0] introduce a formal framework and argue that OOD generaliza- tion can be viewed as a kind of supervised learning problem by augmenting the original feature space with the marginal distribution of feature vectors. In [51], OOD generalization is cast into an online game where player (model) minimizes the risk for a "new" distribution presented by adversary at each time-step. [14 propose a probabilistic framework for domain generalization called Prohable Domain Generalization, wherein the key idea is that distribution shifts seen during training should inform us of probable shifts at test time. Notably, all these works focus on OOD generalization performance, while we present theoretical results for OOD adversarial robustness.
2.3
Works relating domain shifts and adversrial robustness
8 focuses on improving the adversarial robustness of the models by regarding the adversarial distribution as the target domain and then applying the domain adaptation methods, while we focus on improving the model's adversarial robustness on the OOD distribution. [7I] studies the relationship between adversarial robustmess and OOD generalization, it shows that good adversarial robustness implies good OOD performance when the target domain lies in a Wasserstein ball. While we study the OOD adversarial robustness and propose algorithms to improve OOD adversarial robustness. 2 empirically analyzes the transferability of models' adversarial/certifeel robustness under distributional shifts. It shows that adversarially trained models do not generalize better without fine-tuning and that the accuracy-rou -ooussseoo trade-off generalizes to the unseen domain. Its results for adversarial robustness can also be found in our experimental results. (29 investigates how to improve the adversarial robustness of model against ensemble attacks unseen attacks. 2 regards the adversarial examples for each type of attack (such as FGSM, PGD, CW, and so on) as a domain, and utilizes the OOD generalization methods to improve the models generalization performance under different (maybe unseen) attacks.
45 22 study the relationship between the dependence on spurious correlations and the adversarial robustness of the models and show that adversarial training increases the model's reliance on spurious features. [60] studies the relationship between fairness and adversarial robustness and shows that models that are fairer will be less adversarially robust. However, they do not consider the adversarial robustness of the model on the unseen target domain, which is the topic of this paper.
Theoretical Analysis for OOD Adversarial Robustness
In this section, present two theorems in two different settings, each of which inspires an algorithm designed to improve the OOD adversarial robustness. The proofs of all results in this section can be found in Appendix A
We first introduce some notations and basic setups.
Notations. We define [n]] == ==,,,, 21,2,-.. ... .n). We denote scalars and vectors with lowercase letters and lowercase bold letters respectively. We use uppercase letters to denote matrices or random variables, and uppercase bold letters to denote random vectors or random matrices. For a vector z E R", we
1/r for p E 00), where z; is the i-th element of x; for = co, we define |0||00 == max [2s]. For matrix A E gmxxa the Frobenius norm of A
define the f--norm of x as |0||p- == (E (xr)))>/*
15i5n
3

---

AR) EE
where As is the entry of at the i-th row and j-th column. We define the determinant of A as der(A). (u, Σ) represents the multivariable Gaussian distribution with mean vector and covariance matrix Σ. Given f.g. R + R+, we write f f= (g) if there exist z0. a E RR+ such that for all z0, we have f(z) S ag(z). We use sign(.) to denote the sign function [57].
defined as ||||| =
Setups. Let X' I be the input space and y be the label space. We set y = {+1). y (1, .... } (where K' is the number of classes), and y' = IR for the binary classification problem, the multi-class classification problem, and the regression problem, respectively. We use É: y x y R+ as the loss function. We consider learning with the hypothesis class H C {h: :h::2' - VJ. Given a distribution D on X' V. the error of h H with respect the loss function & under the distribution D is RD(e, h) (#.y)~
E [L(h(x), y)], where I E X' and y E V. We further define B(-): : X + 2
as a perturbation function that maps an input to subset B(x) C X, where 2 is the power set of X. The adversarial error of the predictor h under the perturbation function (-) is defined as
RB h)
E (#.1))~
sup ((h(z') x'EB(x)
3.1 The Average Case
In this section, following 20 target environment follows distribution. In this case, we aim to minimize the average target adversarial error of the hypothesis E H. where the average is taken over the distribution of the target environment.
14 52],
we consider the average case, i.c., the case in which the
Suppose that P(X x y) the set of all possible probability measures (environments) on x y for the task of interest. Assume there is prior p P(X' x }), which is the distribution of the environments. Moreover, suppose the process sampling training and test data is as follows:
(1). We generate the training data according to the following two steps: (i) we sample t training environments from p. i.e., D1, Dr p; (ii) the examples D. = {( Vi))... (Zing: Vin.)) }} ~ DI drawn independent and identically distributed (i.i.d.) from D., where ny is the size of D. and i E [t]. To simplify the notations, we also use Dj to denote the empirical distribution the dataset ((z.,,9a) -.. (Zin, : Vin. }}. Let D = Ei= D. and P Σ Dj. To simplify the problem, we assume n1 n2
n, n, but note that with a more careful analysis, our result in the average case can be extended to the case in which ni, Ti are not necessarily the same.
(2). For each test example, first sample environment from p, i.e., D p, then sample an example (I, D.
Let (e, = EE (R [t]] be the average risk of h on prior p. For the perturbation function Dmp
[RS(e, h)] as the average adversarial risk of h. The empirical Rademacher complexity (55 Chapter 26] of the hypothesis class H is defined follows:
B(.), we define C (c, = E
D-p
RA (7)) E
sup NE n2
1
Σ o,h(x;)
where is Rademacher random vector with i.i.d. entries, and (æ1,'.. Ix } is set of data points. The following theorem presents an upper bound for the average adversarial risk of h.
Theorem 3.1. Suppose the loss function E is bounded. i.e., E E [o, U}. Then with probability of at ,,, ,D,, the following bound holds for all h E H:
least 1 - 8 over the sampling D1, ........ ...
In4/5
In4/6
cB(C,)) S (C, L
(9) 22..((9)) + 3U
+ 3U
V
21
2tn
where
ğ =
Ih : X' x + R+ (x = sup E(h(x', (ol.))), E H x'EB(z)

---

Theorem 3.1 presents bound for all hypotheses h E H. We now consider the convergence property of the adversarial empirical risk minimization (AERM) algorithm the average case. We define the output of the AERM algorithm as h E arg inf C (C, h). We then define the hypothesis with the best
adversarial generalization performance as h E arg inf F (c.
hEH
The next corollary shows an upper bound for the excess risk [63 Chapter 4] of AERM:
Corollary 3.2. Suppose the loss function & is bounded, i.e., & E (0, U.. Then with probability of at least 1 over the sampling of D1, ,Dv, the following bound holds:
In8/8
In8/8
(e (E(,,)) (R)(G) + 4Rn 3U
+ 3U
26
21n
Remark 1. The convergence rate for both Theorem 3.1 and Corollary 3.2 O ( which prompts
us to ask: can we derive a tighter bound that has faster convergence rate than O ()) The next section provides an affirmative answer to this question.
3.2 Theory with Limited Environments
In this section, we provide the theoretical analysis for the limited training environment case, i.e., in the case in which (1).. Suppose that we have training environments Di. Dr and one unknown target environment T. Our goal is to find predictor that obtains good adversarial robustness on the target enviromment T. Assume we obtain examples from each training distribution D;.
First, we introduce a discrepancy between the distributions. Based on the hypothesis class H, the seminal work for unsupervised domain adaptation (UDA), 9 defines the discrepancy between two distributions as follows:
(D, (D, D') =2 sup P [h(x) 1|- NEH I=-D
[h(x)) 11/.
9 analyze the generalization error bound of the target domain for UDA by dHaH(:;))) where E H.H.. < h + h' for some h, h' E Hi here, t is the XOR operator. However, the above definition limited the binary classification. This paper extends dx to the multi-class adversarial case. Given the loss function f, distributions P, Q on X' x V/ and hypothesis class H. we define the adversarial discrepancy as follows:
(H(2)) (P,Q) sup hEH
sup ((h(z').)) (2.y)~P x'E((x)
E (a.g)~~
sup E(h(z'), v)) r'E((x)
When B(x) = (x), de (()) (P. Q) becomes the standard case. It can be easily verified that d symmetric and satisfies the triangle inequality (the proof can be found in Appendix A.3 thus, di (( (:.)) is pseudometric.
(.:.)
((2))
(s) The theory outlined in 9 Theorem 2] presents an upper bound with (=.-)) term. To align the feature distributions of the source and target domain, need to calculate dHAR Q), which takes the supremum over two hypotheses h E H:
Comparison of d=(+.)) and (:)))
dHAH (P Q) = sup [Mxx + M(x)) h.KEH INP
H~Q [M(x) + 1 f'(x))
However, the definition of d shows that: ()( (P, Q) takes the supremum over one hypothe- sis H. which is easier to optimize (76 and can thus significantly ease the minimax optimization in Section 4.2
Theorem 3.3. For a given but unknown target distribution T, let A-11 = (AA ;A)lA > 0, -. X 1} be the (I 1)-dimensional simplex, and Conv (D) = {Ei A.D,)/ be
the convex hull of D = (D....., Det. Let Tp E arginf dis (H))) (D, T) be the "projection" of DECom(D)
5

---

onto Conv(D), and X be the weight vector where Tp = Ex=1 N;D, Assume 8 E [0, U/. Then: with probability of at least 5. for all h E H.
he,
R (4)) + EE Ngde(no (D) + +d/(70)
(T, +d))+
TT)
In8/0
(n(1161/8)
4R (g) + 29n (9) V
+ +3U
2tn
2n
Remark 2. The first term the bound is the average empirical adversarial robust error of the model on training environments, and the second term is the weighted average discrepancy on the empirical training distributions D (D1.... D.).. The third term can be viewed as the distance between T and the convex hull Conv (D), which fixed once the task, E, E.D and 'T are given. Thus, minimizing the first two terms of the bound is able to improve the OOD adversarial robustness.
Moreover, (9) and (9) meusure the capacity of the model, and can be regarded as an implicit regularizer the model. There are many existing works that present the upper bounds of the empirical Rademacher complexity for neural networks [49 6 [33 and the adversarial Rademacher complexity [31 73 18 5 677. Their results be sunmarized as follows: for bounded X. with proper weak assumptions on the loss function e, Ry (9) can be upper-bounded by O (((a)) where C' is a constant that is related to some norm of the parameters of h and increases with the norm. Thus, we consider constraints on the norm of the parameters of h in the algorithm designing part of Section
Last but not least, different from the results in Theorem 3.1 the convergence rate is o
(V
16 in
bnt/66
When O(1), o (
int/8 in Theorem 3.3 converges much faster
18 t
than
in Theorem 3.1 since n > t.
dbe 3. deesll das Jkesin
O
The ( (T,Tp) term in Theorem 3.3 is de- termined by the distance between the source (T, and target environments. A larger (T, Tr) may lead to worse adversarial robustness of the model on the target domain. Next, we present a toy example to illustrate this case.
des deenna
Example 1. We consider the input space X = Rd C m and label space y = (+1,-) -1.. For simplicity, we consider only three dis- tributions on X x D. i.e., D(O)_ D(1) and D(2), The marginal distributions for Y satisfy
Figure 1: An intuitive visualization of the distri- butions D( D(2), ((2) (red, green, blue respec- tively). We also represent the three mean vectors μ. Qu, Q² using red, green, and blue arrows. The angle between μ4, Qu is a, which is the same the
((-1)) = D. (0) ({+1)) = (1=-1)))=((((())) ({-1))) =
D ((+1)) = D ( (f-1)) D. ((+1))
3. For D(,, let the conditional distribution of ( given Y be (0 1000Y=y-- y 0,021),
angle between Qμ, Q²,r. More details about the relationship between Q and a can be found in the proof of Theorem A.4 in Appendix A.
where (1) E Rd is a non-zero vector and
8 Rdxd is the covariance matrix, i.e., the elements of X are independent. Let Q be a rotation transformation on IRd, which is special or- thogonal transformation. Suppose that Q / I. where I is the identity transformation. Let Q Rdxd be the matrix of Q under some orthonormal basis. We then know that Q is a rotation matrix and Q²Q QQ" I, det Q) = Q, + I. To model the distributional shift among the environments, we apply the transformation Q to (0) and use (1) Q) 22 = Q² as the mean vectors of D(1), D(2)
((2) respectively. Here, we consider the f-rmrrm adversarial attack with radius e, i.e., B(x) = {x' || x') ||2 < e). We use two environments as the training environments and the remainder as the test environment. Theorem 3.4 shows that larger distance between the training and test environments leads to worse OOD adversarial robustness.

---

Theorem 3,4. Consider the setting in Example 7 and suppose that μ lies in the 2-dimensional
subspace R in Theorem A.4 see Appendix A. for details about R, and see Figure an intuitive
visualization), Let foi (T, B) = [ + v). where [.] is the indicator function and (x) = {x'
|>>->>/lp S r. Consider training with hypothesis class H = +flw (x)) - sign(w) x), w E IRd), and denote D 2D(6) + 1D()),, j {0, 1, 2). * j. Consider the E--norm adversarial attack B3 with radius e; for notation convenience, let Raj(w) Disss) hww) and andRR.(u Ri(w) Risss (Co1, hw)- Let (.)) be the distribution function of the standard normal distribution. Let denote the angle between il and Qu, which is the rotation angle of Q in the subspace R. Furthermore, suppose that O a CrrcosSTiill 2 We then have:
(1) If we train with D(0) and D let 11o which achieves the minimum of Roi (w)) Then
the adversarial accuracy of (01) on the test distribution DD2) is (2) ( ( (u+ Q*H
allutQulla
(2) If we train with D(0) and D(2), let w (02)=+++Q' which achieves the minimum of (Ro((w) Then the adversarial accuracy of (2)) on the test distribution D(1) is R1 (w
(u+ "
)
(3) If we train with D(1) and D(2), let (112)=Qu μ.. which achieves the minimum of R12(w) Then the adversarial accuracy ((2) on the test distribution D(U) is (o((((22))
(Qu+Q²u))
Qu Qu-
(4) Ri (22)) < R2( = (1)
Remark 3. Let ki.j.k} = 1,2]. For task i, we use DO,, D(K) as the training environments and
D() as the test environment. R. (w is the target adversarial error of the learned classifier w(yk) in task i,
We now consider the distance between the training and test environments for each task. Intuitively, we regard the angle as the "distance" between two distributions. We define angle(i, as the angle between the mean vector of D(5) and D(i), + j. For task i, we define the average "distance" between the test environment and each training environment as dave (i) amgleli.j)++amgliia We use davg (i) measure of the distance between the training environments and the test environment for task i.
From the settings in Example 1 it can be clearly seen that dave (0) = amgle(0. tannlee()))) +++2
2
30 2 (2) and dave( angle(1 (1)) +)+
a a, which implies that dayg (1) < davg(0) = 2
davg(2), Theorem tells us that R1 (w)) < (1) Ro(( and thus implies that a smaller distance between the training and test environments leads to better OOD adversarial robustness.
Moreover, the assumption of the angle between a and Qμ in Theorem 3.4 is reasonable. Consider 22, in this case, the attack is strong and perceptible to human eyes. Then, S arrcos Tpilla 25. 1 = -. In this cuse, the maximal angle between the environments is 3 which leads to
== [Iull arccos] strong distribution shift.. When e < ||A the allowed rotation angle can be further enlarged, and when e 0, it becomes the standard case.
2
Furthermore, the data distribution here can be regarded as a simplified data model for RotatedMNIST. Moreover, our experimental results in Section 3 are consistent with analysis here in both the standard and adversarial cases. Please refer to the observation part of Section 5.2 and the table in Appendix for fürther details.
4 Algorithms
In this section, based on our theory, we present two algorithms that can improve the adversarial robustness of the model on the target environment.
7

---

4.1 Adversarial Empirical Risk Minimization (AERM or AT)
Based on Theorem 3.1
which shows an upper bound of the average adversarial risk over the environments, we propose our first algorithm: adversarial empirical risk minimization (AERM, which corresponds to applying AT to multiple source domains). The bound in Theorem 3.1 consists of the average adversarial empirical risk (e, h) = E R g (e, h) and two empirical Rademacher D.
complexity terms (g) + Re (g). As outlined in Remark 2 the empirical Rademacher complexity
implies an implicit regularizer on the model capacity. We choose F as regularizer the model
parameters. The optimization objective of AT is as follows:
(h) = Σ i=1
R
D.
(e, WIWWE
t
where À a trade-off parameerrreeeer, and W is the parameter matrix of the model. From Remark [ know that AT may not generalize well in the case where the training environments are limited. Next, we propose another algorithm for the limited environment case.
4.2 Robust DANN (RDANN)
Theorem 3.3 shows that R., ビ R. (C, and
(D, (D., roles in designing the OOD adversarial training methods. However, the weights X; unknown, since we have no information about the target distribution Since X E [0, 1]. Vj. it is
play the key >; are
evident that Σ, X3 ( (D,, D2) E. (00 (D:, Dj)- We therefore turn to optimize
the average discrepancy E: E, d ((H)) (D., D,). To improve the OOD adversarial robustness, minimize the following:
Σ R (L.h) ( D.
ΣΣ (( (D., Ae||W]]F
where Å1 A2 are two hyper papprr-arammterss. and W is the parameter matrix the model. However, the term # Di= Σj= de (Di, Dj) is constant. Motivated by [7], we minimize the discrepancy of the training environments in the feature space of a feature extractor S.
Specifically, we consider H = {c I'I E F.c e E C); this means that the predictor h consists of (c:
classifier and feature extractor f. where F= [f X' + C= 2 + }} and 2 C IR is the feature space. Any feature extractor f E F determines hypothesis class H, {co flc E C}. Given a feature extractor f, we apply Theorem 3.3 to the hypothesis class H. Then with high probability, for any C, the target error of h co f can be controlled mainly by _ E Rg (c,
and J Ej (D, We then aim find e and f such that co f has good OOD adversarial robustness. Thus, we aim to minimize the following:
L(cof)
R (4,co +\
R HH
D,, +
Tes(hho0f)
(F.f)
To minimize L(co f), we need to solve minimax problem. For simplicity, we fix B(-), and define the following:
E(h(('') v)
P.h,
E
sup x'EB(x)
EE (
sup EB)((
((h(=') (,
(P
Since D(h, P.P). 0 and D(h, P,Q) = D(h, Q, P) for any P. Q, h. our optimization problem can be formulated as follows:
min
Le, f) 1(t-1)
2
Σ
D(g o J,D., >ellW]le.
CE oy cisiss
8

---

Table 2: The results (%) of the algorithms. Results are presented the form of a/b: here, is the OOD adversarial accuracy under PGD-20 attack [44]; and b is the OOD adversarial accuracy under AutoAttack [12]. We conduct the - no-noom attack. Since 664] do not realize MAT and LDAT for RotatedMMNIST we use X denote the unrealized results. Best results for PGD-20 attack are shown bold. For more details about the algorithms, please refer Appendix C.I We use RM, CM, and OH as the abbreviation of RotatedMNIST, ColoredMNIST, and OfficeHome, respectively.
Algorithm
RM
CM
VLCS
PACS
OH
Avg
ERM
0.6/0.0
5.8/X
0.0/0.0
0.3/0.6
0.4/0.0
1.4/X
MLDG
0.2/0.0
4.8/X
0.0/0.0
0.1/0.3
0.6/0.1
1.2/X
CDANN
0.9/0.0
8.2/X
3.0/0.0
1.5/0.3
0.1/0.0
2.7/X
VREx
0,2/0.0
6.4/X
0.0/0.0
0.0/0.3
0.4/0.1
1.4/X
RSC
1.0/0.0
3.9/X
0.0/0.0
0.1/0.4
0.7/0.0
1.1/X
MAT
X/X
10.7/X
0.0/0.0
0.7/1.4
0.8/0.1
X/X
LDAT
X/X
7.9/X
0.0/0.0
0.1/0.3
0.4/0.1
X/X
AT (ours)
93.4/93.3
51.6XX
42.6/41.8
48.1/47.6
30.2/29.8
53.2/X
RDANN (ours)
93.5/93.3
51.1/X
44.9/43.9
48.1/48.0
28.6/27.4
53.3/X
To solve the minimax optimization problem, we adopt an idea similar to that of adversarial neural
networks [24] and refer to Gij as the discriminator. However, there are = case, and training with many discriminators may make the optimization process unstable [3]. We
((t-1) discriminators this
therefore opt to use the same discriminator for all (D,, D2) pairs. Note that:
Σ (, S max max of EC
o D,
such that optimizing shared discriminator d' is equivalent to optimizing lower bound of the original objective. Our final optimization problem then becomes:
min max Len(e, +i1 t(t - 1) FEF e'EC Le(w,8)
Σ Isicist
o f.D, o +h2 W
Luee
Le(w²(8
where w, w', 0 are parameters for c, C respectively. We call our method robust adversarial-domal neural network (RDANN), the pseudo-code of which is presented in Algorithm I
Algorithm RDANN
Experiments
Input:
the training data DI,..., De, the num- ber of iterations T, the number of iterations for the inner maximization problem k, the learning rate 7), the inner max learning rate a, the tradeoff hyper-parameters \1 Xg- Output: the parameters w" HT for c. 1: initialize w 800 =h randomly for i to T do
To verify the adversarial robustness of our algo- rithms, we conduct experiments on the DomainBed benchmark (26), testbed for OOD generalization that implements consistent experimental protocols across various approaches ensure fair compar- isons. Our code is attached in supplementary material.
3: set w: <- with
5.1 Experimental Setup
for jorj+n + 0
do
5: ((++) t w + a V w La(w's aawwi,0) 0¹)
Datasets. The datasets we use are RotatedMNIST
(21), ColoredMNIST [4) VLCS [15). PACS (38). and OfficeHome [62]. There
end for
several different
7:
"0u',0') 00) + A A2 L + Lo(w",
environments in each dataset. For the DomainBed
8:
L + L + >3 Lu (0))
g t- 0¹ 17 V
benchmark, we choose one environment as the test environment and use the others as training envi-
10: w++1 +- w - n/ L
ronments. We report the average accuracy different choices of the test environment. Further details about the selected datasets can be found in Appendix C.2
11: end for
we use small CNN architecture for RotatedMNIST. Col- oredMNIST, and ResNet-50 27 for VLCS, PACS, and OfficeHome.
Backbone network. Following 26

---

Sayeer-arraeetes for adversarial attack and adversarial training. We use fxc fo-m attack for both adversarial attack and adversarial training. We use 0.1 for ColoredMNIIT and RotatedMNIST, and 4/255 for VLCS, PACS, and OfficeHome; moreover, following [74 (5]. we use PGID-0 to generate adversarial examples the training stage and PGDD20 the evaluation stage to avoid overfitting The step size used to generate adversarial examples is set to be e/4.
More details of the experimental settings can be found in Appendix C.4
5.2 Results
Table presents presents the results of our experiments. As is clear from the table, our proposed algorithms significanlly improve the OOD adversarial robustness of the model. For example, under the attack PGD-20, all other algorithms achieve no more than 3% average adversarial accuracy. while our proposed algorithms achieve more than 53% average adversarial accuracy. Moreover, in datasets, the number of environments (f) is small. From Table 2 we can see that the overall performance of RDANN is superior to that of AT. RDANN achieves better comparable adversarial accuracy most datasets (except Offec The results are consistent with our claim in Remark 2 when
== ((1), ). the bound in Theorem 3.3 converges faster than that in Theorem 3.1 The detailed results for each test environment are attached in Appendix
Observations, According to the detailed results for RotatedMNIST and ColoredMNIST in Ap- pendix and Appendix D.2 we can make the following observations (these phenomena occur in both the adversarial training setting and the standard training setting):
For RotatedMNIST, we have six environments, each of which corresponds to rotation angle of the original image. The rotation angle of the i-th environment is x 15,, e {0, 2, 3, 4, 5). For task i, we use the i-th environment the test environment and the remaining environments as the training environments. Following Remark 3 we define (6)
Ejfi angle(i, j) as the average distance between the test environment and each training environment for task i. Then, davg (0) 45% davg( = 33 davg (2) 27", (3) = 27" (4) 33 and (5) = 45% We define the PGD-20 adversarial accuracy of the model trained by RDANN for task as (t): then, a(0) 90.8, a11) = 94.77 7. a(2) 95.3, a3) = 95.6, a(4) = 95.5 and a(5) = 89.0. As i increases, davg (i) first decreases and then increases. while a(i) first increases and then decreases. The result indicates that davg(A (i) is anticorrelated with a(i), which is consistent with the analysis in Note that this phenomenon occurs all algorithms.
Remark 3
For ColoredMNIST, we have three environments, each of which corresponds to correlation between the additional channel and the label. For task E 10, 1,2), we define the correlation cor(i) and cor(1) 0.9, cor(2) 0.8, (3) 0.9. Here, define (ivg()) = Eet; cor(j) cor(i) then d1vg(1) = 0.95, davg (2) = 0.8, d3vg(3) = 1.75.
Similarly, we can define a(i) for a given algorithm. The detailed results in Appendix D.2 imply that davg(0) (i) is anticorrelated with a()). To further understand this phenomenon, present another toy example for ColoredMNIST with a different data model in Appendix B
Conclusion
In this paper, we focus specifically on -itto---dittiuttion adversarial robustness. First, we show that existing OOD generalization algorithms are easily fooled by adversarial attacks. Motivated by this, we then study the theory of the adversarial robustness of models in two different but complementary OOD settings. Based on our theory, we propose two algorithms, AT and RDANN. Extensive experiments show that our proposed algorithms can significantly improve the OOD adversarial robustness of the model.
Acknowledgements
This work is supported by the National Natural Science Foundation of China under Grant 61976161, the Fundamental Research Funds for the Central Universities under Grant 2042022rc0016.
10

---

References
[1] Isabela Albuquerque, João Monteiro, Mohammad Darvishi, Tiago H. Falk, and Ioannis Mitliagkas. Generalizing unseen domains via distribution matching, 2021.
[2] Kumail Alhamoud, Hasan Abed Al Kader Hammoud, Motasem Alfarra, and Bernard Ghanem. Generalizability of adversarial robustness under distribution shifts. CoRR, abs/2209.15042,
2022.
[3] Anonymous. Fairness and accuracy under domain generalization. In Submitted to The Eleventh International Conference Learning Representations, 2023. under review.
[4] Martín Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk mini- mization. CoRR, 0e1119077029995 2019.
[5] Pranjal Awasthi, Natalie Frank, and Mehryar Mohri. Adversarial learning guarantees for linear hypotheses and neural networks. In ICML, volume 119, pages 431-441, 2020.
[6] Peter L. Bartlett, Dylan J. Foster, and Matus Telgarsky. Spectrally-normalize margin bounds for neural networks. In NeurIPS, pages 6240-6249, 2017.
[7] Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexitie: Risk bounds and structural results. Journal of Machine Learning Research, 3:463-482, 2002.
[8] Pouya Bashivan, Reza Bayat, Adam Ibrahim, Kartik Ahuja, Mojtaba Faramarzi, Touraj Laleh, Blake A. Richards, and Irina Rish. Adversarial feature desensitization. In NeurIPS, pages 10665-10677, 2021.
[9] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jen- nifer Wortman Vaughan. theory of learning from different domains. Mach. Learn., 79(1- 2):151-175, 2010.
[10] Gilles Blanchard, Aniket Anand Deshmukh, Urün Dogan, Gyemin Lee, and Clayton Scott. Domain generalization by marginal transfer learning. Journal of Machine Learning Research, 22:2:1-2:55, 2021.
[11] Nicholas Carlini and David A. Wagner. Towards evaluating the robustness of neural networks. In SP, pages 39-57, 2017.
[12] Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-fri free attacks. In ICML, pages 2206-2216, 2020.
[13] John C. Duchi and Hongseok Namkoong. Learning models with uniform performance via distributionally robust optimization. CoRR, abs/1810.08870, 2018
[14] Cian Eastwood, Alexander Robey, Shashank Singh, Julius von Kügelgen, Hamed Hassani, George J. Pappas, and Bernhard Schölkopf. Probable domain generalization via quantile risk minimization. CoRR, abs/2200.009944, 2022.
[15] Chen Fang, Ye Xu, and Daniel N. Rockmore. Unbiased metric learning: On the utilization of multiple datasets and web images for softening bias. In ICCV, pages 1657-1664, 2013.
[16] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adapta- tion of deep networks. In ICML, volume 70, pages 1126-11333 2017.
[17] Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor S. Lempitsky. Domain-adversart training of neural networks. Journal of Machine Learning Research, 17:59:1-5::35, 2016.
[18] Qingyi Gao and Xiao Wang. Theoretical investigation of generalization bounds for adversarial learning of deep neural networks. Journal of Statistical Theory and Practice, 15:1-28, 2021.
[19] Rui Gao and Anton J. Kleywegt. Distributionally robust stochastic optimization with wasserstein distance. Mathematics Operations Research, 48(2):603-655, 2023.

---

[20] Vikas K. Garg, Adam Tauman Kalai, Katrina Ligett, and Zhiwei Steven Wu. Learn to expect the unexpected: Probably approximately correct domain generalization. In AISTATS, volume 130, pages 3574-3582, 2021.
[21] Muhammad Ghifary. W. Bastiaan Kleijn, Mengjie Zhang, and David Balduzzi. Domain generalization for object recognition with multi-task autoencoders. In ICCV, pages 2551-2559. IEEE Computer Society, 2015.
[22] Tejas Gokhale, Swaroop Mishra, Man Luo, Bhavdeep Singh Sachdeva, and Chitta Baral. Generalized but not robust? comparing the effects of data modification methods on out-of- domain generalization and adversarial robustness. In ACL, pages 2705-2718, 2022.
[23] Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In COLT, volume 75, pages 297-299, 2018.
[24] lan J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron C. Courville, and Yoshua Bengio. Generative adversarial nets. In NeurIPS, pages 2672-2680, 2014.
[25] lan J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adver- sarial examples. In ICLR, 2015.
[26] Ishaan Gulrajani and David Lopez-Paz. In search of lost domain generalization. In ICLR, 2021.
[27] Kaiming He, Xiangyu Zhang, Shaoging Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, pages 770-778, 2016.
[28] Zeyi Huang, Haohan Wang, Eric P. Xing, and Dong Huang. Self-challenging improves cross- domain generalization. In ECCV, volume 12347, pages 124-140, 2020.
[29] Adam Ibrahim, Charles Guille-Escured Ioannis Mitliagkas, Irina Rish, David Krueger, and Pouya Bashivan. Towards out-of-distribution adversarial robustness. CoRR, abs/2210.031500 2022.
[30] Qiyu Kang, Yang Song, Qinxu Ding, and Wee Peng Tay, Stable neural ODE with lyapunov- stable equilibrium points for defending against adversarial attacks. In NeurIPS, pages 14925- 14937, 2021.
[31] Justin Khim and Po-Ling Loh. Adversarial risk bounds for binary classification via function transformation. CoRR, abs/ 1es//881009911 2018.
[32] Hoki Kim. Torchattacks: A pytorch repository for adversarial attacks. CoRR, abs/2010.01950. 2020.
[33] David Krueger, Ethan Caballero, Jörn-Henrik Jacobsen, Amy Zhang, Jonathan Binas, Dinghuai Zhang, Rémi Le Priol, and Aaron C. Courville. Out-of-distribution generalization via risk extrapolation (rex). In ICML, volume 139, pages 5815-5826, 2021.
[34] Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. Adversarial examples in the physical world. In ICLR, 2017.
[35] Yann LeCun. The mnist database of handwritten digits. httpp://yan. wwwp://wwewnc.n.neeeeeeee/eeeeee cwm/exdb/ mnist/| 1998.
[36] Jacho Lee and Maxim Raginsky. Minimax statistical learning with wasserstein distances. In NeurlPS, pages 2692-2701, 2018
[37] Boqi Li and Weiwei Liu. WAT: improve the worst-class robustness in adversarial training. In AAAL, pages 14982-14990, 2023.
[38] Da Li, Yongxin Yang, Yi-Zhe Song, and Timothy M. Hospedales. Deeper, broader and artier domain generalization. In ICCV, pages 5543-5551, 2017.
[39] Da Li, Yongxin Yang, Yi-Zhe Song, and Timothy M. Hospedales. Learning to generalize: Meta-learning for domain generalization. In AAAI, pages 3490-3497, 2018.
12

---

[40] Haoliang Li, Sinno Jialin Pan, Shiqi Wang, and Alex C. Kot. Domain generalization with adversarial feature learning. In CVPR, pages 5400-5409, 2018.
[41] Xiyuan Li, Xin Zou, and Weiwei Liu. Defending against adversarial attacks via neural dynamic system. In NeurlPS, 2022.
[42] Ya Li, Xinmei Tian, Mingming Gong. Yajing Liu, Tongliang Liu, Kun Zhang, and Dacheng Tao. Deep domain generalization via conditional invariant adversarial networks. In ECCV, volume 1 11219, pages 647-663, 2018.
[43] Xinsong Ma, Zekai Wang, and Weiwei Liu. On the tradeoff between robustness and faimess. In NeurlPS, 2022.
[44] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018.
[45] Mazda Moayeri, Kiarash Banihashem, and Soheil Feizi Explicit tradeoffs between adversarial and natural distributional robustness. CoRR, abs/2209.07599 075592 2022.
[46] Omar Montasser, Steve Hanneke, and Nathan Srebro. VC classes are adversarially robustly learnable, but only improperly. In COLT, pages 2512-2530, 2019.
[47] Seyed-Mohsen Moosavi-Dezfool Alhussein Fawzi, and Pascal Frossard. Deepfool: A simple and accurate method to fool deep neural networks. In CVPR, pages 2574-2582, 2016.
[48] Vaishnavh Nagarajan, Anders Andreassen, and Behnam Neyshabur. Understanding the failure modes of out-of-distribution generalization. In ICLR, 2021.
[49] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. COLT, volume 40, pages 1376 1401-140,2220 2015.
[50] Sylvestre-Alviss Rebuffi, Sven Gowal, Dan A. Calian, Florian Stimberg, Olivia Wiles, and Timothy A. Mann. Fixing data augmentation to improve adversarial robustness. CoRR, his/2103.01144 2021.
[51] Elan Rosenfeld, Pradeep Ravikumar, and Andrej Risteski. An online learning approach to interpolation and extrapolation in domain generalization. In Gustau Camps-Vally Francisco J. R. Ruiz, and Isabel Valera, editors, AISTATS, volume 151, pages 2641-2657, 2022.
[52] Yangjun Ruan, Yann Dubois, and Chris J. Maddison. Optimal representations for covariate shift. In ICIRR 2022.
[53] Shiori Sagawa, Pang Wei Koh, Tatsunori B. Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. CoRR, abs/1911.0873.. 2019.
[54] Hadi Salman, Andrew Iyas, Logan Engstrom, Ashish Kapoor, and Aleksander Madry. Do adversarially robust imagenet models transfer better? In NeurlPS, 2020.
[55] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning From Theory to Algorithms. Cambridge University Press, 2014.
[56] Zheyan Shen, Jiashuo Liu, Yue Hc, Xingxuan Zhang, Renzhe Xu, Han Yu, and Peng Cui. Towards out-of-distribution generalization: A survey. CoRR, abs/2108. 13624, 2021.
[57] Sign function. Sign function, 2023. [Online; last edited 16-January-2023)
[58] Baochen Sun and Kate Saenko. Deep CORAL: correlation alignment for deep domain adaptation. In ECCV, volume 9915, pages 443-450, 2016.
[59] Christian Szegedy, Wojciech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In ICLR, 2014.
(60] Cuong Tran, Keyu Zhu, Ferdinando Fioretto, and Pascal Van Hentenryck. Fairness increases adversarial vulnerability. CoRR, abs/2211. 11835,21.11185 2022.
13

---

[61] Vladimir Vapnik. Statistical learning theory. Wiley. 1998.
[62]
Hemanth Venkateswara, Jose Eusebio, Shayok Chakraborty, and Sethuraman Panchanathan.
Deep hashing network for unsupervised domain adaptation. In CVPR, pages 5385-5394, 2017.
[63] Martin J. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[64] Qixun Wang, Yifei Wang, Hong Zhu, and Yisen Wang. Improving out-of-distribution general- ization by adversarial training with structured priors. CoRR, abss/210.066077, 2022.
[65] Zekai Wang and Weiwei Liu. Robustness verification for contrastive learning. In JCML, pages 22865-22883, 2022.
[66] Zekai Wang. Tianyu Pang, Chao Du, Min Lin, Weiwei Liu, and Shuicheng Yan. Better diffusion models further improve adversarial training. In ICML, pages 36246-36263, 2023.
[67] Jiancong Xiao, Yanbo Fan, Ruoyu Sun, and Zhi-Quan Luo. Adversarial rademacher complexity of deep neural networks. CoRR, abs/2211, 1ttp/2211.149666 14966, 2022.
[68] Shiji Xin, Yifei Wang, Jingtong Su, and Yisen Wang. Domain-wise adversarial training for out-of-distribution generalization, 2022.
[69] Jingyuan Xu and Weiwei Liu. On robust multiclass learnability. In NeurIPS, 2022.
[70] Hanshu Yan, Jiawei Du, Vincent Y. F. Tan, and Jiashi Feng. On robustness of neural ordinary differential equations. In ICLR. OpenReview.net, 2020.
[71] Mingyang Yi. Lu Hou, Jiacheng Sun, Lifeng Shang, Xin Jiang, Qun Liu, and Zhiming Ma. Improved OOD generalization via adversarial training and pretraing. In ICML, pages 11987- 11997, 2021.
[72] Dong Yin, Kannan Ramchandran, and Peter I.. Bartlett. Rademacher complexity for adversari- ally robust generalization. In ICML., volume 97, pages 7085-7094, 2019.
[73] Runtian Zhai, Tianle Cai, Di He, Chen Dan, Kun He. John E. Hopcroft, and Liwei Wang. Adversarially robust generalization just requires more unlabeled data. CoRR, hbbb/1906.0055,, 2019.
[74] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing, Laurent El Ghaoui, and Michael I. Jordan. Theoretically principled trade-off between robustness and accuracy, In ICML, volume 97, pages 7472-7482, 2019.
[75] Jingfeng Zhang, Xilie Xu, Bo Han, Gang Niu, Lizhen Cui, Masashi Sugiyama, and Mohan S. Kankanhalli. Attacks which do not kill training make adversarial learning stronger. In ICML, volume 119, pages 11778-1 1287, 2020.
[76] Yuchen Zhang, Tianle Liu, Mingsheng Long, and Michael I. Jordan. Bridging theory and algorithm for domain adaptation. In ICML, volume 97, pages 7404-7413, 2019.
[77] Zhengyu Zhou and Weiwei Liu. Sample complexity for distributionally robust learning under chi-square divergence. Journal of Machine Learning Research, 24(230):1-27, 2023.
[78] Xin Zou and Weiwei Liu. Generalization bounds for adversarial contrastive learning. Journal of Machine Learning Research, 24:114:1 14:1-114:54, 2023.
14

---

A Proofs
In this section, we show the proofs of the results in the mainscript.
A.1 Proofs of the Toy Example
Lemma A.1. X ~ NN, Σ) where X ~ RR, then any A E R"*", we have:
AX ~ (VA,, AEA")
Proof of Lemmal A.7 We prove the lemma by powerful tool, the characteristic function of random variables. The characteristic function of a random vector is defined as:
xx xx(w) = E e _
Let Y AX, we have:
④y (w) = E eeww [
E [ eew ((ax)) = B [(((""w))* = 0x (AxxAAW)
Since X ~ NH, E), we have:
(x(w) EE [eww"x "w ヒー n- Iw Iww]
so we have:
(w) E (" "=(("= E ( "200 (Ax)) fw0 "AXA")
Since the characteristic function and the distribution is one-to-one, we have: Y obeys the multi- variable Gaussian distribution and Y (AA,
L
Lemma A.2. Let DY 1) = DY = -1) 2 E Fd and Dxir=y = N Σ) where
f E IRd and D E idddd, then for any linear classifier how E H.:
Bi RD (Loz, hww +b (<l|w0) pr w"
VwuTEw
where p p 1. Further more, if = 2 and E I²I, then w"
B5 arg min' (Lo1, Rww, the wheeH
weight of the most robust hag H under adversarial atlack BB(.) is:
w
Proof of Lemma A.2
Let lww (x) sign(w" (e x), then have:
RD
(Co1, kw)
E
sup (((
[hw (x) # }
(x.y)~D
1
1
E
sup (x)
1 ||w x' <0
+
E
sup ('E
1 / x' > 0
DxwDx
2
1
P
inf x' (xE
w" x' 0
P
sup x'E(((2)
w" x'
2
x~DxIY=I
Dx
1
(w x <||W 1p-
0} + 2 INDXIY--1
P
ww x + e||w||| pp > 0]
2
x-DXI--1
1
PP [Nw" u, N. Eww= < <<l|w||>-
+ IP [V(-W" - u, ww'iw) > - -E|lw]lp
2
P [w u. n" Eww) c </| = (sl|volly- w"
V Sw
where a is the result of Lemma A.l when regard w" as A in Lemma A.I
15

---

If p and Σ = I² then we have:
(E]w/l2 w² -o
(
w"
RDd (Loz, hww)
o1|w012
|
Since (--) is increasing, we need to minimize = that the maximum is achieved if we choose w M.. have w
w 1 i.e., to maximize
w F al|wo|2
it's easy to see
μ..
Lemma A.3. Let D1 D2 be defined as: Py = 1) -DY --1 (2
(ypu,, I²1) where Pi U2 E Rd || ll2 = |2ll| and 14,, let = 1 + 12 and suppose a is the angle between
DY,
- 2. X Fd and D1,X(==g Ny 12x
fi and u2, if0 < 2 arccos pilla then w" μi + μ2 achieves the minimal robust risk.
Proof of Lemma A.3
To simplify the notation, we denote R (L01 hw) by R(w). Then by Lemma
A.2 we have:
R(w)= RD, Bi
(ww)
1 B3 R,, (Co1, (ww) (e,1, }
(cltw]2z w 0 a||w||
p11
+ x
(cl/w| w
pt2
2
w ||12
where ((u)= - -/ $ dy. The proof is divided into steps. In the first step, we prove that for any weight w. we have R(pp) S R(4). where pp is the project of onto the space span 12). Then we can reduce our analysis the weights in the space span (
Step 1. For any w E Rd, we take direct sum decomposition as w = w. + we where w. span (M1 M2) and span (M) u2) have:
L the orthogonal complement space of span (M1, then
w wTH p1 = Mn + w. pn w ThIn
Similarly, we have wTHz : u2. Since w, 1 wi then have | l| + /wel22. for any w E Rdd we have:
c
w
11
w
12
R(w)=
+ +
2
σ
||
2
w
1
c
w
T
11
T H12
+ c
2
σ
W.
w
ww
So it is obvious that R(w.) S R(w).
Step According the above results, we consider w span (2)) Suppose the angle between f1. 22 is a, note that R(w) does not depend on the length of w, so without loss of generality, we assume ||w||| = 1 here. Suppose the angle between and μu is 6, then the angle between and μ 0, then w is uniquely determined by 0, we denote R()) R(w), then we have:
|| 20s
||4 112cos(a 0)
R(0)
+
e
σ
By the rule of derivation for composition function, we have:
1
{
[[(e (e
|11l|2 cos 0)2
||11||2 sin
R'(0)
exp
0
2T
202
1
(e ||
ll cos(a 0))2 || ll sin(a 0)
exp
2 2T
20
1|11112
|| |ll2
cos 0)2
exp
sin
2v 2nT
20
(e
||
cos(a
8))2
sin(a 0)
exp
202
16

---

It is easy to see that when 0 = or 0 = + nI, (0) = 0, since:
R²( αt 2 2
||
(c |1 1l2 cos 5)²
sin a
exp { (e-
|1 la2 cos 5)²
a 2
exp
sin
20
2
20²
-0
Similarly we have R2 + T) = O. Next we prove R(0) achieves the minimum at 0 = 2 taking the second order derivation of 0, we have:
2/2TO (0) = exp {
(c || ll2 cos 8)2
}
(- || la (e
| ll2 cos 0)sin 20
M 12
20²
g²
(c
|| ll2 cos 0)3 cos
+ exp
20²
(c -
|1 22 cos(a-
01)2
||111l2(E- - ||11122 cos(a 0))sin (a 0)
-exp
202
o²
(E
|1 ll2 cos(a 0))²
+ +exp
cos(a - 0)
20²
(c |1
12 cos 8)2 }
|uulla (e || ll2 cos 0)sin
exp
cos 0
20²
o²
(c ||1||22 cos(a- - -8))²]
|11ll2( || ll2 cos(a - O))ssin
+
exp
coss(a - 0)
20²
o²
Then we have:
2v 2TO
R"
( exp
(
{ (E || ll cos g)
cos 2
H1ll (e - | ll2 cos 9 Jsin2g
|
20²
a²
(E | ll2 cos
)
|lilla(E
- || ll2 cos 2 )ssin? 2g
2
+ exxp
cos
20
{
(c- ||
1l cos )
0
a 2
|1H1lla(e || ll2 cos "sin? a
σ² exp
20²
2
Now, for simplicity, let he 1111,2,00 cos cos then sin
x², then consider f(x) 20
(1=)(111)))))) = d'cos |/ (0ll:/ee11111 cos / sinn
2. where a E (0, T). so E (0, 1).
We have:
f(x) 0²x kile - k1 x²) = 0²r - 12r ken 1.2213
k22 (xx - x²) - ke(1 - x²) + o = =k2x(1 - x²) ke(1 - xx2) + 0²x
= 1e1 - x² [k= - -() 0²I.
Since (0, 1), then σ²x > and k(1 -1)) > 0, by the assumption, 0 < a S arccos
[4 lla
2 arecos &. so cos 2 f. so hr - 2 0, so we have f(x) > O. which means that R' () >
so we know that 0 = _ achieves the minimum of R(0), which means that the direction w² 141 M2 achieves the minimum R(w.. Similarly we can show that R()) achieves its maximum at 0 = 0
2 +
which means that the direction - ( + (2) achieves the maximum of R(w) in span (21,
Theorem 3.4 Consider the setting in Example D and suppose that μ lies in the 2- 2-dimensional subspace Ri in Theorem A.4 (see Appendix A.. for details about R and see Figure 7 for intuitive illustration). Let l01 (z. y) 1[x # v). where 1[:] is the indicator function and B B,
{x'
|| ->'1lp I r), consider training with hypothesis class H. {how hw (2) = sign (wr z). w E Rdd), and denote (()) ] + 1.D(s,,,,)) j. E (0, 1, 2] + j. Consider the fz-norm adversarial attack R hww) and (w)) R RBi, (Co1, hww). let ((-) be the distribution conuttioonunnttio function of the standard normal distribution, let a denote the angle between and Qu, which is the rotation angle of Q in subspace R, suppose that 0 < a a arecos | then we have:
with radius e, for notation convenience, let Ray
17

---

1. we we train with D and D under H. let (01) + Qu, which achieves the minimum of Roi (w), then the robust accuracy (o on the test distribution D(2) is:
R2(w)())) = 1b (u Qu)
Il Qu112
2. If we train with D and D(2) under H. let (02) = u Q.u. which achieves the minimum of Roz(w), then the robust accuracy of (02) on the test distribution D( is:
R1 (w) = ① (1 2H
o Tll + 22ull2
3. If we train with D(1) and D(2) under H. then w(1)) Qu + Qu,, which achieves the minimum of R (2) then the robust accuracy of (12) on the test distribution D(U) is:
(Qu Q²²
Ro(w(12)) +
olp Quu112
What's more, we have Rí (w2)
< (21) Ro (w)
Proof of Theorem 3.4
The values of Ro R2 (w (02)) (o()))))) is direct result of Lemma
A.2 and Lemmal
A.3 Next we compare the three ad adversarial risks.
(u+Qu)"
(Qu+Q"#)"* C(02) +lIm+Q*mllz C(12) olQu+QQ'ul: i.e. the subtractor in
(u+Q"H)² Qu
Let C(01)
all Quia
(o))) (W))))) Ro respectively. Since ((u) = T2n Sm.0 e du is monotonely
increasing, judge which of the three robust errors in Theorem 3.4 is the smallest, we need only to judge which of the corresponding C(t)) is the largest.
Firstly, let Qu be the matrix of Q under the orthonormal basis e1, ed where (e.); dig and dig
(Q.ptQ²u)
lifi = j. = O otherwise. Then we have QH = Qoft and we can see that C(12) = alQ.u+ ""Qqptp" SH 2²Q"Q.QQ. " (u+Q.H)) QQH QlpAt
"0""=="0"00" a +Q.
QlAAl C(o1) (where is
a Q.H
from the fact that ||Q,=||2 = ||0||2, Vo and x² Aax xx A Vxr A). So R2(w((1) Ro(w(12))
To compare which one of R2 (w2) and
is smaller, we note that lies in the 2- dimensional subspace Ri E FRd in Theorem A.4 as specified in Theorem 3.4, so there exists
scalar ER such that μ + Q² 22M= k Qu, and we know that Qu aar min Ruz (w) (by Lemma A.2
whow
so we know that Ri (w)) Ra (w) (1( since
inf Ro(w) wie
inf Ri (w)
wiww
inf R2(w) (which is obvious according Lemma A.2 And following the same direction who
of the proof Theorem A.4 it's easy to see that (01)
# + Qu is not the same direction of
Q² y (the weight attains smallest robust error on D(2)), (2) wio EH
inf R2(w), have
Ra (02)) (2)) (1))
Theorem A.4. Let Q be rotation transformation on RR and Q + I, then there exists at least one 2-dimensional subspace R E IRd such that there exists a scalar s.I. + Q kr for any R.
Proof of TheoremAA.4 By the results of matrix theory, we know that since Q is an orthonormal transformation, then there exists an orthonormal basis ....... T7 under which the corresponding matrix of Q, Q, has the form:
Q diag (R1, ... Rm A....., Ar
18

---

ccos 0j sin 0j
-sin 0j cos 0j
where X
1, i 1,2, .0. S - R, 1, 2. , 1m.0 < m 1
82 < T.
m,
Since Q is rotation transformation, Q is a rotation matrix, so \ =... X, = 1. Once given the basis, linear transformations I&d and matrices in Rdxd has one-to-one correspondence, tells us that Q + I, where 7 is the matrix of under the orthonormal basis .!...... -A. So we have consider the subspace Ri span (711 77) be the
Q
in case, without loss of generality subspace spanned by the vectors {?).
For any R. the coordinates of a under the basis .......... na is then [0r,, a2, 0, ... 00' and the coordinates of Qax Qaa is Qua1, 0,... ,0]", Q² [0 22 0, ..... ,0'² respectively. We now prove that there exists k 2cos 01 such that [0,, 0, 0)² + Q² O2 0, 0 kQ[a1, 022 .,..,,,.....0...... .0"" We have:
a1
R1
a1 022
aa cos 0 02 sin 01
02
an sin 01 + 0g cos Q₁
Q
and
@1
[or cos 20 sin 201 an sin 20; + Or2 COS 20
R
022
02)
Q²
0
So the coordinates of Q is:
on
Ta
To (cos 20 + 1) - 022 sin 201
22n cos2 20z sin O2 cos 01
02
sin 20, + 02 (cos 201 +
20g sin 01 cos 0 201 cos? 01
+ Q²
aa cos 01 02 sin 01
aa cos 01 02 sin 0
a1 sin 0 + 0g cos
a1 sin 0 + ag cos
2cos 0,
0
which is just times of the coordinates of Qa. So we get a + Qaa = kQa for any a E R.
A.2 Proofs the Average Case
Theorem 3.1 Suppose the loss function is bounded, i.e,, l E [0, U), then with probability at least
1 8 over the sampling of D,,... DD. all h H. we have:
In4/5
In4/8
(5, S L (e, (9) + 29nn(9) + 3U
+ 3U
V
21
2in
where
Ō = 9h : X' x y +R o
sup E(h(x', (M(a,,))), E 3 x'EB(a)
Our proof consists of 2 steps, 2-step uniform convergence analysis is different from (but based on) the standard Rademacher complexity generalization error bounds.
Proof of Theorem 3.1
Step 1, upper bound the difference between C fi) and C (e, h)) for any h H.
19

---

Let D =D1,," Di). we define:
(2) sup 12 h) (e,
hER
Since 8 [0, changing one of the D; in D will lead to most f change in (D)) So by McDiarmid's inequality we have:
P (2) ((00))E(48(00 (2)) S exp {
2tc²
U2
so with probability at least
I over the choice D, we have:
In4/8
Φ 2 E( + UV
(A.1)
Then we give an upper bound for E( (2)), by the symmetric technique, let 6 = (Si, ( , be a set of independent copy of D, have:
E 8 (2))
= E Dmpt
sup
(c (1, - ()((e))))
NEH
1 Σ
E
sup WCH
E (e( h)
RS. (1)
Drpp
Snup
t=1
E Druf
sup
E
(R (L, (e,A))
hEH
Siup
E
E
sup-
R (e, - RB,
D Dmup
C S~'p'
NEW
E
sup
σi RR5, (e, R5, (2,
D Drep' Grup'a a
hEWt t
$ 2 E Dr-pla
sup NEA!
o R h4
= 2 Dippl
E
sup
E
sup ({E((a.)
E(h(z)) wi)
< 2 E
EE
E
sup
sup ccB((;)
((h(z)) v4)
NEW
1=1
= E Drpp (
E [G)
where: a uses Jensen's inequality; comes from the fact that the random variables os (R h2 - R h2) and RS (c, R h2 are identically distributed, where a; Uniform(1=1)) and o {=1}* has independent elements d1, oü is from the property of sup that sup(a + b) I sup(a) + sup(b) and the fact that a has the same distribution as -a; d uses Jensen's inequality.
Since & [0, U]. change in one data point (I,, yi) will cause at most difference in H. then use McDiarmid's inequality to get: with probability at least
In4/8
E
(G)
RR ( + UV
(A.2)
D Diupt (
Combine A.1 with (A.2) we get: with probability at least
2
In4/8
$ 6 (2) < (9) + 3U
(A.3)
20

---

".,,,..,,,) ".,) be set of Step 2, upper bound the difference between (e, h) and L (g, h) for any h E H.
4E h1) - - ==1
(e, - -R ((,((.))))) (1)
Let D = -D.U...... De and then define:
( sup hEHt
(=)(,,) (e,
1 Σ
R (e.
sup hER t
Since E [0, U] and there in examples in D, changing the j-th example of D. (#ij, Viy) will
cause at most in change 8 (D)) So by McDiarmid's 's inequality we know: with probability at least 1 1 over the choice of D.
In4/0
V
S
T
+
UU
(A.4)
2tn
Next upper bound E
(2) by the symmetric technique, let G 18,,
independent copies of D and let (æij, 0ij) be the j-th example in S, we have:
(c,h) - R (1)
E
B
= E
sup hEM
R
D
iml
E
sup
E
sup
{(h(z)) 8.)
sup ((h(zl)).
D
hEMt
(D..
(EB((E))
z eB(,,)
1=1
EE
sup
E
E(h(E(z)) Tis) EB(E(()))))
sup
sup
e(h(zr))) Wis)
DEH!
S
2/ (((,,)
1=1
sup
sup
((M(5))), (is)))
sup at, (B(,,) ((h(a(())))))
((h(ol)), Bis)
2,6
NESt t
# (B(()))))
1=1
E
sup-
Egj
i E()()))))))) ((h(E)):
sup
- sup at EB(a))
0,6D
NCH!
1
7
i=1
/=1
< 2
E
sup
1
n
Eij
sup (((2)))).6)) # B(a
6.
heH!
12
d 2
Ren (
where:
a
is from Jensen's
inequality; b is from the fact that sup E(h(z'g)) vij)) EB((()
Eij
sup E(h(Z) ). Urg)
has the same distribution as
F. BB(B))
sup E(h(T)) Dty) sup #t EB(a.,) independent entries; c from the property of sup that sup(a + b) sup(a) sup(b) and the fact that Σ has the same distribution as -E.
((h(zl)) Vty). where Egg Uniform((#1)) and Σ has E(z,)),
Similar as before, if we change one of the {mmij ((Di),Bi))) (i))); the change of (G.(G) is at most U so m
by McDiarmid's s inequality, with probability least 1 i. we have:
In4/8
E ②
Rim ( < Rin (g) + U
(A.5)
2ln
21

---

Combine A.4
and A.5
we have: with probability at least
5
2
In4/0
v B (D) S 29 + 3U V 2tn
(A.6)
Combine A.3 and A.6) we have: with probability at least 8:
In4/5
In4/8
Φ D B S (²) 29 (5) + 3U
V
+ 3U
2t
2tn
By the property of supremum, we have: with probability at least 8,
(c
sup (e,))) - (e, + (e( (e)(
sup NEH
NEW
sup (c (t, h)) (e())))
sup kE7
(c)(), -g((e
hew
(2) + v (
In4/8
In4/6
< 22, (g) + 29t ( + 3U
+ 30
21.
2/n.
Proof of Corollary 3.2 The main idea of the proof is to use risk decomposition to reduce < h) CE (C, to (5 _e, (f, h) for some h. Then we have: with probability at least -88
(e, h) - (e, = (e, (e(,,) + (gl,,) (g(e,h)) (2 - - (e,
~ (c,,h) - (e, + (e,h") - (e,
< 2sup he#
(e(()))) - (e, h)
In8/0
In8 /5
xx (ō) + 49.m (0) + 3U
+ 3U
V
2t
2tn
where: from the fact that 2 (f. < (1, by the definition of h; b is from Theorem
3.1
although in Theorem 3.1 we only have bounds for sup (c%(e,)) L (2, ()), we can use C h) h))
hER
similar argumentation in Theorem 3.1 to get the same bound for sup heW
both with probability at least 1 - 8', using union bound for these two cases we get bound for sup (5 h) - (e, ht) with probability at least - 28', take å 5 2 NEW
we get the bound for
(5 h) - (e, h)) with probability at least - 6, this is why we get In4/6 in Theorem 3.1
sup NEW
but In8/ here.
22

---

A.3 Proof of the Limited Environment Case
Proof digg (:)) ) is a pseudometric. obvious that de (+--) is symmetric, now we proof that
((00) (:.)) satisfies the triangle inequality. By definition, for distribution P, P,Q,A Rt:
d ((H))
(P.Q)
sup beH
E (z
sup ((h(z').)) x'EB(())
E (x.g))~
sup ((h(x'); r')
sup
E
sup ('E
e(h(x'); v)
II
sup E(h(x'),)) x'E)(x)
kcH
(z.
(0.2))~R
E
sup ((h(x') x'E
E
sup r'EB(x)
((h(zz)
(x.1)
(x.21)~Q))
S
sup
E
sup e(h((z'), (B)()
IR
sup x'E)())
((h(z'),,))
kEH
(z.y)~~
(a.
E
{(h(z'),3)
E
sup x'EB(z)
((h(x'),))
kEH
(x.9)>R
x
(a.v)~Q
d (((0)
(P, R) +
(
R. Q),
where: a is from the subadditivity of the supremum operator. So di ((1)) (5.) is pseudometric.
Before prove Thorem 3.3 we first give a useful lemma.
Lemma A.5. For any h H. any distribution P, Q on we have:
(R)( -R5 (2, b)
d (i (P.Q)
Proof of Lemma A.5
From the definition of dd(no (P, Q). we can know that:
d (P.Q) = ssup hR) ( (c, (R((,,)) ( Re)(, wh E H,
AEH
which is just what we want.
Theorem 3.3 For a given but unknown target distribution T, let A = (Q1,...,,1))) 2 E.E X = 1} be the t-dimensional simplex and Conv(D) Ei A be the convex hull of
(Di....,Diyy define Tp E arg inf de (D, be the "projection" of T DEComv(D)
onto (2nv( and X be the weight vector where Tp = -1= ArD EE [0, U1, then we have: with probability at least 8. for all h E H.
(e,h)
R D.
(c,h) + EE NidiiN (D,, D.) + d (T, Tr)
In8/8
1n(16//8)
+ 49 (g) + 29,, (9) + 6U
+ 3U
2tn
2n
Proof of Theorem 3.3 Our proof is divided into 2 steps, the first step gets results for the population distributions and the second step uses finite sample approximation to get results for empirical distributions.
Step 1. Get the relationship between the population distributions.
Lemma A.5 tells us that: for all h H.
tells
R (e, h)) S RE, d d (T, D) < (1, (T, d (TTT)(TT.)))
(T,Tp)
23

---

where the last inequality is from the triangle inequality of d (())))) and D = Ei=1 D. Recall
that D -i= D., then we have:
(e(7)) (Tp,D) 2 d (Tp, Tp) + di (200 (Tp. d((H)) (D, D)
digp (Tp, TP) + k(H)) (D, D) + )2(1))
ΣxD,,
Σ xrD;
1 +Σ D.
1=1
(T = =dinn (Tp, Tp) + {(())) (D.D) + sup NEW
R
Σ, A;D. (l, R Σ, 10. (2,h)
(T, = =dien (Tp, Tp) + (H) (D,D) D) + sup
R
E. E, 2;5, ,1, 11) (1) Σ, E, (,
(4,
WER
- deimo (Tp, Tp) + ((H) (D.D)
\j sup R (k,h) Rg
- (e.
NEH
= dd (Tp, Tp) + HH)
(D, D)
Σ
Σ
X3 ( (D D,),
where: a is from the triangle inequality of drn ( :); follows from the linearity of R$ h) and the subadditivity of the supremum operator. So we have, for any h E H:
(E) ( 4 (00 (T, Tp) (Tp, (T,,
(
(D+ ΣΣ
Xi
B D,)
(Dr,
((H)
(A.7)
Step 2. We now show the bound of the finite sample approximation error d ((H) di d (D, D). Since we have no access to the population distribution DD we also give finite
(Tp, TP) and
sample approximation of Rg (E, h) and bound the corresponding approximation error.
The empirial distribution of D is D = - De, then we have:
(R)(E,)) (e.
1 Σ
(R5,(EM) (2.h) (e.h) = ( (δ).
sup NEM
sup keMt t
where 1B ( is defined in the proof of Theorem for all h E H.
3.1
Then we have, with probability at least 1
8
4
R5(hh) = Σ
Σ R (l, h)
R (e, + (9) + 3U In8/5
(A.8)
1 1=1
26n
Note that (((H)((. (D, sup
( Re h)), similar the bound of T
kER
(R)(E,)) R (g, h)). we have that with probability at least 1 4:
sup NEW
In8/8 2tn
(R) RZ((.))) 29 (9) + 3U V
sup he
so with probability at least 1- 8.
In8/8
B 1
(D. D) sup heH
- 29n + 3U
(A.9)
2tn
Now we bound d8 (Tp, Tp), by the definition of Tp, we have:
t
L (Tp TP) = =dē de(())
Σ x;D; Σ D.
5 Σ x ( (D., D.)
1=1
24

---

For each i, we define:
(D.) sup RR (L, R (e, (e, NEM
Since L E U), changing one example in D. will lead to at most
I chang in Te;D),, by x
McDiarmid's s inequality we know: with probability at least 16
In (166/)
r (D.) E r (D.)
UV
2n
Next we upper bound
r (D.) by similar analysis as in the proof of Theorem 3.1 we have: with
probability at least 1
3
1ör
E
(D.))
S (r) + UV
In (116t//)
D.
2n
Then with probability least 1
5
88
In(16t/8)
R (e, 1 R R2,((2 (e,
(D.) ( + 3U
sup NEW
2n
With similar argument, we know that with probability at least 1 gr
(c,h) - R. (c,1)) S (9) - 3U |n(161/0)
R D.
sup
bE7
2n
So with probability at least 48
5
In(16//8)
di (D,, = sup RB, (L,h) R (c, S (9) + 3U
sup NEH
2n
So with probability at least 1 4
In In(16t/5)
((( (Tp,
Tp) S
X
d ((H) (D), D,) (G) + 3U
(A.10)
2n
Now combine A.7
A.
A.9 and
A.10),
have: with probability at least 1 - 8, for any H.
RE
R
(e, h)
B
(T, Tp) + d (20 (Tp, Tp) +
+P)
d8 (n))(( ΣΣ
((2))
In8/8
< 7 1=1
R (L, + (G) + +3U
+ d (T, + 22R (g)
2ln
/n(161/8)
In88/
+ 30 V
+ (2 + 3U V
+ 1 Σ>
\; B
( DD)
((H)
2n
2tn
1
Σ R
D.
(2, + ΣΣΣ
X1 1 (76) (D,, + d
(T, Tr) 49 (9)
In8/5
In(16t/8)
+ (9) + 60 |
+ 3U
21n
2n
B Toy Example to Model the ColOredMNIST
Example 2. Consider data point (x.y), where x E X C Rd+1 consists of invariant feature Tine
Xmx C 2d and spuriously correlated feature Zop {s R. to simplify the example, let
25

---

(Tinv, Tsp) be the feature observed. Consider the case there is linear classifier (( = Winv Ein such that y h((im))) > 0, i..., Zinv is invariant for all distributions on Viy {+1}. Suppose the dataset S = {z D:) v:]] is linearly separable, and the dataset S is induced into two disjoint groups: a majority group Smyj where Esp y > and a minority group Smin where Tssp y < O, let 0] > 0.5, which means that the spurious feature is positively related to the label y.
p P[ ap
The next theorem considers the degree of dependence on the spurious feature of the trained linear classifier.
Theorem B.1 (Theorem of [48).. Let Hi be the set fo linear classifiers, = Wi + W Wsp sp- Consider any task that satisfies all the constraints in Section 3.1 of 148]. Consider a dataset S drawn from D such that the empirical distribution of Dim given Tsp y > 0 is identical to the empirical distribution of Daw given Txp y O. Let Wine (in((t) (t) + WapTaa be initialized to the origin, and trained with an infinitesimal learning rate gradient descent to minimize the exponential loss on a dataset S. Then, for any (I.y) S, we have:
In vplL-p) Mln(t +1)
Wep (t)s
In T-
Ω
1
0
110 bm (t)
Finr
in(t+ In(t + 1)
where:
1. p denotes the empirical level of spurious correlation, p
|s| Ece [xp y 0] which
without generality is assumed to satisfy p E [0.5,1),
2. M denotes the maximum value of the margin of the max-margin classifier on S, iee.
M maxxEs$- I where i is the max-margin classifier on S.
3. C = x²
2(2M-1)
Remark 4. In the proof of Theorem B.I (please refer to (48)). the loss function is:
L(Wan Wap) P. Drr
(Wasti (wa)) +
Din [e- (W 125))
(B.11)
We denote L1- E B [e- twi (wgss) and L2 -E Brw [e- 1w-
L pL1
(1- L) To model the case in the ColoredMNIST dataset, we let St denote the dataset with corruption rate 0.1, S2 the dataset with corruption rate 0.2, S3 the dataset with corruption rate 0.9. For training environment with corruption rate Punin, we have Linain = Puain + (1 Piroin) L2 and Liest = L1 + (1 Prest) 2 if Purain >> 0.5. otherwise we have Lirain =
Ptrain L2 + (1 Perain! L1
and Lient = L2 + (1 - Prest L1. What's 's more, since the lower bound > 0 for p 2. we have
L1.
L1 < L2. So in the standard training case:
1. When we train with S1, Sz. then the overall Pivain 0.1+0.9
2. So according to Theorem B.] we know that (t) = O. which means that the classifier just depends on the invariant Jeature, so the performance on S2 is good. Since Wsp(t) 0, T T.z, so we have Liroin = Proan + (1 - Pumin)
L2 ) = Egn-D (e- distribution here is the same as the test distribution, which means that we can generalize well in this case, which is consistent with our experimental results.
Lyear So the mixed training
2. When training with S2, Ss, then the overall Prrain = 0.2+0.9 = 0.55, which is quite close to 0.5, which means that the correlation between Teg and y is not very strong. It means that the upper bound and the lower bound in Theorem i. small, so Wep is small, the classifier mainly depends on the invariant feature and slighily depends on the spurious feature, which is just little negatively reluted to y when Prest = 0.1 in the test environment. In this case, I Tamain = Pomin In + (1 Pmmii) T = 0.55 + 0.45L.2 and Tasst Ptest Tn + (1 Prea) T-2 = 0.1 + 0.9T2,, and Trest T = - 00.45,, + 0.45T.2
0.45 T. T.)) > 0, but in this case Wsp is small, so we have L2 - L1 is small according to (B.II. so the difference between training error and test error is not too large, so the generalization performance for this case is not bad, which is consistent with our experimental results.
3. Finally, it comes to the failure case in our experimental results, i.e,, using S1, as the training environments and Sg as the test environment. In this case, the overall Puoin
26

---

0.1+0.2 = 0.15, so the classifier depends more on the spurious features compared with the above two cases, what's more, since Pis 0.9, the relationship between Zap and y is almost reversed when we switch to the test stage, so we have Limin = Ptrain T/2 + (1 Pumin) T1 0.85 + 0.15Lz and Tus = Prest Lo2 + (1 Piest) T, 0.1 + 0.9I.2 and Treat Turrin = - -. + 0.75T. 0.75(I2 I,] > O, and the wa here is much larger than that in case 2. which means that L2 L1 here is much larger than that case 2, so the gap between training error and test error here map be much larger than that in case two, leading to the poor generalization performance in practice.
We can see that the analysing results here are consistent with our experimental results for ColoredM- NIST in Appendix D.2
C Experimental Settings
We run each algorithm 20 times and 1 trial (since adversarial training is time-consuming, we just run I trial rather than 3 trials done in DomainBed). We use part of the training data the validation set to select the best model of the 20 runs according to the adversarial robustness of the training environments. Following DomainBed, we use random hyper-parameters in the 20 runs.
C.1 Attacked Algorithms
1. Empirical Risk Minimization (ERM, 61] minimizes the errors across domains.
2. Meta-Learingg for Domain Generalization (MLDG, 39) leverages MAML [T6] meta- learn how to generalize across domains.
3. Class-conditional DANN (C-DANN, tional distributions P X
is a variant of DANN 1rr
matching the condi-
|Y = across domains, for all labels y.
4. Risk Extrapolation (VREx, 33 approximates IRM with a variance penalty.
5. Representation Self-Challe Challenging (RSC, (28) learns robust neural networks by iteratively discarding (challenging) the most activated features.
6. Domain-wise -wie Multiple-perturbattee adversarial perturbation (UAP) with low rank along the dimension of examples (for n exam- ples, use the convex combination of & (k < n) perturbations as the universal perturbation) to conduct universal adversarial training (UAT) to improve the OOD generalization.
Adversarial Training (MAT, 64
use an universal
7. Adversarial Training with Low-rank Decomposed perturbations(LDAT. (64) shares similar idea with MAT, but it uses UAP with low rank along the input space (for N x N images, it constrains the N x N UAP matrix has rank < N) to conduct universal adversarial training (UAT) to improve the OOD generalization.
C.2 Datasets
We use the following datasets provided by the DomainBed 26
1. CNNSTedMNIIS [4) is a variant of the MNIST handwritten digit classification dataset 35 Domain d E (0.1, 0.3, 0.9) contains disjoint of digits colored either red or blue. The label is a noisy function of the digit and color, such that color bears correlation d with the label and the digit bears correlation 0.75 with the label. This dataset contains 70000 examples of dimension (2, 28, 28) and 2 classes.
2. RotatedMNIST 21
variant of MNIST where domain d E {0, 10,30, 45, 60, 75) contains digits rotated by d degrees. Our dataset contains 70000 examples of dimension
(1, 28, 8) and 10 classes.
3. PACS [38] comprises four domains d E art, cartoons, photos, sketches }. This dataset contains 9991 examples of dimension (3, 224, 224) and 7 classes.
4. VLCS [15] comprises four photographic domains d e { 101, LabelMe, SUN09, VOC2007 }. This dataset contains 10729 examples of dimension (3, 224, 224) and 5 classes.
5. OfficeHome 62 includes domains four d E { art, clipart, product, real ). This dataset
contains 15588 examples of dimension (3, 224, 224) and 65 classes.
27

---

C.3 Settings for attacking standard OOD algorithms
We evaluate the adversarial robustness of some of the algorithms in Table For adversarial attacks. we use Loe adversarial perturbation upper bound
0.1 for RotatedMNIST and ColoredMNIST, e 4/255 for others is because = 4/255 is use usually used in 224 x 224 colored images); we use the classical FGSM and PGD-20 as the attack methods, for PGD-20, the step size a c/4, we realize the attacks according to the package 'torchattacks'
32
We train the models in the same hyper-parameter random search setting (except that we just train the model for one trial) in DomainBed, and the we attack the models trained with the best hyper- parameters choosed by the training-domain validation set model selection method in DomainBed with the same seed as used during training. For MAT and LDAT, we use the same hyper-parameter random search setting in [64] except that we train with 20 random papper-rrrmeter for 1 trial and they train with 8 random pyper-paramen for trials.
C.4 Settings for OOD adversarial algorithms
In this subsection, we introduce the settings in our experiments in S We use the training- domain validation set model selection method in the experiment and train the model with 20 random hyper-partee perammrreeeer for trial.
Basic setting for training hyper-parameter random search.
1. For AT, we use the same basic random search setting as ERM.
2. For RDANN, we use the same basic random search setting as DANN.
Setting for adversarial training. We use PGD-10 as the adversarial attack to generate adversarial examples for adversarial training, with 0.1 for RotatedMNISTT and ColoredMNIST and 4/255 for the other 224 x 224 datasets, and we use the attack step size a = c/4 as usually done in the adversarial training community.
Setting for evaluating adversarial robustness. We consider two attack methods, FGSM and PGD- 20, evaluate the OOD adversarial robustness of the trained models. We the same that used for training but we do 20 iterations for PGD in the evaluation stage rather than just 10 iterations in the training stage avoid overfitting, which is also strategy used by the adversarial robustness community.
D Additional Experimental Results
In this section, show the detailed adversarial robustness of the current OOD generalization algorithms and our proposed algorithms, here we show the adversarial robustness in each test environment, for the ColoredMNIST dataset and RotatedMNIST dataset, we 0.1, and for other 224 x 224 datasets, we set 255
use FGSM and PGD-20 as the attacks to evaluate the adversarial robustness and the results are shown in the form of triple tuple (clean accuracy accuracy under FGSM attak accuracy under PGD-20 attack). Each column represents the results for a test environment. The tables show that compared with existing methods, our methods (AT and RDANN) significantly improve the adversarial robustness of the model the target domains.
In Appendices D.I to D.3
In Appendix D.6 we use Attokk as the attacks to evaluate the adversarial robustness. Each column represents the results for a test environment. The results show that under AutoAttack, all the existing methods fails (no more than 1% adversarial accuracy), and our methods significantly improves the adversaria robustness.
28

---

D.1 RotAtedMNIST
Algorithm
15
30
45
60
Ang
MLDG
14./14.1000
/
99.1 / /1.00000
/9.1/17.2/00
98.8
15.3/0.8
96.7/169//0 16.9/00
97.9/1511 102
CDANN
14.7/114/0.
92.7/122/2.
98.5
16.1 /0.5
98.9 123/2
98.9
16.5/
95.9/22.9/ 0.3
97.8/ 15.2 109
VREX
95.1/8.3/D3
98.619./00.1
134/004/00
14.4/0.4
96.3/9.2/..0
15.4/114//.
9..//1.3/0.0
99.3/116/23
/9.1/12.0000
99.0/21.5
96.0/9.9/0.
07,9/13.00 1.0
AT
770/91.8/903
99.2/96.1 794.8
99.2/96.6/98
99.0 09/0/96.33 996399955555
99.2/96..9955
97.2/
98.4 1547794.77 1954
RDANN
96,1/915//03
99.2/96.0/91.
99.2/96.4/95
99.2/96.7/2
99.1 99.1/99.1/955
97.3/9111/890
98.4 /
D.2 ColOredMNIST
Algorithm
+90%
+80 %
-90%
Avg
ERM
71.7/20.0/22
72.8 / 29.8 /.5
9.8 9.8/9.8/98
51.5 19.9 5.8
MLDG
72.3/16.6/0.1
29.
9.719.5/9.0
51.8/ 18.5 4.8
CDANN
71.4/11./11.
7
10.0/8.9/8.1
51.3/2322 8.2
VREx
72.3/24.3/3.7
73.9/29.8/5.9
10.3/10.1/98
52.3/214/6.4
RSC
72.7/36.7/1.2
72.9/36.//.7
10.2/9.1/6.7
$1.9/273/335
MAT
/
9.9/96/9.3
52.2/26.0/
LDAT
72.1/28.3/7.0
72.8/
9.7/9.5/9.3
51.5 77.9
AT
73.7 73.7/724//2.33
73.7/72.6/72.
10.2 10.2//02
/ 51.6
RDANN
73.3 73.3/72.1/722
73.2 13.2/718//1.
19..9.79
52.1/512/511 51.1
D.3 VLCS
Algorithm
Avg
ERM
98.2/47.4/00
62.7/21.
72.1
71.9/6.0/08 0.0
76.2 19.9//99//0
MLDG
98.5/50.000.0
63.5/24.3
73.1/4.9/000
79.7 79.7/10.0/00
78.7/22.3/0.0
CDANN
98.1/58.4/0.0
64.8 64.8/11.9/.0
74.6/10./000
77.1/25.8/ 12.1
7
VREx
98.4/56.2/0.0
64.9/16.2/0.0
69.7/2.7/00
78.4/13.6/00
77.9/22.2/0.
RSC
97.9/55.700.0
64.9/12.5/0.
75.5/3.0/0.0
77.8/4.3/0.0
19.9/13.9/0.
MAT
98.9/52.7/0.0
64.8/18.30.0
68.7/2.3/.00
80.7
/
LDAT
97.2/44.8/0.0
65.8/20.9/0.0
7.90/2.9/00
73.9/5./0.0
76.9 0.0
AT
74.2 63.5
53.0/40.8/39.
47.2 222/36.//36 34.9
49.6/35.1
44.2 /6.0/44.2 42.6
RDANN
69.3 / 66.5 66.3
53.2/43.2/42.1
/0.3 35.5
54.4/3944/
56.8 46.7 44.9
D.4 PACS
Algorithm
A
C
P
S
Avg
ERM
86.8/6.7/0
76.1/29.5/0.9
98.1/55.5/00
67.9/23.5/0.2
02.2/28.8/0.3
MLDG
86.8/10.3/0.0
75.2/30.0/0.2
97.6/62.5/0.0
76.1/29.6/0.1
83.9/33. 1/0.1
CDANN
91.3/18.3/1.0
78.4/31.4/0.
96.7/53.7/4.0
77.1/31.0/0.6
85.9/33.6/15
VREx
160.0
80.5/30.0/0.2
18.1/51.2/0.0
68.7/27.0/0..
83.4/29.
RSC
86.2/6.4/0.0
76.4/29.4/0.
97.5/59.7/0.0
72.2/27.0/0.
83.1/30.6/0.1
MAT
88.3/11 8/0.0
80.5/33.5/1.1
97.4/57.6/0. 1
77.4/32.
85.9/33.8/0.7
LDAT
87.2/8.3/0.0
76.1/26.6/0.1
97. 97.8/54.0/0.0
74.0/33. 1/0.2
83.8/30.5/0.1
AT
59. 99.8/33.
71.4/56.7/54.9
75.7/60.4/57.6
60.1/55.84 8/55.5
66.7/50.9/48.
RDANN
13.8/31.8//5..
63.3/50.5/48.2
76.8/62.3/58.2
68.5/61.8 8/611
68.1/51 1/5../1/8/88

---

D.5 OfficeHome
Algorithm
A
C
P
R
Avg
ERM
62.1/12.6/0.0
52.9/20.9/0
76.4/25.7/0.5
76.0/26.3/0.6
66.9/21 4/0.4
MLDG
61.1/13.7/0.6
12../22.1/0.7
76.5/25.7/0.3
77.4/24.0/0.9
67.0/21.4/0
CDANN
61.8/8.5/0.1
53.5/19.3/0.1
75.8/24.4/0.1
77.6/23.7/0.0
67.2/19.0/0.1
VREx
58.7/8.3/0.0
52.4/20.0/0.1
75.5/22.5/0.7
76.1/23.3/1.0
65.7/18.5/0.4
RSC
59.3/9.1/0.
52.1/18.3/0.
75.2/20.3/1.0
74.1/20.6/12
65.1/17.1V0.7
MAT
57.3/11.2/0.1
54.0/20.2/0.5
75.2/26.9/0.8
17.1/24.1/1.
66.0/20.6/0.8
LDAT
61.2/12.9/000
52.7/20.6/0.4
74.5/27 9/0.6
78.0/29.5M ./0.8
66.6/22.7/0.4
AT
29.6/16.4/14.5
44.6/36.4/35.0
53.2/40.9/38.3
53.7/36.1/32.
45.3/32.4/30.2
RDANN
30.0/17.1/15.3
41.9/33.6/32.1
48.8/3
47.1/33.5/30.8
41.9/3.6/28.6
D.6
Results for AutoAttack
D.6.1
RotatedMNIST
Algorithm
0
30
45
60
Avg
ERM
0.0
0.0
0.0
0.0
0.0
0.0
0.0
MLDG
0.0
0.0
0.0
0.0
0.0
0.0
0.0
CDANN
0.0
0.0
0.0
0.0
0.0
0.1
0.0
VREx
0.0
0.0
0.0
0.0
0.0
0.0
0.0
RSC
0.0
0.0
0.0
0.0
0.0
0.0
0.0
AT
90.6
94.7
95.5
95.3
95.0
88.6
93.3
RDANN
90.6
94.6
95.2
95.6
95.5
88.6
93.3
D.6.2 VLCS
Algorithm
C
L
S
V
Avg
ERM
0.0
0.0
0.0
0.0
0.0
MLDG
0.0
0.0
0.0
0.0
0.0
CDANN
0.0
0.0
0.0
0.0
0.0
VREx
0.0
0.0
0.0
0.0
0.0
RSC
0.0
0.0
0.0
0.0
0.0
MAT
0.0
0.0
0.0
0.0
0.0
LDAT
0.0
0.0
0.0
0.0
0.0
AT
63.2
38.7
33.9
31.4
41.8
RDANN
65.6
41.1
34.7
34.3
43.9
D.6.3 PACS
Algorithm
C
S
Avg
ERM
0.0
1.8
0.0
0.7
0.6
MLDG
0.0
0.5
0.0
0.7
0.3
CDANN
0.0
0.6
0.0
0.4
0.3
VREx
0.0
0.5
0.0
0.9
0.3
RSC
0.0
0.9
0.0
0.6
0.4
MAT
0.0
1.5
0.1
4.0
1.4
LDAT
0.0
0.5
0.0
0.9
0.3
AT
23.4
54.7
57.0
55.2
47.6
ADANN
24.5
48.2
58.0
61.1
48.0
30

---

D.7 OfficeHome
Algorithm
A
C
P
R
Avg
ERM
0.0
0.0
0.1
0.1
0.0
MLDG
0.0
0.1
0.2
0.1
0.1
CDANN
0.0
0.1
0.0
0.1
0.0
VREx
0.0
0.1
0.2
0.1
0.1
RSC
0.0
0.1
0.1
0.0
0.0
MAT
0.0
0.3
0.2
0.1
0.1
LDAT
0.0
0.0
0.1
0.1
0.1
AT
14.2
34.6
38.1
32.4
29.8
ADANN
14.0
31.5
34.4
29.7
27.4
31


Reviews:
[{"review_id": "fSZt3ISjq1", "reviewer": "Reviewer_YSCG", "summary": "The authors use statistical learning theory tools and the HdH divergence to motivate methods to improve the performance of a domain generalizing model dealing with adversarially perturbed, out-of-distribution domains. The authors evaluate two methodologies in that setting, and show how this can indeed defend models.", "questions": "No.", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. While OoD generalization is mostly concerned with improving performance on out-of-distribution domains, there is not much work on evaluating the performance of OoD-trained models on adversarially attacking an out-of-distribution domain.\n2. The two approaches studied are motivated with theory, and are shown to work well in that setting.\n", "weaknesses": "Fixing the following issues would lead me to accept the paper. They are related to toning down some claims and missing references.\n1. Missing references and comparisons. First, the relevant work of “Adversarial Feature Desensitization” by Bashivan et al. 2021. E.g., Bashivan et al. already appear to apply HdH theory to estimate adversarial generalization error bounds, etc. Your setup has some differences in that you’re using pairwise HdH distances on perturbed domains, but it still needs to mention previous HdH approaches to adversarial robustness (and potentially factor that in when making the claims). Moreover, RDANN also echoes “Generalizing to unseen domains via distribution matching” by Albuquerque et al. 2019, e.g., they train on non-perturbed domains while you do, but the logic is quite similar; RDANN would be applying Albuquerque et al.’s approach to adversarially train the model. \n2. Please correct me if I am wrong, but AERM appears to just be adversarial training as done by Madry et al. 2018 (and Goodfellow et al. 2014 before). Adversarial training is done over all samples seen during training; it’s orthogonal to having multiple domains or a single one. I value that the authors provide both theoretical motivation for it and experimental results in the particular setting of adversarial robustness of a model trained for OoD generalization. I would however avoid calling the method itself “your” contribution, or giving it a new name; it’s just adversarial training = training on the adversarially perturbed training dataset (agnostically to whether it corresponds to one or multiple domains).\n3. The benchmark/discussion of results/claims re: performance are quite strange, as they effectively compare undefended models with two defended models, so seeing an improvement in robustness is quite trivial. I suggest framing the results a bit better to avoid making it about improving over existing methods (of course it does, you’re using adversarial training), but rather discussing how adversarial training (your AERM) compares with the RDANN approach, and how on their own (instead of compared to undefended models), they provide robustness on OoD datasets that are adversarially perturbed. Interesting things with your results are that on RotatedMNIST and ColoredMNIST you do not suffer much from the usual drop in clean (= unperturbed) accuracy as you defend a model, compared to undefended models. \n\n\n**Typos and suggestions:**\n1. I believe the phrase “OOD adversarial robustness” is more indicative/suggestive of robustness against diverse perturbations, which is an existing problem, than “adversarial robustness of models trained for OoD generalization” (in fact, a google/bing search appears to confirm this view, with e.g. “Towards Out-of-Distribution Adversarial Robustness” Ibrahim et al. 2022). For minimal effort, I suggest rephrasing to “adversarial robustness of OoD” if you want to keep it short, to clear up any confusion.\n2. I suggest adding equation numbers. \n3. The equation below L250, $c_{ij}$ are introduced. I would write in the text what they correspond to (classifiers for pairs of distributions of features of perturbed domains).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable suggestions.\n\n**For weakness 1:** We are sorry for missing the references and comparisons.\n- \"Adversarial Feature Desensitization\" focuses on improving the adversarial robustness of the models by regarding the adversarial distribution as the target domain and then using the domain adaptation methods, while we focus on improving the model's adversarial robustness on the OOD distribution. Furthermore, due to the availability of the labels for source domains, we do not use $d_ {\\mathcal{H} \\Delta \\mathcal{H}}$ (the HdH distance) but use $d_ {\\mathcal{H}}$, which takes better advantages of the label information.\n- For \"Generalizing to unseen domains via distribution matching\" by Albuquerque et al. 2019, e.g, we claim that RDANN does not echo the method of Albuquerque et al. 2019.\n  - Firstly, in \"Generalizing to unseen domains via distribution matching\", the authors use $d _\\mathcal{H}(S,T)=\\underset{h\\in\\mathcal{H}}{\\sup}|P _S [h(x)=1]-{P} _T [h(x)=1]|$ to measure the discrepancy between the domains. Their algorithm computes the discrepancy by training a domain classifier, which is proven to be valid for binary case (Lemma 2, [1]). However, **in multi-class case, no theory shows that we can compute the discrepancy in this way. So in their paper, there is a gap between the theory and algorithm in the multi-class case**. While our discrepancy is defined as $d _{\\ell(\\mathcal{H})}^\\mathcal{B}(S,T)=\\sup _h|E _{(x,y)\\sim S}[\\sup _{x^\\prime\\in\\mathcal{B}(x)}\\ell(h(x^\\prime),y)]-E _{(x,y)\\sim T} [\\sup _{x^\\prime\\in\\mathcal{B}(x)}\\ell(h(x^\\prime),y)]|$, which takes the loss function and labels into consideration. Moreover, our algorithm RDANN optimizes the upper bound in Theorem 2.3 and calculates the discrepancy $d _{\\ell(\\mathcal{H})}^\\mathcal{B}$ according to its definition, which is **consistent with our theory**.\n  - Secondly, we have tried applying Albuquerque et al.’s approach to adversarially train the model, but the training is extremely unstable and the performance is quite bad. This means that directly combining adversarial training with Albuquerque et al.’s approach is not a good choice, while our theory-driven RDANN is stable and works well.\n\nThank you for your kind suggestion, we will incorporate the references and comparisons in the revision.\n\n**For weakness 2:** Yes, the AERM algorithm is equivalent to conducting adversarial training on multiple source domains. In our paper, we investigate the model's OOD adversarial robustness in two different situations, and our theory-driven AERM algorithm occasionally coincides with the adversarial training method for multiple domains (we are not just trivially applying AT in OOD generalization, but the algorithms are theory-driven).\n\n**For weakness 3:** Thank you for your meaningful suggestions. We will reframe our results to mainly compare and discuss the performance of the AERM and RDANN algorithms. The comparison and discussion about the performance of AEMR and RDANN are as follows(We will incorporate them in the revision):\n- **Comparison**. According to the experimental results in **Table 1** in the \"reply to all reviewers\" part, we can see that in the small datasets RotatedMNIST and ColoredMNIST, AERM is comparable to RDANN, while on the larger datasets VLCS, PACS, and OfficeHome, RDANN achieves better performance.\n- **Discussions**. As the paper suggests, the risk convergence rate for AERM is of order $\\mathcal{O}(t^{-0.5})$ (Theorem 2.1), while the risk convergence rate for RDANN is of order $\\mathcal{O}(n^{-0.5})$ (Theorem 2.3). Here, $t$ stands for the number of source domains while $n$ is the number of examples in each source domain. In our datasets, the number of domains is small, so the convergence rate of RADANN is faster than that of AERM, which is consistent with the superiority of RDANN on VLCS, PACS, and OfficeHome. For the comparable results on RotatedMNIST and ColoredMNIST, we think it is because the dataset is too small to distinguish which one of the two is better.\n- **Discussions for not dropping the clean accuracy on RotatedMNIST and ColoredMNIST**. In the community of adversarial robustness, it is a well-known phenomenon that there is a trade-off between clean accuracy and adversarial robustness. There are many papers trying to explain it theoretically[2] and empirically[3], so it is intuitive that there is still a trade-off between the OOD clean accuracy and OOD adversarial robustness in the OOD setting. While the experiments in [4] show that in the supervised learning setting (no distributional shift), conducting adversarial training on the MNIST dataset does not drop the clean accuracy (Table 4 and Table 5 in [4]), which is consistent with our experiment results. For the reason that the clean OOD accuracies on MNIST datasets do not drop, we think it is that the MNIST dataset is too simple.\n\n**For the typos and suggestions:**\n1. Thank you for your useful suggestions, we will correct them to clear up the confusion in the revision.\n2. We are sorry for bringing the inconvenience during the review period due to missing equation numbers, we agree that it is a good choice to add the equation numbers, and we will add them in the revision.\n3. Thank you for your reminder. In fact, in line 252, we state that $c_ {ij}$ refers to the discriminator for domain $i$ and domain $j$.\n\n\n**References**\n\n[1] A theory of learning from different domains. Ben-David et al'2010, ML.\n\n[2] Precise tradeoffs in adversarial training for linear regression. Javanmard et al'2020, COLT.\n\n[3] Towards deep learning models resistant to adversarial attacks. Madry et al'2017. arXiv.\n\n[4] Implicit bias of gradient descent based adversarial training on separable data. Li, Yan, et al'2020, ICLR."}, {"review_id": "gv6KmSKH1e", "reviewer": "Reviewer_rjrX", "summary": "This paper studies the adversarial robustness of OOD generalization algorithms. Authors claimed that existing OOD generalization algorithms fail in adversarial attacks (FGSM and PGD). To this end, authors first theoretically analyze the problem definition and generalization bound of OOD algorithms in adversarial settings. Then, they proposed two algorithms: adversarial ERM and robust DANN to solve the problem. Experiments on several datasets show the effectiveness of the algorithms.", "questions": "See weakness.", "limitations": "See weakness", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. The problem of adversarial OOD generalization is interesting and of great importance in real scenarios.\n2. The theoretical parts offer valuable insights in the algorithm design.\n3. The experimental results are showing the advantages of the algorithms.", "weaknesses": "I think this paper can be seen as a pioneering work in exploring adversarial robustness of OOD generalization algorithms, but unfortunately has many flaws:\n- Lack of related work discussion. Although the discussion of adv. and OOD is rare, there are certainly some existing works on this intersection. For instance, [Yi et al'2021, ICML] theoretically studied the bounds of adversarial and OOD generalization, and they pointed that at mild conditions, adversarial robustness can guarantee OOD generalization (Thm 3.1). And [Alhamound'2022, arXiv] studies the generalization of adv. algorithms, which is of high interest to your work.\n- The algorithms are intuitive and not novel. I highly appreciate the efforts in deriving the theories and then lead to the algorithm design. But these two algorithms are very simple and intuitive to design. For instance, the average ERM over several adv. distributions and average domain-adversarial training are easy to propose and can even be seen as baselines when one tries to solve the adv. OOD generalization problems. The only reason is that no one has explored this before. But to me, the two algorithms are very simple and not novel.\n- The theoretical part is dense, which I give my appreciation. But this part lacks enough motivation and is hard to read. I strongly encourage authors to revise this to better align with the main topic. In addition, most of the theories are based on Ben-David et al's distribution gap theory and do not present much technical novelty.\n- The experiments are lacking sufficient backbones and comparison methods:\n1. Lack of various backbones in addition to ResNet50. Have you tried Vision Transformer? ViTs are known to be better cope with adv. robustness than CNNs.\n2. Lack of other datasets. The largest dataset in this paper is VLCS, which is not enough for OOD generalization. You should at least utilize the DomainBed datasets.\n3. Lack of adversarial comparison methods. Adversarial robustness is an active area and I'm sure most of them can be applied to OOD algorithms. Authors did not compare with any existing efforts.\n4. Lack of interpretatbility. Why do the algorithms in this paper work? Or why do existing algorithms not work?\n\n\n\nReferences:\n\n[Yi et al'2021, ICML] Improved OOD Generalization via Adversarial Training and Pre-training.\n\n[Alhamound'2022, arXiv] Generalizability of Adversarial Robustness Under Distribution Shifts.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your suggestions.\n\n**Comparison with related works.** We are sorry for ignoring the related works, we now provide comparisons and will incorporate them in the revision.\n- [Yi et al'2021, ICML] studies the relationship between adversarial robustness and OOD generalization, it shows that good adversarial robustness implies good OOD performance when the target domain lies in a Wasserstein ball. While we study the OOD adversarial robustness and propose algorithms to improve OOD adversarial robustness.\n- [Alhamound'2022, arXiv] empirically analyzes the transferability of models' adversarial/certified robustness under distributional shifts. It shows that adversarially trained models do not generalize better without fine-tuning and that the accuracy-robustness trade-off generalizes to the unseen domain. Its results for adversarial robustness can also be found in our experimental results. Moreover, we find an exception that the robustness and accuracy can be reconcilable on MNIST-based datasets. We think it is due to the simplicity of MNIST-based datasets. Moreover, we provide theoretical analyses.\n\n\n**The novelty of the algorithms**\n- Firstly, the algorithms are theory-driven, we just propose algorithms to optimize the upper bounds of the target domain risk. We believe that good algorithms needn't be complicated or tricky, they just need to align well with the theory and perform well in practice. The experiments show that our methods perform well in practice.\n- Secondly, RDANN is not intuitive. A trivial method is running DANN [1] with adversarial examples, however, we have tried it but the training is unstable and the performance is bad. DANN is popular in domain adaptation **(DA)** and is based on the theory of [2]. [2] defines $d _\\mathcal{H}(S,T)=\\sup _h|P _S[h(x)=1]-{P} _T[h(x)=1]|$ and computes the discrepancy by training a domain classifier (Lemma 2), which is used by DANN. However, **in multi-class case, no theory shows that we can compute the discrepancy in this way. So there is a gap between DANN and its theory in the multi-class case**. To address this issue, we define a new discrepancy in terms of labels (the target labels are not available in DA, but source labels are provided in the OOD setting), perturbation set, and loss function, where $d _{\\ell(\\mathcal{H})}^\\mathcal{B}(S,T)=\\sup _h|E _{(x,y)\\sim S} [\\sup _{x^\\prime\\in\\mathcal{B}(x)}\\ell(h(x^\\prime),y)]-E _{(x,y)\\sim T} [\\sup _{x^\\prime\\in\\mathcal{B}(x)}\\ell(h(x^\\prime),y)]|$ and it **can characterize the multi-class adversarial robustness better**. RDANN optimizes the upper bound in Theorem 2.3 and calculates the discrepancy $d _{\\ell(\\mathcal{H})}^\\mathcal{B}$ according to its definition, which **aligns well with the theory** and makes RDANN more stable and perform better.\n\n**The presentation of the theoretical part**\n- **Logical line and the motivations**. Motivated by the failure of existing OOD generalization methods, we theoretically study the OOD adversarial robustness and derive methods to improve models' OOD adversarial robustness. We first analyze the natural case where the domains are drawn from some unknown distribution $p$, since after we deploy the system, we can naturally expect the input examples to be of different styles (i.e., from different domains). Then we get Theorem 2.1 where the convergence rate is $O(t^{-0.5})$. However, the source domain number $t$ is limited in practice, so we derive a target error bound with a faster rate $O(n^{-0.5})$ in Theorem 2.3, where $n\\gg t$. However, the term $d_ {\\ell(\\mathcal{H})}^\\mathcal{B}(\\mathcal{T},\\mathcal{T} _P)$ in Theorem 2.3 is uncontrollable since it depends on the target domain. We regard $d _{\\ell(\\mathcal{H})}^\\mathcal{B}(\\mathcal{T},\\mathcal{T} _P)$ as a quantity that describes the difficulty of the task and provide Example 1 and Theorem 2.4 to support this point.\n- **The novelty and contributions of our theory**. Our definition of the discrepancy is different from that of [2] and our theory is not based on [2]. Please refer to the second point of \"The novelty of the algorithms\" part, which indicates that **the theory of [2] only works for binary case, but our theory works for the multi-class case and describes the adversarial robustness rather than accuracy**. Furthermore, Example 1 and Theorem 2.4 show that the target adversarial robustness is related to the task difficulty measured by the $d_ {\\ell(\\mathcal{H})}^\\mathcal{B}(\\mathcal{T},\\mathcal{T} _P)$. And the experimental results align well with Theorem 2.4.\n\n**The experiments part**\n1. Our experiments are based on a popular benchmark DomainBed, where ResNet50 is the largest network. DomainBed chooses the best results in 20 runs with different random seeds, which is time-consuming, especially when we use adversarial examples. Moreover, ViT is larger than ResNet50, we cannot finish it due to time limitations but are glad to report the results in the revision.\n2. Due to time limitations, we conduct additional experiments on PACS and OfficeHome, the results are in **Table 1** in the \"reply to all reviewers\" part. The additional results are consistent with that in our paper.\n3. We claim that our methods are orthogonal to the adversarial methods. Moreover, AERM can be viewed as a variant of basic adversarial training, and it can be adapted to other adversarial training methods.\n4. Our algorithms are driven by our theory. The algorithms both try to minimize the upper bound of the target adversarial error, which is the reason that our algorithms work. Moreover, RDANN works better than AERM, which is also consistent with our theory. Note that the convergence rate in Theorem 2.1 is $O(t^{-0.5})$ and that in Theorem 2.3 is $O(n^{-0.5})$. $n\\gg t$ in practice, so it is expected that RDANN works better than AERM.\n\n**References**\n\n[1] Domain-Adversarial Training of Neural Networks. Ganin et al'2016, JMLR.\n\n[2] A theory of learning from different domains. Ben-David et al'2010, ML."}, {"review_id": "NFf7Ix5NgO", "reviewer": "Reviewer_sfFB", "summary": "The paper first evaluates the adversarial robustness of current OOD generalization algorithms and shows that existing OOD generalization algorithms are vulnerable to adversarial attacks. Then, the paper presents a theoretical analysis of the adversarial robustness (of a model) on the unseen test domain. After that, the paper designs two algorithms to improve the OOD adversarial robustness inspired by the theoretical implications. Finally, extensive experiments are conducted and the improvement is significant.", "questions": "(1) Could you provide a discussion about the differences between this paper and [1]?\n\n(2) Please provide a discussion about why the clean accuracy of the proposed methods decreases on VLCS but not on ColoredMNIST and RotatedMNIST.\n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "(1) This paper takes the first step to study the adversarial robustness of a model in the out-of-distribution generalization setting. As the extensive experiments show, existing out-of-distribution generalization methods fail under adversarial attacks, which means that it is urgent to study this problem. So, I believe that the studied problem is meaningful for the machine learning reliability community.\n\n(2) The writing is good and the paper is easy to follow. On the one hand, the proof steps are so detailed that it is easy to check the correctness of the theorems. On the other hand, after the theorems, the paper provides some remarks to show the implications of the theorems to help the readers understand the messages that the theorems convey.\n\n(3) The empirical results are strong. The improvement on the out-of-distribution adversarial robustness is significant. The experiments are extensive, and the details of the experimental settings are described in detail.\n\n(4) The proposed algorithms are inspired by the theory, which means that they are guaranteed by the theory. The theoretical analyses are technically solid. This paper not only provides theoretical results in general settings (Theorem 2.1, Corollary 2.2, and Theorem 2.3) where the data distributions and the hypothesis class are not specified but also studies an intuitive example (Example 1, Theorem 2.4 and Example 2, Theorem C.1) that presents many intuitive understandings.\n", "weaknesses": "(1) The paper [1] seems to be very relevant to this paper, but the discussions are missing.\n\n(2) The clean out-of-distribution generalization accuracy on VLCS decreases for both AERM and RDANN, however, this does not happen for ColoredMNIST and RotatedMNIST. The authors do not provide adequate discussion on this phenomenon.\n\n[1] Ibrahim, Adam, et al. \"Towards Out-of-Distribution Adversarial Robustness.\" arXiv preprint arXiv:2210.03150 (2022).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your meaningful suggestions.\n\n**For the weakness (1)**: Thank you for your kind suggestion. We are sorry for not noticing such a related work. Although the title of [1] is about the OOD adversarial robustness, the topic that [1] studies is quite different from ours. [1] investigates how to improve the adversarial robustness of a model against ensemble attacks or unseen attacks. [1] regards the adversarial examples for each type of attack (such as FGSM, PGD, CW, and so on) as a domain, and utilizes the OOD generalization methods to improve the models generalization performance under different (maybe unseen) attacks. While we study the adversarial robustness of a model on the unseen target domain. \n\n**For the weakness (2)**: In the community of adversarial robustness, it is a well-known phenomenon that there is a trade-off between the clean accuracy and adversarial robustness. There are many papers trying to explain it theoretically[2] and empirically[3], so it is intuitive that there is still a trade-off between the OOD clean accuracy and OOD adversarial robustness in the OOD setting. Perhaps the more interesting phenomenon is that the OOD clean accuracies on RotatedMNIST and ColoredMNIST do not drop. The experiments in [4] show that in the supervised learning setting (no distributional shift), conducting adversarial training on the MNIST dataset does not drop the clean accuracy (Table 4 and Table 5 in [4]), which is consistent with our experiment results. For the reason that the clean OOD accuracies on MNIST datasets do not drop, we think it is that the MNIST dataset is too simple.\n\n**For the questions:** Please refer to the answer to the weaknesses.\n\n\n**References**\n\n[1] Ibrahim, Adam, et al. \"Towards Out-of-Distribution Adversarial Robustness.\" arXiv preprint arXiv:2210.03150 (2022).\n\n[2] Javanmard, Adel, Mahdi Soltanolkotabi, and Hamed Hassani. \"Precise tradeoffs in adversarial training for linear regression.\" Conference on Learning Theory. PMLR, 2020.\n\n[3] Madry, Aleksander, et al. \"Towards deep learning models resistant to adversarial attacks.\" arXiv preprint arXiv:1706.06083 (2017).\n\n[4] Li, Yan, et al. \"Implicit bias of gradient descent based adversarial training on separable data.\" International Conference on Learning Representations. 2020."}, {"review_id": "P2KX6AUywL", "reviewer": "Reviewer_sycY", "summary": "This paper studies the adversarial robustness of models on the unseen target domain. Firstly, exhaustive experiments show that existing OOD generalization methods are vulnerable to adversarial attacks. Then, a theoretical analysis for the OOD adversarial robustness is presented. Finally, this paper proposes two methods (AERM and RDANN) based on the theoretical results.", "questions": "As I said in the weaknesses part, would you please provide additional experimental results for other datasets (at least one) in DomainBed?", "limitations": "No.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The topic of this paper is novel and the paper considers two perspectives of trustworthy machine learning, which is very useful in practice. I agree with the authors that the adversarial robustness of the model on the OOD domain is very important since in the real-world task, the data we face always has a different style from what we use during the training stage.\n- The theoretical analysis is strong and interesting. The authors provide theoretical analyses in two different settings (the average setting and the agnostic setting where the distance between the training domains and the test domain is unknown), which cover the practical cases according to how many domains we can sample from. I think the theoretical analysis of this paper is very comprehensive.\n- According to the experimental results, the proposed methods significantly improve the OOD adversarial robustness. Furthermore, the observations on RotatedMNIST and ColoredMNIST are quite interesting and are consistent with the theoretical results of the two examples, which motivates researchers to consider the hardness of the tasks in OOD generalization. \n- The paper is well-written. The details of the methods are adequately explained, the proofs of the theorems are presented step-by-step, and the meaning of the theoretical results is discussed in detail.\n", "weaknesses": "- There are other datasets in the DomainBed benchmark, however, the experiments are conducted only in three datasets (RotatedMNIST, ColoredMNIST, and VLCS). Although AT is time-consuming and DomainBed involve running many groups of random parameters, I think the authors show add at least one more dataset in DomainBed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your meaningful suggestions.\n\n**For the weaknesses:** Thank you for your suggestion, we have extended our experimental results to the PACS dataset and OfficeHome dataset in DomainBed, please refer to **Table 1** in the reply to all reviewers part. From the table we can see that: on the datasets PACS and OfficeHome, the baselines achieve **no more than $2\\%$** average adversarial accuracy under the attack PGD-20 and AutoAttack. Again, our proposed methods can significantly improve the average adversarial accuracy, which is consistent with the results of the experiments in our paper.\n\n\n\n**For the questions:** Please refer to the answer to the weaknesses.\n"}]

Author rebuttal:
# The reply to all reviewers

We would like to thank all the reviewers for all your valuable suggestions, which help us improve the quality of our paper.

According to the suggestion of reviewers, we conduct extra experiments on the datasets PACS and OfficeHome. We present the new results in Table 1.

**Table 1**: The OOD adversarial robustness of the models trained by the baselines and our algorithms (%). Results are presented in the form of **a/b**, where **a** is the OOD adversarial accuracy under PGD-20 attack; **b** is the OOD adversarial accuracy under AutoAttack. The other settings are the same as the Tables in our paper.
| Algorithm | RoatatedMNIST | ColoredMNIST | VLCS | PACS | OfficeHome |
| :----: | :----: | :----: | :----: | :----: | :----: |
| ERM | 0.6 / 0.0 | 5.8 / X | 0.0 / 0.0 | 0.3 / 0.6 | 0.4 / 0.0 |
| MLDG | 0.2 / 0.0 | 4.8 / X | 0.0 / 0.0 | 0.1 / 0.3 | 0.6 / 0.1 |
| CDANN | 0.9 / 0.0 | 8.2 / X | 3.0 / 0.0 | 1.5 / 0.3 |0.1 / 0.0 |
| VREx | 0.2 / 0.0 | 6.4 / X | 0.0 / 0.0 | 0.0 / 0.3 | 0.4 / 0.1 |
| RSC | 1.0 / 0.0 | 3.9 / X | 0.0 / 0.0 | 0.1 / 0.4 | 0.7 / 0.0 |
| MAT | X / X | 10.7 / X | 0.0 / 0.0 | 0.7 / 1.4 | 0.8 / 0.1 |
| LDAT | X / X | 7.9 / X | 0.0 / 0.0 | 0.1 / 0.3 | 0.4 / 0.1 |
| **AERM (ours)** | 93.4 / **93.3** | **51.6** / X | 42.6 / 41.8 | **48.1** / 47.6 | 28.6 / 27.4 |
| **RDANN (ours)** | **93.5** / **93.3** | 51.1 / X | **44.9** / **43.9** | **48.1** / **48.0** | **30.2** / **29.8** |


**Table 1** shows that: On the datasets PACS and OfficeHome, the baselines achieve **no more than $2\\%$** average adversarial accuracy under the attack PGD-20 and AutoAttack. Again, our proposed methods can significantly improve the average adversarial accuracy, which is **consistent** with the results of the experiments in our paper.

Meta-review: The paper received mixed reviews. On the positive side, the reviewers found the paper to be well written, strong theoretical motivation, and good empirical results to support them. On the negative side, one reviewer found the paper to be lacking novelty. However, the other reviewers found the paper to be novel and interesting. The AC agrees the paper has interesting results.
Decision: Accept (poster)