Rademacher Complexity Over $\mathcal{H} \Delta \mathcal{H}$ Class for Adversarially Robust Domain Adaptation
Authors: Yuyang Deng
Nidham Gazagnadou
Junyuan Hong
Mehrdad Mahdavi
Lingjuan Lyu
Venue: Submitted to ICLR 2023 (2023)
Keywords: domain adaptation
learning theory
adversarial learning

Abstract: In domain adaptation, a model is trained on a dataset generated from a source domain and its generalization is evaluated on a possibly different target domain. Understanding the generalization capability of the learned model is a longstanding question. Recent studies demonstrated that the adversarial robust learning under $\ell_\infty$ attack is even harder to generalize to different domains. To thoroughly study the fundamental difficulty behind adversarially robust domain adaptation, we propose to analyze a key complexity measure that controls the cross-domain generalization: the adversarial Rademacher complexity over $\mathcal{H} \Delta \mathcal{H}$ class. For linear models, we show that adversarial Rademacher complexity over $\mathcal{H} \Delta \mathcal{H}$ class is always greater than the non-adversarial one, which reveals the intrinsic hardness of adversarially robust domain adaptation. We also establish upper bounds on this complexity measure, and extend them to the ReLU neural network class as well. Finally, by properly extending our generalization bound for adversarially robust domain adaptation, we explain \emph{why adversarial training can help transferring the model performance to different domains}. We believe our results initiate the study of the generalization theory of adversarially robust domain adaptation, and could shed lights on distributed adversarially robust learning from heterogeneous sources -- a scenario typically encountered in federated learning applications.

Under review as a conference paper at ICLR 2023
RADEMACHER COMPLEXITY OVER HAH CLASS FOR ADVERSARIALLY ROBUST DOMAIN ADAPTATION
Anonymous authors
Paper under double-blind review
ABSTRACT
In domain adaptation, a model is trained on dataset generated from source domain and its generalization is evaluated on a possibly different target domain. Understanding the generalization capability of the learned model is longstand- ing question. Recent studies demonstrated that the adversarial robust learning under Lo attack is even harder to generalize to different domains. To thoroughly study the fundamental difficulty behind adversarially robust domain adaptation, we propose to analyze a key complexity measure that controls the cross-domain generalization: the adversarial Rademacher complexity over HAH class. For lin- ear models, we show that adversarial Rademacher complexity over HAH class is always greater than the -nnaarersaaial one, which reveals the intrinsic hardness of adversarially robust domain adaptation. We also establish upper bounds on this complexity measure, and extend them the ReLU neural network class as well, Finally, based on our adversarially robust domain adaptation theory, we explain different
how adversarial training helps transferring the model performance domains. We believe our results initiate the study of the generalization theory of adversarially robust domain adaptation, and could shed lights on distributed adversarially robust learning from heterogeneous sources a scenario typically encountered in federated learning applications.
INTRODUCTION
Domain adaptation is key learning scenario where tries generalize the model learnt source domain to a target domain. How to predict target accuracy using source accuracy has been longstanding research topie in both theory [Ben-
al.] (2006); (Quinonero-Canie
et al.)
20088; (Ben-David et al. (2010); Mansour et al. (2009); Cortes et al. (2015); Zhang et al. (0019) 2020) and application community Long al. (2015): Saito et al. (2018); You et al. (2019). From
a theoretical perspective, this problem can be attacked by establishing bounds on the generalization of the source-domain-leatee learnt model on target domain, using different complexity measures including the VC-dimension Ben-David et al. (2006) 2010); Zhang et al.) (2020) and Rademacher complex- ity Mansour et al. | (2009); /Zhan et al. (0119). ). particular, the latter works Mansour et al.) (2009); Zhang et al. (2019) rely on the Rademacher complexity over a so-called HAH function class to bound the gap between source and target generalization risks:
Definition 1 Mansour et al. (2009)) Let hypothesis space H. be set of real (vector)-valued functions defined over inpul spuce X and label space y: H (hw : X + y) each parameterized by E W C R.d and f. y y + Th,, be the loss function. Given dataset (x1,..., Xn) sampled
i.i.d. from distribution D defined over X, the empirical Rademacher complexity of HAH over this
dataset is defined as follows:
1 Σ a, Now (xx,)
Lp o HAH) = E,
sup EH 3=1
(1)
where on,...,On are i.i.d. Rademacher random variables with Plao = P(oo=
Intuitively, above quantity measures how well the loss vector realized by two hypotheses within H correlates with random vectors. The better correlation will imply richer hypothesis class. How- ever, unlike the classical Rademacher complexity whose loss vector is computed between predic- tions made by hypothesis and true labels, Eq. (1) is defined merely over predictions made by two

---

Under review as a conference paper at ICLR 2023
hypotheses. Authors of Mansour et al. (2009); Zhang al. (2019) have shown that this complexity measure controls the domain adaptation generalization bound. Unfortunately, none of those works give the precise analysis of AD o HAH). To our best knowledge, Kuroki et al. 2019 is the only prior work to analyze Rp ( HAH) on linear classifier class, but their analysis is not tight. Due to the importance of such complexity measure, we are interested in characterizing how large this complexity measure can be in terms of model dimension and data diversity, even on some toy model. c.g., linear model. Hence, the first question we investigate in this paper is: for linear models, what quantities control the Rademacher complexity over HAH function class?
Meanwhile, in modern machine learning, practitioners are not only interested in transferring stan- dard model accuracy to another domain, but also in transferring robustmess. Consider adversari- ally robust risk over domain D: Rodo- tabell (hw. yy) Ex~D [mx]]|]] ((ww (x + 8), yo (x))], where (-(-) is the labeling function. In the adversarially robust domain adaptation problem, we are curious about the robust risk when the same model ho is tested on the new domain D' Unfortunately, shown empirically [Shafahi et al.] (2019); HHng al. (202I); Fan et al. (2021), robust model learnt on source domain will lose its robustness catastrophically on a different do- main. That is, the gap between robust risks on the old domain and new domains be dramatically huge, compared to the standard risk. This observation naturally leads to the question Why is the robust risk harder adapt to different domains?? which we aim to examine in this paper. To answer this question, inspired by the Rademacher complexity over HAH function class, we properly extend this complexity measure the adversarial learning setting, and propose the adversarial Rademacher complexity over the HAH class. We show that, the ad adversarial version complexity is always greater than its non-adversarial counterpart, similar to the results proven in Yin al. (2019) in the single domain setting. Relying on this new complexity measure, for the first time, we characterize the generalization bound of adversarially robust learning between source and target domain.
Recent studies Salman et al. (2020); Deng et al. (202T) also show that, the model trained adversar- ially on the source domain, usually entails better standard accuracy on target domain, compared to the normally trained model. In this paper, by further exploring our generalization bound, we show that given large enough adversarial budget, small source adversarially robust risk will almost guarantee small target domain standard risk, with the residual error controlled by This con- nection between source robust risk and target standard risk theoretically supports the advantage of performing robust training in domain adaptation tasks.
Our contributions are summarized as follow:
We study the Rademacher complexity over H.H. class, and propose the adversarial variant of it, which is new complexity measure towards better understanding the domain adaptation in adver- sarial learning. In both linear classification and regression settings, first show that adversarial Rademacher complexity over HAH class is greater than its non-adversarial counterpart. We also show that adversarial complexity is smaller than its non-adversarial counterpart plus residual terms polynomially depending on data dimension, model norm and adversarial budget.
We generalize our results to ReLU neural networks, where we derive the similar upper bounds of adversarial H Rademacher complexity of a 2-layer ReLU neural network.
We also establish the connection between robust learning and standard domain adaptation, which helps explain the hidell-observed phenomena that adversarially trained models can have good generalization performance on different domains.
We support our theoretical analysis by providing experiments illustrating how adversarial training can help domain adaptation, especially with l regularization. We also highlight numerically the difficulty of transferring adversarial robustness across domains.
2 PROBLEM SETUP
We adapt the following notations throughout this paper. We lower case bold letter denote vector, e.g., w, and use upper case bold letter to denote matrix, e.g., M. We use ||w/pp and [M]] I denote fy-norm of vector w and matrix M respectively. We define the (p, g)-group norm as the [M]]| p.g := [I( | .-..... || llg where the m,s are the columns of M.
2

---

Under review as a conference paper at ICLR 2023
We use D: X' + R to denote data distribution (domain) defined over instance space X, and D be the empirical distribution with nop samples drawn i..d. from D. We let H. := (hw X ++ } be the hypothesis space, and vector
E W R denotes the model parametrization of hw- Given a loss function 8 y x y - R, and a data distribution 'D, we let (D hw:l:/,ww))))))))))))))))>)))h == Ex (((1w(()) hww (x))] be the risk of the disagreement between models hw and hww domain D. Specially, when the second argument of RD(:,-) is the labeling function over D, it becomes the commonly used risk function. We also define twO adversarially robust risks: (I) Model-label robust risk as R-D Rade-labell risk as RRy (hyd (lww:bw))) = Ex-D [max| Se E(hw (x + 6), hw (x 6))]
(lw: v) = Ex-DD [max] Se E(ow (x 0), (x)) and (2) Model-model robust
In the domain adaptation scenario, we consider source domain S and target domain T distributions, and let I and S be the empirical source and target distributions with ngg and nt samples. A key quantity that controls the generalization in domain adaptation is the following discrepancy measure: Definition (H.H. discrepancy Mansour al. (2009); (Ben-Bavid al. (2010). Given hypothe- sis class H. risk function RD(..) ). HAH discrepancy between distributions S and TT is defined by:
discHAH(S,T)
max Aww Bow EH (Rs how) - R. (Rew Newwshew Now
The HAH discrepancy defines a semi-distance over two distributions, and it does not depend on the labeling function of two distributions hence invariant to potential model shift across domains.
Another advantage of it, is that it can be efficiently estimated by finite samples, if the Rademacher complexity over HAH is finite. Hence based Definitions [ and Mansour al. 2009) derived the following generalization bound among source and target domains.
Lemma (Domain adaptation generalization lemma, consequence of Theorem of Mansour et al. 2009)). Assume that the loss function i is symmetric and obeys the triangle inequality. We further
assume is bounded by M. Then Vhw E H, the following holds with probability at least 1 C:
Ry (rwwhwr) I (h (wg)) + discHan(S, + RT RRyhh hwg) + R (hww. :T) VT)
log(2/c) + 3M
log(2/c)
+ RE o HAH) + Rt( HAHH) + 3M
n&T
where yr the labeling function on target domain, hwz hwg are the best target and source models in H. i.e. hwg arg mingeR. R& (h, ys) and hw; = arg minnen Ry (h.
The above bound successfully connects the target risk and source risk, with the help of Rademacher complexity over HAH and disCHAR distance. It turns out that, Rs HAH) and R (E H.H) are the key complexity measures that control the generalization between different domains. Hence, to study the generalization of domain adaptation in the adversarial setting, it naturally motivates us to consider the following adversarial robust variant of this measure as defined below.
Definition (Adversarial Rademacher complexity over HAH class). Let H be a set of real-valued hypothesis functioos: H = (hw X + V}, and E(.,-) y y + I. be the loss function. Given dataset (x1...,x,, x,} sampled from distribution D, the empirical adversarial Rademacher complexity of HAH over this dataset is defined follows
Ap HAH) = E,
sup bw New EH
Σ
oi max E(bw (x; + 8), Now (x; + +5))
(3)
1881
where oI,...., on are i.idd. Rademacher random variables with Pfo;; = 13 Pfo; -13
As we can see, 3 is defined over the class:
i HAH = { x max e(1ow( + 8), Aow /x + 8)): lww, how E H || Se
We will see later how this quantity controls the generalization of adversarial domain adaptation. We also generalize HAH discrepancy to the adversarial setting:
Raddo tobel and Rade also called constant-in-ball risk and exact-in-ball risk in Gourdeau al. 2021
3

---

Under review as a conference paper at ICLR 2023
Definition 4 (Adversarial HAH discrepancy). Given hypothesis class H. risk function Ro (..)), the adversarial H.H. discrepancy distance between two distributions and T defined by:
max (R (bw; Now)) R.g (Now; low))
disCHaH Aww EH
The definition of adversarial H.H. discrepancy is analogous to standard one, and for linear models can indeed be estimated as function of the latter. We defer this result to Appendix F Lemma 19
Lemma 2 (Adversarially robust domain adaptation generalization lemma). Assume that the loss function & is symmetric and obeys the triangle inequality. We further assume é is bounded by M.
Then, for any hypothesis w H. the following holds:
Radv-label label
Ry
(lw, vT) S Ri Radu-label Lobel (lo 118 R Radv- label (lw''s MS)
+ discHAn (T, R (hw7: hw + Ry - label (Iw7,330 y7)
Rs(l HAH) + Rro HAH) + 3M 12g(2/c)
log(2/c)
+ 3M
ns.
The proof of Lemma 2 is deferred to Appendix Here we establish the relation between source adversarially robust risk and target adversarially robust risk. It shows that the adversarial discrepancy and adversarial complexity measure Rt HAH) source and target domains the key quantities controlling the deviation between the model's performance on the two domains. Hence, answer our previously proposed question, why the robust risk is harder adapt to different domain, it is essential to study the connection between adversarial and non aon-adversarial Rademacher complexities over HAH class.
3
MAIN RESULTS
3.1 BINARY CLASSIFICATION SETTING
We start with the binary classification problem where the labels come from [-1,+13, Like in Section 4.1 of Yin et al. 2019), we introduce the hypothesis class of linear functions with bounded weights:
H. = {hw x + (w, x) w E Rdd //wl, S W}
(5)
where p 2 1. Moreover, we consider the following loss ((ww((), y) == (yy (x)) where & is monotonic non-increasing and T. Lipschizt function. With such loss Φi, the non-adversarial class of loss functions over H.H becomes
o HAH = {x + 6(hw (x), how (x)) = (x))(x)// ( (x)) lw: ho E H
However, directly analyzing e HAH class will be difficult since do not assume the formula of & explicitly. Hence, following Yin et al. 2019), let us define the following class of functions
f HAH = {x -> hw (x))w(()) Pow how E H
We switch from the study of the Rademacher complexity defined I over the function class introduced in (5) that is for linear classifiers applied to binary classification, to the following formula
RD o HAH) E,
sup w.w': w|l W w/ SW n
oow x, WT x;
(6)
Indeed, by Ledoux- Talagrand contraction property Ledoux & Talagrand 2013) of Rademacher complexity we have that At HAH) & LoRi o HAH). Thus, in the following lemma we aim at estimating RD( HAH).
4

