Optimistic Rates for Multi-Task Representation Learning
Authors: Austin Watkins
Enayat Ullah
Thanh Nguyen-Tang
Raman Arora
Venue: NeurIPS 2023 poster (2023)
Keywords: Learning Theory
Multi-task and Transfer Learning
Classification
TL;DR: We show excess bounds for multi-task representation learning that are fast under near-realizability.

Abstract: We study the problem of transfer learning via Multi-Task Representation Learning (MTRL), wherein multiple source tasks are used to learn a good common representation, and a predictor is trained on top of it for the target task. Under standard regularity assumptions on the loss function and task diversity, we provide new statistical rates on the excess risk of the target task, which demonstrate the benefit of representation learning. Importantly, our rates are optimistic, i.e., they interpolate between the standard $O(m^{-1/2})$ rate and the fast $O(m^{-1})$ rate, depending on the difficulty of the learning task, where $m$ is the number of samples for the target task. Besides the main result, we make several new contributions, including giving optimistic rates for excess risk of source tasks (multi-task learning (MTL)), a local Rademacher complexity theorem for MTRL and MTL, as well as a chain rule for local Rademacher complexity for composite predictor classes.

Optimistic Rates for Multi-Task Representation Learning
Austin Watkins Johns Hopkins University Baltimore, MD 21218 awatki290jhr edu
Enayat Ullah Johns Hopkins University Baltimore, MD 21218 enayat@ edu
Thanh Nguyen- -ang Johns Hopkins University Baltimore, MD 21218 nguyent@cs: j edu
Raman Arora Johns Hopkins University Baltimore, MD 21218 arora@cs. .eraacs.jhu.. jhu. edu
Abstract
We study the problem of transfer learning via Multi-Task Representation Learning (MTRL), wherein multiple source tasks are used to learn a good common repre- sentation, and predictor trained on top of it for the target task. Under standard regularity assumptions on the loss function and task diversity, we provide new sta- tistical rates on the excess risk of the target task, which demonstrate the benefit of representation learning. Importantly, our rates are optimistic, i.e., they interpolate between the standard Om -1/2) rate and the fast O(m O(m-1) rate, depending on the difficulty of the learning task, where is the number of samples for the target task. Besides the main result, we make several new contributions, including giving optimistic rates for excess risk of source tasks (Multi-Tase Learning (MTL)), a local Rademacher complexity theorem for MTRL and MTL, as well as a chain rule for local Rademacher complexity for composite predictor classes.
Introduction
Transfer learning has emerged powerful tool in modern machine learning. The goal is to find good predictor on a given targer task with little data, by extracting knowledge from source task(s). The source tasks either be explicitly given (supervised learning), constructed from domain knowledge (unsuperviseddieffssueevviie learning). An example the supervised learning approach widely successful practice in deep learning, wherein complex model is first trained task with plentiful data, then applied to target task by extracting representations of data by freezing the last layer of the complex model, and training a simple (linear) classifier top of it [Bengio et al., 2013, Donahue et al., 2014]. Similarly, the unsupervised approaches of training a (large) neural network on general objective has seen tremendous success, especially natural language processing [Brown et al., 2020, Devlin et al., 2019] and computer vision. As before, a simple linear classifier trained on the output of the penultimate layer works well on target task.
source
Representation learning, where the goal is to learn representations of data that are useful across multiple domains and tasks, is common theme in the examples above. We study popular formalization of this type of machine learning called Multi-Task Representation Learning (MTRL). As the name suggests, We seek to effectively pool the nš data points to extract a common good representation useful for the target task. Therefore, if our tasks sufficiently "diverse"" we hope effectively circumvent our data scarcity by sharing knowledge between tasks. As by-product, since the shared representation
are given source tasks each with a small number of data points, say n.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

can also be used for the source tasks themselves, this procedure is also effective for the related problem of multi-task learning (MTL).
To study the transfer of knowledge via representations within the MTRL framework, we consider a composite-leanning model. This model consists of F and H. class of hypotheses and represen- tations respectively, where the final end-to-end predictors are given via the composition f o h, for all f E F, H. Since we must decide between compositions, we use two-stage empirical risk minimization procedure. First, the multi-task representation learning stage, the procedure selects one common representation and predictors, one for each task, by minimizing the average empirical loss on the source tasks. Second, the transfer learning stage, the procedure selects predictor for the target task that minimizes the empirical loss, w.r.t. m samples, on top of the fixed representation from stage one.
We desire to learn good predictor i.e., one that has small excess risk from F H. for the target task. In this work, we consider the class H to be complex (e.g., deep neural networks), whereas the class F consists of simple functions (e.g.. linear predictors). Therefore, the class F a H. is complex, so directly learning it would require a large number of samples. Yet, if we can effectively pool all our data from each task, the total number of examples could be sufficiently plentiful to successfully learn a complex representation. Further, a good representation can significantly reduce the statistical burden of learning a good predictor for the target task. This phenomenon formalized by the prior work of Tripuraneni et al. [2020]. which is the work most related to ours. Specifically, they show that if the loss function is Lipschitz and the tasks are sufficiently diverse (see Definition 2), the excess (transfer) risk for the target task is bounded as,
Excess transfer risk = =Ō (v
C(H) + +I((F nt
C(F)
m
where C(H) and C(F) denote the complexity measures associated with learning H. and F respec- tively (precise definition to follow in a later section).
While the above rate has the desirable properties described above, it is insufficient on many fronts, which our work seeks address. First, it is akin the standard rate of n n-122, albeit optimal in agnostic settings, for single-task PAC learning. However, it is well-known that a fast rate is achievable under realizability in the standard supervised learning. But, the above guarantee does not capture this possibility. Importantly, the work of Tripuraneni et al. [2020] operates under the assumption that the loss function is Lipschitz- in such settings, it generally not possible to get fast rates, despite realizability, even for the special case of learning half-spaces [Srebro et al., 2010]. In the single task setting, the literature contains rich theory of guarantees that interpolate between the slow and fast rate depending on the level of realizability, such guarantees are called "optimistic rates". We derive such optimistic rates for MTRL. Consequently, as an important application of our general theory, we show that the (transfer) risk of the MTRL approach on the target task is bounded as,
δ Linnge + (Lisser
V Liuure (C(H) + IC(F)) +
Furger Lurerr C(F) + C(H) + +I(F) + C(F) m
L
(I)
nt
m
ru
when using non-negative smooth losses (such as squared loss in linear regression or smoothed ramp loss for classification [Cortes et al., 2021, Srebro et al., 2010].. The values Lsoure and L Liager represent the minimum average risk over the source tasks and target task respectively, hence (1) yields a fast rate under mild realizability, i.e. when they small.
In the course of proving the above, we extend a number of foundational results in the single-task setting to the multi-task setting. We list them in our contributions below.
1. We give general local Rademacher complexity result for transfer learning via multitask represen- tation learning - see Theorem 1.
2. We also provide local Rademacher complexity result for multitask learning see Theorem 3. Our result has two benefits compared prior work [Yousefi et al., 2018). First, we perform MTL via MTRL that leads to improved bounds which show the benefit of pooling data as opposed to learning each task separately. Second, we operate under the special, yet fairly natural setting, of hypothesis classes with product-space structure this simplifies the proof significantly as well as recovers the result for single-task setting with the exact same constants (unlike rates in Yousefi et al. [2018]).
2

---

3. For non-negative smooth losses, we derive optimistic rates (such as Eqn. (1)) for transfer learning and MTL via MTRL. Notably, when we restrict our rates to the single task setting, our proof is significantly simpler and our obtained bound on local Rademacher complexity is smaller compared to the prior work of Srebro et al. [2010].
4. Finally, we present a chain rule for local Rademacher complexity for composite settings, which allows us to decouple the (local) complexities of representation and predictor classes.
1.1 Our techniques
In this section, we expand on our contributions and provide an overview of techniques and challenges overcome in the context of prior art.
Local Rademacher complexity for transfer learning via MTRL. We build on the work of Tripura- neni et al. [2020], which introduced the notion of task diversity. They showed that task diversity leads to improved rates on excess transfer risk via MTRL, compared to training only on the target task. Their work however yields the standard ((m rate on excess risk, akin to what is obtained in agnostic settings. We provide a local Rademacher complexity result for transfer learning via MTRL, yielding optimistie rates depending on distributional properties. Our methods are based on tools and techniques from the seminal local Rademacher complexity paper of Bartlett et al. [2005]] A crucial component of our results is relative deviation Bennett concentration inequalities established via log-Sobolev inequalities together with the entropy method [Bousquet, 2002]. We make the crucial observation that the above concentration inequalities, though established for the single-task setting, are general enough to be used to extend the local Rademacher complexity framework to the multi-task and transfer learning setting.
Local Rademacher complexity for multi-task learning via MTRL. Intermediate to our above contribution, we provide a local Rademacher complexity result for MTL via MTRL, yielding optimistic rates. We note that the prior work of Yousefi et al. [2018] already provided a local Rademacher complexity result for MTL, though not via MTRL; importantly, our work establishes the benefits of pooling data compared to learning each task separately. However, in contrast to Yousefi et al. [2018]', our setting is limited to hypothesis classes with product space structure rather than a general vector-valued hypothesis. This simply means that the tasks are permutation-inve invarrinnt in our setting, which we argue is a fairly reasonable assumption in the multi-task context. This assumption makes the analysis much simpler as we can reuse concentration inequalities for single task setting whereas Yousefi et al. [2018] had to extend log-Sobolev concentration inequalities to the multi-task setting. Additionally, this yields bounds with better constants than Yousefi et al. [2018] - in the special case of a single task, this recovers the known result with the exact same constants.
Optimistic rates for non-negative smooth losses. An important application of our theorems is providing optimistic rates when using non-negative smooth losses, which is known enable distribution-Fi free optimistic rates in a single task setting [Cortes et al., 2021, Srebro et al., 2010]. This result shows the provable benefits of representation learning. Further, it can be combined with the chain rule for Gaussian complexity of Tripuraneni et al. [2020]. This allows us to separate the composite class F H into the complexities of representation class H and predictor class F and also reuse existing complexity bounds in the literature. While we borrow some of the tools for optimistic rates theory in the single task setting from Srebro et al. [2010], the prior proof technique does not directly extend to the multi-task setting. Consequently, we modify the proof, simplifying it significantly as well as getting an improved bound, even in the single task setting. In particular, Srebro et al. [2010] bounds the local Rademacher complexity of the loss class by an Ez-covering number via Dudley's entropy integral formula, which is then bound by -ooerrin number of hypothesis class using smoothness, which in turn is bound by the fat-shattering dimension, which eventually is bound by the (global) Rademacher complexity of the hypothesis class. Some of the steps seemingly do not generalize in the multi-task setting because there are no (well-studied) multi-task analogues, e.g. the fat-shattering dimension. Our proof starts with the above bound on the local Rademacher complexity of the loss class by an fg-coerrigg number via Dudley's entropy integral formula but then applies the well-known Sudakov minoration incquality that yields a bound in terms of Gaussian width; this is in turn bound by Rademacher complexity by standard known relations between the two quantities.
Chain rule for local Rademacher complexities. In the application to non-negative smooth losses, the local Rademacher complexity of the loss class is bounded by non-trivial function of the
Yousefi et al. [2018] additionally considers Bernstein classes, which we do not. However, we think that our results can be extended to that setting.
3

---

(global) Gaussian complexity of the hypothesis class which is further bounded using the chain rule of Tripuraneni al. [2020]. For general loss functions, there may not be any such non-trivial function. To this end, for Lipschitz losses, we develop chain rule of local Rademacher complexity, Theorem 5, that similarly allows separating the local complexities of the representation and predictor class.
1.2 Related work
As mentioned before, our work is most related to, and builds on, Tripuraneni et al. [2020]. Other related work includes an early work of Baxter [2000] that gives guarantees on excess risk of transfer learning and multi-task learning via MTRL under a certain generative model for tasks. This was subsequently improved by Maurer et al. [2016], Pontil and Maurer [2013]. These early works give rates of the form O (t-1/2 + m m-12)) and do not capture the advantage of having a large number of source samples per task. Prior work has extensively studied the special case of linear representations and/or linear predictors, partly in the context of meta learning, for instance see Du et al. [2021], J, Tripuraneni et al. [2021], ], Xu and Tewari [2021]. Further, multitask learning has been explored under various notions of task relatedness BaviD and Borbely, 2008, Cavallanti et al., 2010].
Regarding optimistic rates, the seminal work of Vapnik and Cervonenkis [1971] provided the first optimistic rates, via a normalized uniform convergence analysis. but was limited to the PAC learning setting. Much later, a line of work of Bousquet et al. [2002], Koltchinskii and Panchenko [2000] derived optimistic rates in more general settings using the technique of localization. In this area, an important result is the local Rademacher complexity theorem of Bartlett al. [2005], which many works have leveraged to yield improved rates for various problems [Blanchard et al., 2007, Cortes al., 2013, Ullah et al., 2018J. Importantly, this theorem applies learning with non-negative smooth losses [Srebro et al., 2010] where the local Rademacher complexity-basee technique can be used give distribution- free optimistic rates. Further, optimistic rates have seen renewed interest owing to the interpolation/beniig overfitting phenomenon in deep learning. In certain problems, predictors may interpolate the data (zero training error), yet have small risk. A line of work [Zhou et al., 2020, 2021] shows that in certain linear regression problems, optimistic rates can be used to derive risk bounds that explain the phenomenon, where the usual tool of uniform convergence provably fails.
There has been some work on optimistic rates in the multi-task setting. The work of Yousefi et al. [2018] established a local Rademacher complexity theorem for multi-task learning (see Section "Our techniques" for detailed comparison). Besides that, the work of Reeve and Kaban [2020] proved optimistic rates for vector-valued hypothesis classes for self-bounding loss functions (which includes non-negative smooth losses).
Notation. Denote ||-1|2 be the Euclidean norm and I| be the infinity norm. We use the convention that [m]] = [1...., , .m] is the list of contiguous integers starting at 1 and ending at m. For f = (fi...,, fe) let f = -JJ f() and denote
Pf = E Pyls = B(, P : = p7
(X:).
2 Problem setup and preliminaries
Let X' C Rd and ) C IR denote the input feature space and the output label space respectively. The source tasks and the target task are represented using probability distributions (P3) and Po. respectively. Let F and Fo be a class of predictor functions from R& to y for the source tasks and target task respectively, and H a class of representation functions from I2d to R*
al. [2020], we assume that marginal distribution of P, over X' is the same for all the j from 0 to f, and that there exists a common representation h² E H and task-specific predictors f E F for E [t] and fo E Fo such that P, can be decomposed as P, y) P. (x) hh*())) Note that this decomposition does not assume that fj h is the optimal in-class predictor; however, we will assume it is to make our optimistic rates more meaningful (although this is not strictly necessary). Also the decomposition implicitly assumes that y depends on only via f (x)) and thus any additional noise in y is independent of ær Note that like Tripuraneni et al. [2020], we allow the predictor class for the target task Fo to be different than on the source tasks F. For example, when performing logistic regression with a linear representation
Following Tripuraneni

---

B E R and linear predictor E R we have Put 11f3 o = oww" BTx), (w"BBx)) the sigmoid function.
where
Given loss function é Rxy R, the goal is find good predictor foh from the composite-class Fo o H with small transfer risk,
Runger h) i ((..)) (((fo h(x),
Yet, standard, do not have access the joint distribution for all tasks, but instead independent and identically distributed (i.i.d.) samples from each source task and m i..d. samples for the target task. Let (x)) ut) be the ?th sample for the 1th task. To accomplish the above, we use the source data to find a representation, and the target data to find predictor for the target task. Specifically, in this MTRL procedure, first, train on all source task data, then freeze the resulting representation. Second, we train over this frozen representation to find good predictor on the target samples.
We formalize the above the following two-stage Empirical Risk Minimization (ERM) procedure,
(f,
h) arg min
ELfs o (Ugoh(z)).. h())).
(Multi-task (representation) learning)
TEFSEHEER nt j=
1 Σ lf 362))..6). feFo m
fo E arg min
(Transfer learning)
Besides bounding the transfer risk, we seek to understand the above procedure also yields improved bounds for the source tasks (the problem of MTL).
R (F,
Σ j=1
E (n.) pl(ff h(x).v) v))
We make the following regularity assumptions. Assumption 1.
A: The loss function l is nonnegative and b-bounded, i.e., S (ly',)) s < co for all y' y E e.
B: All functions in F are L-Lipschitz,fo for some O < L < 0o w.r.. 11-12, ie., [[((z]) f(z2)ll2 5
L || f2r all 21, 22 E ffm(f) and f E
C: Any fo E F o H is D-bounded over X w.r.t || lloc, iee, supaex If o h(x) S < 8 for all f F and h E H.
Unlike Tripuraneni al. [2020], we assume for some of our theorems that our function is smooth instead of Lipschitz, as leveraging smoothness is key to achieving fast rates [Srebro et al., 2010].
Definition 1 (H -mosooohhesss). The loss function f E (11, y) e, (32. v) < (y1 y2l for all y1, V2 E R. E V.
R x y
R is H H-smooth if
Task diversity [Tripuraneni et al., 2020J. We benefit from learning representation for new target task, so long as there must be information encoded for that task by the source tasks. A typical way to quantify this encoded information is to control the difference between the learned representation and the underlying representation. To this end, we use the framework introduced by Tripurameni et al. [2020] that quantifies measure of task diversity. As mentioned in their work, this framework recovers task diversity assumptions in Du et al. [2021] exactly. In our setting, the definitions given in Tripuraneni al. [2020] simplify considerably.
Definition 2. The tasks (P, ) are (v, e)-diverse over Pq. for the corresponding f E F Fo and representation h² H. have that for all hi' E
Rianger (f', hh') (f ho), < Peeo
inf
1
inf f'E
Rysunce (f', h1') Ruource (f" (1)))))))))))))))) +
Parameters and quantify the similarity between learning the source tasks and the target task. For a detailed analysis of these parameters and the framework introduced by Tripuraneni al. [2020], see Appendix B.
5

---

Local Rademacher Complexity. We now define the measures of complexity that are used in our work. Let u. p,n E N, an input space Z, class of vector-valued functions Q + R", and dataset (2)))e()) where zj E Define the data data- deela-deendentt Rademacher width, Rz(-), as
P.P.u
Rz Q ( Eo,,,
o.j (g: (=3))
sup O
TEP
where J.i. are i.d. Rademacher random variables. Analogously, define the depe-denendnnt Gaussian width, (z(-),
1 n.p.u Σ s.j.k=1
Óz(2%P) E S.sss
Digi (z))))
sup gEQ
TIP
where Diji are i.i.d. (N 1) random variables. We define the worst-case Rademacher width as Rr (Q su Rz @))) and, analogously, the worst-case Gaussian width as G, (QSP) 2 (z(@ep) (QP).. The above definitions generalize the standard Rademacher and Gaussian width for real-valued functions and can be derived as special case of the more general set-based definitions [Wainwright, 2019] (see Appendix A).
We now define local Rademacher width Rz (Q r) Rz (fq E Q V(q) S Er}), where V - R. That is, the local Rademacher width is simply the Rademacher width restricted by functional. In our applications, where b is the uniform bound the range of q in fo-nomm Note this recovers the classical local Rademacher width for real-valued functions and non von-product spaces (p = u = 1). We are mostly interested in the local Rademacher width of the loss applied the pairwise composition between our vector-valued hypothesis class and our representation class. Specifically, if we define such a class as Ce(F (H)) = {(E o fi o h fc h) h E H. F then we seek to bound Rt (JF (H)), r). Crucially, our bound will be a sub-root function in r, where we define this type of function below.
consider any V satisfying V(q) s b b1 Em (2)))) up
Definition 3 (Sub-root Function). A function vb [0, oo) - o0) is sub-root if it is nonnegative, nondecreasing, and if + v)(r)/ fr nonincreasing for > O.
Sub-root functions have the desirable properties of always being continuous and having unique fixed point, i.c., r" = <((")) ) is only satisfied by some r"; see Lemma 8 in Appendix A.
3 Main Results
In this section, we detail our local Rademacher complexity results for transfer learning (TL) and MTL via MTRL, a bound on the local Rademacher complexity of smooth bounded non-negative losses, and the application this bound to both TL and MTRL.
Our first result is a local Rademacher complexity result for TL via MTRL.
Theorem 1. Let h and fo be the learned representation and target predictor, described in Eqns. (2) and (3). Under Assumption LA,, if f is (v. divverse over Fu w.F.t h" and let 1/1 and the be sub-root functions such that ti (r) 2 (I, o Fet o H.r) and v/2(r) 2 Rm (6 Fo,r), then with probability at least 4e the transfer learning risk is upper-bounded by
(Viharsee (fonee/ff,, (1)
(V
b6
b5
Riareer Fo, fo, h)) s Ri h²) + ci
+
m
b
m
b
-
02 Rooucce (f" 1ot)
(Vb0 nt.
r2
b8
r
(4)
b
nf
where ri and rã are the fixed points of th (r) and (hr(r), respectively, and cı and og absolute constants."
Bartlett et al. [2005] uses "complexity", but we use "width", as common stochastic processes. For exact constants for each term, please refer to Appendix D.

---

Inequality (4) bounds the transfer risk in terms of task diversity parameters v and e; local Rademacher complexity parameters, fixed points ri and rf; the minimum risk for the target task; and the minimum average risk for the source tasks.
As discussed in Xu and Tewari [2021]. there exist settings where the task diversity parameters and e are favorable, i.c., 6 = O and V = (1), so we will disregard them in the subsequent discussion. The bound is an optimistic rate because it interpolates between vri + vrz and rí + r depending on both Rearget (Jō h²)) and Rsource (h"
The fixed point ri is a function of F (H) and encodes its complexity measured with respect to the number of samples for the source tasks (among other class-specific parameters). The same reasoning holds for 2 w.r.t. Fo.
We consider H to be complex and both F and Fg to be simple. So, if we instead learned the target task directly, then we would pay the complexity of (F( against m samples. In contrast, in our bound, we only pay the complexity of Fo for m samples and the complexity of F (H) for nt samples. Since in many settings nt is much larger than m, we are successfully leveraging our representation to learn the target task.
FH)(H)
The dependence on minimum risk is useful in various settings. An instructive regime is when nt >> m with Rtarget (fö h²) = and Rsource (1" > O; in this case, we achieve a bound of vrī + rz. This demonstrates that data-abundant environments can be leveraged to learn representations that work well in small sample regimes.
The next result uses a decoupling of function classes, the Gaussian chain rule of Tripuraneni et al. [2020], and smoothness to bound rī and rz. We see that under this additional assumption that & H H-smooth, rī and rž decay quickly.
Theorem 2. Under the setting of Theorem I along with being H smooth and Assumptions 1.B and 1.C, with probability at least 6 the fixed points in Inequality (4),
b )
r S czb
H6 (Fo log (1 +
and
m
3 S c c/ (1 (7)) (,,(F) H log(nt)* +
D2 Hoglog (nt) + b(1 + 5)
nt
where 0 and c4 are absolute constants.
Remark 1. Note that in Theorem 2 it is not necessary to apply the chain rule. If the chain rule is not used, Assumptions 1.B and I.C is not needed. The fixed point 12 would be bounded as a function of FSH(HH) In the following, we use the above decomposed form for interpretability.
Note that for constant L, D, H. b, and 6, the terms on the right are always fast, the rate of decay depends crucially on the behavior of the Gaussian widths for each class. For many function classes
used in machine learning, it is common that G,t s / ntt
C(F) where C(-) is some notion of complexity of the function class, which could be, for instance, the VC dimension, pseudo-dimension, fat- shattert dimension, etc. Therefore, it is common that
/C(H) and (F) R
6 nt (H) + (F) se 2 C(H) + C(F) and (2 h) C(Fo)
ne
Recall, from our discussion following Theorem 1, that these fixed points control the order of the rate. Therefore, this theorem interpolates between rate of 1/ 1/Vm 1/Vnt and 1/m + 1/nt, where the fast rate is achieved in a realizable setting.
Linear classes. As an example let us consider a linear projection onto lower dimensional space along with linear regressors and squared loss. Let X = Rdd y = IR and
F ( (2) a z, a R
||| S <c),
H [h| h(x) B x, Rdxk B is matrix with orthonormal columns }
If we assume that P,, is sub- Gaussian then standard arguments (see Tripuraneni et al. [2020]) show that 2 (Fo 1.) < 0 k). 62 (F) < O kb and (2, (H) < O O(Ed) To simplify the bounds let I= 1, H 1, D 1, b 1, and 0.05. Thus, under the assumptions of Theorem 2, the fixed
points are bounded by
7

---

+ 1 m
k22d
k
1
ri ~
and ri x
+
m
nit.
nh
nt.
which gives
k
Rurgel (fo, h)
Reargel ((: 2
Reargee Chargee(JO::1 (1)
V
+
(
k2d
ko d
m)
+
|Roource (f .h²)
+ 11
+
nt
nt
The following result is such a bound on the local Rademacher complexity for a non-negative H- smooth loss and any function class H.
Proposition (Smooth non-negative local Rademacher complexity bound). Under the setting of Theorem I along with E being H H-smooth and Assumptions I.B and I.C, there exists absolute constants C2 and C4 such that
Rea (H)). ( VH log(n)² + DVH log(n)
+ Vn)
(5)
vn
ni
log (IFF((H)) + ) = I& (H) + (F) and IT = v /HG (F (H))
evb
(6)
where
G(FE(H))
cD
When we specialize the above bound to the standard single-task non-compositional setting and compare with Srebro al. [2010], then
eVb Bn(FV
Ri (C (F)
evb
< RF log (n) log
Rr (F)
H log (n)
eb
Sd (F) Hr log (n) log
H log n B
The second inequality uses the relation 6 (F) 2 log(n)
[Wainwright, 2019, p. 155] and that x. r~ x log eC/z /x is increasing in x until x = C. The third inequality uses Khintchine's 's inequality,
(F) 2 vBB where B is the bound on the range of F. Thus, the upper bound above is always
better than the bound in Srebro et al. [2010]* for large enough Furthermore, under the additional though well-studied assumption that {(0) S B² [Arora et al., 2022, Shamir, 2015], ours is better for n ((1). Finally, the Gaussian and Rademacher widths are of the same order for the class of linear predictors, bounded in norm, by a strongly convex regularizer, general ouccuulidean settings. Hence, in this setting, our bound is smaller by factor of /log n. in Kakade et al. [2008] see Appendix E for a detailed comparison.
3.1 Multi-Tass Learning
Next, we detail some theorems foundational to the results above. For those results, we were able to link MTL with MTRL by using the task diversity assumption. Therefore, naturally have the following local Rademacher result for MTL.
Theorem 3. Let (F, h) be an empirical risk minimizer of Roource (:. as given in Eqn. (2). Under Assumption I.A, let Ap be a sub-root fianction such that vp(r) 2 R, (J (H),,) with r" the fixed point of (r), then with probability 1 1-26"
2e
Reouree ( do) < Rscurce (f", hh)) + o( Reoorce (f", (²,,
bd ni
b5
7
+
(7)
b
nt
where e is an absolute constant.
We note that Srebro et al. [2010] incur an additional /rb/n r term when converting from complexity to width
8

---

As above, we can use our bound on the local Rademacher complexity of a H-smooth loss class to get the following result. This result is similar to Srebro al. [2010], Theorem yet ours in an MTL via MTRL. setting.
Theorem 4. Under the setting of Theorem 3 along with being H-smooth and Assumptions 1.B and I.C, with probability at least 3e 3e of (()) is bounded by
cb (1))))))))
H log(nl)* D2 log(nt)² 6(1 + +0] nt
nt
where e is an absolute constant.
3.2 Local Rademacher complexity chain rule
Using the chain rule of Tripuraneni et al. [2021], as we did above, to decouple the complexities of the representation and prediction classes desirable. Yet. our general local Rademacher complexity Theorems I and 3, as stated, do not seem to have this property. Consequently, we develop a local chain rule, which aims separate the local complexities of learning the representation and predictor. The main result is the following.
Theorem 5, Suppose the loss function f is Li-Liscchitz Define the restricted representation and predictor classes follows,
Eo Fx = ( E fo 3h E H: V(eo fol ho) sr}
= ( 3f Est: V Sr),
where V is the functional in the local Rademacher complexity description. Under Assumptions 1.B and 1.C and that the worst-case Gaussian width of the above is bounded by the sub-root functions y and Uhe respectively, there exists absolute constant such that
(Ce (1),,)) sc (LLe)>>()) ((Le))))))))))) + (r)) log (nt)
D.
(nt)²)
4 Proof Techniques
In this section, we give details on some of the tools we use by giving proof sketches for the results in Section 3. In the next section, cover some theorems the root of all our results.
Proof sketch for Theorem 1. Let Jo arg min Runger (J, R1). By a risk decomposition, we can bound the excess transfer risk by Rusga(fo: h) Rurger (Fon fi) + sup inf pe Runged (f', hi) Ro, We can now use Theorem 3, with t = 1, to bound Reargs (fo, h). Note that Reager (fō. h) RurraaaFo h) I O. Now inf yEFF Rusgall h)) R h²) is less than (inf f'ejes Rsource (f', ( Rsource - (f", (f", by the task-diversity assumption. As shown in Tripu- (Rsouree (f", h) Raource (f"" (f", with Reource ( h). We can then apply Theorem to the remaining Rsmaree (f, f.) term. By leveraging task diversity again we can bound the remaining ( It) as function of (f h²).
raneni et al. [2020], we can bound inf f' (
Proof sketch for Proposition 1. We achieve the following bound on the local Rademacher com- plexity of the loss class by using truncated version of Dudley's integral [Srebro et al., 2010, see. Lemma A.3].
[" /br
{4a + 10(nt) 1/2 Riye (FOO oSagvbr
inf
v Na (H)),
(F r),
We observe that we can use smoothness to move the dependence on the loss to an appropriate scaling, which gives that (F(C (H)), r), nt) < ((FF(((H) e/10),e////111/ /12Hrrd nt) (Lemma 18 in the appendix). Next, we apply Sudakov minoration to bound the log covering number by the Gaussian
width of our function class: / (FF3 /1////22/ ni) < /12Hrnn 9 (F (H)). With these simplifications, the parameter a from Dudley's integral can either be solved for exactly (as in Inequality 6), so long as a S vbr, or set such a way that it always holds (like in Inequality 5). Finally, we can optionally apply the Gaussian chain rule from Tripuraneni et al. [2020] to bound G (FF0 (H) with LB,, (H) + (F).

---

Proof sketch for Theorem 2. The right hand side of Inequality 5 is sub-root function in r, because it is an affine transformation of vr. Therefore, we just solve for the fixed point of this sub-root function, i.e., solve for r" w.r.t. the equation below.
evr" (G VH log(n)² + DVH log(n) Vn
(8)
ml.
All that remains of the proof is basic algebraic simplifications. The proof for Inequality 6 similar.
Discussion
The proofs of the above results hinge on the following local Rademacher complexity result.
Theorem 6. Let F. be class of non-negative bounded functions. Assume that X] j............................j.. Xj are
draws from P3 for [t] and all nt samples are independent. Suppose that Var f) VV()) S
BPf, where V is a functional from F to R and B O.
Let be a sub-root root function with fixed point r" such that BR(FWM r) S ()(r) all r 2 r", then for K >> 1 and 8 > with probability at least
PM 200 + a)² K
Kr
BK8
1 1 bō
e F Pf
Pf-
+ nt
K K-
B 4
3 nt
Yousefi et al. [2018], Theorem 9, showed a result of this form in a more general setting of Bernstein classes and function class that is not necessarily product space. In contrast, for simplicity, do not consider Bernstein classes, though we believe such a generalization is possible, and our function classes are product spaces. By doing so, achieve better constants than Yousefi al. [2018] by using the next theorem.
Theorem 7 (Concentration with t functions). Let F be a class of functions from X R and assume that all functions f in F are Py-measurable for all j E [t]. square-integrable and satisfy Ef = 0. Let sup ess sup f S 1 and Z = supfers: Ej=1 Ei= fy(X)). Let a > O such that ²² 2 supserai EE Var [f)(x]) almost surely. Then, for all 5 2 0. we have that
5 3 se
PIZ < EZ + v 22 -EEZ) +
This result also holds for sup fEFst
Σ Σ fx(x) under the condition that sup
Il. S 1.
feF
Yousefi et al. [2018] also proves something similar to the above from scratch using 'Logarithmic Sobolev" incqualities. We make the observation that within our setting a proof similar to the original proof given by Bousquet [2002] still holds. To clarify this further, Yousefi al. [2018] state:
Note that the difference between the constants in (2) [Bousquet, 2002, Theorem 2.3] and (3) (Yousefi et al., 2018, Theorem 1] due to the fact that we were unable to directly apply Bousquet's version of Talagrand's 's inequality (like it was done in Bartlett et al. [2005] for scalar-valued functions) to the class of vector-valued functions.
We show that within the product space structure, which we consider to be the most natural for MTL, it is possible to achieve the same constants. Concretely, when t = 1, we realize the single function version of Bousquet [2002] exactly.
The proof of Theorem 6 is similar to the one given in Bartlett et al. [2005]. Sec. 3, and generalized to MTL by Yousefi al. [2018], Appendix B. Indeed, follow the same steps within these proofs but use our inequality above.
6 Conclusion
We provide the first optimistic rates for transfer learning and multi-task learning via multi-task representation learning. This is achieved by establishing local Rademacher complexity result for multi-task representation learning. We provide distribution-free optimistic rates for smooth non- negative losses by bounding the local Rademacher complexity for multi-task loss classes. Besides our contributions to multi-task representation learning and multi-task learning, our work provides several foundational results and improved rates the standard single-task setting. Directions for future work include: exploring adversarial robustness, active learning, and fine-tuning of the representation within multi-task representation learning.
10

