Identification of Negative Transfers in Multitask Learning Using Surrogate Models
Authors: Dongyue Li
Huy Nguyen
Hongyang Ryan Zhang
Venue: Accepted by TMLR ()

Abstract: Multitask learning is widely used in practice to train a low-resource target task by augmenting it with multiple related source tasks. Yet, naively combining all the source tasks with a target task does not always improve the prediction performance for the target task due to negative transfers. Thus, a critical problem in multitask learning is identifying subsets of source tasks that would benefit the target task. This problem is computationally challenging since the number of subsets grows exponentially with the number of source tasks; efficient heuristics for subset selection does not always capture the relationship between task subsets and multitask learning performances. In this paper, we introduce an efficient procedure to address this problem via surrogate modeling. In surrogate modeling, we sample (random) subsets of source tasks and precompute their multitask learning performances; Then, we approximate the precomputed performances with a linear regression model that can also be used to predict the multitask performance of unseen task subsets. We show theoretically and empirically that fitting this model only requires sampling linearly many subsets in the number of source tasks. The fitted model provides a relevance score between each source task and the target task; We use the relevance scores to perform subset selection for multitask learning by thresholding. Through extensive experiments, we show that our approach predicts negative transfers from multiple source tasks to target tasks much more accurately than existing task affinity measures. Additionally, we demonstrate that for five weak supervision datasets, our approach consistently improves upon existing optimization methods for multi-task learning.

