Adversarially Robust Multi-task Representation Learning
Authors: Austin Watkins
Thanh Nguyen-Tang
Enayat Ullah
Raman Arora
Venue: NeurIPS 2024 poster (2024)
Keywords: Learning Theory
Multi-task and Transfer Learning
Adversarial Robustness
Primary area: learning_theory
TL;DR: We give bounds for adversarially robust transfer learning.

Abstract: We study adversarially robust transfer learning, wherein, given labeled data on multiple (source) tasks, the goal is to train a model with small robust error on a previously unseen (target) task.
In particular, we consider a multi-task representation learning (MTRL) setting, i.e., we assume that the source and target tasks admit a simple (linear) predictor on top of a shared representation (e.g., the final hidden layer of a 
deep neural network).
In this general setting, we provide rates on~the excess adversarial (transfer) risk for Lipschitz losses and smooth nonnegative losses.
These rates show that learning a representation using adversarial training on diverse tasks  helps protect against inference-time attacks in data-scarce environments.
Additionally, we provide novel rates for the single-task setting.

Adversarially Robust Multi-task Representation Learning
Austin Watkins Johns Hopkins University Baltimore, MD 21218 awatki290jhu edu
Thanh Nguyen-Tang Johns Hopkins University Baltimore, MD 21218 nguyentêca, juu edu edu
Enayat Ullah Meta" enayat com
Raman Arora
Johns Hopkins University Baltimore, MD 21218 arora@cs .era@cs.jhu.. juu. edu
Abstract
We study adversarially robust transfer learning, wherein, given labeled data multiple (source) tasks, the goal is to train a model with small robust error on a previously unseen (target) task. In particular, tation learning (MTRL) setting, i.e., we assume that the source and target tasks admit simple (linear) predictor top of shared representation (e.g., the fi- nal hidden layer of a deep neural network). In this general setting, we provide rates the excess adversarial (transfer) risk for Lipschitz losses and smooth non- negative losses. These rates show that learning a representation using adversarial training diverse tasks helps protect against inference-time attacks in data- environments. Additionally, we provide novel rates for the single-task setting.
consider multi-task represen-
Introduction
In many real-world applications, we typically have scarcity of data for the intended task. Consider, for example, settings where the learner's environment is evolving rapidly or where access to high- quality labeled data is expensive or infeasible due lack of expertise or computational limitations.
These problems are typically studied under the framework of transfer learning [6. 22, 23, 40, 19]. Such approaches aim to leverage plentiful labeled data from the source domain to learn models that can handle distribution shifts and work well on the target domain despite having small labeled dataset for the target task.
As transfer learning methods have proven successful in various applications [16. 18, 27], there is growing effort to utilize these approaches in high-risk environments like healthcare, medicine, trans- portation, and finance. Any vulnerability of these systems provides malicious agents with tempting targets. Consequently, the users of these MI. systems may find their health and financial well-being potentially jeopardized. Additionally, institutions that deploy these systems risk public relations crises and lawsuits. A particular concern is attacks that happen after a model is deployed. Such attacks are called "inference-time attacks" where, for example, malicious agent attacks large lan- guage model (LLM) chatbot, self-driving car, or a fraud-detection system. Much of the literature focuses inference-time attacks that add small perturbations to the model's 's input. Prior work has demonstrated that this can cause ML models to act unpredictably [8. 35].
Work done while the author was at Johns Hopkins University.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