---

Acknowledgements
This research was supported, in part, by DARPA GARD award HR001 12020004, NSF CAREER award IIS-1943251, funding from the Institute for Assured Autonomy (IAA) at JHU, and the Spring '2 workshop on "Learning and Games" the Simons Institute for the Theory of Computing.
References
Raman Arora, Raef Bassily, Cristóbal Guzmán, Michael Menart, and Enayat Ullah. Differentially private generalized linear models revisited. In Advances in Neural Information Processing Systems, volume 35, pages 22505-22517, 2022.
Peter I.. Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities. Annals of Statistics, 33: 13:1497-1537, 2005.
Jonathan Baxter. A model of inductive bias learning. Journal of artificial intelligence research, 12: 149-198, 2000.
Witold Bednorz and Rafat Latala. On the boundedness of bernoulli processes. Annals of Mathematics, 18063):1167-1203 2014.
Shai Ben-David and Reba Schuller Borbely. A notion of task relatedness yielding provable multiple- task learning guarantees. Machine learning, 73:273-287, 2008.
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE transactions pattern analysis and machine intelligence. 35(8):1798-1825 2013.
Gilles Blanchard, Olivier Bousquet, and Laurent Zwald. Statistical properties of kernel principal component analysis. Machine Learning, 66:259-299 2944, 2007.
Olivier Bousquet. A bennett concentration inequality and its application to suprema of empirical processes. Comptes Rendus Mathematique, 334(6):495-500, 2002.
Olivier Bousquet. Concentration inequalities for sub-additive functions using the entropy method. In Stochastic inequalities and applications, pages 213-247. Springer, 2003.
Olivier Bousquet, Vladimir Koltchinskii, and Dmitriy Panchenko. Some local measures of complexity of convex hulls and generalization bounds. In Computational Learning Theory: 15th Annual Conference on Computational Learning Theory, COLT 2002, pages 59-73. Springer, 2002.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Giovanni Cavallanti, Nicolo Cesa-Bianchi and Claudio Gentile. Linear algorithms for online multitask classification. The Journal of Machine Learning Research, 11:2901- 2010.
Corinna Cortes, Marius Kloft, and Mehryar Mohri. Learning kernels using local rademacher complexity. Advances in neural information processing systems, 26, 2013.
Corinna Cortes, Mehryar Mohri, and Ananda Theertha Suresh. Relative deviation margin bounds. In International Conference Machine Learning, pages 2122-2131. PMLR, 2021.
Giulia Denevi, Dimitris Stamos, Carlo Ciliberto, and Massimiliano Pontil. Online-within-onlin meta-learning Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, pages 13089-13099, 2019.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Iiainaallinngee Linguistics: Human Language Technologies, NAACL-HLD 2019, pages 4171-4186, 2019.

