
\section{Introduction}





The state-of-the-art (SOTA) models in real-world applications rely increasingly on the usage of weak supervision signals \cite{pennington2014glove, devlin2019bert, liu2019multi}. 
Among these, \emph{cross-task} signals are one of the most widely-used weak signals 
\cite{zamir2018taskonomy, mccann2018natural}. 
Despite their popularity, the benefits of cross-task signals
are not well understood from a theoretical point of view, especially in the context of deep learning \cite{he2020foreshadowing, NEURIPS2020_0607f4c7}, hence impeding the efficient usage of those signals.
Previous work has adopted representation learning as a framework to understand the benefits of cross-task signals, where knowledge transfer is achieved by learning a representation shared across different tasks \cite{baxter2000model, maurer2016benefit, tripuraneni2020provable,tripuraneni2020theory, du2021fewshot}. 
However, the existence of a shared representation is often too strong an assumption in practice. Such an assumption also makes it difficult to reason about several critical aspects of cross-task learning, such as the quantification of the value of the source data and the impact of fine-tuning \cite{kalan2020minimax, chua2021fine}. 

In this paper, we propose {\bf T}arget-{\bf A}ware {\bf W}eighted {\bf T}raining (\NAMEALG), a weighted training algorithm for efficient cross-task learning. 
The algorithm can be easily applied to existing cross-task learning paradigms, such as pre-training and joint training, to boost their sample efficiency

by assigning adaptive (i.e., trainable) weights on the source tasks or source samples.
The weights 
are determined in a theoretically principled way by minimizing a representation-based task distance between the source and target tasks. 
Such a strategy is in sharp contrast to other weighting schemes common in machine learning, 
such as importance sampling in domain adaptation \cite{shimodaira2000improving, cortes2010learning, jiang2007instance}.


The effectiveness of \NAMEALG{} is verified via both theoretical analyses and empirical experiments.
Using empirical process theory, we prove a non-asymptotic generalization bound for \NAMEALG{}. The bound is a superposition of a vanishing term and a term depending on the task distance, the latter of which is potentially negligible due to the re-weighting operation.
For brevity, all proofs for the theory part are deferred to the Appx. \ref{sec:appx-theory}.
We then conduct comprehensive experiments
on four sequence tagging tasks in natural language processing (NLP): part-of-speech (PoS) tagging, chunking, predicate detection, and named entity recognition (NER). 
We demonstrate that \NAMEALG{} further improves the performance of BERT \cite{devlin2019bert} in both pre-training and joint training for cross-task learning with limited target data, achieving an average absolute improvement of $2.5\%$ on the performance. 

As a byproduct, we propose a representation-based task distance that depends on the quality of representations for each task, respectively, instead of assuming the existence of a single shared representation among all tasks.
This finer-grained notion of task distance 
enables 
a better understanding of 
cross-task signals.
For example, the representation-based task distance gives an interpretable measure of the value of the source data on the target task based on 
the discrepancy between their optimal representations.
Such a measure is more informative than measuring the difference between tasks via
the discrepancy of their task-specific functions (e.g. linear functions) as done in  
previous theoretical frameworks \cite{tripuraneni2020theory}.
Furthermore, the representation-based task distance clearly conveys the necessity of fine-tuning:  if 
this distance is non-zero, then fine-tuning the representation becomes necessary
as the representation learned from the source data does not converge to the optimal target representation.

{Finally, we conclude the introduction part by comparing our work with some recent attempts in the similar directions. \citet{liu2020meta} analyze the benefits of transfer learning by distinguishing source-specific features and transferable features in the source data. 
Based on the two types of features, they further propose a meta representation learning algorithm to encourage learning transferable and generalizable features. 
Instead of focusing on the distinction between two types of features, our algorithm and analyses are based on the representation-based task distance and are thus different.
\citet{chua2021fine} present a theoretical framework for analyzing representations derived from model agnostic meta learning \cite{finn2017model}, assuming all the tasks use approximately the same underlying representation. 
In contrast, we do not impose any a priori assumption on the proximity among source and target representations, and our algorithm seeks for a weighting scheme to maximize the proximity.
} 

\iffalse
{\bf Paper organization.} Section \ref{sec:alg} gives the optimization formulation and algorithmic derivation of \NAMEALG.
Section \ref{sec:theory} studies the theoretical properties of \NAMEALG. In particular, we introduce a representation-based task distance in Section \ref{subsec:dist}, give an alternative derivation of \NAMEALG~based on task distance minimization in Section \ref{subsec:alg_as_dist_minimization}, and establish learning-theoretic guarantees for \NAMEALG~in Section \ref{subsec:alg_performance}. Section \ref{sec:experiments} contains numerical experiments. Section \ref{sec:discuss} concludes with a discussion of open problems.
For brevity, proofs and experimental details are deferred to the appendices.
\fi
\section{\NAMEALG: Target-Aware Weighted Training}\label{sec:alg}



\subsection{Preliminaries}
Suppose we have $T$ source tasks, represented by a collection of probability distributions $\{\calD_t\}_{t=1}^T$ on the sample space $\calX\times \calY$, where $\calX\subseteq \bbR^d$ is the feature space and $\calY \subseteq \bbR$ is the label space\footnote{For classification problems, we take $\calY$ to be a finite subset of $\bbR$.}.
We have a single target task, whose probability distribution is denoted as $\calD_0$.
For the $t$-th task, where $t = 0, 1, \hdots, T$, we observe $n_t$ i.i.d.~samples $S_t = (\bsx_{ti}, y_{ti})_{i=1}^{n_t}$ from $\calD_t$.
Typically, the number of samples from the target task, $n_0$, is much smaller than the samples from the source tasks, and the goal is to use samples from source tasks to aid the learning of the target task.


Let $\Phi$ be a collection of \emph{representations} from the feature space $\calX$ to some latent space $\calZ \subseteq \bbR^r$. 
We refer to $\Phi$ as the \emph{representation class}.
Let $\calF$ be a collection of \emph{task-specific functions} from the latent space $\calZ$ to the label space $\calY$. 
The complexity of the representation class $\Phi$ is usually much larger (i.e., more expressive) than that of the task-specific function class $\calF$.

Given a bounded loss function $\ell: \calY\times \calY \to [0, 1]$, the optimal pair of representation and task-specific function of the $t$-th task is given by
\begin{equation}
	\label{eq:opt_enc_dec_pair}
	(\phi^\star_t, f^\star_t) \in \argmin_{\phi_t\in\Phi, f_t\in\calF} \calL_t(\phi_t, f_t), \qquad \calL_t(\phi_t, f_t) :=  \bbE_{(X, Y)\sim\calD_t} [\ell(f_t\circ\phi_t(X), Y)].
\end{equation}
Note that in general, the optimal representations of different tasks are different.

\subsection{Derivation of \NAMEALG}
Under the assumption that the optimal representations $\{\phi^\star_t\}_{t=0}^T$ are similar, a representation learned using samples only from the source tasks would perform reasonably well on the target task. 
Consequently, we can devote $n_0$ samples from the target task to learn only the task specific function. This is a much easier task, since the complexity of $\calF$ is typically much smaller than that of $\Phi$.

This discussion leads to a simple yet immensely popular two-step procedure as follows \cite{du2021fewshot, tripuraneni2020theory}.
First, we solve a weighted empirical risk minimization problem with respect to the source tasks:
\begin{equation}
	\label{eq:representation_learning}
	(\hat \phi, \{\hat f_t\}_{t=1}^T)  \in \argmin_{\phi\in \Phi, \{f_t\} \subset \calF} \sum_{t=1}^T \omega_t \hat\calL_t(\phi, f_t), 
	\qquad
	\hat\calL_t(\phi, f_t) := \frac{1}{n_t} \sum_{i=1}^{n_t} \ell(f_t\circ\phi(\bsx_{ti}), y_{ti}),
\end{equation}
where ${\boldsymbol{\omega}} \in \Delta^{T-1}$ is a user-specified vector lying in the $T$-dimensional probability simplex (i.e., $\sum_{t=1}^T \omega_t = 1$ and $\omega_t \geq 0, \forall 1\leq t\leq T$).
In the second stage, we freeze the representation $\hat\phi$, and seek the task-specific function that minimizes the empirical risk with respect to the target task:
\begin{equation}
	\label{eq:representation_transfer}
	\hat f_0 \in \argmin_{f_0\in\calF} \hat\calL_0(\hat\phi, f_0).
\end{equation}
In practice, 
we can allow $\hat\phi$ to slightly vary (i.e., via fine tuning) to get a performance boost. 
In the two-step procedure \eqref{eq:representation_learning}--\eqref{eq:representation_transfer}, the weight vector ${\boldsymbol{\omega}}$ is usually taken to be a hyperparameter and is \emph{fixed} during training. Popular choices
include the uniform weights (i.e., $\omega_t = 1/T$) or weights proportional to the sample sizes (i.e., $\omega_t = n_t/\sum_{t'=1}^T n_{t'}$)  \citep{liu2019multi, johnson2019survey}. 
This reveals the \emph{target-agnostic} nature of the two-step procedure \eqref{eq:representation_learning}--\eqref{eq:representation_transfer}: the weights stay the same regardless the level of proximity between the source tasks and the target task

Consider the following thought experiment: if we know a priori that the first source task $\calD_1$ is closer (compared to other source tasks) to the target task $\calD_0$, then we would expect a better performance by raising the importance of $\calD_1$, i.e., make $\omega_1$ larger. 
This thought experiment motivates a \emph{target-aware} procedure that adaptively adjusts the weights based on the proximity of source tasks to the target.
A natural attempt for developing such a task-aware procedure is a follows:
\begin{align}
	\label{eq:alg_constrained_ver}
	\tag{OPT1}
	\min_{\substack{\phi\in\Phi, f_0\in \calF, \\  {\boldsymbol{\omega}} \in \Delta^{T-1}}} \hat\calL_0(\phi, f_0) 
	\qquad  \textnormal{subject to } 
	\phi \in \argmin_{\psi\in\Phi} \min_{\{f_t\} \subset \calF} \sum_{t=1}^T \omega_t \hat\calL_t(\psi, f_t).
\end{align}
That is,
we seek for the best weights ${\boldsymbol{\omega}}$ such that solving \eqref{eq:representation_learning} with this choice of ${\boldsymbol{\omega}}$ would lead to the lowest training error when we subsequently solve \eqref{eq:representation_transfer}.

Despite its conceptual simplicity, the formulation \eqref{eq:alg_constrained_ver} is a complicated constrained optimization problem. 
Nevertheless, we demonstrate that it is possible to transform it into an unconstrained form for which a customized gradient-based optimizer could be applied.
To do so, we let $(\phi^{\boldsymbol{\omega}}, \{f_t^{\boldsymbol{\omega}}\})$ be any representation and task-specific functions that minimizes 
$


	\sum_{t=1}^T \omega_t \hat\calL_t(\phi, f_t)
$
over $\phi\in\Phi$ and $\{f_t\}\subset \calF$.
Equivalently, $\phi^{\boldsymbol{\omega}}$ minimizes
$
	\sum_{t=1}^T \omega_t \min_{f_t \in \calF} \hat\calL_t(\phi, f_t)
$
over $\phi \in \Phi$.
With such notations, we can re-write \eqref{eq:alg_constrained_ver} as 
\begin{equation}
	\label{eq:alg_unconstrained_ver}
	\tag{OPT2}
	\min_{f_0\in\calF, {\boldsymbol{\omega}} \in \Delta^{T-1}} \hat \calL_0(\phi^{\boldsymbol{\omega}}, f_0).
\end{equation}
The gradient of the above objective with respect to the task-specific function, $\nabla_f \hat\calL_0(\phi^{\boldsymbol{\omega}}, f_0)$, is easy to calculate via back-propagation. 
The calculation of the gradient with respect to the weights requires more work, as $\phi^{\boldsymbol{\omega}}$ is an implicit function of ${\boldsymbol{\omega}}$.
By the chain rule, we have
$
	\frac{\partial}{\partial \omega_t} \hat\calL_0(\phi^{\boldsymbol{\omega}}, f_0) = [\nabla_\phi \hat\calL_0(\phi^{\boldsymbol{\omega}}, f_0)]^\top \frac{\partial}{\partial \omega_t} \phi^{\boldsymbol{\omega}}.
$
Since $\phi^{\boldsymbol{\omega}}$ is a minimizer of $\phi\mapsto \sum_{t=1}^T \omega_t \min_{f_t \in \calF} \hat\calL_t(\phi, f_t)$, we have
\begin{equation}
	\label{eq:implicit_function}
	F(\phi^{\boldsymbol{\omega}}, {\boldsymbol{\omega}})= 0, ~ \forall {\boldsymbol{\omega}} \in \Delta^{T-1}, \qquad F(\phi, {\boldsymbol{\omega}}):= \nabla_\phi \sum_{t=1}^T \omega_t \min_{f_t\in\calF} \hat\calL_t(\phi, f_t).
\end{equation}
By implicit function theorem, if $F(\cdot, \cdot)$ is everywhere differentiable 
and the matrix $\partial F(\phi, {\boldsymbol{\omega}})/\partial \phi$ is invertible for any $(\phi, {\boldsymbol{\omega}})$ near some $(\tilde\phi, \tilde {\boldsymbol{\omega}})$ satisfying $F(\tilde\phi, \tilde {\boldsymbol{\omega}}) = 0$, then we can conclude that the map ${\boldsymbol{\omega}} \mapsto \phi^{\boldsymbol{\omega}}$ is a locally well-defined function near $\tilde {\boldsymbol{\omega}}$, and the derivative of this map is given by
\begin{equation}
	\label{eq:implicit_function_gradient_wrt_weights}
	\frac{\partial}{\partial \omega_t} \phi^{\boldsymbol{\omega}} 
	= - \bigg(\frac{\partial F(\phi, {\boldsymbol{\omega}})}{\partial \phi}\bigg|_{\phi = \phi^{\boldsymbol{\omega}}}\bigg)^{-1}  \bigg( \frac{\partial F(\phi, {\boldsymbol{\omega}})}{\partial \omega_t}\bigg|_{\phi = \phi^{\boldsymbol{\omega}}}\bigg).
\end{equation}
To simplify the above expression, note that under regularity conditions,
we can regard $\nabla_\phi \hat\calL_t(\phi, f_t^{\boldsymbol{\omega}})$ as a sub-gradient of the map $\phi\mapsto \min_{f_t\in\calF} \hat\calL_t(\phi, f_t)$. This means that we can write 
$
	F(\phi^{\boldsymbol{\omega}}, {\boldsymbol{\omega}}) = \sum_{t=1}^T \omega_t \nabla_\phi \hat \calL_t(\phi^{\boldsymbol{\omega}}, f_t^{\boldsymbol{\omega}}).