While several works have focused on imparting ML algorithms with robustness to adversarial at- tacks [21, 46, 41, 28, 10], there is little emphasis on adversarially robust transfer learning, i.e., ensuring robustness to tasks with little (or no) supervision by leveraging labeled data from related tasks. In this paper, we study this problem from a theoretical perspective, building on prior work on this topic [13, 26, 12, 42]. We focus on transfer learning via learning representation that provides method for sharing knowledge between different, albeit related, tasks 47.45, 14, 29, 49]. A common approach to achieve this has been termed multi-task representation learning (MTRL) [9, 24, 11J. In practice, the class of representations is a complex model like a deep neural network, and the predic- tors trained top of them simple linear models [7, 14]. Such paradigm offers hope that can pool our data, potentially providing a substantial benefit if performed well.
In this work, we are interested in answering the following question: can multi-task learning be used to learn complex representations that facilitate robust transfer while also benefiting from the diversity of source data? We answer in the affirmative. Consider class of representations H. from Rd to a lower dimensional space RR and class of real-valued predictors trained on top of it. Let t be the number of source tasks, be the number of samples per source task, and be the number of samples for the target task. For exposition, let C(.) be the complexity of a function class that is independent of f, n, and the adversarial attack. For Lipschitz losses, we bound the excess transfer risk for the adversarial loss by
δ (VOCLF) n2
dC(H) RC(FF m
+
nt
For smooth and nonnegative losses, we bound the excess transfer risk for the adversarial loss by
! AC(F) + v Li KC(F) ò (V
(V dC(F) nl
dC(H) dC(F), dC(H) +E
Line
m
m
n
m
ne
where v and e quantify task relatedness, Lee is the average best possible adversarial risk for the source tasks, and Li is the best possible adversarial risk for the target task². The second bound is called an optimistic rate [34]. Both L and Lur allow the rate above to interpolate between a slow and fast rate depending on how difficult to be adversarially robust within the setting. Both of these rates show the benefit of pooling nt data to learn feature function that assists in mitigating adversarial attacks.
In the process of showing the above, we establish several results that we believe are of independent interest. A more complete list of our contributions follows.
1. We show bounds on the excess transfer risk for the adversarial loss class for both Lipschitz losses (Theorem 2) and smooth nonnegative losses (Theorem 5).
2. Foundational to Theorems 2 and 5 are Lemmas 1 and 3, resp. These lemmas are similar to results in prior work [25, Lemma 4.4 and Lemma 6.5.]. However, ours are less restrictive because we remove a Lipschitzness assumption on the adversarial loss class. In Appendix B.2, we provide an example of an attack model for which our lemma applies but the previous lemmas do not.
3. In our general attack model (Assumption 4) and both Lipschitz losses and smooth nonnegative losses, we bound the sample-dependent Rademacher complexity of the adversary loss class by the worst-case Rademacher complexity times multiplicative factor attributed to the adversarial attack. This latter factor for many common attacks has a dimensional dependence of Vd d. Additionally, when the loss function is smooth and nonnegative, our bound is a sub-root function, which is suitable for optimistic rates.
4. We provide framework for studying adversarial robustness in MTRL, which consists of several foundational contributions, e.g., Theorems and Definition 1, Assumption 4.A, Algorithm 1.
1.1 Some core difficulties and techniques
A core part of arguments is pair of covering number lemmas that convert from the adver- sarial loss class into the standard loss class at the expense of inflating the data. However, after applying this result to the integrand of Dudley's integral, the sample complexity depends on the radius of the cover of the function class. This dependency makes bounding the integral difficult.
Forr illustration, we use the "Gaussian chain rule" [37] to decompose F H. Due to space limitations, henceforth refrain from it except when indicated. For more details, the paragraph after Assumption 3.

---

Prior work either invoked a model or made parametric assumption to bound this integral [25]. In contrast, we bound the integral in more generality. We elaborate on these difficulties and detail our technique in Proof Sketch 5.
We use a comparison inequality from celebrated work [31] in a novel way, to our knowledge, that allows decomposition that separates function class complexity and attack complexity. Un- fortunately, this is not a full decomposition due to a weak log log dependence between the factors. However, we show that this dependence can be handled appropriately.
We present a reduction from multi-task learning to single-task learning, see the proof of Theo- rem 3, that believe is of independent interest. In particular, this observation allows simplifica- tion of prior work [37, 39] due to these works' use of worst-case complexity.
1.2 Prior work
Adversarial attack. Prior work has shown that the normalization of model weights, data, and the definition of robustness can significantly impact the dimensional cost of achieving adversarial robustness. Although not directly comparable, it informative to contrast the generalization bounds for linear classifiers presented by [5] and [17]. Both works perform Rademacher complexity based analysis with losses that are Lipschitz and satisfy certain monotonic properties. However, they mainly differ in how they normalize the quantities involved. Let and be Hölder-conjugates, [5] consider II-Il, linear classifiers with II-I1,, normalized data being attacked with I1-Iloo perturbations. They show that the Rademacher complexity of suitably transformed version of the linear model, after applying Talagrand's 's contraction lemma, has tight / dimensional dependence. Thus, when p = 1, there is no dimensional dependence. On the other hand, [17] consider 11-112 and I1-Ilp bounded linear classifiers with data being I1-112 bounded and being attacked with Il-ll, perturbations. They show that the Rademacher complexity of similarly transformed function class has no dimensional dependence. Both rates lead to generalization bounds on the robust risk. Taken together, these works demonstrate how prior research has strongly leveraged the relationship between the norm on the attack, which we cannot control, and the model and data norms. Both works also provide rates for neural networks. [5] provides a lower bound, showing that a certain variational version of a neural network has a vd lower bound. [17] shows that their rate has an vd upper bound via "tree transformation" which is then used to bound the robust risk. Finally, both works consider the optimization of surrogate losses for neural networks.
Ad Adversarial transfer. Theoretical analyses of adversarial transfer in MTRL remain relatively scarce, despite many empirical studies [33, 47, 43, 1, 38, 32]. Two works that provide theoreti- cal insights into this problem [13] and [26]. First, [13] is perhaps the first theoretical study of this problem. Specifically, they study a shared linear projection onto a smaller dimensional sub- space with linear classifiers trained on top of it, analogous to the regression study in [36, 15). Under I1 or Il-1l2 perturbation attacks, they show that the transfer risk of the adversarial loss decays as /k/m + Vk-d/nt along with multiplicative constants that depend on task diversity and can reduce the rate as more diverse tasks are gathered. In addition, they study the combination of semi- supervised learning and adversarial training and show their complementary qualities. Second, [26] considers a composite model, with a linear model being trained on top of a neural network. For additive perturbations and Lipschitz losses, they provide two results showing that the robustness of the predictor is bounded by the robustness of the representation it is trained on. Their first result, with high probability, bounds the difference between the adversarial loss of the end-to-end predictor and the standard loss in terms of the average Euclidean difference in the representations over the predictions. Their second result, applied classification, provides sufficient condition for robust- ness in terms of a bound on the aforementioned Fuclidean difference. These results are independent of the method used for training the parameters of the representation.
While not strictly in the MTRL setting, [12] works with a non-composite model and gives a suf- ficient condition for robust transfer in terms of the discrepancy between the symmetric difference hypothesis space. They give generalization bounds using Rademacher complexity. Also, [42] stud- ies the connection between domain transfer and adversarial robustness, showing that robustness is neither necessary nor sufficient for domain transferability.
Optimistic rates. Optimistic rates are type of neff-normalized inequality that bounds the excess risk that interpolates between two rates of decay. The prototypical example being the use of smooth nonnegative losses to give a rate where fast O(1/n) is achieved when task is realizable and
3

---

standard ((1/vn) when it is not [34]. Optimistic rates have been shown for linear regression with Gaussian data [48], output prediction [30], adversarial robustness [25], and multi-task learning [39]. The typical way to achieve optimistic rates is via local Rademacher complexity machinery [4].
2 Problem setup and preliminaries
Let X S Rd and y S R denote the input and the label spaces, respectively. Let be class of representation maps from R to RR and F and Fo each be a class of predictors from R to y. For a loss function é : R x y + R. denote by {(-, y) so we can represent the functions consistently as composition. Let Il-1l2 and I|- denote the Euclidean norm and the uniform norm, respectively. We use the convention that (-)) hides log terms from the usual asymptotic notation.
Each source task is represented by distribution {P;} over X' V. for j = I.....,,, and the target task is represented by probability distribution Po- Following prior work [37, 39], we make the following assumptions for tasks Pa.... Pt. We assume that (a) the marginal distribution over X is the same; (b) there exists common representation h² H and task- predictors fj E F, h (x)); and (c) the predictor f h" is the optimal* in-class predictor for its respective task w.r.t f. The assumption above implies that any additional noise in y is independent of æ because depends on x only via f3 h² (ar). As noted in [39], the second assumption above does not imply the third.
fö Fo such that P3 can be decomposed (z v) P
We assume that we have access to n training examples for each source task drawn i.d. from the respective distributions PI...., P., and m examples for the target task Po. We use (2²), v/) to denote the 7th training example for the jth task.
Adversarial attacks and adversarial training. We formulate our attack with a function class A {A : X + X. For example, A
8 I 0.01, + X3 for additive I| attacks. Our goal to learn a composite predictor fo h E Fo o H which performs well and robust these adversarial attacks, i.e., it has small adversarial risk defined formally as follows. Let fo E Fo and f = (f1,..., fi) E F Then, the adversarial population risk and empirical risk for the target and the source tasks defined as follows.
max o So o ho A)(o) A)))) AEA
Rear h A) = B(e.w)~PP
max(l, o ff o ho A)(o)) ho)))))))))) AEA
Raro (f. 11, A) =
E (a
j=1
Rear 11, A) = Σ
Lo o 1 A) (c5)) AEA
max
i=1
(f A) = ntt j=1
max
Ly o hoo AEA
We also make natural modifications of the two-stage learning procedure used in [37, 39].
Algorithm 1 (Two-stage adversarial MTRL).
( h) E arg min Raro (f,, JEFOL DEH
(Stage 1)
Multi task adversarial (reresenatation) learning
fo arg min Prar (For b,
(Stage 2)
jeFo Adversarial Transfer learning
In Stage 1, we perform empirical risk minimization over the adversarial loss class for the combined t tasks. After Stage 1 we have t compositions fi h...., fo
h which minimize the average risk
3 As prior work [37, 39], we allow different predictor classes for the source and target tasks. "This assumption not strictly necessary but helps making the optimistic rates more interpretable.

---

above. Now, in Stage 2, we fix the representation h learned from the source tasks and perform empirical risk minimization again to find a new predictor for the target task. The final predictor for the target task is fo h.
Adversarial task diversity. Naturally, if all of our tasks are drastically different we expect Al- gorithm to perform poorly. Therefore, is crucial to quantify the relationship between the tasks. Prior work in the linear setting gives sufficient properties between the tasks to provide provable rates [15, 36]. However, these assumptions are terms of spectral properties and therefore not suitable in more general setting. A more general notion of task relatedness called task diversity was intro- duced in [37]. This relationship between tasks was shown to be sufficient for Lipschitz losses [37] and smooth nonnegative losses [39]. Yet, it was not clear if these guarantees hold in an adversarial setting. To close the gap, we introduce a new notion of adversarial task diversity."
Definition 1 (Robust (v, E, A)-task diversity ). The tasks (P,Yi-) are (v, e, A over Po. if for the corresponding f E FSt, ,f0 E Fo and representation h" E H, we have that for all h' E H
( A)- Rear (Jō h², A) S v v I'EFo
inf
Rare ( "N, A) Rare ",,"""" A)) + e. J'EFRI
inf
Loss class and dataset notation. Let function class Q a function class and its l-fold Cartesian product be Q8t, We use the following notation for the standard MTRL loss class.
( = ((x1, + ((eg) o ())(x))......) (cy o (2+)) q E 2
We define an adversarial counterpart to the MTRL loss class (above) as follows.
(2*)) (.1,,...,,.))) ..) + (max(Cyr o A)(1)) max(ey, o o A)(a)) 1 E 281). AEA
AEA
We define the function class Q restricted by functional V R' - R at r as Q,, {q E Q V(()= S r). We will consider V to be multiple (by factor of b) of the adversar- ial or standard risk. The Rademacher complexity of this restricted functional class yields local Rademacher complexity. When using local Rademacher complexity
common to bound it by a sub-root function. A function vb [0, 0o) > [0, oo) is sub-root if it is nonnegative, nondecreasing, and i + (r)) /r is nonincreasing for r > 0. Sub-root functions are continuous and have unique fixed points [4]. Given E X let Cx()) be proper I1-Ila-cover of A(x) at scale Since Cz(E) is proper. this cover is realized by some subset of A. Let CA(c)) (s) be this subset of A w.r.t. x. Given a dataset S = {(x;, 3/) (/:)))) Jejjs) we notate Se = ((A(a,), ) u)) i E [m], A CAta.) (e) to represent the approximate inflation of S with respect to AA at radius e. Our convention is to have all covers be minimal when minimality can be achieved.
Complexities. Next, we introduce the notions of complexities of functions classes that we will utilize. First, we give the Rademacher based complexities suitable in MTRL on a fixed set of inputs. Let Q be class of vector-valued functions from Z to Ra. Denote the p-fold Cartesian product of Q as Q"99. For Z fine the data-dependent Rademacher width and data-dependent Rademacher complexity, respec- tively, as Rr Z) == Bo,,, |sup (np)) (np)-1 Enphe (z)k(gz(=())) and [ Z) = E Isup (mp) Eijl" Jijk (g (z]))al] where ozjik are i.idd Rademacher random variables. In contrast to the convention we will place particular emphasis on the dataset, and therefore, it is prominent in the notation. We define the worst-case Rademacher width and the worst-case Rademacher complexities as R{@@P, n) = supz R( Z) and [ n) =
= (Et))En)))) where z} E Z, de-
(9 Z).
Next, using the same notation, we define the empirical covering number of vector-valued func- tion class. With > O, define (2( ,, Z) be the cardinality of a minimal cover C' such that for all q E 0 there is a q E C such that (np) E P.P.9 1-j.== ((gg(2))) (2))) (2)())) < E² and N (Q ,,, Z), similarly, but with max 10 (z²)) ((
(2)())) S & as the norm instead.
Finally, we define the fat-shattering dimension. Let Q be class of functions from Z to IR and let Z ( }m} where Z C Z. Then, for 7 > O, we say that Z is y-shattered by Q, if there
'Note that this is slightly different than the definitions introduced in [37]. here we are using a product space structure like [39] to simplify the problem.
5

---

exist Pl...... Tw,, such that for all b E {0, 17 there is a q Q such that for all i E [m]] we have fx; 2 7t + y if b; 1 and fx,) S r; 7 if b, 0. Let vez((,)))) 7) be the cardinality of the largest subset of Z that is y-shattered by Q. If largest subset does not exists, let vez(2, 7) co.
Assumptions. We make the following assumptions the loss function, hypothesis classes, and the adversarial attack function. The first two assumptions regarding if the loss is Lipschitz or smooth nonnegative are standard.
Assumption (Lipschitz loss). The loss function e R y R is Ly-Lipschitz and b-bounded i.e. |e(y', w)1 < b < xc, Vy' E R,y E y and ( v) by (32, 4)1 - Lely V2 for all yı E R. y E Y.
Assumption 2 (Smooth nonnegative loss). The loss function E R y R is nonnega- tive, b-bounded, and H H-smooth, i.e., 0 S f(y' y) bbbb <bb x for all y/ E RR y and (v1.8) - (22, v) S H y2l for all y1, 92 E R.yey.
The next assumptions are that the predictor and representation function classes are Lipschitz. Assumption (Hypotheses and feature maps are Lipschitz).
A: All functions in F and Fo are Il-ll-Lipschitz for some 0 < L < oc, ie. (5(z)) [(22) S T ø2l for all 21, 22 E Df and f T Fu.o
B: All functions in H are (II-IlAy Il-lli-Lipschitz for some 0 < Ln co, ie. l1h(z1) h(22))l S [=]|=1 22 = for all 21, 22 E Dom(h) and h E H.
If the norm in Assumption 3.A is Euclidean and additionally any f Fo H is D-bounded over X' w.r.t. || . ll2 then these assumptions are sufficient to apply the so called Gaussian chain rule [37]. This allows more interpretabiliiy since the statistical cost of learning can be broken up into two terms, for F and H separately, in a rather intuitive way. We do not apply this theorem primarily due to space limitations. However, for illustrative reasons, we will assume these assumptions hold when we analyse the asymptotics of Theorems 2 and 5.
Finally, we make the following assumptions on the adversary. Assumption (Bounded within-domain adversarial attacks).
A: A(x) is totally bounded w.r.t II- for all X. That for all 0 a finite number of I1-I1 balls of radius e cover A(x) for all x E X.
B: The attack function cannot perturb outside of the input domain X, i.e., A S {A: X + 27.
First, Assumption 4.A trivially implies that there exists A < oc such that SuPAEA.EEx ||
A. Second, Assumption 4.B is reasonable assumption as we discuss in Appendix
3 Adversarial multi-task representation learning
In this section, we give our main adversarial MTRL results. Given robust task diversity (Definition 1) holds, these theorems show that with high probability, adversarial excess transfer risk decays with the sample size and is bounded by the complexity of the non-adversarial loss class and an additional factor derived from the adversarial attack. First, we show our result for Lipschitz losses, and then for smooth nonnegative losses.
3.1 Lipschitz losses
Lipschitz losses, like ramp loss, are frequently used in machine learning. We will start with uniform convergence bound that is foundational to our study of Lipschitz losses. The following result bounds the adversarial excess transfer risk by the Rademacher complexity of the adversarial loss class for the source tasks and target task. This result is an adversarially robust version of the main MTRL result [37] before utilizing the Lipschitzness of the loss. Alternatively, it can be seen as MTRL version of Corollary I in [44].
Theorem 1. Let in and jo be the learned representation and target predictor, as described Algo- rithm 1. Under Assumption I and that f is (v, &, A) -ivieres over Fo w.r.l. h then, with probabilty

---

at least 28, we have that Riat fo. R A) Rrar (fo: ht, A) is bounded by
-ー (=((
8by (2g /// nft +8 sup (Fo o +) logg2/ heR
We now apply the above to Lipschitz losses classes. But, before we do, let us define special function that features prominently in our work. Let the function A A L, n, 3) be mapped to
log log Si (dv/L)) +
( (1
3 3
cp)
(
+ 10
VeC
4o 1o8
SA
eb 4o//L
log 16po88
E
When needed, we will use (t='":-'''" or N ((()))))))))) to indicate which data is being inflated.
Theorem 2. Under the setting of Theorem along with Assumption 3. Assumption 4, (ebb/4e//llaa)) (SAal// ((ee//4e//mLa)) 2 ee, vex(C(F o HH, B,b,,, (Cx(F o (2b)) 2 1, then the Rademacher complexities (FFC((F)(H)) n) and A( o h)) m) in Theorem I are, respectively, bounded by
2/51 (71), n) n) A (2-1, LLs,,t,, nt, Bi) and 2 sup NEM
[R[(C o h), m) (2 m, 32), (I)
where L3 LeLy Ln, L1 LeLy, and C, are absolute constants.
If we ignore the two factors that come from the adversarial complexity, the result is similar to prior work in the non-adversarial setting of [37]. In fact, if A exclusively contains the identity function, then we recover the adn-adversarial version modulo log factors.
The assumptions on the fat-shattering dimension and size of the inflated dataset are in several of our theorems. It should be noted that they are technical and mild First, [SA(1/VT) is usually exponential in d, and, therefore, practically always larger than e" < 16. Also, the assumption trivially holds if the dataset is larger than 16. Second, VCx o H), 9b) 2 1 is just a parametric version of the assumption that the fat-shattering dimension is nonzero. Practically speaking, 3 being 1 or 1/2 is reasonable and does not impact the bound in any meaningful way.
A dimensionality analysis on the first expression in Equation (1). Recall that A(r) is to- tally bounded for all x E X' w.r.t. Il- So, over the sample S, the attack class perturbs the points only so far. That is, SuPres,Ar,AE.A A(x) - A'(())l < A < oo for some A. This gives us a radius for which we place n balls of radius A to cover A(S). By standard vol- ume arguments, e.g. Lemma A.8 in [20], each of these balls can be eb/4cy/tt Ly-oeeee by LntLz//eb) many points. Thus, n (12o//ntLaA/ebb bounds the cardinality of the inflated dataset S (eb/4e//ntL.. By using this inequality in Equation (1), RC S) is bounded by [ (H)), nt) / (dlog(LLAA/b) log (d log(oonnnn (LnL /b) log(n), where we set 3 = 1, ig- nored constants and lower-order terms. Therefore, as a function of d, the adversarial training costs at least factor of Vd d more in comparison to the standard non-adversarial loss. The analysis of the second expression in Equation (1) is similar but the dimensional dependence is V log k because the inflation happens in the image of the representation space.
The dimensionality and sample size dependencies of Equation (1). Like in the introduction, let C(-) be the complexity of a function class which is independent of the sample complexity and
and the adversarial attack. Generally, (C n) decays as [98) (CFFo o h), m) as O(VC(Fo)/m.) If the image of the source tasks predictors is bounded and Il-lla-Lipschitz, we can decompose ())))))))))) n) into O O(/C(H)/nt + (O(C(F))/n) by using the Gaussian chain rule [37]. Additionally, the adversarial robustness factors contribute Ö(vd) for the source tasks and Ō(Vk) for the target task because of the dimensionality analysis in the prior paragraph. Taken together, in this setting, the adversarial excess transfer risk decays as Ö (VdC(F)/n + dC((H)/nt + VkC(Fo)/m).. See Appendix B. for detailed comparison of the above rate the linear setting studied in [13].
Proof Sketch 1. The result follows by bounding the adversarial Rademacher complexities by calling Theorem twice. However, for the Rademacher complexity w.E.t the target task one must make the observation that we can treat h o A(x) as the attack function class for all x. This function is totally bounded by Assumption 3.8 B and therefore we can proceed normal. See Appendix E.I for details.
7

---

The proof above depends on the following bound on the Rademacher complexity of the multi-task function class (H)F)(()) To achieve this bound, we reduce the multi-task setting to the single- task setting. Although simple, this reduction simplifies arguments made in prior work [37, 39] because these works use worst-case complexity.
Theorem 3. Under the setting of Theorem 2, R(LA(FS(H)) (HL). is bounded by 2 RI(((FF (H)), x) (2~1, L,,,t,, B1), where L, = L LegII1.1p 1.z.
Proof Sketch 2. The proof reduces the multi-task setting the single-task setting by observing that the date-dependent multi-task Rademacher complexity is equivalent to the data-dependent single- task Rademacher complexity task. See Appendix E. for details.
dataset with an additional immutabbe component indexing the
The proof of Theorem immediately implies we can use the machinery in the single-task setting literature. This is also true in the non-adversarial setting. Therefore, the above reduction technique applies to situations outside adversarial robustness. However, the above argument does not work when using worst-case Rademacher complexity because S would not be a sample of i.i.d. ran- dom variables. Yet the above method is a convenient tool as we are using worst-case cosst-case Rademacher complexity because our analysis goes through the fat-shattering dimension. In Appendix D, we give a short remark on notion of fat-shattering dimension suitable for vector-valued classes.
3.2 Smooth and nonnegative losses
Like in the case of Theorem 1, we extend prior work the adversarially robust learning setting. Since much of what we discussed about sample complexity and dimensionality parameters in the prior section also applies here, this section will be more brief.
Theorem 4. Let h and fo be the learned representation and target predictor, as described Algo- rithm! 1. Let 1/1 and the be sub-root functions such that vi(r) 2 (R(CA(FF( ln), and (2(()) 2 bsupREn (Fo o h Ir), m) with rí and r the fixed points of the (r) and (2(().. respec- tively. Under Assumption 2 and that f is A)divves over Fo w.r.t. h", then, with probability Rear (fō: h², (t,,)) is bounded by.
least 20-6, 8, we have that Rear (fo.h.
bd /9 m
ri
17165 +
21967ri
Rear(Jo, hi, AA
+ 211
m
2b
65 (o/11
+ v V Parceff 6v/
r
10266
217r +
nt +
146
+
b
nt
b
Theorem 4 requires bounding the local Rademacher complexity of the adversarial loss class by sub-root function, which is the main challenge in applying this result. We show that such a bound is obtained if the predictor classes are Lipschitz and the loss smooth and nonnegative.
Theorem 5. Under the setting of Theorem 4 along with Assumption 3, Assumption 4,
IS (eb/ /nt///////tt (Sabbb// (e(e//bc//mmm)))) 2 e., vex(E(F H), Bib), vcx H), B2b) Z 1. then the fixed points /ra/h /b and /rq/b in Theorem 4 are, respectively, bounded by
2 2/12H (9) ( (H), A (24H6) 1/2 L2, L2, 3.)
and 2v I2H Di (Fo h A tur (24116) 1/2 L,, m, 32), where L2 = LzL#
Comparing Theorems 2 and 5, the latter has twice many complexity terms: two for the target task and two for the source tasks. Therefore, we will start our asymptotic analysis of Theorem 5 from where the analysis after Theorem left off. For the target task terms, one of these terms is multiplied by the square root of the adversarial risk for the best-in-class predictor and representation, i.e. Rear R.a. h²,,, ,A). This factor is zero when an adversarially robust classifier exists. This leaves only one complexity term remaining for the target task, which is squared version of the last one. Thus, this setting, the bound a fast rate in the number target samples m. This reasoning shows the value of learning a robust representation because it takes fewer samples to learn good predictor.
8

---

Similarly, the bound is fast rate in the number of source tasks and respective samples per task n if there exist predictors with zero adversarial risk on the souree tasks. Thus, the bound on the excess transfer risk of the adversarial loss class decays as (dC + dC(H)/nt + kC(FF)/m) when robust predictors and representations exist in our chosen classes.
Proof Sketch 3. The proof is like the argument for Theorem 2, but use Theorem 6 not Theorem 3.
In the setting above, we now give our bound on the local Rademacher complexity of the adversarial loss class. Importantly, the bound is a sub-root function in r.
Theorem 6.
Under the setting of Theorem 5, R(CA(FW) (7) Ir), S) is bounded by ((24H6)-1/² L2, nt, B1), where L2 = LzL
2v 2V12H (R] Proof Sketch 4. Use the reduction in the proof of Theorem 3, then use Theorem
4 Standard adversarial learning
4.1 Lipschitz losses
In this section, we bound the adversarial Rademacher complexity for the standard single-task setting under the assumption of Lipschitz loss. Such bounds immediately give results for the excess risk of the adversarial loss class via a uniform convergence guarantee like Corollary I in [44]. The results and arguments for smooth and nonnegative losses are similar. See Section 4.2 for details.
The following result bounds the class by two factors: the worst-case Rademacher complexity for the non -on-adversarial loss class and function that encodes the power of the attack model.
Rademacher complexity for the adversarial loss
Theorem 7. Let F be Ly-Lipschitz w.r.f.
I-11A: Under Assumption 1, Assumption 4, (eA(eb/Ae//LL e", vCx((((F), 96) 2 1, then (CA(FF), S) is bounded by 2) A n,,,,
(2)
where L1 LELF and C, e are absolute constants.
Many of the remarks in Section 3 apply Theorem See Appendices B.2 and B.3 for detailed comparisons to [25] and [4], respectively.
Proof Sketch 5. The difficulty of studying adversarial robustness originates from the variational component of the adversarial loss class. Under certain assumptions, we can remove the max func- tion with an appropriate "inflating" of the dataset by using a covering number argument inspired by [25]. The proof of the result below is in the appendix.
Lemma 1. Let F be L--Lsschhitz w.r.t. I1-11 Under Assumption 1, and Assumption 4, we have N (C E) & (L(F), SA(e/2L))) where L1 LLL..
Although we find Lemma I insuitive, it does result in a difficulty that we demonstrate below. First, as expected, apply Lemma 6, Dudley's 's integral; then Lemma 1. These steps are shown in the inequality below.
((LA(F),)) S 4a +
10
SA VII (OCNsCCC)),, (C E
E
de
(3)
/n
2L,
The above removes the variational component of the loss at the expense of "inflating" the data. Yet, notice that now this "inflated" data S is a function of This makes the integral more difficult to study because, after applying other techniques from prior work [34, 39], one cannot move the sample complexity out of the integral. This difficulty is resolved in prior work by either invoking a model (e.g.. FF being linear predictors) or making parametric assumption. Both of these approuches are used in [25], with the parametric assumption being N
S E
Alternatively, we provide an approach that overcomes these challenges while retaining the generality of the results. Starting at Equation (3), our approach is to decouple the complexity of the class and the properties of the inflated dataset. We observe that weak decoupling can be achieved by the use of comparison inequality from Il cover to the fat-shattering dimension. In particular, such comparison inequality is the following special case of celebrated result in [31].
'The special case is the empirical measure the drawn data.

---

Lemma 2 (Rudelson and Vershynin (2006)). Suppose F is uniformly B bounded for B > 0, then, for all 5 > O, we have log.N (F, V Cv log( Bn/ve) log vn/v) for 0 < E < B where V vex(FF ( and C,e c > are universal constants.
If we apply Lemma 2 to the integrand of Equation (3), then N / S Cvex(C(() cfe/2)
(ISAl//LL))) where, for illustrattve purposes, we removed the fut-shattering dimension factors from the denominators by assuming that vcx(C(FF) cfe/2) 2 1. (In general, we must be more nuanced than this by handling cases see the full proof for more details.) This decomposition allows us to handle each factor in turn in a way that was not possible before. Yet, the picture is more complicated than this, for instance, E can depend weakly on SA(.). Nevertheless, from here, the complete proof see Appendix E.2.2 proceeds with more traditional analysis and relies on other standard lemmas. The above weak decomposition illuminates the significance of Assumption 4.B in our analysis. In particular, when the image of all attacks is in X, we have that the points fat-shattered are within X, not A(X), i.e,
we have vcx vCx(F(F), 2) not A(x) (L(F), If Assumption 4.B does not hold, there is a stronger dependence between the complexity of the attack and the complexity of the predictors.
To our knowledge, this is novel use of this family of fat-shattering comparison inequalities, and our techniques derive novel rates in the single-task setting while retaining the generality. The authors of [31, p. 607] conjecture that the log (n/vv u) factor in Lemma 2 can be removed, although it is unclear what the nature of { like dependence would be. Naturally, their conjecture implies another: that, for our setting, the Rademacher complexity of the adversarial loss class is (F), is O(VZ).
4.2 Smooth nonnegative losses in the single-task setting
In this section, we bound the local Rademacher complexity of the adversarial loss class for smooth nonnegative losses in the standard single-task setting. Many of the remarks in Section 4.1 apply here too. Thus, we will forgo much of this repetitive commentary for the sake of space. First, we bound the adversarial local Rademacher complexity of the adversarial loss class.
Theorem 8. Under the setling of Lemma 3 along with (eb/Ac///))) 2 e and vcx bB)) Z 1, then we have xF ()) is bounded by v/2H A (F, m)) 112 Ly, n,, 3). where C, e are absolute constants.
A non-adversaril version of Theorem 8 was shown in the seminal [34] with a bound of order Õ(V Hr (9 (F, n)). In comparison, in the adversarial setting, the expression in Theorem 8 has the additional factor due to the adversary which is of order Ö(Vd), Importantly, our bound is also sub- root function in r and, thus, suitable for optimistic rates derived from local Rademacher complexity. See Appendix B.2 for a comparison of these results with those in [25].
Proof Sketch 6. The proof proceeds by using Lemma 3 and analysis similar to the proof of Lemma 1.
Our proof of Theorem 8 depends on the following covering number lemma, which similar to Lemma 6.5. in [25]. The proof of this lemma is in Appendix E.2.3.
Lemma 3. Let F be a class of predictors and let F Ir be all functions in F with empirical ad- versarial risk less than r on S. If 1o is Lø-Lipschitt w.r.t. II-II then under Assumption 2 and Assumption 4, we have N2 i)), S Nox (F,e/2/12Hr,
S.A ( (5/2//2HrL=)
5 Conclusion
In this work, we have shown several theorems that demonstrate that a representation derived from adversarial training can assist in defending against adversaries on downstream tasks. Such theorems show how utilizing diverse tasks can assist in learning robust representations in data-scarce or high- stake domains. Some additional questions are how to optimally select source tasks to maximally assist in learning a robust representation and if the assumption of the attack residing within the data domain can be relaxed while retaining our ((v)) rate in general settings. Our main technical innovation is using a celebrated fat-shattering inequality [31] to carefully control the inflation of the dataset. In doing so we have also shown several novel rates in the single-task setting.
10

---

Acknowledgments and Disclosure of Funding
This research was supported, in part, by the DARPA GARD award HR001 12020004, NSF CA- REER award IIS-194325,, funding from the Institute for Assured Autonomy (IAA) at JHU, and the Spring"22 22 workshop on "Learning and Games" at the Simons Institute for the Theory of Computing.
References
[1] Kumail Alhamoud, Hasan Abed AI Kader Hammoud, Motasem Alfarra, and Bernard Ghanem. Generalizability of adversarial robustness under distribution shifts. Trans. Mach. Learn. Res., 2023, 2023.
[2] Noga Alon, Shai Ben-Dar Davida Nicolò Gesa-Bianchi, and David Haussler. Scale-sensitive di- mensions, uniform convergence, and learnability, In 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993, pages 292-301, IEEE Computer Society, 1993.
[3] Martin Anthony and Peter L. Bartlett. Neural Network Learning Theoretical Foundations. Cambridge University Press, 2002.
[4] Peter L. Bartleut Olivier Bousquet, and Shahar Mendelson. Localized rademacher complexi- ties. In Computational Learning Theory, 15th Annual Conference on Computational Learning Theory, COLT 2002, Sydney, Australia, July 8-10. 2002, Proceedings, volume 2375 of Lecture Notes in Computer Science, pages 44-58. Springer, 2002.
[5] Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities Risk bounds and structural results. J. Mach. Learn. Res., 3:463-453 2002.
[6] Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of represen- tations for domain adaptation. In Advances Neural Information Processing Systems 19, Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 4-7, 2006, pages 137-144. MIT Press, 2006.
[7] Yoshua Bengio, Aaron C, Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE Trans. Pattern Anal. Mach. Intell., 35(8):1798-15)) 2013.
[8] Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Srndic, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Machine Learning and Knowledge Discovery in Databases European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part III, volume 8190 of Lecture Notes in Computer Science, pages 387 487-402. Springer, 2013.
[9] Yifang Chen, Kevin G. Jamieson, and Simon S. Du. Active multi-task representation learning. In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 3271-3298. PMLR, 2022.
[10] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via ran- domized smoothing. In Proceedings of the 36th International Conference on Machine Learn- ing, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 1310-1320. PMLR, 2019.
[11] Liam Collins, Hamed Hassani, Mahdi Soltanolkotabi, Aryan Mokhtari, and Sanjay Shakkottai. Provable multi-task representation learning by two-layer relu neural networks. In Forty-first In- lernational Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024.
[12] Yuyang Deng, Nidham Gazagnadou, Junyuan Hong, Mehrdad Mahdavi, and Lingjuan Lyu. On the hardness of robustness transfer: A perspective from rademacher complexity over symmetric difference hypothesis space. CoRR, abs/2302. 2023.

---

[13] Zhun Deng, Linjun Zhang, Kailas Vodrahalli, Kenji Kawaguchi, and James Y. Zou. Adversarial training helps transfer learning via better representations. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6- 14, 2021, virtual, pages 25179-25191, 2021.
[14] Jeff Donahue, Yangqing Jia, Oriol Vinyals, Judy Hoffmann, Ning Zhang, Eric Tzeng, and Trevor Darrell. Decaf: A deep convolutional activation feature for generic visual recognition. In Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014, volume 32 of JMLR Workshop and Conference Proceedings, pages 647-655, JMLR.org, org. 2014.
[15] Simon Shaolei Du, Wei Hu, Sham M. Kakade, Jason D. Lee, and Qi Lei. Few-shot leamn ing via learning the representation, provably. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
[16] Mohsen Ghafoorian, Alireza Mehrtash, Tina Kapur, Nico Karssemeijer, Elena Marchiori, Mehran Pesteie, Charles R. G. Guttmann, Frank-Erik de Leeuw, Clare M. Tempany, Bram van Ginneken, Andriy Fedorov, Purang Abolmaesumi, Bram Platel, and William M. Wells III. Transfer learning for domain adaptation in MRI: application in brain lesion segmentation. In Medical Image Computing and Computer Assisted Intervention MICCAI 2017 20th Inter- national Conference, Quebec City, QC, Canada, September 11-13, 2017, Proceedings. Part III, volume 10435 of Lecture Notes in Computer Science, pages 516-524. Springer, 2017.
[17] Justin Khim and Po-Ling Loh. Adversarial risk bounds for binary classification via function transformation. CoRR, abs/18 abss/181.09911 10.09519, 2018.
[18] Xiaofeng Liu, Xiongchang Liu, Bo Hu, Wenxuan Ji, Fangxu Xing, Jun Lu, Jane You, C.-C. Jay Kuo, Georges EI Fakhri, and Jonghye Woo. Subtype-aware unsupervised domain adaptation for medical diagnosis. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 2189-2197. AAAI Press, 2021.
[19] Xiaofeng Liu, Chae Hwa Yoo, Fangxu Xing, Hyejin Oh, Georges El Fakhri, Je-Won Kang, and Jonghye Woo. Deep unsupervised domain adaptation: A review of recent advances and perspectives. CoRR, abs/2208.07422, 2022.
[20] Philip M. Long and Hanic Sedghi. Generalization bounds for deep convolutional neural networks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
[21] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC. Canada, April 30- May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
[22] Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation with mul- tiple sources. In Advances in Neural Information Processing Systems 21, Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems, Vancou- ver, British Columbia, Canada, December 8-11, 2008, pages 1041-1048. Curran Associates, Inc., 2008
[23] Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. In COLT 2009 The 22nd Conference on Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009, 2009.
[24] Yuren Mao, Weiwei Liu, and Xuemin Lin. Adaptive adversarial multi-task representation learning. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Re- search, pages 7724-6738 PMLR, 2020.
12

---

[25] Waleed Mustafa, Yunwen Lei, and Marius Kloft. On the generalization analysis of adversarial learning. In International Conference on Machine Learning. ICML 2022. 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 16174-16196. PMLR, 2022.
[26] Laura Fee Nern, Harsh Raj. Maurice André Georgi, and Yash Sharma. On transfer of adver- sarial robustness from pretraining to downstream tasks. In Advances in Neural Information Processing Systems 36: Anmual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
[27] Maithra Raghu, Chiyuan Zhang, Jon M. Kleinberg, and Samy Bengio. Transfusion: Under- standing transfer learning for medical imaging. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 3342 3352, 2019.
[28] Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Semidefinite relaxations for certifying robustness to adversarial examples. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 10900-10910, 2018
[29] Ali Sharif Razavian, Hossein Azizpour, Josephine Sullivan, and Stefan Carlsson. CNN features off-the-shelf: An astounding baseline for recognition. In IEEE Conference on Computer Vision and Puttern Recognition, CVPR Workshops 2014, Columbus, OH, USA, June 23-28, 2014, pages 512-519. IEEE Computer Society, 2014.
[30] Henry W. J. Reeve and Ata Kabán. Optimistic bounds for multi-output prediction. In Proceed- ings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 0030-8040. PMLR, 2020.
[31] Mark Rudelson and Roman Vershynin. Combinatories of random processes and sections of convex bodies. Annals of Mathematics, 164:603-648. 6688, 2004.
[32] Hadi Salman, Andrew Iyya, Logan Engstrom, Ashish Kapoor, and Aleksander Madry. Do adversarially robust imagenet models transfer better? In Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 12, 2020, virtual, 2020.
[33] Ali Shafahi, Parsa Saadatpanah, Chen Zhu, Amin Ghiasi, Christoph Studer, David W. Jacobs, and Tom Goldstein. Adversarially robust transfer learning. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenRe- view.net, 2020.
[34] Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. In Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a meeting held 6-9 December 2010, Vancouver, British Columbia, Canada, pages 2199-2207. Curran Associates, Inc., 2010.
[35] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
[36] Nilesh Tripuraneni, Chi Jin, and Michael Jordan. Provable meta-learning of linear repre- sentations. In Proceedings of the 38th International Conference Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Re- search, pages 0444-10443, PMLR, 2021.
[37] Nilesh Tripuraneni, Michael Jordan, and Chi Jin. On the theory of transfer learning: The im- portance of task diversity. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
13

---

[38] Francisco Utrera, Evan Kravitz, N. Benjamin Erichson, Rajiv Khanna, and Michael W. Ma- honey. Adversarially trained deep nets transfer better: Illustration on image classification. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
[39] Austin Watkins, Enayat Ullah, Thanh Nguyen-Tame and Raman Arora. Optimistic rates for multi-task representation learning, In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
[40] Garrett Wilson and Diane J. Cook. A survey of unsupervised deep domain adaptation. ACM Trans. Intell. Syst. Technol., 1 1165:51:1-51:46, 2020.
[41] Eric Wong and J. Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 5283-5292. PMLR, 2018.
[42] Xiaojun Xu, Jacky Y. Zhang, Evelyn Ma. Hyun Ho Son, Sanmi Koyejo, and Bo Li. Adver- sarially robust models may not transfer better: Sufficient conditions for domain transferability from the view of regularization. 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 14770-24802. PMLR, 2022.
International Conference on Machine Learning, ICML
[43] Yutaro Yamada and Mayu Otani. Does robustness on imagenet transfer to downstream tasks? In IEEE/CVF Conference on Computer Vision and Pattenn Recognition, CVPR 2022, New Orleans, LA, USA, June 18-24, 2022, pages 9205-9214, IEEE, 2022.
[44] Dong Yin, Kannan Ramchandran, and Peter L. Bartlett. Rademacher complexity for adversar- ially robust generalization. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceed- ings of Muchine Learning Reseurch, pages 7085-7094. PMLR, 2019.
[45] Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson. How transferable are features in deep neural networks? In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, 2014.
Quebec. Canada, pages
[46] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing, Laurent El Ghaoui, and Michael I. Jordan. Theoretically principled trade-off between robustness and accuracy. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 7472-7482. PMLR, 2019.
[47] Jiaming Zhang, Jitao Sang. Qi Yi, Yunfan Yang, Huiwen Dong, and Jian Yu. Imagenet pre- training also transfers non-robustness. In Thirty-Seventh AAAI Conference on Artificial Intel- ligence, AAAI 2023, Thirty-Fifth Conference on Innovative Applications of Artificial Intelli- gence, IAAI 2023, Thirleenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2023, Washington, DC, USA, February 7-14, 2023, pages 3436-3444, AAAI Press, 2023.
[48] Lijia Zhou, Frederic Koehler, Danica J. Sutherland, and Nathan Srebro. Optimistic rates: A unifying theory for interpolation learning and regularization in linear regression. CoRR, abs/21 12.04470, 2021.
[49] Fuzhen Zhuang, Zhiyuan Qi, Keyu Duan, Dongbo Xi, Yongchun Zhu, Hengshu Zhu, Hui Xiong, and Qing He. A comprehensive survey on transfer learning. Proc. IEEE, 109(1):43- 76, 2021.
14

---

Contents
1 Introduction
1.1 Some core difficulties and techniques
1.2 Prior work
Problem setup and preliminaries
3
Adversarial multi-task representation learning
3.1
Lipschitz losses
3.2 Smooth and nonnegative losses
8
4
Standard adversarial learning
4.1
Lipschitz losses
4.2
Smooth nonnegative losses the single-task setting
10
Conclusion
10
Glossary
15
A A remark about attack functions
17
B Technical comparisons to prior work
18
B.1 Comparison to [13]
18
B.2 Comparison [25]
18
B.3 Comparison to [44]
19
C Lemmas
19
Vector-valued fat-shattering dimension digression
19
Proofs
20
E.1
Proofs in Section 3
20
E.2
Proofs in Section 4.1
E.2.1
Structural Results
E.2.2
Lipschitz Losses
24
E.2.3
Smooth and nonnegative losses
25
NeurIPS Paper Checklist
28
15

---

Glossary
[ (Q Z) The data-dependent Rademacher complexity of @8P for Z = (=f) seln) i.e.
|i| (Q Z) = Eo,,,
Σ iJAk=1
Sak (g5 (2)))))
sup 9000v
nP
where zj E Z and o.j.u are iid. Rademacher random variables. Rs 1,, The empirical adversarial risk for source tasks.
Roro h, A) =
1
Σ
max
Lug fo AEA
o ho (36)
Read (f, h, A) The empirical adversarial risk for the target task.
Rear (f, h A)
max AEA
(os 13 o h A)
nit
(e, L,,,
The function that maps to
log log SA ( eb
cp B
(
VeC + 40
4evn
eb Acv/nI/ )) log
16pc3n
4cynI.
+
c
/
log
SA
c²
This function encapsulates the cost of being robust adversarial attacks within rates. (.(-)) The adversarial loss class:
(a( = { (3I1...,,.))+ Iz)
max o A)(xi)...... max(C,, o ge o A)(x))) E goo) AEA
AEA
Rare (f, A) The adversarial risk for the source tasks.
Rere (f A) = 1 E
(a.))>
max(ly oooho MEA
Rear (Jo, It, A) The adversarial risk for the target task.
max o ho A)(r)
Rear (fo. A) = B(e,))
AEA
(2, Z)
The covering number of Q scale w.r.t. the empirical ||-1|p on Z.
R(Q8P. 8p Z)
The data-dependent Rademacher width of 0p for Z (2)) jelpl,emm ie..
p.p-g
भR Q Op Z) Eois.
Σ
Jisk (2s (21))
sup 75000
up 1.,,=1
where 2 Z and o... are i...d Rademacher random variables.
16

---

vcx (Q,E)
The fat-shatteiing dimension of Q at scale with points from X.
(e(e) The inflated dataset w.r.t. attacks A, sample S, and scale e. See Section 2.
fj The ground truth predictor for task j.
8 The loss function & IR x y + R. We also use the notation Lz(z) = ((x, v).
L()) The non-adversarial loss class:
((0 == ( ma) - ((ey, o (a))) (c o (z) 1 Q*))
A The function class containing the attack functions that are maps from &' X.
A An attack function A X X' in A.
h* The common representation for all tasks
L L1 = -,L.F
Ly The Lipschitz constant for the predictors F. U Fo w.r.t. ||-||: a positive LF such that [f(z)) - f(2) S -=||21 22ll for all 21, 22 E Dom(f) and f E FUFo
Le The Lipschitz constant for the loss function é: positive Le such that 16 (v1.1))) v) ly(v2. f) s Telyn 3/2 for all y1, E y E
Ix The Lipschitz constant for the representations H w.r.t. the norms (II-Il II:I]): a positive Li such that [[b(2)) h(22)ll s Lx]l21 22l1a for all 21, 22 E Dom h) and h H.
L2 L2 = LyLn
La La = L
H. The smoothness constant for a smooth loss: a positive H such that (1, y) - Ey (122 v) s
Hly1 - y/2 for all 3/1 3/2 E R. y V
The dimension of the embedding space, i.e., the dimension of the image of the representations.
H The representations class that consists of functions from Rdd to R*
F A hypothesis class consisting of functions from X' to V.
Fo A hypothesis class for the target task consisting of functions from X' to V.
The dimension of the space from which the data is drawn.
X The input space, i.e., X' C Rdd
y The label space, i.e., y C
6 The bound on the loss function: a positive 6 such that (e(y', g)1 < so for all o/ ERyey
F The cartesian product of F for times.
t The number of source tasks.
The number of samples drawn for each source task.
m The number of samples drawn for the target task.
A A remark about attack functions
While Assumption 4.B not made several works on adversarial robustness the linear setting [4, 13], it is made in at least one other work [25, p. 3]. It seems that the literature has yet to formally made a distinction between these two settings. Therefore, we would like to make a few short remarks about how Assumption 4.B is natural and mild.
First, in practice, X' is frequently known. Therefore, if one seeks to protect against adversarial tacks, protections can be put in place for inputs that are not in Y. Thus, since the adversary wants to avoid detection, it is reasonable for an adversary to only perturb within the input domain. Second, many attacks in the empirical literature naturally fall into this category, e.g., a sticker placed on stop sign. In addition, for image classification with as the space of images, the famous examples of images [35] that have been slightly perturbed by definition fall into this category. Also, a key difficulty of being robust adversarial attacks is caused by the curse of dimensionality. Specifi cally, in classification, this manifests in the distance from any point to the decision boundary being
17

---

exceedingly small. This is also true under Assumption 4.B. Finally, in practice, it is common to preprocess the input before passing it to the model, e.g., subtracting the mean, removing outliers, dividing by the standard deviation, and clipping. So, it is a reasonable assumption that the input to the model, adversarial or not, will often be within the same space.
B
Technical comparisons to prior work
B.1 Comparison to [13]
To our knowledge, the first work to study adversarial attacks in the MTRL regime is [13]. Although we both consider MTRL, there are several differences; they consider classification with represen- tation functions that are orthonormal matrices and the predictors as linear maps, II- attacks, a spectral condition to relate the tasks similar to [15, 36], the loss function (z, + (x), and uub-Gaussian generative model. Ignoring these differences, they show that the excess transfer risk decays as /k/m + / //kdd/nt. nt. In comparison, if we instantiate our function classes as they have, C(F) is (A) and (HH) is (dd)²) (see e.g., [37, p. 7J). Plugging these values into the expression from the asymptotic analysis of the Lipschitz loss, our rate is O ((Vdk// dk/nn + dk /nl + k//m). We observe vd and v gap between the source tasks and target task rate, respectively, compared to their rate. We believe the additional /dk/n term in our rate is an artifact of using the Gaussian chain rule [37].
B.2 Comparison to [25]
Ignoring our MTRL results, the paper most similar to our own is [25], which does a substantial analysis of adversarial attacks in the multi-class setting. Like in Appendix B.3, we must be careful due to different assumptions. In particular, our results hold for subtly different attack model. Let us define their notation for illustrative purposes. They define an attack as A X x + X where B is the "noise class." They require that 5 + ((,(A(z, 6)), v) is L-Lipschitz for ||- and, similar to our own assumption, the existence of a cover of B. Yet, unlike Lemma 4.4 of [25]. we do not require the Lipschitz assumption. Consequently, our analogous lemma, Lemma 1, applies to attack models for which theirs does not. As an example, define an attack A(x, 5) to be r
otherwise + 8/ [|01| where B = {6 [|ó]|2 < 1} The attack is not continuous and, therefore, not Lipschitz. So the Lipschitz assumption 5 + {(f(A(x, 6)), y) does not hold for non-trivial losses and predictors.
Ignoring these differences, they state their main generalization bound as, with probability at least 1 1-8 8 over the training data S, for all f F.
log(2/8)
In {(
24
ViogN'nn CaaaNonGnan, E 5)5) de)
Radv()) ( - Radv(s) S 3/
+ inf 8a +
2n
050
where
Gadr = ((f((())((((((()))) () and S (m. [n], e Co(e/2L)
Their work then proceeds to bound this integral under additional assumptions like instantiating F to be specific model or making parametric assumptions. In comparison, we bound the above integral by Equation (2). We believe this new bound provides new insights into the cost of being adversarially robust that were not clear before because of the additional assumptions made for the analysis. In particular, our work shows that under mild assumptions, for a large attack model, the dimensional dependence attributed to the attack is Ö(vd).
Now let us make comparison of our optimistic rate Theorem 6.8 in [25], which is also an optimistic rate. Their work introduces robust version of the self seff-bounding Lipschitz loss [30], of which a smooth loss is special case. They bound the local Rademacher complexity of this loss class by sub-root function (see Lemma 6.6) under the assumption that N No (C(F), e SA(/2TL)) < Ro, s² for e E [b,, bz] and that Ro, does not depend on m. However, due to this parametric assump- tion, it is unclear what the worst-case dimensional dependence one has to pay before instantiating
18

---

model and attack. In comparison, our approach does not require such assumptions, and we can now state that, in our setting, the worst-case dimensional dependence due to the adversary is O(vd).
B.3 Comparison to [44]
Our work is not strictly comparable to [44] due to making different assumptions. They consider linear predictors and ||-Il perturbation attacks, i.e., A {x + x + |10 S }. This can imply that if E X' it not necessarily true that A(x) X for some A E A which violates Assumption 4.B. Ignoring this important difference, we instantiate FF to be - -bouddd linear
predictors and X' to be I1-ll--boumm -bunded, where q are Hölder-conjugates. Note Equation (2) has dimensionality dependence O(Vä) because, after applying Talagrand's contraction inequality, (C(F), n) has at most logarithmic dimensionality dependence for p or = 2, In contrast, they have dimensional dependence of d'-/4, So, ignoring logs, we match their bound when p 2, and our bound is worse by vdl when p 1. Further, these two bounds behave differently function the perturbation distance. We have a logarithmic dependence in A, whereas they have linear dependence.
C Lemmas
In this section, we list several lemmas from prior work that we use in our proofs. Lemma 4 (Lemma A.3. in [34]). For any hypothesis class F, any sample size n and any [9]] (F, n) we have that
(Fx 4n (m,
E2
Lemma' 5 (Lemma B.1 in [34)). For any H-smooth nonnegative function f R + RR and any tr have that
(J(L) f(r))² < (H((L) + ((
Lemma 6 (Lemma A.I. [34]). For any function class F containing functions f ::X' + and
S (Z), ). we have that
sup VerA
NoggN((Fe,,))
R(F n) S inf a20
4a + 10
de
a
n
D Vector-valued fat-shattering dimension digression
To our knowledge, the literature has not yet defined a notion of fat-shattering dimension suitable for vector-valued classes. In this section, extend the fat-shattering dimension [2] vectur-valued
functions. Let 2 = {q= = .gi......4h . be a class vector valued functions and = (a)) (1.n,) ( be points in the domain of the coordinates of Q, where ny are positive integers. We say that 5 is
(1.))((11))
y-shattered by Q if there exists reals ry for j E [t] and E [ny] such that for all 6 E {0, E| E, "
there is q E @ such that
(xt) 13 7 if and 91, (xt) S - if 0. Let vcx((, (Q,r) be the cardinality of the largest set r-shattered. Indeed, the authors proved foundational lemmas of the form found in [2. 3] in an effort to show The-
orem before realizing the lifting argument. In fact, note that vcx( Q, 7) = vcxx [ ? where the left is the vector-valued fat-shattering dimension and the right is the real-valued fat-shattering dimension with Q being defined as in the proof of Theorem 3.
This definition has several immediate desirable constructionist properties. Let F be a real-valued function class whose domain is X.
19

---

1. If (F, d. then vc,r ( ?) td: use the same sample that shattered the real- valued function class times.
2. If is vector valued function class and v2x(2,7) d. the function class restricted to one coordinate has fat-shattering dimension [d/t] by the pigeonhole principle.
Although suitable for multi-task learning, the class of functions defined above is strict subset of classes defined for multi-output prediction [30]. The fat-shattering dimension is a special case, i.e., one-dimensional, of the combinatorial dimension. the multi-output setting, we conjecture that the more general notion of combinatorial dimension is the correct characterization.
E
Proofs
E.1 Proofs in Section 3
Here give some proofs not provided in the main body of the paper.
Theorem 1. Let h and fo be the learned representation and target predictor, as described Algo- rithm 1. Under Assumption I and that gr is (v, E, A.) over Fo w.E.. h", then, with probability at least - 28, we have that Reat { h A) - Rrar (S h" A) is bounded by
n) 8by log log//////00/// (22////n/=////) sup (CF o m) (og(((0) m-te. (2/
beH
The proof proceeds exactly as the main generalization bound within in [37, pp. 12-14), we note that the adversarial attack does not change that the assumption that the loss is bounded and Lipschitz. Therefore, two assumptions prevent us from applying this result directly. First, we use (v. E, diversity instead of (v, e)-dierrsity Second, we use the two-stage adversarial training ERM instead of the non-adversarial two-stage ERM. If we follow the same structure of the proof in the non- adversarial setting, these differences are of no consequence. Indeed, if we apply the traditional risk decomposition, utilize the definition of ERMs, use symmetrization on both the source tasks and target task, and, finally, apply the diversity assumption to connect the source tasks the target tasks, this completes the proof.
Theorem 2. Under the setting of Theorem along with Assumption 3, Assumption 4, La)//////l (eeeb//emmm))
et, vex(C(F HH) Bib), (Cx(F(FF H), (2b) 2 1. then the Rademacher complexities R(C)(F)(H))) m) and (FF o h), in Theorem I are, respectively, bounded by
, (PP(CC(F(H))) (2 nt, nt, 3:) and 2 sup [C] o ht), m m, m.), (1)
keH
where L3 LLLFLH, L1 LLLF, and C, c are absolute constants.
Proof of Theorem 2. Given Theorem all that remains is to bound adversarial Rademacher com- plexity the source tasks and target task. We will bound the Rademacher complexity for the target task. The proof for the source tasks complexity is similar, but we do not push forward the geometry of the attack into the embedding space, i.c., for the source tasks, we must only invoke Theorem 3.
Recall by Assumption 3.B we have that H is (II II-II) Lipschitz. Also, by Assumption 4.A, A(x) is totally bounded for all x E X' w.n. II-IIA- Lipschitz functions are uniformly contin- uous, and uniformly continuous functions preserve the property of being totally bounded. So, o A(x) is totally bounded for all E X w.n. ||-I]. Observe that maxsem Ri(A hi), m) maxxeи St(LnaAFoo) m), i.e., we can take the perspective that h A is the attack func- tion class. Now, we apply Theorem with H containing only the identity and = 1, have maxneи Di( PR(ChaA(Fo) m) < SuueRR RFF((FF o h), m) Li, 32). The Rademacher complexity still a function of h because the worst-case Rademacher complexity is in terms of the image of h on X.
Theorem 3. Under the setting of Theorem 2. ((LA(FF)()))))) is bounded by
2 Ri (F((C(()))))) (H)), m) La, nt, B1), where L3 = LLLFLH.
20

---

R(C2((),, and R(C(F = ci(c(O ()) S), where T E [t] and $ = ()...)...... (zf, 1)...., (ee' ....... (zt t)} 2 = 38) A= 1 A(x)IA AJ. and Sx(+) = SA(+).
Proof. We observe that (
TT, IT= foh (S)(F((()))))
We consider the new lifted component of S immutable. That it does not change when tak- ing worst-case Rademacher complexity. We have reduced our problem to the standard single-task setting, and we can apply our result below Theorem 7, which gives the result.
Theorem 4. Let i and fo be the learned representation and target predictor, as described Algo- rithm 1. Let 1/1 and the be sub-root functions such that (i(rr 2 ( l)), and (2(r) 2 bsupnen (Fo o h ) m) with rī and r2 the the fixed points of (r) and (r)) respec- rively. Under Assumption 2 and that f is (v, E, A)-diverss over Fo w.r.t. h", then, with probability at least 2e-8, we have that Rear (o,
Rear
(fō: Rear(f
AA),))))AA)))))) is bounded by.
bd 9
ri
17165
21967ri
Rear ho, A))
219
m
m
26
( v R h A),
6V bd
r b
10266 217rg b
nt +
146v
The remarks made after Theorem are equally applicable here. That is, the proof proceeds exactly as the main generalization bound within in [39. pp. 32-34], because the adversarial loss does not impact the argument. Besides the usual risk decomposition and symmetrization, the additional step is showing a result analogous to Theorem 12 in [39]. Yct, the proof of this theorem is first applying Bernstein inequality, then doing routine computations, this too goes through. Therefore, routine argument shows the above result.
E.2 Proofs in Section 4.1
In this section we give proofs not in the main text of the paper.
F.2.1 Structural Results
In this section, we give some of our structural results foundational to our analysis of both Lipschitz losses and smooth nonnegative losses. The following two lemmas are essentially the complete and generalized argument given in Proof Sketch 5.
Lemma 7. Ler s(.) be a function from the reals to finite subsets of X such that if EI < E2 we have that (s(=2) [s(E))] Let e, K., X, p be positive reals and n positive integer. Under Assumption along with max max a22) S S No s( (ov/px)
ob 2 et and vex (CxF(F(F 2 1, then
log (C(F), pE, (+) & max
1
2
1
4Cen
R (F, n)2
CEP
2
log
4ee/
$
eb 4cv/ppx)
where
E1 = l/g log
(ovmpxx)
Ea
b/3/Cxp.
[F,.)
Q1
cEIP
02
cE20
and e, C' are absolute constants.
21

---

Proof. We first apply Lemma 2. That is, for & >
we have
bls(5) pevex pevex(C(()) (C(F), cEpE)
((())
s
Lo (C(F), (C pE, s (2) S (Vcx( log
logs
vex(C(F)) cEp)
We will ensure that this expression is well defined by enforcing bounds on various variables e.g. that the fat-shattering dimension is greater than one. Yet, assume for now that everything well behaved.
First, to bound A, to apply Lemma 4 we need that
(F) S cEPE
80, with some abuse notation, we will set
9 (FF .))
dEp
Now, applying Lemma 4, we have
A 4n (I n)2(
cE
Now bound B, we want to bound these log factors by function that constant in e and a. We use that, by Khintchine's inequality, >
eb Ao/REp"
Using this inequality and since a S and |s(E)| - |s(#] = |s levispx (1 and
vex (cF() S vcx(f(F), we can simplify the log factors, which implies
44v/E s (saviiSp))
is (Anrette))
B < log
log
evcx([(F),, CE
vC (C(F), cEpp))
Combining both of these arguments gives
(Ac//n|s (Arv((e)))
|s 1s ((cooiises)) (C(F) cEpR)
log No (C(F),pE, (E(F) pe, (7) S CAn)))((,,))
cEpe log (vcx(((F)),
logs
Let EM = arg max max.e (E vex (C(F) cEpk) 2 13.
Let { = 1/ log log s JevMpA) )
Note that s devnnx))
eb
is sufficiently large by assumption for this
expression be well defined.
Case #1 Suppose & E EM). Using this value for the expression we derived above we have that
(Ac/nEil
18 Jav/ pk
(C(F), log ao pE, s (A))
log
log
ctipe
(Vcx([(F),
Focusing on the log factors again, we can use that ει E (0, Evrl to simplify with
Log.Noo (C(F), pe, (f)) S C4npp)((FF n)²
eb (Avyns) )) log
eb ((((aeyeB)))))
cE log
22

---

Furthermore, since & S we can simplify further,
log AovTt 8 (eevisipx) log ((<(TeV(SiIN)))) s log 40v 8
( eb
(<evm(z)) log ((((nevio)))
Finally,
eb logst ((((eevne)))
=
shows that
log.Noc 00 (C(F), (e, pe, (+) S (Cen)p)((F,n))
2
[ee/ (ewmpx)) ))
8 ( eb
log
csipE
e
Case #2 Suppose & (M.CM) Recall that vcx (FFF), b,8) 2 1. This implies that & b//cpp. (0, EM). Also by monotonicity of fat-shattering dimension we have that {2 < & 1. This implies that we can make the same argument as we made for the first case with the slight modification that
log ((((Ee)))))
eb
which doesn't t change the final result.
Taking the maximum over both the cases shows that
No (C(F), pE, | (()) max
1 1 ? E
ACen
(F,
log
44c//]
8 { D
(
eb
CEP
The next theorem uses the comparison inequality given in Lemma 7 inside Dudley's integral along various observations about the quantities involved to bound the desired integral.
Lemma (A Dudley's integral computation). Ler s(-) be a function from the reals finite subsets of X such that if E < E2 we have that (s(E2) [s(E1).. Let K. X, be positive reals and n positive integer. Under Assumption along with s( devmpx
2 E and vex (C(F. Bb) 2 1, then
10 In /-" Vlog (C(F)) pe, (5)) de
inf a>0
4a
is bounded by [R) m) (ogglog
eb
exp)
(
4
VeC
4cv/n eb
(16c:pman) ))
+
20
cp / loo
log
36
cp
ebb
where c, C are absolute constants.
Proof of Lemma 8, Starting with
4a + (oR
Vn 1/d
10
(C(()))))))))) pe,
x (57) de
Focusing the integrand, apply Lemma 7.
( 1
1
VeC [)](F,n)
log 4cvn eb Acvmpp))
[ de
4 max {a) 20max oE(01:0g)
m))
max
5
32
cp
23

---

where 1 and 02 come from the dependence that the lower bound on the integral has from either & or &2 respectively. If we replace the maximum with the summation and evaluate the integral then have shown the result.
1
veC
4ovn
4cv/pp// (oo)ppx))
))
n²
4(01 + az) + 20
+
[F
m))
log
log
51
E2
cp
0r
where 01
c$iP
02
p9 (F.m)
ctap
Therefore the above is equal to
1)
4
VeC
AevT
eb 4cv/npx)
Eo [D m)
(F, m)
20
cp V
joog
log
51
32
cp
Now the fact that inequality,
1/ log log
eb 4nv/ppr)
and
E1 S 1 and b3/nc and Khintchine's
[F) n) loglogs ( eb
4cvrppd ) +
cxp)
(
vec
4cv/n
4cv/ix ))
eb
16c:3pm
+ 20
/ log
log
36
cp
cp
e²b
E.2.2 Lipschitz Losses
The proof below is inspired by Lemma 4.4. in [25].
Lemma 1. Let F be Li-Lisschitz w.r.t |1-11 Under Assumption 1, and Assumption 4, we have No (C s, 8) < No SA. (())) where L1 LLLF.
Proof of Lemma I. First note that for generic f E F and A, E A that the following chain of inequalities holds:
max max ( o fo A) (cr A. (it
kE(ni
AEA
max iE(n) AEA
(ey 0 A)))x²))
(6rofo Ai)
max max <E[n] AEA
Az')) o
o
(x)
foy o A.) (a+) Ai)
(o
A, (x²)
max max *E|n] AEA
where in the last inequality added and subtracted (g.. o f A, ) (x*) then applied triangle inequality. Applying Lipschitzness of o we can bound the first term:
max max (Lyr of A)()t) of (o)) aE/n] AEA
< max max L1 A(x²) A,(xt) |al #E|n| AEA
24

---

Now fix >> 0. Now let Ca(E/2L1) be cover of A at scale e/2L1 w.r.t. ||-1, and our sample S. Let A be in the cover above and e/2L, close the attack x²,
Li A(x') A((x)) Iaa 2
max max <E(n] AEA
Now construct o1-1loo cover of L(F) at radius e/2 on the image of all CA(e/2L1) on S. Call this set S. 2
which constructs "inflated sample". Now pick the to be e/2 close to f on our inflated sample. Therefore, by definition, we have,
max max 7EIn AEAl (eo+ fo
fo Ai) o A. (x)) $ E
So the Equation (4) upper bounded by E.
Therefore we have shown appropriate cover of L(F) on the specified larger sample is a cover of our adversarial loss class. More formally,
() ( 2T,1 )
which shows the result.
Theorem 7. Let F be Lipisschiizz w.r.t 1.11AA: Under Assumption 1, Assumption 4, (Saeeb/Ao/7LL)) 2 e", vcx(C(F), 1, then (CA((F),
8) is bounded by
2 (C(F), m) ,1,
(2)
where L1 = LELF and C, are absolute constants.
Proof of Theorem 7. Applying Lemma and Lemma shows the following.
10
((L)(F),S) < 4a: + VlogN2(Ca(FF.ees)) de
Vn
10
S 4a +
de
Vn
< 4a +
10
S"
/
log.N>
((F), E SA
2 .
E de
(5)
Vn
(2L
Now using Lemma with = 1/2 and Equation (5) is bounded by
2L, and = and s(-) = SA(+), we have that
2 (C(F))
lous log SA Acc/nT. -2) (2
cb 1
{
VeC
[4c/n] n
SA Acc/nl,n) )
( log
eb
8c5n
40
log
28
6
,,,,,,
E.2.3 Smooth and nonnegative losses
Lemma 3. Let F be class of predictors and let F lr be all functions in F. with empirical ad- versarial risk less than r on S. If 1, is - w.r. I1-I1 then under Assumption and Assumption 4, we have (2 s) No (F, (F,e/2/12Hr,5, SA
25

---

Proof of Lemma 3. First note that for generie f f F Ir and A E A by applying Lemma 5, that the following chain of inequalities holds:
max (eooooo os A)(a') - -(g)))((( d.) (o)) AEA
1
A) - (en of (ot)
max AEA
12
$ 6H
Σ max
n
(11)) + ( A. (z1) A (f
o
())*)) - (fo A.) ((t))) (
n
AEA
I 6H max max iE(n] AEA (foA)(zz)) - (f
A:) (x'))
21
Σ
(())))o))(())+ (lst fo (4: fo
max+ AEA
n
<6H max max (Jo (oo -(oo Ao (0))) )
Σ
max
{ (5o
1
1 n of
(e(n] AEA
n
1-1 AEd
< 12HHr max max ((x)) - (i
((oAA)(ot)) (fooi)))(oooieeee
2
iE|m] AEA
So, taking the square root of both sides,
2
max Cor A) max (bg: o ff fo
(6)
AEA
AEd
S
/12Hr max max iE(n| AEA
(f ()(a)) - (fo 1s) (a*))
Now by triangle inequality and Lipschitzness of F lr,
max max *E|n] AEA (f o A)(x' - (a')
[[0oA)(0)) (1))))()) + (fO (a') - (Fo4))
max max iE|n] AEA
[1o - A.)
(1o (00))
(1ro - -(j (io co) }
S max max :E|n] AEA
+ +max iE(1)
{11 ( (x+)) A - (fo
< LF max max 1E|n) AEAl
A(x') - A,(00)/ + max
iE(m)
Fix E > O. Let Cet 12Hr) be a cover of A at scale 22//22//122 w.r.t Il- Let C be with all Ca(E/2LeV/2HHr) being included in the cover at seale
cover of F o e/2v12Hr w.r.t. S and 11
Pick each A, E Cc(e/2L= such that
L maxa max A(x') A(x')-A(()))) Se/2v12Hr eE|n] NEAl
and, with A, fixed, pick fo Ả E C such that
{ A.) -(foo))))-((Foo)aa
} S < 12HT.
max 16 mz
26

---

Therefore maxie(n] maxAEa (fo (fo A)(x') - at scale e, so
-o (fo s 5 So C covers Lx(F 1+)
N2(CA(F 1)),,)) SNo F. 2212HT SA (2112HLL
Theorem 8. Under the setting of Lemma 3 along with (5(ee//cc/TLz)) 2 e and vex((F,83) 2 then have A(L S)) is bounded by /12H (F, (24HH)--1/2 T, n, 3). where C, e are absolute constants.
Proof. Let Eas arg max { vex F, cvb
2V12H 2 21
Applying Lemma 6 and Lemma we have
Vn L VlogNN((A((F) 8, S)
10
R(CA(F 1), < 4a
$ 4a + Vn / (
10 yvbr
SA Nog [F, "2112HT" 2LLV12HT )) de
Now using Lemma 8, which our general bound of this type of integral, we have with p 1/2v12H and A = 2L=v12HH and x vor and 8(-) = S-()), the integral bounded by
v V12H (J,
log log SA
eb
c
+ 40
VeC
log
4cc/
SA dovnLF ))
deve log 22/22
16c3n
4Cv/nL/
82/12HT
V12H (A) M)A
(24H6)) 1/2 1,,,,11,,,,,,,,, B).
27

---

F
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our theorems are in the setting of adversarially robust transfer learning and the asymptotic rates given in the introduction directly follow from our theorems (as ex- plained the main body).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Our theorem statements are clearly qualified with the assumptions and algo- rithm they use. When our assumptions differ from prior work, we discuss this in detail in Appendix B.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairnsss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
28

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provide proofs for all our results. Due to considering Lipschitz and smooth nonnegative losses there are a few proofs that are trivially nearly identical, when this is the case we clearly indicate this and remark exactly what to modify,
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g., in the case of a large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all sub- reasonable avenue for reproducibility, which may depend
missions to provide on the nature the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case thors are welcome to describe the particular way they provide for reproducibiliiy. In the case of closed-source models, it may be that access to the model is limited in
29

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips..
public/guide Souiddes/CodeSumissiiiooo. ollccy for more details.
While we encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed reproduce the results. See the NeurlPS code and data submission guidelines (https:
//nips. wttpcccppppcccccccccccccc.cc...c ppblic//uideee /wwpudddeeeeeeuuuueeeeeeee Ctt///odeeeeeeieee wwsbbmmsssiiii..mmmimmmsssm onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Question:
Answer:
[NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
30

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources Question:
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics attps://neurii: Ceppblcc/Ethcsaaaitiii
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there is a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Ye]]
Justification:
See, in particular, the second paragraph in the introduction.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
31

---

Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
license, copyright information, and terms of use the pack- age should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
If assets are released,
32

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details the dataset/code/mmodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and screenshots, applicable, well as details about compensation (if any)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects. and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "CBjB3UXoOW", "reviewer": "Reviewer_evww", "summary": "This work studies the adversarially robust multi-task representation learning. They introduce the definition of robust $(\\nu, \\epsilon, \\mathcal{A})$-task diversity and the algorithm of two-stage adversarial MTRL. Using these, they show novel results on excess transfer risk for adversarial loss under mild conditions. The authors then present the proof sketches and compare the results with previous work in detail.", "questions": "1. Although the authors include a section to discuss the difference in results and techniques used in this work and prior works. It is still not clear whether there is a major difference between the **proof techniques** of your work and that of [26] since the results shown in these two works are similar. If so, what are the main differences and difficulties? \n\n2. In the definition of $\\mathcal{A}$, it looks like any function $A \\in \\mathcal{A}$ maps all inputs $\\mathcal{x}$ to $\\mathbb{x} + \\delta$ with the same $\\delta$. Does it correct? If so, it is a weaker version of the regular adversarial attack.", "limitations": "N/A.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. It is a valuable work to study adversarially robust multi-task representation learning. The notations, definitions, and assumptions are all clearly written, which makes it easy to understand.\n2. The algorithm 1 is reasonable in practice for me. the authors discuss the novel assumption to show that it is also reasonable. Most of the assumptions in this paper seem to be mild. \n3. The authors carefully discuss the differences of results shown in this work and related works. They also compare the techniques used in this work and previous works. It is clear to understand the contribution of this work.", "weaknesses": "1. The proofs shown in section F.1 are not clear. The authors do not show the formal proofs of these theoretical results.\n2. The authors introduce the definition of the vector-valued fat-shattering dimension, which is a generalization of the fat-shattering dimension, while it does not seem to appear in the theoretical results, which makes it confusing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback and appreciating our work.\n\n> The proofs shown in section F.1 are not clear. The authors do not show the formal proofs of these theoretical results.\n\nWe will revisit this section to improve the clarity and rigor. For Theorem 1 and Theorem 4, we were careful to identify exactly which modifications are required from the standard arguments within [38] or [40] to complete the proof. We will add these algebraic details to make a more cohesive document for completeness so the reader doesn't need to reference [38] and [40]. Additionally we will revisit the proofs of theorem 2 and theorem 3, whose work is entirely our own.\n\n> The authors introduce the definition of the vector-valued fat-shattering dimension, which is a generalization of the fat-shattering dimension, while it does not seem to appear in the theoretical results, which makes it confusing.\n\nYes, you are correct. The definition of vector-valued fat-shattering dimension in section ``Vector-valued fat-shattering dimension digression'' within the appendix is not used. However, while not essential for a complete document, we do believe that this digression is useful for understanding the utility and weaknesses of the lifting argument we use. In particular such a definition seems necessary to prove data dependent (i.e., not worse-case) bounds (see commentary after Proof Sketch 2). Indeed, we could have explained this better and we will add additional signaling to aid the reader towards this end per this discussion.\n\n\n> Although the authors include a section to discuss the difference in results and techniques used in this work and prior works. It is still not clear whether there is a major difference between the proof techniques of your work and that of [26] since the results shown in these two works are similar. If so, what are the main differences and difficulties?\n\n\nWhile we were heavily inspired by [26], we were interested if similar results hold in general. By studying their proof we noticed that the main roadblock towards our goal was after applying Dudley’s integral that the sample complexity within the covering number was itself a function of the variable of integration from Dudley’s integral. Standard arguments do not account for this complexity and it is unclear where to proceed from here to retain generality without getting at least a linear dependence on dimension. \n\nSo while we both start with volumetric arguments then use Dudley's integral, at this point we substantially diverge. On one hand, [26] instantiates the various function classes and attacks to proceed with their final bound by leveraging prior covering numbering arguments for the classes they instantiated. On the other hand, to remain function class and attack class agnostic (under our assumptions), we utilized several celebrated general comparison inequalities that are not featured [26]. This is primarily Lemma A.3. in [35] and the celebrated result in [32]. In addition, the simple application  of these inequalities does not give the final result as the various quantities must be treated carefully which we believe is shown by the relative complexity of the proof of Lemma 7. For additional commentary please review section C.2 Comparison to [26]. \n\n> In the definition of $ \\mathcal{A} $, it looks like any function $A \\in \\mathcal{A}$ maps all inputs $x$ to $x + \\delta$ with the same $\\delta$. Does it correct? If so, it is a weaker version of the regular adversarial attack.\n\nYes, your first sentence is correct, yet we emphasize that the attacker can pick a different $A$ for each data point, which allows for the generality to instantiate the regular adversarial attacks.   In fact, our adversarial attack formalization allows for significantly more general attacks, which we believe has value in our analysis. Besides regular additive attacks, one can also instantiate to spacial attacks (e.g. image rotations) or patch attacks.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XiDqqErHpq", "reviewer": "Reviewer_4GkJ", "summary": "The paper studies adversarially robust transfer learning, wherein, given labeled data on multiple (source) tasks, the goal is to train a model with small robust error on a previously unseen (target) task. The paper considers a multi-task representation learning (MTRL) setting, i.e., assuming that the source and target tasks admit a simple (linear) predictor on top of a shared representation (e.g., the final hidden layer of a deep neural network). The paper provides rates on the excess adversarial (transfer) risk for Lipschitz losses and smooth nonnegative losses. These rates show that learning a representation using adversarial training on diverse tasks helps protect against inference-time attacks in data-scarce environments.", "questions": "1.What's the experimential results of the proposed theory?\n2.In line 155, as for the proposed Two-stage adversarial MTRL, I have a question wonder whether it's better to optimize a two-stage optimization than one-stage optimization?\n3.Are Lipschitz losses and smooth nonnegative losses necessary for adversarial transfer?\n4.Are different datasets effect the results of adversarial transfer?\n5.Are the claim that representation derived from adversarial training assist in defending against adversaries on downstream tasks in different adversarial attacks?", "limitations": "It's better to verify the effectiveness of the proposed approach on realistic datasets.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper has good originality, quality, clarity, and of important significance.", "weaknesses": "No experiments are provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your insights and recognition of our work.\n\n> 1.What's the experimential results of the proposed theory?\n\nWe agree the paper would benefit from experiments, as many theory papers would. Although we do not have experimental results, we emphasize that our results are complete and stand on their own as a contribution to our understanding of adversarial robustness. We see our work as a theoretical first step in this direction and we foresee empirical work as future work.\n\n> 2.In line 155, as for the proposed Two-stage adversarial MTRL, I have a question wonder whether it's better to optimize a two-stage optimization than one-stage optimization?\n\nThat is an interesting question and a comparison between these two settings would be valuable. Your suggestion naturally allows the representation to be trained having seen the data, in theory providing a benefit, so we consider this a promising direction of future work. While the single-stage approach underscores the value of learning the representation, the two-stage approach would be akin to fine-tuning. \n\n> 3.Are Lipschitz losses and smooth nonnegative losses necessary for adversarial transfer?\n\nThis is an interesting question. We study Lipschitz losses and smooth nonnegative losses, e.g., hinge and squared loss, because many of the standard losses in the literature fall under these assumptions. It would be interesting to see if these conditions are also necessary. \n\n> 4.Are different datasets effect the results of adversarial transfer?\n\nIf we fix a target dataset, then different source datasets affect the task diversity assumption parameters $\\nu, \\varepsilon$ (assuming task diversity is satisfied).\n\n> 5.Are the claim that representation derived from adversarial training assist in defending against adversaries on downstream tasks in different adversarial attacks?\n\nOur theory applies to a wide variety of attack models. But, the threat model is known to the learner at the time of training. Otherwise, it is hard to say anything. Possibly, one can prove a no-free-lunch theorem to formalize it. \n\n> It's better to verify the effectiveness of the proposed approach on realistic datasets.\n\nWe agree and that may follow in future. But, currently it is a theoretical paper and complete on its own as are many related theory papers. There is hardly any space to discuss any empirical results in a meaningful way without seriously undermining the writing of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6G942amfPM", "reviewer": "Reviewer_g9e1", "summary": "This paper conducts theoretical studies on adversarially robust transfer learning, which is to learn a model with small robust error on a downstream (target) task from a model pretrained on multiple other (source) tasks. Considering the specific multi-task representation learning (MTRL) setting, this paper provides rates on the excess adversarial (transfer) risk for Lipschitz losses and smooth non-negative losses, showing that a representation derived from adversarial pretraining can assist in defending against adversaries on downstream tasks.", "questions": "1. What attacks are applicable to this work? $\\|\\cdot\\|_2$ attack, $\\|\\cdot\\|_1$ attack, or $\\|\\cdot\\| {\\\\infty}$ attack?\n1. What is $g, \\mathcal G$ in equation 2? (line 173)", "limitations": "Limitations are discussed in the paper. No potential negative societal impact is found.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1.  This paper theoretically shows bounds on the excess transfer risk for the adversarial loss class for both Lipschitz losses and smooth nonnegative losses, demonstrating the benefits of adversarial pretraining on source tasks for downstream tasks in transfer learning.", "weaknesses": "1. The proposed theoretical results are interesting, but empirical experiments are missing to support the presented theories, such as the benefits of adversarial pertaining to downstream tasks and that it takes fewer samples to learn a good predictor for downstream(target) tasks with adversarially robust representations learned from related source tasks,\n2. As the paper introduces some additional empirical assumptions, such as assumption 4 which requires adversarial attack functions to be bounded within the known input domain, some practical examples or empirical experiments will be helpful to justify it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful reading of our work.\n\n> The proposed theoretical results are interesting, but empirical experiments are missing to support the presented theories, such as the benefits of adversarial pertaining to downstream tasks and that it takes fewer samples to learn a good predictor for downstream(target) tasks with adversarially robust representations learned from related source tasks,\n\nWe agree the paper would benefit from experiments, as many theory papers would. Although we do not have experimental results, we emphasize that our results are complete and stand on their own as a contribution to our understanding of adversarial robustness. We see our work as a theoretical first step in this direction and we foresee empirical work as future work.\n\n> As the paper introduces some additional empirical assumptions, such as assumption 4 which requires adversarial attack functions to be bounded within the known input domain, some practical examples or empirical experiments will be helpful to justify it.\n\nIndeed, we agree this would aid the reader and we will add such concrete practical examples. Recall we do have one example on line 150,  $ \\mathcal{A}= \\\\{ x \\mapsto x + \\delta \\mid \\| \\delta \\|_\\infty \\leq 0.01, x + \\delta \\in \\mathcal{X} \\\\}  $  for additive \n$ \\| \\cdot \\|\\_\\infty $ attacks. Also, please review Section B for additional commentary on this assumption.\n\n> What attacks are applicable to this work? $\\| \\cdot \\|_2$ attack, $\\| \\cdot \\|_1 $ attack, or $  \\| \\cdot \\|\\_\\infty  $ attack?\n\nYes, our bound works for any finite additive $p$-norm perturbation ($p \\geq 1$) attack. In addition, our approach allows for attacks beyond the above, as we can extend to patch attacks or spatial attacks (e.g., image rotations). This generality we believe is a strength of our analysis.\n\n> What is in $g, \\mathcal{G}$ equation 2? (line 173)\n\nThis should be $q, \\mathcal{Q}$. Thank you for catching that typo.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aLNDiU7aCB", "reviewer": "Reviewer_6tUb", "summary": "In this study, the authors explore adversarial multi-task representation learning, where a predictor and feature extractor are trained on multiple source tasks with adversary and then another predictor following the feature extractor is trained on a target task with adversary. They provide bounds on the excess risk under mild assumptions, showing that these bounds decrease with larger training sample sizes for individual source tasks $n$, the total sample size of all source tasks $nt$, and the sample size of the target task $m$. These results suggest that large sample sizes and diverse source tasks contribute to robust learning in adversarial transfer learning. Additionally, the input and feature dimensions increase these bounds. The excess risk decreases more rapidly when using smooth and non-negative losses compared to Lipschitz losses from a sample size perspective. Furthermore, based on the multi-task results, the authors consider excess risk in a single-task setting.\n\nThe authors first derive Theorem 1 for Lipschitz loss and Theorem 4 for non-negative losses based on [38]. Rather than directly addressing the adversarial loss class, they consider the inflation of the sample space $S$ by an adversarial attack $A$, examining its coverage by balls and standard volume arguments. These results bound the Rademacher complexities of function classes in source and target tasks with adversary (Theorems 2 and 5).\n\nAdditionally, a new reduction method from a multi-task setting to a single-task setting (Theorem 3) may aid future work in both adversarial and non-adversarial settings.", "questions": "The authors assume each source task has a common sample size $n$. If each source task has a different sample size, which affects the first term of the bounds: the maximum or the average sample size?\n\nMinor comments:\n- In Lines 46 and 47, there is unnecessary space.\n- In the equation under Line 47, $\\nu$ and $\\epsilon$ are still not defined.\n- Eq. (2) (and (6) in the Appendix) misses $(x_1), \\ldots, (x_t)$. Additionally, $g \\in G$ should be $q \\in Q$.\n- Eq. (3) and Line 323 might not need $\\sup$.", "limitations": "The authors address the limitations of their assumptions in Appendix C.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The problem settings and assumptions regarding data distribution (Lines 140--145), function properties (Assumptions 1--4), and the fat-shattering dimension and size of the inflated dataset (Theorems 2 and 5) are mild. The derived results, such as the order in terms of sample size and input or representation dimensions, seem appropriate. The bounds are interpretable and offer important insights for adversarial transfer learning: diverse source tasks and sample sizes facilitate robust transfer learning.\n\nMany prior studies emphasize the importance of sample complexity in adversarial training. However, obtaining sufficient training samples for a target task is not always feasible. This study theoretically provides valuable guidance for such situations from the perspective of transfer learning.\n\nMoreover, the derived upper bounds have the same order (growth rate concerning dimensions and sample sizes) as prior work on the non-adversarial setting [38]. This indicates that even in adversarial training, it is sufficient to prepare training samples similarly to standard training, ignoring constant and logarithmic terms, which is a positive outcome for the community.", "weaknesses": "One might (easily) predict this result from [38]. Under Assumption 4, the sample complexity of the perturbed dataset can be regarded as the finitely scaled sample complexity of the original dataset (as the authors exploited this concept). From the perspective of covering number and Dudley's integral, this leads only to logarithmic differences in orders. It might not be very difficult to conclude that the same order controls the bounds of the excess risk even in adversarial transfer learning as in standard transfer learning. Nonetheless, I acknowledge the authors' effort in providing a formal proof, even if the results are predictable.\n\nThe looseness of the bound is also a weakness, though it is a natural property of Rademacher complexity-based bounds. For example, the bound in Theorem 1 includes two worst-case Rademacher complexities $\\hat{R}(\\ldots, n)$ and $\\hat{R}(\\ldots, m)$, and $\\sup_h R(\\ldots)$ (the worst-case in terms of the hypothesis class of representation). This looseness may be due to the mild assumptions. Tighter bounds for more restrictive cases might enhance the interpretability of the derived bounds.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are thankful for your thoughtful comments on our work.\n\n> One might (easily) predict this result from [38]. Under Assumption 4, the sample complexity of the perturbed dataset can be regarded as the finitely scaled sample complexity of the original dataset (as the authors exploited this concept). From the perspective of covering number and Dudley's integral, this leads only to logarithmic differences in orders. It might not be very difficult to conclude that the same order controls the bounds of the excess risk even in adversarial transfer learning as in standard transfer learning. Nonetheless, I acknowledge the authors' effort in providing a formal proof, even if the results are predictable.\n\n\nWe initially had the same thought as this is the reasoning that is often the case in the non-adversarial setting. However, in our setting we found that these logarithmic dependencies are of supreme importance. Recall that the data is inflated to a sample size exponential in the dimension. Therefore, the order of the logarithmic dependence is of great importance.\nIndeed, if one naively uses the standard argument, e.g. in [35], the order of the logarithm is too large and therefore you get at least linear dependence in dimension once all factors are accounted for. We actually spent several weeks at first working on that idea. This is the very reason we leverage the deep theory provided by Rudelson and Vershynin, as it provides minimal logarithmic dependence, and perform the careful analysis in the proof of Lemma 7.\n\n> The authors assume each source task has a common sample size $n$. If each source task has a different sample size, which affects the first term of the bounds: the maximum or the average sample size?\n\nThe analysis can be readily extended to this setting with the final bound featuring the minimum of the sample sizes.\n\n\n> * In Lines 46 and 47, there is unnecessary space.\n> * In the equation under Line 47, $\\nu$ and $\\epsilon$ are still not defined.\n> * Eq. (2) (and (6) in the Appendix) misses $(x_1), \\ldots, (x_t)$. Additionally, $g \\in G$ should be $q \\in Q$. \n> * Eq. (3) and Line 323 might not need $\\sup$.\n\n\nThank you for your careful reading of the text. We will fix those typos and the missing definition.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: A good theoretical work on multi-task representation learning. All the reviewers agree to accept it. Congratulations!
Decision: Accept (poster)