---

Jeff Donahue, Yangqing Jia, Oriol Vinyals, Judy Hoffman, Ning Zhang, Eric Tzeng, and Trevor Darrell. Decaf: deep convolutional activation feature for genenc visual recognition. In International conference on machine learning, pages 647-655. PMLR, 2014.
Simon Shaolei Du, Wei Hu, Sham M. Kakade, Jason D. Lee, and Qi Lei. Few-shot learning via learning the representation, provably. 9th International Conference on Learning Representations, ICLR 2021, 2021.
Sham M Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. Advances in neural information processing systems, 21, 2008
Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Adaptive gradient- based meta-learning methods. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural 2019.
Information Processing Systems 2019, NeurlPS 2019, pages
Vladimir Koltchinskii and Dmitriy Panchenko. Rademacher processes and bounding the risk of function learning. In High dimensional probability II, pages 443-457. Springer, 2000.
Michel Ledoux and Michel Talagrand. Probability in Banach Spuces: isoperimetry and processes, volume 23. Springer Science & Business Media, 1991.
Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes. The benefit of multitask representation learning. Journal of Machine Learning Research, 17(81):1-32, 2016.
Massimiliano Pontil and Andreas Maurer. Excess risk bounds for multitask learning with trace norm regularization. In Conference on Learning Theory, pages 55-76. PMLR, 2013.
Henry Reeve and Ata Kaban. Optimistic bounds for multi-output learning. In International Confer- ence on Machine Learning, pages 8030-8040. PMLR, 2020.
Ohad Shamir. The sample complexity of learning linear predictors with the squared loss. J. Mach. Learn. Res., 16:3475-3486, 2015.
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Optimistic rates for learning with a smooth loss. arXiv: Learning, 2010.
Nilesh Tripuraneni, Michael I. Jordan, and Chi Jin. On the theory of transfer learning: The importance of task diversity. Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 2020.
Nilesh Tripuraneni, Chi Jin, and Michael Jordan. Provable meta-learning of linear representations. In International Conference on Machine Learning, pages 10434-10443, PMLR, 2021.
Enayat Ullah, Poorya Mianjy, Teodor Vanislavov Marinov, and Raman Arora. Streaming kernel pea with ō( (T) random features. Advances in Neural Information Processing Systems, 31, 2018.
VN Vapnik and A Ya Cervonenkis. On uniform convergence of the frequencies of events their probabilities. Teor. Veroyatnost. i Primenen, 16(2):264-779, 1971.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science,
volume 47, Cambridge university press, 2018
Martin J. Wainwright. High-D Digennimmnsi Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
Ziping Xu and Ambuj Tewari. Representation learning beyond linear prediction functions. Advances in Neural Information Processing Systems, 34:4792 48044, 2021.
Niloofar Yousefi, Yunwen Lei, Marius Kloft, Mansooreh Mollaghasemi, and Georgios C. Anagnos- topoulos. Local rademacher bomplexity-based learning guarantees for multi-task learning. Journal of Machine Learning Research, 19(38):1-44 47, 2018.
Lijia Zhou, Danica J Sutherland, and Nati Srebro. On uniform convergence and low-norm interpola- tion learning. Advances in Neural Information Processing Systems, 33:6867-6877, 2020.
12

---

Lijia Zhou, Frederic Koehler, Danica J. Sutherland, and Nathan Srebro. Optimistic rates: A unifying
theory for interpolation learning and regularization in linear regression. CoRR, abss21112.04470 2021.
13

---

Appendices
Contents
Introduction
1.1 Our techniques
1.2 Related work
2 Problem setup and preliminaries
3.
Main Results
3.1 Multi-Task Learning
3.2 Local Rademacher complexity chain rule
4
Proof Techniques
5
Discussion
10
6
Conclusion
10
Appendices
14
Additional preliminaries on Gaussian processes and complexities
16
A.I Preliminaries
16
A.2 Sub-root functions and local Rademacher Complexity
19
Task diversity digression
19
C Technical Miscellanca
21
C.I Martingale Concentration Inequality
C.2 Empirical Process Lemmas
22
C.3 Analytic Inequalities
24
D Proof's of main results
25
D.1 Concentration Inequalities and Risk Bounds
................................
26
D.2 Multi-Task Learning
................................
32
D.3 Multi-Task Learning via Representation Learning
34
D.4 Empirical Local Rademacher Complexity Bound
Bo..............................
36
D.5 Theorems for transition from empirical to po..............................
39
D.6 Smooth Learning Bounds
40
D.7 Smooth MTL and MTL via MTRL
42
D.8 Local Rademacher complexity chain rule
42
E Detailed comparison with prior works
43
14

---

E.1
Comparison with Srebro et al. [2010]
43
E,2 Comparison with Denevi et al. [2019], Khodak et al. [2019]
45
15

---

A Additional preliminaries on Gaussian processes and complexities
A.1 Preliminaries
We recall basic preliminaries on (sub) Gaussian processes [Vershynin, 2018, Wainwright, 2019]. Given a set C R² random process is a collection random variables { defined on the same probability space, indexed by elements of set θ The random process induces the following canonical psuedometric on the (abstract) set θ defined as d(0, 0²) = || Zo ll -
V (Zo Zor> 8, (oseudo)metrivg the set T. This allows us to define the covering and packing number of the set θ with respect to the metric d, denoted as @ d, e) and MMO, d, e) respectively,
Definition 4 (Covering number). An c-cover of set θ with respect to a metric d, a set C C θ such that for any 0 θ there exists c C, such that d(0,c) c) The e-covering number, O(O,d, the cardinality of the smallest e-cover.
Definition 5 (Packing number). An e-packing of a set with respect to a metric d, a set P θ such that for all p. q P. p.P q. d(p, q) e. The e-packing number, MM@,, d, c) is the cardinality of the largest e-packing.
These are related follows. Lemma (Wainwright (2019]). For any totally-bounded sel O and > 0,
M(O,d,20) s (V(, M(
A well-studied problem is to control the process uniformly, E[supoee Zg] in terms of the geometric properties the set θ
random process is a Gaussian process, if for all finite sets O, S O, the distribution of the random vector {Zg) ) ee is Gaussian. A well-known result regarding controlling Elsupage Zo] is the Sudakov minoration inequality.
Lemma 2 (Sudakov minoration [Wainwright, 2019]). Let (Ze, 0 E θ} be a zero-mean Gaussian process. Then
E
sup Zo 6E88
2 sup a a20 2
v Tog M(O,d,)),
An important example is the so-called canonical Gaussian process, Zø (0. g), where g NN Ix) is the standard Normal vector. In this case, the canonical metric simply becomes the f2-norm, d(0, 0') |10 0'112- The uniform control of the random process becomes standard object, known as Gaussian width of the set O.
( E
sup Zo .a0e
E.
sup (g. 0) .
The celebrated Fernique-Talagrand theory of majorizing measures establishes characterization of the Gaussian width of a set in terms of its metric geometry see Vershynin [2018] for more details.
A related concept that of Gaussian complexity, where the goal is to control the process absolutely and uniformly, defined as,
(
= E
sup 22
/ = E,
sup Kg. 031 LETT
These two are related as follows.
Lemma (Vershynin [2018]). The following are true about the relationship between Gaussian width and complexity.
1. (()) < (()).
2. For any E O we have (8(0) -1001) s 50()) s (0(() )) + 1101).
16

---

An important category, generalizing Gaussian process, is that of uub-Gaussian processes, in which for all 0, 8' O the random variable Zy- Zg is (as.:"")suu-aaaai
E exp (A(Zo - Zg))² - exp
for all X.
The supremum of sub-Gaussian process is upper bound by Dudley's entropy integral formula, as follows.
Lemma 4 (Refined Dudley's entropy integral formula Wainwright [2019]). Let {Zolaees be zero-mean sub-Gaussian process indexed on set θ with diameter B, then
4a + 10 {" Vlog (0, (O,
Elsup Ze] S [8| sup Ze Zor S #E
inf 05a5B
0,8'
An important example of sub-Gaussian process is the so-called BernouliiRRademache process, where Za (a, f), where a E f-1,11", whose co-ordinates are i.i.d. Rademacher random variables. This leads to the notions of Rademacher width R()) and Rademacher complexity, R(O), defined as follows.
R()) E, sup (a, 0) LeEe
Ri(e) = E. sup (o. 03]
The Rademacher width and complexity are related in the same way as Gaussian width and complexity (akin to Lemma 3).
Lemma 5 (eershynnn [2018]). The following is true about the relationship between Rademacher width and complexity:
1. R(O) < R(O)
2. For any θ we have (oi(e) + +101) (()) 2 22 ( (101)+
Further, the Gaussian and Rademacher widths are related as follows. Lemma 6 (Wainwright [2019]). For set O C R
V 2 2 (0)) < ((0) < (2)()) Vog
Akin to the Feriique-Talggen Talagrand majorizing measures theory for Gaussian processes, complete characterization of the expected suprema for Bernouli/Rademacher processes terms of metric and co-ordinate geometry is obtained via (the now proved) Talagrand's Bernoulli conjecture Bednorz and Latala [2014] 4], Ledoux and Talagrand [1991].
Complexity of real-valued function classes. Relatedly, another well-studied concept is Gaus- sian/Rademacher width/complexity of a set of real-valued functions on a fixed set of inputs. We first define it and then argue how this is simply special case of the above "see" of these. Consider class of functions which map an abstract set Z to R. Given input Z consisting n points in the domain of g Q, the Gauusiaa/Rademachhon complexity and width of Q, on Z are defined follows.
Āz (Q) = E
sup 9EQ
(24)
Rz(() E
sup IEQ
1=1
1
Gz E
sup Q
(i:();)
(z E sup
gig(2s)
q
where o, and 9i are i.i.d. Rademacher and standard Normal random variables, respectively. The metric induced on set Q is the the L2 distance with respect to the empirical measure on input Z,
dz(g.4) = l1g d'l <'1121()
(a(z)) - -
17

---

The corresponding covering and packing numbers of Q are denoted as WN(2 Z) and M(Q. 2). To reduce the above from the set-definition, consider the set
( = 1 n
(((=1). ..... .(......)())))))))). :
In that case, Rz(2) ((2(Z)) Further, dz(a,0) vn d(0,, 07r) where 0g (((2)), ... ((=n)) and Og (1'( (z2),..... (=2),...; (2n)) and thus lie in ((Z).
(22)),
Complexity function classes in the multi-task learning setting. We now generalize the above to functions encountered in multi-task representation learning. For input space 2, P. 9. E N. consider a class of vector-valued functions Q - IR, and dataset = (tj)se where #3 E 2. For @ the p-fold Cartesian product of Q, we define its data-dependent Rademacher width, R-),), data-dependent Gaussian width, Gz (-), data-dependent Rademacher complexity, (.),)) data- cata-dependent Gaussian complexity, 6z, with respect to input Z as,
n.P-9
Rz (P = Eocsih
sup QEQRp np
Jayh (a:(23))
(Rademacher width)
1jk=1
n.P.y
(z(OSP) Eyis.
sup qE 2 np
Dhash (a)(2)))
(Gaussian width)
ij,k==
1 n.P.q
Rz( Eori.
sup 9e R
JOk (ar(2)))
(Rademacher complexity)
ni
i,jk=
n.P.g
(Z( E B
sup gEoe>
np Ils. (2)(2)))
(Gaussian complexity)
where Jij.k and Ji..k i..d. Rademacher and standard Normal random variables, respectively. To reduce the above from the set-based definition, consider the set
@ (((a(()))))))) : = Q
In the above, the notation 1 up (((a, (2)))))))))) denotes a vector in 1PP4 obtained via enumerating i.j
and k.
The corresponding metric analogously is,
dz(g,q') = =11q d'll = npp
(2g)(2))) (c: /npdz(0q." 0g)),
i.j.k
where 0g up (()) and similarly oy which lie in (Zr
The above can be used to define covering and packing numbers of Ø8r, denoted as ((O Z)
and M(Q@r, Z) respectively.
The concepts of Dudley's entropy integral formula and Sudakov minoration thus generalize accord- ingly. A result of the following form, for real-valued functions, appears in Srebro et al. [2010]. Lemma 7 (Refined Dudley's entropy integral). Consider class of vector-valued func- tions and imput set Z = jEb)eeM)) Define = suPge ||lll
vmpsup
(((((()))))) DE up
L
Then,
Blyap
Rz(FF S
inf OSa
4a + 10
v VlogN (QBP, P e, Zide
Ja
B
log (QRP, c, Z)
inf 0
4a + 10
de
np
The equality above follows from the change of variables.
18

---

inf Fee Worst-case complexities of functions. Often, we take the sup over datasets of specified size, in the above definitions of Rademacher/ Gaussian width/complexity, yielding their worst-case counterparts, denoted as,
6 6ap(2
sup B2(2 2E
8 6np(2 = sup 3z (z()))) P)),
ZE
Rap (
sup Rz (QSP), ZE
Rap (Q
sup Ri Q ZM
The corresponding metric similarly is
dnp(q.d')=
sup dz(q. q²): Zez"y
which can then be used to define covering and packing numbers of Ω denoted as ,,, mp) and M e, ni)), respectively.
As before, Dudley's entropy integral formula and Sudakov minoration generalize analogously.
A.2 Sub-root functions and local Rademacher Complexity
We present key property about sub-root functions from [Bartlett et al., 2005] below. Lemma 8 (Lemma 3.2. [Bartlett et al., 2005]). & [0. oc) 7 [0, 00) is a nontrivial sub-root function, then it is continuous [0, oc) and the equation vi(r) has unique positive solution. Moreover, if we denote the solution by r", then for all > 0,r 2 v/(r) if and only if Sr. r.
B Task diversity digression
In this section make series of observations regarding the task-diversity definition introduced by Tripuraneni et al. [2020]. Within this work, they introduce two definitions that are used to relate average source tasks performance target task performance: task-averaged representation difference and worst-case representation difference.
Definition 6 (The task-averaged representation difference w.r.h H).
1 Σ inf & j=1 PEF
d (1::h)
EajMyrP (E(S' o H (1z) u5) - e (Jz (
Importantly, like the work which introduces these concepts, it is possible to statistically control dr.f [h; hi*) where h results from the first step of the two-tage ERM procedure, see the variational definition Eqn. (2).
The other quantity they introduce is the worst-case representation difference. Definition (The worst-case representation difference w.n. h, h' E H).
db:) sup inf Eny-P E( o 1 (x). - E(So -(oo))))))))))))) M()..)) M.).))
JoeF PEF
Finally, they introduce the following assumption the two quantities defined above. It has multiplicative parameter and additive parameter e.
Definition 8 (1, et-tas diversity w.r.t h E H ('Tripuraneni al., 2020]). For a function class F, we say f E Fr is (v, e)-dieesse over Fo representation h, if uniformly for all h' E H.
d7.Fo (N': h) < dr,s hh';h) fvv + +
We will make series of observations about these quantities which provide substantial simplification our setting.
First, observe in the setting of product space,
dh:,(h':h))
[Rrouree (f', Rsouree (f,h)}
19

---

and
dy (h':))
sup inf (Rurgalf' h/) Reurea (fo, h)} foEFo J'EF
Note, here we are again leveraging product space structure to simplify prior work. Recall Section observed that this structure allows to recover existing single function theorems exactly, unlike Yousefi et al. [2018]. Specifically in the proof of Theorem we "commute" suprema and summations.
Here we are "commuting" infima and summations to simplify the framework specified in Tripuraneni al. [2020] within our setting. Note they work with product spaces but do not make the simplifying observation above. Nonetheless, the definitions they provide are suitable for the more general function classes considered in Yousefi et [2018], which are not necessarily product spaces.
Now consider the setting detailed in the preliminaries applied our approximation h, E and f" E F with the following ratio
SuP inf (Burzes (b) Rurges (Jo, h²)) dz.Fo (h: jr
inl ye RRuncce (S', ,i) Rusurce (f ( 100)
inf PEr Rearze (f', h)) inf FoETo Rearper (fo, h²) infgeroo Rsource (f', (i) Rsource (f" ,10²)) Per Pemgar (f', 1i) Rearger i hi)) inf i' Rssorce (f', ,h) Rsource (f ht))
(9)
Note every sup and inf will realize function that minimizes their respective risk.
This ratio a measure of how similar the performance we can expect when we use our representation learned from the source tasks to and apply it the target task. That is if we seek to control this quantity we do not care per se if the risks are small nor do we care that we are getting good performance in comparison to the ground truth, but how comparable is our performance between source and target.
We seek to control this ratio with some V
yee Ruarze (f', h) - Runger (Jū, inf g'r {
S V
Raource (f' h) Rsonce (f", ht))
If the risk source tasks and target task is similar w.r.t. to the ground truth for all tasks then # se 1. That is low (high) average risk on the source tasks leads to low (high) risk on the target task.
This is even more apparent in the realizable setting.
inf Per Rearga (f', ",, .h) inf ger Rsouce (f' ,h)
1
First, imagine setting in which there are several tasks and on all but few source tasks, we perform well.
re Rearge (f', fi) inf pere Rsoucee (f', f.)
relatively small
relatively big
Then 1. will be small, which is okay if do not care about performance across all tasks, as long as the target task performance good.
Alternatively, imagine that the task does relatively poorly on the target task but is still small. This desirable.
could lead very large I which ッ
inf Per Reagea (f', h)
relatively big
~
inf yr eer Rsouce (f', fi)
relatively small
20

---

Therefore we allow for an additive to capture this quantity when we get risk on the source task is very small, but we are okay with relatively poor performance on the target task.
That is we care about the following inequality
inf Rssonce (fou (f',h) .h. Rsource (f", (fthh))) te, (10) inf Rearge h) Rurgal Reargalo fō h*) 1/ f'E PEF
1
where encodes how much tolerance we have between the performance on the source tasks and the target task. Hence, is Inequality (10) which we care to control over all functions in H. Therefore. we will assume uniformly for all h' E H. that:
inf Rearge (S', h)) Riargel (So h-) S JEF
inf f'EFFI { Runurce (f', h)) R (f" (f,)h)) +
Although we observe this simplification, to be succinct we will still use that d (h:
inf Rurgall ( h) Reunge (fo;"") h²) f'eF
(11)
and
(h; inf frerse
(Bsunce (,, h) Ravarve hh,))
(12)
and use this notation in the proofs of Appendix D.3.
C Technical Miscellanea
In this section, we present technical miscellanea that we shall later refer to in obtaining our proofs of the main results in Appendix D.
C.1 Martingale Concentration Inequality
For the sake of notational succinctness, we forgo the compositional model by overloading the notation to just consider generic function class F : X' + R.
Lemma (Theorem 2.1 in Bousquet [2002]). Let Wi...., Wn, be independent random variables in Polish space W.
Let
A= A=o(W A=,,W...., W..)
Vk E [n] be a-ulgebras generuted by these rundom variables.
= oWW............. Wk-1. Wa+1.... Wn)
We denote by F2 [:] the expectation taken conditionally on Ag. Let ((()) = 2r)) + and vxx) =
1 x.
Let (Z, .i..., Zn,) be sequence of A-measurable random variables and let (Zn)ke(n) be sequence of random variables that are A& measurable, respectively. Assume that there exists u > such that for all [n) the following inequalities satisfied
2 5 Zμ < a.s., 16, [2 and Z% S u a.s.
Let a be a real number satisfying o² 2 - Es (Zz)² almost surely and let v
(1 + u) EZ) + no?. If the following condition holds
Σ k=1
7
Zt < Z a.s.
we obtain, for all A 2 0,
log E,
((Z=(()))
S w ((->)u;
which gives the following bounds for all O.
8
PIZ 2 EZ + 5) S exp -up -
and
P[Z 2 E
V2vō + // S -5
21

---

The following corollary is immediate as independence is sufficient Bousquet [2003] and we can express the summation over random variables "double summation" where we first sum over q E [n]] and then over E [t]-
Corollary (Lemma 9 in block structure). Assume that ...... W are n independent draws from P3 for j [$] with random variables some polish space, where all nt samples are independent.
Let A be the sigma algebra generated by je())e(().e)) and A be the sigma algebras generated by (Wj) vel)) We denote by Eg [-] the expectation taken conditionally on A% (1)))())))
Let Z be a A-measurable r.v. (2 (E(0 be sequence of A-measurable random variables, and (7i) [e() be sequence of random variables that A% measurable, respectively. Assume that there exists 0 such that for all lo E [t] and E [m]] the following inequalities are satisfied
27 S Z - Nx S a.s.,
(13)
Ex
2 2 0, 2 v u
(14)
and
a.s.
(15)
Let a R be real number satisfying
2% 27
N nl
E
(16)
q=1
almost surely and let v = (1 + u)] /
+ no²
If the following condition holds
Z 2 < Z a.s.,
(17)
==
we obtain, for all 2
log E
[2(2-E(21)
$ (
which gives the following bounds for all 8 O.
upp ( ) and P(Z E [
8 22vō +
P E 7 + 8) S exp
3 5e
C.2 Empirical Process Lemmas
The following result standard symmetrization.
Lemma 10. Let F be a class of functions from X to R and let X. denote the set of inputs {x}) ni Assume that all functions in F are Py-measurable for all j [6]. Then,
iz==1"
1 n EΣB(y)
E
sup fEr
- ΣΣ B(X))
S 20 (FR0))
VI
nt j=
j=
where { is sequence of nt independent Rademacher variables.
The result follows by standard symmetrization proof extended to the multi-function setting.
Proof. Let Xt...., Xy be independent copies of X X1..... ...... Xy probability space P3 for all [4]
Let Ex be the expectation with respect to X] ....:: X7 for all j E [t] and Ex be the expectation with respect to _....., for all it). Let of be i...d Rademacher random variables for all [t]
22

---

and i E [n). Fixing X x....., X3 for all j E [t], and using the copied variables we have that
E sup JEF
1 2 n nt i=
(x3)
E 1
ΣΣ fx(x))
Ttt
j=1
[(()) Ex 1 2
net ΣΣb03)
Ex sup JEFS
iml
By Jensen's inequality, we have
1 = -ΣΣ 5(x)
E ΣV ((33))
E sup feFS
n1
ml
j=1
== E1
S Ex x sup fEf
f((z) nt
ΣΣ :=
1588))
nt i=1
(1(8)))((33))
X sup JEF
nt
If X and X3 have the same distribution, we could exchange - for (xx)) and the equation would be equivalent. We can do this with Rademacher random variables, by randomly flipping the sign with probability 1/2. This yields the following
1 nl
EEEEOO ((()))
E sup JEFAI
BXX)
E
j=1
t=1
1 - E
ΣΣ (0)1((3))
nt x.X.8 sup Fe
ΣΣ (b(03))
<
nl. x sup Se
f=1
ΣΣ (05(()))) j=1==1
+ E., sup nt
JEFOr
2E (FO1).
where the last inequality follows from triangle inequality.
The next result, Gaussian chain rule given in Tripuraneni al. [2020), is crucial decoupling the complexity of the representation function class and the hypothesis class.
Theorem 8 (Theorem from Tripuraneni et al. [2020]). Let the function class F consist of functions that satisfy Assumption Then the (empirical) Gaussian width of the function class F (HH) satisfies,
{4a {4a 64G (F01 (Ht) log (2)
6 (F)(H))
inf D20>>
where (()) = L..e. (H) + (F). Further, G (F) & D then by computing the exact infima of the expression.
eD
Gx (FF((H)) < 64G (FF) log G
(18)
23

---

Lemma 11 (Lemma A.4 in Bartlett et al. [2005]). Let F be class of real-valued functions range in (a, bl. Given set of i..d points, with probability least functiionn with
Rz(F)
a]6
(R2 =
inf aE(0.1)
Ama - aa) a +
C.3
Analytic Inequalities
Lemma 12. If - VžA - B = for A, B > 0 then r & A² + 2B.
Proof. As the discriminant of the quadratic in v is positive we are guaranteed real roots 21, 01,
Taking the larger of the two solutions we have V02 = 4 + VAR+4B So x2
4 B+
A 44444B
2
By AM-GM, 32
A² B + 1- 44 A 2B
Lemma 13 (Lemma B.I. from Srebro et al. [2010]). For any H-smooth non non-negative function 8 R and any t, E R. we have that
(l(t) {(r)) s (H((()) + (t))) r)²
Lemma 14. For k [0, [n].
2
in
fn
Σ
ajz
Σ
aji
I ukg
1===
(k.a)
Proof. First note that for any & E [m].
2
a2
K
O
This follows from applying reverse triangle inequality
04
a
|ax
1=1
1=1
Finally, we square both sides and rearrange the single summation into double summation, which completes the proof.
Lemma 15. Consider the function f(x) aln (b/2) a, 2
1. The minimizer of the function over 0 < x S = min (a. b).
2. The corresponding minimum value is a In
eb
min(a.b]
3. For any c such that a S c b, a In (eb/a) S cln (eb/cc.
Proof. The first and second claims follow from the fact that the function f decreases from to a, and then increases. The third claim follows since the function -> x In (eb/2) x:) increases till x=b.
Lemma 16. Let Z be random variable taking values in R and let A R be such that PP A 0. then sup |Z| 2 ess sup Z = ||]] 2 A.
Proof. The first inequality is standard. The second simply follows from the definition of ess sup: ess sup /Z| inf {a E R: : Z 2 a] = 0}

---

D Proofs of main results
Thcorem 2.1 Bousquei (2002), Lemuna
Theorem
Multi-Function Rennett inequality
Thoorem 10
Lemma 19
Mulri-Function Analog Theorem 2.1 Bartlert [2005)
Rademacher wichh to empirical Rademacher width
Theorem LRC Bound
Lees class umpiriccal LRC bound
MTL
Loss class LRC bound
Theorem
Thoorem Target task transfer bound
Theorem
task-avergged represenation difference bound
Theorem MTL via MTRL
Theorem 18
Figure 1: A graph demonstrating the dependency structure of results. The top blue node is the concentration inequality given in Bousquet [2002]. We abbreviate "local Rademacher complexity" with "LRC"
In this section, we restate the main theorems our main paper (with precise constants) and give detailed proof of our results. A graph in Appendix D shows the dependency between our theorems.
Note the relationship between the theorems in the main paper and the theorems in the appendix are as follows:
Theorem becomes Theorem 15
Theorem 2 becomes Theorem 18
Proposition becomes Theorem 16
Theorem becomes Theorem 12
Theorem 4 becomes Theorem 17
Theorem 5 becomes Theorem 19
Theorem 6 becomes Theorem 11
Theorem becomes Theorem
In Appendix D.I, present Theorems 9 to 11 which are generalizations of prior work and also recover the single function setting. In particular, we give concentration inequality and two risk bounds. In Section D.2, we present Theorem 12 our result for multitask learning with bounded non-negative loss classes. Next, Appendix D.3 contains Theorems 13 to 15 the MTL via MTRL learning setting.
The remaining theorems add the additional assumption smoothness. We start, in section Ap- pendix D.4, by giving Theorem 16, our bound the empirical local Rademacher complexity of smooth bounded non-negative loss classes. However, in order to use the above result with our prior theorems need bound the local Rademacher complexity constrained on the risk one
25

---

constrained by the empirical risk. So, in Appendix D.5, we introduce Lemmas 19 and 20 to make this conversion. In Appendix D.6 we conclude by invoking our bound on the local Rademacher complexity of smooth bounded non-negative loss classes within our MTI. and MTRI. theorems with Theorems 17 and 18.
D.1 Concentration Inequalities and Risk Bounds
In this section we forgo the compositional model and will consider a generic function class F. Theorem 9 (Concentration with functions). Let F be a class of functions from X to and assume that all functions in F are Py-measurable for all [0, qquare-integreee and satisfy E Let sup Il S 1 and fer
7
sup feFee
ΣΣ 5(X))
(19)
j=1
or let sup sss f S 1 and
SEF
= sup fx()).
(20)
feFs j=1
1
Let a > such that o²
2
sup
1
Σ
Var [X]]] almost surely, then for all 2 0, we have
fEFe
1=1
P(Z S EZ v 20(tno² 2IEZ) + 5 {) se
Proof of Theorem 9. We prove the result for Z defined in Equation (19); the proof for the definition
of in Equation (20) similar. Let
in Σ (x3))
Z
sup fEFe( 1===1
and ,1"), "e be the functions that achieve the supremum w.r.t Z.
f,m
Σ
100 (x,))
=
11=1
Next, for each [t] and q e [n] let
sup JEFo
Σ
FX33)
sup JEF8
fx(X))
Σ f(x)) j=
J==1 (k.
The random variable 75 is essentially removing fx(X9) term from Z. We define ((h.a)) as the functions which achieve the supremum w.r.t Zg. That is,
(k.0)
2
k. (
(k.9)
Finally define,
1,m
24 =
Σ
(kir) (X3)
-z
1,1=1
26

---

We now prove that the conditions in Corollary are satisfied.
in
Σ
(1.)))
(x))) (x3)
1==1
Σ 1==1
00) (xz)
Σ (x²)
(21)
J==1
(1.0)
Σ
1 (x})
Σ (x3)
(22)
1==1
f==1
(k.)))
Σ
1/ (x3)
+ (x
Σ
(x))
(by triangle inequality)
f==1 (k.)))
(k.0)()))))
(x:)
1
(by assumption)
(0) where Inequality 21 follows from f ...., ft being the functions which achieve the supremum
w.r.t Z and Inequality 22 follows from f( (( ((h.4) achieving the supremum w.r.t 2
In addition, we show that EE [ is non-negative. Recall that Ey is conditioned on A4.
Eg
72
Ey
11 (1a))) (X))
7%
1===
E
Σ
(( (X3)
zz
(since Z is constant w.r.t EE)
1=1=1
E
(k:a) (X))
2%
(using Jensen's 's inequality).
Finally, each s² is constant w.r.t EE besides when j 1 and i = so the above reduces to:
Ex
Σ
(
-z%
(k.))
0.
27

---

Also, we have
- 1) = (nt 1) Σ
>
10)
(xz)
j=1 1=1
Σ
1
k
j==1 (kk)))()g)))
1,9
Σ
Σ
(X))
k
J,i=1
(k.g)
Σ
k
J,==1
(k.
f,
Z
k
Therefore, Σ/ j- En 1i= (Z z 1 Z.
Finally,
27
Ex
27
Σ
Ey
Σ
1(0000 (x²)
Σ
k
k,g=1
Jai=
(
f,m
(fSthee) (x,))
(by Corollary 14)
k
As the samples for the same task are being drawn from the same distribution,
E
(2z)
27
Σ
f.m
( f
(k.1)
(x,))
k
k,g=1
(1+t
B1
Note that f/ (k.11) is fixed function w.r.t. x therefore { is a fixed function as we integrate
over X4. So. E/ (xx) < sup E (1(()))) }].
Applying this reasoning to the t
functions gives the desired bound.
71
E
1 x
(k..))
27 (x:))
S n Σ
sup FEEF
Ej ((x())
E (fx())
= n sup
fEFAI
Note, crucially, that the product space strueture of our function class for allows us to move the suprema outside the summation. Dividing by nt gives the desired bound.
Σ B
( (2
[2:)²
27
<
sup JEfaI
Eg [(A()))))]
sup JEFB:
Var (Xx2))
k.
k=1
28

---

The right-hand side is bounded by x² by hypothesis. Finally, now we apply Corollary all the conditions are satisfied.
Theorem 10 (Analog of Theorem 2.1 in Bartlett et al. [2005]). Let F be a class of functions that
map X' into (a, b). Given an imput X- { {X assume that there is some such that for all
I that & شE= Var [x}]
S r. Then, for every > with probability e
28r sup (Pf -P Pm s inf 2(1 x)E38x + +V in fEFBi
-
8
+ (b-
a)
a
3
nel
Proof of Theorem 10. Let V sup pm where pm t
Ei=ı E f)()))
and Pf- E. f. Let F ا-ه (b-a) f / be set of scaled functions. For each f E F we
have that F.f = 0 and / < 1. In addition, for all f j we have that Σラ=1 Var [ (X})]
(b-a)z & Σラ= Var [f) ( (x3)) I (b Therefore, the conditions for Theorem are satisfied.
Letting& Z supjetse frr Ej= Ei 1x(x)) = (b-a) V+ as in Equation (20), we thus have with probability 1 - e ē::
28r 4SEV+ (b- a)
(b -a)5
V+ s EV+ +
nf3
28r 48EV+ (b a)
(b a)ō
< EV+ +
+
(23)
nt
nt3
28r
OEV+ + 5(b a)
(b - (b-8)8
< EV+
(24)
tn
ant
nt3
S 2(1 + EX + v 28r
[ +
8
+ (b a)
(25)
tn
nt
where Inequality 23 is by subadditivity of the square root, Inequality 24 is by application of the AM-GM inequality, and Inequality 25 is by Lemma 10.
Theorem 11. Let F be a class non-negative b bounded functions. Assume that X ..... X are n draws for j E [t] and all nt samples are independent. Suppose that
Var [f] < VV) BPP
where is a functional from J to and B > O. Given an input X = {x]] "ن let ab be a sub-root function with fixed point r" such that XE r) I (b)r) for all r 2 r". Then, the following holds: For K > 1, a O, and 1, with probability least 1 -
K K-1 fm 200(1 a)² a)²Krr Kr*
K
BKr
( a
1 ba
Vf F Pf
+
+
4 nt
nt
Remark 2 (Comparison to Yousefi et al. [2018]. Theorem of this form was shown by Yousefi et al. [2018], which generalized results from Bartlett et al. [2005] to vector valued functions. The proof of Theorem 11 follows the same steps as the proof of Theorem Yousefi et al. [2018]. Yet, we will use our Theorem 10 which has better constants than Theorem I within Yousefi et al. [2018] for when the class that the suprema is indexing over is has product spuce structure.
The following lemma, and its proof, is a modified version of work in [Yousefi et al., 2018, Lemma B.2 J. which is generalized version of work within [Bartlett et al., 2005, Lemma 3.8.J. We remove the Bernstein class structure, make B > 0, and only consider non-negative bounded functions
5 The reason we restrict to non-negative functions instead of functions that map to [a. 6] as done in prior work is because we failed to reproduce step within Bartlett et al. [2005] and Yousefi et al. [2018]. Consider the last sentence within the first paragraph of the proof of Lemma 3.8. in Bartlett et al. [2005]. It is shown that Pf < pr f + r/BB)). Now fr may be negative for f which maps to (a, b] with < 0. Therefore, we cannot multiply this quantity by value greater than one. In this case K/(K 1) for K > L.
29

---

The theorem can be generalized to Bernstien classes like Theorem B.3 from Yousefi et al. [2018] with worse dependence on B.
Lemma 17. Let K > 1,r > 0 and B > Suppose that for all f E F we have V S BPf. Define the re-scaled version of F as
{
rf, V (.....- UI.....))EEEB
F
5')) 15}= max (r,))
(26)
V = sup r'E
Pf pm S
r BK then
K
vf E FO, Pf K-1
pm f + BK
Proof of Lemma 17. Let f be any element in Fe:
Case 1. If Vff) Sr, then f' = f and the inequality V S BK
leads to
P(f) S PM + BK
If all component functions of f are positive then pn (f) is positive and as K/(K - 1) for all
K >>> we have
K P(f)
K K-1 Pm(
BK
Case 2.
If Vf) 2 r, then f = rr rf\(((f) and the inequality V, S BK yields
P(f) S (f())+ V(f)
& Pm (f) + P(f)
BK
K
Solving for P(f) gives
K
K
P(f) S K - pm(f)+
pm (m( + BK
K-1
which completes the proof.
Proof of Theorem 11. We modify the proof within Yousefi et al. [2018], which generalises the proof within Bartlett et al. [2005] by extending it to multi-function and Bernstein classes. At a high level we apply the same steps as Yousefi et al. [2018), yet we use our concentration inequality and do not need to consider the more complicated inequality [Yousefi et al.. 2018, Lemma B. 1] as do not have the additional Bernstein structure. The proof closely follows from Yousefi et al. [2018] with minor modifications
described and presented for completeness.
Let r 2 r be a fixed real number.
We seek use Theorem on FSt see Equation (26). therefore we will validate the conditions of the theorem.
Verifying Conditions of Theorem 10.
Fix f E FBt Thus, f rf/ max(r; V(f)) for some f F. If max(r, V(f)) r, then
I' r'= m/x(r, V(f)) = f. Thus, Var f Var [ < V S r. If max(r, V(f)) V()).
then [f"
v²(f) Var [f] < v(n) < r. Therefore, sup P'e Σj= E [ (x,))² s
,
Finally, recall, functions in F are positive and b-bounded.
Thus, by Theorem 10, with probability at least --5 and V5 00 0
25r
8
sup (Pf pmf) < inf fe
< 2(1 + a EX +
+ a 3 nt
+
tn
30

---

Bounding (Frt) Now we must control the Rademacher complexity within the above inequality. This part of the proof is the same for Bartlett et al. [2005]. Yousefi et al. [2018].
Let Fu, v) = (f E Fot a S <V() - 0) for all 0 v w S v, and let
Rx( = 1
S (x))
nt t=1
Rx (F+1) sup P'EFFI
[Rx(f)),
Observe that Rx (JOD)) -EX (FS1). By assumption we have that ((f) S B(P)) S Bb, Vf FFM, Fix some À and define l as the smallest integer such that r > Bb. By leveraging the principle that combining function classes on a uniform set of inputs is equivalent to the Minkowski sum of the created image, and utilizing the trait of Rademacher width breakdown under Minkowski sum as detailed by Vershynin [2018], we have,
Rx (91 U22 Rx (9:) + Ri (G2).
We thus the following inequalities
Fi
(F
E
sup FEFR
= E Rx(5')
sup JEFAI nl
T max(r, v(J)) oJ (x3)
j=1
1 t
< E
sup
(X,)
+ E
sup
V(F) (3
(e,) nt
(B)) nt j=1
j=
< E
sup (E.r nt
1
of (x:)
sup (e
Rx(n)
i=1
1=0
< ( St
Σ -- (Foe, ,,(ttt
3=0
As r 2 r", we can bound the local Rademacher width with the sub-root function.
$ (r()
3 (1ait))
B
1=0
Now the suo-root property of db gives us that that (Err S (x(((() for any & 2 and, hence,
(i(r) 1+
(trr)
1+ VX )
A
Rx
x-
I
B
B
1=0
Pick x = 4 in the above inequality, which gives Rx (F31) S (v)() B. Also, r" is the fixed point of sb we have for all r 2 r" that vbr) S vr/r*d (r*) = Vrr". Taken together, we have
5 Ax (FRO) S Vir Vr 2r
B
Applying Lemma 17. The remainder of the proof is simple manipulations and applying Lemma 17. Here our proof deviates from [Yousefi et al., 2018]. Using our above bound the Rademacher complexity gives for any r 2 r* and å > 0, we have with probability at least - -5
10 B
28r
In + b -
1 8
sup (Pf - pm inf inf fEFB
(1
IT
+ +
a
3
rl
Now, letting A = 10(1 + +a + v 28/ and C= + 1)) 6
Pf pm fr} < AVr + C.
sup Pe
31

---

Setting Avr C BR gives quadratic, which has both roots bounded by (ABK)² + 22BKCby Lemma 12 now applying Lemma 17 we have that
K Pm Pf K-1
2C. 2C.
Plugging in our values for A and C gives
Pf K K-1 Pm f P" 100 (1 a)² Kr
K
BKg
+ 20v
+2
+
nt
nl
nt
Applying AM-GM incquality,
PM P" 101 (1 +a)² Kr*
BK8
1
b6
Pf K K-1
+ 802
2
+
B
nt
3
nt
which completes the proof.
D.2 Multi- Task Learning
The following theorem is a vector-valued generalization of Theorem 5.2 within Bartlett et [2005] with several differences: do require & < r", b 1, and solve for constants.
Theorem 12. Let (f be empirical risk minimizer given in Eqn. (2). Let (prr > BE (H),r) with r" the fixed point of (r)). Then, under Assumption 1.A with probabil- ity 1 -
Reourco (F S Rsource (f", h1)) V Rssurco ht) hi)
bō 66
+ 146
T*
10268
217r*
rd.
b
nl
(27)
Proof of Theorem 12. To simplify the notation within the proof let L" = Rsource hh),
We follow steps similar to the proof of Theorem 5.2 within Bartlett al. [2005]. Assume f arg min Pyly exists. (As mentioned in Bartlett et al. [2005] if it does nor exist we can consider
sequence converging to the infimum.) Note that {5ī (Xx) (E())) are nt independent r.v.. Note that
b
Var (773f)
E (z)(
(fj(x) -Ld
ml
j=
By Bernstein inequality, with probability 1 - 6-
20 bb
2 b5
pn < pM f L +
in
3 tn
By Theorem 11, setting a + and B = b. and union bound, with probability 1 - -
K
L6
268
17896K8
6865
1
Pt S
V2
L
nt
3rd
882nl
3nt
By change of variables we consider K > 0 by adding 1 to K:
(K +
V2
L6 nt
L"
+
266
178968 (K +
1)
6866
144r*
(K 11)
3mst
+
+
882nt
3nt
b
K
1789K66
r
L6 + L*
2236968
144r*
V2
L'
L
268
/2
882ml.
882ml.
K
nl.
K
3knl
32

---

2 Applying AM-GM to
K 2Vmr.
L'b
L'
1789K46
14
+ v2
L8
2236966
144r
2L
5b6
882nt
882nt
K
3K
These are the terms without K:
L8 nt
2236965
144r*
L
v2
(28)
882nf
b
Considering only those terms function of K:
1789K66
1
2L *
5b8
882nl
b
K
3Knl
max
VL'.V'
23
We set K
Terms with K in the numerator are upper-bounded by
VF..
178965
VI"
144r*
V L +
882n/ max
(V
bmax
V V.
net
Terms with K the denominator are upper-bounded by
2L
b8
+
5h6
68
max
L
3rt max
VL",
mf
33

---

Expanding both expressions gives eight terms where we will choose an appropriate value to maximize the quantity:
2L Vr"
L'
I '2
b
Vbmax
bg VI"
1
L
I 1441
b
b max
Vo..V
bd
me
5b382
5b5
3n in
VL"
bd
3nt
ml
17896262
178968
882nt
882n max
Vo..v
b6
2L Vbvo
L6
2V
Vnvtman max
VL
bd ml
144r"
r"8
<
144
Vo max
net.
5vbvr=8
5
8"8
3
3nt max
VL"
66
nd
1789 L'
1789
L*bō
882
nf.
882nt max
Adding all of the right-hand side expressions together gives:
3553
L 68
Lrr
325966
437
r+5
146
V nt
882
nt
882nt
Adding the terms without K, Equation (28)
gives:
L
3553
L*b5
L'r
1281468
437
r+5
144r*
22
V
146
L
+
+
nt
882
nt
441nt
nt
b
Applying AM-GM again
bg
3553
8986766
1301
VL
V
146
+
L
ml
882
ne
882md
6b
Rounding to the nearest integers:
V
bō 6
146
p
L
102b5
217r
vll.
D.3 Multi-Task Learning via Representation Learning
34

---

Theorem 13. Let be an empirical risk minimizer as in (2). Let (()rrrrrrr))))))) 2 bER r" the fixed point of (b(r). Then, if Assumption I.A holds. Then, with probability at least e
(f (e
F o H. with
dz s V Reource (ffffhhh))
66 V
r
10266
217r*
146
+
nt
nt
b
where recall that dr,f g is defined in Equation (12).
Proof of Theorem 13.
dz.f. (h,
= inf { (Raunce (f', ( ,h) Roonree (f" (1,))a))))))))))))
F
s Reauree (F (i) Rumncel (f" 11))
bō 6V
10268
217r*
$ v Rsource (f" ht))
146
+
+
ne
nt
where the last inequality is due Theorem 12.
By using hypothesis which rates the task-averaged representation distance to the worst representation difference we can bound the excess transfer risk.
Theorem 14. Let fo be an empirical risk minimizer of Reorze( h) in Eqn. for any representation h. Let (()) 2 (ERz o Fo. with r" the fixed point of (r)). Then if Assumption 1.A holds, with probability at least
bō (o/ m
Raarger (ox hi) S Raarger (oo h2)
+ v Ruarger hr)
17165
21967r
+
+ d (h;
2b
Proof of Theorem 14. Let fo arg argminnee ser Ranze (f, ht. By adding and subtracting dy Fo (h: h²) then applying Theorem 12 to Renger (So, lt), we have convenient cancellation of Rarger (Fo, h). For notational succinctness let
bd 146
and B. -r
102b8 217r"
A 61
/
m
m
Therefore we have:
Rearge (f., fi) Rurgea (uu h))
dr (h; + dr Fo (o(h;
Rearet fo. fi)
(Rarger (Fo, hi) Reargolfo h²)) + dr
s Rearger ( Fo. h) + v Reagal fo. h)A, B.
Ruungec ( h) Riarga ( (1)))))) + dd:.o
V Reuree (Fo, h)., + B, Reunge (fū, h²) + dy,5, hh:
Now note that Rurger Fo. h)) (fug h²) + dro (h, h²). After applying subadditivity of the square root v and AM-GM can bound dro..; sa (h, h²) with Theorem 13. This is concretely
35

---

demonstrated with the following chain of inequalities:
Rungea (fo. h) - Rungel (f, h²) + dro.5o (h, A + BB + Runger (fo h²) + dy. Jo (h;
Rusgal h + V (d. (h, + Bd + Rurget 5o h²) + dr (h: h*)
d dro.55 l()
A?
B, + R 11)) d Fo (h:h²)
+
2
Rurger S0 11)
A, + B₁
Ringar (fö 1(
2
A
+ + Be + Reagge
1²) + dr F. (h;hh)
2
3
A?
$ Resger (f h-)
2
As
+
B, + Reargel (fū, h²) + FF (h;
2
2
We can apply AM-GM to A?
6
MM
+
146
= to get A2 72h6
42632r
m
Finally, by collecting like terms, we have that Ranger (So, It) is bounded by
m Rusgea (f), // bd + 219
17168
21967r
Ruarea (o, h²) + dr (h;
m
2b
Theorem 15. Let l and fo be the learned representation and target predictor, as described in Eqns. (2) and (3). Let th (r) 2 (ERzz(t (fo oH, r) and 1/2(r) 2 bERRz (fo with rī and rī the fixed points of 1/ (r) and 122(r), respectively. Then, under Assumption 1.A and that f is (v, -ivieerse over Fo w.r.t. h², with probability at least 1 - 4e-5, the transfer learning risk is upper- bounded by,
Ruargr (so. (S:
h) S RavrgerSo h1)) + v Reurger (S0. 100)
b8 + 219
ri
+
17165
21967ri
b
m
2b
+ (V ( Roouncee( (oy1
6y
146
r
+
10265
217r
+
not
nt
b
Proof of Theorem 15. The proof is by first applying Theorem 14, then (v, e)-diversity assumption, and finally Theorem 13. This is demonstrated with the following series of inequalities.
Riarger h) S Reargrr (fo ht)
b8 9
219 m
ri
17168 + m
21967ri
+ Rearger (Torge(So, (fū, h²)
2b
dr (h;
2 / Reange he)
16 219
ri
+
17165
21967r
+ Reargel (fo hh"
m
2b
b5 6v/
10255
217r
+
( Rsource (f",, (1")
+ 146
+
+ E.
nt
nt
b
D.4 Empirical Local Rademacher Complexity Bound
The following lemma allows us to discard the composition of loss so long as we appropriately scale the cover.
36

---

Lemma 18. For non-negative H-smooth loss and any function class F, we have:
N (Ce(F% (r, S N/C
nl
V12Hrnt
We follow the same first few steps as in Srebro al. [2010] but then bound the maximum by summation to recover empirical L2 cover.
Proof of Lemma 18. By Lemma 13 we that for non-negative H smooth function f. we have that (f(t)-f(r)) & (f
Using this inequality, for any sample X {(r).. betd- sE(n)
of nt points, for an fcr we have,
(e - vf))
sup
X
i= j=1
6H
$ sup X
(f w/) + (2f) (f f
fo (zt))
6H
(f)) + (z:) (x.) .2))
max (f (zt) fs (z:))²
sup X
2E|n
< sup V12HT
max K
(f(z)) (z)))
x
S sup V12Hr X
f
sup V12Hrol X
ΣE (z))
That is, cover of (f e FB1 Pf S Sr at radius e/ 12/Hrrt also cover of Cr(F3, ,r) and we can conclude that,
at radius
N (Cr(F s),, SN (ro), V12Htrn nl ml)
which completes the proof.
Theorem 16 (Smooth non-negative local Rademacher complexity bound). Under the setting of Theorem 15 along with being H Hmsoooth and Assumptions 1.B and I.C, have:
Ris (FF = 640/3G (FS( / Vorlog (nt)² 80/3Dv Hr log (nt) + 4 4
Vnl
(29)
and if 16G (F)((H)) < D and vb 640 640 which holds for large enough samples,
ev3vb
< 2560 (500
(H) log
(30)
((201I(FO((H))
where
G(FS((H)
=
L.me(H) + (.(F)
and [(Fs((H)
VHG (F))
of
37

---

Proof of Theorem 16. Let Z denote the dataset of nt points.
We
first
compute
(UP supz If (z))
Note that,
sup sup |1 12(2) S (()(FF(()) z
sup 1K o f o 1ll
fEFB McH z
((()(M(2)))))
sup fErSChEH nt
j=li=1
sup ΣE
((((((()))) br.
JEFECHE
Therefore, by refined Dudley's entropy integral formula, we have
vbr
(og.((rrr)) e, nl) de
Rid (Ce (F)))))))))
(H)),r) s
inf Vbr2a20
4a + 10
(by Lemma 7)
nt
/br
log logN(FFM(P)) (7),
Vi2ffrnt nt)
inf Vbr2a20
4a + 10
de
(by Lemma 18)
Vbr /12Hrntgne(For (H))
inf Vbr2a20
4a + 20
V de
(by Lemma 2)
/bb 4a + 40v 3/rrrt (FO))) log
inf Vbr2020
(H))
(31)
Now we apply the Gaussian chain rule Theorem 8 to (FF((H))) giving us:
{sa 4a + 40V3HH inf 448 + 64G (J (H)) log T D2620
D
v
Vbr
( inf Vbr2a20
log
Setting mi6 (Jr (H)) D) and simplifying by bounding the minimum with 16G (FSt(H) we have:
eD
br
Rad (F (FF))))))) s 2560/3G (F)) v HHr log min (16G (Fo (H)) D)
log
a +4a
(F8) v HHrlog Doing the same for 8 with min have
cD min[160][7
Rid (Cr (H)), 2560V3G (F)) VHr
eD
log
min (16G (H)) D))
evb
log
min
Vb, 640/3G (F& (H)) H log
[ (H)))
The above expression is optimal with respect the parameters and and clearly gives four different possibilities based on the two minima. Since, under a bounded setting, G(F would typically go down with nd, for large enough nı have that min(16G (T)((H) D) = 16G (F*((H))
and
cD
min \br, 640V3G (FF*(())))))))))))))))))) / lo
min (16G (FO((H)) D)
eD
= 640033 (F))(
Hr
12G (FF
38

---

Under these conditions, we have
ev3vb 1920IT (H)
Rid (1 log
where (1(F3 G ( V log
(eG(Fo!(7))
Under the other three possibilities for the minima some or all the logarithmic factors are identically one and lead to simplified bound.
Alternativlyy, for a more simple bound which always holds set =
br nf
and
to get Vns
D
And (FF(( s 640V3G (FF((H) VHr log (nt)² 80v3Dv Hr log (nd) + 4 4ybr
Vnl
Remark 3 (Standard single function setting.). Everything in the proof of Theorem 16 up to Equa- tion (31) holds for a conpoopposi model and where t= 1 which corresponds to the standard setting, In this context, there is need to apply the Gaussian chuin rule, Theorem 8, Let Q X + R be a hypothesis class and note that we have v. i.d. samples.
If we set a min (vbr, (Q) then we have
evb
R,,((( < 40V3,, min (V5,10/36.,00//
and if we set a==
3vbr Vn
N. ( (VV Hrlgg (n) +
Using Lemma 5, we also get the following bounds for local Rademacher complexity (as opposed to width),
evb
br
(C(()))
+V
min
10 30,
5vbr
RR, R,,(() < (Q
(n) +
vi
D.5 Theorems for transition from empirical to population
Lemma 19. Let F be a class of functions that map X' into [0, b] with > 0. Fix a
For every
5 > O and r that satisfy
b6
8
r> r 224 E F PS Sr)+
+
nl
3
have with probability least 1 - that
{ at Pf S ( e pm < 2r
The proof is similar to the proof of Corollary 2.2 within Bartlett al. [2005].
39

---

Proof of Lemma 19. For f E {f E F Pf r) we have [ar - Pf - bPf - br. By
Theorem 10, with probability 1- e every f (f E Fot
Pf S r satisfies, with v2.
2br
8
pmf Pf + 2(1 a F F +
+ b
nt
n
2hr
1
5
1 + 2(1 + a E2 F
+ b
nt
a
nt
5r+2(1 2(1 + R. 01
6d
+ r
+ b
+
1
nt.
2
02
nt
S 2r.
D.6 Smooth Learning Bounds
Lemma 20. Under the setting of Theorem for any 6 > 0, the fixed point r is bounded by.
cG (.G(F Hb Hogog (nt)* + 2332800D Hb log (nt)²
112628
194462
+
ml
3nl
vl.
where 01 < 1.5 x 10 and G(FO (H)) = Tz (H) + (F.).
Further, if
16G (F*( D and vb 2 640 640v (1003II(F*)) (H)),
where I(FF((H) VHG (FFI(H) log ( ) then for any 5 >> O, the fixed the fixed
point r is bounded by,
De 2 16G (F))(H))
2/33b
e2G (JOI (Hi)) Hblog
log
1920G (FSI(H)) /H log
16G (
112628
3nd
with 02 <88 10
Proof of Lemma 20. Let
>(r) 4(a + () F Pf < +)
bo8
8
2
3
Now we have
bE9tz {1 {EE e F
PP 7) < 4(1 a E92 { bf E F
r b
128
2
Pf S
+
nt
a
(r))
(32)
Note that from Lemma 19, we have that, for any 5 > 0. with probability at least 5
2r
Rz bf e r jot Pf < } < Rz of E ret pm f <
b
Further, we can apply the concentration of Rademacher complexity, Lemma 11, to bound the expected value of the left-hand side as follows. With probability at least 1 - -5
40

---

Exi bf E F Pf 1 bl
7
S 282 { bf E Fo
Pf -
1
+
1-8
nt
Hence, with probability
2e 20_ we get,
E Fiz bf E F Pf - 5) - 282 { bf E F PM -
bf
2r
b
b
nt
We now apply Lemma 16 and upper bound the right-hand side by taking supremum over Z. This gives us,
E Pi bf E Fer Pf S 5.] - 2nnx { (ss E pm f
2r
628
b
nl
Plugging the above in Eqn. (32), we get,
2r BERZ { FSt F Pf S :3 S 8(1 + a)ERR bf FBL fm
b
628 nl 3
(s
4(1 (1++a) + -
Suppose that the local Rademacher complexity is bounded by multiple of vr, say VfE. Now bounding the local Rademacher complexity with Theorem 16, we have that,
bERz { E Fot
b - 8(1 + +a) + 1,6 nt + 4(1 + a) +
2) a
Pf
= DVF+D
where
6 88 + 4(1 + a)
2
A = 8(1 + ())
D
nt. 3
Note that AVF + D is sub-root and larger than 7(r). Thus if we solve for fixed point r" of this expression we have Avr* + D = r*. By Lemma 12 we have r" A 2D. Therefore, with a 1/8,
RR, {
E 8 P }
bounded by a sub-root function of with the following fixed point:
672 (F)) + 139 b28
(33)
3 nt
We have seen from Theorem 16 that if 16G (T (H)) S D and vo 2 610)3T1(70((1)) then we
ev3vb
E = 2255053310 (H) log
1920II(FOI(H)
In this setting, using Equation (33), the fixed point is bounded by:
De
2/3vb
112626 8
796262400G (H)) Hb log
log
16G (FW
1920G (FO (H)) / log
c
3nt
Alternatively, can always set E as follows:
80 40/3DVE H log (nt) + 5vb Vnl
E 640v3G (F))(H) H log (nt)²
therefore we also have that the fixed point is bounded as:
149299200G (F)) Hblog (nt)* + 2332800D Hbb log (nt)²
112628
1944
+
nt
3nt
nt
41

---

D.7 Smooth MTL and MTL via MTRL
When we add the additional assumption that the loss function smooth we have the following extensions to Theorems 12 and 15
Theorem 17. Let (f, be an empirical risk minimizer as given in Eqn. (2). Let v((r) z bR (F rH) with r" the fixed point of (rr).. Then, under Assumption along with being H H-smooth, with probability - 2e
Reource (f, S Rsource ) + Raource (f ,h)
bō 61
+
146
r
+
102b6
217r*
not
ntt
b
(34)
where
rx s ((F(F())))))) H log (nt)² +
D H2H log (nt)²
bō
82
b
nt
nt
nt
with < 1.5 10s and G(F = Lē (H) G,,
Proof of Theurem 17. Use the fixed point bound from Lemma 20 that always holds and substitute into Theorem 12.
Theorem 18. Let h and fo be the learned representation and target predictor, as described in Eqns.
(2) and (3). Let thi (r) (E F H, and (22(r) 2 (f, Fo, r) with rī and r the fixed points of 1o (r) and (r2r),, respectively. Then, under Assumption along with E being H H-smooth. and that f is (v, e)-diverse over Fo w.r.t ht, with probability at least 2e the transfer learning risk is upper-bounded by,
b6
in
17168
21967ri
Rearger Soo h)) Rearger + V [o h())
219
+ m
2b
(35)
( V Reourcolf" ,f"))
bō 61 net
r2
10268
217r
146/
E,
(36)
nt
where
r b
S c (FF)))H))) и log (nt)*
D D2H log (nt)
bd
8²
+
nl
n2
where c < 1.5 x 1 and
11266
1296b
97200 (Fo h) log (m)²
3m
m
Proof of Theorem 18. Use the the fixed point bound from Lemma 20 that always holds and substitute it into Theorem 15.
D.8 Local Rademacher complexity chain rule
Theorem 19. Suppose the loss function & is Lu-Lipschitz. Define the restricted representation and predictor classes as follows,
Fx)x = (lo f St :3h e H: V fol)
(x H: Bf : h) sr),
where V is the functional in the local Rademacher complexity description. Under Assumptions I.B and 1.C and that the worst-case Gaussian width of the above is bounded by the sub-root functions u and yn, respectively, there exists absolute constant such that
6 (.( S (((LLe>>>)) + dx((r) log (nt)
D
(nt)²
42

---

Proof of Theorem 19. Define
to (H) = f.)) ((2 h) sr).
Observe that for any (eo f. f,h) Fx (H), have f E Fx(r) and h Hx(r). Hence, to fo (H)()) _ Fx(r) o Hx(r)
Further, by assumption, the composed function é o f is LeI-Lipschitz We can now apply the (standard) chain rule of Tripuraneni al. [2021] which gives us,
3n (n (H)())) - Gnr(C Fx(r) Hx(r))
(LLeV>>() + (r)) log (nt) D
sc
(nt)²
which completes the proof.
E Detailed comparison with prior works
In this section, we provide a more detailed comparison with prior works.
E.1
Comparison with Srebro et al. [2010]
Firstly, we identify some erroneous missing though fixable steps in the proof of Srebro al. [2010].
1. Dudley's integral formula. The work of Srebro et al. [2010] seems to interchange the concepts of Rademacher width and complexity with the same notation (F). The original Dudley's 's formula and its truncated version proved by Srebro et al. [2010] is for Rademacher (or Gaussian) "width". yet in their work, it is used to bound Rademacher complexity. It is possible to translate from width to complexity, but this will lead to an additional term of
V br as detailed below. This additional term only changes their result by constant factors.
Lemma 21. Consider a class of functions F with range in [0, b). Then given inpul Z of n points, Rz {1 FF sr] < 2iz { Pm S rr) + br
Proof. The proof follows by application of Lemma 5. In particular, given input Z of points, for any { [FFF: pm s < r) we have that
b n
br
1 = n 1=1
Σ $(
f(z)) S
Plugging this in Lemma gives the claimed bound.
2. Centering, Within Srebro et al. [2010] they consider loss with the "bounded difference" property: vg, ú, s/ we have that [é y) - E(ğ', x)1 S 6. To bound the local Rademacher
complexity of their loss class which is empirically constrained with pm(eo f) S r. they use Dudley's 's integral. Note the upper limit of integration in Dudley's 'slee'ss integral is / // 8'2
and it is claimed that / pm o f)2 < Vbr because (m f)² bP(Eo < br. Yet, this reasoning only follows for b-bounded losses not under this weaker condition of bounded difference, Yet, it is possible to center the process and perform a comparable analysis. To resolve this issue let f = arg inf ye. (m o f' and consider (f f) (fo f). This process is now b-bounded. Centering the process in this way does not affect the downstream results because
width is shift agnostic due symmetry.
43

---

3. Missing condition on n. This omission is related to the subsequent discussion about comparison with Srebro al. [2010]. In the proof of Lemma 2.2. after Eqn. 23, the limits of integration are required to satisfy V12HrRn (F) I vbr. Using the fact that in the setup, in general, Ri, (F) θ (.)). the above is equivalent to n Q HB² This condition on n is missing from their main statement. Further, as we detail in Appendix E.1.1, this term, in general, can be unbounded.
4. Fat-Shattering inequality. Using the notation from Srebro et al. [2010]. Note that fatz is a decreasing function z. Also x (og( is a decreasing function x for x 2 Therefore fatz log( fat, is an increasing function in æ. So therefore, for e [y,, 0) we have fat., log( fat., fat. log( fat, fate log( fat,)) This in inequality is in the wrong direction on page 27 of Srebro al. [2010].
Disregarding the above issues, the bound obtained on Srebro et al. [2010] on the local Rademacher complexity is,
Rn(C((F.r) = O ( (F) (log (n)) (n))
(37)
In contrast ours is,
evb
(L, ( Hrl
(38)
(FVH
Worst-case improvement for large enough samples. Accordingly, we bound the above as,
We first perform general comparison.
evb (F,(H
Rr (Le (F.
evb Ri (F) V Vlog (n)
- enn (F) Hr (n)
S ()) (n) log
eb
n
H log (n) 13
The above is of the same form as the bound of Srebro et al. [2010] in Eqn. (37), and it is easy to see that ours better whenever n = ( w
h Worst-case improvement for constant samples. Unfortunately, the term H can be unbounded, from above, in general, detailed in Appendix E.1.1. However, a reasonable and standard assumption removes this issue. If we assume that loss at zero is bounded as follows, {()) S B², then we show in Lemma 22, that b = = 12(1), thereby, making the requirement to be a constant number of samples. A uniform bound on (()) features in the characterization of sample complexity of learning with non-negative smooth losses as well as the regime described by the above bound on ε()) has been considered in prior works [Arora al., 2022, Shamir, 2015].
Improvement for certain hypothesis class. the above chain of inequalities, we use the bound that (F) < RR (F) Vlog n which is tight in the worst case. However, there are natural situations where the two are of the same order. A prominent example is linear predictors with data bounded in (any) norm ||-II and hypothesis class bounded in the via a (regularization) function R which is strongly convex with respect to the dual norm ||l [Kakade et al., 2008].
E.1.1 Understanding the HB term
No non-trivial lower bound. Firstly, we see that the term is not non-trivially lower bounded, in gen- eral. Consider the function {(f()) = = (q - f()))² This function is 1-smooth and considers (which bounds the size of fz)), however, b here is controlled by the size of and thus could be un- bounded. This means that the is non-trivial lower bound on H in general. The above example also works if relax the definition of b to be "bounded difference". (() (L(f(z)) ((f()))))) as opposed to uniform absolute bound.
1
44

---

A lower bound under {()) bound. We give a lower bound under the assumption of bound on 8(O).
Lemma 22. Let F. be a class of real-valued functions and let the loss function f: R + be non-negative H-smooth function with E(O) S Lo, and supzeRange(F) 8(2) b. Then,
HB²
b
14
2Lg.
HB
Proof. Note that
b sup {(2) = {(2) {()) + E(0)
H
(e(0), z/)
Lo
2
10) H 1
H
+
Lo
2H
2
{(0)
+ H + Lo
2
2L + HB²
where the first inequality uses smoothness, the second AM-GM inequality, and the third uses the self-bounding property of non-negative smooth losses (Lemma 2.1 in Srebro et al. [2010]).
O
No non-trivial upper bound. Consider the function {(z) H(1 + sin(=)): this is non-negative, H -mooth, and 2H. However, we can define the size of the domain B as arbitrary, without affecting the smoothness and range boundedness. Thus, #B² is unbounded from above, in general. b Note that even assuming an upper bound on E(O) doesn't help here.
E.2 Comparison with Denevi et al. [2019], Khodak et al. [2019]
more specific case of meta-learning in Denevi et al. [2019]. Khodak et al. [2019], which has the type of representation learning we study frequently called as "feature learning." " It is possible give guarantees for excess transfer risk in this more general setting, For example, the work of Denevi et al. [2019], under a generative model assumption, is restricted to linear predictors and convex losses. In their Thm. 5, they get rate of O
MTRL can be
J + vi) on excess transfer risk. However, Vn
for the feature learning setting, as they point out, this rate contains terms with hidden dependence on n and Their guarantee for feature learning, with linear representations (which is more restrictive than ours) Corollary gets a rate of O +
Another work of Khodak et al. [2019] mainly considers two settings of convex and strongly con- vex losses, respectively. Interestingly, fast rates in terms of the number of tasks be obtained.
Thm. 5.1 in the work, obtains the following rates, O + 1 for convex Lipschitz losses and
Vns
)11) vml)
for strongly-convex Lipschitz losses.
45


Reviews:
[{"review_id": "S2zizXX68u", "reviewer": "Reviewer_Sb8D", "summary": "The authors consider the transfer learning and the multi-task learning setting in a Representation Learning context: multiple source tasks are used to learn a good common representation to facilitate the learning process of a target task (transfer learning) or of the same source tasks (multi-task learning). Under regularity assumptions on the loss function and task similarity, the authors provide optimistic statistical rates for the transfer learning and the multi-task learning setting demonstrating the benefit of representation learning. These optimistic bounds interpolate between the standard -1/2 rate and the fast -1 rate, depending on the difficulty (i.e. the realizability) of the learning tasks. In order to reach such a result, the authors also provide the following intermediate contributions: they give a local Rademacher complexity theorem in the representation learning setting (for both the multi-task learning and transfer learning scenarios) and a chain rule for local Rademacher complexity for composite function classes which allows to decouple the (local) complexities of representation and predictor classes.", "questions": "In Ass. 1, the Lipschitz and the boundedness assumptions are necessary? Smoothness is for sure necessary to get faster rates.\n\nThe authors should recall in my opinion that m in the first equation represent the number of samples of the target task.\n\nCould you please make a detailed comparison between your optimistic bounds and the non-optimistic bounds in the references [1-2] I mentioned above by only keeping the leading terms w.r.t. the samples/tasks number and the complexity measures?\n\nWhat you call 'transfer learning' looks more similar to meta-learning. In transfer learning usually you only have one source task and one target task and you do not investigate the source task training, but only the transfer knowledge from source to target.\n\nThe authors developed their analysis under a quite general notion of task similarity introduced in previous literature. However such similarity assumption seems to be not well motivated for the representation learning setting in which the natural task similarity assumption is that the target estimators of the tasks all lies in the range of the representation. This natural link is well explained for instance in the reference [1] I mentioned above.\n\nThe paper 'Optimistic Rates for Learning with a Smooth Loss' does not use Rademacher complexity measures in order to give optimistic rates. Did you based the proofs on that? If yes, why are you instead using Rademacher complexities?", "limitations": "I do not see any potential negative societal impact related to this work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The authors address a topic that is interesting in a formal and rigorous way. \n\nThe paper is written in a quite clear way. ", "weaknesses": "Some bounds given by the authors, especially those related to the Rademacher complexities, and also Sec. 4 and Sec. 5 should be simplified more in my opinion in order to make them more readable. \n\nThe authors did not provide computational experiments testing the performance of the proposed method in the main body.\n\nThe authors adapt optimistic rates present in literature for the single-task setting in order to get their optimistic bounds for representation learning. I wonder if the theoretical contribution is enough for the venue. I would like to better understand which are the main technical difficulties the authors had to face to adapt the optimistic bounds from the single-task to the multiple-task setting. \n\nSome basic gradient based representation-learning references are missing, such as [1-2] below. \n\nReferences\n\n[1] Denevi et al. \"Online-within-online meta-learning.\"\n\n[2] Khodak et al. \"Adaptive Gradient-Based Meta-Learning Methods.\"\n\n", "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---\n## Our theoretical contribution and technical difficulties\nWe see our work as foundational, extending our understanding of multi-task representation learning. For a more complete discussion recall our Section 1.1 - Our techniques, dedicated to `\"provid[ing] an overview of techniques and challenges overcome in the context of prior art.\" However, perhaps this is best emphasized visually, in working towards proving our main MTRL result - see Fig. 1., the proof graph - we have provided many necessary improvements and generalizations to build towards our final MTRL rates.\n\nThe main technical contributions are, (a). extending core concentration inequalities tools to the general MTRL setting, (b). bounding the local Rademacher complexity.\n* **Concentration inequalities.**\nMost of the existing tools and techniques in learning theory focuses on the single task setting. In order to show our results we need concentration inequalities which apply to the MTL setting, however these results do not trivially extend to the MTL setting. Indeed, as [YLK+18] observed, the difficulties in deriving MTL results are foundational, going back to a Bennett like inequality for the suprema of empirical processes (our analog is Thm. 7). From here we developed foundational analogs, e.g. Thm. 6, of the single task local Rademacher complexity results applicable to a MTL setting. We believe this theorems are of independent interest.\n* **Optimistic rates for non-negative smooth losses.**\nPart of the proof in [SST10] first bounds the covering number by its fat-shattering dimension and then bounds the fat-shattering dimension by the Rademacher complexity. This works well in the standard single task setting. Yet, there are no analogs we know of for the fat-shattering dimension of the multi-task function class. Herein lies the weakness of applying this approach, whereas our approach uses the Gaussian complexity which is a much more general notion of complexity. Besides the generality of our proof technique, which achieves better rates even in the single task setting, our contribution is a more simple proof.\n* **Mistakes.**\nFinally, in the process of developing the tools which are needed for the MTL setting we have identified various errors within the literature. First, while seminal and foundational, the proof within [SST10] has some minor flaws, in an effort to correct the literature we included those within Appx F.1. Concretely, a fat-shattering inequality is used in the wrong direction, there is an assumption between parameters which is not specified, there is a missing term when converting between Rademacher complexity and width, finally the process is not centered which is required in order for the second moment within the upper limit of integration of Dudley's integral to be bounded. Second, we failed to generalize Lemma 17 to bounded and possibly negative functions see footnote 5 on page 27. Finally, while not a mistake, we clarify the literature w.r.t. a comment made within [YLK+18] about achieving the same constants within a single task setting, see lines 344-356.\n\n---\n## Regarding Assumption 1 Lipschitz and the boundedness\n\nOur main result, Thm. 1, actually *only* uses Assumption 1.1., boundedness and non-negativity of the loss. We will change the writing to indicate this. This gives a bound in terms of fixed points of the local Rademacher complexities. Under the additional assumption of smoothness, we can further bound the fixed point. Finally, under the additional assumption of the Lipschitzness of the predictor class $\\mathcal{F}$ and the boundedness of $\\mathcal{F}\\circ\\mathcal{H}$ we can give a more interpretable bound in terms of their individual complexities via the Gaussian chain rule. Concluding, we would like to emphasize that these are standard assumptions, including the non-negativity and boundeness of loss, in learning theory, for instance, see [BBM02, SST10, TJJ20].\n\n---\n## Regarding references [1-2]\n\nThank you for these references. While these indeed bear similarities to our setting, there are crucial differences, which makes them incomparable. These include, a generative model of tasks in the mentioned papers, which we don't have, as well as the assumption of convexity therein (which we understand is made for computational reasons). We will add a discussion to this effect in the revised version.\n\n---\n## Regarding transfer learning vs. meta-learning\n\nWe are interested in the problem of transfer learning by learning a common representation from multiple source tasks. The most related work is [TJJ20] so we decided to remain within their discourse and reuse their terminologies. We note that the setting of multiple sources tasks has appeared even in many earlier works on transfer learning, for instance, [Bax00]. However, there are indeed many similarities between our setting and the ones mentioned by the reviewer.\n\n---\n## Regarding the task similarity assumption\n\nThe task similarity assumption has been studied in prior works, for instance [TJJ20]. Our main focus is to understand whether under this standard assumption, we can achieve fast rates, such as those in single task settings. However, in the special case of a linear representation class, the assumption recovers the task diversity assumption within many prior works, such as [DHK+20, TJJ21] and is similar to the one mentioned by the reviewer.\n\n---\n## Gaussian vs Rademacher complexity\n\nWe assume you mean Gaussian complexity? A side-by-side comparison between our proof and the one within [SST10] shows that although they start similarly, with Dudley's theorem, they soon diverge substantially. The biggest reason is that there exists results in terms Gaussian complexity for which there are no known Rademacher complexity analogs. Nevertheless, since Gaussian and Rademacher complexities are related, so it is possible to state all the results in terms of Rademacher complexity."}, {"review_id": "awo2GBkxKc", "reviewer": "Reviewer_BPxZ", "summary": "This paper aims to examine the optimistic rates for multi-task representation learning. The authors illustrate that the rate may be faster than the standard rate, depending on the complexity of the learning tasks. The analysis comprises multiple theoretical contributions.", "questions": "1. Can you explain the distinction between multitask learning and multitask representation learning? Typically, MTL involves acquiring shared representation layers, which serve as the objective for MTRL.\n\n2. What is the significance of optimistic rates in MTRL, and how does it manifest in real-world situations?\n\n3. Could you offer an intuitive definition of task diversity as it pertains to definition 2?\n\n", "limitations": "1. Assumptions are too strong.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The theoretical analysis sounds solid from my perspective. However, I am not an expert in this area and haven't gone through all the supplementary material. I would like to refer to other reviewers in the discussion period.\n\n2. The authors provide detailed comparisons with other theoretical works and expand on the key contributions, helping to understand the critical points of this work better. However, it is still hard to understand the details for readers not in this field. ", "weaknesses": "1. The assumption 1 regarding the boundness of the loss function and its gradients is too restrictive, particularly since the feature domain is not bound.\n\n2. Although the paper presents new findings in this field, it lacks a thorough explanation of the significance of these results.\n\n3. No conclusion section.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your questions, suggestions, and appreciating our contributions.\n\n---\n## Regarding the assumptions on the loss function\n\nOur main result, Theorem 1, actually only uses Assumption 1.1., boundedness and non-negativity of the loss $\\ell$. We will change the writing to indicate this. \nFor the subsequent results, we assume that the gradient is Lipschitz (i.e. loss is smooth), but this does not preclude the gradient from being unbounded.\nWe note that these assumptions are standard and borrowed from prior works in (single-task) learning theory such as [SST10]. \n\n---\n## About a conclusion section\n\nWe will add a conclusion section in the revision.\n\n---\n## Regarding the distinction between MTL and MTRL\n\nMTL is more general than MTRL. MTL is about learning several tasks simultaneously. This is not limited to procedures which learn a common representation for all tasks, which is the case for MTRL.\nFor an example of work which is MTL but not MTRL see [MP04].\n\n[MP04] - Micchelli, C., \\& Pontil, M. (2004). Kernels for Multi--task Learning. Advances in neural information processing systems, 17.\n\n---\n## Significance of optimistic rates in MTRL\n\nThe pursuit of optimistic rates is motivated by practice. In many settings, while we can prove only a rate of $1/\\sqrt{n}$, it is observed in practice that the error converges at a faster rate. This is typically for the tasks that we can learn with good accuracy, which is often the case. This is what we observe in transfer learning and what we hope to understand through optimistic bounds here.\n\nThe optimistic rates for MTRL that we provide show that with smooth losses, standard two-stage ERM can automatically adapt to the problem instance (both for the source tasks and the target task). As a result, we can interpolate from the standard rate of $\\mathcal{O}(\\frac{1}{\\sqrt{nt}} + \\frac{1}{\\sqrt{m}})$ to the fast rate $\\mathcal{O}(\\frac{1}{nt} + \\frac{1}{m})$.\n\nAlso, note that in practice, we typically use a fairly complex class for learning the representations (e.g., multilayered neural networks) and a simpler one for the predictor (e.g., linear functions). Therefore, the price we pay for $\\epsilon$-excess risk for the target task with the MTRL is $\\frac{C(\\mathcal{F})}{\\epsilon}$ as compared to $\\frac{C(\\mathcal{F} \\circ \\mathcal{H})}{\\epsilon}$; this can yield significant gains as the former is much smaller. This result further emphasizes the provable benefits of pooling data from multiple tasks for transfer learning.\n\n---\n##  Intuition for task diversity assumption\n\nIntuitively the task diversity assumption assumes that the ratio of the excess risk of the target task and the excess risk of the source task is well-behaved, i.e. the ratio is $O(1)$. \nIn other words, for any representation, excess risk w.r.t. the best predictors for the target task is upper bounded by the excess risk of the source tasks w.r.t. the best predictors for the source tasks. \nFor example, when in the linear case this is when the source tasks span $\\mathbb{R}^d$ and therefore are able to \"learn\" a target task in all directions (e.g. see [DHK+20]). \nWe have a high-level discussion on this assumption within Appendix B - Task diversity digression section.\n\n---\n## Regarding our assumptions\n\nAll our assumptions are standard in learning theory -- see for instance the foundational work of [SST10], in the single-task smooth loss setting, and the work of [TJJ20], in the multi-task Lipschitz loss setting."}, {"review_id": "LjqZWkbOqp", "reviewer": "Reviewer_9335", "summary": "This paper shows novel statistical rates for generalizing to a target task via multi-task representation learning (MTRL) that attain the optimistic 1/nt + 1/m rate, where n is the number of samples per source task, t is the number of source tasks, and m is the number of samples per target tasks, when the optimal source and target risks achievable by the representation and predictor function classes are small. This is an improvement over the previous state-of-the-art rate of 1/rt(nt) + 1/rt(m), and matches the analogous optimistic rate in the single-task setting. Key to the results are novel technical contributions extending local Rademacher complexity analysis to the multi-task setting. ", "questions": "N/A", "limitations": "Yes", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. The results are a very significant contribution in my opinion -- the established rates significantly improve over previous state-of-the-art in the near-realizable setting. Indeed, the near-realizable setting is important to consider. All assumptions are reasonable and consistent with prior work. Broadly, multi-task representation learning is an important research area. \n \n2. The analysis is rigorous, there are no mistakes in the proofs to my knowledge. From my understanding, substantial technical innovation is required to achieve the results by extending the local Rademacher complexity framework to the multi-task setting.\n\n3. The paper is very well-written.", "weaknesses": "1. The Related Works section should also compare with [XT21].", "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 contributions.\nRegarding [XT21], thank you for pointing us to this work --  we will add a discussion as suggested, in the related work section."}, {"review_id": "sn49dTnTuV", "reviewer": "Reviewer_JPW9", "summary": "This work studies multitask representation learning for some (general) function hypothesis classes. The estimators correspond to the composition of a \"complex\" function $h$ (corresponding to the shared representation) and a specific task regressor $f_i$ from a simple hypothesis class. This work aims at bounding the excess transfer risk of the ERM estimator. It extends the bound of Tripuraneni et. al (2020) to optimistic rates. More precisely, the square root bounds of Tripuraneni et. al (2020) are improved to linear bounds when 0 risk solutions exist on every task (e.g. no label noise). To do so, the authors do not need to assume the loss to be Lipschitz, but instead need to assume it is smooth (Lipschitz derivative).\n\n-------\n\nI acknowledge having read the author's rebuttal. The authors answered some of my concerns as explained in the comments below.", "questions": "See weaknesses section above.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Getting optimistic rates for multitask learning is a nice improvement wrt previous bounds on transfer excess risk.\nThe obtained bound is quite general. Notably, the setup and results are well put in the context of the literature, easily relating this result to previous one.", "weaknesses": "My main concern is about the current writing of the paper. First of all, I think it deserves a few careful proofreading, as many typos or grammatical errors can be found. Here are a few examples:\n - l. 108: \"we can reuse of\"\n - l. 118-119:  \"is bound\", \"is bound by\"\n - l. 161: I think there is a j subindex missing in the last sum in both the definition of $Pf$ and $P_n f$\n - l. 192: \"In order for there to be any value to learning\" -> weird phrasing\n - l. 198: I guess it should be $f^*$ and $\\hat{h}$ instead of $f$ and $h'$\n\nAlthough these typos are not significant in many sentences, they bring confusion when they appear in definitions (lines 161 and 198). More generally, I find the mathematical content to be quite technical and hard to follow. Some claims are confusing if not inexact. \nFor example the setting described line 171 *does not* imply that $f_j^{\\star}\\circ h^{\\star}$ is the optimal predictor. The same claim indeed also holds for $\\frac{1}{2}f_j^{\\star}\\circ h^{\\star}$. I think the authors should here introduce the setting similarly to Tripuraneni et al (2020), saying that $f_j^*$ and $h^*$ are in the hypothesis class.\n\nAlso, some notations are heavy/confusing, making the technical content (which is already hard to follow by definition) very hard to get. As an example, the variable $q$ in the equation line 204 represents both an integer and functions. In Theorem 1, it is not clear what $\\psi$ exactly is. I find the whole $r_1^*$ and $r_2^*$ quite cumbersome: I would have preferred to directly state Theorem 1 with the bounds on these quantities provided in Theorem 2. More generally, the whole Section 3 is hard to understand. I think that illustrating the obtained results in the particular case of the linear representational model would help the reader.\n\nAs a last concern, the current seems like an incremental improvement of Tripuraneni et al (2020), with tools leading to optimistic rates, that are mostly inherited from Srebro et al (2010). Even though the authors claim in the introduction that Srebro et al's tools cannot be directly used to MTL, the difference seems to be tenuous and only be due to bounding the Rademacher complexity.\nAlso, the authors might provide more motivation regarding optimistic rates.", "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 contributions. Regarding the typos pointed out and suggestions, we appreciate the careful reading and have made corrections in the revision. \n\n---\n## About the setting with the optimal predictor \n\nWe thank the reviewer for the suggestion. Indeed, from the assumptions, the optimal predictor is only guaranteed to depend on $x$ via $f_j^*\\circ h^*$. We have revised the sentence as suggested by the reviewer.\n\n---\n## Regarding $q$ notation on line 204\n\nNote that $q$ is an integer and $q_j(\\cdot)$ is a function. However, we will modify the notation emphasize this difference. \n\n---\n## About $\\psi$ within Thm. 1\n\nWe will clarify that it is *some* subroot function of $r$ which bounds the local Rademacher complexity. \n\n---\n## For $r_1^*$ and $r_2^*$ notation\n\nOur main result, Theorem 1, actually *only* uses Assumption 1.1., boundedness and non-negativity of the loss function $\\ell$. We will change the writing to indicate this. This gives a bound in terms of fixed points of the local Rademacher complexities.\nFinally, under the additional assumption of smoothness of the loss,  Lipschitzness of the predictor class $\\mathcal{F}$ and the boundedness of $\\mathcal{F}\\circ \\mathcal{H}$ we can give a more interpretable bound on the fixed point in terms of their individual complexities via the Gaussian chain rule.\nHence, stating the result in terms of $r_1^*$ and $r_2^*$ is required for generality.\n\n---\n## About including a linear representation example\n\nThat is a great suggestion; we will indeed include this in the final version.\n\n---\n## Regarding our contribution w.r.t. prior works\n\nWe see our work as foundational, extending our understanding of multi-task representation learning. For a more complete discussion recall our Section 1.1 - Our techniques, dedicated to `\"provid[ing] an overview of techniques and challenges overcome in the context of prior art.\" However, perhaps this is best emphasized visually, in working towards proving our main MTRL result - see Fig. 1., the proof graph - we have provided many necessary improvements and generalizations to build towards our final MTRL rates.\n\nThe main technical contributions are, (a). extending core concentration inequalities tools to the general MTRL setting, (b). bounding the local Rademacher complexity.\n* **Concentration inequalities.**\nMost of the existing tools and techniques in learning theory focuses on the single task setting. In order to show our results we need concentration inequalities which apply to the MTL setting, however these results do not trivially extend to the MTL setting. Indeed, as [YLK+18] observed, the difficulties in deriving MTL results are foundational, going back to a Bennett like inequality for the suprema of empirical processes (our analog is Thm. 7). From here we developed foundational analogs, e.g. Thm. 6, of the single task local Rademacher complexity results applicable to a MTL setting. We believe this theorems are of independent interest.\n* **Optimistic rates for non-negative smooth losses.**\nPart of the proof in [SST10] first bounds the covering number by its fat-shattering dimension and then bounds the fat-shattering dimension by the Rademacher complexity. This works well in the standard single task setting. Yet, there are no analogs we know of for the fat-shattering dimension of the multi-task function class. Herein lies the weakness of applying this approach, whereas our approach uses the Gaussian complexity which is a much more general notion of complexity. Besides the generality of our proof technique, which achieves better rates even in the single task setting, our contribution is a more simple proof.\n* **Mistakes.**\nFinally, in the process of developing the tools which are needed for the MTL setting we have identified various errors within the literature. First, while seminal and foundational, the proof within [SST10] has some minor flaws, in an effort to correct the literature we included those within Appx F.1. Concretely, a fat-shattering inequality is used in the wrong direction, there is an assumption between parameters which is not specified, there is a missing term when converting between Rademacher complexity and width, finally the process is not centered which is required in order for the second moment within the upper limit of integration of Dudley's integral to be bounded. Second, we failed to generalize Lemma 17 to bounded and possibly negative functions see footnote 5 on page 27. Finally, while not a mistake, we clarify the literature w.r.t. a comment made within [YLK+18] about achieving the same constants within a single task setting, see lines 344-356."}]

Author rebuttal:

Meta-review: This paper shows novel statistical rates for generalizing to a target task via multi-task representation learning (MTRL) that attain the optimistic 1/nt + 1/m rate, where n is the number of samples per source task, t is the number of source tasks, and m is the number of samples per target tasks, when the optimal source and target risks achievable by the representation and predictor function classes are small. This is an improvement over the previous state-of-the-art rate of 1/sqrt(nt) + 1/sqrt(m), and matches the analogous optimistic rate in the single-task setting. Key to the results are novel technical contributions extending local Rademacher complexity analysis to the multi-task setting.

All reviewers believe this paper makes valid contributions to the community. The AC agrees and recommends acceptanc.
Decision: Accept (poster)