$
Plugging this expression back to \eqref{eq:implicit_function_gradient_wrt_weights} and recalling the expression for $\partial \hat\calL_0(\phi^{\boldsymbol{\omega}}, f_0)/\partial \omega_t$ derived via the chain rule, we get 
\begin{equation}
	\frac{\partial}{\partial \omega_t} \hat\calL_0(\phi^{\boldsymbol{\omega}}, f_0) =  - [\nabla_\phi \hat\calL_0(\phi^{\boldsymbol{\omega}}, f_0)]^\top  
	\Big[\sum_{t=1}^T \omega_t \nabla_\phi^2 \hat\calL_t(\phi^{\boldsymbol{\omega}}, f_t^{\boldsymbol{\omega}})\Big]^{-1} 
	[\nabla_\phi \hat\calL_t(\phi^{\boldsymbol{\omega}}, f_t^{\boldsymbol{\omega}})].
\end{equation}
\begin{algorithm}[t!] 
\SetAlgoLined
\caption{{\bf T}arget-{\bf A}ware {\bf W}eighted {\bf T}raining (\NAMEALG)}
\vspace*{0.12 cm}
\KwIn{Datasets $\{S_t\}_{t=0}^T$.}
\KwOut{Final pair of representation and task-specific function $(\hat \phi, \hat f_0)$ for the target task.}
Initialize parameters ${\boldsymbol{\omega}}^0\in\Delta^{T-1}, \phi^0 \in \Phi, \{f_t^0\}_{t=0}^T \subset \calF$\;
\For{$k = 0,  \hdots, K-1$}{
Starting from $(\phi^k, \{f^k_t\}_{t=1}^T)$, run a few steps of SGD 
to get $(\phi^{k+1}, \{f_t^{k+1}\}_{t=1}^T)$\;
Use the approximate gradient $\nabla_f \hat\calL_0(\phi^{k+1}, f_0)$ to run a few steps of SGD from $f_0^k$ to get $f_0^{k+1}$\;
Run one step of approximate mirror descent \eqref{eq:task_gradient}--\eqref{eq:mirror_descent} from ${\boldsymbol{\omega}}^k$ to get ${\boldsymbol{\omega}}^{k+1}$\;
}
\Return{$\hat \phi = \phi^{K}, \hat f_0 = f_0^{K}$}
\label{alg}
\end{algorithm}
Now that we have the expressions for the gradients of $\hat\calL_0(\phi^{\boldsymbol{\omega}}, f_0)$ with respect to $f_0$ and ${\boldsymbol{\omega}}$, we can solve \eqref{eq:alg_unconstrained_ver} via a combination of alternating minimization and mirror descent. 
To be more specific, suppose that at iteration $k$, the current weights, representation, and task-specific functions are ${\boldsymbol{\omega}}^k, \phi^k,$ and $\{f^k_t\}_{t=0}^T$, respectively. At this iteration, we conduct the following three steps:
\begin{enumerate}[leftmargin=0.5cm]
	\item Freeze ${\boldsymbol{\omega}}^k$. Starting from $(\phi^k, \{f^k_t\}_{t=1}^T)$, run a few steps of SGD on the objective function $(\phi, \{f_t\}_{t=1}^T) \mapsto \sum_{t=1}^T \omega_t^k \hat\calL_t(\phi, f_t)$ to get $(\phi^{k+1}, \{f_t^{k+1}\}_{t=1}^T)$, which is regarded as an approximation of $(\phi^{{\boldsymbol{\omega}}^k}, \{f_t^{{\boldsymbol{\omega}}^k}\}_{t=1}^T)$;
	\item Freeze $(\phi^{k+1}, \{f_t^{k+1}\}_{t=1}^T)$. Approximate the gradient $\nabla_f \hat\calL_0(\phi^{{\boldsymbol{\omega}}^{k}}, f_0)$ by $\nabla_f \hat\calL_0(\phi^{k+1}, f_0)$. Using this approximate gradient, run a few steps of SGD from $f_0^k$ to get $f_0^{k+1}$;
	\item Freeze $(\phi^{k+1}, \{f_t^{k+1}\}_{t=0}^T)$. Approximate the partial derivative $\partial \hat\calL_0(\phi^{{\boldsymbol{\omega}}^k}, f^{k+1}_0)/\partial \omega_t$ by 
	\begin{equation}
	    \label{eq:task_gradient}
		g^k_t := - [\nabla_\phi \hat\calL_0(\phi^{k+1}, f_0^{k+1})]^\top  
		\Big[\sum_{t=1}^T \omega_t \nabla_\phi^2 \hat\calL_t(\phi^{k+1}, f_t^{k+1})\Big]^{-1} 
		[\nabla_\phi \hat\calL_t(\phi^{k+1}, f_t^{k+1})].		
	\end{equation}
	Then run one step of mirror descent (with step size $\eta^k$) from ${\boldsymbol{\omega}}^{k}$ to get ${\boldsymbol{\omega}}^{k+1}$:
	\begin{equation}
		\label{eq:mirror_descent}
		\omega_t^{k+1} = \frac{\omega_t^k \exp\{-\eta^k g^{k}_t\} }{\sum_{t'=1}^T \omega_{t'}^{k}\exp\{-\eta^k g^{k}_{t'}\}}.
	\end{equation}
\end{enumerate}

We use mirror descent in \eqref{eq:mirror_descent}, as it is a canonical generalization of Euclidean gradient descent to gradient descent on the probability simplex \citep{beck2003mirror}.  
The update rule \eqref{eq:mirror_descent} has a rather intuitive explanation. 
Note that $g^{k}_t$ is a weighted dissimilarity measure between the gradients $\nabla_\phi \hat \calL_0$ and $\nabla_\phi \hat\calL_t$. 
This can further be regarded as a crude dissimilarity measure between the optimal representations of the target task and the $t$-th source task. 
The mirror descent updates $\omega_t$ along the direction where the target task and the $t$-th source task are more similar.
The overall procedure is summarized in Algorithm \ref{alg}.

A faithful implementation of the above steps would require a costly evaluation of the inverse of the Hessian matrix $\sum_{t=1}^T \omega_t \nabla_\phi^2 \hat\calL_t(\phi^{k+1}, f_t^{k+1})\in\bbR^{r\times r}$. 
In practice, we can bypass this step by replacing the Hessian-inverse-weighted dissimilarity measure \eqref{eq:task_gradient} with a consine-similarity-based dissimilarity measure (see Section \ref{sec:experiments} for details).


The previous derivation has focused on weighted pre-training, i.e., the target data is not used when defining the constrained set in \eqref{eq:alg_constrained_ver}. 
It can be modified, \emph{mutatis mutandis}, to handle weighted joint-training, where we change \eqref{eq:alg_constrained_ver} to
\begin{align}


	\min_{\substack{\phi\in\Phi, f_0\in \calF, \\  {\boldsymbol{\omega}} \in \Delta^{T}}} \hat\calL_0(\phi, f_0) 
	\qquad  \textnormal{subject to } 
	\phi \in \argmin_{\psi\in\Phi} \min_{\{f_t\} \subset \calF} \sum_{t=0}^T \omega_t \hat\calL_t(\psi, f_t).
\end{align}
Compared to \eqref{eq:alg_constrained_ver}, we now also use the data from the target task when learning the representation $\phi$, and thus there is an extra weight $\omega_0$ on the target task.
The algorithm can also be easily extended to handle multiple target tasks or to put weights on samples (as opposed to putting weights on tasks). 
{We believe the algorithm could also be applied to improve the efficiency of learning from cross-domain and cross-lingual signals, and we postpone such explorations for future work.}






























\section{Theoretical Guarantees}\label{sec:theory}

\subsection{A Representation-Based Task Distance}\label{subsec:dist}

In this subsection, we introduce a {representation-based task distance}, which will be crucial in the theoretical understanding of \NAMEALG. 
To start with, let us define the representation and task-specific functions that are optimal in an ``${\boldsymbol{\omega}}$-weighted sense'' as follows:
\begin{equation}
	\label{eq:avg_opt_encder_and_decoders}
	(\bar \phi^{\boldsymbol{\omega}}, \{\bar f_t^{\boldsymbol{\omega}}\}_{t=1}^T) \in \argmin_{\phi\in\Phi, \{f_t\}\subset \calF} \sum_{t=1}^T \omega_t \calL_t(\phi, f_t) 
\end{equation}
Intuitively, $(\bar\phi^{\boldsymbol{\omega}}, \{\bar f_t^{\boldsymbol{\omega}}\})$ are optimal on the ${\boldsymbol{\omega}}$-weighted source tasks when only a single representation is used.
Since $\bar\phi^{\boldsymbol{\omega}}$ may not be unique, we introduce the function space $\bar\Phi^{\boldsymbol{\omega}} \subset \Phi$ to collect all $\bar\phi^{\boldsymbol{\omega}}$s that satisfy \eqref{eq:avg_opt_encder_and_decoders}.
To further simplify the notation, we let
$$
	\calL^\star_t(\phi) := \min_{f_t\in\calF} \calL_t(\phi, f_t).
$$
$\calL^\star_t(\phi)$ is the risk incurred by the representation $\phi$ on the $t$-th task.
With the above notation, we can write $\bar \phi^{\boldsymbol{\omega}} \in \argmin_{\phi\in\Phi} \sum_{t=1}^T \omega_t \calL^\star_t(\phi)$.
The definition of the task distance is given below.
\begin{definition}[Representation-based task distance]
    \label{def:task_dist}
    The representation-based task distance between the ${\boldsymbol{\omega}}$-weighted source tasks and the target task is defined as 
    \begin{equation}
        \label{eq:task_dist}
        \mathtt{dist}\Big(\sum_{t=1}^T \omega_t \calD_t, \calD_0\Big) :=  \sup_{\bar\phi^{\boldsymbol{\omega}} \in \bar\Phi^{\boldsymbol{\omega}}} \calL_0^\star(\bar\phi^{\boldsymbol{\omega}}) - \calL_0^\star(\phi^\star_0),
    \end{equation} 
    where the supremum is taken over any $\bar\phi^{\boldsymbol{\omega}}$ satisfying \eqref{eq:avg_opt_encder_and_decoders}, {and $\phi^\star_0$ is the optimal target representation}. 
\end{definition}
If all the tasks share the same optimal representation, 
then above distance becomes exactly zero.
Under such an assumption, the only source of discrepancy among tasks arises from the difference in their task-specific functions. 
This can be problematic in practice, as the task-specific functions alone are usually not expressive enough to describe the intrinsic difference among tasks.
In contrast, we relax the shared representation assumption substantially by allowing the optimal representations to differ and the distance to be non-zero.

The above notion of task distance also allows us to reason about certain important aspects of cross-task learning. For example, this task distance is asymmetric, capturing the asymmetric nature of cross-task learning.
Moreover, if the task distance is non-zero, then fine-tuning the representation becomes necessary, because solving \eqref{eq:representation_learning} alone would gives a representation that does not converge to the correct target $\phi_0^\star$. An empirical illustration of the representation-based task distance is in Appx. \ref{sec:appx-exp}.



\subsection{\NAMEALG~and Task Distance Minimization}\label{subsec:alg_as_dist_minimization}

{To give theoretical guarantees for \NAMEALG{}, we start by analyzing} the two-step procedure \eqref{eq:representation_learning}--\eqref{eq:representation_transfer} with fixed weights. 
Such an analysis requires a few standard technical assumptions. {The first one concerns the Lipschitzness of the function classes, and the second one controls the complexity of the function classes via uniform entropy \citep{wellner2013weak} as follows.}
\begin{assump}[Lipschitzness]
	\label{assump:lip}
	The loss function $\ell: \calY\times\calY \to [0, 1]$ is $L_\ell$-Lipschitz in the first argument, uniformly over the second argument. 
	Any $f\in\calF$ is $L_\calF$-Lipschitz w.r.t. the $\ell_2$ norm.
\end{assump}
\begin{assump}[Uniform entropy control of function classes]
\label{assump:unif_entropy}
There exist $C_\Phi >0, \nu_\Phi>0$, such that for any probability measure $\bbQ_\calX$ on $\calX\subseteq \bbR^d$, we have
\begin{equation}
  \label{eq:dim_encoder}
  \calN(\Phi; L^2(\bbQ_\calX); \ep) \leq (C_\Phi/\ep)^{\nu_\Phi}, \qquad \forall \ep > 0,
\end{equation}
where $\calN(\Phi; L^2(\bbQ_\calX); \ep)$ is the $L^2(\bbQ_\calX)$ covering number of $\Phi$ (i.e., the minimum number of $L^2(\bbQ_\calX)$ balls\footnote{For two functions $\phi, \psi\in\Phi$, their $L^2(\bbQ_\calX)$ distance is $\big({\int \|\phi(\bsx) - \psi(\bsx)\|^2 d\bbQ_\calX(\bsx)}\big)^{1/2}$.} 
with radius $\ep$ required to cover $\Phi$). 
In parallel, there exist $C_\calF>0, \nu_\calF>0$, such that for any probability measure $\bbQ_\calZ$ on $\calZ\subseteq\bbR^r$, we have 
\begin{equation}
  \label{eq:dim_decoder}
  \calN(\calF; L^2(\bbQ_\calZ); \ep) \leq (C_\calF/\ep)^{\nu_\calG}, \qquad \forall \ep > 0,
\end{equation}
where $\calN(\calF; L^2(\bbQ_\calZ); \ep)$ is the $L^2(\bbQ_\calZ)$ covering number of $\calF$. 
\end{assump}
Uniform entropy generalizes the notion of Vapnik-Chervonenkis dimension \citep{vapnik2013nature} and allows us to give a unified treatment of regression and classification problems.
For this reason, function classes satisfying the above assumption are also referred to as ``VC-type classes'' in the literature \citep{koltchinskii2006local}. 
In particular, if each coordinate of $\Phi$ has VC-subgraph dimension $\textnormal{\texttt{vc}}(\Phi)$, then \eqref{eq:dim_encoder} is satisfied with $\nu_\Phi = \Theta(r\cdot\textnormal{\texttt{vc}}(\Phi))$ (recall that $r$ is the dimension of the latent space $\calZ$). 
Similarly, if $\calF$ has VC-subgraph dimension $\textnormal{\texttt{vc}}(\calF)$, then \eqref{eq:dim_decoder} is satisfied with $\nu_\calF =\Theta(\textnormal{\texttt{vc}}(\calF))$. \


The following definition characterizes how ``transferable'' a representation $\phi$ is from the ${\boldsymbol{\omega}}$-weighted source tasks to the target task.
\begin{definition}[Transferability]
\label{def:transferable}
An representation $\phi\in\Phi$ is $(\rho, C_\rho)$-transferable from ${\boldsymbol{\omega}}$-weighted source tasks to the target task, if there exists $\rho>0, C_\rho>0$ such that for any $\bar \phi^{\boldsymbol{\omega}} \in \bar\Phi^{\boldsymbol{\omega}}$, we have
\begin{equation}
\label{eq:transferable}
	\calL_0^\star(\phi) - \calL_0^\star(\bar \phi^{\boldsymbol{\omega}} ) \leq C_\rho \bigg(\sum_{t=1}^T \omega_t [\calL^\star_t(\phi) - \calL^\star_t(\bar \phi^{\boldsymbol{\omega}})]\bigg)^{1/\rho}.
\end{equation}
\end{definition}
Intuitively, the above definition says that relative to $\bar \phi^{\boldsymbol{\omega}}$, the risk of $\phi$ on the target task can be controlled by a polynomial of the average risk of $\phi$ on the source tasks.
This can be regarded as an adaptation of the notions of transfer exponent and relative signal exponent \cite{hanneke2020value,cai2021transfer} originated from the transfer learning literature to the representation learning setting.
This can also be seen as a generalization of the task diversity assumption \cite{tripuraneni2020theory,du2021fewshot} to the case when the optimal representations $\{\phi^\star_t\}_{t=1}^T$ do not coincide.


The next theorem gives theoretical guarantees for the two-step procedure \eqref{eq:representation_learning}--\eqref{eq:representation_transfer}.

\begin{theorem}[Performance of the two-step procedure with fixed weights]
\label{thm:ub_fixed_weights}
Let $(\hat\phi, \hat f_0)$ be obtained via solving \eqref{eq:representation_learning}--\eqref{eq:representation_transfer} with fixed ${\boldsymbol{\omega}}$.
Let Assumptions \ref{assump:lip} and \ref{assump:unif_entropy} hold. 
Fix any $\delta\in(0, 1)$ and define $N_{\boldsymbol{\omega}} = (\sum_{t=1}^T \omega_t^2/n_t)^{-1}$. 
There exists a constant $C = C(L_\ell, L_\calF, C_\Phi, C_\calF)>0$ such that the following holds: if for any representation $\phi$ in a $C\sqrt{(\nu_\Phi + T\nu_\calF + \log \delta^{-1})/N_{\boldsymbol{\omega}}}$-neighborhood of $\bar\Phi^{\boldsymbol{\omega}}$\footnote{A representation $\phi$ is in an $\ep$-neighborhood of $\bar\Phi^{\boldsymbol{\omega}}$ if $\sum_{t=1}^T \omega_t [\calL_t^\star(\phi) - \calL_t^\star(\bar \phi^{\boldsymbol{\omega}})] \leq \ep $.},  
there exists a specific $\bar \phi^{\boldsymbol{\omega}} \in \bar \Phi^{\boldsymbol{\omega}}$ such that $\phi$ is $(\rho , C_\rho)$-transferable, then there exists another $C' = C'(L_\ell, L_\calF, C_\Phi, C_\calF, C_\rho, \rho)$ such that with probability at least $1-\delta$, we have
\begin{align}
	\calL_0(\hat\phi, \hat f_0) - \calL_0(\phi^\star_0, f_0^\star) & 
	\leq C' \bigg[\bigg(\frac{\nu_\calF + \log(1/\delta)}{n_0}\bigg)^{\frac{1}{2}} + \bigg(\frac{\nu_\Phi + T\nu_\calF + \log(1/\delta)}{N_{\boldsymbol{\omega}}}\bigg)^{\frac{1}{2\rho}}\bigg]\nonumber\\
	\label{eq:ub_fixed_weights}
	& \qquad + \mathtt{dist}\Big(\sum_{t=1}^T \omega_t \calD_t, \calD_0\Big).
\end{align}
\end{theorem}


The upper bound in \eqref{eq:ub_fixed_weights} is a superposition of three terms. Let us disregard the $\log(1/\delta)$ terms for now and focus on the dependence on the sample sizes and problem dimensions. The first term, which scales with $\sqrt{\nu_\calF/n_0}$, corresponds to the error of learning the task-specific function in the target task. 
This is unavoidable even if the optimal representation $\phi^\star_0$ is known. 

The second term that scales with $[(\nu_\Phi+ T\nu_\calF)/N_{\boldsymbol{\omega}}]^{1/2\rho}$ characterizes the error of learning the imperfect representation $\bar \phi^{\boldsymbol{\omega}}$ from the source datasets and transferring the knowledge to the target task. 
Note that this term is typically much smaller than $\sqrt{(\nu_\Phi + \nu_\calF)/n_0}$, the error that would have been incurred when learning only from the target data, thus illustrating the potential benefits of representation learning.
This happens because $N_{\boldsymbol{\omega}}$ is typically much larger than $n_0$ as long as the weights are not too imbalanced (e.g., when $\omega_t = n_t/\sum_{t'=1}^T n_{t'}$, then $N_{\boldsymbol{\omega}} = \sum_{t=1}^T n_t$).

The third term is precisely the task distance introduced in Definition \ref{def:task_dist}.
The form of the task distance immediately demonstrates the possibility of ``matching'' $\bar\phi^{\boldsymbol{\omega}} \approx \phi_0^\star$ via varying the weights ${\boldsymbol{\omega}}$, under which case the third term would be negligible compared to the former two terms.
For example, in Appx. \ref{appx:exact_match}, we give a sufficient condition for exactly matching $\bar\phi^{\boldsymbol{\omega}} = \phi^\star_0$.

Note that the task distance $\mathtt{dist}(\sum_{t=1}^T \omega_t\calD_t, \calD_0)$ can be naturally estimated from the data by replacing all population quantities with their empirical version. 
Indeed, if we estimate $\calL_0^\star(\phi) = \min_{f_0\in\calF}\calL_0(\phi, f_0)$ by $\min_{f_0\in\calF}\hat\calL_0(\phi, f_0)$ and $\bar \phi^{\boldsymbol{\omega}} \in \argmin_{\phi\in\Phi} \sum_{t=1}^T \omega_t \cdot \min_{f_t\in\calF}\calL_t(\phi, f_t)$ by the argmin of $\sum_{t=1}^T \omega_t \cdot\min_{f_t\in\calF}\hat \calL_t(\phi, f_t)$, then overall, the quantity $\calL_0^\star(\bar\phi^{\boldsymbol{\omega}})$ can be estimated by
$$
	\min_{f_0\in\calF}\hat\calL_0(\phi, f_0) \qquad \textnormal{subject to } \phi \in \argmin_{\psi\in\Phi} \sum_{t=1}^T \omega_t \hat\calL_t(\psi, f_t).
$$
Thus, minimizing the estimated task distance over the weights (note that $\calL_0^\star(\phi^\star)$ is a constant) is equivalent to the optimization formulation \eqref{eq:alg_constrained_ver} of our algorithm. This gives an alternative and theoretically principled derivation of \NAMEALG.


The proof of Theorem \ref{thm:ub_fixed_weights} is based on empirical process theory. Along the way, we also establish an interesting result on multi-task learning, where the goal is to improve the average performance for all tasks instead of target tasks (see Lemma \ref{lemma:err_learn_encoder}). The current analysis can also be extended to cases where multiple target tasks are present. 



\subsection{Performance Guarantees for \NAMEALG}\label{subsec:alg_performance}

In this subsection, we prove a non-asymptotic generalization bound for \NAMEALG.
The fact that the weights are learned from the data substantially complicates the analysis.
To proceed further, we make a few simplifying assumptions.
First, we assume that the sample sizes of the source data are relatively balanced: there exists an integer $n$ such that $n_t = \Theta(n)$ for any $t\in\{1, \hdots, T\}$.
Meanwhile, instead of directly analyzing \eqref{eq:alg_constrained_ver}, we focus on its sample split version. 
In particular, we let $B_1 \cup B_2$ be a partition of $\{1, \hdots, n_0\}$, where $|B_1| = \Theta(|B_2|)$. 
Define 
$$
	\hat\calL^{(1)}_0(\phi, f_0) := \frac{1}{|B_1|} \sum_{i\in B_1} \ell(f_0\circ \phi(\bsx_{0i}), y_{0i}) , \qquad 
	\hat\calL^{(2)}_0(\phi, f_0) := \frac{1}{|B_2|} \sum_{i\in B_2} \ell(f_0\circ \phi(\bsx_{0i}), y_{0i}) .
$$
We first solve \eqref{eq:alg_constrained_ver} restricted to the first part of the data:
\begin{align}
	\label{eq:alg_constrained_ver_sample_split_1}

	(\hat \phi, \hat {\boldsymbol{\omega}} ) \in \argmin_{\substack{\phi\in\Phi, {\boldsymbol{\omega}} \in \Delta^{T-1}}} \min_{f_0\in \calF} \hat\calL_0^{(1)}(\phi, f_0) 
	\qquad  \textnormal{subject to } 
	\phi \in \argmin_{\psi\in\Phi} \min_{\{f_t\} \subset \calF} \sum_{t=1}^T \omega_t \hat\calL_t(\psi, f_t).
\end{align}
Then, we proceed by solving
\begin{align}
	\label{eq:alg_constrained_ver_sample_split_2}
	\hat f_0 \in \argmin_{f_0\in\calF} \hat \calL_0^{(2)} (\hat \phi, f_0).
\end{align}
Such a sample splitting ensures the independence of $\hat\phi$ and the second part of target data $B_2$, hence allowing for more transparent theoretical analyses\footnote{Such strategies are common in statistics and econometrics literature when the algorithm has delicate dependence structures (see, e.g., \cite{hansen2000sample,chernozhukov2018double})}.
We emphasize that sample splitting is conducted only for theoretical convenience and is not used in practice. 



The following theorem gives performance guarantees for the sample split version of \NAMEALG.
\begin{theorem}[Performance of \NAMEALG~with sample splitting]
\label{thm:ub_learned_weights}
Let $(\hat\phi, \hat f_0)$ be obtained via solving \eqref{eq:alg_constrained_ver_sample_split_1}--\eqref{eq:alg_constrained_ver_sample_split_2}.
Let Assumptions \ref{assump:lip} and \ref{assump:unif_entropy} hold. 
In addition, assume that the learned weights satisfy $\hat{\boldsymbol{\omega}}\in\calW_\beta := \{{\boldsymbol{\omega}} \in \Delta^{T-1}: \beta^{-1} \leq \omega_t/\omega_{t'} \leq \beta , \forall t\neq t'\}$, where $\beta\geq 1$ is a absolute constant. 
Fix $\delta\in(0, 1)$. 
There exists a constant $C = C(L_\ell, L_\calF, C_\Phi, C_\calF)>0$ such that the following holds: if for any weights ${\boldsymbol{\omega}}\in\calW_\beta$ and any representation $\phi$ in a $C \beta\cdot \sqrt{({\nu_\Phi \log \delta^{-1}})/{{nT}} + ({\nu_\calF + \log T})/{n}}$-neighborhood of $\bar\Phi^{\boldsymbol{\omega}}$,
there exists a specific $\bar \phi^{\boldsymbol{\omega}}\in\bar\Phi^{\boldsymbol{\omega}}$ such that $\phi$ is $(\rho , C_\rho)$-transferable, then there exists another $C' = C'(L_\ell, L_\calF, C_\Phi, C_\calF, C_\rho, \rho)$ such that with probability at least $1-\delta$, we have 
\begin{align}
	\calL_0(\hat\phi, \hat f_0) - \calL_0(\phi^\star_0, f_0^\star) & 
	\leq C' \bigg[\bigg(\frac{\nu_\calF + \log(1/\delta)}{n_0}\bigg)^{\frac{1}{2}} + \beta^{1/\rho}\bigg(\frac{\nu_\Phi+ \log(1/\delta)}{nT} + \frac{\nu_\calF + \log T}{n}\bigg)^{\frac{1}{2\rho}}\bigg]\nonumber\\
	\label{eq:ub_learned_weights}
	& \qquad + \mathtt{dist}\Big(\sum_{t=1}^T \hat\omega_t \calD_t, \calD_0\Big).
\end{align}
\end{theorem}

Compared to the bound in Theorem \ref{thm:ub_fixed_weights}, the above bound is different in two main aspects. First, the second term in \eqref{eq:ub_learned_weights} is slightly worse than the second term in \eqref{eq:ub_fixed_weights}, as it involves an extra $\beta^{1/\rho}$ factor and an additional $\calO(\beta^{1/\rho}(\log T/n)^{1/2\rho})$ term.
This is a consequence of the fact that the weights are learned from the data.
Second, the task distance term in \eqref{eq:ub_learned_weights} involves the learned weights, as opposed to the fixed weights in \eqref{eq:ub_fixed_weights}.
The proof bears similarity to the proof of Theorem \ref{thm:ub_fixed_weights}, with additional complications in ensuring a uniform control of the learned (and thus random) weights.













\section{Experiments}

\label{sec:experiments}

\begin{table}[t]
\centering
\scalebox{0.96}{
\begin{tabular}{c||c|c|c|c||c}
\hline
 \diagbox[font=\footnotesize\itshape]{Learning Paradigm}{Target Task} & PoS & Chunking  & Predicate Detection & NER  & Avg \\ \hline
 Single-Task Learning & 34.37 & 43.05 & 66.26 & 33.20 & 44.22  \\ \hline
  Pre-Training & 49.43 & 73.15 & 74.10 & 41.22 & 59.48  \\ 
 Weighted Pre-Training & {\bf 51.17} *** & {\bf 73.41} & {\bf 75.77} *** & {\bf 46.23} *** & {\bf 61.64} \\ \hline
 Joint Training & 53.83 & 75.58 & 75.42 & 43.50 &  62.08  \\ 
 Weighted Joint Training & {\bf 57.34} *** & {\bf 77.78} *** & {\bf 75.98} *** & {\bf 53.44} *** & {\bf 66.14} \\ \hline
 Normalized Joint Training & 84.14 & 88.91 & {\bf 77.02} & 61.15 &  77.80 \\ 
 Weighted Normalized Joint Training & {\bf 86.07} *** & {\bf 90.62} *** &  76.67 & {\bf 63.44} *** & {\bf 79.20} \\ \hline

\end{tabular}}
\caption{The benefits of weighted training for different learning paradigms under different settings. There are four tasks in total, PoS tagging, chunking, predicate detection and NER. For each setting, we choose one task as the target task and the remaining three tasks are source tasks. We randomly choose $9K$ training sentences for each source task, because the training size of the chunking dataset is $8936$. As for the target task, we randomly choose $100$ training sentences for PoS tagging, $100$ training sentences for chunking, $300$ training sentences for predicate detection, and $500$ training sentences for NER respectively, based on the difficulty of tasks. Single-task learning denotes learning only with the small target data.
For each setting under a specific learning paradigm, the significance level based on the paired sampled t-test is also shown, where *** indicates the pvalue is smaller than $0.001$. More details can be found in Sec. \ref{sec:experiments}.
}
\label{table:results}
\end{table}

\begin{figure}[t]
	\centering
    \includegraphics[width=\textwidth]{figures/weighted_analysis.pdf}
    \caption{Analysis of the weighted training algorithms. We analyze the impact of two crucial factors on the improvement of the weighted training algorithms: the ratio between the training sizes of the source and target datasets, and the training size of the target dataset. In this figure, we use NER as the target task and source tasks include PoS tagging and predicate detection. In the first sub figure, we keep the training size of the target tasks as $500$, and change the ratio from $1$ to $128$ in a log scale. In the second (third) sub figure, we keep the ratio as $8$ ($10$), and change the training size of the target dataset from $500$ to $8000$ in a log scale. The corresponding improvement from the normalized joint training to the weighted normalized joint training is shown. 
   
    More details can be found in Sec. \ref{sec:experiments}.
    }
	\label{fig:analysis}
\end{figure}

\iffalse
\begin{figure}[t]
\centering
\subfigure[The impact of the ratio between the training size of the source dataset and the target dataset.]{
	\centering
	\includegraphics[scale=0.22]{figures/improvement_ratio.eps}
	\label{fig:ratio}
}
\subfigure[The impact of the training size of the target dataset.]{
	\centering
	\includegraphics[scale=0.22]{figures/improvement_main_training_size.eps}
	\label{fig:main-size}
}
\subfigure[Weighted-sample training.]{
	\centering
	\includegraphics[scale=0.22]{figures/weighted_sample.eps}
	\label{fig:weighted-sample}
}
\caption{Analysis.}
\label{fig:analysis}
\end{figure}
\fi

In this section, we verify the effectiveness of \NAMEALG{} in extensive experiments using four NLP tasks, including PoS tagging, chunking, predicate detection and NER. More details are in Appx. \ref{sec:appx-exp}.

{\bf Experimental settings.} In our experiments, we mainly use two widely-used NLP datasets, Ontontes 5.0 \citep{hovy2006ontonotes} and CoNLL-2000 \citep{sang2000introduction}. Ontonotes 5.0 contains annotations for PoS tagging, predicate detection and NER, and CoNLL-2000 is a shared task for chunking. There are about $116K$ sentences, $16K$ sentences and $12K$ sentences in the training, development, and test sets for tasks in Ontonotes 5.0. As for CoNLL-2000, there are about $9K$ sentences and $2K$ sentences in the training and test sets. As for the evaluation metric, we use accuracy for PoS tagging, span-level F1 for chunking, word-level F1 for predicate detection, and span-level F1 for NER. For each setting, we choose one task as the target task and the remaining three tasks are source tasks. We use BERT\footnote{While BERT is no longer the SOTA model, all SOTA models are slight improvements of BERT, so our experiments are done with highly competitive models.} \citep{devlin2019bert} as our basic model in our main experiments. Specifically, we use the pre-trained case-sensitive BERT-base pytorch implementation \citep{wolf2020transformers}, and the common hyperparameters for BERT. In the BERT, the task-specific function is the last-layer linear classifier, and the representation model is the remaining part. 

{\bf Cross-task learning paradigms.} Pre-training first pre-train the representation part on the source data and then fine-tune the whole target model on the target data. Joint training use both source and target data to train the shared representation model and task specific functions for both source and target tasks at the same time. The difference between joint training and normalized joint training lies in the initialization of task weights. For (weighted) joint training and (weighted) pre-training, the weights on tasks are initialized to be $\omega_t = n_t/\sum_{t'=1}^T n_{t'}$ (i.e, the weights on the loss of each example will be uniform), whereas for the (weighted) normalized joint training, the weights on tasks are initialized to be $\omega_t = 1/T$ (i.e., the weight on the loss of each example will be normalized by the sample sizes). Note that the loss for each task is already normalized by the sample size (see Eq. \ref{eq:representation_learning}).

{\bf Settings for weighted training.}
For scalability, in all the experiments, we approximate $g^k_t$ in Eq. \eqref{eq:task_gradient} by $-c \times \textnormal{\texttt{sim}}(\nabla_\phi \hat\calL_0(\phi^{k+1}, f_0^{k+1}), \nabla_\phi \hat\calL_t(\phi^{k+1}, f_t^{k+1}))$, where $\textnormal{\texttt{sim}}(\cdot, \cdot)$ denotes the cosine similarity between two vectors. 
For weighted joint training and weighted normalized joint training,
we choose $c = 1$. For weighted pre-training, we choose the best $c$ among $[1, 10, 30, 100]$, because the cosine similarity between the pre-training tasks and the target task are small in general. In practice, we further simplify the computation of $\nabla_\phi \hat\calL_t(\phi^{k+1}, f_t^{k+1})$ ($t = 0, 1, \hdots, T$) in Eq. \eqref{eq:task_gradient} by computing the gradient over the average loss of a randomly sampled subset of the training set instead of the average loss of the whole training set as in Eq. \eqref{eq:representation_learning}. In our experiments, we simply set the size of the randomly sampled subset of the training set as $64$, though larger size is more beneficial in general. 
In our experiments, we choose $\eta^k = 1.0$ in the mirror descent update \eqref{eq:mirror_descent}. 
It is worthwhile to note that there is no need to tune any extra hyperparameters for weighted joint training and weighted normalized joint training, though 
we believe that the performance of \NAMEALG{} can be further improved by tuning extra hyper parameters, such as the constant $c$ and the learning rate $\eta^k$. 
\iffalse
For (weighted) joint training and (weighted) pre-training, the weights on tasks are initialized to be $\omega_t = n_t/\sum_{t'=1}^T n_{t'}$ (i.e, the weights on the loss of each example will be uniform), 
whereas for the (weighted) normalized joint training, the weights on tasks are initialized to be $\omega_t = 1/T$ 
(i.e., the weight on the loss of each example will be normalized by the sample sizes). Note that the loss for each task is already normalized by the sample size (see Eq. \ref{eq:representation_learning}).
\fi

{\bf Results and analysis.} Table \ref{table:results} demonstrates the effectiveness of \NAMEALG{} for pre-training (with fine-tuning), joint training, and normalized joint training on four different settings, where the target task is PoS tagging, chunking, predicate detection and NER, respectively. 
As a byproduct, we find that normalized joint training is much better than the widely used joint training when the source data is much larger than the target data. 
More experiments 
can be found in Appx. \ref{sec:appx-exp}. 
Furthermore, we analyze two crucial factors (i.e., the ratio between the training sizes of the source and target datasets, and the training size of the target dataset) that affect the improvement of \NAMEALG{} in Fig. \ref{fig:analysis}. 
In general, we find that \NAMEALG{} is more beneficial when the performance of the base mode is poorer, either because of a smaller-sized target data or due to a smaller ratio between the source data size and the target data size. 
Finally, we note that \NAMEALG{} can be easily extended from putting weights on tasks to putting weights on samples (see Appx. \ref{sec:appx-exp} for experiments on the weighted-sample version of \NAMEALG{}).
\section{Discussion}
\label{sec:discuss}

In this paper, we propose a new weighted training algorithm, \NAMEALG{}, to improve the sample efficiency of learning from cross-task signals. 
\NAMEALG{} adaptively assigns weights on tasks or samples in the source data to minimize the representation-based task distance between source and target tasks. 
The algorithm is an easy-to-use plugin that can be applied to existing cross-task learning paradigms, such as pre-training and joint training, without introducing too much computational overhead and hyperparameters tuning. The effectiveness of \NAMEALG{} is further corroborated through theoretical analyses and empirical experiments. 
To the best of our knowledge, \NAMEALG{} is the first weighted algorithm for cross-task learning with theoretical guarantees, and the proposed representation-based task distance also sheds light on many critical aspects of cross-task learning.

\iffalse
We point out several interesting directions for future work. 
First, we plan to investigate the information-theoretic role of the representation-based task distance by proving a distance-aware lower bound. 
Second, we are curious whether we can estimate the representation-based task distance efficiently in practice to provide guidance on selecting relevant source tasks ahead of training.
Finally, we plan to evaluate \NAMEALG{} in other settings, such as cross-domain and cross-lingual settings; in more general cases, such as multiple target tasks in the target data; and in other tasks, such as question answering, textual entailment, image classification, and object detection.
\fi

We conclude this paper with two open questions. First, although we gave an efficient implementation of task-weighted version of \NAMEALG{}, an efficient implementation of sample-weighted version of \NAMEALG{} is still lacking, and we leave it for future work. 
Second, we are not aware of any method that can efficiently estimate the representation-based task distance without training the model, and we plan to work more on this direction.

\iffalse
{\bf More applications}

\begin{itemize}
    \item {\bf \NAMEALG{} can be easily applied to cross-domain and cross-lingual settings.}
    \item {\bf Multiple target tasks.} Experiments on the setting where there are multiple target tasks.
    \item {\bf Other tasks.} Applied to more tasks, such as QA and image classification.
\end{itemize}

{\bf Better understanding:}

\begin{itemize}
    \item {\bf Provide a lower bound with the task distance.} 
   
    \item {\bf How to estimate the task distance efficiently in practice.}
    \item The goodness of representations can be extended to decodable information bottleneck \cite{dubois2020learning} or maximal coding rate reduction \cite{yu2020learning}. Our current formulation only considers sufficiency which provides optimal representations under infinite data limit but cannot provide optimal representations with finite samples; but decodable information bottleneck can provide optimal representations even with finite samples.
\end{itemize}
\fi
\section{Omitted Proofs}
\label{sec:appx-theory}

We start by introducing some notations.
For a set $S$, we let $\Indc_S$ be its indicator function and we use $\# S$ and $|S|$ interchangeably to denote its cardinality. 
For two positive sequences $\{a_n\}$ and $\{b_n\}$, we write 
$a_n \lesssim b_n$ or $a_n = \calO(b_n)$ to denote $\limsup a_n/b_n < \infty$,  
and we let $a_n \gtrsim b_n$ or $a_n = \Omega(b_n)$ to denote $b_n \lesssim a_n$. 
Meanwhile, the notation $a_n\asymp b_n$ or $a_n = \Theta(b_n)$ means $a_n \lesssim b_n$ and $a_n \gtrsim b_n$ simultaneously.
For a vector $\bsx$, we let $\|\bsx\|$ denote its $\ell_2$ norm.
In this section, we treat $L_\ell, L_\calF, C_\Phi, C_\calF$ as absolute constants and we hide the dependence on those parameters in our theoretical results. The exact dependence on those parameters can be easily traced from the proofs.

\subsection{Proof of Theorem \ref{thm:ub_fixed_weights}}\label{prf:thm:ub_fixed_weights}
We start by stating two useful lemmas.

\begin{lemma}[Error for learning the imperfect representation from source data]
\label{lemma:err_learn_encoder}
Under the setup of Theorem \ref{thm:ub_fixed_weights}, 
there exists a constant $C_1 = C_1(L_\ell, L_\calF, C_\Phi, C_\calF)>0$ such that 
for any $\delta\in(0, 1)$, we have
\begin{equation}
	\label{eq:err_learn_encoder}
	\sum_{t=1}^T \omega_t [\calL^\star_t(\hat \phi) - \calL^\star_t(\bar \phi^{\boldsymbol{\omega}})] \leq C_1 \cdot 
	\sqrt{\frac{\nu_\Phi + T\nu_\calF + \log(1/\delta)}{N_{\boldsymbol{\omega}}}}
\end{equation}	
with probability at least $1-\delta$.
\end{lemma}
\begin{proof}
	See Appendix \ref{prf:lemma:err_learn_encoder}.
\end{proof}



\begin{lemma}[Error for learning the task-specific function from target data]
\label{lemma:err_learn_decoder}
Under the setup of Theorem \ref{thm:ub_fixed_weights}, there exists a constant $C_2 = C_2(L_\ell, C_\calF) > 0$ such that for any $\delta\in(0, 1)$, we have
\begin{equation}
	\label{eq:err_learn_decoder}
	\calL_0(\hat\phi, \hat f_0) - \calL_0^\star(\hat \phi) \leq C_2 \cdot \sqrt{\frac{\nu_\calF + \log(1/\delta)}{n_0}}
\end{equation}	
with probability at least $1-\delta$.
\end{lemma}
\begin{proof}
	See Appendix \ref{prf:lemma:err_learn_decoder}.
\end{proof}


To prove Theorem \ref{thm:ub_fixed_weights}, we start by writing
\begin{align*}
	\calL_0(\hat\phi, \hat f_0) - \calL_0(\phi^\star_0, f_0^\star) 
	& = \calL_0(\hat \phi, \hat f_0) - \calL_0^\star(\hat \phi) +   \calL_0^\star(\hat \phi) - \calL_0^\star(\bar \phi^{\boldsymbol{\omega}}) + \calL_0^\star(\bar \phi^{\boldsymbol{\omega}}) - \calL_0^\star(\phi^\star_0).
\end{align*}
Suppose the two high probability events in Lemmas \ref{lemma:err_learn_encoder} and \ref{lemma:err_learn_decoder} hold. Then we can bound $\calL_0(\hat\phi, \hat f_0) - \calL_0^\star(\hat \phi)$ by \eqref{eq:err_learn_decoder}. Meanwhile, since $\hat\phi$ is in a $C\sqrt{(\nu_\Phi + T\nu_\calF + \log \delta^{-1})/N_{\boldsymbol{\omega}}}$-neighborhood of $\bar\Phi^{\boldsymbol{\omega}}$, 
we can invoke the transferability assumption to get
$$
	\calL_0^\star(\hat\phi) - \calL_0^\star(\bar \phi^{\boldsymbol{\omega}}) \leq C_\rho \bigg(\sum_{t=1}^T \omega_t [\calL^\star_t(\phi) - \calL^\star_t(\bar \phi^{\boldsymbol{\omega}})]\bigg)^{1/\rho} \leq C_\rho C_1^{1/\rho} \cdot \bigg(\frac{\nu_\Phi + T \nu_\calF + \log(1/\delta)}{N_{\boldsymbol{\omega}}}\bigg)^{1/2\rho}.
$$
Moreover, we have the trivial bound that $\calL_0^\star(\bar \phi^{\boldsymbol{\omega}}) - \calL_0^\star(\phi^\star_0) \leq \sup_{\bar \phi^{\boldsymbol{\omega}}} \calL_0^\star(\bar \phi^{\boldsymbol{\omega}}) - \calL_0^\star(\phi^\star_0)$.
Assembling the three bounds above gives the desired result.


\subsubsection{Proof of Lemma \ref{lemma:err_learn_encoder}}\label{prf:lemma:err_learn_encoder}
We start by writing
\begin{align*}
	& \sum_{t=1}^T \omega_t[ \calL_t^\star(\hat \phi) - \calL_t^\star(\bar\phi^{\boldsymbol{\omega}})] \\
	& \leq \sum_{t=1}^T \omega_t[\calL_0(\hat \phi, \hat f_t) - \calL_t(\bar\phi^{\boldsymbol{\omega}}, \bar f_t^{\boldsymbol{\omega}})] \\
	& = \sum_{t=1}^T \omega_t \bigg( \calL_t(\hat\phi, \hat f_t) - \hat\calL_t(\hat \phi, \hat f_t) + \hat\calL_t(\hat \phi, \hat f_t) - \hat \calL_t(\bar \phi^{\boldsymbol{\omega}}, \bar f_t^{\boldsymbol{\omega}}) + \hat \calL_t(\bar \phi^{\boldsymbol{\omega}}, \bar f_t^{\boldsymbol{\omega}}) - \calL_t(\bar \phi^{\boldsymbol{\omega}}, \bar f_t^{\boldsymbol{\omega}}) \bigg)\\
	& \leq \sum_{t=1}^T \omega_t \bigg(\calL_t(\hat\phi, \hat f_t) - \hat\calL_t(\hat \phi, \hat f_t)  + \hat \calL_t(\bar \phi^{\boldsymbol{\omega}}, \bar f_t^{\boldsymbol{\omega}}) - \calL_t(\bar \phi^{\boldsymbol{\omega}}, \bar f_t^{\boldsymbol{\omega}}) \bigg) \\
	& \leq \sup_{\phi\in\Phi, \{f_t\}\subset \calF} \omega_t \bigg( \calL_t(\phi, f_t) - \hat\calL_t(\phi, f_t)  + \hat \calL_t(\bar \phi^{\boldsymbol{\omega}}, \bar f_t^{\boldsymbol{\omega}}) - \calL_t(\bar \phi^{\boldsymbol{\omega}}, \bar f_t^{\boldsymbol{\omega}}) \bigg) \\
	& = \sup_{\phi\in\Phi, \{f_t\}\subset \calF} \sum_{t=1}^T \omega_t \cdot \frac{1}{n_t} \sum_{i=1}^{n_t} \bigg( \calL_t(\phi, f_t) - \ell(f_0\circ \phi(\bsx_{ti}), y_{ti})  + \ell(\bar f_t^{\boldsymbol{\omega}} \circ \bar \phi^{\boldsymbol{\omega}}(\bsx_{ti}), y_{ti}) - \calL_t(\bar \phi^{\boldsymbol{\omega}}, \bar f_t^{\boldsymbol{\omega}})\bigg),
\end{align*}
where the first inequality is by $\calL_t^\star(\cdot) = \min_{f_t\in\calF} \calL_t(\cdot, f_t)$ and the second inequality is by the fact that $(\hat\phi, \{\hat f_t\}_{t=1}^T)$ is a minimizer of \eqref{eq:representation_learning}.
To simplify notations, let $\bsz_{ti} = (\bsx_{ti}, y_{ti})$ and let the right-hand side above be $G(\{\bsz_{ti}\})$.

Fix two indices $1\leq t'\leq T$, $1\leq i_{t'}\leq n_t$, and let $\{\tilde \bsz_{ti}\}$ be the source datasets formed by replacing $\bsz_{t', i_{t'}}$ with some $\tilde \bsz_{t', i_{t'}} = (\tilde \bsx_{t', i_{t'}}, \tilde y_{t', i_{t'}}) \in \calX\times \calY$. Since $\{\bsz_{ti}\}$ and $\{\tilde\bsz_{ti}\}$ differ by only one example, we have
\begin{align*}
	& \sum_{t\neq t'} \sum_{i=1}^{n_t} \frac{\omega_t}{n_t} \bigg( \calL_t(\phi, f_t) - \ell(f_t\circ\phi(\bsx_{ti}), y_{ti}) + \ell(\bar f_t^{\boldsymbol{\omega}} \circ \phi^{\boldsymbol{\omega}}(\bsx_{ti}), y_{ti}) + \calL_t(\bar\phi^{\boldsymbol{\omega}}, \bar f_t^{\boldsymbol{\omega}}) \bigg) \\
	& \qquad + \sum_{i\neq i_{t'}} \frac{\omega_{t'}}{n_{t'}} \bigg( \calL_{t'}(\phi, f_{t'}) - \ell(f_{t'}\circ\phi(\bsx_{t', i}), y_{t', i}) + \ell(\bar f_{t'}^{\boldsymbol{\omega}} \circ \phi^{\boldsymbol{\omega}}(\bsx_{t', i}), y_{t', i}) + \calL_{t'}(\bar\phi^{\boldsymbol{\omega}}, \bar f_{t'}^{\boldsymbol{\omega}}) \bigg)\\
	& \qquad + \frac{\omega_{t'}}{n_{t'}} \bigg( \calL_{t'}(\phi, f_{t'}) - \ell(f_{t'}\circ\phi(\bsx_{t', i_{t'}}), y_{t', i_{t'}}) + \ell(\bar f_{t'}^{\boldsymbol{\omega}} \circ \phi^{\boldsymbol{\omega}}(\bsx_{t', i_{t'}}), y_{t', i_{t'}}) + \calL_{t'}(\bar\phi^{\boldsymbol{\omega}}, \bar f_{t'}^{\boldsymbol{\omega}}) \bigg) \\
	& \qquad - G(\{\tilde \bsz_{t i}\}) \\
	& \leq \frac{\omega_{t'}}{n_{t'}} \bigg[ \bigg( \calL_{t'}(\phi, f_{t'}) - \ell(f_{t'}\circ \phi(\bsx_{t', i_{i'}}), y_{t', i_{t'}})\bigg) - \bigg( \calL_{t'}(\bar \phi^{\boldsymbol{\omega}}, \bar f_{t'}^{\boldsymbol{\omega}}) - \ell(\bar f_{t'}^{\boldsymbol{\omega}}\circ \bar \phi^{\boldsymbol{\omega}}(\bsx_{t', i_{t'}}), y_{t', i_{t'}}) \bigg) \\
	& \qquad\qquad + \bigg( \calL_{t'}(\phi, f_{t'}) - \ell(f_{t'}\circ \phi(\tilde\bsx_{t', i_{i'}}), \tilde y_{t', i_{t'}})\bigg) - \bigg( \calL_{t'}(\bar \phi^{\boldsymbol{\omega}}, \bar f_{t'}^{\boldsymbol{\omega}}) - \ell(\bar f_{t'}^{\boldsymbol{\omega}}\circ \bar \phi^{\boldsymbol{\omega}}(\tilde\bsx_{t', i_{t'}}), \tilde y_{t', i_{t'}}) \bigg)\bigg] \\
	\label{eq:err_learn_encoder_finite_diff}
	& \leq \frac{4 \omega_{t'}}{n_{t'}}, \numberthis
\end{align*}
where the last inequality is by the fact that the loss function is bounded in $[0, 1]$. Taking the supremum over $\phi\in\Phi, \{f_t\}\subset \calF$ at both sides, we get $G(\{\bsz_{ti}\}) - G(\{\tilde \bsz_{ti}\}) \leq 4\omega_{t'}/n_{t'}$. A symmetric argument shows that the reverse inequality, namely $G(\{\tilde \bsz_{ti}\}) - G(\{\bsz_{ti}\}) \leq 4\omega_{t'}/n_{t'}$, is also true. That is, we have shown
$$
	|G(\{\bsz_{ti}\}) - G(\{\tilde \bsz_{ti}\})| \leq \frac{4\omega_{t'}}{n_{t'}}.
$$
This means that we can invoke McDiarmid's inequality to get
$$
	\bbP\bigg( G(\{\bsz_{ti}\}) - \bbE [G(\{\bsz_{ti}\})] \geq \ep\bigg) \leq  \exp\bigg\{\frac{-2\ep^2}{\sum_{t=1}^T \sum_{i=1}^{n_t} 16\omega_t^2/n_t^2}\bigg\}
$$
for any $\ep>0$, or equivalently
\begin{equation}
	\label{eq:err_learn_encoder_mcdiarmid}
	G(\{\bsz_{ti}\}) \leq \bbE[G(\{\bsz_{ti}\})] + 2\sqrt{2} \cdot \sqrt{\frac{\log(1/\delta)}{N_{\boldsymbol{\omega}}}}
\end{equation}	
with probability at least $1-\delta$ for any $\delta\in(0, 1)$. To bound the expectation term, we use a standard symmetrization argument (see, e.g., Lemma 11.4 in \cite{boucheron2013concentration}) to get
$$
	\sqrt{N_{\boldsymbol{\omega}}} \bbE[G(\{\bsz_{ti}\})] \leq 2\sqrt{N_{{\boldsymbol{\omega}}}} \bbE \bigg[\sup_{\phi\in\Phi, \{f_t\}\subset \calF} \sum_{t=1}^T \sum_{i=1}^{n_t} \ep_{ti} \cdot \frac{\omega_t}{n_t} \bigg(-\ell(f_t\circ \phi(\bsx_{ti}), y_{ti}) + \ell(\bar f_t\circ \bar \phi(\bsx_{ti}), y_{ti})\bigg) \bigg],
$$
where the expectation is taken over the randomness in both the source datasets $\{\bsz_{ti}\}$ and the i.i.d.~ symmetric Rademacher random variables $\{\ep_{ti}\}$. Consider the function space $\mathscr{G} : = \{(\phi, \{f_t\}_{t=1}^T): \phi\in \Phi, \{f_t\}\subset \calF\}$. Let
$$
	M_g := \sqrt{N_{\boldsymbol{\omega}}} \cdot \sum_{t=1}^T \sum_{i=1}^{n_t} \ep_{ti} \cdot \frac{\omega_t}{n_t} \cdot [-\ell(f_t\circ \phi(\bsx_{ti}), y_{ti})], \qquad g = (\phi, \{f_t\}_{t=1}^T) \in \mathscr{G}
$$
be the empirical process indexed by the function space $\mathscr{G}$. Conditional on the randomness in the data $\{\bsz_{ti}\}$, this is a Rademacher process with sub-Gaussian increments:
$$
	\log \bbE e^{\lambda(M_g - M_{\tilde g})} \leq \frac{\lambda^2}{2} \sfd^2(g, \tilde g), \qquad \forall \lambda \geq 0, g = (\phi, \{f_t\}_{t=1}^T), \tilde g = (\tilde \phi, \{\tilde f_t\}_{t=1}^T) \in \mathscr{G},
$$
where the pseudometric
$$
	\sfd^2(g, \tilde g) := N_{\boldsymbol{\omega}} \cdot \sum_{t=1}^T\sum_{i=1}^{n_t} \frac{\omega_t^2}{n_t^2} \bigg( \ell(f_t\circ\phi(\bsx_{ti}), y_{ti}) - \ell(\tilde f_t \circ \tilde \phi(\bsx_{ti}), y_{ti}) \bigg)^2 \leq N_{\boldsymbol{\omega}} \cdot \sum_{t=1}^T \frac{\omega_t^2}{n_t} =1. 
$$
Thus, we can invoke Dudley's entropy integral inequality (see, e.g., Corollary 13.2 in \cite{boucheron2013concentration}) to get
$$
	\bbE[\sup_{g\in\mathscr{G}}M_g - M_{\bar g}~|~\{\bsz_{ti}\}] \lesssim \int_0^1 \sqrt{\log\calN(\mathscr{G}; \sfd; \ep)} d\ep, 
$$
where $\bar g = (\bar\phi^{\boldsymbol{\omega}}, \{\bar f_t^{\boldsymbol{\omega}}\})$, and $\calN(\mathscr{G}; \sfd; \ep)$ is the $\ep$-covering number of $\mathscr{G}$ with respect to the pseudometric $\sfd$. Taking expectation over the randomness in $\{\bsz_{ti}\}$, we get
\begin{equation}
	\label{eq:err_learn_decoder_dudley}
	\bbE[G(\{\bsz_{ti}\})] \lesssim N_{{\boldsymbol{\omega}}}^{-1/2} \cdot \int_0^1 \sqrt{\log \calN(\mathscr{G}; \sfd; \ep)} d\ep.
\end{equation}	
We now bound the covering number of $\mathscr{G}$. To do so, we define
$$
	\bbQ:= \sum_{t=1}^T N_{\boldsymbol{\omega}} \cdot \frac{\omega_t^2}{n_t} \cdot \sum_{i=1}^{n_t} \frac{\delta_{\bsx_{ti}}}{n_t}, \qquad \bbQ_t := \frac{1}{n_t} \sum_{i=1}^{n_t}  \delta_{\bsx_{ti}},
$$
where $\delta_{\bsx_{ti}}$ is a point mass at $\bsx_{ti}$.
Let $\{\phi^{(1)}, \hdots, \phi^{(N_\ep)}\}\subset \Phi$ be an $\ep$-covering of $\Phi$ with respect to $L^2(\bbQ)$, where $N_\ep = \calN(\Phi; L^2(\bbQ); \ep)$. This means that for any $\phi \in \Phi$, there exists $j\in \{1, \hdots, N_\ep\}$ such that
$$
	\|\phi - \phi^{(j)}\|_{L^2(\bbQ)}^2 := \sum_{t=1}^T\sum_{i=1}^n N_{\boldsymbol{\omega}} \cdot \frac{\omega_t^2}{n_t^2} \|\phi(\bsx_{ti}) - \phi^{(j)}(\bsx_{ti})\|^2 \leq \ep^2.
$$
Now for each $j\in\{1, \hdots, N_\ep\}$ and $t\in\{1, \hdots, T\}$, let $\{f_t^{(j, 1)}, \hdots, f_t^{(j, N^{(j)}_\ep)}\}$ be an $\ep$-covering of $\calF$ with respect to $L^2(\phi^{(j)}\# \bbQ_t)$, where $\phi^{(j)}\# \bbQ_t$ is the pushforward of $\bbQ_t$ by $\phi^{(j)}$, and $N^{(j)}_\ep = \calN(\calF; L^2(\phi^{(j)}\# \bbQ_t); \ep)$ has no dependence on $t$ due to the uniform entropy control from Assumption \ref{assump:unif_entropy}. This means that for any $f_t\in\calF, j\in\{1, \hdots, N_\ep\}$, there exists $k\in\{1, \hdots, N^{(j)}_\ep\}$ such that
$$
	\|f_t - f_t^{(j, k)}\|_{L^2(\phi^{(j)}\# \bbQ_t)}^2 := \frac{1}{n_t} \sum_{i=1}^{n_t} \bigg(f_t \circ \phi^{(j)}(\bsx_{ti}) - f_t^{(j, k)} \circ \phi^{(j)} (\bsx_{ti})\bigg)^2 \leq \ep^2.
$$
Now, let us fix $(\phi, \{f_t\}_{t=1}^T) \in \mathscr{G}$. By construction, we can find $j\in\{1, \hdots, N_\ep\}$ and $k_t \in \{1, \hdots, N^{(j)}_\ep\}$ for any $1\leq t\leq T$ such that 
\begin{equation}
	\label{eq:err_learn_decoder_covering}
	\|\phi - \phi^{(j)}\|_{L^2(\bbQ)} \leq \ep, \qquad \|f_t - f_t^{(j, k_t)}\|_{L^2(\phi^{(j)}\# \bbQ_t)} \leq \ep, ~~ \forall 1\leq t\leq T.
\end{equation}	
Thus, we have
\begin{align*}
	& \sfd^2\bigg((\phi,\{f_t\}_{t=1}^T), (\phi^{(j)}, \{f_t^{(j, k_t)}\}_{t=1}^T)\bigg) \\
	& = N_{\boldsymbol{\omega}} \cdot \sum_{t=1}^{T} \sum_{i=1}^{n_t} \frac{\omega_t^2}{n_t^2} \bigg(\ell(f_t\circ\phi(\bsx_{ti}), y_{ti}) - \ell(f_t^{(j, k_t)} \circ \phi^{(j)}(\bsx_{ti}), y_{ti})\bigg)^2\\
	& \leq L_\ell^2 N_{\boldsymbol{\omega}} \cdot \sum_{t=1}^T \sum_{i=1}^{n_t} \frac{\omega_t^2}{n_t^2}  \bigg(f_t\circ \phi(\bsx_{ti}) - f_t^{(j, k_t)} \circ \phi^{(j)}(\bsx_{ti})\bigg)^2\\
	& = L_\ell^2 N_{\boldsymbol{\omega}} \cdot \sum_{t=1}^T \sum_{i=1}^{n_t} \frac{\omega_t^2}{n_t^2}  \bigg(f_t\circ \phi(\bsx_{ti}) - f_t\circ \phi^{(j)}(\bsx_{ti}) + f_t\circ \phi^{(j)}(\bsx_{ti}) - f_t^{(j, k_t)} \circ \phi^{(j)}(\bsx_{ti})\bigg)^2\\
	& \leq 2L_\ell^2 N_{\boldsymbol{\omega}} \sum_{t=1}^{T} \sum_{i=1}^{n_t} \frac{\omega_t^2}{n_t^2} \cdot L_\calF^2 \|\phi(\bsx_{ti}) - \phi^{(j)}(\bsx_{ti})\|^2 + 2 L_\ell^2 N_{\boldsymbol{\omega}} \sum_{t=1}^T \frac{\omega_t^2}{n_t} \cdot \frac{1}{n_t} \sum_{i=1}^{n_t} \bigg(  f_t\circ \phi^{(j)}(\bsx_{ti}) - f_t^{(j, k_t)} \circ \phi^{(j)}(\bsx_{ti})\bigg)^2 \\
	& = 2L_\ell^2 L_\calF^2  \|\phi - \phi^{(j)}\|_{L^2(\bbQ)}^2 + 2 L_\ell^2 N_{\boldsymbol{\omega}} \sum_{t=1}^T \frac{\omega_t^2}{n_t} \cdot \|f_t - f_t^{(j, k_t)}\|_{L^2(\phi^{(j)}\# \bbQ_{t})}^2\\
	& \leq 2L_\ell^2 (L_\calF^2 + 1) \ep^2.
\end{align*}
This yields 
\begin{align*}
	\calN(\mathscr{G}; \sfd; \sqrt{2}L_\ell\sqrt{L_\calF^2+1} \cdot \ep) 
	& \leq \bigg| \bigg\{ (\phi^{(j)}, \{f_t^{(j, k_t)}\}_{t=1}^T): 1\leq j\leq N_\ep, 1\leq k_t \leq N_\ep^{(j)}, \forall 1\leq t\leq T\bigg\}\bigg| \\
	& = N_\ep \cdot (N_\ep^{(j)})^T \\
	& \leq \bigg(\frac{C_\Phi}{\ep}\bigg)^{\nu_\Phi} \cdot \bigg(\frac{C_\calF}{\ep}\bigg)^{T\nu_\calF},
\end{align*}
from which we get
\begin{align*}
	\log \calN(\mathscr{G}; \sfd; \ep) & \leq \nu_\Phi \log(C_\Phi L_\ell \sqrt{2(L_\calF^2 + 1)}) + T \nu_\calF \log(C_\calF L_\ell \sqrt{2(L_\calF^2 + 1)}) + (\nu_\Phi + T \nu_\calF) \log(1/\ep) \\ 
	& \lesssim (\nu_\Phi + T \nu_\calF) (1 + \log(1/\ep)).
\end{align*}
Plugging the above inequality to \eqref{eq:err_learn_decoder_dudley}, we get
$$
	\bbE[G(\{\bsz_{ti}\})] \lesssim N_{\boldsymbol{\omega}}^{-1/2} \cdot \sqrt{\nu_\Phi + T\nu_\calF} \cdot \bigg( 1 + \int_0^1 \sqrt{\log(1/\ep)} d\ep\bigg) \lesssim \sqrt{\frac{\nu_\Phi + T \nu_\calF}{N_{\boldsymbol{\omega}}}}.
$$
The proof is concluded by plugging the above inequality to \eqref{eq:err_learn_encoder_mcdiarmid}.

\subsubsection{Proof of Lemma \ref{lemma:err_learn_decoder}}\label{prf:lemma:err_learn_decoder}
Since $\hat\phi$ is obtained from the source datasets $\{S_t\}_{t=1}^T$, it is independent of the target data $S_0$. Throughout the proof, we condition on the randomness in the source datasets, thus effectively treating $\hat \phi$ as fixed.
Let $f_{0, \hat \phi} \in \argmin_{f_0\in\calF} \calL_0(\hat \phi, f)$. We start by writing
\begin{align*}
	\calL_0(\hat \phi, \hat f_0) - \calL_0^\star(\hat \phi) 
	& = \calL_0(\hat \phi, \hat f_0) - \hat \calL_0(\hat \phi, \hat f_0) + \hat \calL_0(\hat\phi, \hat f_0) - \hat \calL_0(\hat \phi, f_{0, \hat \phi}) + \hat \calL_0(\hat \phi, f_{0, \hat \phi}) - \calL_0(\hat \phi, f_{0, \hat \phi})\\
	& \leq \calL_0(\hat \phi, \hat f_0) - \hat \calL_0(\hat \phi, \hat f_0) + \hat \calL_0(\hat \phi, f_{0, \hat \phi}) - \calL_0(\hat \phi, f_{0, \hat \phi}) \\
	& \leq \sup_{f_0\in \calF} \calL_0(\hat \phi, f_0) - \hat \calL(\hat \phi, f_0) +  \hat \calL_0(\hat \phi, f_{0, \hat \phi}) - \calL_0(\hat \phi, f_{0, \hat \phi}).
\end{align*}
The right-hand side above is an empirical process indexed by $f_0\in\calF$. Using similar arguments as those appeared in the proof of Lemma \ref{lemma:err_learn_encoder}, we have
$$
	\sup_{f_0\in \calF} \calL_0(\hat \phi, f_0) - \hat \calL(\hat \phi, f_0) +  \hat \calL_0(\hat \phi, f_{0, \hat \phi}) - \calL_0(\hat \phi, f_{0, \hat \phi}) \lesssim \sqrt{\frac{\nu_\calF + \log(1/\delta)}{n_0}}
$$
with probability at least $1-\delta$, which is exactly the desired result.





\subsection{A Sufficient Condition for Exactly Matching  \texorpdfstring{$\bar\phi^{\boldsymbol{\omega}} = \phi_0^\star$}{}}\label{appx:exact_match}
\begin{proposition}[Weighting and task distance minimization]
	\label{prop:weighting_and_task_distance}
	Suppose that for every $\phi\in\Phi$, there exists two source tasks $1\leq t_1, t_2\leq T$ such that $\calL_{t_1}^\star(\phi) \leq \calL_0^\star(\phi) \leq \calL_{t_2}^\star(\phi)$.
	Then there exists a choice of weights ${\boldsymbol{\omega}}$, possibly depending on $\phi$, such that
	$
	\mathtt{dist}(\sum_{t=1}^T \omega_t\calD_t , \calD_0) = 0.
	$

\end{proposition}
\begin{proof}
By construction, it suffices to show the existence of some ${\boldsymbol{\omega}}$ such that 
\begin{equation}
	\label{eq:weighting_and_task_distance_sufficient_condition}
	\sum_{t=1}^T \omega_t \calL_t^\star(\phi) = \calL_0^\star(\phi), \qquad \forall \phi\in\Phi.
\end{equation}	
By assumption, fix any $\phi\in\Phi$, we can find $1\leq t_1, t_2\leq T$ such that $\calL_{t_1}^\star(\phi) \leq \calL_0^\star(\phi) \leq \calL_{t_2}^\star(\phi)$. We set $\omega_t = 0$ for any $t\notin \{t_1, t_2\}$. If $\calL_{t_1}^\star(\phi) = \calL_0^\star(\phi) = \calL_{t_2}^\star(\phi)$, then any choice of $\omega_{t_1}, \omega_{t_2}$ will suffice. Otherwise, we let
$$
	\omega_{t_1} = \frac{\calL_{t_2}^\star(\phi) - \calL_0^{\star}(\phi)}{\calL_{t_2}^\star(\phi) -\calL_{t_1}^\star(\phi)}, 
	\qquad \omega_{t_2} = \frac{\calL_{0}^\star(\phi) - \calL_{t_1}^{\star}(\phi)}{\calL_{t_2}^\star(\phi) -\calL_{t_1}^\star(\phi)}.
$$
It is straightforward to check that such a choice of ${\boldsymbol{\omega}}$ indeed ensures \eqref{eq:weighting_and_task_distance_sufficient_condition}. The proof is concluded.
\end{proof}



\subsection{Proof of Theorem \ref{thm:ub_learned_weights}}
The proof bears similarities to the proof of Theorem \ref{thm:ub_fixed_weights}, with additional complications in ensuring a uniform control over the learned weights.
Let $f_{0, \hat \phi} \in \argmin_{f_0\in\calF} \calL_0(\hat \phi, f_0)$.
Note that
\begin{align*}
	& \calL_0(\hat \phi, \hat f_0) - \calL_0(\phi^\star_0 , f_0^\star)  \\
	& = \calL_0(\hat \phi, \hat f_0) - \hat\calL_0^{(2)} (\hat \phi, \hat f_0) 
	+   \hat\calL_0^{(2)} (\hat \phi, \hat f_0) -  \hat\calL_0^{(2)} (\hat \phi, f_{0, \hat \phi})  \\
	& \qquad +  \hat\calL_0^{(2)} (\hat \phi, f_{0, \hat \phi}) -  \calL_0 (\hat \phi, f_{0, \hat \phi}) +  \calL_0^\star (\hat \phi) - \calL_0^\star(\bar\phi^{\hat{\boldsymbol{\omega}}}) +  \calL_0^\star(\bar\phi^{\hat{\boldsymbol{\omega}}}) - \calL_0^\star(\phi^\star_0) \\
	\label{eq:ub_learned_weights_decomposition}
	& \leq \calL_0(\hat \phi, \hat f_0) - \hat\calL_0^{(2)} (\hat \phi, \hat f_0) + \hat\calL_0^{(2)} (\hat \phi, f_{0, \hat \phi}) -  \calL_0 (\hat \phi, f_{0, \hat \phi}) +  \calL_0^\star (\hat \phi) - \calL_0^\star(\bar\phi^{\hat{\boldsymbol{\omega}}}) +  \calL_0^\star(\bar\phi^{\hat{\boldsymbol{\omega}}}) - \calL_0^\star(\phi^\star_0). \numberthis
\end{align*}
Let $\hat f_t \in \argmin_{f_t\in\calF} \hat\calL_t(\hat\phi, f_t)$.
We then have
\begin{align*}
	& \sum_{t=1}^T \hat \omega_t[\calL_t^\star(\hat \phi) - \calL_t^\star(\bar \phi^{\hat{\boldsymbol{\omega}}})] \\
	& \leq \sum_{t=1}^T \hat\omega_t [\calL_t(\hat\phi, \hat f_t) - \calL_t(\bar \phi^{\hat{\boldsymbol{\omega}}}, \bar f_t^{\hat {\boldsymbol{\omega}}})]\\
	& = \sum_{t=1}^T \hat\omega_t \bigg( \calL_t(\hat \phi, \hat f_t) - \hat \calL_t(\hat\phi, \hat f_t)  +  \hat \calL_t(\hat\phi, \hat f_t) - \hat \calL_t(\bar \phi^{\hat {\boldsymbol{\omega}}}, \bar f_t^{\hat {\boldsymbol{\omega}}})+ \hat \calL_t(\bar \phi^{\hat {\boldsymbol{\omega}}}, \bar f_t^{\hat {\boldsymbol{\omega}}}) - \calL_t(\bar\phi^{\hat {\boldsymbol{\omega}}}, \bar f_t^{\hat {\boldsymbol{\omega}}})\bigg)\\
	& \leq \sum_{t=1}^T \hat\omega_t \bigg( \calL_t(\hat \phi, \hat f_t) - \hat \calL_t(\hat\phi, \hat f_t)  + \hat \calL_t(\bar \phi^{\hat {\boldsymbol{\omega}}}, \bar f_t^{\hat {\boldsymbol{\omega}}}) - \calL_t(\bar\phi^{\hat {\boldsymbol{\omega}}}, \bar f_t^{\hat {\boldsymbol{\omega}}})\bigg) \\
	& \leq 2 \sup_{\phi\in\Phi, \{f_t\}\subset \calF, {\boldsymbol{\omega}} \in \calW_\beta} \sum_{t=1}^T \omega_t \bigg( \calL_t(\phi, f_t) - \hat \calL_t(\phi, f_t)  + \hat \calL_t(\bar \phi^{ {\boldsymbol{\omega}}}, \bar f_t^{{\boldsymbol{\omega}}}) - \calL_t(\bar\phi^{ {\boldsymbol{\omega}}}, \bar f_t^{{\boldsymbol{\omega}}})\bigg) .
\end{align*}
Let $\bsz_{ti} = (\bsx_{ti}, y_{ti})$, and let $\{\tilde \bsz_{ti}\}$ be the source datasets formed by replacing $\bsz_{t', i_{t'}}$ with $\tilde \bsz_{t', i_{t'}}$.
Let 
$$
G(\{\bsz_{ti}\}):= \sup_{\phi\in\Phi, \{f_t\}\subset \calF, {\boldsymbol{\omega}} \in \calW_\beta} \sum_{t=1}^T \omega_t \bigg( \calL_t(\phi, f_t) - \hat \calL_t(\phi, f_t)  + \hat \calL_t(\bar \phi^{ {\boldsymbol{\omega}}}, \bar f_t^{{\boldsymbol{\omega}}}) - \calL_t(\bar\phi^{ {\boldsymbol{\omega}}}, \bar f_t^{{\boldsymbol{\omega}}})\bigg).
$$
Then conducting a similar calculation to what led to \eqref{eq:err_learn_encoder_finite_diff}, we get
$$
	|G(\{\bsz_{ti}\}) - G(\{\tilde \bsz_{ti}\})| \leq \frac{4\omega_{t'}}{n_{t'}} \lesssim \frac{\beta}{nT},
$$
where the last inequality is by the fact that ${\boldsymbol{\omega}} \in \calW_\beta$ implies $\omega_t\leq \beta / T$ for any $1\leq t\leq T$. 
Now, invoking McDiarmid's inequality, we get
\begin{equation}
	\label{eq:err_learn_decoder_sample_split_mcdiarmid}
	G(\{\bsz_{ti}\}) \leq \bbE G(\{\bsz_{ti}\}) + \calO\bigg(\beta \sqrt{\frac{\log(1/\delta)}{nT}}\bigg)
\end{equation}	
with probability at least $1-\delta$. Now, a standard symmetrization argument plus an application of Dudley's entropy integral bound (similar to what led to \eqref{eq:err_learn_decoder_dudley}) gives
\begin{equation}
	\label{eq:err_learn_decoder_sample_split_dudley}
	\bbE[G(\{\bsz_{ti}\})] \lesssim (nT/\beta^2)^{-1/2} \cdot \int_0^1\sqrt{\log \calN(\mathscr{G}; \sfd; \ep)} d\ep,
\end{equation}	
where now $\mathscr{G}:= \{(\phi, \{f_t\}_{t=1}^T, {\boldsymbol{\omega}}): \phi\in\Phi, \{f_t\}\subset \calF, {\boldsymbol{\omega}} \in \calW_\beta\}$, and 
\begin{align*}
	& \sfd^2\bigg((\phi, \{f_t\}_{t=1}^T, {\boldsymbol{\omega}}),(\tilde \phi, \{\tilde f_t\}_{t=1}^T, \tilde{\boldsymbol{\omega}}) \bigg)  \\
	& \asymp \frac{nT}{\beta^2} \sum_{t=1}^T \sum_{i=1}^{n_t} \frac{1}{n_t^2} \bigg(\omega_t\ell(f_t\circ\phi(\bsx_{ti}), y_{ti}) - \tilde\omega_t \ell(\tilde f_t\circ\tilde\phi(\bsx_{ti}), y_{ti})    \bigg)^2\\
	& = \frac{nT}{\beta^2} \sum_{t=1}^T \sum_{i=1}^{n_t} \frac{\omega_t^2}{n_t^2} \bigg( \ell(f_t\circ\phi(\bsx_{ti}), y_{ti}) - \ell(\tilde f_t\circ\tilde\phi(\bsx_{ti}) \bigg)^2 +  \frac{nT}{\beta^2} \sum_{t=1}^T \sum_{i=1}^{n_t} \frac{1}{n_t^2} (\omega_t - \tilde\omega_t)^2 [\ell(\tilde f_t \circ\tilde \phi(\bsx_{ti}), y_{ti})]^2 \\
	& \lesssim \frac{1}{nT} \sum_{t=1}^T \sum_{i=1}^{n_t}  \bigg( \ell(f_t\circ\phi(\bsx_{ti}), y_{ti}) - \ell(\tilde f_t\circ\tilde\phi(\bsx_{ti}) \bigg)^2 + T^2 \|{\boldsymbol{\omega}}-\tilde {\boldsymbol{\omega}}\|^2 ,

\end{align*}	
where the last inequality is by $n_t \asymp n, \omega_t\leq \beta/T$ for any $1\leq t\leq T$ and $\beta \geq 1$.
This means that we can construct a $C \ep$-covering of $\mathscr{G}$ by the following two steps (where $C$ is an absolute constant only depending on $L_\ell$ and $L_\calF$): (1) cover the space $\{(\phi, \{f_t\}_{t=1}^T)\}$ by the same construction as \eqref{eq:err_learn_decoder_covering}; (2) construct an $\ep/{T}$-covering of $\calW_\beta$ with at most $(c{T}/\ep)^T$ many points, where $c$ is an absolute constant. Overall, we can construct a $C\ep$ covering $\mathscr{G}$ with
$
	(C_\Phi/\ep)^{\nu_\Phi} \cdot (C_\calF/\ep)^{T\nu_\calF} \cdot (c{T}/\ep)^{T}
$
many points. Hence, we have
\begin{align*}
	\log\calN(\mathscr{G}; \sfd; \ep) & \lesssim (\nu_\Phi + T\nu_\calF) (\log(1/\ep)+ 1) + T (1+ \log T + \log(1/\ep))  \\
	& \lesssim  (\nu_\Phi + T \nu_\calF) (\log(1/\ep) + 1) + T\log T,
\end{align*}	
where the last inequality is by $\nu_\calF \geq 1$. 
Plugging this inequality back to \eqref{eq:err_learn_decoder_sample_split_mcdiarmid} and \eqref{eq:err_learn_decoder_sample_split_dudley}, we get
\begin{align*}
	\sum_{t=1}^T \hat \omega_t[\calL_t^\star(\hat \phi) - \calL_t^\star(\bar \phi^{\hat{\boldsymbol{\omega}}})] 

	& \lesssim  \beta \sqrt{\frac{\nu_\Phi + \log(1/\delta)}{nT} + \frac{\nu_\calF + \log T}{n}}.
\end{align*}	
with probability at least $1-\delta$.
This means that under this high probability event, we can invoke the transferability assumption to conclude the existence of a specific $\bar \phi^{\hat{\boldsymbol{\omega}}}$ with
$$
	 \calL_0^\star (\hat \phi) - \calL_0^\star(\bar\phi^{\hat{\boldsymbol{\omega}}})  \lesssim C_\rho \beta^{1/\rho} \cdot  \bigg(\frac{\nu_\Phi + \log(1/\delta)}{nT} + \frac{\nu_\calF + \log T}{n}\bigg)^{1/2\rho}.
$$
Recalling \eqref{eq:ub_learned_weights_decomposition}, we arrive at
\begin{align*}
	& \calL_0(\hat \phi, \hat f_0) - \calL_0(\phi^\star_0 , f_0^\star)  \\
	& \leq \calL_0(\hat \phi, \hat f_0) - \hat\calL_0^{(2)} (\hat \phi, \hat f_0) + \hat\calL_0^{(2)} (\hat \phi, f_{0, \hat \phi}) -  \calL_0 (\hat \phi, f_{0, \hat \phi}) +   \sup_{\bar \phi^{\hat{\boldsymbol{\omega}}}}\calL_0^\star(\bar\phi^{\hat{\boldsymbol{\omega}}}) - \calL_0^\star(\phi^\star_0) \\
	& \qquad +  \calO\bigg(C_\rho \beta^{1/\rho} \cdot  \bigg(\frac{\nu_\Phi + \log(1/\delta)}{nT} + \frac{\nu_\calF + \log T}{n}\bigg)^{1/2\rho}\bigg) \\
	& \leq \sup_{f_0\in\calF} \bigg\{ \calL_0(\hat\phi, f_0) - \hat\calL^{(2)}_0(\hat\phi,  f_0) + \hat \calL_0^{(2)}(\hat\phi, f_{0, \hat\phi}) - \calL_0(\hat\phi, f_{0, \hat \phi})\bigg\} +\sup_{\bar \phi^{\hat{\boldsymbol{\omega}}}}\calL_0^\star(\bar\phi^{\hat{\boldsymbol{\omega}}}) - \calL_0^\star(\phi^\star_0) \\
	& \qquad +  \calO\bigg(C_\rho \beta^{1/\rho} \cdot  \bigg(\frac{\nu_\Phi + \log(1/\delta)}{nT} + \frac{\nu_\calF + \log T}{n}\bigg)^{1/2\rho}\bigg)  
\end{align*}
with probability $1-\delta$. Since $\hat\phi$ is independent of the second batch of target data $\{(\bsx_{0i}, y_{0i}): i\in B_2\}$ and $|B_2|\asymp n_0$, a nearly identical argument as that appeared in the proof of Lemma \ref{lemma:err_learn_decoder} gives
$$
	\sup_{f_0\in\calF} \bigg\{ \calL_0(\hat\phi, f_0) - \hat\calL^{(2)}(\hat\phi,  f_0) + \hat \calL_0^{(2)}(\hat\phi, f_{0, \hat\phi}) - \calL_0(\hat\phi, f_{0, \hat \phi})\bigg\} \lesssim \sqrt{\frac{\nu_\calF + \log(1/\delta)}{n_0}}
$$
with probability at least $1-\delta$. We conclude the proof by invoking a union bound.

















\section{Experimental Details and Additional Results}
\label{sec:appx-exp}

\begin{table}[t]
\centering
\scalebox{0.76}{
\begin{tabular}{c||c|c|c||c}
\hline
\diagbox[font=\footnotesize\itshape]{Learning Paradigm}{Setting} & PoS + {\bf NER} & PoS + Chunking + {\bf NER}  & PoS + Chunking + {\bf Predicate Detection} & Avg \\ \hline
 Single-Task Learning &  68.47 & 68.47 &  78.00 & 71.65  \\ \hline
 Joint Training & 65.70 & 67.12 & 79.81 & 70.88 \\ 
 Weighted Joint Training & {\bf 69.58} & {\bf 69.73} & {\bf 80.38} & {\bf 73.23} \\ \hline
\end{tabular}}
\caption{Additional experiments to illustrate the benefits of weighted joint training compared to joint training. For each setting, the task in the bold text is the target task and the remaining tasks are source tasks. The improvement from weighted training in the joint training paradigm indicates that \NAMEALG{} is also beneficial with one or two source tasks. More details can be found in Appx. \ref{sec:appx-exp}.
}
\label{table:extra-weighted-joint-training}
\end{table}

\begin{table}[t]
\centering
\scalebox{0.86}{
\begin{tabular}{c||c|c|c|c|c|c|c|c||c}
\hline
\diagbox[font=\footnotesize\itshape]{Learning Paradigm}{Ratio} & 1 & 2  & 4 & 8 & 16 & 32 & 64 & 128 & Avg \\ \hline
 Single-Task Learning & 30.08 & 30.08 & 30.08 & 30.08 & 30.08 & 30.08 & 30.08 & 30.08 & 30.08  \\ \hline
 Normalized Joint Training & 38.55 & 36.53 & 42.37 & 54.18 & 62.08 & 63.58 & 62.85 & 62.33 & 52.81 \\ 
 Weighted Normalized Joint Training & {\bf 42.31} & {\bf 42.13} & {\bf 51.64} & {\bf 59.08} & {\bf 63.46} & {\bf 64.86} & {\bf 64.08} & {\bf 63.65} & {\bf 56.40} \\ \hline
 Upper Bound & 62.69 & 70.31 & 75.65 & 79.39 & 81.59 & 83.19 & 84.18 & - & - \\ \hline
\end{tabular}}
\caption{The performance for the analysis on the ratio between the training sizes of the source and target datasets in Fig. \ref{fig:analysis}. In this part, we use NER as the target task and source tasks include PoS tagging and predicate detection. We keep the training size of the target task as $500$, and change the ratio from $1$ to $128$ in a log scale. Single-task learning denotes learning only with the small target data, and upper bound denotes learning with the target data that has the same size as the overall size of all datasets in cross-task learning. "-" means that we do not have enough training data for the upper bound in that setting.
More details can be found in Appx. \ref{sec:appx-exp}. The sampling strategy\protect\footnotemark{} for training examples we used for the analysis is a little different from that used in the main experiments (Table \ref{table:results}), so that the performance of single-task learning for the same setting can be a little different.
}
\label{table:ratio}
\end{table}

\begin{table}[t]
\centering
\scalebox{0.98}{
\begin{tabular}{c||c|c|c|c|c|||c}
\hline
\diagbox[font=\footnotesize\itshape]{Learning Paradigm}{Target Size} & 500 & 1000  & 2000 & 4000 & 8000 & Avg \\ \hline
 Single-Task Learning & 30.08 & 54.26 & 68.05 & 74.77 & 79.20 & 61.27 \\ \hline
 Normalized Joint Training (Ratio=8) & 54.18 & 64.69 & 71.33 & 76.95 & 80.37 & 69.50 \\ 
 Weighted Normalized Joint Training (Ratio=8) & {\bf  59.08} & {\bf 66.00} & {\bf 72.30} & {\bf 76.95} & {\bf  80.64} & {\bf 70.99} \\ \hline
 Upper Bound & 79.39 & 81.49 & 83.53 & 84.26 & - & - \\ \hline
 Normalized Joint Training (Ratio=10) & 58.06 & 65.94 & 71.48 & 77.33 & {\bf 80.34} & 70.63 \\ 
 Weighted Normalized Joint Training (Ratio=10) & {\bf 60.96} & {\bf 67.45} & {\bf 72.52} & {\bf 77.44} & 79.94 & {\bf 71.66} \\ \hline
  Upper Bound & 79.70 & 82.32 & 83.39 & 84.84 & - & - \\ \hline
\end{tabular}}
\caption{The performance for the analysis on the training size of the target dataset in Fig. \ref{fig:analysis}. In this part, we use NER as the target task and source tasks include PoS tagging and predicate detection. We keep the ratio between the training sizes of the source and target datasets as $8$ ($10$), and change the training size of the target dataset from $500$ to $8000$ in a log scale. Single-task learning denotes learning only with the small target data, and upper bound denotes learning with the target data that has the same size as the overall size of all datasets in cross-task learning. "-" means that we do not have enough training data for the upper bound in that setting. More details are in Appx. \ref{sec:appx-exp}.  
}
\label{table:target-size}
\end{table}

\begin{table}[t]
\centering
\scalebox{0.76}{
\begin{tabular}{|c||c|c|c|c|}
\hline
\diagbox[font=\footnotesize\itshape]{Learning Paradigm}{Target Task} & PoS & Chunking  & Predicate Detection & NER   \\ \hline
 Weighted Pre-Training  & (0.68, 0.01, 0.31) & (0.32, 0.30, 0.37) & (0.33, 0.35, 0.32) &  (0.92, 0.05, 0.04) \\  \hline
\multirow{2}{*}{Weighted Joint Training}  & (0.04, 0.04, 0.03) &  (0.04, 0.04, 0.05) & (0.04, 0.04, 0.05) & (0.04, 0.04, 0.05)  \\
  &  {\bf 0.89} & {\bf 0.87} & {\bf 0.87} & {\bf 0.87}    \\  \hline
\multirow{2}{*}{Weighted Normalized Joint Training}  &  (0.0005, 0.0004, 0.0004) & (0.0005, 0.0005, 0.0004) & (0.002, 0.002, 0.002) & (0.003, 0.003, 0.003)  \\  
  &  {\bf 0.9986} & {\bf 0.9987} & {\bf 0.995} &  {\bf 0.990}  \\  \hline
\end{tabular}}
\caption{The final weights on tasks in the main experiments. For each setting, the final weights on three source tasks are represented by a three-element tuple. The source tasks are always organized in the following order: PoS tagging, chunking, predicate detection, and NER. For example, the tuple (0.68, 0.01, 0.31) for the target task Pos tagging in the weighted pre-training indicate that the final weights on the three source tasks (chunking, predicate detection, NER) are 0.68, 0.01, and 0.31 respectively. As for \NAMEALG{} in the joint training, we have an extra weight on the target task, which is bold in the second line. More details can be found in Appx. \ref{sec:appx-exp}.
}
\label{table:final-weights}
\end{table}

\begin{table}[t]
\centering
\scalebox{0.86}{
\begin{tabular}{c||c|c|c|c||c}
\hline
\diagbox[font=\footnotesize\itshape]{Learning Paradigm}{Target Task} & PoS & Chunking  & Predicate Detection & NER  & Avg \\ \hline
 Weighted Pre-Training (fixed weights) & 49.17 & 73.05 & 74.26 & 39.84 & 59.08  \\ 
 Weighted Pre-Training (dynamic weights) & {\bf 51.17}  & {\bf 73.41} & {\bf 75.77} & {\bf 46.23}  & {\bf 61.64} \\ \hline
 Weighted Normalized Joint Training (fixed weights) & {\bf 86.93} & 90.12 & 74.90 & {\bf 63.60 } & 78.89  \\ 
 Weighted Normalized Joint Training (dynamic weights) &  86.07 & {\bf 90.62}  &  {\bf 76.67} &  63.44  & {\bf 79.20} \\ \hline 
\end{tabular}}
\caption{Comparison between dynamic weights and fixed final weights. There are four tasks in total, PoS tagging, chunking, predicate detection and NER. For each setting, we choose one task as the target task and the remaining three tasks are source tasks. More details can be found in Appx. \ref{sec:appx-exp}.
}
\label{table:dynamic-weights}
\end{table}



\begin{figure}[t]
	\centering
    \includegraphics[scale=0.5]{figures/weighted_sample.pdf}
    \caption{Extension to weighted-sample training. The weighted training algorithm can be easily extended from the weights on tasks to the weights on samples. As for the experiments on weighted-sample training, we use the PoS tagging on entity words as the source task and named entity classification on entity words as the target task. Note that the settings for the weighted-sample training is quite different from those for the weighted-task training in the remaining parts, because the weighted-sample training is much more costly compared to the weighted-task training. 
    More details can be found in Appx. \ref{sec:appx-exp}.
    }
	\label{fig:weighted-sample}
\end{figure}

\begin{figure}[t]
	\centering
    \includegraphics[scale=0.5]{figures/illustration-eps-converted-to.pdf}
    \caption{Illustration for the task distance. We find that {\bf the source data is more beneficial, when the task distance between the source data and the target data is smaller or the size of the target data is smaller. } In this part, we keep the training size of the source task as $10000$, and change the training size of the target task from $10$ to $10000$ in a log scale. STL denotes the single-task learning only with the target data. LTL denotes the learning to learn paradigm, where we first learn the representations in the source data and then learn the task-specific function in the target data. For the learning to learn paradigm, we consider the source task with different flip rates from $0.0$ to $1.0$, where the flip rate is an important factor in generating the source data and lower flip rate indicates smaller task distance between the source data and the target data. More details are in Appx. \ref{sec:appx-exp}.
    }
	\label{fig:illustration}
\end{figure}



In this subsection, we briefly highlight some important settings in our experiments. More details can be found in our released code. It usually costs about half an hour to run the experiment for each setting (e.g. one number in the Table \ref{table:results}) on one GeForce RTX 2080 GPU. As far as we know, the code and data that we used and curated do not contain personally identifiable information and offensive content.

{\bf Data.} In our experiments, we mainly use two widely-used NLP datasets, Ontontes 5.0 \citep{hovy2006ontonotes} and CoNLL-2000 \citep{sang2000introduction}. Ontonotes 5.0 is a large multilingual richly-annotated corpus covering a lot of NLP tasks, and we use the corresponding English annotations for three sequence tagging tasks, PoS tagging, predicate detection and NER. CoNLL-2000 is a shared task for another sequence tagging task, chunking. There are about $116K$ sentences, $16K$ sentences and $12K$ sentences in the training, development, and test sets for tasks in Ontonotes 5.0. The average sentence length for sentences in Ontonotes 5.0 is about $19$. As for CoNLL-2000, there are about $9K$ sentences and $2K$ sentences in the training and test sets. The corresponding average sentence length is about $24$. 

{\bf Tasks.} We consider four common sequence tagging tasks in NLP, PoS tagging, chunking, predicate detection and NER. PoS tagging aims to assign a particular part of speech, such as nouns and verbs, for each word in the sentence. Chunking divides a sentence into syntactically related non-overlapping groups of words and assign them with specific types, such as noun phrases and verb phrases. Predicate detection aims to find the corresponding verbal or nominal predicates for each sentence. NER seeks to locate and classify named entities mentioned in each sentence into pre-defined categories such as person names, organizations, and locations. Based on the above datasets, there are $50$ labels in PoS tagging, $23$ labels in chunking, $2$ labels in predicate detection, and $37$ labes in NER. As for the evaluation metric, we use accuracy for PoS tagging, span-level F1 for chunking, token-level F1 for predicate detection, and span-level F1 for NER. 

\footnotetext{Specifically, in the main experiments, we first randomly sample $9K$ sentences and then sample specific number of sentences (e.g. $500$ sentences for NER) among the $9K$ sentences for the training set of the target task. In the analysis, we first randomly sample $100K$ sentences and then sample specific number of sentences (e.g. $500$ sentences for NER) among the $100K$ sentences for the training set of the target task. We use a different sampling strategy for training sentences in main experiments and analysis, simply because the largest training size of the data we considered in the two situations is different. }

{\bf The model.} We use BERT \citep{devlin2019bert} as our basic model in our main experiments. Specifically, we use the pre-trained case-sensitive BERT-base pytorch implementation \citep{wolf2020transformers}. We use the common parameter settings for BERT. Specifically, the max length is $128$, batch size is $32$, the epoch number is $4$, and the learning rate is $5e^{-5}$. In the BERT model, the task-specific function is the last-layer linear classifier, and the representation model is the remaining part. 

{\bf Cross-task learning paradigms.} In our experiments, we consider two cross-task learning paradigms, pre-training and joint training. Pre-training first pre-train the representation part on the source data and then fine-tune the whole target model on the target data. Joint training use both source and target data to train the shared representation model and task specific functions for both source and target tasks at the same time. As for the multi-task learning part in both pre-training and joint training, we adopt the same multi-task learning algorithm as in MT-DNN \citep{liu2019multi}. 

{\bf Additional experiments to illustrate the benefits of \NAMEALG{}.} In this part, we conduct additional experiments with \NAMEALG{} on the joint training with fewer source tasks compared to the main experiments in Sec. \ref{sec:experiments}. For simplicity, we make the target task bold to distinguish it from source tasks for each setting. For example, in the setting of PoS + Chunking + \textbf{NER}, NER is the target task and other two tasks are source tasks. For PoS + {\bf NER}, we randomly sample $20K$ training sentences for PoS tagging and $2K$ training sentences for NER. For PoS + Chunking + {\bf NER}, we randomly sample $20K$, $9K$\footnote{We choose $9K$ training sentences for chunking because the training size of the chunking dataset is $8936$.} and $2K$ training sentences for PoS tagging, chunking and NER respectively. As for PoS + Chunking + {\bf Predicate Detection}, we randomly sample $20K$, $9K$, and $2K$ training sentences for PoS tagging, chunking, and predicate detection respectively. As shown in Table \ref{table:extra-weighted-joint-training}, we can see that \NAMEALG{} is still beneficial with one or two source tasks, which is a complement for our main experiments in Sec. \ref{sec:experiments}, where there are three source tasks. 

{\bf Analysis of some crucial factors.} As shown in  Fig. \ref{fig:analysis}, we analyze two crucial factors that affects the improvement of \NAMEALG{}. First, in general, we find that the improvement of \NAMEALG{} in normalized joint training is larger when the ratio between the training sizes of the source and target dataset is smaller, though the largest improvement may not be achieved at the smallest ratio. Note that the improvement vanishes with large ratio mainly because the baseline (normalized joint training) is already good enough with large ratio (see the specific performance in Appx. \ref{sec:appx-exp}). Second, the improvement from \NAMEALG{} will decrease with the increase of the training size of the target data. In a word, \NAMEALG{} is more beneficial when the performance of the base mode is poorer, either with a smaller target data or with a smaller ratio. The specific performance for experiments in our analysis on two crucial factors for \NAMEALG{} (see Sec. \ref{sec:experiments}), the ratio between the training sizes of the source and target datasets, and the training size of the target dataset, can be found in Table \ref{table:ratio} and Table \ref{table:target-size} respectively. 

{\bf Dynamic weights analysis.} In our experiments, there are always four tasks in total, PoS tagging, chunking, predicate detection and NER. For each setting, we choose one task as the target task and the remaining three tasks are source tasks. The final weights on tasks are shown in Table \ref{table:final-weights}. To better understand our algorithm, we compare \NAMEALG{} with dynamic weights and \NAMEALG{} with fixed final weights. \NAMEALG{} with dynamic weights is the default setting for our algorithm, where weights on tasks for each epoch are different. As for \NAMEALG{} with fixed weights, we simply initialize the weights as the final weights that learned by our algorithm and fix the weights during the training. As shown in Table \ref{table:dynamic-weights}, we find that \NAMEALG{} with dynamic weights (the default one) is slightly better than \NAMEALG{} with final fixed weights. It indicates that fixed weights might not be a good choice for weighted training, because the importance of different source tasks may change during the training. In other words, it might be better to choose the weighted training with dynamic weights, where the weights are automatically adjusted based on the state of the trained model. 

{\bf Extension to the weighted-sample training.} As shown in Fig. \ref{fig:weighted-sample}, \NAMEALG{} can be easily extended from the weights on tasks to the weights on samples. We can see that \NAMEALG{} based on weighted-sample training is also beneficial for both pre-training and joint training. Because the weighted-sample training is much more costly compared to the weighted-task training, we choose a much simpler setting here. In this part, we use the PoS tagging on entity words as the source task and named entity classification on entity words as the target task. Note that both tasks we considered here are word-level classification task, i.e., predicting the label for a given word in a named entity. We still use the Ontontes 5.0 \citep{hovy2006ontonotes} as our dataset. There are $50$ labels in PoS tagging on entity words, and $18$ labels \footnote{In NER, we have $37$ labels because each type of entities have two variants of labels (B/I for beside/inside) and one more extra label $O$ for non-entity words is also considered. } in named entity classification on entity words. There are $37534$ examples in the development set and $23325$ examples in the test set for both source and target tasks. As for the training set, we randomly sample $1000$ examples for the source task and $100$ examples for the target task. As for the model, we use a two-layer NNs with $5$-gram features. The two-layer NNs has a hidden size of $4096$, ReLU non-linear activation and cross-entropy loss. As for the embeddings, we use $50$ dimensional Glove embeddings \citep{pennington2014glove}. The majority baseline for named entity classification on entity words on the test data is $20.17\%$. As for training models, the size of the training batch is $128$, the optimizer is Adam \citep{kingma2015adam} with learning rate $3e^{-4}$, and the number of training epochs is $200$. As for updating weights on samples, we choose to update the weights every $5$ epochs with the mirror descent in Eq. \ref{eq:mirror_descent} and thus $40$ updates on weights in total. In this part, we approximate the inverse of the Hessian matrix ($\Big[\sum_{t=1}^T \omega_t \nabla_\phi^2 \hat\calL_t(\phi^{k+1}, f_t^{k+1})\Big]^{-1}$ ) in Eq. \ref{eq:task_gradient} by a constant multiple of the identity matrix as in MAML \citep{finn2017model}, and choose the constant as $5$. According to our experiments, the results of this approximation are similar to those of the approximation that we used in Sec. \ref{sec:experiments}. The corresponding results are shown in Fig. \ref{fig:weighted-sample}. 

{\bf Settings for simulations on task distance.} In this part, we first randomly generate $10K$ examples $\calD$, where the dimension of the inputs are $1000$ and the corresponding labels are in $0-9$ ($10$ classes). For each dimension of the input, it is randomly sampled from a uniform distribution over $[-0.5, 0.5]$. For each flip rate $q\% \in [0, 1]$ , we randomly choose $q\%$ of the data and replace their labels with a random label uniformly sampled from the $10$ classes. The data with flip rate $q\%$ is denoted as $\calD_{q\%}$ (including $\calD_{0.0}$ for the original dataset). For each dataset $\calD_{q\%}$, we train a 2-layer NNs $\calM_{q\%} $with $100\%$ accuracy and almost zero training loss on the dataset. The 2-layer NNs can then be used to generate data for the task $T_{q\%}$. We use the $T_{0.0}$ as the target task and change $q\%$ from $0.0$ to $1.0$ as the source task. Based on the process of the data generation, we can see that the flip rate $q\%$ plays an important role on the intrinsic difference between the source task $T_{q\%}$ and the target task $T_{0.0}$. In general, we can expect that smaller flip rate $q\%$ indicates smaller task distance between the source task $T_{q\%}$ and the target task $T_{0.0}$. This data generation process is inspired by the teacher-student network in \cite{hinton2015distilling}. As shown in Fig. \ref{fig:illustration}, we keep the training size of the source task as $10000$, and change the training size of the target task from $10$ to $10000$ in a log scale. For simplicity, we use the same architectures for both the teacher network that we used for generating data and the student network that we used for learning the data, i.e., a two-layer neural network with a hidden size of $4096$, an input size of $1000$, and a output size of $10$. As for training, the size of the training batch is $100$, the optimizer is Adam \citep{kingma2015adam} with learning rate $3e^{-4}$, and the number of training epochs is $100$. 

{\bf Details on using existing assets.} As for the corresponding code and pre-trained models for BERT, we directly download it from the github of huggingface whose license is Apache-2.0, and more details can be found in \url{https://github.com/huggingface/transformers}. As for the Ontonotes 5.0, we obtain the data from LDC. The corresponding license and other details can be found in \url{https://catalog.ldc.upenn.edu/LDC2013T19}. As for CoNLL-2000 shared task, we download the data directly from the website and more details are in \url{https://www.clips.uantwerpen.be/conll2000/chunking}.