Published in Transactions on Machine Learning Research (03/2023)
Identification of Negative Transfers in Multitask Learning Using Surrogate Models
Dongyue Li Northeastern Universily, Boston
li. H.dongyu&Chortteesller...c edu
Huy L. Nguyen Northeastern University, Boston
hw..gggucn@hhorttcsstee...t
Hongyang R. Zhang
lo. ho..hhangghootthesssevv.cccm
Northeastern Universily, Boston
Reviewed on OpenReview: https: openreview. net/ forun? id= FgFFAI9933
Abstract
Multitask learning widely used in practice to train a low-resource target task by augmenting it with multiple related source tasks. Yet, naively combining all the source tasks with target task does not always improve the prediction performance for the target task due to negative transfers. Thus, a critical problem in multitask learning is identifying subsets of source tasks that would benefit the target task. This problem is computationally challenging since the number of subsets grows exponentially with the number of source tasks; efficient heuristics for subset selection does not al always capture the relationship between lask subsets and multitask learning performances. In this paper, we introduce an efficient procedure to address this problem via surrogate modcling. In surrogate modeling, sample (random) subsets of source tasks and precompute their multitask learning performances; Then, approximate the precomputed performances with a linear regression model that can also be used to predict the multitask performance of unseen task subsets. We show theoretically and empirically that fitting this model only requires sampling lincarly many subsets in the number of source lasks. The fitted model provides a relevance score between each source task and the target task; We use the relevance scores to perform subset selection for multitask learning by thresholding. Through extensive experiments, transfers from multiple source tasks to target tasks much more accurately than existing task affinity measures. Additionally, we demonstrate that for five weak supervision datasets, our approach consistently improves upon existing optimization methods for multi-task learning.
show that our approach predicts negative
1 Introduction
Multitask learning (MTL) is an approach to combining several lasks logether and learning one model for all tasks simultaneously (Caruana, 1997). The premise is that by combining the data samples of several tasks together, the dataset size of each task increases, thus improving the learning performance for every task. However, naively using all the source (asks may worsen performance compared to single-task learning (STL) for target tasks if there exist source tasks that are unrelated to them. This problem is commonly referred to as negative transfers in the literature but is challenging to predict for many tasks (Rosenstein et al., 2005).
The importance of developing a better understanding of multiple learning performance is well recognized. In the seminal work of Caruana (1997, Chapter 3), heuristics for judging "task-relatedness" applications are discussed; For instance, tasks that share many input features are more likely to be related to each other. A classical result by Ben-David et al. (2010) introduces an H-divergence notion that quantifies the distance between two label distributions and relates the bias of source domains to this notion. MTL
several

---

Published in Transactions on Machine Learning Research (03/2023)
S1
S2
6g
k
k
Sampling Random Subsets
Computing MTL Performance
Using Relevance Scores to Select Source Tasks
Step Constructing the Model: 0 argmin n (8x - -(())
Step 2. Selecting Source Tasks: = (c. (. < <r/v
1,2, "..
Our approach involves two steps, as shown in the figure above. In the first step, we sample random subsets of source tasks among k source tasks. Let these random subsets be denoted as S2. Sn. For from 1 up to n, we train an MTL. model using the combined data of all the tasks in S; and the target task. We evaluate the loss of this MTL model on an evaluation set from the target task and denote the evaluation loss as f(S.). Then, we train a linear regression model to estimate the relevance scores 81, o...... minimizing the mean squared error between go (S.) = Ejes, 0g and ((S)), as shown on the left. Let the estimated scores be denoted as θ = 02.00..... 0g). To predict the MTL performance of any unseen subset S, we compute (g(S) = Eies 0g. In the second step, we perform subset selection by choosing any task whose relevance score below a threshold 7: We choose this selection criterion by examining the subset S that minimizes (5) Ejes Sies0 0g, as shown in the right. figure.
Figure 1:
...... 88, by
may perform worse than STL if the bias is too large. In wuakly-supervised learning, several programmatic labeling functions are used to annotate corpus of unlabeled data, and each labeling function can be treated as source task (Ratner et al., 2016). The task labels can be highly noisy, causing negative transfer during training even though the tasks share the same input features (Ratner et al., 2019). In multitask learning of text prediction tasks, negative transfers are observed between different categories of tasks (e.g., question answering vs. soquence labeling) and different sizes of datasets (Vu ct al., 2020).
Motivated by the need to reduce negative transfers between different. tasks, researchers have developed optimization methods for multi-task learning from various fields. The most thorough approach to addressing these issues is to train all possible combinations of source tasks with the target task and find which subset of source tasks improves performance on the main larget task. If there are ht source lasks, then this approach requires training 2* MTL models. This is impractical (e.g,, when & 2 20). more efficient solution is to train combinations of every single source task with the target task to determine one task helps and then merge the helpful tasks together. This approach captures pairwise transfers, which measures first-order task affinities from one source task to another task (Fifty et al., 2021). Regarding higher-order transfers from multiple source tasks to another task, approximation techniques such averaging the first-order affinity scores of each source lask have been explored (Slandley et al., 2020).
This paper designs and analyzes a scalable approach to identify negative transfers from multiple source tasks to one target task. The key idea is to construct a surrogate model to approximate the MTL performance of a subset of source lasks combined with the larget lask. Compared with prior works that measure task-relatedness based on either gradient similarity (Yu et al., 2020) or feature space alignment of neural networks (Nguyen et al., 2020; Raghu et al., 2020; Wu et al., 2020), negative transfers from a set of lasks to another task. It also differs from existing discrepancy notions (e.g., H-divergence) between source and target domains, which are difficult to measure for deep neural networks. Our approach builds on a recent paper that designs datamodels to predict the predictions of deep neural networks trained on a subset of training data (Iyyas et al., 2022). Unlike their work that focuses on single-tase taak learning, we build surrogate models for multi-lask learning with deep neural networks.
approach can be used to identify
The first step of our approach involves learning a relevance score between every source task and the target task while accounting for the presence of the other source tasks. Let 6, denote the relevance score of task for i from 1 to k where & is the total number of source tasks. Conceptually, 0 is analogous to the important
2

---

Published in Transactions on Machine Learning Research (03/2023)
score of a feature in random forests when hundreds of other features are available. To estimate the relevance scores, we introduce a surrogate model (o)),, parametrized by the relevance scores 0, to approximate MTL. performances. Given any subset of source tasks S, lct f(5) be a loss function that measures the performance of combining S and the larget lask to train an MTL model and then evaluated on the larget lask. The value of f(S) provides a relevance measure between S and the target task. Recall that O measures the relevance of task to the target task. Thus, a lower value of 0g indicates a higher relevance of task i to the target task.
We specify linear surrogate model as go = Ejes Oj (parametrized by the relevance scores) and minimize the mean squared error between go (S,) and f(S.) over n random subsets, for i from 1 to n. In particular, we precompute the values of f(S)). ((S))...... f(S,) by training one MTL model for each subset. We use such a linear specification of I because computing the performance of each subset requires training an MTL model, which is not scalable unless n grows almost. linearly in k. In addition, we take inspiration from the recent work on datamodels (Ilyas et al., 2022), which shows that a linear regression model can extrapolate the predictions of deep neural networks for subsets of training data. We rigorously analyze the sample complexity of our approach in Theorem 2.1. After fitting 0, we predict the performance of an unseen subset S as g)( and compare it with the STL performance of the target task to determine if S provides a negative transfer.
The second step of our approach involves selecting a subset of source lasks by choosing any source task whose relevance score is below a threshold y. We derive this selection criterion by examining the minimum of the surrogate model (o) over all possible subsets S. We analyze this algorithm in a sctting that includes one group of source tasks closer to the target task and another group further from the larget task. The analysis reveals that for each task i, its relevance score 02 is proportional to the sum of the MTL performances of all subsets that include i. Moreover, these performances preserve the distance gaps from the source tasks. See Theorem 3.1 for the precise result. In practice, we pick via cross-validation; See Section 4 for the range of y that we validate on in the experiments. Taken together, our approach provides an efficient pipeline to predict and optimize multitask learning performances for task subsets. See Figure for an illustration.
Experimental Results. We conduct extensive experiments to validate our approach in numerous data modalities and performance metrics. We summarize a list of our results as follows:
The runtime for constructing surrogate models until convergence scales lincarly in k, and the predicted performances accurately fit the true MTL performances of unseen subsets, measured by Spearman's 's correlation (0.8 averaged among 16 evaluations). Our approach achieves 4 times higher accuracy for predicting positive vs. nogative transfers than known approximation schemes, measured by the Fi-score.
By selecting source tasks based on the predicted MTL performances and only using the selected source tasks, we observe consistent benefits over existing optimization methods. We evaluate our approach on many datasets, including weak supervision, NLP, and multi-group fairness. In addition, we apply our approach to different MTL encoders, including BERT and multi-layer perceptrons. Notably, we consider a weak supervision dataset with as many as 164 labeling functions (Zhang et al., 2021). By selecting labeling functions with our approach and then applying MTL, we obtain up to 3.6% absolute accuracy lift compared with existing methods.
We further visualize the tasks selected by our approach and find a scparation between the selected tasks in terms of their labeling accuracies. Besides, our approach can also be used in scenarios where multiple groups of heterogeneous subpopulations are present. We are interested in the fairness and robustness of the learned model, measured as the performance of the worst-performing group. We apply our MTL framework as an augmentation to expand the dataset size of the worst-performing group and show consistent, empirical performance in the worst-group accuracy metric.
Summary of Contributions. To summarize, this paper makes three contributions to studying negative transfers in multi-task learning. First, we study the higher-order task relationships from a set of source tasks to another task. We meta-learn such relationships using a linear regression method that can also predict an unseen subset's MTL performance. Second, we design a subset selection criterion for multi-task learning, which adjusts a threshold on the averaged MTL performances of subsets of tasks. Compared with the existing literature, our approach is better at predicting higher-order task relationships (See Figure 3 in Section 3 for the detailed result). Third, we validate our approach with extensive theoretical and experimental results.
3

---

Published in Transactions on Machine Learning Research (03/2023)
Organization. We describe the problem setup and the surrogate model in Section 2. use the relevance scores to perform subset selection for multitask learning. We present the experiments in Section 4. Then, we discuss the related works in Scction 5. Lastly, we summarize the paper in Section 6. The appendix provides complete proof of our theoretical results and omitted results from the experiments.
In Section 3, we
2 Predicting Multitask Learning Performances Using Surrogate Models
This section describes the design and analysis of surrogate models for multitask learning, We begin by defining the problem setup. Then, we describe the construction of surrogate models and the cstimation of the relevance scores. Lastly, we analyze the sample complexity of the constonction procedure.
2.1 Preliminaries
Problem Setup. Let t = 0 denote the main target task of interest. Suppose the task's features and labels are drawn from an unknown distribution, denoted as D,. Let X' denote the feature space. Let the set of all possible labels be denoted as y. We are given a dataset, which includes a list of examples drawn independently from D,. Besides, we are also given datasets from related source tasks, which all supported on X y.
A naive approach to optimize MTL is combining all the datasets and evaluating the trained model on the target task. However, this might result in worse performance than single-task learning. Thus, it is crucial to identify if a source task would help or hurt. The most thorough solution for addressing this question is by enumerating all possible combinations of source tasks, leading to a total of 2$ combinations. For cach combination of source lasks, train a multitask model using the selected source tasks and the main lask. While this procedure optimizes the performance of MTL, it is too slow for large
How can optimize the performance of MTL efficiently? Relatedly, given set of source tasks, we predict their transfer effects upon the largel task efficiently? Below, we define two common transfer effects.
Positive vs. Negative Transfer. Consider any multitask learning algorithm, denoted as A, which trains a joint model given any set of tasks. For any subset S S {1, 2.......kk k), we say that S provides a negative transfer to & if the performance of A(S U (()) worse than A((1)) (e-g., in terms of higher loss values). Likewise, we say that S provides positive transfer to t if the performance of A(S (t)) is better than A((I)). We aim to design a scalable method to predict such positive and negative transfer effects.
It is worth highlighting that both types of transfers are often observed in practice. To give an example, we consider a binary classification datasct that involves total of 51 tasks. We pick one of them as the target task, use the rest as source tasks, and consider the case where |S| = 1. This leads to training 50 models for each target task, one for every combination of one source task and the target task. The results are shown in Figure 2, which provides illustrations for four different target tasks. The y-axis corresponds to the accuracy difference between the MTL and STL results. We consistently find a mix of positive and negative transfers for all four larget lasks.
Surrogate Models. A recent paper by llyas et al. (2022) designs linear regression method to predict the predictions of deep neural networks trained on subset of training data. Surprisingly, an empirical finding from that paper is that this linear regression model provides a very good fit. on a number of popular benchmark datasets such as CIEAR. This finding is later explored by another recent paper (Saunshi et al., 2022). We defer further discussions the related works in Section Both of these works focus on single-task supervised learning. Next, we will apply this idea of linear surrogate models to multi-task learning.
2.2 Constructing the Linear Surrogate Model
First, we construct a surrogate model to fit multitask learning performances. Let be an encoder that is shared by all tasks. For any input features a E X, the encoder á maps x into a feature vector. For every source task in S and the target task, there is separate prediction layer for each of them. Let vo, th1, .2.,..,, .., thk denote the prediction layers, which map the feature vectors to the output.
4

---

Published in Transactions on Machine Learning Research (03/2023)
Target lask: III
Target task: LA
Target Lask: NV
Target task: SC
Ace. improvement (%6
Ace. improvenenn (9)
2
Acc. improvement (%)
2
CA
TX
GA
TX
CA
CA
PL
Acc. improvenenn
1
1-
NY
1-
M5
1-
CA
Source tasks
Souroe tasks
Source tasks
Source tasks
Figure 2: Illustration of mixed outcomes in multitask learning: In each ligure, we train 50 multitask models based on one fixed target task and one source task from 50 source tasks. æ axis: Each bar represents one source task from 50 source tasks. y axis: Test accuracy of MTL, with one source task minus the test accuracy of STL with the target task alone. For further description of the experiment sctup, see Scction 4.1.
Given any subset S, we train & and thi, for i E (O) by minimizing the average loss over the combined training data along with the target task. Let ((5) and w for i E S {0}, be the trained model. We evaluate its loss on the target task's validation dataset. Let D, = ((11.1().....).......))...))))))
(Im: ym)] denote a set of m independent samples from D,, which usod as a validation set for the target task. Let be a non-negative loss such the cross-entropy loss. We define mullilask learning performances as:
m (5)
S(S)
(x=)), wi): for any S S (1,2,...,Ak) k). m Σ (((b))
el
Our main idea is to construct a surrogate model, parametrized by a relevance score 0 for each source task We use a linear specification inspired by recent work of Tlas al. (2022)1
go = Σ 0i, where 0g is the i-th entry of 0, for any i = 1, 1,,,...,. k.
(2)
IES
The procedure for estimating is as follows. First, sample n subsets of source tasks from {1, 2,....,,, ......,, denoted as S2..,...., Sn. Sn. We sample each subset from the uniform distribution over subsets with a fixed size of os We will justify this choice later in Section 3.2. For instance, to capture the transfer from five source tasks to the target task, we can set = 5. Then, compute the value of f(S.) by training one MTL model for every = 1, 1,2,..., n. Lastly, minimize the mean squared error (MSE) between (S;) and f(S)), averaged over all i:
(0) = 1 ( )(
Let i denote the minimizer of the above MSE. For brevity, refer to i as the task model. After estimating 0, for an unseen subset of source tasks S, we predict its MTL performance ga(S)= Eies
2.3 Sample Complexity
We show that given n Ooklog can estimate å accurately. To be precise, let U denote the uniform kJ.
distribution over all subsets of size drawn from , Let T denote unseen subset drawn from U. The population risk for given 0 is defined as the expected MSE between f(T) and (T):
((0) EE [((T)) ((0))) ST
(T)))
(4)
Let the minimizer of the above risk be denoted as 6* We prove that Ô converges to 8 using Rademacher complexity-basel arguments. Let the function class of t/s and d be denoted as H. Let the loss function
We use this specification for scalability consideration. Note that it is possible to consider more complex specifications, 1.k- The construction procedure and the analysis is conceptually the same. However, the sample complexity for fitting these quadratic variables is O(k²), rendering it infeasible for large e.g., k 2 100.
such as adding quadratic variables 01.2,01.3... 1
5

---

Published in Transactions on Machine Learning Research (03/2023)
class be F= (((1)((())) y) Ver. & from Hj. Recall that D. = ((11((()))))))) (x2, v2), ................................ (Tmm fmm) refers to the dataset used to evaluate the value of S(T), and its size is equal to m. Let 01. ......... om be mn independent Rademacher random variables, collectively as oim- The Rademacher complexity of JF over D, is defined
Rm (F)
E
E 1mm
Σ of h( M(22 us) hEF
sup
(5)
where the expeclation taken over the randommess of the empirically-drawn dataset D. and the Rademacher random variables dim- We follow the convention of big- notations for stating the result. Given two functions h(n) and h (n), we use h(n) O(' (n)) or h(n) h ('(n) to indicate that h(n) S C hn(n) for some fixed constant C' when is large enough. Our result is stated formally below.
Theorem 2.1. Suppose the functions in F are all bounded from above by a fixed constant C O. Suppose is less than k/2.. Let be the ramber of sampled subsets and m be the size of the set used to evaluate f- With probability least 0.99, On converges to 0 as n, m are both large enough:
(A: log" (k)) +1
(log(k))aa m
f0- CV
+ (m,
(6)
n
where || denotes the Fuclideon norm of vector.
Based on the above result, is clear from equation (6) that provided with O log (k)) random samples, the first error term relating n shrinks a negligible value (one may think of as fixed constant such as or 10). There are two error terms decreasing with m, the size of DD used to evaluate f. The Rademacher complexity (F) is known to be of order 0(m 1122) when H represents family of neural networks (Bartlett. et al., 2017). These two error terms are due to the variance of f since is measured on finite set. Lastly, we note that the probability value of 0.99 in the above theorem statement can be adjusted to other values. the proofs, state the result more generally for any probability value 1 where 5 O; See the statements of Lemma 2.2 and Lemina 2.3 below for details.
Proof Overview. We introduce few notations to examine ga(S) and the covariance uf Let In E {0, 13,kk be a wero-one matrix; For any i = 1,2,..., n, the i-th is 1s, the characteristic vector of S,. Let f be a vector in which f. f(S),, for any = 1,2,...,m. n. The Ô that minimizes equation (3) is equal to
0= (Z, f.
Let J and let be the i-th entry of v, for i 1,...,k. k. Based on the definition of In, observe that
Ui Σ f(S;), for any 1 isisk k.
(8)
ISiSniiE,
Next, let I E {0, 13 x be zero-one matrix, where [4| is the number of subsets in U. Each row of I corresponds to the characteristic vector of subset. Let f be vector such that cach entry of this vector corresponds to the MTL performances (cf. equation (1)) of a subset in distribution U. The population risk minimizer 8* for reducing C(0) in equation (4) equal to
= [I -' I IT. R.f..
Our proof involves two steps. First, we deal with the error due to the randomness of the random subsets. Let
θ - II - II
We state the following result, which shows that e converges to n incrcases.

---

Published in Transactions on Machine Learning Research (03/2023)
Lemma 2.2. In the setting of Theorem 2.1, conditional on f(T) for any subset T E u, with probability 1-26 20 over the randomness of S2,S2.... S2...... , Sn, for any 6 2 0, the Euclidean distance between ô and 0 satisfies:
(k (1log"(266 + 8 ko 00 - 0 - 440V
(9)
ôn
The proof of the above result relies on novel union bound taken over all subsets in S, Crucially, there are most 2 subsets. By taking the logarithm of 2 after the union bound, get factor of as shown in equation (9). Second, we prove the convergence from I to 0*,
increases.
Lemma 2.3. the setting of Theorem 2.1, for any 8 0, with probability at least 8 over the rondomness of S1, , and [(S1), ... f(Sn), the Fuclidean distance between O and 0r satisfies:
Rm (F) V
(log (6-1k)) 4m
|00 0-1|
(10)
Combining Lemma 2.2 and Lemma 2.3 together, we have thus proved that equation (6) holds. The proof of the above two results can be found in Appendix B. This result justifics why we use a lincar specification, as we can scale up the sample complexity.
Remark 2.4. The proof of Theorem 2.1 uses the design of the a-sized subsets. In particular, the covariates of these a-sized su subsets are zero-one vectors, with the ones being drawn randomly. We show that the population covariance of all the a-sized subsets is an identity matrix plus a rank-one matrix. See equation (12) in Section for the derivation. This implies that the inverse of the covariance matrix is an identity matrix plus a rank-one matrix.
3 Subset Selection for Multitask Learning
Next, we design an algorithm to optimize the performance of the target task using the relevance scores of cach source task. We analyzo this algorithm a sctting whore the tasks are separated into two groups, with one group being more similar (measured by Euclidean distances) to the larget task than the other group.
3.1 Using Relevance Scores to Select Source Tasks
Provided with the surrogate model, we can optimize the target task performance by using the predicted MTL performances. A natural way is to select the subset that minimizes the value of 93(5) over subset S. Due lo the lincar specification of Jg. this is equivalent to selecting source tasks with small 0.- Thus, select source task if 0, below the desired threshold y, which can be determined via crossvalidation. Then, we train a model by combining the selected source tasks with the target task. The complete procedure shown below. We will rigorously justify the existence of threshold afterward.
Algorithm Subset Selection for Multi-Task Learning Using Relevance Scores
Input: & source tasks; Training and validation datasets of the target task. Require: Size each subset a; Number of sampled subsets nı; MTL algorithm f; Task selection threshold 7.
Output: Trained model o(55)) (1(")
For == 1,..., n, sample a random subset S, from (1.2....,k) with size ar evaluate f(S.) following equation (1).
2: Estimate the relevance scores 0 following equation (3).
3: Select source tasks based on their relevance scores: S* = {i : 0 < 1 1,2.... k.. k].
Train model by combining S* and t; denote the trained model as G(S"), and (8"))) for all i E S* U (t).

---

Published in Transactions on Machine Learning Research (03/2023)
3.2 Analysis of the Algorithm
We analyze the above procedure in a synthetic setting where the data is generated from a linear process. We assume that the input features for each task are drawn from an isotropic Gaussian distribution with p dimensions. For each task from 0 to k; let g E I denote the linear process for task i. Given a data point from task i with feature vector z, its label is generated as y = x ( + where is a random variable with mean 0 and variance o². Suppose there a, b such that b > a > 0. For every i I,...,R, k; task is called a good task if [| - ( S a; On the other hand, is bad task if [|8(9) - | 2 b. We show that there exists a threshold that separates good tasks from bad tasks, stated formally as follows.
two groups of tasks depending on their distances to ((0, given by
Theorem 3.1. In the setting described above, suppose f is bounded from above by a fixed constant C > O. Suppose there are d Z le klog + pp+ a² (a² -1) 172--2 n 2 (a² - b2)-2 and m Z plogp. With probability at least 0.99, there exists a threshold y such that
data points from every source and larget task. Suppose
For any i = 1, 1,2,....ku ,,, if lask i is a good lask; then O₂- <- Otherwise, if task is a bad task, then 0 >
The intuition behind the above result is that 0, averages the MTL performances of all subsets involving i. If is a good task, the average performance will be lower, leading to a lower relevance score. Morcover, there exists threshold that separates the relevance scores of good tasks and bad tasks. We give toy example illustrate why 0 can preserve the Fuclidean distance gaps from B. Our experiments later also confirm the existence of such separation (ef. Figure 5).
Example 3.2 (One-dimensional case). Consider one-dimensional case where p= 1 and every 3 is real value. Let g = 0. Let 0 < g(9 < a if i is good task. Let b < 30) if i is a bad task.
Our first observation is that 0 is proportional to % (cf. equation (8)), as shown in Lemma 3.3.
Our second observation is that i is proportional to 3(0), This is because is is the sum of f(S) among all S U involving i, and f(S) is the average of g0) among E S. Thus, v2 is the average of all I's from the n random subsets, while ((0) has larger weight in v than the other I's because is always in S.
Taken together, we conclude that the relevance scores can preserve the relative values of 3 in this example.
Proof Overview. We now generalize the intuition from the one-dimensional case, beginning with the first observation. We show that the relevance scores preserve the distance gap of every pair of tasks from B.
Lemma 3.3. In the setting of Theorem 3.1, with probability 1 1- 8, for any 8 0, the following holds:
1 0 8,) an (u; uz)) x
log(6-1k) for any ssicjsi Vn
(11)
n
The above result analyzes the covariance of In, which is proportional to identity plus constant shift. Let Id be a l by & identity matrix and e E & be vector whose entries are all equal to one. By the definition of In and Woodbury matrix identity, we have
I In
a Idxx
ala - 1) T E kik: - 1)
In In
k [ddxx ka - 1 ec )
E
(12)
n Io
n a
Crucially, if we multiply v on the right-hand side of equation (12), then we will get [ R- (e Tu)e). Recall that e is all one's vector, which has the same entry in every coordinate after rescaling. Then, recall 0 from equation (3). By matrix concentration inequalities, the spectral norm of the deviation from I.Z. to its expectation satisfies
I In
I In
a logg(k6))) 1) Vn
E
(13)
11
8

---

Published in Transactions on Machine Learning Research (03/2023)
See equation (20), Appendix B.1 for the proof. Thus, combining equations (12) and (13), we claim that 0 is equal to a o- minus a shared term for every task, modulo the deviation error of order Onn-1/2), By subtracting 0, Au; and 0 Uzz we can cancel out the shared term, leading to equation (11).
Next, we formalize the second observation from the one-dimensional case. Based on equation (8), 02 is a sum of f(S) for all subsets S such that E S. We then show that f(S) is the sum of 30) for all j É S, based on the pooling structure our MTL model. Thus, the Euclidean distance between g(0 and ((0) will also reflect in Us. For complete proof of Theorem 3.1 (and Lemma 3.3), see Appendix B.4. This result substantiates our intuition that O, provides the relevance score of each source task to the target task while accounting for the presence of other source tasks.
Remark 3.4. After identifying the related tasks from all the source tasks, we can then combine them together with the target task for multi-task learning. Given that the distance between their 3-coefficients is small enough (i.c., small enough), we can show that MTL. performs better than single-task learning.
4 Experiments
We apply our approach to three settings. The first setting is about applying weak supervision to unlabeled data, and we apply our algorithm to select labeling functions for combining the weak labels of the labeling functions. The second setting involves language prodiction tasks from NLP benchmarks. Again, we use our algorithu to select source tasks to improve the performance of target tasks. The third setting involves learning from multiple groups of heterogeneous subpopulations, where the goal is to train a model with robust performance across all groups. We cast this multi-group learning problem into an MTL framework and apply our algorithm to select subset of groups to improve the robustness of target tasks. For all these settings, we show that surrogate models can predict negative transfers accurately and fit. MTL performances well; Moreover, our approach provides consistent benefits over various optimization methods for multi-task learning. The code repository for reproducing our experiments can be found at https: Com/NEU-StatsMMl www----eeeaaccaa---ooeooo--
4.1 Experimental Setup
Datasets. First, we apply our approach to several text classification tasks from weak supervision dataset (Zhang et al., 2021). Each dataset uses several labeling functions to create labels for every unlabeled example. The labels generated by different labeling functions may conflict with each other. We view each labeling function as a source task. The goal is to predict an unlabeled set of examples which is viewed as the target task. validation dataset that includes the correct labels available for pross-validation We include the datasct statistics in Table
Second, we consider MTL with natural language processing tasks. We collect twenty-five datasets across a broad range of tasks, spanning sentiment classification, natural language inference, question answering, etc., from GLUE, SuperGLUE, Twee,Eval, and ANLI. We view one task the larget and the rest as source lasks. The goal is to select subset of source tasks for the best MTL performance. We provide the statistics of the twenty-five tasks in Table 4, Appendix C.1.
Third, we consider multi-group learning settings in which datasel involves multiple subpopulation groups. We consider income prediction tasks based on US census data (Ding et al., 2021). The goal is predict whether individual's income is above $50,000 using ten features, including the individual's education level, age, sex, etc. There are 51 stales in this dataset; we view each state one task. For prediction, one state as the target task and the remaining fifty states as source tasks. We use the racial group of each individual to split a state population into nine subpopulation groups. We evaluate the robustness of a model by the worst-group accuracy. This metric measures the accuracy of the worst-performing group among all groups. We use six states as the larget task. See Table 2 for dataset statistics.
use
We use a standard approach for conducting MTL, i.e., hard parameter sharing. For text classification, use BERT-Base with hidden size of 32. The surrogate modeling procedure requires three parameters: the size of subset,
Implementation.
the encoder. For tabular features,
fully-connected layer
9

---

Published in Transactions on Machine Learning Research (03/2023)
1.0%
1.0
Linear suroggate modeling
0.8
Higher-order appreximation
score
0.9
0.6
Finstoonker task affinity
0.8
0.4
0.7
0.2
First
Teat
0.6
0.0
Fifh
Twentieth
0.5
2
5
10
20
0
100
200
300
400
Figure 3: Left: Our approach can consistently predict /ntttiivee transfers from up to 20 source tasks to the larget task. Right: Convergence of surrogate models increases up to 400, leading to an Fi-score of 0.8 for predicting positive/negative transfers from up to 20 source tasks to one target task.
the number of samples, and the loss function. We select the size from a range between 3, 5. 10, and 15. We select the number of samples from a range between 50, 200, 400, and 800, depending on k. We also collect a holdout set of size 100 for constructing the surrogate model. For classification tasks, we set the loss function as the negative classification margin, i.e., the difference between the correct-class probability and the highest incorrect-clas probability. After estimating the surrogate model g from equation (3), we use g(S) as the predicted multitask loss for unseen subset S. We compare g(S) with the STL performance of task to determine whether the transfer from S to t is positive or negative. We measure the Fi-score for the minority class (between the positive and negative classes) on the holdout set.
4.2 Results for Predicting Negative Transfers
We validate that our fitted models can accurately identify positive negative transfers from source tasks. Then, we show that these models can be constructed efficiently by reporting the runtime.
Results. We test the accuracy of using surrogate models to predict positive vs. negative transfers. We first evaluate the four examples shown in Figure 2. We set the size of a as 5 and n as 400. Using the model compare the MTL performances with STL performances, we can correctly predict the transfers with an Fi-score of 0.82, averaged over the four larget tasks. Second, we conduct the same tests for weak supervision and NLP tasks. Similarly, we find that task models can predict positive vs. negative transfers with Fi-score of 0.8 on average for ten different target tasks.
Furthermore, we compare these results with two baselines that either compute first-order task affinity scores or higher-order approximations by averaging first-order affinity scores. Our approach yields much more accurate predictions across different subset sizes of a, ranging from up to 20. Figure provides the illustration for one target task, which is conducted on the US Census dataset, along with fifty source tasks.
Lastly, we measure Spearman's 's correlation between the predicted performances and true performances. We observe an average coefficient of 0.8 across 16 target tasks. See Appendix A for the details.
Computational Cost. Next, we report the runtime cost collected on an NVIDIA Titan RTX card. First, we show that the rumning time of our procedure scales lincarly with k, the number source tasks. Recall that our approach requires training n models, one for each random subset. We find that collecting n < 8k samples suffice for the fitted model to converge. The results hold for 16 target tasks shown in Figure of Appendix A. We plot the number of hours w.r.t. A in Figure 4. The results confirm our hypothesis.
100
Hours
10
20 10
50 100160 k
Our approach is also comparable with the baseline approaches. Among them, the most related ones compute first-order affinity scores and conduct a branch-and- bound search algorithm over the task space, which has exponential complexity in (Standley et al., 2020; Fifty al., 2021). In our experience, with more than 20 tasks, these methods take more than 200 hours. Our approach requires at most 145 hours. This is consistent with our theoretical predictions in Section 2. Later in Section 4.5, elaborate ways to speed up the training.
Figure 4: We show that the runtime of our approaches scales lincarly with k the number of source tasks.
10

---

Published in Transactions on Machine Learning Research (03/2023)
Table 1: Accuracy/FI-scort from surrogate modcling followed by task selection (ours), as compared with
MTL methods and weak supervision methods that use label model to aggregate the weak labels.
Dataset (Metries)
Youtube (Ace.)
TREC (Acc.)
CDR (F1)
Chemprot (Ace.)
Semeval (Ace.)
Training
1,586
4,963
8,430
12,861
1,749
Validation
120
500
920
1,607
178
Test:
250
500
4,673
1,607
600
# source tasks
10
68
33
26
164
Naive MTL
94.72+0.85
64.10+0.500
58.20++0.55
03.43:00.53
89.00=11.06
HOA
1..
74.67:+4.66
59.76++0.97
45.57+00.41
89.94+4.42
TAG
95.20:10.65
77.50:13.62
59.31+00.15
53.67
89.06
TAWT
94.53+1.05
72.40:22236
69.85:+-0.30
53. 76:22.99
86.83=1.78
Auto-A
95.80=0.885
73.70=0.67
59.07=00.05
02.50=11.28
87.91=0.66
Majority voting
95.3611..71
66.56.12.3
58.89100.50
57.32.10.98
85.0310.883
Probabilistic modeling
93,8411.61
68.64.33.57
58.48.10.73
57.00.11.20
83,9310.88
McTaL
92.3211.44
18.28:11.9
58.48:10.90
56.17:10.66
71.74:10.57
Alg. 1 (Ours)
97.47:10.82
81.80=1.14
61.22:00.99
57.54+00.55
93.50:10.24
4.3 Results for Improving MTL Performance
Next, we apply our approach to MTL on weak supervision and NLP tasks. We compare our approach with the following baselines. First, we consider training by naively combining all source and target tasks. Second, we consider bilevel optimization methods, including TAWT (Chen et al., 2022) and Auto-A (Liu al., 2022), and MTL optimization methods, including HOA (Standley et al., 2020), TAG (Fifty al., 2021). The latter two methods use branch-and-bound algorithm that does not scale to over 20 tasks in one dataset. To allow for comparison with them, we apply the thresholding procedure to their first-order task affinity scores to select source tasks. To set the threshold in our algorithm, we use grid search from -0.5 to 0.5 at an interval of 0.1. We choose this range because it covers the values of most coefficients in our experiments.
Multitask weak supervision. First, we apply our algorithm to five weak supervision datascts, which involve text classification from multiple weak labels. We select a subset of labeling functions so that using their weak labels to train end model best. improves performance on the target task. We also compare against methods that use a label model to aggregate the weak labels and then train an end model the aggregated label. These include taking a majority vote on the weak labels, applying probabilistic modeling to combine the noisy labels (Ratner et al., 2016), and MeTal (Ratner et al., 2019).
Next, we compare the experimental results, shown in Table 1. Compared with naively MTL, which trains all tasks together, our algorithm improves the test performance by 6.4% on average. Compared with MTL optimization and weak supervision methods, our algorithm outperforms their results by up to 3.6% absolute and 2.3% average.
Lastly, we examine the labeling functions se- lected by our approach. Recall that our proce- dure places a threshold over the coefficients to separate good and bad source tasks. Here, we use the number of correct and incorrect labels as a proxy of relatedness between a labeling function and the target task. Figure 5 shows the results, measured on two datasets, namely Chemprot and TREC. Each dot represents one source task. We observe a clear scparation be- tween selected and excluded source tasks when we compare the correct/ snreect/incorect labels each task. This shows that our algorithm selects more accurate labeling functions for multi-task weak supervision.
1500
600
Selected
Selected
Correct Jabels
Correct labels
Excluded
Excluded
1000
400-
500
200
0
500 1000 1500
100
200
300
Incorrect labels
Incorrect labels
Figure 5: We find that the selected and not-sclected source tasks are separated in terms of the number of correct labels provided by each source task versus the number of incorrect labels from each source task. Each dot represents one label- ing function.
11

---

Published in Transactions on Machine Learning Research (03/2023)
Table 2: Worst-group accuracics using MTL with source tasks selected by our algorithm, as compared
STL, MTL optimization methods, and exhaustive search over combinations of up to two source lasks.
Dataset
HI
KS
LA
NJ
NV
SC
Training
4,638
9,484
12,400
28,668
8,884
14,927
Validation
1,546
3,161
4,133
9,556
2,961
4,976
Test
1,547
3,162
4,134
9,557
2,962
4,976
Smallest group size
67
75
58
52
61
203
GroupDRO
74.56=0.58
75.50+0.59
74.90+0.38
76.95++0.20
73.06+0.66
75.56+ 1.36
Correct-n-oone -tcotrst
74.37+0.27
1..92+11.19
74.25+00.15
77.60++0.10
73.22+0.40
76.23+0098
Naive MTL
06.63:00446
75.22:40.73
73.2441.01
77.28:10.25
73.22+1.12
76.23 49
HOA
74.67=0.32
75.22+1148
73.69=0.88
77.49:10.25
73.88
76.80=0.66
TAG
74.48=0..11
1..97+1.18
73.24+1.01
77.41=00.48
74.05=0.844
76.41=0.50
TAWT
73.53
75.14.1..39
73.31
76.4711131
72.8910.88
76.5910..7
Exhaustive search (a $ 2)
75.10.10.37
77.03
73,6011..0
77.40.10.24
73.2111.10
77.16.10.21
Alg. (Ours)
75.47+0073
76.96:+0.69
75.62+00.1
78.17=0.36
75.21=0.52
77.62++0.34
NLP tasks. Next, we test our approach to NLP tasks. We collect 25 datasets from GLUE, SuperGLUE, EvellEval, and ANLL See Table 4, Appendix C.2 for complete list. We evaluate our approach by first selecting source tasks and then applying MTL. We test on five target tasks: CoLA, RTE, CB, COPA, and WSC. For each task, we use the rest 24 tasks as source tasks.
We first compare our approach with STL and naive MTL. We observe that naive MTL can perform worse than STL, e.g., on CoLA and WSC datasets. By contrast, our approach always outperforms STL (by 5.5%) and naive MTL (by 5.4%), on average. We then compare our approach with TAG and HOA. Our approach shows an average improvement of 2.2% and especially effective for tasks with a small training set.
4.4 Results for Improving Robustness in Multi- group Learning
We apply our approach to multi-group learning settings where the input distribution contains a heterogeneous mixture of subpopulations. The objective of these problems is to learn model that performs robustly for all groups. In particular, apply our approach to three performance metrics: worst-group accuracy, democratic disparity, and equality of opportunity. We also compare against STL methods, including group distributional robust optimization (GroupDRO, Sagawa et al. (2020)) and supervised contrastive learning (correct-n-contrast, Zhang et al. (2022)). Table 2 presents the comparison.
Compared with single-task learning, including GroupDRO and corract-n-contrast, we find that task modeling improves the worst-group accuracy by 1.17% on average. Compared with existing MTL optimization methods, our approach shows favorable gain of up to 1.9% absolute accuracy. Measured by two fairness metries, namely democratic disparity and equality of opportunity, our algorithm outperforms all baseline methods by 1.8% on average. These results can be found in Table 6 of Appendix C.2.
4.5 Techniques to Speed Up Training
Lastly, we show that we can further reduce the runtime of our approach by adding two techniques. Our objective is to achiove comparable performance results to the ones shown Table 1, but we will speed up the computation of
(S..) using the following two simple techniques.
First, we can reduce the size of the training set for computing f by downsampling the training data from each task by fixed proportion.
Second, we can reduce the number of iterations for training each MTL model by carly stopping the training procedure.
To illustrate the benefit of these two techniques, we apply them are shown in Table 3. We find that by downsampligg 40% of the training data and early stopping at 20% of the training epochs, we can achieve comparable performance to fully training MTL models. In particular, the
weak supervision datasets. The results
12

---

Published in Transactions on Machine Learning Research (03/2023)
Table Spoeding up our approach by training models on sampled subsets of tasks with 20% training epochs (early stopping) and 40% training data (downsampling). With these two speed-up techniques, we can achieve comparable performance compared to fully computing the MTL performances.
Dataset (Metries)
CDR (Hours/ / P1)
Chemprot (Hous / Acc.)
Alg. w/o early stopping and downsampling
38.34H / 61.22:+0.39
31.14H / 55.5440.55
Alg. 1 w/ carly stopping and downsampling
2.89H / 60.77-00005
3.761 57.0660.84
accuracy difference is within 0.5% for both datascts. However, manage to reduce the training time for computing (S2), (S.)) by 12x times. In Table 7 of Appendix C.3, we report the running time for all the baselines on these two datasets. Overall, our approach is comparable to the baseline optimization methods in terms of efficiency.
4.6 Ablation Studies
Benefit of modeling higher-order transfers. We validate the benefit of modeling higher-order task transfers over approaches that only precompute first-order or second-order task affinities. First, compared with approaches that compute first-order task affinities, our approach improves the accuracy by 3.0%, as is clear from Tables 1 and 2. Second, we precompute the MTL performance for every combination of two source lasks. We run an exhaustive search over - 1)/2 combinations to find the best combination for MTL. We test six target tasks with k 50, which requires training 1, 225 MTL models with two source tasks and one target task each time. We find that our selection procedure consistently outperforms the best two-task subsets by 1.21% absolute accuracy. This is shown on the last two lines in Table 2.
Sensitivity of model parameters. There are three parameters that require tuning: the subset size a, the number of samples n, and the loss function l. We vary a for each dataset between (3, 5, 10, 15) via cross-validation, on holdout set of 100 subsets. We pick in {50, 200, 400, 800} according to the number of tasks k. Besides, we find that choosing as the classification margin function performs the best in practice.
The threshold is usually set 0.3 or 0.4 for weak supervision datasets, which selects most of the source tasks on average except the highly noisy labels. For instance, on the Semeval dataset with 164 source tasks, our approach selected 160, while a is 15. For the NLP and multi-group learning tasks, is usually set as -0.3. This usually selects 3 or 4 source tasks, while a is 5. Thus, there is only a small number of helpful source lasks for a particular larget task.
Lastly, we find that the selected tasks remain the same when using different random seeds to train the surrogate model. For details, see Appendix C.4.
5 Related Work
We note that there is vast body of work multi-task learning from various fields. A recurring theme for multitask learning research is inspired by a desire to imitate human intelligence as we continue to learn new information and extrapolate the learned information to new tasks and domains (Thrun and Pratt, 1998). In the early literature, many studics focus on MTL with lincar and kernel-based models. common approach is to set up separate parameters for each task while adding explicit regularization to the combined parameters (Evgeniou and Pontil, 2004; Argyriou et al., 2007; 2008). For linear models, this approach can be related to low-rank matrix approximation (Ando and Zhang, 2005). Inspired by the development of deep learning, recent works focus on MTL with deep neural networks (Yang and Hospedales, 2017). More broadly, see several recent surveys (Zhang and Yang, 2021; Jiang et al., 2022) for more comprehensive references. Within this vast literature, the contribution of our work is in the identification of negative transfers and the design of subset selection methods. Below, we discuss several relevant topics in detail.
Understanding Black-box Predictions. Surrogate modeling a classic technique for studying black-box functions (Sacks et al., 1989; Ong al., 2003), which we use as a proxy to study task relatedness. Our approach builds on the recent work of datamodels (Ilyas et al., 2022). However, there are two major differences between our work and their work. First, we apply the idea of surrogate models to multitask learning, whereas
13

---

Published in Transactions on Machine Learning Research (03/2023)
their work focuses on the single-task supervised learning setting. Second, besides empirical demonstrations, we have also conducted a theoretical analysis of our approach to multi-task learning. Our findings reinforce the result of Πlya et al. (2022) that the performances of deep neural networks can be extrapolated efficiently and accurately. Recent work has sought lo explain why datamodels can perform well using harmonic analysis (Saunshi et al., 2022). It would be interesting to see if their techniques can be used to explain the empirical findings of our work in the context of MTL. More broadly, there is line of work developing techniques to understand the influence of data in black-box models through influence functions. See Koh and Liang (2017) and Yeh et al. (2018) for further references.
Formal Notions of Task-relatednoss. There is a rich discussion about formulating notions of task- relatedness in the literature (Ben-David and Schuller, 2003). Ben-David et al. (2010) introduces a discrepancy notion called H-divergence, which leads to a generalization bound for minimizing the empirical risk of naive MTL. Transfer exponents are another measure of discrepancy between two distributions (Hanneke and Kpotufe, 2019). Geometric distance mcasures for linear data models have also been considered in few-shot learning (Du et al., 2020) and meta-learning (Kong et al., 2020; Saunshi el al., 2021).
Note that none of these task-relatedness measures can be measured on deep neural networks due to the complexily of these models. One heuristic solution is to measure the cosine similarity between the gradients of each task's loss functions during training (Yu et al., 2020; Dery et al., 2021; Chen et al., 2022). Another solution is to mcasure the similarity of the predicted probabilitics between tasks (Nguyen et al., 2020). This leads to noisy estimate of task-relatedness, which is best for capturing first-order transfers. Standley et al. (2020) combines domain knowledge from visual intelligence to build task relation taxonomy for 26 tasks. Compared with their approach, our approach is more generic, applies to any MTL settings with little to no domain knowledge, and efficiently captures higher-order transfer in a principled framework. Rather than defining an explicit relatedness measure, our work uses surrogate models to measure task-relatedness. This perspective circumvents the design of explicit relttednsss measures for deep neural networks but is still useful for predicting transfers and for optimizing the performance of MTL.
Optimization Methods for MTL. An empirical motivation for this paper stems from recent work using weak supervision for training deep models (Ratner et al., 2016). We build a multi-task weak supervision approach (Ratner et al., 2019) while adding new capability to deal with conflicts between labeling functions in the end model. This problem has also been studied in the rich literature about learning from noisy labels (Liu and Tao, 2015). For example, Xia et al. (2019) and Xia et al. (2020) propose to estimate transition matrices for multi-class prediction and use statistically-coniise Complementary to these works, we fit a surrogate model to approximate multitask learning performances and use the surrogate model to predict the performance of unseen task combinations.
weighting to integrate multiple noisy labels.
Our approach selects source tasks for learning target task, which has been studied in several recent works using optimization methods (Guo et al., 2019; Chen et al., 2022). Recent work (Liu et al., 2022) optimizes a weighted combination of per-task loss functions and jointly updates task-specific weights by the gradients of per-task losses during training. By contrast, our approach focuses on subset selection. Besides, our approach can separate lasks with more noisy labels when source lasks have disparate labeling precision. Our selting is also related to the task grouping problem (Kumar and Daume III, 2012), which aims to assign tasks into several groups, with each group of tasks learned in a separate MTL model. Unlike this problem, we select a subset of source tasks for a particular target task.
There are also works that apply low-rank tensor factorization to the parameters of multiple linear regression tasks (Wimalawarne et al., 2014). Along this line of research, several recent works apply low-rank regularization methods with a block-diagonal structure on the model parameters (Nie et al., 2018; Yang et al., 2020). Yang and Hospedales (2017) revisit the idea of tensor factorization in the context of deep neural networks. Liu et al. (2016) provide generalization bounds for multi-task learning under a low-rank structural condition on all the tasks. Their results shed light on when MTL would be better than STL.
Lastly, we note that task relations are characteristically different between different benchmarks due to the nature of the data. This paper focuses on developing methodology for predicting MTL performances using rigorous ical and empirical arguments. Our extensive experiments demonstrate the usefulness of the methodology. It would be interesting to apply our methodology to large-scale benchmarks beyond what
14

---

Published in Transactions on Machine Learning Research (03/2023)
we have studied (Zamir et al., 2018; Aribandi et al., 2022). Besides, it would be interesting to see if our approach can be applied to other related settings such as federated learning (Wang et al., 2020) and multitask reinforcement learning (Wang et al., 2022), where the problem of identifying negative transfers also ariscs. Lastly, although our work focuses on subset selection for multitask learning at the task level, it would be interesting to see if similar approaches could be applied the feature level.
6 Conclusion
This paper studied how to efficiently predict negative transfers from multiple source tasks to one target task. The main contribution the design and analysis of surrogate models for predicting multi-task learning performances. Both theoretical and empirical results show that approach is efficient, accurate, and advances over prior optimization methods for multi-task learning.
Our work opens up many interesting questions for future work. Although we demonstrated the empirical strength of linear models for MTL. a rigorous explanation is lacking; Can recent. analytic tools for understanding datamodels (Saunshi et al., 2022) be used here? Can more advanced sampling techniques, such as adaptive sampling, help speed up the training of surrogate models, which might enable the training of more powerful models? Lastly, our experiments show that the validation set size of the target task does not need to be very large for the approach to perform well. This is currently not explained by our Rademacher complexity-basee bound. It is possible that with tighter generalization analysis via data-dependent bounds, one might get a result that captures few-shot learning scenarios. This would be an interesting question for future work. Understanding task relationships in multitask learning is a complex and challenging research question. We hope our work inspires more principled studies in this direction.
Acknowledgment
Thanks to Andrew Tyas, Simon Du, Shuxiao Chen, and Chicheng Zhang for helpful discussions at various stages of this work. Thanks to the anonymous referees and the action editor for providing constructive feedback on our work. DL acknowledges the financial support from seed grant and the startup fund from the Khoury College of Computer Sciences, Northeastern University.
References
Ando, R. K. and Zhang, T. (2005). "A framework for learning predictive structures from multiple tasks and unlabeled data". In: Journal of Machine Learning Research.
Argyriou, A., Evgeniou, T., and Pontil, M. (2008). "Convex multi-task feature learning". In: Machine learning. Argyrion, A., Pontil, M., Ying. Y., and Micchelli, C. (2007). "A spectral regularization framework for multi-task structure learning". In: Advances in neural information processing systems 20.
Aribandi, V., Tay, Y., Schuster, T., Rao, J., Zheng, H. S., Mehta, S. V., Zhuang, H., Tran, V. Q., Bahri, D., Ni, J., et al. (2022). "ExT5: Towards Extreme Multi-Tan -ask Scaling for Transfer Learning". In: ICLR.
Bartlett, P. L., Foster, D. J., and Telgarsky, M. J. (2017). "Speetrally-normaaized margin bounds for neural networks". In: NewrIPS 30.
Bartlett, P. L. and Mendelson, S. (2002). "Rademacher and Gaussian complexities: Risk bounds and structural results". In: Journal of Machine Learning Research 3.Nov, pp. 463 -422.
Ben-David, S., Blitzer, J., Crammer, K., Kulcsza, A., Percira, F., and Vaughan, J. W. (2010). "A theory of learning from different domains". Tn: Machine learning 79.1, pp. 151-175.
Ben-David, S. and Schuller, R. (2003). "Exploiting task relatedness for multiple task learning". In: Learning theory and kernel machines. Springer, pp. 567-580.
Caruana, R. (1997). "Multitask Learning.. PhD thesis. CMU. Thesis. Chen, S., Crammer, K., He, H., Roth, D., and Su, W. J. (2022). "Weighted Training for Cross-Tas Learning". In: ICLR
15

---

Published in Transactions on Machine Learning Research (03/2023)
Dery, L. M., Dauphin, Y., and Grangier, D. (2021). "Auxiliary task update decomposition: The good, the bad and the neutral". Tn: JCLR.
Ding, F., Hardt, M., Miller, J., and Schmidt, L. (2021). "Retiring adult: New datasets for fair machine learning". In: NeurIPS 34.
Du, S. S., Hu, W., Kakade, S. M., Lee, J. D., and Lei, Q. (2020). "Few-shot learning via learning the representation, provably". In: ICML.
Evgeniou, T. and Pontil, M. (2004). "Regularized multi-task learning". In: KDD.
Fifty, C., Amid, E., Zhao, Z., Yu, T., Anil, R.,, and Finn, C. (2021). "Efficiently identifying task groupings for multi-task learning". In: NewrIPS 34.
Guo, H., Pasunuru, R., and Bansal, M. (2019). " "AutoSeM: Automatic Task Selection and Mixing in Multi-Tass Learning". In: NAACL.
Hanneke, S. and Kpotufe, S. (2019). "On the value of target data in transfer learning". In: NewrIPS 32. Ilyas, A., Park, S. M., Engstrom, L., Leclere, G., and Madry, A. (2022). "Datamodels: Predicting predictions from training data". In: ICML.
Jiang, J., Shu, Y., Wang, J., and Long, M. (2022). "Transferability in Deep Learning: A Survey". In: arXiv preprint trXiv:2201.0588
Ju, H., Li, D., Sharma, A., and Zhang, H. R. (2023). "Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds Graph Diffusion". In: ATSTATS.
Ju, H., Li, D., and Zhang, H. R. (2022). "Robust Fine-Tuuine of Deep Neural Networks with Hessian-basse Generalization Guarantces". In: ICML.
Koh, P. W. and Liang, P. (2017). "Understanding black-box predictions via influence functions". In: Interna- tional conference on machine learning. PMLR, pp. 1885-1894.
Kong, W., Somani, R., Song, Z., Kakade, S., and Oh, S. (2020). "Meta-lcarning for mixod linear regression". In: International Conference on Machine Learning. PMLR, pp. 5394-5404.
Kumar, A. and Daume III, H. (2012). "Learning task grouping and overlap in multi-task learning". In: ICML. Li, D. and Zhang, H. (2021). "Improved regularization and robustness for fine-tuning in neural networks". In: NewrIPS 34, pp. 27249-27262
Liu, S., James, S., Davison, A. J., and Johns, E. (2022). "Auto-lambda: Disentangling dynamic task relation- ships". In: TMLR.
Liu, T. and Tao, D. (2015). "Classification with noisy labels by importance reweighting". In: IEEE Transactions on pattern analysis and machine intelligence.
Liu, T., Tao, D., Song, M., and Maybank, S. J. (2016). " "Algorithm-dependee generalization bounds for multi-task lcarning". In: IEEE transactions on pattern analysis and machine intelligence.
Nguyen, C., Hassner, T., Seeger, M., and Archambeau, C. (2020). "Leep: A new measure to evaluate transferability of learned representations". In: International Conference on Machine Learning. Nic, F., Hu, Z., and Li, X. (2018). "Calibrated multi-task lcarning". In: KDD.
Ong, Y. S., Nair, P. B., and Keane, A. J. (2003). "Evolutionary optimization of computationally expensive problems via surrogate modeling". In: AIAA journal.
Raghu, A., Raghu, M., Bengio, S., and Vinyals, O. (2020). "Rapid learning or feature reuse? towards understanding the effectiveness of maml". In: ICLR.
Ratner, A., Hancock, B., Dunnmon, J., Sala, F., Pandey, S., and Ré, C. (2019). "Training complex models with multi-task weak supervision". In: AAAL
Ratner, A. J., De Sa, C. M., Wu, S., Selsam, D., and Ré, C. (2016). "Data programming: Creating large training sets, quickly". In: NewrIPS 29.
Rosenstein, M. T., Marx, Z., Kaelbling, L. P., and Dietterich, T. G. (2005). "To Transfer Not To Transfer".
In: http: //orraess acadiau. ca/ courses / comp / dsilver ITWS05 Suwmitted_ ITWS10- RosensteinM05, LttpeiiooooS_SSS_______ pdf.
16

---

Published in Transactions on Machine Learning Research (03/2023)
Sacks, J., Welch, W. Mitchell, T. J., and Wynn, H. P. (1989). "Design and analysis of computer experiments".
In: Statistical science.
Sagawa, S., Koh, P. W., Hashimoto, T. B., and Liang, P. (2020). "Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization", In: ICLR.
Saunshi, N., Gupta, A., Braverman, M., and Arora, S. (2022). "Understanding Influence Functions and Datamodels via Harmonic Analysis". In: arXiv preprint ar wrXii2221000107:
Saunshi, N., Gupta, A., and Hu, W. (2021). "A Representation Learning Perspective on the Importance of Train- Validation Splitting in Meta-Learning" In: International Conference on Machine Learning.
Standley, T., Zamir, A., Chen, D., Guibas, L., Malik, J., and Savarese, S. (2020). "Which tasks should be learned logether in multi-task learning?" In: ICML. PMLR, pp.
Thrun, S. and Pratt, L. (1998). "Learning to learn: Introduction and overview". In: Learning to learn. Springer. Vershynin, R. (2011). "Spectral norm of products of random and deterministic matrices". In: Probability theory and related fields 150.3, pp. 471-509.
Vu, T., Wang, T., Munkhdalai, T., Sordoni, A., Trischler, A., Mattarella-Micke A., Maji, S., and Iyyer, M. (2020). "Exploring and predicting transferability across NLP tasks". In: EMNLP. Wainwright, M. J. (2019). High- dinensoimel statistics: A non-asymptotic viewpoint. Vol. 48. Cambridge University Press.
Wang, H., Yurochkin, M., Sun, Y., Papailioponlos, D., and Khazaeni, Y. (2020). "Federated learning with matched averaging". In: ICLR.
Wang, Z., Zhang, C., and Chaudhuri, K. (2022). "Thompson Sampling for Robust Transfer in Multi-Task Bandits". In: ICML.
Wimalawarne, K., Sugiyama, M., and Tomioka, R. (2014). "Multitask learning meets tensor factorization: task imputation via convex optimization". In: NewrIPS 27.
Wu, S., Zhang, H. R.,, and Ré, C. (2020). "Understanding and improving information transfer in multi-task learning". In: TCLR.
Xia, X., Liu, T., Han, B., Wang, N., Gong, M., Liu, H., Niu, G., Tao, D., and Sugiyama, M. (2020). "Part-dependent label noise: Towards instance-dependent label noisc". In: NewrIPS.
Xia, X., Liu, T., Wang, N., Han, B., Gong, C., Niu, G., and Sugiyama, M. (2019). "Are anchor points really indispensable in label-noise learning?" In: NewrIPS.
Yang, F., Zhang, H. R., Wu, S., Su, W. J., and Ré, C. (2021). "Analysis of information transfer from heterogeneous sources via precise high-dimensional asymplotics" In: arXiv.
Yang, Y. and Hospedales, T. (2017). "Deep multi-task representation learning; A tensor factorisation approach". In: TCLR.
Yang, Z., Xu, Q., Cao, X., and Huang, Q- (2020). "Task-feature collaborative learning with application to personalized attribute prediction". In: TPAMI.
Yeh, C.-K., Kim, J., Yen, F.-H., and Ravikumar, P. K. (2018). "Representer point selection for explaining deep neural networks". In: Advances in neural information processing systems.
Yu, T., Kumar, S., Gupta, A., Levine, S., Hausman, K., and Finn, C. (2020). "Gradient surgery for multi-task learning". In: NewrIPS 33, pp. 5824 5836.
Zamir, A. R., Sax, A., Shen, W., Guibas, L. J., Malik, J., and Savarese, S. (2018). "Taskonomy: Disentangling lask transfer learning". : In: CVPR, pp. 1722.
Zhang, J., Yu, Y., Li, Y., Wang, Y., Yang, Y., Yang, M., and Ratner, A. (2021). "WRENCH: A Comprehensive
Benchmark for Weak Supervision". In: NewrIPS Datasets and Benchmarks Track.
Zhang, M., Sohoni, N. S., Zhang, H. R., Finn, C., and Ré, C. (2022). "Correct---ontraae A Contrastive Approach for Improving Robustness to Spurious Correlations". In: 1CML.
Zhang, Y. and Yang, Q. (2021). "A survey on multi-task learning". In: JEFE Transactions on Knowledge and Data Engineering.
17

---

Published in Transactions on Machine Learning Research (03/2023)
A
Results for Constructing Surrogate Models
Section 2.3 shows that the sample complexity for learning task models is linear in the number of source tasks. Here, we provide empirical evidence to support this result. We plot the convergence of task modeling on sixteen target tasks from three datasets described in Section 4.1. We measure the MSE between task model predictions and empirical training results on the holdout set of size 100, following the experimental setup described in Section 4.2. Figure 6 shows the results. The red line shows the variance of f, measured across five random seeds. We observe that:
The MSE of task models consistently converges close to the variance of the prediction loss.
The Spearman correlation coefficient between the predictions and the true performances is 0.8 on average.
Thus, we conclude that linear surrogate models can be accurately fitted with less than 8k samples, and the fitted model can accurately predict the performances of unsampled subsets.
Spearman Corr.: 0.80
Spearman Corr.: 0.74
Spearman Corr.: 0.81
Spearman Corr.: 0. 0.78
MSE (Holdoul)
2.0
MSE (Iollout)
MSE (lollout)
2.0
MSE (Haldont)
2.0
MSE
MSE
MSE
MSE
1.5
1.5
1.5
1.5
war
var f
1.0-
1.0-
1.0-
1.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0
50
100
150
200
50
100
150
200
0
100
200
300
400
200
400
600
800
T Chemprot
n
X2
(a)
(b)
CDR
(c)
TREC
(d) Semeval
Spearman Corr.: 0.85
Spearman Corr.: 0.74
Spearman Corr.: 0.74
Spearman Corr.: 0.72
2.0
MSE (Holdout))
2.0
MSE ([oldont))
2.0
MSE (Holdout)
2.0
Test MSE
1.5
MSR
1.5
1.5
sa
1.5
1.0
1.0
1.0
1.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
50
100
1.5
200
50
100
150
200
50
100
150
200
50
100
150
200
1 (e) CoLA
(I) RTE
(g)
COPA
(h)
WSC
Spearman Corr.: 0.89
Spearman Corr.: 0.82
Spearman Corr.: 0.88
Spearman Corr.: 0.82
MSB (Holdoul)
2.0
MSE (Holdout))
2.0
MSE (Holdout)
2.0
MSE (Holdout)
2.0
MSB
MSB
MSE
MSE
1.5
1.5
1.5
1.5
1.0-
1.0-
1.0-
1.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0
100
200
300
400
100
200
300
400
100
200
300
400
100
200
300
400
n
17
71
(1) HI
(j) LA
(k) MN
(I) NM
S Spearmen Corr:: 0.76
Spcarman Corr.: 0.74
Spearmon Corr: : 0.77
Spcarmon Corr.: 0.82
MSE (Hohlont)
2.0
MSE (Holdont)
2.0
MSE (Holdout)
2.0
MSE (Holdout)
0.9
MSE
MSB
MIE
MSE
1.5
1.5
1.5
0.6
1.0
1.0
1.0
0.3
0.5
0.5
0.04
0.0
0.0
0.0
100
200
300
400
0
100
200
300
400
100
200
300
400
100
200
300
400
n2
π
(m)
KS
(n)
NJ
(o) NV
(p) SC
Figure 6: The MSE of linear surrogate models converges close to the variance of MTL performances. (a-d) Weak supervision tasks. (e-h) NLP tasks. (i-p) Multi-group learning tasks.
B Complete Proofs of Theoretical Results
Notations. We use f(n) = (1 + (n) to indicate that [f(n) - g(())//(()) approaches zero as n goes to infinity. For matrix denoted as X, denote the spectral norm (or the largest singular value) of X as ||||2 Denote the Frobenius norm of X |X
18

---

Published in Transactions on Machine Learning Research (03/2023)
B.1 Proof of Lemma 2.2
In the first part of the proof, we prove the convergence from i to 0 by dealing with the randomness of $1, S2,S....,55 Sn- Recall that 4 the uniform distribution over subsets of (1,2..... k} with size a. Let [ = (a) denote the number of subsets from U.
Proof of Lemma 2.2. Recall the definitions of ô and 0 from Section 2. They can be written equivalently as follows:
I In
I [2
I
0
and
We will use the triangle inequality to separate the error between and 0 into two parts:
0
T In
I
v
I
I
f
I
2
n
[44)
72
In
I
(14)
U
I
I
+
(15)
[2
We compare and I Recall that both vectors have & coordinates, each corresponding to one task. For TeT any task i = I,... ki let & denote the difference between the i-th coordinate of zh and the i-th coordinate of If. [
E, Σ ((S
Σ S(T).
(16)
M
IiiSn iES,
TEU:
Notice that the sampling of Si, . ..,,.,. Sn independent of the randomness in f. Therefore, we have that the expectation of & is zero:
.....
E E O, for any i = 1.
Next, we apply Chebyshev's incquality to analyze the deviation of & from its expectation. We consider the variance of &i, which is equal to the expectation of & since the mean of & is zero:
27
E E7
=
E
Σ
J(S))
Σ Tel:: iET
S(T)
7
U
15j5n: iES,
=E
Σ
f(S,)
2
Σ
f(S,) Σ
F(T) + Tup
(
E
Σ
S(T))
n
n M
ISiSnies,
I3i5ni iES,
TEM:
TeU: iET
(17)
Notice that for any E U such that E T, the probability that T is sampled in the training datasct of size n is equal to
(4-11)
n-1
[24]]
U
For any two subsets T * T that are both from 24 such that i T and i T', the probability that T and T" are both sampled in the training set (of size n) is equal to
[M
n1
(1))
[21]
2
19

---

Published in Transactions on Machine Learning Research (03/2023)
Thus, by taking the expectation over the randomness of the sampled subsets in equation (17) conditional on I, we can cancel out the cross terms for every pair of two tasks o i', leaving only the squared terms as:
E
[ E
[
1
Σ
(S(T)) 2
C² S
T iET
C
n
4
n
2
M
u²
n
n
Tel: iET
since the value of f' bounded from above by an absolute constant C. Therefore,
C*k
E
3
7
By Markov's incquality, for any 0,
k
C
Pr
a²
Therefore, with probability at least 1- - 8, for any 5 > O, conditional on the randomness of f, we have that
f U
S SCV
(18)
Next, random matrix concentration results analyze the difference between the indicator matrix of the sampled subsets and the indicator matrix of all subsets in U. Denote by
II
In
I'I [
I
E
and A = M
By the Anermann-Morrisee formula calculating matrix inversions, we get
I In
-1
I I
-1
(| + A)- - ---11
11
[2
2
(AF + +dxxx
A (AAA (A+E) E)
(Amin (A)) -1
||:1||2
(Amin (A E))
|
(19)
Amin (A)(Amin (A) [E]12)
We now use the matrix Bernstein inequality (cf. Theorem 6.1.1 in Tropp (2015)) to deal with the spectral norm of F. Let
I for any i == 1,...,n. n
x, = =111,,13
21"
In expectation over U, we know that [X,] 0, for any i 1...., n. Additionally, || S 2a, since it is a linear combination of indicator vectors with a entries of ones in each indicator vector. Therefore, for all t > 0,
(nt)2/2
Pr E| ž t| Pr
Pr
Σ x
2 nt
< 2k exp (~(2a)án + nntt3333)
With some standard calculations, this implies that for any 8 820 0, with probability at least - 6,
4a log (2k6-)
|bl|2 <
(20)
vn
20

---

Published in Transactions on Machine Learning Research (03/2023)
By applying equation (18) into equation (14) and equation (20) into equation (15), we have shown that with probability at least. - 26, for any 5 2 O,
4a log 2k0-1)
0 0 0
1
k CV
(21)
n
2
vn
(Amin (A)) (A))
(Amin (A) (|
Lastly, we examine the norm of 5. Let 2; be the number of subsets Sj among S S n such that E SJ, for any i = I...., n. Recall that the value of bounded from above by an absolute constant C. Thus, based the definition of from equation (8), we have:
C
k Σ
C2
2
4i
= =Ca,
(22)
since the size of each subset is strictly equal to a.
Regarding the minimum eigenvalue of A, notice that the diagonal entry of I'I is equal (--1)- The [
off-diagonal entries of this matrix are equal (x=2). Thus, based on standard algebra, one can prove that
Aminl (A) 2 1
k-1 21
(23)
Applying equations (22) and (23) back into equation (21), we conclude that with probability at least 26,
i the estimation error between 0 and 0 grows at rate of V as follows:
0 o| = 4Ca log (2kg
k +
-1-99) a
k
Ca
Von
k
En
Thus, we have proved that equation (9) holds, and the proof is complete.
B.2 Proof of Lemma 2.3
In the second part, we prove the convergence from 0 to 6* by dealing with the randomness of f.
Proof of Lemma 2.3. Based on the definitions of 0 and 6*, their difference can be written as follows:
1
0+1|
I I
I
I
E [f])
(24)
I
I
f EE [f]
[
2
I
|lf E [fll
[
VMVI
-
|| E [fll
(by equation (23))
ViuI
For each subset T' U, recall that f(T) is the MTL outcome of combining the datasets of all tasks of T with the main target task. We will apply Rademacher complexity-basee generalization bound to analyze the generalization error f(T)- E [[[)] Recall the Rademacher complexity of F with samples from Dj is defined in equation (5). By Bartlett and Mendelson (2002, Theorem 5), with probability at least 1 - d, we can get:
S(T) < [[((T) + (F)
log (1/6) 2m
(25)
2
21

---

Published in Transactions on Machine Learning Research (03/2023)
Similarly, one can get the result for the other directions of the error estimate. With a union bound over all subsets 7 E U4 with probability at least ô, we get:
f(T) E[((() + (F)
a log 5
+
for all T e u,
(26)
2
2m
since
k
log
S a log
8
Let V log (k6 (k6-1)/(2m) Applying equation (26) back into equation (24), we have shown
|00 00 < =1-7)
a) k
(m)
+
TEU
= =(1
a -
Rm
+
k
2
Thus, based on the condition that S k/2, the proof of equation (10) is complete.
Proof of Theorem 2.1. Notice that equation (6) follows by combining equation (9) from Lemma 2.2 and equation (10) from Lemma 2.3, together with the condition that a < 1/2. Thus, the proof of the theorem is finished.
Remark. Our result depends on the Rademacher complexity of the function class. This complexity measure can be vacuous on real data for deep neural networks. would be interesting incorporate data-dependent generalization bounds in the proof (e.g., Li and Zhang (2021) and Ju et al. (2022), 2023).
B.3 Convergence of the Empirical Risk
Based the results from Lemma 2.2 and Lemma 2.3, also prove the convergence of the loss values. This is stated precisely in the following result.
Corollary B.1 (of Theorem 2.1). In the setting of Theorem 2.1, we have that
log(5-18 k)
C(0") - (o) & Ca Rm + 1.
+ a 3.5 3.55
+
c
2.5
V On
(27)
Proof. To analyze the generalization error of 0, based on equation (2), we can expand the loss term as
I 0 fl²
(0) =
0 f
+
f
n
1 1
I. E [5]
+
2
iI.
EE [1]
A +
-
(28)
22

---

Published in Transactions on Machine Learning Research (03/2023)
Based on Lemma 2.2, the distance between & and 6* is at the order of (/2) with high probability, We will use this result to deal with the first term in equation (28) as follows:
1
[+]
[
In
In -B
(29)
7
7
1
2
[ In, 0(0) (00)
EE
0 8¹)
7
n
I In
1|-00-0 -0(0) +
2
110-
0
(by triangle inequality)
11 2
n
(00) -(0) 20 61
where e denotes the right hand side of equation (6). In the last step, the first part uses the fact that InJ In/ / is the average n rank one matrix, cach with spectral norm a since they have exactly a ones. The second part uses an argument similar equation (22) and the result of equation (6). Next,
(0,)
= 00 - TT)T + +00 O0,) 1|p
1 (0 - -o.)) 7 11 + +1(00- 00)
(by triangle inequality)
|10 |0|| )e1
(by equation (6))
We show that the norm of 0 and On are both bounded by a constant factor times v k. To see this,
|0-1 =
[I 1) II'
E [f]
I I 1
I
E [f]
[
$ (1 (1- a -1
Coa
(by equation (23) and the condition that f is bounded by C*)
Notice that the spectral norm of the difference between I I/ [2]] and Z,J In/n has been analyzed in equation (20). Thus, with similar steps as above, can show that
)) -0+'+ 4a log (2k5-1)
| < (1-
OVE.
vn
To wrap up analysis above, we have shown that equation (29) is most
E3 2(1 a/k)-1 4a log (2ko-1) v
C-āa + +Ca e1.
Next, we consider the second term in equation (28). Let e2 Rm((F) +
log(k/6) 2m
be the deviation error
indicated in equation (26). Thus, every entry of f - E [ is at most e2. Besides, each entry I,O,, E is less than
Vallm,l + C,
because |Tm I a and f is bounded from above by C. Thus, the second term in equation (28) is less than
4a log (2ko-1)
)cva+c).
62 Va. ((1-
a) Ko +
Vn
23

---

Published in Transactions on Machine Learning Research (03/2023)
For the population loss (()*), notice that
((0))
II0
|-]
I0
[f]
[f]
[2<]
1
IB*
E
151
1
E
[ff 7)
(30)
f
[
f
We know that each entry of IO - TE [f] at most (1 (1-a//)) va + C. Thus, by HoelIding's inequality, with probability least - 6, we have
1 n
1 2
I0 | s ((1-a/))-Va+
log (6-1)
I
(31)
n
Lastly, we consider the third term in equation (28), compared with the second term in equation (30). For every u, let er = f(T) E [f()). By equation (26), we know that eT is of order O(m 0mm11/2), for every T E U. Therefore
(J) + S
a log(k//)) 2
(32)
2m
which is of order O(m-1). Similarly, the same holds for the variance of f in the second term of equation (30).
Comparing equations (31) and (28), we have shown that
[(0*)- - (0) & ((1 a/k) "a++) log(d-1)
+ea +3
s (C+ (m)(F)+ + Valog(ko-))
C2a log (2ko-1) + 8C2
Vm
V
The above follows by incorporating the definitions of the error terms e2, e3, e4. Thus, we have proved that equation (27) holds. The proof is now finished.
B.4 Proof of Theorem 3.1
Recall that In {0, 1|a8 is the indicator matrix corresponding to the task indices from the training dataset. Given a set of tasks S with size a, denote their feature matrices and label vectors as (1), (X2, Y2), (Xa, Ya). With hard parameter sharing (Yang et al., 2021), we minimize
a
((B)
X -XI-
(33)
The minimizer of E(B), denoted as B, is equal to the following
B Ex,xx (
((EXTT)
For isotropic covariates, by matrix concentration results, the loss of using B on the validation set of the target task is equal to
S(S) 1 p000|1 +0
2 (1
m
First, state the proof of Lemma 3.3 from Section 3.
24

---

Published in Transactions on Machine Learning Research (03/2023)
Proof of Lemma 3.3. We have that Y = xx,(0 tc(1, where elt) is a random vector whose entries are sampled
independently with mean and variance o². We have
S(S) -
X, X
Σ X
(
(34)
For task i, we know that its coefficient is equal to the i-th entry of
I I
I
1
T
Let Z In. By equation (12), for any * J. we observe that
0, 0g k
12-
0j
(ei (T) - E [2]
- IE [2] < |le ejll 1
2Ca
2-11-E 1
(by equation (22))
4a log (2k0--1)
2
(by equations (19), (20), (23))
vn
(1 alkk/)²
The last step follows by applying equations (20) and (23) into equation (19). Thus, we have finished the proof of equation (11).
Second, we show that provided n, and d are sufficiently large, separation exists in the coefficients of between good and bad tasks.
Proof of Theorem 3.1. We calculate 0 for all I,..., k and compare its value between good task and bad task. We first compare their expectations over the randomly sampled subsets. By equation (18), we get
Ck8-14 1/2
U1
S(T)
and
U
Vn
TEl::
SE
Ck8-11 1/2
Σ S(T)
<
vn
TEU: JET
Therefore, by applying the triangle inequality with the above two results, we get
02 U2 Ereuser J(T) -reeser
2Ck5-1/2
(35)
[u
vn
To deal with equation (35), we apply union bound over the sample covariance matrix of every subset T in U to show that they are close to their expectation. By Gaussian covariance estimation results (e.g.. Wainwright (2019, equation (6.12))), for a fixed l such that = {ii, f2.,2..... da), we get
26 aa t +c)²
2
Ex,X, Idpxp ad JET
2 P ad
(36)
with probability at least 1 - 2 exp (- )ade With union bound over all T U, we have that the above holds with probability at least 1 - 8 for all T E U, for that is equal to
2ak log(2k0- 228--1)
ad
25

---

Published in Transactions on Machine Learning Research (03/2023)
Let E1 denote the error term from equation (36), by inserting the value of c:
E1 2 ad
p
2xx log + 2
+ (Via t
2
ad
Let
Σ CxJ xT),), for any T TEu.
ad
jET
One can verify that
[((2) ||r| $ 2 1) | 12 < 3El ||r]|1
Notice that
( ]
E [1 E
Tr
(ad)2
jET
If j a good task, then the expectation over eli is equal to a² Id by the assumption of Theorem 3.1. If j is a bad task, on the other hand, then the expectation over e(t) is equal to 12 ld.
Let s(T) denote the number of good tasks in T, for any T [ (1,2,...,,A A). Thus,
p ((a's(() + 62 (a-a((()) sT))
E [
[2]
(37)
add
To argue about the deviation error of ||uT||? we use the following two estimates (see, e.g., Vershynin (2011)), which holds with high probability:
((0)) T xxx] (b)) -0)- (E0)) x,x]o(01 S pVdd" for any j I,...,;; ((E)) T X c0il E pvdda? for any 1 <i<js <ijsk.. k.
Therefore, we get that for any TEu,
pV
|ur|l - E [| <
(38)
d2
To finish the proof, consider a good task i versus a bad task j. We need the gap in the expectation term between the good/bad tasks to dominate the standard deviation from the error terms. The gap the expectations is based on equation (37). The standard deviation terms are upper bounded by the sum of equations (35) and (38).
Thus, provided that
p(a² -Ba) 2 (1 321)
PVda? d²
2Ck5 1/2
(1- 35,)
(39)
a²d
vn
there must exist a threshold separating all the good tasks from the bad ones. We can verify that condition (39) is satisfied when
n 2 C k22.
and
- b2)2
a²
b + k klog (2k) +p.
2k
d 2
a b2
To apply Algorithm 1, we set the threshold 7 as k/a times any value between the left-hand and right-hand side of equation (39) (recall that k/a is inherited from Lemma 3.3). Thus, when and d satisfy the condition above, combined with Lemma 3.3, with high probability, for any i such that 6 y, i must be good task. When 0 > 7, much be bad task. Thus, we have finished the proof.
26

---

Published in Transactions on Machine Learning Research (03/2023)
C Experiment Details
We describe details that were left out of the paper's main lext. First, we describe the additional experimental setup and the implementation specifics. Second, we present results to further validate the sample complexity of task modeling. Third, we provide the experimental results that are omitted from Section 4, including the results for fairness measures and ablation studies.
C.1 Implementation Details
For evaluating multitask learning with natural language processing tasks, we collect twenty-five tasks from several benchmarks, including GLUE, SuperGLUE, EveetEval, and ANLI Due to the computation constraint, we did not include the tasks with a training set size larger than 100k. The collection spans numerous categorics of tasks, including sentence classification, natural language inference, and question answering. Table 4 shows the statistics of the twenty-five tasks.
Table 4: Dataset description and statistics of twenty-five text datasets.
Task
Benchmank
Train. Set
Dev. Set
Task Category
Metrics
CoLA
GLUR
8.5k
1k
Grammar acceptability
Matthews corr.
MRPC
GLUE
3.7k
1.7k
Sentence Paraphrase
Acc./F1 Acc.
RTE
GLUE
2.5k
3k
Natural language inference
SST-2
GLUE
67k
1.8k
Sentence classification
Acc.
STS-B
GLUE
7k
1.4k
Sentence similarity
Pearson Pearson/Spearre /Spaarman corr.
WNLI
GLUE
634
146
Natural language inference
Acc.
BoolQ
SuperGLUE
9.4k
3.3k
Question answering
Acc.
CB
SuperGLUE
250
57
Natural language inference
Acc./F1
CОРА
SuperGLUE
400
100
Question answering
Acc.
MultiRC
SuperGLUE
5.1k
953
Question answering
F1./EM
WiC
SuperGLUE
6k
638
Word sense disambiguation
Acc.
WSC
SuperGLUE
554
104
Coreference resolution
Acc.
Emoji
Evee
45k
6k
Sentence classification
Macro-averaged F1 Macro-averaged F1
Emotion
EveetEval
3.2k
374
Sentence classification
Hate
Eval
9k
Sentence classification
Macro-averaged F1
Irony
TweetEval
2.9k
953
Sentence classification
Offensive
TweetEval
12k
1.3k
Sentence classification
Macro-averaged F1
Sentiment
EvaetEval
45k
2k
Sentence classification
Macro-averaged Recall
Stance (Abortion)
TveetEval
587
66
Sentence classification
Avg. of F1 and F1()
Stance (Atheism)
Fvel
461
Sentence classification
Avg. of Fi and F1(
Stance (Climate)
Tweet Fval
355
40
Sentence classification
Avg. Pi(e) and F1(
Stance (Feminism)
Tweet Eval
597
67
Sentence classification
Avg. of F1 and F1(O)
Stance (H. Clinton)
Eval
620
69
Sentence classification
Avg. of Pi and F)())
ANLI (A1)
ANLI
1.7k
1k
Natural language inference
Acc.
ANLI (A2)
ANLI
4.5k
Natural language inference
Acc.
Next, we report the results for baselines by running the open-sourced implementations from the respective publications. We describe the hyperparameters for baselines follows. For higher-order approximation and task affinity grouping, m lasks with the largest task affinity scores as source tasks for each larget task. m is searched between 0 and the number of total tasks.
compute the task affinity scores between source and target tasks. Then, select
For gradient decomposition, we search the number of decomposition basis and auxiliary task gradient direction parameters, following the search space in Dery et al. (2021).
For weighted training, we search the task weight learning rate in [10- 102). The hyper-parameters are tuned the validation dataset by grid search. For each target task, we search 10 times over the dyper-paramett space. We use the same number of trials in tuning dyper-parametery for baselines.
27

---

Published in Transactions on Machine Learning Research (03/2023)
Table Accuracy CaauracyCCorrlatii /Corcllaion scores on the development using surrogate modcling followed by thresholding (ours), as compared with STL and MTL methods.
Dataset
CoLA Matthews Corr.
RTE
CB
COPA Accuracy
WSC Accuracy
Metries
Accuracy
Accuracy
Train
8500
2500
250
400
554
Validation
1000
3000
57
100
104
STL
59.38+0.70
67.94=0.74
70.36+1.82
64.00+2.19
00.00:22.76
Naive MTL
57.11+0.88
69.31=0.97
71.78+1.39
66.00=2.02
58.20:+:199
HOA
60.09+0.755
69.03+2.08
80.71+2.62
67.20+2.56
61.35:13..1 12
Alg.
(Ours)
60.43:10.79
70.83+t..97
83.57+2.48
69.20+3.71
65.38-2.311
Table 6: Violation of two fairness-related measures (demographic parity and equality of opportunity) six multi-group learning tasks with tabular features, averaged over ten random seeds. Lower is better.
Demographic parity
HI
KS
LA
NJ
NV
SC
STL
12.95+1.76
4.09+1.15
26.30+1.21
26.06+0.53
12.62+1999
22.51
Naive MTL
8.25+1331
4.06+1.17
21.24+0.66
27.73+0.94
13.35+0.51
18.83#0.80
HOA
8.63+:2.95
6.15:3.00
22.83++0.53
26.1440.29
13.15+0.64
19.39
TAG
8.9342.35
3.97:00.1
20.72:10.86
25.2110.68
12.24
18.77
TAWT
18.12:11.80
4.84+0.71
25.77=0.94
25.66:+0.38
12.40=0.74
23.16::0.2
Alg. (Ours)
2.13
1.06.1.62
17.25
24.96
11.34
17.66.0.80
Equality of opportunity
H1
KS
LA
NJ
NV
SC
STL
9.8611.29
1.43:33.62
29.64:1.24
22.43:11.02
13.61
29.93:10.77
Naive MTL
3.86
2.03.12.11
21.26.11.35
24.43.11.49
12.14
21.22.11.75
HOA
3.5512285
4.34.13.18
22.88.1..72
22.98.11.18
12.9212.23
23.31
TAG
0.27=0.25
1.18+0.97
1..66+1.43
21.89+0.69
11.66+1.58
19.89+
TAWT
4.21
1.40+22.14
30.38+22.17
23.26+0..0
11.77+1.01
30.86+0084
Alg. 1 (Ours)
0.24+1.32
0.2141.34
14.1442.32
21.48:10.90
9.65+13.49
18.54+1.61
C.2 Omitted Results from Section 4.3
Complete results for NLP tasks. In Table 5, report the complete experimental results for applying our approach to NLP tasks, reported in Section 4.3.
Optimizing related metrics. We show that lask modeling applicable to various performance metrics for capturing task affinity. Besides the average performance and worst-group performance discussed in Section 4.3, consider two fairness measures: demographic parity and equality of opportunity (Ding et al., 2021).
The demographic parity measure is defined as:
Pr | =
black] - Pr [0 1 white]
which measures the difference in the positive rates between white and African American demographic groups.
The equality of opportunity measure is defined as:
Pr [0- = 1 1,g black] - Pr = y 1,9 white]
which measures the difference in the true positive rates between the two groups
We consider the binary classification tasks with multiple subpopulation groups. Table shows the comparative results. First, similar to the worst-group accuracy results, we find that multitask approaches (including ours and previous methods) decrease the violation of both fairness measures compared ERM, suggesting the benefit of combining related datasets. Second, our approach consistently reduces both fairness measure violations more by 1.26% and 2.31% on average than previous multitask learning approaches, respectively.
28

---

Published in Transactions on Machine Learning Research (03/2023)
C.3 Comparing the Running Time
We provide comparison of the running time between our approach and the baselines in Table 7. We notice that the running time of our approach is comparable to MTL optimization methods after adding early stopping and downsampling to reduce the training time. Our approach slightly slower than weak supervision methods that directly aggregate the weak labels while achieving 5% better performance on average.
Datasct (Metries)
CDR (Hours / F1)
Chemprot (Hours Acc.)
Naive MTL
1.99 / 58 28.20-0..55
1.89 / 53 33.4310.53
Majority voting
2.00
08.89-0.50
1.91 / 57 077.2
Probabilistic modeling
2.00 58 48778
1.91 / 57 1.210.0020
MetaL
2.00 58.48=0.90
1.91 / 56. 56.17#0.66
TAWT
2.30
/ 10.30
2.02 / 53.76.12.9
Auto-A
3.46
59.07-00.05
3.31 / 52.50111.28
Alg. w/o early stopping and downsampling
38.34
61 0.39
31.14 / 57.54++0.55
Alg. w/ early stopping and downsampling
2.89
/ 60.77=0.00
3.76 / 57 0..00.8881
Table 7: Running time of our approach after adding early stopping and downsampling to speed up the computation of ((S)....
as compared with baseline approaches.
C.4 Ablation Studies for Constructing Surrogate Models
Loss function: We consider three choices of prediction losses, including zero-one accuracy, cross-entropy loss, and classification margin. We observe that the classification margin is more effective than the other two metrics. The Spearman's correlation of using the margin is 0.86 on average over two tasks (HI and LA). In contrast, the Spearman's correlations of using the loss and accuracy are 0.61 and 0.34, respectively. Besides, we compare the task selection using the three metrics in Table 8. We find that using the margin outperforms the other two by 0.37% on average over the six target tasks in terms of worst-group accuracy.
HI
KS
LA
NJ
NV
SC
f uses zero-one accuracy f uses cross-entropy loss
16.1
76.39
75.15:0..4
77.4011.49
74.34
77. 77.29:10.19
75.33 0.80
75.82.10.60
74.1911.37
77.5110.35
74.55
77.21
f uses classification margin
75.47=0.73
76.96=0.69
75.62+0.11
78.17#0.36
75.21+0.52
77.62+0.34
Table 8: Choosing different loss functions & for six target tasks the multi-group learning setting.
Subset size: Recall that we collect training results by sampling n subsets from a uniform distribution over subsets of constant size. We evaluate the MSE of task models by varying a 5, 10, 20). To control the computation budget the same, we scale the number of subsets n according to a. We train 800, 400, 200, 100 models with = 2, 5, 10, 20, respectively. We observe similar convergence results as in Among them, a 5 yields a highest Spearman's correlation of 0.89 between f(-) and g(-).
Figure 7.
MSE (Holiout)
2.0
Spearman Cor:: 0.88
MSE (Holiout)
2.0
Spearman Corr.; 0.80
MSB (Holiout))
Speerman Corr.: 0.82
MSR (Holdout))
2.0
Spearman Corr. 0.T
MSE
MSF
MSF
MSB
1.5-
1.5
1.5
1.0-
1.0
1.0
1.0
0.5
0.5
0.5
0.5
0.0
400
600
800
100
200
300
400
100
150
200
25
100
72
72
7
71.
(a)
= 2
(b)
=
(c)
10
(d)
20
Figure 7: Fitting surrogate models using different a evaluated on a fixed target task.
Number of sampled subsets: Lastly, we show that task selection remains stable under different values of n. We measure the effect on two tasks (Hl and LA) by comparing the 10 tasks with the smallest coefficients estimated from 100,200, 400 subsets. We observe that using 100 subsets identifies 7/10 source tasks compared with = 400. Increasing to 200 further identifies 9 10 source tasks compared with n 400.
29


Reviews:
[{"review_id": "NbwbpcLu6v", "reviewer": "Reviewer_Nt3Y", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* Overall, I thought this paper did a very good job in justifying the proposed algorithm. The theoretical evidence may not be very satisfying, but its development added to my understanding of the algorithm, and I appreciated the clarity of its exposition (both in the main and appendix). The experiments provided more convincing evidence considering relevant settings and showing consistent improvements across different multitask settings.\n  * Given the proof approach, the Rademacher-based bound can't say much when the target task's validation sample is small, i.e., approaching the few-shot setting. However, looking at dataset sizes in the main tables and appendix, the proposed method does perform well at somewhat low validation set sizes. It might be good for the paper to briefly highlight this dimension of the method's performance.\n\n* The potential weakness here is in the paper not discussing the limitations of the proposed method directly.\n  * The proposed method's computational cost relative to competitors: the runtime cost in section 4.2 is fine to include but not sufficient to address this weakness.\n  * Does the theoretical development shed light on the $(n, m)$ regime where the proposed algorithm would be preferred to single task learning on the target? E.g., among a set of linear prediction tasks as described for Theorem 3.1?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers the multitask learning setting wherein a set of \"source\" tasks/datasets are available to augment with when training on a \"target\" task/dataset.\nGiven a target task sample, the paper proposes a parameterized algorithm for identification/selection of an $\\alpha$-sized subset of source tasks to add to the training set of the target sample.\nThe algorithm constructs a linear predictive model of transfer by minimizing squared loss on a dataset of size $n$ whose examples are 1-hot encodings of source task presence/absence and whose labels are model performance when trained on the selected sources + target datasets.\nThen, the algorithm compares the linear coefficients of the predictive model, or source relevance scores, to a threshold $\\gamma$ to select the source tasks for multitask training.\n\nThe accompanying guarantees show that the algorithm's estimated coefficients converge to the population coefficients and that a threshold value exists, under some conditions, for linear regression tasks. The experiments consist of three multitask learning settings: selecting labelers in a weak supervision setting, standard NLP multitask learning, and robust learning in a multi-group setting. The proposed algorithm shows improvement over single task, naive multitask, and other competitor baselines in all settings. Some ablations and further analysis suggest the proposed algorithm is not sensitive to its parameters, validates some settings selected for the experiments, and suggests the algorithm is somehow capturing the effect of higher-order interactions between source and target tasks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* What are the relative runtime differences b/w the proposed method and competitors listed in Table 1? Please include a summary of relative computational costs of the proposed method vs. competitors listed in the paper.\n\n* Does the result of Theorem 2.1 only hold when one knows the target task is composed of exactly $\\alpha$ source tasks?\n\n* Based on their experiments, can the authors say \n  * How often a set of source tasks not in the length-$n$ training set was selected?\n  * How often a set of source tasks of size less than size $\\alpha$ was selected? Greater than size $\\alpha$?\n  \n* Theorem 3.1 describes the conditions under which a threshold exists. This justifies the final selection step of the proposed algorithm. How does the the superlinear growth in $m$ (w.r.t. $p$) compare to conditions required for computing a corresponding \"good\" linear predictor when performing single task learning on the target?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "fbV3jPlX2e", "reviewer": "Reviewer_HbzV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "From the length of this paper, the mathematical analysis, and experimental results sections, it is clear the authors have invested significant time and effort into developing and evaluating their approach. I applaud their presentation of the experimental findings; it seems clear that their method \"works\".\n\nI have one suggestion for improvement: **make the manuscript more simple.**\n\nWhile I consider myself familiar with this space, it was surprisingly difficult for me to understand the proposed method, approach, and motivation. There seems to be a lack of structure to the abstract, introduction, and other sections of this paper which makes it difficult for a reader unfamiliar with this work to understand the message it seeks to convey. \n\nFor instance, you might simplify your abstract like:\n\n(1) [Multi-task is useful for objectives where labeled data is limited]: \nMulti-task learning is widely used throughout industry and academia to fit a training objective where labeled data is limited by training this objective alongside other objectives where data is more abundant. \n\n(2) [But identifying these other objectives is difficult]: \nHowever, identifying the training objectives that would improve the performance of the task with limited labeled data is difficult. \n\n(3) [It is difficult because source tasks can interfere with the training of the target task.]:\n...\n\n(4) [We propose a solution that models the association between a subset of source tasks and a target task by leveraging a surrogate model]:\n...\n\n(5) [We find this approach to predict negative transfer between source tasks and the target task]:\n...\n\nI also struggle to understand the formulation of the surrogate model. \n\nFigure 1 describes selecting a subset of task groupings, fully training a multi-task learning model with these groupings and the target task to compute $f(S_i)$: the performance of the target task when trained together with the tasks in $S_i$, and then a surrogacy model is introduced? What is this surrogate model? Why are you using $\\theta$ to indicate relevancy scores rather than its traditional usage as a model's parameters? What is $g_\\theta(S_i)$? What are the surrogacy model's inputs and outputs, and ow is it paramterized (i.e. what are its parameters -- a shallow MLP, CNN, etc.)? Later in the page, it says $g_\\theta(S) = \\sum_{j\\in S} \\theta_j$, where $\\theta_j$ are the relevancy scores. \n\nBut in one paragraph above, \"To estimate the relevance scores, we introduce a surrogate model $g_\\theta(S)$,  parametrized by the relevance scores, to approximate MTL performances.\" To me, this means you parameterize the model by the relevancy scores (i.e. these are the model's parameters), and you're using this model to predict the relevancy scores themselves?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work explores task selection in multi-task learning: given a target objective, which subset of a collection of source tasks would most improve the performance of the target? \n\nThis is a very challenging problem; non-linear interactions among different tasks often makes it difficult to identify such a collection of source tasks. For instance, while tasks A and B may individually help task X; training X together with A and B may actually result in performance degradation than from training X by itself. \n\nTo this end, the authors propose a three-step algorithm:\n(1) randomly sample a set of task sequences from the collection of source tasks. Let's say $n$ tasks sequences are sampled in total.\n(2) For each of the $n$ task sequences, fully train a multi-task model where the targets are the objectives in this sequence *and* the target objective (i.e. the task whose performance we would like to maximize).\n(3) Train a surrogate model to predict the influence of this sequence of source tasks on the target task.\n\nDuring test time, one can limit the sequence of source tasks to a single task to measure if this task offers \"positive\" or \"negative\" transfer on the target task.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please simplify the writing. Consider saying less to communicate more. Make it super simple, and clean up the notation to better convey your meaning. I'm also guilty of falling into this trap myself -- when you invest significant time into a project and think about it all the time -- it can be difficult to recognize another person/reader does not have the same context you do. The best & strongest works try to convey the readers understanding & familiarity into the minds of their audience. \n\nI'm currently marking \"No\" to both \"Claims and Evidence\" as well as \"Audience\" sections, as I do not understand your approach, and cannot confidently answer these questions in the affirmative. I suspect other readers may experience similar confusion.\n\nYou may also consider citing the following related work. While I don't think it's necessary to compare against its approach, a sentence in the related work about the (dis)similarity to your own approach would be appropriate: \n\n[1] Auto-λ: Disentangling Dynamic Task Relationships, Liu et al. \n\n------ Updated Response 2/16/23 ----- \n\nGiven the author's elucidating response and changes to their manuscript, I strongly endorse the publication of this work. ", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "uhSZrEWtdL", "reviewer": "Reviewer_ZoXn", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The motivation of this paper is good. This paper considered a critical problem in a multi-task learning problem, i.e., negative transfer, which has recently received much attention in the machine learning community. \nThe proposed algorithm seems promising, supported by rigorous theoretical guarantees and empirical studies.\n\nHowever, there are still some weaknesses in the work:\n1.\tThe contribution of this work is not clear. The authors should give more explanations about this, particularly the strengths of the proposed method against the existing literature targeting negative transfers.\n2.\tSome parts of the paper are difficult to understand and need to be improved. Details of them will be listed in the next part.\n3.\tThe related work for solving negative transfers in MTL is incomplete. For example, another essential line to address negative transfers in MTL is called block-diagonal structural learning, which aims at promoting positive information across all tasks and suppressing negative knowledge sharing in the learning process [1,2]. I think the authors should consider this and discuss the strengths of the proposed method.\n4.\tThe efficiency of the proposed algorithm is a significant concern, but it has not been well verified in the paper.\n\nRef:\n[1] Task-Feature Collaborative Learning with Application to Personalized Attribute Prediction.\n[2] Calibrated multi-task learning. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper aimed to improve the performance of multi-task learning problems by identifying the valuable subsets for the target task due to the wide existence of negative transfers. It proposed a simple algorithm that mainly includes two key steps: 1) sample some randoms subsets from source tasks and leverage them to train multiple surrogate models, respectively; 2) use the scores predicted by the surrogate model for each task as the standard to select the beneficial subsets to train the final model for the target task. Finally, theoretical analysis and comprehensive experiments are conducted to show the effectiveness of the proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1.\tIn Fig.1 and Alg.1, what is the surrogate model? What are its parameters? In the descriptions of the paper, it seems that the surrogate model $g_{\\theta}$ is just combined by some scalar value $\\theta_i$ for all k tasks. How do we generalize the proxy $g$ to the unseen task selections?\n2.\tIn Sec.2.2, it is unclear whether we need to train the surrogate model by sampling n subsets and then use the model to select the positive sources tasks to train the final prediction model for the target or both of the models are trained simultaneously. Thus, some of the method sections should be reorganized.\n3.\tIn Eq.(5), why the expectation of Rademacher complexity is taken by $\\tilde{D}$ instead $D_t$?\n4.\tIn Thm.2.1, what is the difference between $\\alpha$ and $m$? And how is the probability of at least 0.99 obtained?\n5.\tEach subset $S_i$ with size $\\alpha$ would be independently used to train a surrogate model. But I notice that the practical $\\alpha$ is relatively small, which seems insufficient to train a deep neural network model. How to deal with this case in the paper?\n6.\tIn my opinion, sampling multiple random subsets to train surrogate models is time-consuming and might be unaffordable in the practical deployment of deep learning models. The authors should provide the practical training time for both the proposed algorithm and the baseline models to show the efficiency.\n7.\tWhat is the effect of $\\gamma$ to the performance of negative transfers?\n8.\tSome new SOTA competitors that suppress the negative transfers in MTL should be compared, such as [1, 2].\n9.\tThis paper attempts to address the negative transfer problem across the task perspective, but the negative transfer across features is also essential. Is the proposed method available for this?\n", "broader_impact_concerns": "I don't have such concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents work on multitask learning. It focuses on an important and challenging research problem in multitask learning: given a target objective, which subset of source tasks can most improve the performance of the target? To address the problem, the paper proposes a simple but effective idea that tends to determine which tasks may train well together in multi-task learning paradigms. Both theoretical and experimental results are provided to confirm the superiority of the proposed method.

Before rebuttal, reviewers raise several concerns about this paper, including the running time of the algorithm, supplementary explanations of surrogate models, and several questions on theory parts. The authors provide detailed and convincing responses to address the concerns. Reviewers are satisfied with the responses and consider that this paper is stronger after revisions. AC and all reviews appreciate the contributions of this paper. We therefore recommend an acceptance.

This paper is high quality and then selected for the Featured Certification, which is recommended by most reviewers. After the responses from the authors, the claims of this paper are clearly justified. AE and reviewers consider that this paper makes sufficient contributions to the research area of multitask learning, including its strong motivation, simple and effective idea, and meaningful theoretical results. This paper will largely inspire follow-up research. Therefore, it deserves the Featured Certification and should be highlighted.


Decision: Accept (poster)