---

Under review as a conference paper at ICLR 2023
Lemma 3 (Rademacher complexity for binary classification under linear hypothesis). Consider hypothesis class defined in (5) Assume that a set of data {x1,..,X,, are draw from D. Let Rif o HAH) be defined as in 66 Then the following statement holds true for non-adversarial Rademacher complexity:
RD HAH)
W Σ xxxx] ))xx)
)²
log(2d) +
X
2 2,00
(2d)
{
{1,
1 1/1 p> 2
n
where X RRnxd is the data matrix and i-th row of X x;
The proof of Lemma is deferred to the Appendix G.1 Lemma shows that the magnitude of the non-adversarial Rademacher over HAH class depends on the spectral norm data covariance ma- trix. It implies that more diverse dataset will result in a larger Rademacher complexity, and hence harder to perform domain adaptation. We notice that Kuroki et al. (2019) also gave an estimation of the upper bound of (f HAHH in their Lemma 5, but our bound is superior to theirs in the following two aspectives: (1) Our bound is tighter in terms of the dependency covariance matrix, (xxx))20 II
since our bound depends on |-i=1 (x,x,] )²l1, while their bound depends on Σ;= [|xxx; (2) We consider that model capacity is controlled by p-norm while they only consider 2-norm.
Then, let us specify the class of functions involved in the definition of the adversarial Rademacher complexity of HAH in follows:
H1 }
i HAH =
@(hw 80 (x + 8)) Aw how E H ENJ.
max 1ô
and let us define
HHH { {x+> min h 5)ll + 8) lww ho E HH)
||8| Se
With the above notations, can characterize the adversarial counterpart of (6) Again by Ledoux- Talagrand's property, as in Yin et al. 2019g Awasthi et al. 2020)), get that Rp HAH) s Rf a HAH), where
RD(f HAH) Ee
sup I,, s, 71 oi min w (x: + 80w' (x; + 6) TT(xx [1
(8)
Theorem (Adversarial Rademacher complexity for binary classification under linear hypothesis), Consider hypothesis class defined in (5). Assume a set of data {xI, Xn) are drawn from Let ( o HAH) and RD o HAH) be defined as in (6) and (8), respectively. The following statement holds true for adversarial Rademacher complexity over HAH function class under linear hypothesis (5):
W Vn
(1+ (1+Vdv/og(3//n log(3 (ed"/0" +2|
RD - HAH) & RDlf HAH)
/d
where pd is such that 1/p - 11pp"pp"- 1, and X E BRxd is the data matrix and i-th row of X is X,.
Moreover, the following lower bound also holds:
0,
1sp52 p>
Rp o HAH) 2 Rp HAH)
+
W
dl 2//0/E D x 1l.
(9)
The proofs for Theorem I are deferred to Appendices and From 1.. we notice that the upper bound of RD(f f HAH) has the smallest dependence in model dimension d the weights are constrained by the f--nrrm (p 1). This is a similar observation in Yin et al. (2019) where they consider single domain setting. However, in their single domain setting, when p I, adver- sarial Rademacher complexity is dimension free while we still have vd dependency. This heavier dependence is likely due to the fact that RD HAH) is defined by coupling two models and hence enlarges the complexity. The bound achieves the sublinear convergence ((1/vn) over the number
5

---

Under review as a conference paper at ICLR 2023
of samples and quadratic dependence maximum model weight W. It implies that models with suppressed norm can help adversarially robust domain adaptation since it reduces the Rademacher complexity,
will see in the experiments.
The lower bound result in ( shows that, adversarial Rademacher complexity over HAH will be always larger than non-adversarial one, which implies that adversarial robust domain adaptation is at least as hard as non-adversarial domain adaptation, and that is why, as we will also see in our experiments, given model, the gap between its source domain robust risk and target domain robust risk is usually larger than that in terms of standard risk. Moreover, the gap between adversarial and non-at adversarial complexity is controlled by the spectral norm of Rademacher variable induced covariance matrix. This dependence reveals that more diverse dataset would be harder to transfer robustness, compared the standard domain adaptation.
3.2 LINEAR REGRESSION SETTING
In this section consider linear regression problems. The hypothesis class of linear functions with bounded weights remains the same as in (5). However, we consider the following class of quadratic loss functions:
fo HAH == {x+ (xhw(x), how (x)) (hw (x) hww (x)))² hw hw E H}
(10)
The following lemma establishes the upper bound non-adversarial Rademacher complexity over HAH in the above setting.
Lemma 4 (Rademacher complexity for regression under linear hypothesis). Let H be the set of linear functions with bounded weights as defined in (5). Then the following statement holds true for non-adversarial Rademacher complexity over H.H class:
4W2
{1
1sp52 (2--//2 p> 2
(e HAH))
Σ (xxx] D2
log(2d) - |XX log(2d)
where X E Raad is the data matrix and i-th row of X is X
As in the binary classification case presented in Section 3.1 we are able to relate the non-adversarial Rademacher complexity over HAH class to the spectral norm of data covariance matrix.
The proof of Lemma is deferred to Appendix H.I
Theorem (Adversarial Rademacher complexity for regression under linear hypothesis). Let H be the set of linear functions with bounded weights as defined in (5) Then the following statement holds true for adversarial Rademacher complexity over HAH function class:
Rp HAH) < Rp e HAH)
+4 Vn @ + dé?) (vddlog(6VT) + +1) 221 p>
2
(1, 1Sp52
where X Raad is the data matrix and i-th row X is x,, Meanwhile, the following lower bound holds as well:
0, aw2 (1 d' 2//0)
1Sp52 En x 11a p> > 2
Ro( o HAH) 2 (e HAH) +
The proof of Theorem is deferred to Appendices H.2 and H. Few comments can be made concerning the above theorem. First, the upper bound adversarial Rademacher complexity also depends quadratically on W and adversarial budget and super-linearly ond, for the lower bound, established the similar gap between (i HAH) and ( as in classification setting, which means the data diversity also affects hardness of adversarially ro- bust domain adaptation in regression setting.
model dimension d. Sec-

---

Under review as a conference paper at ICLR 2023
4 EXTENSION TO NEURAL NETWORKS WITH RELU ACTIVATION
We next extend our analysis methods to more complicated neural network function class. In this section, will present results for two-layer ReLU neural networks. That is, consider the following hypothesis class
H. = (hw x a
TT ReLU a Rd, W Raxd ||llp I A, I S W).
(11)
The following theorem establishes the relation between Adversarial Rademacher complexity and non-adversarial version in classification setting. As in Section 3.1 we consider the same loss func- tions of the form Elhw (x).y) = @lyhw (x)) in classification sctting, and la loss in regression setting.
Theorem 3 (Adversarial Rademacher complexity on ReLU neural network class). Let H be the set of two-layer ReLU neural networks with bounded weights as defined (II). Then, the follow- ing statement holds true for adversarial Rademacher complexity over H. F. function class, with classification loss
RD (f HAH) & Ro(s HAH)
A²w (2gg
{L 1sp52 p 2
E (vde + 2|xx111))+ Vlog(2d)(VV) + 21
(
Similarly the following statement holds true for adversarial Rademacher complexity over H.H function class with &g loss:
R6 HAH) (o HAH)
2 2 ev (2d) 3
[1.
1 1sp52 d2-A/1,, p>
2 2e
(vde + 211x11122 + Vlo((dd 22
n
The proof of Theorem is deferred to Appendices and 1.2 theorem, get the similar upper bound for ReLU neural network class to what showed in the linear model case. The upper bound of adversarial Rademacher can be bounded by non-adversarial version plus terms depending the norm of each layer, and the norm of data points. We would like to mention that, unlike the linear case where we show that the gap between adversarial and non- adversarial Rademacher complexity is lower bounded, here do establish such lower bound, due to the difficulty of analyzing ReLU unit.
As we can see from the above
5 ADVERSARIAL TRAINING HELPS TRANSFER TO DIFFERENT DOMAIN
Here we discuss the connection between standard ERM learning and adversarially robust learning. As observed by prior works (Sllmnn al. (2020); Deng al. (202T), if model is adversarially trained on the source domain, then its standard accuracy on target domain is sometimes better than it had been fitted via vanilla ERM on source domain. In this section, we try explain this phe- nomena from adversarially robust domain adaptation perspective. We found that, when adversarial budget is large enough, small source adversarial risk almost guarantees the small target domain standard risk. First, we need to introduce the following optimization problem.
Definition 5. Let p and p' be two vectors on the N-dimensional simplex and let & be a 0-1 vector: Let also A be arbitrary subset of [N] (1.....NN, The Subset Sum Problem with Structural Objective can be defined as solving the following combinatorial optimization problem:
min ŁE(0,1)N
? = l. Vie S.1.
We denote its optimal value as V V'(p'pp,,,
The above problem is a variant of Subset Sum Problem Hartmanis (982). which is also NP. complete. We look for subset of coordinates of simplex vector p. such that their sum is closest

---

Under review as a conference paper at ICLR 2023
to given goal. The given goal has special structure: it is defined as sum of subset of coordinates in another simplex vector p'. If the constraint set Ae has more indices, the optimal value will be smaller since we can determine the value on more coordinates of l. In the following lemma, we explain how this combinatorial measure helps us to connect adversarially robust and standard risks for the binary classification task.
Lemma 5. Consider binary classification task, with sign linear classifier class H = {ho ho sign(w w ||llp S } and 0-1 loss function ((x,)) y) = - y/. Assume all domains share the same labeling function v(x) E {-1,1). The following statement holds for any T':
RT. S Ro (lw, y) (p'.pp,,AA)).
where & is the loss vector such that E. = 3 sisin(( w T x:) ) (xx)l, with x; E X. The vectors P. p' are probability mass vectors of TT and T ie., p(x) = Px x), E X and p'(x) Px~ = x),x E X Moreover, A. = {d: w x S c/|w||1. E X, Vw. [ S W).
The corresponding proof is given in Appendix J Lemma shows that, the standard risk on domain T' can be bounded by robust risk on domain : plus the quantity controlled by c. Since the set A, stores all indices such that we can choose to flip & value between 0 and then if we have larger e, there will be more indices in Ac, which means there are more coordinates in l we can play with, and hence smaller value of V*
6 EMPIRICAL RESULTS
In this section, we verify the theoretical implications through empirical studies on a multi-domain dataset, DIGITS Ganin & Lempitsky (2115). DIGITS has 28 x 28 images and includes 5 different domains: MNIST (Lecun et al. 1998), SVHN (Netzer et al., 2011). USPS (Hull 1994). SinthDigits (Ganin & Lempitsky/ 2015), and MNIST-M (Ganin & Lempitsky 2015). All domain datasets
subsampled to contain 7438 images to eliminate the effect of number of samples in generalization.
Given model hw parameterized by w, consider two training methods:
Adversarial Training: min " 1=1 w
max E(hw (x: + +8), vx,)),
(12)
10 Se
Standard Training: min w n
Σn
E(ti (x:), 1=1
(13)
To solve the inner maximization in (12), we leverage k-step PGD (projected gradient descent) attack (Madry et al. 2018) with a constant noise magnitude e. Following (Madry et al., 2018). we use 7, and attack inner-loop step size 2/255, for training, and adversarial test. Then we use Adam to minimize the losses with 100 epochs and learning rate of 10-2 decaying in cosine manner. We evaluate the model performance by: (1) standard accuracy (SA): classification accuracy on the clean test set; and (2) robust accuracy (RA): classification accuracy adversarial images perturbed from the original test set.
c88/25,,
How does adversarial robustness transfer arcoss domains? In this experiments, we use a volutional network whose architecture elaborated in Appendix K We report the transfer accuracy in Table where models are trained on source domain (first column in each row) and tested on dif- ferent target domains (the rest columns), as well as the difference between source SA/RA and target SA/RA. The experiment has the following implications: (1) We observe that transfer difference A is more significant on RA than SA. For example, for the model trained on MNIST dataset, no matter trained standardly or adversarially, their testing RAs on all other domains drop dramatically than SAs. It implies that ad adversarially robust domain adaptation is harder than standard domain adapta- tion, illustrated by Theorem [ (2) The models trained on complicated dataset may gain higher robust accuracy at simple dataset, e.g., SVHN - (MNIST, SynthDigits and USPS} and MNIST-M + MNIST. The increase can be attributed to that the source domain has more complicated features and thus more robust features are learnt. However, exploring the reason behind this interesting phenomena is beyond the scope this paper.
8

---

Under review as a conference paper at ICLR 2023
Table I: Transferred standard (SA %) and robust (RA %) accuracies tested on different domains from the DIGITS datasets. A indicates the difference between the train and test domain accuracy.
Target
MNIST
MNIST-M
SVHN
SynthDigits
USPS
Source
SA
RA
SA
RA
SA
RA
SA
RA
SA
RA
Standardly-trained models
Acc
98.8
95.9
34.7
15.3
16.0
5.9
25.0
7.8
49.9
27.9
MNIST
A
40..0
40.0
-64.1
-0.6
-82.8
90.1
- 73.7
88.2
-8899
-6800
Acc
97.2
76.7
94.1
28.5
33.9
0.0
49.1
1.7
63.6
5.3
MNIST-M
A
4-3.1
+48.2
+00.0
+0.00
60.2
28.5
45.0
26.8
30.55
-23.2
Acc
59.6
32.7
47.2
5.2
87.5
6.0
84.3
28.4
64.5
22.5
SVHN
A
-27.9
+26.7
-40.3
-0.8
+0.0
+0.0
-3.2
+22.4 .
22.99
+16.5
Acc
83.6
57.0
57.9
9.1
73.0
3.8
96.1
59.8
82.7
40.4
SynthDigits
A
12.5
-2.
-8.22
50.7
23322
56.1
+0.0
+0.0
-13.4
19.4
Ace
67.0
54.3
25.8
13.1
9.6
5.1
31.2
13.1
98.7
94.1
USPS
A
-31.7
39.8
- 73.0
80.9
89.2
89.0
67.6
81.0
+0.0
+-0.0
Adversarially-trainnn models
Acc
99.0
98.3
49.5
31.9
19.4
14.6
32.2
17.3
59.7
38.8
MNIST
A
+0.0
+0.0
-99.5
-66.4
-79.6
-83.7
66.9
-81.0
39.44
-59.5
Acc
96.9
94.5
93.0
76.8
26.9
11.5
46.4
25.4
66.5
46.8
MNIST-M
A
444.0
+17.7
40000
+0.00
65.3
46.5
-1.4
26.5
30.0
Acc
56.2
46.6
43.3
18.0
76.2
12.6
78.9
60.2
66.8
51.3
SVHN
A
-0.00
+4.0
32.9
24466
+0.0
+0.0
+2.7
+17.6
99.3
+8.7
Acc
84.9
75.6
58.0
25.8
64.1
17.9
95.6
84.8
82.6
64.8
SynthDigits
A
10.6
-9.2
-37.6
-5.11
-31.5
-6.9
+0.0
+0.0
-3300
Acc
72.3
65.6
24.1
15.4
9.7
5.3
30.1
16.8
98.9
97.5
USPS
A
26.6
31.9
-7.8
82.2
89.1
92.3
68.8
80.8
+0.0
+0.00
60
4 regularization
Adversarial training helps domain adaptation. We can see from Table sometimes when models are adver- sarial trained on simple dataset (e.g., MNIST and Syn- thDigits dataset), it is noticeable the standard accuracy on other datasets improved. For example, if we do ad- versarial training on MNIST dataset, we achieve signifi- cantly higher SA other dataset, than standard trained model on MNIST. The same phenomena happens when choose SynthDigits USPS source domain. Such advantages are consistent with our Corollary 3
0.0
0.001
domain MNIST_ M
30
USPS
0.15
0.20
0.25
Figure 1: Robust accuracy drops (A) by varying the ε regularization inten- sity (Ji) and foo perturbation A linear classifier is adversarially trained on the MNIST and tested target domains.
Does lj regularization help adversarial transfer? Our Theorem 1 shows that the adversarial Rademacher com- plexity over HAH class is suppressed the when the fn-mrmm of the model parameters is controlled. To empirically investigate the relation, model on vectorized images x and solve the following optimization problem with & regularization: minw 1 > max ||lx_|61.._ <e ((hwww( (x; + 8), y(x:)) + pu || where μ 2 is the regularization tensity. In Figure [ we present the drops of robust accuracy from source domain to target domain RAs - RAT, regarding the intensity of l regularization. Consistent with our theoretical results, increasing ε regularization (μ 0) can reduce the transfer accuracy drops different level of adversarial attacks.
consider a linear
CONCLUSION
this paper we propose and analyze the adversarial Rademacher complexity over HAH class, which is proven to be key factor that controls the generalization of adversarially robust risk to dif- ferent domains. We theoretically explain that why adversarial domain adaptation is harder than different domain than standard domain adaptation. We also characterize the standard accuracy of a given model on any target domain, using its adversarial accuracy on the source domain, which matches with the recent observation regarding the superiority of adversarially training.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Pranjal Awasthi, Natalie Frank, and Mehryar Mohri. Adversarial learning guarantees for linear hypotheses and neural networks, In International Conference on Machine Learning, pp. 431- 441. PMLR, 2020.
Shai Ben-David, John Blitzer. Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. Advances neural information processing systems, 19, 2006.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wort- man Vaughan. A theory of learning from different domains. Machine learning, 79(1)1151-175, 2010.
Corinna Cortes, Mehryar Mohri, and Andrés Muñoz Medina, Adaptation algorithm and theory based on generalized discrepancy. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 169-178,20 2015.
Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal. Pac-learning in the presence of adversaries. Advances in Neural Information Processing Systems, 31, 2018.
Zhun Deng, Linjun Zhang, Kailas Vodrahalli, Kenji Kawaguchi, and James Y Zou. Adversarial training helps transfer learning via better representations. Advances in Neural Information Pro- cessing Systems, 34:25179-25191, 2021.
Dimitrios Diochnos, Saeed Mahloujifar, and Mohammad Mahmoody. Adversarial risk and robust- ness: General definitions and implications for the uniform distribution. Advances in Neural In- formation Processing Systems, 31, 2018.
Dimitrios I Diochnos, Saeed Mahloujifar, and Mohammad Mahmoody, Lower bounds for adversar- ially robust pac learning, arXiv preprint arXiv: (ttv::99000585 05815, 2019.
Lijie Fan, Sijia Liu, Pin- Yu Chen, Gaoyuan Zhang, and Chuang Gan. When does contrastive learning preserve adversarial robustness from pretraining to finetuning? Advances in Neural Information Processing Systems, 34:2 14:21480-21192, 2021.
Yaroslav Ganin and Victor Lempitsky. Unsupervised domain adaptation by backpropagation. In International Conference on Machine Learning, pp. 1180-1189, PMLR, June 2015.
Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, and James Worrell. On the hardness of robust classification. The Journal of Machine Learning Research, 12211-2221, 2021.
Juris Hartmanis. Computers and intractability: guide to the theory of np-completeness (michael garey and david s. johnson). Siam Review, 24(1):90, 1982.
Junyuan Hong, Haotao Wang, Zhangyang Wang, and Jiayu Zhou. Federated robustness propagation: Sharing adversarial robustness in federated learning. arXiv preprint arXiv:2106.1011 2021.
Jonathan J. Hull. A database for handwritten text recognition research. IEEE Transactions on
Pattern Analysis and Machine Intelligence, 16(5):550-554, May 1994.
Justin Khim and Po-Ling Loh. Adversarial risk bounds via function transformation. arXiv preprint arXiv: 1et..08109011 19, 2018.
Daniel Kifer, Shai Ben-David, and Johannes Gehrke. Detecting change in data streams. In VLDB, volume 4, pp. 180-191. Toronto, Canada, 2004.
Seiichi Kuroki, Nontawat Charoenphakdee, Han Bao, Junya Honda, Issei Sato, and Masashi Sugiyama. Unsupervised domain adaptation based on source-guided discrepancy, In Proceed- ings of the AAAI Conference Artificial Intelligence, volume 33, pp. 4122-4129, 2019.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-basel learning applied to document recog-
nition. Proceedings of the IEEE, 86(11) 1):2278-223332 November 1998.
Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: Isoperimetry and Processes. Springer Science & Business Media, 2013.
10

---

Under review as a conference paper at ICLR 2023
Mingsheng Long, Yue Cao, Jianmin Wang, and Michael Jordan. Learning transferable features with deep adaptation networks. In International conference on machine learning, pp. 97-105, PMLR, 2015.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant to adversarial attacks. International Conference on Learning Representations, 2018.
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. arXiv preprint arXiv:0902.3430 2009.
Pascal Massart. Some applications of concentration inequalities to statistics. In Annales de la Faculté des sciences de Toulouse: Mathématiques, volume 9, pp. 245-303, 2000.
Mehryar Mohri and Andres Muñoz Medina. New analysis and algorithm for learning with drift- ing distributions. In International Conference on Algorithmic Learning Theory, pp. 124-138. Springer, 2012.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Omar Montasser, Steve Hanneke, and Nathan Srebro. Vc classes are adversarially robustly learnable, but only improperly. In Conference on Learning Theory, pp.
PMLR, 2019.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Ng. Reading digits in natural images with unsupervised feature learning. In NIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011. 2011.
Muni Sreenivas Pydi and Varun Jog. The many faces of adversarial risk. arXiv preprint arXiv:2201.08956, 2022.
Joaquin Sainonero-Candelle Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence. Dataset shift in machine learning. Mit Press, 2008
Kuniaki Saito, Kohei Watanabe, Yoshitaka Ushiku, and Tatsuya Harada. Maximum classifier dis- crepancy for unsupervised domain adaptation. In Proceedings of the IEEE conference on com- puter vision and pattern recognition, pp. 3723-3732, 2018.
Hadi Salman, Andrew Hyas, Logan Engstrom, Ashish Kapoor, and Aleksander Madry. Do adver- sarially robust imagenet models transfer better? Advances in Neural Information Processing Systems, 33:3533-35455 2020.
Ali Shafahi, Parsa Saadatpanah, Chen Zhu, Amin Ghiasi, Christoph Studer, David Jacobs, and Tom Goldstein. Adversarially robust transfer learning. arXiv preprint arXiv:195.00823: 2019.
Joel A Tropp et al. An introduction to matrix concentration inequalities. Foundations and Trends@ in Machine Learning, 8(1-2):1-230) 2015.
Dong Yin, Ramchandran Kannan, and Peter Bartlett. Rademacher complexity for adversarially robust generalization. In International conference machine learning, pp. 7085-7094, PMLR, 2019.
Kaichao You, Mingsheng Long, Zhangjie Cao, Jianmin Wang, and Michael Jordan. Universal domain adaptation. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pp. 2720-2729, 2019.
Yuchen Zhang, Tianle Liu, Mingsheng Long, and Michael Jordan. Bridging theory and algorithm for domain adaptation. International Conference on Machine Learning, pp. 7404 -413. PMLR, 2019.
Yuchen Zhang, Mingsheng Long, Jiammin Wang, and Michael I Jordan. On localized discrepancy for domain adaptation. arXiv preprint arXiv:2008.06242. 2020.

---

Under review as a conference paper at ICLR 2023
A MORE RELATED WORK
Here, we briefly discuss some relevant prior works.
Discrepancy Based Domain Adaptation Theory A significant category of the domain adapta- tion study discrepancy based generalization analysis. [Ben-David al.] (2006) borrowed the A- discrepancy from seminal work Kifer et al. (2004), and gave the target domain generalization in terms of source domain error and this discrepancy measure. Afterwards, [Ben-David et al. (2010) proposed HAH discrepancy, which is easier to estimate from unlabeld data, and also proved VC dimenson based generalization bound. Mansour et al. (2009) also consider HAH discrepancy, while their analysis depends Rademacher complexity over HAH function class. They claim that in some situation, their learning bound is superior to Bavn--avid et al. (0100's 's bound. MMhri & Muñoz Medina (2012) proposed Y-ddiscrepancy which is labeling function dependent measure, but hence it cannot be estimated from unlabeled data. Kuroki et al. (2019) advocated source-guided discrepancy and showed that
tighter discrepancy measure than HAH discrepancy. Zhang et al. (2020) proposed localized discrepancy measure, where they argued that when defining a dis- crepancy measure, considering the whole hypothesis class may be too pessimistic, so they chose to incorporate risk level as well into the discrepancy definition.
Generalization of Adversarially Robust Learning To characterize the generalization of adver- sarially robust learning, a line of researches Khim & Loh (2018); Yin et al. (2019); Awasthi et al. (2020) are conducted via Rademacher complexity point of view. Khim & Loh (2018) is among the first to examine the adversarial Rademacher complexity under &oo attack, and as a concurrent work, Yin al.) (2019) characterized the upper and lower bound of it, and claim that adversarially robust is at lease as hard as standard ERM learning. Awasthi et al. (2020) further extended Yin eet al. (219)'ss 's results to adversary under arbitrary norm constraint, and analyze the complexity of neural network as well. Another category of generalization studies robust learning are based on PAC learning framework. Cullina et al. (2018) proved that empirical robust risk minimization is a successful robust PAC learner. |Mnntasser et al. (2019) show that, the function classes with finite VC dimension are adversarially robustly PAC learnable, with the sample complexity related to dual VC dimension, which could be exponentially larger than vanilla VC dimension. Diochnos et al. 2019) proved the lower sample complexity bound for robust PAC learning under hybrid attack. They show that sample complexity exponetially in the adversary budget is unavoidable Gourdeauu ct al. (202I) also studied the hardness of robust classification under PAC learning framework, and proved some impossibility results regarding the adversary budget. Diochnos et al. (2018) investi- gated different adversarial risk definitions, and proved negative results on the uniform distribution. Pydi & Jogl (022) also analyzed the existing adversarial risk notions, and discovered the difference and connections among them.
Robustness Transfer Robustness transfer is a newly initiated research area. Shafahi et al. (2019) discovered that by fine-tuning the network target domain, the robustness can be inherited by the new model. Hong et al. (2021) considered the federated learning scenario, where they wish to transfer robust model from computationally rich users users that cannot afford adversarial training. They proposed a batch- normalization based method to share robust among different clients. Fan al.] (202T) studied when the robust features learnt in contrastive learning can be transferred to different tasks.
B DIFFERENCE BETWEEN ROBUST LEARNING, STANDARD DOMAIN ADAPTATION AND ADVERSARIALLY ROBUST DOMAIN ADAPTATION
Here we briefly discuss the difference between the three relevant learning scenario: adversarially robust learning, standard domain adaptation and adversarially robust domain adaptation. In the goal of adversarially robust learning, we care about the gap between population robust risk and empirical robust risk, on the same domain; While in standard domain adaptation, we consider the gap between the (standard) risk the target domain and the risk the source domain. In adversarially robust domain adaptation, we care about the relation between adversarially robust risks on target and source domain, respectively.
12

---

Under review as a conference paper at ICLR 2023
C TECHNICAL NOVELTY
In this section we explain our technical novelty compared to existing works regard Adversarial Rademacher complexity Yin et al. (2019) Awasthi al. (2020). Taking classification setting for example, Yin et al. 2019): Awasthi et al. (2020) consider the Rademacher complexity over the loss class between model predictions and labels, i.c., R = Elsup A Di=1 o, minjolls (x + linear in w and 8. We consider the
8)], where the inner minimization problem loss between predictions among two models, hence the Rademacher complexity is 9 Elsup n Li=ı oj min
(x + 5)w''(xx + 5)], where the inner problem is quadratic in terms of w and ô. Hence, unlike previous works single domain Rademacher complexity, where the inner problem has simple closed form solution, we have to use E-nets and covering num- ber idea to prove upper bound. Our another key technical contribution is in the proof of lower bound results. For lower bound proofs, controlling the magnitude of Rademacher complexity with the inner problem being quadratic objective is significantly harder than linear objective. We derive the (complicated) closed form solution to inner quadratic programming, and leverage the symmetric property of Rademacher random variables avoid heavy computation.
D USEFUL LEMMAS
In this section, we present necessary lemmas that are used further in the proof of our main results.
D.1 MATRIX CONCENTRATION INEQUALITY
Theorem (Matrix Bernstein inequality, Thm 6.1.1 of Tropp al, 2015)). Let us denote by ||-I|, the spectral norm of matrix. Consider a finite sequence of n. independent, random matrices Z; with common dimension d1 X d2. Assume that
1 = and
Zell2 S L, Vi
Let Y Ex=1 Zz. Then,
E
| = E
Σ
Z
S 2 Var(YY log(d1 di + dz) + log(d, + d2)
(14)
i=
where the matrix variance is given by
Var(Y) := max
E YY
2 |E
Y Y [1
max
IE
[Z,Z,]]
Σ
E
Z
Z.
D.2 BASIC LEMMAS
Lemma 6 (Basic squared norm inequality). For any vector a,b, we have that ||a - b1l2 < 2 ||a|? +
2 1bbb-
Lemma (Hölder inequality). Letp R such that p oc. Let p* be its conjugate, that if p = 1. Let Let, E Rd, then the following inequality holds
1 < x., p² is such that
I(v, w) S |ll |w
Ifp= = 1. we set = x.
Lemma (Equivalence of p-norms). Let q > p 2 1, then all v E Rd we have l|v I llvl1 5 //p-1/9 ||v|, It also holds for q co, that is |vll & [|v1, - d/lp ||
13

---

Under review as a conference paper at ICLR 2023
Lemma (Maximum dot product over loo ball). The loo and & norms duals of each other. That
is:
xxx =||1=|
(15)
||||| s0 Sr
and this maximum is attained for x² esgn(z), where sgn denotes the element-wise sign function.
Proof. Hölder inequality implies that for all 2, x E IR?,
x S 2a æ $ || 1=111 S e e||2|1
Finally, we notice this upper bound is reached for x= = esgn(=) as
P
2 Tx = cz sgn(z) = 2,sgn(2) (2) = c c||=||
Lemma 10 (Minimum dot product over foo ball). Ler Rd, the solution of
min
TTx = -c -c||=|1
(16)
| S
is attained at x² -esgn(2).
Proof. Same reasoning as in Lemma
Lemma 11 (Lower bound of minimum "quadratic" form over foo ball). Let E Rd, the solution of (u, a:) (u, x) 2 -c² ||u||, [|v||
min Wellos
(17)
Proof. Let E Bo e) which denotes the foo centered ball of radius e O. Hölder's inequality for dual norms applied twice gives us:
(u,, 2), x) s ||~||| ||u|| ||lll S c² ||ulla [|v|]
which directly implies that
min (u, (u, x) 2 -2a [ulla ||lll I
Remark 1.
We make several comments on the above Lemma 77
Note that if u, then the objective becomes positive and a simpler and sharp lower bound it is reached for = Oa-
Else if v -22 ||ll[ which means the lower bound in is sharp.
then applying Lemma 12 implies that the minimum is reached and equals
Else if vLu, then one should be able prove that the minimum is reached at something like
x² -| which correspond to an objective equaling: (u, (v, x²) - ||
Lemma (Maximum squared dot product over loo ball). We have that
max (z Tx)2 e² || ||=||
(18)
and this maximum is atlained for (esgn(=), -esgn(=)), where sgn denotes the element-wise sign function..
Proof. Hölder inequality implies that for 2, x E RR,,
(z T= < || || < e² ||>||
Finally, we notice this upper bound is reached for x¹ tesgn(=) (=) as
(2 xz²=² (2 2g) 2 ||
14

---

Under review as a conference paper at ICLR 2023
Lemma 13. Let A be symmetric matrix, we have that
sup
Aw's
||A
SW:
LWW
Let w, w' with & 2--norm norm smaller than W. By Cauchy-Schwarre inequality we directly get Proof.
that
Cauchy Schwarz
Aw 1 (ww, Aw')l We then perform eigendecomposition on A:
S
|| [wll2 1l/ll2 - 12211
(19)
w A'Aw'= w TUEUU w' w2y "yyyTEy.
where Σ is diagonal matrix containing eigenvalues A;'s of A, U is orthogonal matrix since A symmetric, y == 1 U w and y' == 1 SU'', w'. In this orthogonal basis, let i* be the coordinate W
W
of the eigenvalue X;- with largest magnitude in absolute value. We denote by (ex)xejag the canonical basis of Rd. Let y e., and y' sgn(A. )y, we get
y Ey' |A,-
max (,(2) V (A2) = |A||
[Eld]
Thus, the upper bound 19 is attained by inverting the change of variable from y, w, w'.
Lemma 14. Let A E Raxd Then the following statements hold:
w Aww' {1.
f1
sup [w]psSW.|w//.SS
W Aw's
<
sup |w]]:SW.IW/IlSW
2/1-
else ifp >2 '
(20)
f fdl-2/p, else if p > 2
sup [wl,
w T Aw''
sup [w WWW
T A'''
(1,
(21)
Proof. We begin with proving the first inequality. If S p S 2, we know that:
BP(W) S B:W).
Hence sup WWl, /w SW w Aw' SUPp W Aw'.
If p >> 2, since -1/2-177 w |w/p, llp. we know that /w|pp S W implies /:/2-17 | S W. So
we have:
BP( = {w: || - W) S {w: d1/2-1/2 1/n |w|22 S <W) S 12-11//
Hence:
sup
w Aw'
sup WwllaSWav/2 1/x,/lw' W//2 1/s
w Aw'
|w
w Aw' 21-2/p W
sup
Now we switch to prove the second incquality. If S p S 2, then |w/2 2 /1/p-172 know
w ppp so we
B2(W) = {w: : ||w|12 < W] S {w:
d 1/2 1/2 |wllp S W) = B, 1d
Hence:
sup
w Aw'
sup |||l ///p-///
w Aw'
< 62/p-1
sup
w Aw'
|| |wl.
15

---

Under review as a conference paper at ICLR 2023
If p 2, then have
(2(W) _ (WW):
so we can conclude the relation:
sup |
w Aw''s
sup Aw'.
|wll ww
Lemma 15 (Partition). Let us define A (-1,-11 Then, there must be an equal partition of A = A+ + A such that A is obtained by multiplying -1 on each vector in At. That is, |A+ = A and A a-a,ac a A+}.
Proof. We prove by induction. When N = 1, we have Ai 1-,,,1), and we can partition it as A {1}, and A = (-13:
The we assume the hypothesis holds for N = h: that is, As == {-1,+11A can be partition as A A A such that | = AAg and A = {-a, A Now. for N k + 1, we append all vectors E A by 1, and put T, into A and append all vectors E A by -1, and put la T, -1] into Ap+1- It can be verify that, | | and Art1 a.a
D.3 QUADRATIC OBJECTIVE SUBJECT TO INFINITE NORM CONSTRAINT
Lemma 16. Let w E TP,,, E RR and 2 Let us consider the problem
8 arg max (w (wT a)²
8ER*:||011..
The solution is given by
8 =sgn(()))nn(( E R
(22)
where we overload the notation sgn denotes in the mean time a single element and a coordinate wise sign operator. i.e., san E R but sgn(w) Rº. Moreover, the maximun reached is
(w" 8 + a)² (asgn(a) (a) w" sgn(w) + a)² (c [c][w]], + |al)2
(23)
Proof. Let us give a first intuition and proof in dimension one and then extend this to larger dimen- sions.
Case p = 1 (w becomes w²) In this setting the problem intuition clear: one should select 6, with maximal amplitude, that makes 5w having the same sign If and have the same sign, then e. Else, 8 -E.
Case p E N For all w, d IR,, Hölder inequality gives that w
T 61 S |10]| ||w/]
Let 8 E IRP such that ||0]| S. Then, this implies that on the feasible set
w T 8 S <e|[w]]
(24)
Thus,
(w 8 + a)² (w" 8)-2 + 2aw 8 + a²
2 || + 2aw T 5 + a²
2 ||w]| + +2(a T 8) a²
2 ||w 2/a/e |/|| a (e ||w|| + +aa))²
Finally, one check that upper bound of the objective is attained for 5 given in 22
16

---

Under review as a conference paper at ICLR 2023
Lemma 17. Let w E IR,, E I and 2 0. Let us consider the problem
8' arg min
(w" 8 + a)²
(25)
S 6
Let := fiE [p]: w, 1
e selllll la), then solution is given by
Viel vi Ip
wi
w.
0
Else /|sse < |al, and the solution is given by
8
c
Wi
w:
ViEl 1 Vi [
6,
This solution can be condensed in the following formulation:
Wi
6:
min
IiEI
[w]]
||
[a]
(26)
6,
Wi W
The minimal value is given by:
min (w 8 + a)² a² =0 8
{1
< [/|w/l [a|
})
(w
Se
Remark 2. Note that general there are an infinite number of solutions to 25 in (26 one can
choose arbitrarily the value of 8 for all E [p|\] (as soon as it is kept smaller than in absolute value).
Proof. Let ip] = (I...., p). Let us try to build solution which drives the dot product w towards - a. Let = {i E [p] w, + 0}.
Case 1: Ife || |a|. uet 5t E R such that
Vi E
Tw will
8
Vi E [p]
This vector is in the feasible set as 1|0" max
|a|
[w:
|a|
S e, as assumed. Then,
[[
[w]]
[w
w?
w +
+a=0
w
Wa
SET
This means that if the entries of vector w are large enough (in absolute value), we can build a feasible vector 8" such that the objective in (25) zero.
Case 2: If'e /|wl]1 <
lal. Let us 8 E R2 such that
8
ViEi I
w.
6:
Vi E lp
This vector is in the feasible set as ||8
11 = maxiea
a w.
= assumed. Then,
w:
w
1 e [ |||
8" +a=
+a a
w;
la
IE1
E|0.1]
17

---

Under review as a conference paper at ICLR 2023
This means that if the entries of vector are too small (in absolute value), can only build feasible vector such that w 8 close too -a. And the corresponding objective in (25 becomes
a² (1
[
Finally, one just can show with Hölder inequality that (w"8 8 + a)² 2 a² - c [iwll for all 5 in the feasible set, which concludes the proof. 2 the computation follows easily, else we can just replace ó + - to get back to the former case.
18

---

Under review as a conference paper at ICLR 2023
E PROOF OF GENERALIZATION LEMMA ( (LEMMA 2)
In this section we provide the proof of Lemma 2 First let us introduce the following helper lemma.
Lemma 18. Assume S and T are the sets of data drawn from S and T, with size ns and nt respectively, and the value of E(.) is bounded by M. Then we have:
edv discHAn(S T) disc odv (S, T,,TT1- S Ri((E o HAH) + R HAHH)
1og(2/c)
log(2/c)
3M
+3M1
ns
12T
Proof. Since absolute value satisfies triangle inequality, we have:
disc (S, T)
discha (S,S) $) + disc
HAH (T, (T, + discHA HAH (5, 7)
According to Rademacher- generalization bound Mohri et al. (2018). we know that
log(2/c)
disc (S,
max (Rgd (h, - Rh, h,) Rg(( HAH) + 3M N,
115
and for discHAH (T, T).
Proof of Lemma
Proof. Since the loss function satisfies triangle inequality, we can split Re (w, v7) into the following terms:
Rado tabel (hw yT) S Rydu (hw: lews) + Radu (hw3. :lw;)) Rqdu (hwe yT)
s Rg (hw: lww)) ) + discHAH (T,S) + R7jh (1wg g: lww)) + Ry (hwz, BT)
S Rodo (Iw: lowz) + discHAH (T, (F, + Radu (lww3, lww)) ) Radu (Iw7, UT)
log(2/c)
log(2/c)
+ Rs(E HAH) Ri HAH) + 3M ns
+MM
n&T
$ Rg Rado- label (hw; Us) +
Rg Radv label (Iw Us)
Us)
+ disc (T, 8) Rof (lw lww)) ) Rodo (lww3 MT)
log(2/c)
log(2/c)
+ Rs(E HAH) Ry (e (6o HAH) 3M
3-M
ns.
nt
where we plug in Lemma 18 at last step.
F EXTENSIONS
F.1 ESTIMATION OF ADVERSARIAL DISCREPANCY FROM STANDARD DISCREPANCY
The following Lemma gives the bound we estimate adversarial HAH discrepancy from standard HAH discrepancy.
Lemma 19. The following relations between adversarial discrepancy from standard discrepancy holds for linear model class with bounded norm: H. {hw (w, x), [wwlpp W). For Los Lipschitz binary classification loss, we have:
discady edv ($, ( discHAn(S,T
discHax
1
15p52 1d112/1p p>2
[1
+ 22 Vde
Σ
|x
Σ
/xoll2/
11
x,ET
x, ES
19

---

Under review as a conference paper at ICLR 2023
For lg regression loss, have:
disc (8, T) < discHan($,7) 7)
+ &vdeW2
1
Σ
|xs|12
+
Σ
lxxil2
f1 1sp52 dd--2/p
n1t
p>? 2
x,ET
X,ES
Proof. Let B,()) == (w E Rd ||wlp S W be the norrm centered ball with radius W. By the
definition of disc (S, T), we have:
HASCHAH (S, T)
max w.w Ef ww: 1Rq (w, w') -Rg (w, w')l
RR - Rg(w, w') + R.gh (w, w') R27 (w, w')
max (W)
- -RR (w,w)- -Rs(w, w'))
discHan($, +
|Rq (w, w') R w')l
max w,w'EB,
max w.w'EB, (W)2 IRgle (w,w')= - (s((, w')
Now
we study the
gap max W'B, (R (w, w')
Rr((w, w')l and
max w EB, (Rode( (w, w')- R R (w,, w')l For linear classification, we have:
(Rqq (w, w') R+(,, w')l
W.w'EB,
max W.W'
max (ø((w, x; +) - x; 8)) (((w, xx) (w', xx))) 5:11811~<Se
TTT
x,ET
1
max
x; (w', x; + 8)) ((w, xx) (w', xx)i
W. (W)
nT
X,ET
Σ
max Lolw ((x, + 0)( + +0) -xxx,) w'
max
w, W.,'EB,
TIT
5:11811=S5
X,ET
Lo
Σ
max
[w T ((x4 + 5x) + +8²)T - -xxx]) w'l
nT
W.
XEeX
Cauchy Schwarz
Lg TI
Σ
max (W)
||w]lel((x; + (xx + +8;)T -x,x, w//l2
X,E
< La nT
max w.w'EB,(Wy
12 + x,,, |2al/''l2
w.w
X,ET
where 8 is maximizer of the i-th optimization problem in ö over the exx- -all of radius We know
S p S 2
that ||wl|2 S W.
1/2-1/2 p> and x x, lla s 2v 12. so we have:
1
[1
15p52
Rede (w, w') Ry w')
2 La
Σ
2vdel|x:l12
max (W
( p>
nT
x.ET
20

---

Under review as a conference paper at ICLR 2023
which concludes the proof for linear classification setting. Now we switch to regression setting:
|Rg (w, w') - R,((W, w')l
max w.w' W. (BV)
Σ
max 1(w, X; + -(w, x; + +5)12 - -l(w, xx) - (w', xx,
max W,W'EB, (W)2
6:11811 Se
x,ET
max W,W'EB((W'
Σ
max 1( w'w x; + +0)113 - 11( w', x
6:118|| Se
X
Σ (w- w [(x, + -,)( + t,] xxx,] ] (w - w) x,ET
max EW'
(w w')
Σ
[ + xx,; (w ww)
max w.w' (W)2
Tt
X,ET
Now, we let : W- w and re-write the above inequality as:
Ryg (w, w') - R (w, w')l
(W))
Cauchy- Schwarz
1 Σ
x + +x,0,1
l|vl2
1&T
X,ET
4W {1
ps 2 p >> 2
x + x;,
d222//1
IVT
x
5 2 dl- > 2
< &V
|xill
x
where we use norm equivalence (Lemma
g
to bound ||v|22-
F.2 ADVERSARIALLY ROBUST DOMAIN ADAPTATION GENERALIZATION BOUND
In this section, we will present the generalizatin bound of adversarially robust domain adaptation, using our upper bound for adversarial Rademacher complexity over HAH class, An immediate implication of Theorem iis the following bound:
Corollary (Adversarially Robust Domain Adapation Learning Bound, Linear Classification). As- sume that the loss function is symmetric and obeys the triangle inequality. We further assume i is bounded by M. Then, for any hypothesis how E H. the following holds:
Rod Radv-label (Iw UT) S R Redu-tabel (lw US) + Radoo-abell (Iw's: US)
+ disc odv
(T,)) Rydu (lww lww)) + Ryge (lww .VT)
log(2/c)
log(2/e)
+ Ris(E o HAH) (E HAH) + 3M
ns
n2T
+ + Loed Wo //' +2||XT
/v + ||
VnT
Vns
where p is such that 1/p + 1/p" 1, and X and XT are the data matrix concatenated by data points from S and T. respectively.
Proof. Combining Lemma 2 and Theorem 1 will conclude the proof.
21

---

Under review as a conference paper at ICLR 2023
An immediate implication of Theorem 2 is the following result.
Corollary 2 (Adversarially Robust Domain Adapation Learning Bound, Linear Regression). As- sume that the loss function i is symmetric and convex. Also let S and I have ns and net data points, respectively. We further assume i is bounded by M. Then, for any hypothesis hw E H. the following holds with probability at least c:
Ry Rade-label (hws BT) S 6RS soaau--abelea (tw: ys) + 6R5
GRRad--aaa (hw3, vS)
+ HAH (F, 3R (hw; Awg)) + +3R (hw3.V1e
log(2/c)
log(2/c)
+ MO
+3Ms(lo HAHH) + (1 HAH)
ns
nT
W2
(de [X512,22
+ 2)
W
11, 15p52 x 11--//p, ( p>
de [ + d2
+
+ VnT
Vnss
where Xs and X are the data matrix concatenated by data points from á and i, respectively.
Proof. The following proof is almost identical to that of Lemma 2 and the only change is that we
apply Jensen's 's inequality instead of triangle inequality here:
(hw: VT) vT) z 3R (hw: lww:) ) 3R (Iw /ww + 3R (Iw,
s 3R (hw: lowg) ) 3disc HAH (T, + 3Rq (Nwwz llw ) 3R9 (Iw7 (!T
odv
- 3R3 (lw, lww)) 3disc adv
(T, T8) + 3R (liw Mww + +3R74 (lwwy 1/T))
log(2/c)
log(2/c)
+ 3R (E HAH) + 3RT (E HHDH) +3 3M
+ 3M
n1.
11
< G (ltw, yss) 6 label (ww3.
+ 3disc (T, 3R (hw3, hwg)) + 3R (tw,,: BT)
log (2/c)
log(2/c)
+ s HAH) + 35 (AHH) +3 3M V
+ 3M
TTT
where we plug in Lemma 18 at last step. Finally plugging in Theorem
will conclude the proof.
0
G PROOFS FOR BINARY CLASSIFICATION
G.1 PROOF OF LEMMA 3
Proof. To simplify notations, we omit to specify the fact that the model parameters w and w' belong to Rd. We first prove the upper bound results. By definition, we have
1 oww x, x x;
Rp(f HAH) = E,
||w
SW
1=1
11 2122/p,
if 2
E
sup
T
xxxiX
w'
[w|l2
[w
SW
else if
i=1
Lemma
W
E,
x
{1.
222-
if 5 else if p >
(27)
We now look for more explicit upper bound of the above Rademacher complexity depending the dimension d and on norm covariance of data points X,...., X,, To do so, we introduce some notations before applying matrix Bernstein inequality (Theorem 6.1.1 Tropp et al. (2055)
22

---

Under review as a conference paper at ICLR 2023
recalled in Theorem 4 Let Z, o E Raxd for all [n]. These random matrices
symmetric, independent, have zero mean and are such that for all E [n]. Moreover, let Y Σ Z. For each Zi, notice that it has bounded spectral norm:
|
Amax (Z
Amax (x,x/ x = ||x:112 max jE(n
1 = |X| 2,00
so that according to matrix Bernstein inequality, we get the desired bound
W
1 |
Rf HAH
2 Σ
[xxx]) )2
log(2d)
| 2, log(2d)
i=1
f d/2
1,
else if > 2
G.2 PROOF OF THE UPPER BOUND OF THEOREM 1
Alike the analysis of Theorem 7 from Awasthi et (2020). the below study uses the notion of coverings. For completeness sake, we recall its definition.
Definition 6 (p-covering). Let p > O and les (V, be a normed space. A set C C is an e-covering of for any v E V, there exists o' such that [|0- - r' S p.
We also copy Lemma 6 from Awasthi et al. (2020) dealing with the size of coverings of balls.
Lemma 20. Let > O. Let B C. R.d be the ball of radius R 2 0 in a norm ||-I] and let C be one of the smallest p-covering of B w.r. II-I], Then,
3R
| S
p
Now ready to present the proof of upper bound of the adversarial Rademacher complexity for linear binary classification.
Proof of the upper bound of Theorem 7 this proof, we consider the linear hypothesis class were the norm of the models is controlled by a general -y-norm for 0. Let (,) : {w E Rd [[w]] 1p I W). the hypothesis class defined in (5) then writes
H = {ho x (w, x) w B,(W)}
Similarly, let (x) := {8 E R2 |001 Sc).
Recall that we define in 8
As(F o HAH) = E,
sup w.w' (W)) TI i=1
min
wT + 10 (xi + +8)
(E)
Eg sup
(x} ww
X4 +
min SEB (e)
8T TTwTT& 8 x3 (ww'T + w'w T)8)
w. (W))
< Ri o HAH) + E,
sup w. w.W'EB,
o min 6EBro(e)
(8T ww T 5 (ww'T + w'w 10)
Now we examine the upper bound of the second term A using the notion of covering recalled in Def- Let be a p-covering of the lp ball (W) w.r.t. the Ey norm, with > 0. Let us define inition 6
(h, w') == min 5 Tww x3 (ww'T + w'w (e
(28)
23

---

Under review as a conference paper at ICLR 2023
Thus rewrite A as
1 Σ i=1
A = Eg
sup W,W'
o. w. w')
E
sup w.w'e (W))
(1i(WW, Wey w/) + ww w') sle w'l)
W.,, We.W ||w-wel /ollw' ww'l,
where We, respectively w is the closest element to w, resp. w', in C. Using the subadditivity of the supremum, we get
A E,
sup ECC
OeVi W. W
+ EEg
sup (W,)
Σ os (vl(w, w') (We, w')) 1=1
1
1
Eg
sup
0.%% W
sup (W)) n
(w, (Wer w'Jl
E.W n
1
Eg
sup WCR
T. (w, W
max SEIn] w.w W. (W)
sup
(w, w')
(WW w')l (1T)
(29)
n
where we recall that Wes resp. w is the closest vector to w, resp. w', in C.
Bounding (I): We first need to bound the left-hand side term (I). We introduce the vector
/ (WW, w == [V1 w'..... 2/n (w, w)]] e R
By Massart's 's lemma (Lemma 5.2 of Massart 2000 ) we able control the first term (I) in
o, o w)
K /2 22 (og(()
(4) Eg
sup w.w Eec n
I
(30)
with K given by the largest l-- norm of r/ over the covering C?, that is
x²
max WW'
11
max wW EC2
Σ
(31)
Now we examine the upper and lower bound of (w, w'). For upper bound, by taking 0 we know that (W, w') is non-positive. Thus, we only have to control how negative this term can be. Let w, w C22 we have
1i (W, w')
min SEB (e)
8 @TwT 8 x, (WW/T + w )
min (e
8 Ww
min (E)
x, (ww/ T + #ww )
Lemma 10
min (E
5 ww T - c||[WWTT + Www x
(32)
We focus on the first term which a quadratic optimization problem under infinite norm constraints. For all d, w' E (e) x (W) this quadratic form can be lower bounded by calling Hölder's inequality twice and norm equivalence, that is if p* we have llvllp d/" ||
ww 8 22- -18" ww/T.
Lemma
111122- ||
11, W II,
Lemma
-2/v" ||0113 |W||, p ||wl|p if > 1 else p
110112 [w|,
BCB w.w w.w (W)2
B/r" 2w2 if
?2 else if
24

---

Under review as a conference paper at ICLR 2023
Using the same tools, now study the second term
ww Xi =
=-(W',
x:) [|]]]
Lemma
Z
|x3 || |
Lemma 8
//2 ||x:| p- [[
[[ll
if > else if
||x:ll [w/] || l1
w.w (B))
dd/p" w² |
if > else if 1
w ||< llo
and symmetrically we get the same bound for - || x l|
By taking the convention that d'/r" 1 if p = 1 (i.e. p = oo), we drop the disjunction between = and p > 1 in what follows.
Combining (32) and the above inequalities, the auxiliary function the (8 can be lower bounded after applying the triangle inequality:
2/ (W W. w/) 2 -2 ew2 -2dd
/p" W2 |xxIIpp-
So that we get
(/ w/2 s (d2/e" 2 2ed"/1 W2 ||x; l1,
s &ddi (ea
+ max ||x; 1n-
jE
=ddi (ed
+ |
p" ,00
Finally we get the following upper bound for K defined in 31
S /ncd"/p" (ed + | p- pc)
which, jointly with the application of Lemma 20 immpliss the upper bound for (I):
K K 2og IC
/d W (edtt//" + lo)
(4dlog(3W/p)
(33)
Vn
Bounding (IT). Now we turn to bounding the second term of 29 Let w, w' E (W) and let Wa. resp. w/e be the closest element to w, resp. w', in C. Let us define an "implicit" minimizer w.r.t. (the objective being continuous over a closed ball it attained) for vh w():
8% arg min o% Wow'' de x (wow. + w.w. Jo..
(34)
6-
Thus, have
di (w, w') (We, w¹))
min (c)
8 ww 8 + x3 (WW'T www 18-18")))) w.w' 5, -x. (wow" + w.w..)..
<())) Ww 5: + x,] (Ww'T + +w'w T 15:- - -68) T W. 6% -w](WwW. + w... )o0 T
-60) (wW'T www. (00 +x, (WW"T w.w. + w'wT w.w.
-T (w(w'- - -w')T -(w. -w
x (w(w'- -W:) -(w, w)w? + w'(w wo) (w' w'w 5%
We focus on upper bounding a single term the ones appearing above. By applying Hölder's inequality twice and norm equivalence we get:
(5)) w(w' wT)To² 5%
Lemma i
wwlp |5 p- ||w' - w'llp pe 2 W
Lemma K
25

---

Under review as a conference paper at ICLR 2023
where in the last line used that ||w - wellp S p. by the definition of the p-covering of the ball (W) w.r.t the ey-norm. Proceeding identically with other terms involving x; get
Lemma
Lemana
| w(w'= o
xx.lp- |w/lp l| wellp 1102
ped /p W ||x
finally get that
W W, w') 4/ (We. w') S 2pc W + 4pcd W |xx:lpp-
Similarly can prove the same bound holds for other side of the difference (by using "implicit" minimizer of tha (w w'). Thus we are able to control (If):
[o( w') (we, w'll S 2ped ((ed/ve +2||X|1pr, (35)
max =E|n] w.w.BB, (W)
sup
And finally, we proved that
+ oo) (p+ V V w MwW/oog3/// Mogg(w//))
A
/r
Wedd/v'
which concludes the first part of the proof if we choose p= p==-e WW/vn:
d/v
A < 25
22
[1+Vavlog(3))
(ed'/' + 2 X pl
Vn
G.3 PROOF OF THE LOWER BOUND OF THEOREM 1
In this subsection we present the proof of lower bound of the adversarial Rademacher complexity for binary classification under linear hypothesis.
Now we are going to prove the lower bound result of ad- versarial Rademacher complexity. Recall the definition of non-adversarial Rademacher complexity
Proof of the lower bound of Theorem 7
RD(s o HAH)
E sup
O&W X;X; W
||w W.
SW
1=1
1
sup
w
OxXiX
W
71
|| wwlps/..lww'lpp....
1
ifl
E
|| W//l////lwla
sup
0xX,X
w'
x
2112/p
else if p 2
==1
Lemma
W22 E
1
if s
x
x
2/p
else if >>p
due to equivalence
norms.
Now,
we denote v such that According to Lemma 13 the maximum
arg max/ SW. Dizi o,w x;X, w'.
value of Σn o,w! x,X, w' is:
n
W Σ xxX,X
[w/ [ o.w X w'
sup
2
and if we define S(o) EL x the maxima is attained when v Wv VVmax(S(() (S(or)) is an eigenvector of fo-nrrm W associated the largest eigenvalue of S(
26

---

Under review as a conference paper at ICLR 2023
Now, switch to adversarial Rademacher:
RD HAH)
E
sup [wil, w Sl
di min w (xxx 0)(x; 6) w
[ Se
d d'-2iv,
i 2 else if p>p
E
sup
0 min w (x:
wx(x; + 0) + +5) w/
WW 71
8 Sr
1
fdt-2/v
if 1 S p 5 else if > 2
sup
min
(x: + 6)(x; + +)
|6 x Se
1
where in the first inequality used that, if 1 p S then (w) C B (d and else when p > 2, we simply have that (2 C (W). According to Lemma 17
we have:
RD(f HAH) 2 EE
w x; w x, min {
el </|wll 1
w x; 1)
sup Sw
oi t=1
Ti
Case I: 1 111sp22
First, to avoid confusion in different Rademacher variables, let us use o' and or to denote the Rademacher variables in RD(f HAH) and RD(f HAH). Then, let us define v W Vmxx (S(o')3) (m 2)) Then we consider the gap:
RD HAH) Af o HAH)
TT,, min {1,
el [/w]l 27
w x; ))
= =Egr
sup
of
w x; -w--
Tt S2w 1=1
1 Σ oow x;xx w
Eg
sup
||w]|25 WWWW [//wwll: 1125W
x; via X2 min (1, <llv"'112
} 1) Eg Σ o.v Dov x V2
2 E.g
/v xi
n1
i=1
W2
< Vmnxx (S(o') 2201)
E
o
- Vm(v (S(o')2) xx)² (.)2min min
n
Vmax (S(a)) (2) xx
W
<l|V Vimax (S(o 2)
0
(Vmax (S(o')3) xx,)) 2
min
1,
Vmnx (S(T x;
1=1
Let us define
12
<l ( (S(o')2)11 Vmax ((()))2 xx|
1(0') Σ oi
-2( (S(a))) x2) min 1,
and
J(o') Σ of (Vinx (S(a))((( xx,² min
el| el/V (S(o)))))11
Vmax (S( 1
so that
Rp (f HAH) RD HAH) 2 W (E, [[(o']] E, (J(a'))
n
We now going to prove that T(o) + T(-a) 0 and J( + J a) 0.
27

---

Under review as a conference paper at ICLR 2023
First we know that Vmax (S(o)))) Vmax (S(=))))))) since S(-o)= -0)==(->>) (--Ei xxx,,, )= S(o)² So
</ Vmux (S(
VTTux (S((o) )x, 1)
T(o)+ + +1-o) = Σ
o
- 2( (V (S(o'))) x;)² min
i=1
{1, cl|Vmax ( ( Vmax (S()))2) x. })
+
-0
( (S(o')3)Txx) min
im1
0.
Similarly ((o + )(-))= =
According Lemma 15 can split (-1,+1}" into A+ and AT, such that |A+|
|A- and
A = - where is element-wised negative sign. So we know:
E. = Σ
(())+ +
Σ oEA
1 ((o)= = Σ 2
(0)
+ Σ
1(-o)=
2n
2n
2n
oeAt
oedt
oEAt
[o]]( = Σ
+ Σ
[aa== = Σ
1
[ +
Σ
1
J(-o) =0
J
2
2"
2"
2n
GEA
oEA
GEA1
gEA1
Hence we conclude that Rplf HAH) 2 RD(f HAH). Case Il: p > 2.
Similarly we have that
RD (f HAH) RD HAH)
1 Σ
w x; w x, min { 1. w xi }
E /w/l1 27
EEg'
sup
o
||W
T1 1=1
d' d'22/EE.
o,w xix]
T w'
sup
||wla W.W../llwl 11 WwllssW.lwwllsss
1
T/ x; TnT min { / x;| )
cllv/'// )
Eg'
o
m
i=1
d
2/PPE
O,V" X.X:Tv 4
W2 (1
d /1-2/p)Eo
Σ xxx,
n
W
n
el| vlxx (S(o >>)
Eng
0
2( mux (S(a')2)T 2(( x;)² min
n
Vmax (S ((()))2) x;
W/2
mix (S(o')2)) x² min {
I max (S(o )1 )
2
Eng
Vmnx (S(a')2) x;
n
W22
n (1
d!
d//2/D
Σ x;xix
where in the last step we also use the same reasoning as in Case I.
28

---

Under review as a conference paper at ICLR 2023
H PROOFS FOR LINEAR REGRESSION
H.1 PROOF OF LEMMA 4
In this subsection we are going to present the proof of upper bound of the Rademacher complexity for regression under linear hypothesis.
Proof. We first aim controlling the non-adversarial Rademacher complexity over the HAH class. We specify its definition given in T for the linear regression setting below
1
n
Ro(E HAH) E w. w. w.w.:,lllI,s...... w/l
sup
os (w(w"' x; w x,2²
S 72
2=1
We introduce the variable change w w', which yields
Rp o HAH) = E,
L o T x,)²
(36)
vvllvll, S2W
We first derive the upper bound of Rs(E HAH). We follow similar steps than in Appendix G.1 we rewrite the supremum as a spectral norm and then apply a matrix Bernstein inequality. We have that
1 Σ
RD HAH) Eg
sup [v:llvl S2W ni i=1
x,)²
Eg
sup
,,X,X
[vlllvl n SW
n1
Eg
sup
T
n
xxXIX
2/22/1
if 5 else pfpp. 2
v:llvllaS22
n
2
1,
if < p 555 else if p >
E.
xxXX
1112//2
n
Following exactly the same steps as in Appendix G.] we apply the matrix Bernstein inequality. Let us denote by Z; == x;x;x Rdd the random matrices we want to apply Theorem 4 to. Then, Z? of (x ) (x,x] ) is a deterministic matrix. These random matrices Z, are symmetric, independent, have zero mean and are such that for all i E [n]]
1Z:l22 V Ammax (23)
Amaax (x,x, x
||x:1|2 < max
|
|
X
2,00
jE(n
Moreover, let Y = Σm= Z. According to matrix Bernstein inequality, we get the desired bound
Re o HAHH)
4
Σ
n
(xxTT) )2
log(2d) + |x|2 log(2d) x
fa-22
PS2 2/12 p> 2
71
H.2 PROOF OF THE UPPER BOUND OF THEOREM 2
In this subsection we will present the proof of upper bound of the adversarial Rademacher complex- ity for regression under linear hypothesis.
29

---

Under review as a conference paper at ICLR 2023
Proof. We then examine the adversarial Rademacher complexity of linear regression models defined in
as
Rg HAH) E.
sup w:|lw 1|, w :|lw' 1 W
o.
max (w" (x) + + w + 0))² 8:1681
(37)
We start by expressing Ny (LHAH)) a function of Rt (A)HAH)) its non-adversarial counterpart studied in Lemma
Let
w'. We expend this quantity follows
(e HAH)
Eg
sup v:llvll S2W π
oi
max (V- + 8)
5:1681 Se
Er,
sup
ai max (v x;)² + 2v x, v + +v)
v n
8: &l Se
< Rs o HAH) + +E
sup
0j max
2v x,=" v + (v
v:llv p S2W
6: | St
= Rts HAH) + EE
sup (vllv] , 22
di max
vT +06 )v
8: 8:
(38)
where we used the subadditivity of the supremum in to make appear the non-adversarial Rademacher complexity over HAH class.
Now we examine the upper bound of the second term A using the notion of covering recalled in Def- inition Let be a covering of the centered Cp ball of radius 2W, that we denote by (2W), with lp balls of radius p > O. Let us define
(i(v) = max v v=(2x, + +68 jv
(39)
5:1 8:16111x Se
Thus we can rewrite as
1
Σ divi(v)
Eg
sup
VEB, (2W)
1=1
Ex
sup (2W,(2W)
Σ i=1
σi ( - G((v))
v.EC: vell
< Egg
sup VEC n1
n (i)i(v)
+ +E,
sup
1
Σ o, - -
v (2W) n
i=1
i=1
n
< Egg
sup VEC n (v)
sup (2W)
Σ
- -
(40)
(IT)
where V. is the closest element to v in C and where we used the subadditivity of the supremum.
Bounding (I): We first need to bound the left-hand side term (I). We introduce the vector
<(V)= = (V), Sn [ E R
By Massart's lemma (Lemma 5.2 of Massart 2000 we able control the first term (T) in 29
< K 2og C
(I) = E, sup Σ vec
(41)
i=1
30

---

Under review as a conference paper at ICLR 2023
with K given by the largest fy-norm of over the covering C, that is
k²a
max
||c1
max VEC
(a(i)
max vEB,(2W)
Σ G(v)?
(42)
VEC
Now we examine the upper bound of K. Note that (i(v) 2 0, then we can upper bound as follows
<ı(v)= =
max
v2 T + +88 )
5: Se
max |
12,0 + +08 1/2
8:11811
|
max
[2,0
+ max
88 (1a)
6:16 St
6: Se
||vl
max 5:168 Se
|8112
1|1x1122
max Se
1|01|/
Mi de (vde + 2 2|x111))
(43)
where we applied Cauchy-Schwand inequality and the definition of operator norm and then the sub- additivity of the maximum. Recalling the case disjunction
||vl|2 S ||v||
if S p S else if p > 2 .
(44)
[ivll, S dllpp/1/-1///
we are able to upper bound K2, by using (42) and 43 which leads to
K²
max (2W)
2(v)
|1 (Vdc)² Σ6
Vde [dd++2|xx1l2)
max (28)
|l (1 d
(Vde+ 2 11x)l12) Σ
(1,
if fispp2
max v2B,(2W)
clse if > 2
1=1
= (4W3) Σ
(vdc+2||xill))
{1, +1
i (1
(2/2-2/033
else if > 2
Then, by taking the square root in the above we get
K < 3
Σ (Vde + 2(1xx1)))))
f1,
if 5 else if >
221-//1,
Jointly with the application of Lemma 20 we can conclude that
2 (1) <
dd
Σ
(Vde + + 211xx112) 22dlgg(6W/p)
{1. {2
(di-2/9,
else if > 2 (45)
if 5
n
Bounding (II).
Now we turn to bounding the second term of (40)
(IT) == sup (28,(2W)
(c((v) - G(vv))
recalling that (v) == max S. corresponding closest point in the covering Ve E C. Let us define
(2x,5T + 58 T jv. Let i E [n]. E B,()W) and its
{
8" arg max | 1. Se v (2x,0 88 vv
8 := arg max
|1. Se v. (2x,0T + 56 \v..
31

---

Under review as a conference paper at ICLR 2023
Also, let M == 2x,6" + + Then, we make the difference explicit and upper bound it
- -
v (2x,0" + 6 jv v. 62x,6" 55,5 Vee.
S Sv T2x,2x00 + + jv vo (2x,0" 00000 Lve.
= M'v V..'v
vov M' v. M' vo)
Cauchy-Schwarz
-
1lv (llvl12 + (|vell2))
S 4pp vde (Vde + 2 211x1ll)) x (ai-2/1,
[1. f else if p
where lastly used the same arguments leading to (3) the norm transfer in 44) and the inequality Il-ll2 I vd I1-ll Symmetrically, we can show that the above upper bound holds for Çi(v.) - (i(v). Thus, (II) is upper bounded by
(IT) < 4pWVVde Vde
2 1
Σ
|xalla]
[1. 111-2/0,
if else if p
(46)
Let us choose p W/n. We have then proved that
(T) + (IT)
1 2dde
Vde + 211xxl12) /2dlog(6W/p) + 40W (vde
2 Σ
1xill2
i=1
11
if PS else if 2
d1-2/2,
d
W
2 n
4 vdc Vicc+
>
1xx1l12 +
(vde+2 Vdee + 2 21xxsll)) v 2d log(6n)
i=
1, 2/1,
if 5 else if >
By combining (38. 44 and the above bound, able finish the proof for the upper bound of the adversarial Rademacher complexity over class HAH for linear regression. Finally, this gives
As(L o HAH) S Rl HAH)
W2 + 4
Vile
Vile +
2 Σ
|xxll2 +
Vdde + 2 1x1111)) / 2d log(6n)
i=1
iml
1,
if 2 else if >
2/2-
H.3 PROOF OF THE LOWER BOUND OF THEOREM 2
In this subsection we present the proof of lower bound of the adversarial Rademacher complexity for regression under linear hypothesis.
32

---

Under review as a conference paper at ICLR 2023
Proof. Recall the definition of non-adversarial Rademacher complexity
1
Ro(E o HAH)
E
sup S2W
0:(vv x;)²
1=1
Lemma
[1, 11-2/p
if s
E
sup I
02 x;)²
else if p > 2
==1
due to
equivalence
norms.
Now, we denote V such that One can verify that the maximum value of
1 Di= (, (v)2),,)
arg M/xx|//ll22
E o x.) is:
n Σ
n V
4W2
sup
o,(v x2)
sup
Σ
xXXX
Σ oxxXX
22 7i
n S2
n
2
and if we define S(o) = nh
iml , the maxima is attained when v 2W V (S(or)²)
Now, we switch to adversarial Rademacher:
Ro - HAH) = E
oi max (v (v (x, + 6))²
sup
S2W
S2W T
|8
im
Lemma
4
f fd
2
sup
max (v (x; (x+ + 5))3
S2W n2
18 St
11
else if p 2
According to Lemma 16
we have:
RDll HAM)) =
1
Σ 1=1
{ [d
if 5 else if p
sup
11,
|Ivllag2W
Case I: 2
First, to avoid confusion in different Rademacher variables, let use o' and to denote the Rademacher variables in Rp o HAH) and Rp HAH). Then, let us define v 2W ViVVaaxx(("")) (S(a')²)
Ax HAH) RD(l HAH)
n d(dl|vll +
n o, xx,
E.
sup S2v n
xx,12
x,122
sup [vlla52w
n
1=1
n
n
Eg
[ell/v'*ll +x
Er
ov(v" x;)²
n1
71
i=1
4W2
n
Eg
o [2cl Vmax (Sll (S(o') + 2 Vmaa (S (S(0')))113
max (2(r)²)xx xx, + || (l()) and we claim Let [(o) = Σ ai (2ell max (S Iv
that ((o) + (J ((-o) = O. Now we are going to prove this claim. First we know that Vmax (S())) = Vmux (S(-o)2). )) since S(-o)² Σn x S So
J(0r + 1(-o) = Σ
σ. Vmaa (2l ( + e ( (113)
i=1
σi [2ex/Vmax V (S( e22 e/ mmx (3(
0.
33

---

Under review as a conference paper at ICLR 2023
According to Lemma
15
split (-1, +11" into A and AT, such that |AA*|
|A-
and
A -A where is element-wwee -wised negative sign. So we know:
[ - Σ ((o)+
Σ mEA-
1 ((o)= - Σ
1 J(o)+ 2
Σ
(--o)
-
2
aEA+
DeAt
oEA+
Hence we conclude that Ro(L HAH) 2 RD(lo HAH).
Case II: p >
Similarly we have:
Rp(e HAHL) (e o HAHL
Eg
sup
dell|v/l + 1 xx11)
-d' d'-2/1EB
sup Σ oilv T xz)²
S2W
||v|.52W T
2 Eg'
d<[e|lv*|| 1| + ++1*'xx11]]
d 22-2/PEE Σ o1(v"* T x2)²
4V2
n
= (1 dl 22-2/p)
E
Σ xiXiX
4W2
Egr
2
of (Ell Vax
+ + (()))))))
(S(o
i=1
4W2
2 (1 d 2/p)
E
x,X,X
where in the last step also use the same reasoning as in Case I.
I PROOF OF NEURAL NETWORK COMPLEXITY BOUNDS
In this section, we will present the proof of upper bound of the adversarial Rademacher complexity under two-layer neural network hypothesis (Theorem 3).
We provide the proof of classification
bound Appendix [.] and regression in Appendix I.2
1.1 PROOF OF BINARY CLASSIFICATION SETTING
Proof of the classification bound of Theorem We recall that ( stands for the é, ball of radius R (either in vector Rd or matrix Raxdd space). To simplify notations, we denote the coordinate-wiss ReLU activation function by
g(x) = max x), Rd + Rdd
where max is applied coordinate-wiset Using the definition of the fo HAH class in 7 we upper bound the adversarial Rademacher complexity in the binary classification setting by expressing it as its non-adversarial counterpart plus an additional term. Thus we get
AD HAH) = E,
min a [T((W(x; + 8))a" g( (xW + +)) 1=1 @
sup a.'' (W)
As the function 8 + g (X, + 6))a WW + 8)) is continuous composition of continuous function (linear and ReLU), then it reaches a minimum of the compact for ball ra- dius > O. also denoted by (c). Let o argument of the minima of the latter function,
34

---

Under review as a conference paper at ICLR 2023
i.e. 6 arg mer a g(W(x 8))a² (xW"(x; + 8)). With this notation, write
Ro(f HAH) s RDls HAH)
1
+ Eg
sup a. L.,' W. (W))
0,a (W + 6.))(W +,)))aa' ( a'
n
(D HAH)
+ E.
sup E, (A) W. (W)
oi (o(W(x; + 6W)) +8)) o( (W'x))((''<))))) a
7
Let the term inside the expectation being maximized (as a continuous function over compact set) at a", a" W W And let
S. = oi [W(W"(x + 61)) (W")) (x; + 87)) ((W''x,)) ("'x:)(W"''xx x:) 1ddxd
Then, we can rewrite the term in the expectation as
n1
Cauchy- Schwarz ineq.
12
a
Es Si
a'
aa
12
2
S
1=1
i=1
2
Lemma
1
f
|a"|
lp
71
S
X
1/1-
else p
1=1
.a (B,
1
i
12
S:
x
d
2/v9
2/v
else if p 2
Thus we have the following inequality
Ro(j HAH) & Rp o HAH) +
A2 E
Σ S, i=1
1 x
if 5S else if 2
(47)
Let us now estimate the spectral norm of the average of random matrices Σm= S. using the matrix Bernstein inequality of Theorem 4 We have that
l1, = [lg( (x; + 87)) (W")))(W""""x" + 6;)) g(W' x, ())((")" 112
+ +8)) 9(W"' x,))
+o( + (["'((())))))) 3)) ("" T
(W'
< <l (x; + (,))( (x; + 6,)) -9(W" xx))
+ +1 (x: -()) - -( ([W'')))g ()9x (W"',,) x
CamchySSchwarz
I 6;)1 W 8/112 + W
5, || | x1|
Lemma W2 de + (1x x
1
if < p 2 else >2
(48)
d112//p
1,
ifl
< W2 + 2 2,000
x
1/10
else
(49)
35

---

Under review as a conference paper at ICLR 2023
where used the 1-Lipschitzness of the ReLU function. Now let examine the upper bound of the variance of the sum. We notice that S S; is a deterministic matrix as of = 1. Thus, we have
Var Σ S:
=
E [S S.
|s
1=1
B8
" E(vide + 2xxx111)) x {id- (/1-2
[1
if 5 else if p.p... >>>
W Vde)
Using
we can apply matrix Bernstein inequality of Theorem we get
Σ i=1
S:
(Werag/ 2
Σ E(Vie + +2 211xx112) log(2d)
2
+ W + 1 x
{1,
if 5 else if > 2
(d2-2/1,
W (2d)
2 2 de + 2x
(log(2d) (V + +2 (2,00)
i=1
1,
if S p 2 else if 2
d 2/10/
The above combined with (47) concludes the proof
RD(S HAH) < Ro(ʃ HAH)
A2 + w dlog(2d)
2 Σ
dd + 22|1xx112) + Vlog(2d)(VVL + X 12,00)
==1
1,
if p 2 else if pfpp5 >
2-11/2
1.2 PROOF REGRESSION SETTING
Proof of the regression bound of Theorem
First, by the definition of Rp HQH) we have that
Rp HAH)- E.
sup (A) (W)
G max Se
(aT (TT(W((; +)) - (x 0)))
7m1
< RD HAH)
+ E,
sup
Σ σ. (a T
(W(x
+ - a'T o'' + +x)))
n,a'eB, (W))
n
im1
-a' -(a g Wx,) - a'T g. ( ('))))
where, like in Appendix I.I
we denote by 8, an argument of the maxima of the inner function, (x(((x + 6)) (x( + +)))² Then, by introducing follow-
i.e. d arg maxxxeB...e
ing matrices
36

---

Under review as a conference paper at ICLR 2023
P. (x + (,))) 8))) - (Wx.) E ER
Q (W"((x; + 6,)) (x + +8)) 3W"' (W'xx)) E Rddd
R. (x + ( (x, + 05)) (o('x) E Rdxd
we can rewrite the upper bound of the adversarial Rademacher complexity as
Rp(( HAH) - Rp(l o HAH) + E.
sup a,a' (A)2 W.W' (W)
oi(a Paa Q'a'' +a R,a')
1=1
S Rb o HAH) + E,
sup
Σ i=1
0,a Pla
(AB,(A)
W. W.W.ER EE,
+ Eg
sup (A)
Σ o, 'iia' 2=1
+ Eg
sup
Σ n 1=1
o,a R,a'
n
a. (A)
W. (B,)))²
W. W.W W' (W))
S Rpllo o HAH)
+ n
BB
sup (A)
a
oi
a
i=1
(W)
Eg
sup (A)
Σ
0iQq
a'
+
1
E.r
sup a.a (()))
a
Σ o a'
11
n
W. W.W'EB, (W))
we get that W,
Following the same steps that lead to
47
Re o HAH) < Ré HAH)
2
x [1,
E, Σ P
+ Ex
Σ
+
+E
Σ i=1
o
R
211-
else if
where the matrices are defined by
P = gWWp 8,))g ( 87)) -Wpp: E Rdxd
Q: == (Wi + 6, (X + 6))) xW (Wxx:) Rdxd
R (( (x; + W + )) ((
Raxd
for some optimal matrices Wp. W p. W W W W with fn-norm smaller than W. Now
examine the spectral norm o o; a and o R; by following the same steps leading to 448).
1 [|g( ( + 8;) WWp(x + 8)))
(
1
if <p52
$ <WeevdlVdee + 11) x
(50)
2/pp/p
else if > 2 D(("xx)
| = [lo(Wa (W + +o,))
11
if 111p522
<W2eVdlVde + +2 x
d112/pp
else if ((Wxx))((WX))
|o 112 |lo(W 6,1) +5;))
1
if >
S WWevd(V + 211xx x
21pp
else if pf
37

---

Under review as a conference paper at ICLR 2023
Now examine the variance of Ei= osPi Ei=1 a,Q; and Σi=1 o;R
a o
Var
E P Pi]
f=1
2
(o(Pp(x (3)))(Wpp)) +o,)² [(Wix)lg(Wxx)) 171
(weevd(vvee +2 (2 x
f1,
if S 552 else pf 2
d/1-4/1,
==1
-Weevad) 2 Σ
+ /2(x22//x11) x
if p else if p > 2
(2-1/p,
Similarly, we can show that Var (E 02 Q and Var (E o,R can be upper bounded the same way. Now, by applying three times the matrix Bernstein inequality (Theorem[4) we have:
a
(1) S 2 dloo((d))
3,
de + 22/2xx 12 + vlog(2d)(Vde +2 (2,000))
1
if f S 2
d212/p
else if
which concludes the proof.
J PROOF OF LEMMA 5
In this section present the proof of Lemma
Proof. The proof idea is to show that, by perturbing the standard risk on T within the adversary set, the perturbed risk can approximate the standard risk on T' with some emror. First, us define perturbed risk for any perturbation
Ry 8) = EXNT (x + +0), [x)]
(51)
Σ Ep(x) sign(w(x 5(x)) y(x)
xEX
p (1.)
(52)
We then recall the definition of the standard risk on T
RT (bw,y) = [((()
sign(w x) - -x(x)
XEX
=p'Te.
(53)
We recall the definition of adversarially robust risk over domain T for the labeling function y(-)
Right (hw,y) = Ex-T
max E(hw (w + 8), x)))(())))))))))()()))))))))))))
(54)
[|8 Sr
So, for any such that || 1mx S.c, we get that
(hw y) - Rydo (hwi))) y)
51
RT (lows v) RT y/,
52
53
p p' D [((16.)111)
Since the above inequality holds for any 8 such that |101o00 S E, we must have
RT. (hw, 4) Rod v) < min
lp e 1 [((0.)
11o.
38

---

Under review as a conference paper at ICLR 2023
Now, let's examine the coordinates in A. For i-th coordinate, if it is in A, we know that
w S w X; S <|[w|l1
which implies that, there a 6 that can change the sign of Sign(w(x + 6)). and hence change the value of f.. That is, if w xy(xx 2 O, there is 6 arg = w 0y(x), such that
+ (')((())=
xyy(x) - <||w|| S
Similarly, if w T xx)(x) < 0, there is a 0" = arg max w 6y(x). such that:
w xxxxxx) w 6' )(x( w xy(xx) + < w 1|2 2 0
Finally, get
1 - 2--pp-iii {((1)))!=11
min
6: Sc
- p e)
min
ŁE(0.1)N
s.t.
= (MEA
VV'''' P.L.A)
Corollary 3.
Continuing with the settings and assumptions in Lemma the following statement holds with probability at least -
Ri. (bw: y) S RRgdo-Label (Nw: y) Radvv-aabel label (liw': 1) V (p'''p,,,
adv + discHAH
() + Rado (lw (ww)) ) + Red (1w
(1 log(1/c)
(L/c)/c)
As(E HAH) + Rt HAH)++M
n1. +V
(55)
Combining Ledmas@andd Corollary 3 Equation (55) shows that, small robust risk source domain will imply small standard risk on any target domain 7 ,i the residual error (* p, e, A,) also small. The residual error mainly depends on the adversarial budget. If the adversarial budget e is larger, A. will be larger, which means the quantity V* (p', p, L, A.) will be smaller. However, there is trade-off since will also affect other terms in the right hand side of the bound, such as adversarial Rademacher and the adversarial disagreement between hwy and hwg.
K DETAILS ON EXPERIMENTS
In Table 2 we present the details of the convolutional network. For the convolutional layer (Conv2D or Conv ID), the first argument is the number channel. For fully connected layer (FC), we list the number of hidden units as the first argument.
39

---

Under review as a conference paper at ICLR 2023
Table Convolutional network architecture.
Layer
Details
feature extractor
conv1
Conv2D(64, kemel size=5, stride=1, padding=2)
bnl
BN2D, RELU, MaxPoo22D(kermll size=2, stride=2)
conv2
Conv2D(64, kernel size=5, stride=l, padding=2)
bn2
BN2D, ReLU, Max size=2, stride=2)
conv3
Conx2D(128, kernel size=5, stride=1, padding-2)
bn3
BN2D, ReLU
classifier
fel
FC(2048) BNID, ReLU
bn4
fc2
FC(512)
hn5
BNID, ReLU FC(10)
fe3
40


Reviews:
[{"review_id": "r9906dmIp8W", "reviewer": "Reviewer_RkC2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies robust learning and domain adaptation from a learning theory perspective. It does so notably by looking at the adversarial Rademacher complexity (RC) of the robust loss function between two classes. Various results are presented: adversarially robust domain adaptation (Lemma 2), an upper bound on the RC of binary classification for linear classifiers (Lemma 3), upper and lower bounds on the adversarial RC of binary classification for linear classifiers (Theorem 1), as well as similar results for regression tasks (linear classifiers) and neural networks with ReLU activations. They finally related the robust and standard risks for linear classifiers. The authors finish with an empirical study.", "summary_of_the_review": "I think this is interesting work, with novel contributions. I believe there remains work to be done in how the paper situates itself in the literature, and that certain aspects of the contribution should be explained in more details. \n\nI gave a 5/10, because of the questions above. I am open to changing my score after the response from the authors, and I am looking forward to our discussion. ", "strength_and_weaknesses": "Note: Work cited in parentheses refers to the authors’ bibliography. Work cited in the form [ABC12] is for this review and the bibliography appears at the end of the review.\n\n## Strong points\n\nThe work is timely and interesting, and brings new ideas to the field of robustness and domain adaptation. The paper is clear and well-written. Lots of results are presented.\n\n## Weak points/omissions/clarifications:\n\nI think there are issues in the definitions of the problem (in the definition of robustness), and the related work needs clarifications. \n\n**Robust Risk Definitions**\n\nAdversarial risks defined on p.2 and p.3:\nThe adversarial risk defined on p.2 is not the same as the adversarial risk defined on p.3. Indeed, in the former, the label of the perturbed point is compared to the label $y_{\\mathcal{D}}(x)$ of the *unperturbed* point, while in the latter, it is compared to the another hypothesis’  labelling (potentially the ground truth) *also* on the perturbed point. The risk on p.2 has been defined in the literature as corrupted instantce/constant-in-the-ball robustness, and the second as error region/exact-in-the-ball. \n\nIt would be necessary to name the robust risk(s) used in this paper, as when the two definitions don’t coincide, the guarantees obtained have a different meaning.  On one hand, the error region/exact-in-the-ball risk talks about the probability measure of the expansion of the error region; we ask that the target and hypothesis *agree* in the perturbation region. On the other hand, for the more commonly-used robust risk in the literature, which is the corrupted instance/constant-in-the-ball one, a correctly classified point should not change labels if it is perturbed. \n\nIn Lemma 2 for example, a key assumption is that the loss function is symmetric and obeys the triangle inequality. This is the case for the exact-in-the-ball/error region one, but not for the constant-in-the-ball, because the first labelling function is w.r.t. a perturbed point, while the second is w.r.t. an unperturbed point. I think this poses some issues with the triangle inequality too. \n\n(Q1:) In this paper, it seems that most results use the exact-in-the-ball while Lemma 5 and Corollary 1, and the adversarial training procedure in section 6 appear to use the constant-in-the-ball. I have skimmed through the proof of Lemma 5, and it does not seem to be using prior results in the paper — can you confirm that the proof is “stand alone”, and for this particular notion of robustness? Otherwise, there could potentially be a mistake in there. \n\n(Q2:) Moreover, with this definition of robustness, I think that the adversarial RC used in this result is the same one as in (Yin et al 2018). If so, could you comment on the difference between your results and theirs (Thm 2 in particular), as well as other follow-up work using the same notion of robustness? \n\nWork that has compared different notions of robustness, to cite/read for reference: [DMM18], [GKKW21] and [PJ21]. All papers also look at fundamental limitations of robust learning compared to standard learning.\n\n\n**Related Work**\n\n(Diochnos et al. 2019). The exponential dependence on the budget not totally right: in the Theorem 3.4 statement, we can see that the budget (= number of bits) is defined as $b = \\rho \\cdot n$, so the exponential dependence on $\\rho$ is actually the normalized budget. E.g., the bounds are superpolynomial only when the number of bits the adversary can flip at test time is $\\omega(\\sqrt{n\\log(n)})$. The work of [GKKW22] gives an actual exponential dependence on the number of bits ($=b$) the adversary is allowed to perturb (though for a more restricted setting), so a superpolynomial lower bound happens when the budget is $\\omega(\\log(n))$ instead. In both works the dependence on the budget is for the error region/exact-in-the-ball robustness and is for specific problems: assumptions on concept classes and distribution families are necessary to obtain such guarantees — closeness and Normal Lévy families for (Diochnos et al. 2019) and monotone conjunctions (and superclasses like linear classifiers and decision lists) under the uniform distribution for [GKKW22].\n\n(PAC Learning frameworks for robustness). The works of (Cullina et al. 2018) and (Montasser et al. 2019) use the corrupted instance/constant-in-the-ball robustness, while the work of (Diochnos et al. 2019) uses the error region/exact-in-the-ball one. This means that the guarantees obtained differ in meaning and are general incomparable (e.g. the perturbation budget doesn’t explicitly appear in the work of (Montasser et al. 2019)). Also follow-up works [MHS21] look at implementing this algorithm with the use of a Perfect Adversary Oracle and [MHS22] gives a characterization of robust learnability through a minimax learner. The notion of robustness used by each work should be stated explicitly. \n\n(The $\\mathcal{H}\\Delta\\mathcal{H}$ class). (Cullina et al. 2018) also had a look at the robust loss of a hypothesis class, though for the constant-in-the-ball/corrupted instance notion of robustness and through the adversarial VC dimension, defined in their work. [APU20] also looks at the margin class (robust loss function) and relate its VC dimension to the sample complexity of robust learning for this notion of robustness. Recent work [GKKW22b] looks at the adversarial perturbation region of $\\mathcal{C}\\Delta\\mathcal{H}$ (i.e. the robust loss functions w.r.t. to exact-in-the-ball/error region robustness), where $\\mathcal{C}$ is the set of possible labelling functions, though through the lens of VC dimension as well, similarly to (Cullina et al. 2018) and [APU20]. Since the VC dimension and Rademacher complexity are related, there may be a link here. \n\n## Other Questions \n\n- How do the goals of robust learning and (standard and adversarial) domain adaptation differ? It would be a good idea to devote a section in the appendix to go into more details on this.\n- Could you comment on the methodology used to get RC upper bounds in Sections 3 and 4, and how they differ in approach of the works mentioned in Appendix A?\n- On p.8, you say that “If the adversarial budget $\\epsilon$ is larger, $\\Lambda$ will be larger, which means the quantity $V^*(p’,p,\\ell,\\Lambda)$ will be smaller.\" Can you explicitly state this dependence?\n\n**Typos/Comments**\n\n- p.2, second paragraph: a few typos:\n\n\"That is, the gap between robust risks on old domain and new domain can be dramatically huge...\" -> \"That is, the gap between robust risks on the old and new domains can be dramatically huge...\"; \n\n\"This observation naturally leads to the question of, *why the robust risk is harder to adapt to different domains?*, which we aim to examine in this paper.\" -> \"This observation naturally leads to the question of why the robust risk is harder to adapt to different domains, which we aim to examine in this paper.\" or \"This observation naturally leads to the question *Why is the robust risk harder to adapt to different domains?*, which we aim to examine in this paper.\"; \n\n\"...we properly extend this complexity measure to adversarial learning setting, and propose the adversarial Radmeacher complexity over H∆H class.\" -> \"...we properly extend this complexity measure to *the* adversarial learning setting, and propose the adversarial Radmeacher complexity over *the* H∆H class.\"\n- p.3, paragraph above Defn 2: “source domain $\\mathcal{S}$ and target domain $\\mathcal{T}$” — is there a “distribution” missing after this? Also, $\\hat{\\mathcal{T}}$ and $\\hat{\\mathcal{S}}$ should be switched. \n- p.3, paragraph after Defn 2: “The another advantage” -> “Another advantage”\n- p.3 paragraph above Defn 3: $d_{H\\Delta H}$ -> $disc_{H\\Delta H}$? \n- p.3, last sentence: “to adversarial setting” -> “to the adversarial setting”\n- p.4, paragraph after Defn 4: I think this is misleading: Lemma 19 is only derived for linear classifiers, while the sentence implies that the result is more general. \n- p.4, Lemma 2 statement: in the first term on the RHS of the inequality (adversarial RC w.r.t. $\\mathcal{S}$), should $\\mathbf{w}$ be $h_{\\mathbf{w}}$ instead?\n\n**References**\n\n[APU20] Ashtiani, H., Pathak, V., and Urner, R. (2020)  Black-box certification and learning under adversarial perturbations. In *International Conference on Machine Learning*.\n\n[DMM18] Diochnos, D., Mahloujifar, S., and Mahmoody, M. (2018). Adversarial risk and robustness: General definitions and implications for the uniform distribution. In Advances in Neural Information Processing Systems. \n\n[GKKW21] Gourdeau, P., Kanade, V., Kwiatkowska, M., and Worrell, J. (2021). On the hardness of robust classification. In *Journal of Machine Learning Research*, 22. \n\n[GKKW22] Gourdeau, P., Kanade, V., Kwiatkowska, M., and Worrell, J. (2022). Sample complexity bounds for robustly learning decision lists against evasion attacks. In *International Joint Conference in Artificial Intelligence*. \n\n[GKKW22b] Gourdeau, P., Kanade, V., Kwiatkowska, M., and Worrell, J. (2022). When are local queries useful for robust learning?. In *Advances in Neural Information Processing Systems*. \n\n[MHS21] Montasser, O., Hanneke, S. and Srebro, N. (2021). Adversarially Robust Learning with Unknown Perturbation Sets. In *Conference on Learning Theory*.\n\n[MHS22] Montasser, O., Hanneke, S. and Srebro, N. (2022). Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization. In *Advances in Neural Information Processing Systems*. \n\n[PJ21] Pydi, M. S. and Jog, V. (2021). The many faces of adversarial risk. In *Advances in Neural Information Processing Systems*. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "BLBxx66vz9", "reviewer": "Reviewer_Du9x", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper attempts to provide generalization bounds for adversarially robust domain adaptation. \n\nThe seminal work of Ben-David (2010) established the H-Delta-H divergence as a complexity measure for this task in the binary classification setting. Mansour (2010) established the discrepancy based distance as a complexity measure for domain adaption for multi-class classification with general loss functions. The discrepancy-based distance is further estimated from finite samples via empirical Rademacher complexity of the disagreement hypothesis class H-Delta-H.\n\nThis paper traces the following abstract template of results similar to Yin et. al. (2018) and Awasthi. et. al. (2019) but for the task of robust domain adaptation. \n- Define an adversarial Rademacher complexity via the adversarial loss function. (Here in addition the hypothesis class is H-Delta-H and the adversarial discrepancy is defined). \n- Show that adversarial Rademacher complexity is bounded by standard-Rademacher complexity + an expression that depends on the norm of the predictors and size of corruption. \n- Show that adversarial Rademacher complexity can be lower bounded by the standard complexity with a dimensional cost. \n- Instantiate the adversarial Rademacher complexity upper bound for linear predictors and 1-hidden layer neural networks.\n\nIn addition to the above, the authors show that adversarial target risk can be linked to the adversarial source risk via the adversarial Rademacher complexity and adversarial discrepancy distance. This is in the same spirit as the result from Mansour (2009). \n\nCertainly establishing the above points require sufficient effort and the authors appear to have done so rigorously. Finally, the authors establish a link between standard target risk and adversarial source risk - a result that can potentially explain why adversarially trained classifiers have better standard domain adaptation. \n", "summary_of_the_review": "I recommend accept as I believe this work clears the bar of sound technical contribution. ", "strength_and_weaknesses": "Strength\n- Extension of the same flavor of results from standard generalization -> robust generalization -> robust domain adaptation. \n- Dimension-dependent lower bounds for uniform convergence in robust domain adaptation task. \n- Link between standard target risk and adversarial source risk. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "5xQ7FyUsUq", "reviewer": "Reviewer_K4Lj", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors try to unravel why domain generalization is much more difficult in the adversarial scenario. Since the generalization bound is with respect to the adversarial Rademacher complexity term, they propose to analyze this key measure and show that adversarial Rademacher complexity is always greater than the non-adversarial one. They also try to explain the impact of adversarial training over generalization by a bound with respect to clean target error and adversarial source error. The experiments partly validate the theoretical results.", "summary_of_the_review": "I believe the paper is well written and I appreciated the theoretical bounds about generalization error. However there are some parts of the paper that are confusing. Therefore, I believe the paper could be significantly improved by clarifying the points above.", "strength_and_weaknesses": "## Pros:\n1. The writing is clear and easy to follow. The paper is well-organized.\n2. The experiments partly validate the theoretical results.\n## Cons: \nI have two main concerns about the paper:\n1. About the definition of adversarially robust risk. In this paper, $$\\mathcal{R} _\\mathcal{D}^{adv}(h _w,h _{w'})=\\mathbb{E} _{x\\sim \\mathcal{D}}[max _\\delta \\ell(h _w(x+\\delta),h _{w'}(x+\\delta))].$$ However, the classical definition [A][B] of adversarial error is $$\\mathcal{R} \n_\\mathcal{D}^{adv}(h _w,h _{w'})=\\mathbb{E} _{x\\sim \\mathcal{D}}[max _\\delta \\ell(h _w(x+\\delta),h _{w'}(x))].$$\nThe definition of adversarial error is different with the classical one. Could the authors give some explainations about this? Furthermore, it seems that the authors use the classical definition to train their network in the experiments (see eq. (13)). Does it contradict with the theory?\n\n2. About the reason why adversarial training gets better domain generalization than standard training. The authors explain this by an error bound which shows that the target clean error can be bounded by the source adversarial error. In my opinion, the bound can indeed explain that adversarial training in source domain can robustify the model on target domain. But, **there is no direct evidence** that adversarial training entails better standard accuracy on target domain, **compared to the normally trained model.**\n\nSome typos in the paper:\n1. In Lemma 2 and Corollary 1, the hypothesis is denoted by $w$ and $h_w$, are these two notations denote the same hypothesis?\n\n[A]: Theoretically Principled Trade-off between Robustness and Accuracy. ICML 2019.\n\n[B]: Towards Deep Learning Models Resistant to Adversarial Attacks. ICLR 2018.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject