# Representation Transfer Learning via Multiple Pre-trained models for Linear
Regression

Navjot Singh<EMAIL_ADDRESS><EMAIL_ADDRESS>Suhas Diggavi
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this paper, we consider the problem of learning a linear regression model
on a data domain of interest (target) given few samples. To aid learning, we
are provided with a set of pre-trained regression models that are trained on
potentially different data domains (sources). Assuming a representation
structure for the data generating linear models at the sources and the target
domains, we propose a representation transfer based learning method for
constructing the target model. The proposed scheme is comprised of two phases:
(i) utilizing the different source representations to construct a
representation that is adapted to the target data, and (ii) using the obtained
model as an initialization to a fine-tuning procedure that re-trains the
entire (over-parameterized) regression model on the target data. For each
phase of the training method, we provide excess risk bounds for the learned
model compared to the true data generating target model. The derived bounds
show a gain in sample complexity for our proposed method compared to the
baseline method of not leveraging source representations when achieving the
same excess risk, therefore, theoretically demonstrating the effectiveness of
transfer learning for linear regression.

##  1 Introduction

A critical challenge for Deep Learning applications is the scarcity of
available labeled data to train large scale models that generalize well to the
data distribution. This is captured under the framework of _Few-Shot Learning_
where Transfer Learning has emerged as an attractive framework to address this
issue [1]. In transfer learning, one typically has access to a model trained
on some data domain (hereby called _source domain_) that can be adapted to the
data domain of interest (_target domain_). Within this context, a recently
proposed strategy is that of _representation transfer learning_ [2, 3], where
one typically assumes a shared structure between the source and target
learning tasks. The idea is to then learn a feature mapping for the underlying
model (e.g. Neural Network representations) using the sample rich source
domain that can be utilized directly on the target domain, for e.g, by
training a few layers on top of the obtained network representation. This
adaptation utilizes much fewer samples than what is required for training the
entire model from scratch, while achieving good generalization performance
which has been empirically observed for various large-scale machine learning
application including image, speech and language [1, 4, 5] tasks.

A defining factor in the need for representation transfer methods is that the
source and target domains have different distributions. Learning across
different domains has been studied extensively in the context of _Domain
Adaptation_ (see for e.g. [6, 7]) where it is usually assumed that source and
target domain data can be accessed simultaneously. However, in many important
practical scenarios of interest, the target data samples (labeled or
unlabeled) are not available when training the source models. Transferring the
source dataset to the target deployment scenario is infeasible for modern
large-scale applications and violates data privacy. Thus there has been an
increasing interest in transferring pre-trained source models to the target
domain for sample efficient learning.

Despite the immense empirical success of representation transfer learning,
development of a theory for understanding the generalization of representation
learning methods and the sample complexity requirements is still in its
infancy. Recent efforts in this direction have been made in understanding
generalization for the simpler case of linear models [8, 9, 10, 11]. Within
these works, [8, 10, 11] consider a common low-dimensional representation in
the data generation process for the source and target domains, while [9]
allows for the general case of data-generating representations being
different. However, the analysis presented in that work requires the number of
samples at the target to scale with the dimension of the model (see [9,
Theorem 3.1]), which is impractical for few-shot learning scenarios.

A related line of work for understanding generalization of large scale models
in the small sample regime is through the lens of _benign overfitting_. This
is inspired by the surprising (empirical) observation that many large models,
even when they overfit, tend to generalize well on the data distribution [12,
13]. In this context, [14, 15, 16] study this phenomena for linear models and
analyze the generalization properties of the _min-norm solution_ , where
optimization methods like Gradient Descent are known to converge to in this
setting [17, 18]. Specifically, these works seek to understand how the data
distribution affects the excess population risk of the min-norm solution
relative to the true data-generating linear model.

In this paper, we make efforts to understanding the generalization of linear
models while leveraging pre-trained models inspired by the notions of
representation transfer learning and benign-overfitting discussed above. These
ideas lend themselves organically to the construction of a sample efficient
training method for the target which we describe below briefly, along with our
contributions.

##### Key Contributions:

Our work provides a method for leveraging multiple pre-trained models for
linear regression objectives (of dimension $d$) on a target task of interest
in the small sample regime (samples $n_{T}\ll d$). The proposed two-phase
approach leverages representation transfer (Phase 1) and over-parameterized
training (Phase 2) to construct the target model, and we provide theoretical
bounds for the excess risk for each phase of the training process (Theorem 1
and Theorem 2). In particular, we show that the learned model after the first
phase has an excess risk of
$\mathcal{O}\left(\nicefrac{{q}}{{n_{T}}}\right)+\epsilon$, where $q$ is
dimension of the subspace spanned by learned source representations and
$\epsilon$ is a constant that captures the approximation error when utilizing
source representations for the target model (c.f. Assumption 1). This provides
a gain in sample complexity compared to the baseline
$\mathcal{O}\left(\nicefrac{{d}}{{n_{T}}}\right)$ when learning the target
model from scratch when the given source representations span a subspace of
dimension much smaller than $d$ (i.e. $q\ll d$). For the case when all
representations are the same ($\epsilon=0$), we recover the result of [8] for
a _single_ common representation. Similarly, for the overall model obtained
after the second phase, we provide conditions on the target data distribution
and the source/target representations that lead to an excess risk much smaller
than $\mathcal{O}\left(\nicefrac{{d}}{{n_{T}}}\right)$. Thus, we theoretically
demonstrate the benefit of leveraging pre-trained models for linear
regression.

###  1.1 Related Work

The problem of learning with few samples has been studied under the framework
of _Few-Shot learning_ , where _Meta-learning_ – using experiences from
previously encountered learning tasks to adapt to new tasks quickly [19], and
_Transfer-learning_ – transferring model parameters and employing pre-training
or fine-tuning methods [3], are two major approaches. Theoretical works on
Meta-learning algorithms typically assume some relation between the
distribution of source and target tasks, for e.g., being sampled from the same
task distribution. A more general framework is that of _Out-of-Domain (OOD)_
generalization, where the goal is to learn models in a manner that generalize
well to unseen data domains [20].

Transfer learning, especially, representation transfer learning has shown
empirical success for large-scale machine learning [2], however, theoretical
works on understanding generalization in this setting are few; see [21, 22,
11]. A related line of work is representation learning in context of _Domain
Adaptation (DA)_ , see for e.g. [23, 24, 25, 26]. However, this usually
assumes that source and data domains can be accessed simultaneously. There are
deviations from this theme in _Multi-Source DA_ where the goal is to
understand how multiple source models can be combined to generalize well on a
target domain of interest, although without changing the learned model based
on the target samples [27, 28, 29].

In context of leveraging pre-trained models for linear regression, our work is
most closely related to [8, 9] that theoretically analyze representation
transfer for linear models. In contrast to [8], we allow for the true target
representations to be different among the source models as well as the target,
and introduce a notion of closeness between these representations (c.f.
Assumption 1). Although a similar setting was considered in [9] where
representations are assumed to be close in the $\ell_{2}$ norm, their
resulting bound for the fine-tuned model risk shows that the required number
of target samples scale with the dimension of the learned model for efficient
transfer [9, Theorem 3.1]. In contrast, the proposed method in our work
provides analysis relating these bounds to the properties of the target data
distribution taking inspiration from works on benign overfitting for linear
regression [14, 18, 30]. This enables us to identify conditions on the target
data distribution that allow the required target samples to be much smaller
than the overall model dimension (see Theorem 2).

###  1.2 Paper Organization

We set up the problem and define the notation we use throughout the paper in
Section 2. Section 3 describes our training method for the target task model
when given access to multiple pre-trained source models. Section 4 establishes
excess risk bounds of our proposed scheme, which are proved in Sections 5 and
Section 6. Section 7 provides numerical results and some concluding remarks
are presented in Section 8.

##  2 Problem Setup and Notation

##### Notation:

We use boldface for vectors and matrices, with matrices in uppercase. For a
matrix $\mathbf{A}$, we denote the projection matrix onto its column space by
$\mathbf{P}_{\mathbf{A}}:=\mathbf{A}(\mathbf{A}^{\top}\mathbf{A})^{\dagger}\mathbf{A}^{\top}$
where $\mathbf{W}^{\dagger}$ denotes the Moore-Penrose pseudo-inverse of the
matrix $\mathbf{W}$. We define
$\mathbf{P}^{\perp}_{\mathbf{A}}:=\mathbf{I}-\mathbf{P}_{\mathbf{A}}$, where
$\mathbf{I}$ denotes the identity matrix of appropriate dimensions. We denote
by $\mathcal{C}(\mathbf{A})$ the column space of a matrix $\mathbf{A}$ and by
$\sigma_{i}(\mathbf{A})$, $\lambda_{i}(\mathbf{A})$ its $i^{th}$ largest
singular value and eigenvalue, respectively. $\left\|.\right\|_{F}$ denotes
the Frobenius norm. For a vector $\mathbf{v}$, $\|\mathbf{v}\|_{2}$ denotes
the $\ell_{2}$ norm, while for a matrix $\mathbf{V}$, $\|\mathbf{V}\|_{2}$
denotes the spectral norm. $\text{Tr}[\,.\,]$ denotes the trace operation.
$\lesssim$ denotes the inequality sign where we ignore the constant factors.
The notation ${\mathcal{O}}$ is the ‘big-O’ notation and we define
$[m]=\\{1,2,\ldots,m\\}$.

##### Setup:

We consider $m$ number of source tasks and a single target task. We denote by
$\mathcal{X}\subseteq\mathbb{R}^{d}$ the space of inputs and
$\mathcal{Y}\subseteq\mathbb{R}$ the output space. The source and target tasks
are associated with data distributions $p_{i}$, $i\in[m]$ and $p_{T}$,
respectively, over the space $\mathcal{X}$. We assume a linear relationship
between the input and output pairs for source task $i\in[m]$ given by:

$\displaystyle
y_{i}=\mathbf{x}_{i}^{\top}\mathbf{B}_{i}^{*}\mathbf{w}_{i}^{*}+z_{i},\quad{\boldsymbol{\theta}}_{i}^{*}:=\mathbf{B}_{i}^{*}\mathbf{w}_{i}^{*}$
(1)

where $\mathbf{x}_{i}\in\mathcal{X}$ denotes an input feature vector drawn
from distribution $p_{i}$, $y_{i}\in\mathcal{Y}$ is the output, and
$z_{i}\sim\mathcal{N}(0,\sigma^{2})$ denotes Gaussian noise. The associated
true task parameter
${\boldsymbol{\theta}}_{i}^{*}:=\mathbf{B}_{i}^{*}\mathbf{w}_{i}^{*}$ is
comprised of the representation matrix
$\mathbf{B}_{i}^{*}\in\mathbb{R}^{d\times k}$ which maps the input to a lower
$k-$dimensional space (where $k\ll d$) and a head vector
$\mathbf{w}_{i}^{*}\in\mathbb{R}^{k}$ mapping the intermediate sample
representation to the output. The data generation process for the target task
is defined similarly with distribution $p_{T}$ and associated target task
parameter given by
${\boldsymbol{\theta}}_{T}^{*}=\mathbf{B}_{T}^{*}\mathbf{w}_{T}^{*}$. For
sources $i\in[m]$, we define the input covariance matrix
$\boldsymbol{\Sigma}_{i}=\mathbb{E}_{\mathbf{x}_{i}\sim
p_{i}}[\mathbf{x}_{i}\mathbf{x}_{i}^{\top}]$ and similarly for the target
distribution, $\boldsymbol{\Sigma}_{T}=\mathbb{E}_{\mathbf{x}_{T}\sim
p_{T}}[\mathbf{x}_{T}\mathbf{x}_{T}^{\top}]$.
In our scenario of interest, the pre-trained models are trained ‘offline’ on
source distributions and are made available to the target task during
deployment. That is, for training the target task, we have access to only the
models learned by the source tasks and not the source datasets themselves. For
learning the pre-trained source models, we assume $n_{S}$ number of samples
for each of the source tasks (thus, $mn_{S}$ source task samples in total)
denoted by the pair $(\mathbf{X}_{i},\mathbf{y}_{i})$ for source $i\in[m]$
where $\mathbf{X}_{i}\in\mathbb{R}^{n_{S}\times d}$ contains row-wise input
feature vectors and $\mathbf{y}_{i}\in\mathbb{R}^{n_{S}}$ is the vector of
corresponding outputs. We similarly have $n_{T}$ samples
$(\mathbf{X}_{T},\mathbf{y}_{T})$ for the target task where $n_{T}\ll n_{S}$.
We also assume $n_{T}\ll d$.
With the data generation process defined above, we now define the expected
population risk on the target distribution for $\hat{{\boldsymbol{\theta}}}$:

$\displaystyle R(\hat{{\boldsymbol{\theta}}})=\mathbb{E}_{\mathbf{x}\sim
p_{T}}\mathbb{E}_{\mathbf{y}|\mathbf{x}^{\top}{\boldsymbol{\theta}}_{T}^{*}}[(\mathbf{y}-\mathbf{x}^{\top}\hat{{\boldsymbol{\theta}}})^{2}]$

Our goal is to learn a model $\hat{{\boldsymbol{\theta}}}$ for the target task
that generalizes well to the target data distribution. Thus, we want
$\hat{{\boldsymbol{\theta}}}$ that minimizes the _Expected Excess Risk_
defined by:

$\displaystyle\text{EER}(\hat{{\boldsymbol{\theta}}},{\boldsymbol{\theta}}_{T}^{*}):=R(\hat{{\boldsymbol{\theta}}})-R({\boldsymbol{\theta}}_{T}^{*})$
(2)

Since we are given access to only $n_{T}\ll d$ target samples, it is
infeasible to learn a predictor from scratch that performs well for the excess
risk defined in (2).
To aid learning on the target, we have access to models learned on the source
tasks. Specifically, the target has access to the trained source models
representations $\\{\widehat{\mathbf{B}}_{i}\\}_{i=1}^{m}$ that are solutions
of the following empirical minimization problem:

$\displaystyle\\{\widehat{\mathbf{B}}_{i},\widehat{\mathbf{w}}_{i}\\}_{i=1}^{m}\leftarrow$
$\displaystyle\min_{\\{\mathbf{B}_{i}\\},\\{\mathbf{w}_{i}\\}}\frac{1}{mn_{S}}\sum_{i=1}^{m}\left\|\mathbf{y}_{i}-\mathbf{X}_{i}\mathbf{B}_{i}\mathbf{w}_{i}\right\|_{2}^{2}$
(3)

Since we have data rich source domains ($n_{S}\gg d$), we expect the obtained
source models $\widehat{\mathbf{B}}_{i}\widehat{\mathbf{w}}_{i}$ to be close
to ${\boldsymbol{\theta}}^{*}_{i}$ for $i\in[m]$ (c.f. Equation (1)). For
effective representation transfer, we also want the learned representations
$\\{\widehat{\mathbf{B}}_{i}\\}$ to be close to the true representations
$\\{\mathbf{B}^{*}_{i}\\}$, in the sense that they approximately span the same
subspace. We make this notion precise in Lemma 1 stated with our main results
in Section 4. Given access to the source model representations, our proposed
method for training the target model leverages the representation maps
$\\{\widehat{\mathbf{B}}_{i}\\}_{i=1}^{m}$ to drastically reduce the sample
complexity. We describe our training method in Section 3 and provide the
excess risk bounds for the resulting target model in Section 4.

##  3 Learning with Multiple Pre-trained models

To leverage source representations for training the target model, it is
instinctive that there should be a notion of closeness between the true source
and target model representation that can be exploited for target task
training. We now make this notion precise. We first define as
$\mathbf{V}^{*}\in\mathbb{R}^{d\times l}$ the matrix whose columns are an
orthonormal basis of the set of columns of all the source representation
matrices $\\{\mathbf{B}_{i}^{*}\\}_{i=1}^{m}$. The individual source models
can thus be represented by
${\boldsymbol{\theta}}_{i}^{*}=\mathbf{V}^{*}\widetilde{\mathbf{w}}_{i}^{*}$
for all $i\in[m]$. The target model
${\boldsymbol{\theta}}_{T}^{*}=\mathbf{B}_{T}^{*}\mathbf{w}_{T}^{*}$ governing
the target data generation is assumed to satisfy the following:

###### Assumption 1

Consider the projection of the target model
$\mathbf{B}^{*}_{T}\mathbf{w}_{T}^{*}$ to space $\mathcal{C}(\mathbf{V}^{*})$
given by $\mathbf{V}^{*}\widetilde{\mathbf{w}}_{T}^{*}$ for some
$\widetilde{\mathbf{w}}_{T}^{*}\in\mathbb{R}^{l}$. Then for some $\epsilon>0$,
we have:

$\mathbb{E}_{\mathbf{x}\sim
p_{T}}\left[\mathbf{x}^{\top}\mathbf{V}^{*}\widetilde{\mathbf{w}}_{T}^{*}-\mathbf{x}^{\top}\mathbf{B}_{T}^{*}\mathbf{w}_{T}^{*}\right]^{2}\leq\epsilon^{2}$

The value of $\epsilon$ in Assumption 1 above captures how far away the output
of the true target model is to a model learned using the true source
representations. Note that if the columns of $\mathbf{B}_{T}^{*}$ can be
constructed by the vectors in $\mathbf{V}^{*}$, the above is satisfied for
$\epsilon=0$. Assumption 1 can also be re-written as:

$\left\|\Sigma_{T}^{\nicefrac{{1}}{{2}}}\left(\mathbf{V}^{*}\widetilde{\mathbf{w}}_{T}^{*}-\mathbf{B}_{T}^{*}\mathbf{w}_{T}^{*}\right)\right\|_{2}^{2}\leq\epsilon^{2}$
(4)

We are given access to $n_{T}$ samples for the target machine given by
$(\mathbf{X}_{T},\mathbf{y}_{T})$ and pre-trained models representations from
the sources $\\{\widehat{\mathbf{B}}_{i}\\}_{i=1}^{m}$ (c.f. Equation (3)).
Our proposed training scheme consists of two phases, which we will now
describe independently in the following. We split the available $n_{T}$ target
samples into $n_{T_{1}},n_{T_{2}}$ for the two respective phases. At a high
level, in _Phase 1_ , we make use of the available source representations to
construct a target representation and adapt it to the target task using
$n_{T_{1}}$ samples. The obtained model is then used as an _initialization_
for _Phase 2_ where we train the entire (over-parameterized) model, including
the representation matrix, using $n_{T_{2}}$ samples. We provide the resulting
excess risk bounds for the model obtained after _Phase 1_ and the final target
model after _Phase 2_ in Section 4.

###  3.1 Phase 1: Transferring source representation to target

In the context of utilizing pre-trained models, we will make use of the
empirical source representations $\\{\widehat{\mathbf{B}}_{i}\\}_{i=1}^{m}$ to
learn the target model. We first construct a matrix
$\widehat{\mathbf{V}}\in\mathbb{R}^{d\times q}$ whose columns are the
orthonormal basis of the columns of $\\{\widehat{\mathbf{B}}_{i}\\}_{i=1}^{m}$
which denotes a dictionary of the learned source representation matrices111The
construction of $\widehat{\mathbf{V}}$ from $\\{\widehat{\mathbf{B}}_{i}\\}$
can be done by the Gram-Schmidt process. This can be done in the pre-
deployment phase after training the source models, and $\widehat{\mathbf{V}}$
can be made available directly to the target task.. Note that we have $q\leq
mk$. Having constructed the representation, we train a head vector
$\widehat{\mathbf{w}}_{T_{1}}\in\mathbb{R}^{q}$ minimizing the empirical risk
on $n_{T_{1}}$ samples:

$\widehat{\mathbf{w}}_{T_{1}}\leftarrow\min_{\mathbf{w}_{T}\in\mathbb{R}^{q}}\frac{1}{n_{T_{1}}}\left\|\mathbf{y}_{T_{1}}-\mathbf{X}_{T_{1}}\widehat{\mathbf{V}}\mathbf{w}_{T}\right\|_{2}^{2}$
(5)

Here, $\mathbf{y}_{T_{1}}\in\mathbb{R}^{n_{T_{1}}}$ denotes the first
$n_{T_{1}}$ values of $\mathbf{y}_{T}$ and
$\mathbf{X}_{T_{1}}\in\mathbb{R}^{n_{T_{1}}\times d}$ the first $n_{T_{1}}$
rows of $\mathbf{X}_{T}$. We denote the resulting model at the end of this
phase by
${\boldsymbol{\theta}}_{\text{Phase}_{1}}:=\widehat{\mathbf{V}}\widehat{\mathbf{w}}_{T_{1}}$.
Since we only have to learn the head vector using the available representation
$\widehat{\mathbf{V}}$, the sample complexity requirement is greatly reduced,
which is also evident from our bound for
$\text{EER}({\boldsymbol{\theta}}_{\text{Phase}_{1}},{\boldsymbol{\theta}}_{T}^{*})$
provided in Theorem 1.

###  3.2 Phase 2: Fine-tuning with initialization

The obtained model ${\boldsymbol{\theta}}_{\text{Phase}_{1}}$ from the
previous phase utilizes empirical source representation for its construction.
However, the true target model ${\boldsymbol{\theta}}_{T}^{*}$ may not lie in
the space spanned by the source representation and thus
${\boldsymbol{\theta}}_{\text{Phase}_{1}}$ lies in a ball centered
${\boldsymbol{\theta}}_{T}^{*}$ whose radius scales with $\epsilon$ (c.f.
Assumption 5). To move towards the true model ${\boldsymbol{\theta}}_{T}^{*}$,
we utilize $n_{T_{2}}$ number of target samples (independent from the
$n_{T_{1}}$ samples in the previous phase) to train the entire linear model
using Gradient Descent (GD) with ${\boldsymbol{\theta}}_{\text{Phase}_{1}}$ as
the initialization. In particular, the GD procedure minimizes the following
starting from ${\boldsymbol{\theta}}_{\text{Phase}_{1}}$:

$\displaystyle f({\boldsymbol{\theta}})=\frac{1}{n_{T_{2}}}\|{\bf
y}_{T_{2}}-\mathbf{X}_{T_{2}}{\boldsymbol{\theta}}\|_{2}^{2}$ (6)

Here, $\mathbf{y}_{T_{2}}\in\mathbb{R}^{n_{T_{2}}}$ and
$\mathbf{X}_{T_{2}}\in\mathbb{R}^{n_{T_{2}}\times d}$ are the remaining sample
values from Phase 1. Since $n_{T_{2}}\ll d$, we are in an over-parameterized
regime, for which it is known that GD procedure optimizing the objective in
(6) converges, under appropriate choice of learning rate, to a solution
closest in norm to the initialization [17, 31, 18]; mathematically:

$\displaystyle\min_{{\boldsymbol{\theta}}}\|{\boldsymbol{\theta}}-{\boldsymbol{\theta}}_{\text{Phase}_{1}}\|_{2}$
(7) $\displaystyle\text{s.t.
}\|\mathbf{y}_{T_{2}}-\mathbf{X}_{T_{2}}{\boldsymbol{\theta}}\|_{2}=\min_{\mathbf{b}}\|\mathbf{y}_{T_{2}}-\mathbf{X}_{T_{2}}\mathbf{b}\|_{2}$

We denote the solution of the above optimization problem as
${\boldsymbol{\theta}}_{\text{Phase}_{2}}$, which forms our final target task
model. We provide bounds for
$\text{EER}({\boldsymbol{\theta}}_{\text{Phase}_{2}},{\boldsymbol{\theta}}_{T}^{*})$
in Theorem 2.

##  4 Main Results

We now provide theoretical bounds on the excess risk for the target (c.f.
Equation (2)) when leveraging pre-trained source models. In Section 4.1, we
first state excess risk bounds for the model obtained after Phase 1 (see
Section 3.1), denoted by
${\boldsymbol{\theta}}_{\text{Phase}_{1}}:=\widehat{\mathbf{V}}\widehat{\mathbf{w}}_{T}$,
where target representation $\widehat{\mathbf{V}}$ is constructed as a
combination of source representations and adapted to the target data using
$n_{T_{1}}$ amount of target samples by training a target-specific head vector
$\widehat{\mathbf{w}}_{T}$. In Section 4.2, we provide our overall excess risk
for the model ${\boldsymbol{\theta}}_{\text{Phase}_{2}}$ (c.f. Equation (7))
obtained by re-training the entire (over-parameterized) model via Gradient
Descent with $n_{T_{2}}$ number of target samples (independent form the
previously utilized $n_{T_{1}}$ samples) using
${\boldsymbol{\theta}}_{\text{Phase}_{1}}$ as the initialization.

###  4.1 Theoretical results for representation transfer: Phase 1

We work with the following assumptions:

######  Assumption 2 (Subgaussian features)

We assume that $\mathbb{E}_{\mathbf{x}\sim p_{j}}[\mathbf{x}]=0$ for all
$j\in[m]\cup\\{T\\}$. We consider $\bar{p}_{j}$ to be the _whitening_ of
$p_{j}$ (for $j\in[m]\cup\\{T\\}$) such that
$\mathbb{E}_{\bar{\mathbf{x}}\sim\bar{p}_{j}}[\mathbf{x}]=0$ and
$\mathbb{E}_{\bar{\mathbf{x}}\sim\bar{p}_{j}}[\bar{\mathbf{x}}\bar{\mathbf{x}}^{\top}]=\mathbf{I}$.
We assume there exists $\rho>0$ such that the random vector
$\bar{\mathbf{x}}\sim\bar{p}_{j}$ is $\rho^{2}$-subgaussian.

######  Assumption 3 (Covariance Dominance)

There exists $r>0$ such that $\Sigma_{i}\succeq r\Sigma_{T}$ for all
$i\in[m]$.

######  Assumption 4 (Diverse source tasks)

Consider the source models
${\boldsymbol{\theta}}_{i}^{*}=\mathbf{V}^{*}\widetilde{\mathbf{w}}_{i}^{*}$
for $i\in[m]$. We assume that the matrix
$\widetilde{\mathbf{W}}^{*}:=[\widetilde{\mathbf{w}}_{1}^{*},\ldots,\widetilde{\mathbf{w}}_{m}^{*}]\in\mathbb{R}^{l\times
m}$ satisfies
$\sigma_{l}^{2}(\widetilde{\mathbf{W}}^{*})\geq\Omega\left(\frac{m}{l}\right)$

######  Assumption 5 (Distribution of target task)

We assume that $\widetilde{\mathbf{w}}_{T}^{*}$ follows a distribution $\nu$
such that
$\left\|\mathbb{E}_{\widetilde{\mathbf{w}}\sim\nu}[\widetilde{\mathbf{w}}\widetilde{\mathbf{w}}^{\top}]\right\|_{2}$
is $\mathcal{O}\left(\frac{1}{l}\right)$. We denote
$\Sigma_{\widetilde{\mathbf{w}}_{T}^{*}}=\mathbb{E}_{\widetilde{\mathbf{w}}\sim\nu}[\widetilde{\mathbf{w}}\widetilde{\mathbf{w}}^{\top}]$.

##### Note on Assumptions:

Assumption 2 on sub-Gaussian features is commonly used in literature to obtain
probabilistic tail bounds [8, 9, 30, 14]. Following [8], Assumption 3 states
the target data covariance matrix is covered by the covariance matrices of the
source data distributions. We remark that this assumption allows the
covariance matrices to be different, in contrast to works [9, 10] that assume
a common covariance matrix for all the distributions. Assumption 4 (also made
in related works [32, 8, 9]) says that the head vectors corresponding to the
matrix $\mathbf{V}^{*}$ for each source model should span $\mathbb{R}^{l}$.
This effectively allows us to recover the representation $\mathbf{V}^{*}$
provided enough source machines ($m>l$) that individually capture one or more
features of $\mathbf{V}^{*}$. This assumption is also central to proving our
result in Lemma 1 provided below which show that the matrices
$\widehat{\mathbf{V}}$ and $\mathbf{V}^{*}$, whose columns form an orthonormal
basis for the span of $\\{\widehat{\mathbf{B}}_{i}\\}$ and
$\\{\mathbf{B}_{i}^{*}\\}$, respectively, span the same subspace for
constructing the target model.

###### Lemma 1

Let matrix $\widehat{\mathbf{V}}\in\mathbb{R}^{d\times q}$ be formed by
empirical source representations $\\{\widehat{\mathbf{B}}_{i}\\}$ obtained
from solving (3) and the matrix $\mathbf{V}^{*}\in\mathbb{R}^{d\times l}$
formed from the true representations $\\{\mathbf{B}_{i}^{*}\\}$. Under
Assumption 2-4, for any $\mathbf{b}\in\mathbb{R}^{l}$ such that
$\|\mathbf{b}\|_{2}=1$, $n_{s}\gg\rho^{4}(d+\log(\nicefrac{{m}}{{\delta}}))$
and $n_{T_{1}}\gg\rho^{4}(\max\\{l,q\\}+\log(\nicefrac{{1}}{{\delta}}))$, with
probability at-least $1-\delta_{1}$, we have:

$\displaystyle\min_{\mathbf{u}\in\mathbb{R}^{q}}\|\mathbf{X}_{T_{1}}\widehat{\mathbf{V}}\mathbf{u}-\mathbf{X}_{T_{1}}\mathbf{V}^{*}\mathbf{b}\|_{2}\leq\frac{\sigma^{2}n_{T_{1}}}{rn_{S}}\left(km+kdm\log(\kappa
n_{s})+\log\left(\frac{1}{\delta_{1}}\right)\right)$

A proof of the lemma above is provided in Section 5. We now state our main
result for the excess risk on after Phase 1.

######  Theorem 1 (Phase 1 training result)

Fix a failure probability $\delta\in(0,1)$ and further assume
$2k\leq\min\\{d,m\\}$ and the number of samples in the sources and target
satisfy $n_{s}\gg\rho^{4}(d+\log(\nicefrac{{m}}{{\delta}}))$ and
$n_{T_{1}}\gg\rho^{4}(\max\\{l,q\\}+\log(\nicefrac{{1}}{{\delta}}))$,
respectively. Define
$\kappa=\frac{\max_{i\in[m]}\lambda_{\max}(\Sigma_{i})}{\min_{i\in[m]}\lambda_{\min}(\Sigma_{i})}$
where $\lambda_{\max}(\Sigma_{i})$ denotes the maximum eigenvalue of
$\Sigma_{i}$. Then with probability at least $1-\delta$ over the samples,
under Assumptions 1 \- 5, the expected excess risk of
${\boldsymbol{\theta}}_{\text{Phase}_{1}}:=\widehat{\mathbf{V}}\widehat{\mathbf{w}}$
satisfies:

$\displaystyle\mathbb{E}[\text{EER}({\boldsymbol{\theta}}_{\text{Phase}_{1}},{\boldsymbol{\theta}}_{T}^{*})]\lesssim\frac{\sigma^{2}}{n_{T_{1}}}(q+\log(\nicefrac{{1}}{{\delta}}))+\epsilon^{2}+\sigma^{2}\left[\frac{1}{rn_{s}m}\log\left(\frac{1}{\delta}\right)+\left(\frac{kd\log(\kappa
n_{s})+k}{rn_{s}}\right)\right]$

where expectation is taken over $\widetilde{\mathbf{w}}_{T}^{*}$ for the
target task (c.f. Assumption 5). We provide proof for Theorem 1 in Section 5.

##### Discussion:

The bound in Theorem 1 shows the population risk of the learned model
${\boldsymbol{\theta}}_{\text{Phase}_{1}}$ lies in a ball centered at the true
target model risk $R({\boldsymbol{\theta}}_{T}^{*})$ with radius
$\epsilon^{2}$, which represents the _approximation error_ for using source
representations for the target task (see Assumption 1). Note that the expected
excess risk scales as $\mathcal{O}\left(\nicefrac{{q}}{{n_{T_{1}}}}\right)$
with respect to the number of target samples when the representation is
learned from the source representations. This demonstrates a sample gain
compared to the baseline of
$\mathcal{O}\left(\nicefrac{{d}}{{n_{T_{1}}}}\right)$ for learning the entire
model (including representation) with the target data when $q\ll d$, that is,
when the empirical source representations together span a subspace of
dimension much smaller than $d$. For the case when source and target
representations are all the same,
$\mathbf{B}_{T}^{*}=\mathbf{B}_{i}^{*}=\mathbf{B}^{*}\in\mathbb{R}^{d\times
k}$ for all $i\in[m]$, the excess risk scales as
$\mathcal{O}\left(\nicefrac{{k}}{{n_{T_{1}}}}\right)$, which recovers the
result of [8].

###  4.2 Theoretical results for overall scheme: Phase1 + Phase2

We require the following additional assumptions:

###### Assumption 6

The rows of the target data matrix $\mathbf{X}_{T}$ are linearly independent.

###### Assumption 7

The Gradient Descent procedure to optimize (6) converges to
${\boldsymbol{\theta}}_{\text{Phase}_{2}}$ with
$f({\boldsymbol{\theta}}_{\text{Phase}_{2}})=0$.

Assumption 6 is typically made in literature for analysis in the over-
parameterized regime for linear regression, see [14], and can also be relaxed
to hold with high probability instead and incorporated in the analysis [30].
Assumption 7 holds in our setting as the objective in (6) is strongly convex
and smooth for which GD can converge to the optimum [33].

######  Theorem 2 (Phase 1 + Phase 2 training result)

Consider obtaining the final target model by using $n_{T_{1}}$ samples during
Phase 1 for representation transfer and then fine-tuning in Phase 2 with
$n_{T_{2}}$ samples (independently drawn from Phase 1). Denote the eigenvalues
of the covariance matrix of the underlying data $\Sigma_{T}$ by
$\\{\lambda_{i}\\}_{i=1}^{d}$. Then under Assumptions 1-7, the excess risk of
the final parameter
$\hat{{\boldsymbol{\theta}}}_{T}:={\boldsymbol{\theta}}_{\text{Phase}_{2}}$ is
bounded as follows with probability at least $1-\delta$:

$\displaystyle\mathbb{E}[\text{EER}(\hat{{\boldsymbol{\theta}}}_{T},{\boldsymbol{\theta}}_{T}^{*})]$
$\displaystyle\lesssim\frac{\lambda_{1}}{\lambda_{d}}\frac{r_{0}(\Sigma_{T})}{n_{T_{2}}}\left(\frac{\sigma^{2}}{n_{T_{1}}}(q+\log(\nicefrac{{1}}{{\delta}}))+\epsilon^{2}\right)+r\sigma^{2}\log\left(\frac{1}{\delta}\right)\left(\frac{k^{*}}{n_{T_{2}}}+\frac{n_{T_{2}}}{R_{k^{*}}(\Sigma_{T})}\right)$
$\displaystyle\qquad+\frac{\lambda_{1}\sigma^{2}}{\lambda_{d}}\frac{r_{0}(\Sigma_{T})}{n_{T_{2}}}\left(\frac{1}{rn_{s}m}\log\left(\frac{1}{\delta}\right)+\left(\frac{kd\log(\kappa
n_{s})+k}{rn_{s}}\right)\right)$

where $r_{k}(\Sigma_{T})=\frac{\Sigma_{i>k}\lambda_{i}}{\lambda_{k+1}}$,
$R_{k^{*}}(\Sigma_{T})=\frac{(\Sigma_{i>k}\lambda_{i})^{2}}{\Sigma_{i>k}\lambda_{i}^{2}}$.
Here, constant $b>1$ and $k^{*}=\min\\{k\geq 0:r_{k}(\Sigma)\geq
bn_{T_{2}}\\}$ with $k^{*}\leq\frac{n_{T_{2}}}{c_{1}}$ for some universal
constant $c_{1}>1$.

We provide a proof for Theorem 2 in Section 6.

##### Discussion:

Theorem 2 shows the excess risk of our overall target model
($\hat{{\boldsymbol{\theta}}}_{T}={\boldsymbol{\theta}}_{\text{Phase}_{2}}$)
as a function of the number of samples $n_{S},n_{T_{1}},n_{T_{2}}$ and
parameters depending on the target data covariance matrix, $\Sigma_{T}$. Since
we re-train the entire model (including the representation) with $n_{T_{2}}$
target samples, the population risk of the learned model
$R({\boldsymbol{\theta}}_{\text{Phase}_{2}})$ can be made closer to the true
risk $R({\boldsymbol{\theta}}_{T}^{*})$ by increasing $n_{T_{2}}$, which is in
contrast to the result of Theorem 1 which shows closeness only in an
$\epsilon^{2}$ radius ball due to using source representation directly to
construct the target model.
We now provide a baseline comparison to the standard linear regression
scenario where we do no utilize any source models and instead learn the target
task model from scratch using the available $n_{T}=n_{T_{1}}+n_{T_{2}}$
samples. The excess risk in this setting is
$\mathcal{O}\left(\frac{\sigma^{2}d}{n_{T}}\right)$. If the number of source
samples are large enough ($n_{S}\gg d$) to get a good empirical performance on
the source models (c.f. Equation (3)), the bound from Theorem 2 demonstrates a
sample gain compared to the baseline when:

$\displaystyle\frac{\lambda_{1}}{\lambda_{d}}\frac{r_{0}(\Sigma_{T})}{n_{T_{2}}}\left(\frac{\sigma^{2}}{n_{T_{1}}}(q+\log(\nicefrac{{1}}{{\delta}}))+\epsilon^{2}\right)+c\sigma^{2}\log\left(\frac{1}{\delta}\right)\left(\frac{k^{*}}{n_{T_{2}}}+\frac{n_{T_{2}}}{R_{k^{*}}(\Sigma_{T})}\right)\ll\frac{\sigma^{2}d}{n_{T_{1}}+n_{T_{2}}}$
(8)

It can be seen that for the above relation to hold, we require:

  * •

The target data covariance matrix $\Sigma_{T}$ should be such that the term
$R_{k^{*}}(\Sigma_{T})$ is much larger than $n_{T_{2}}$, and $k^{*}\ll
n_{T_{2}}$. This is satisfied, for e.g., in the case when eigenvalues of
$\Sigma_{T}$ decay slowly from largest to smallest, and are all larger than a
small constant [14].

  * •

Using the definition of
$r_{0}({\Sigma_{T}})=\nicefrac{{\sum_{i=1}^{d}\lambda_{i}}}{{\lambda_{1}}}$,
and noting that $\nicefrac{{\sum_{i=1}^{d}\lambda_{i}}}{{\lambda_{d}}}<d$, the
following provides a sufficient condition the first term on the L.H.S. of (8):

$\displaystyle\frac{qd}{n_{T_{1}}n_{T_{2}}}\ll\frac{d}{n_{T_{1}}+n_{T_{2}}}$

This, is turn, imposes the following restriction on $q$, which is the
dimension of the subspace formed by the source representations
$\\{\widehat{\mathbf{B}}_{i}\\}$:

$\displaystyle q\ll\frac{n_{T_{1}}n_{T_{2}}}{n_{T_{1}}+n_{T_{2}}}$ (9)

Since $n_{T_{1}}+n_{T_{2}}=n_{T}$, it is easy to check that the R.H.S. of (9)
is maximized when $n_{T_{1}}=n_{T_{2}}=\nicefrac{{n}}{{2}}$. With this optimal
splitting of the target samples for each of the phases, we require
$q\ll\nicefrac{{n_{T}}}{{2}}$ for the inequality in (8).

##  5 Proof for Phase 1 training

We now provide the proof for Theorem 1 which establishes a generalization
bound for the learned model formed by leveraging the pre-trained source
models.
We first note the following results from [8] that will enable us to prove
Theorem 1 later in Section 5.2 (and Theorem 2 in Section 6).

######  Claim 1 (Covariance of Source distribution, Claim A.1 of [8])

Suppose $n_{s}\gg\rho^{4}(d+\log(\nicefrac{{m}}{{\delta}}))$ for
$\delta\in(0,1)$. Then with probability at least $1-\frac{\delta}{10}$ over
the inputs $\mathbf{X}_{1},\ldots,\mathbf{X}_{m}$ in the source tasks, for all
$i\in[m]$ we have

$0.9\boldsymbol{\Sigma}_{i}\preceq\frac{1}{n_{s}}\mathbf{X}_{i}^{\top}\mathbf{X}_{i}\preceq
1.1\boldsymbol{\Sigma}_{i}$

######  Claim 2 (Covariance Target distribution, Claim A.2 of [8])

Suppose $n_{T}\gg\rho^{4}(k+\log(\nicefrac{{1}}{{\delta}}))$ for
$\delta\in(0,1)$. The for any given matrix $\mathbf{B}\in\mathbb{R}^{d\times
2k}$ that is independent of $\mathbf{X}_{T}$, with probability at least
$1-\frac{\delta}{20}$ over target data $X_{T}$, we have

$0.9\mathbf{B}^{\top}\boldsymbol{\Sigma}_{T}\mathbf{B}\preceq\frac{1}{n_{T}}\mathbf{B}^{\top}\mathbf{X}_{T}^{\top}\mathbf{X}_{T}\mathbf{B}\preceq
1.1\mathbf{B}^{\top}\boldsymbol{\Sigma}_{T}\mathbf{B}$

######  Proposition 1 (Lemma A.7 from [8])

For matrices $\mathbf{A}_{1},\mathbf{A}_{2}$ (with same number of columns)
such that
$\mathbf{A}_{1}^{\top}\mathbf{A}_{1}\succeq\mathbf{A}_{2}^{\top}\mathbf{A}_{2}$
and for matrices $\mathbf{B}_{1},\mathbf{B}_{2}$ of compatible dimensions, we
have:

$\left\|\mathbf{P}^{\perp}_{\mathbf{A}_{1}\mathbf{B}_{1}}\mathbf{A}_{1}\mathbf{B}_{2}\right\|_{F}^{2}\geq\left\|\mathbf{P}^{\perp}_{\mathbf{A}_{2}\mathbf{B}_{1}}\mathbf{A}_{2}\mathbf{B}_{2}\right\|_{F}^{2}$

###### Proposition 2

Consider matrices $\mathbf{A}\in\mathbb{R}^{a\times b}$ and
$\mathbf{B}\in\mathbb{R}^{b\times c}$. Then for any
$\mathbf{u}\in\mathbb{R}^{a}$, we have:

$\|\mathbf{P}^{\perp}_{\mathbf{A}}\mathbf{u}\|_{2}^{2}\leq\|\mathbf{P}^{\perp}_{\mathbf{A}\mathbf{B}}\mathbf{u}\|_{2}^{2}$

Proof: For given $\mathbf{A}\in\mathbb{R}^{a\times b}$ and
$\mathbf{B}\in\mathbb{R}^{b\times c}$ and $\mathbf{u}\in\mathbb{R}^{a}$, we
have:

$\displaystyle\|\mathbf{P}^{\perp}_{\mathbf{A}}\mathbf{u}\|_{2}^{2}$
$\displaystyle=\min_{\mathbf{r}\in\mathbb{R}^{b}}\|\mathbf{A}\mathbf{r}-\mathbf{u}\|_{2}^{2}$
$\displaystyle\leq\min_{\mathbf{r}\in\mathcal{C}(\mathbf{B})}\|\mathbf{A}\mathbf{r}-\mathbf{u}\|_{2}^{2}$
$\displaystyle=\min_{\mathbf{s}\in\mathbb{R}^{c}}\|\mathbf{A}\mathbf{B}\mathbf{s}-\mathbf{u}\|_{2}^{2}$
$\displaystyle=\|\mathbf{P}^{\perp}_{\mathbf{A}\mathbf{B}}\mathbf{u}\|_{2}^{2}$

$\square$

###  5.1 Some important results

We now provide proof of results used to establish the resulting bound for
Phase 1 training provided in Theorem 1, which is proved later in Section 5.2.
These results provide guarantees on empirical training of the source models
(c.f. Lemma 2) as well as the performance of empirically learned source
representations on the target data (c.f. Lemma 1).
These results would also be useful for the proof of Theorem 2 presented later
in Section 6.

####  5.1.1 Proof of Lemma 1

We first prove Lemma 1 which establishes a bound on using the learned
empirical representation $\widehat{\mathbf{V}}$ on the target data.

[Restating Lemma 1] Consider the matrix
$\widehat{\mathbf{V}}\in\mathbb{R}^{d\times q}$ formed by empirical source
representations $\\{\widehat{\mathbf{B}}_{i}\\}$ obtained from solving (3) and
the matrix $\mathbf{V}^{*}\in\mathbb{R}^{d\times l}$ formed from the true
representations $\\{\mathbf{B}_{i}^{*}\\}$. For any
$\mathbf{b}\in\mathbb{R}^{l}$ such that $\|\mathbf{b}\|_{2}=1$, with
probability at-least $1-\delta_{1}$, we have:

$\displaystyle\min_{\mathbf{u}\in\mathbb{R}^{q}}\|\mathbf{X}_{T}\widehat{\mathbf{V}}\mathbf{u}-\mathbf{X}_{T}\mathbf{V}^{*}\mathbf{b}\|_{2}\leq\frac{\sigma^{2}n_{T}}{rn_{S}}\left(km+kdm\log(\kappa
n_{s})+\log\left(\frac{1}{\delta_{1}}\right)\right)$

Proof: We first note that:

$\displaystyle\|\mathbf{P}^{\perp}_{\mathbf{X}_{T}\widehat{\mathbf{V}}}\mathbf{X}_{T}\mathbf{V}^{*}\mathbf{b}\|_{2}:=\min_{\mathbf{u}\in\mathbb{R}^{q}}\|\mathbf{X}_{T}\widehat{\mathbf{V}}\mathbf{u}-\mathbf{X}_{T}\mathbf{V}^{*}\mathbf{b}\|_{2}$

Using the fact that $\\{\widetilde{\mathbf{w}}_{i}\\}$ span the space
$\mathbb{R}^{l}$, we can write
$\mathbf{b}=\widetilde{\mathbf{W}}^{*}\boldsymbol{\alpha}$ for some
$\boldsymbol{\alpha}\in\mathbb{R}^{m}$ where $\boldsymbol{\alpha}$ is
$\mathcal{O}(1)$. We have:

$\displaystyle\|\mathbf{P}^{\perp}_{\mathbf{X}_{T}\widehat{\mathbf{V}}}\mathbf{X}_{T}\mathbf{V}^{*}\mathbf{b}\|_{2}^{2}$
$\displaystyle=\|\mathbf{P}^{\perp}_{\mathbf{X}_{T}\widehat{\mathbf{V}}}\mathbf{X}_{T}\mathbf{V}^{*}\widetilde{\mathbf{W}}^{*}\boldsymbol{\alpha}\|_{2}^{2}$
$\displaystyle\lesssim\|\mathbf{P}^{\perp}_{\mathbf{X}_{T}\widehat{\mathbf{V}}}\mathbf{X}_{T}\mathbf{V}^{*}\widetilde{\mathbf{W}}^{*}\|_{F}^{2}$
$\displaystyle=\sum_{i=1}^{m}\|\mathbf{P}^{\perp}_{\mathbf{X}_{T}\widehat{\mathbf{V}}}\mathbf{X}_{T}\mathbf{V}^{*}\widetilde{\mathbf{w}}^{*}_{i}\|_{2}^{2}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\lesssim}}n_{T}\sum_{i=1}^{m}\|\mathbf{P}^{\perp}_{\boldsymbol{\Sigma}_{T}^{\nicefrac{{1}}{{2}}}\widehat{\mathbf{V}}}\boldsymbol{\Sigma}_{T}^{\nicefrac{{1}}{{2}}}\mathbf{V}^{*}\widetilde{\mathbf{w}}^{*}_{i}\|_{2}^{2}$
(10)
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\lesssim}}\frac{n_{T}}{r}\sum_{i=1}^{m}\|\mathbf{P}^{\perp}_{\boldsymbol{\Sigma}_{i}^{\nicefrac{{1}}{{2}}}\widehat{\mathbf{V}}}\boldsymbol{\Sigma}_{i}^{\nicefrac{{1}}{{2}}}\mathbf{V}^{*}\widetilde{\mathbf{w}}^{*}_{i}\|_{2}^{2}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\lesssim}}\frac{n_{T}}{rn_{S}}\sum_{i=1}^{m}\|\mathbf{P}^{\perp}_{\mathbf{X}_{i}\widehat{\mathbf{V}}}\mathbf{X}_{i}\mathbf{V}^{*}\widetilde{\mathbf{w}}^{*}_{i}\|_{2}^{2}$

where $(a)$ follows from Claim 2 (with
$\mathbf{B}=[\widehat{\mathbf{V}}\quad-\mathbf{V}^{*}]$), $(b)$ follows from
Assumption 3 and $(c)$ from Claim 1. We now note that
$\mathbf{V}^{*}\widetilde{\mathbf{w}}^{*}_{i}=\mathbf{B}_{i}^{*}\mathbf{w}_{i}^{*}$.
We now note that $\widehat{\mathbf{V}}$ is the matrix whose columns are an
orthonormal basis of the set of columns of the matrices
$\\{\widehat{\mathbf{B}}_{i}\\}$. Thus for each $i\in[m]$, there exists a
matrix $\mathbf{C}_{i}$ such that
$\widehat{\mathbf{B}}_{i}=\widehat{\mathbf{V}}\mathbf{C}_{i}$. Now using the
result of Proposition 2 we have:

$\displaystyle\|\mathbf{P}^{\perp}_{\mathbf{X}_{T}\widehat{\mathbf{V}}}\mathbf{X}_{T}\mathbf{V}^{*}\mathbf{b}\|_{2}^{2}\stackrel{{\scriptstyle
Prop.~{}\ref{prop:mat_cols}}}{{\lesssim}}\frac{n_{T}}{rn_{s}}\sum_{i=1}^{m}\left\|\mathbf{P}^{\perp}_{\mathbf{X}_{i}\widehat{\mathbf{B}}_{i}}\mathbf{X}_{i}\mathbf{B}_{i}^{*}\mathbf{w}_{i}^{*}\right\|_{2}^{2}$
$\displaystyle\qquad\leq\frac{n_{T}}{rn_{s}}\sum_{i=1}^{m}\left\|\mathbf{P}_{\mathbf{X}_{i}\widehat{\mathbf{B}}_{i}}(\mathbf{X}_{i}\mathbf{B}_{i}^{*}\mathbf{w}_{i}^{*}+\mathbf{z}_{i})-\mathbf{X}_{i}\mathbf{B}_{i}^{*}\mathbf{w}_{i}^{*}\right\|_{2}^{2}$
$\displaystyle\qquad=\frac{n_{T}}{rn_{s}}\sum_{i=1}^{m}\left\|\mathbf{P}_{\mathbf{X}_{i}\widehat{\mathbf{B}}_{i}}\mathbf{y}_{i}-\mathbf{X}_{i}\mathbf{B}_{i}^{*}\mathbf{w}_{i}^{*}\right\|_{2}^{2}$
$\displaystyle\qquad=\frac{n_{T}}{rn_{s}}\sum_{i=1}^{m}\left\|\mathbf{X}_{i}\widehat{\mathbf{B}}_{i}\widehat{\mathbf{w}}_{i}-\mathbf{X}_{i}\mathbf{B}_{i}^{*}\mathbf{w}_{i}^{*}\right\|_{2}^{2}$

The proof can then be concluded by using the result from Lemma 2 stated below
that provides a bound for the trained empirical source models in (3).
$\square$

The following lemma establishes guarantees on the learned empirical source
representations.

######  Lemma 2 (Multi-Source training guarantee)

With probability at least $1-\frac{\delta}{5}$, we have:

$\displaystyle\sum_{i=1}^{m}\left\|\mathbf{X}_{i}(\widehat{\mathbf{B}}_{i}\widehat{\mathbf{w}}_{i}-\mathbf{B}_{i}^{*}\mathbf{w}_{i}^{*})\right\|_{2}^{2}\leq\sigma^{2}\left(km+kdm\log(\kappa
n_{s})+\log\left(\frac{1}{\delta}\right)\right)$

Proof: First we instantiate Claim 1, which happens with probability atleast
$1-\frac{\delta}{10}$. For the given source datasets and matrix
$\mathbf{A}\in\mathbb{R}^{d\times m}$ with columns $\\{\mathbf{a}_{i}\\}$, we
define the map $\mathcal{X}(\mathbf{A})$ as
$\mathcal{X}(\mathbf{A})=[\mathbf{X}_{1}\mathbf{a}_{1}\quad\mathbf{X}_{2}\mathbf{a}_{2}\ldots\quad\mathbf{X}_{m}\mathbf{a}_{m}]$.
Now consider the matrix
$\boldsymbol{\boldsymbol{\Delta}}\in\mathbb{R}^{d\times m}$ whose columns are
given by
$\\{\widehat{\mathbf{B}}_{i}\widehat{\mathbf{w}}_{i}-\mathbf{B}^{*}_{i}\mathbf{w}^{*}_{i}\\}_{i=1}^{m}$.
For convenience of notation, we define
$\mathcal{X}(\mathbf{\boldsymbol{\Delta}}):=[\mathbf{X}_{1}(\widehat{\mathbf{B}}_{1}\widehat{\mathbf{w}}_{1}-\mathbf{B}^{*}_{1}\mathbf{w}^{*}_{1})\quad\ldots\quad\mathbf{X}_{m}(\widehat{\mathbf{B}}_{m}\widehat{\mathbf{w}}_{m}-\mathbf{B}^{*}_{m}\mathbf{w}^{*}_{m})]$.
We are interested in providing a bound for the quantity
$\|\mathcal{X}(\mathbf{\boldsymbol{\Delta}})\|_{F}^{2}$. The $i^{th}$ column
of the matrix $\boldsymbol{\boldsymbol{\Delta}}$ can be decomposed as
$\mathbf{R}_{i}\mathbf{r}_{i}$ where $\mathbf{R}_{i}\in\mathcal{O}_{d\times
2k}$ (set of tall orthonormal matrices in $d\times 2k$) and
$\mathbf{r}_{i}\in\mathbb{R}^{2k}$.

$\displaystyle\boldsymbol{\boldsymbol{\Delta}}=[\mathbf{R}_{1}\mathbf{r}_{1}\quad\mathbf{R}_{2}\mathbf{r}_{2}\ldots\quad\mathbf{R}_{m}\mathbf{r}_{m}]$

For each $i\in[m]$, we now decompose
$\mathbf{X}_{i}\mathbf{R}_{i}=\mathbf{U}_{i}\mathbf{Q}_{i}$ (where
$\mathbf{U}_{i}\in\mathcal{O}_{n_{s}\times 2k}$ and
$\mathbf{Q}\in\mathbb{R}^{2k\times 2k}$). Since
$\\{\widehat{\mathbf{B}}_{i},\widehat{\mathbf{w}}_{i}\\}_{i=1}^{m}$ are the
optimal solutions for the source regression problems, we have
$\sum_{i=1}^{m}\|\mathbf{y}_{i}-\mathbf{X}_{i}\widehat{\mathbf{B}}_{i}\widehat{\mathbf{w}}_{i}\|_{2}^{2}\leq\sum_{i=1}^{m}\|\mathbf{y}_{i}-\mathbf{X}_{i}\mathbf{B}_{i}^{*}\mathbf{w}_{i}^{*}\|_{2}^{2}$.
Substituting
$\mathbf{y}_{i}=\mathbf{X}_{i}\mathbf{B}_{i}^{*}\mathbf{w}_{i}^{*}+\mathbf{z}_{i}$
for $i\in[m]$, we get
$\|\mathcal{X}(\boldsymbol{\boldsymbol{\Delta}})\|_{F}^{2}\leq
2\left\langle\mathbf{Z},\mathcal{X}(\boldsymbol{\boldsymbol{\Delta}})\right\rangle$
(where the inner product of matrices is trace of their product) and we denote
the matrix of noise vectors as
$\mathbf{Z}:=[\mathbf{z}_{1}\quad\mathbf{z}_{2}\quad\ldots\quad\mathbf{z}_{m}]\in\mathbb{R}^{n_{s}\times
m}.$ Now:

$\displaystyle\left\langle\mathbf{Z},\mathcal{X}(\boldsymbol{\boldsymbol{\Delta}})\right\rangle$
$\displaystyle=\sum_{i=1}^{m}\mathbf{z}_{i}^{\top}\mathbf{X}_{i}\mathbf{R}_{i}\mathbf{r}_{i}=\sum_{i=1}^{m}\mathbf{z}_{i}^{\top}\mathbf{U}_{i}\mathbf{Q}_{i}\mathbf{r}_{i}$
(11)
$\displaystyle\leq\sum_{i=1}^{m}\left\|\mathbf{U}_{i}^{\top}\mathbf{z}_{i}\right\|_{2}\left\|\mathbf{Q}_{i}\mathbf{r}_{i}\right\|_{2}$
$\displaystyle\leq\sqrt{\sum_{i=1}^{m}\left\|\mathbf{U}_{i}^{\top}\mathbf{z}_{i}\right\|_{2}}\sqrt{\sum_{i=1}^{m}\left\|\mathbf{U}_{i}\mathbf{Q}_{i}\mathbf{r}_{i}\right\|_{2}}$
$\displaystyle=\sqrt{\sum_{i=1}^{m}\left\|\mathbf{U}_{i}^{\top}\mathbf{z}_{i}\right\|_{2}}\,\,\|\mathcal{X}(\boldsymbol{\Delta})\|_{F}$
(12)

We will now provide a bound for the first term in the product on the R.H.S. of
(12). Since $\mathbf{U}_{i}$ depends on $\mathbf{R}_{i}$, it also depends on
the value of $\mathbf{Z}$. To provide a bound, we use an $\epsilon$-net
argument to cover all possible values of $\\{\mathbf{R}_{i}\\}_{i=1}^{m}$. We
first consider a fixed set of matrices
$\\{\bar{\mathbf{R}}_{i}\\}_{i=1}^{m}\subset\mathcal{O}_{d\times 2k}^{m}$. For
these given matrices, we can find decompose
$\mathbf{X}_{i}\bar{\mathbf{R}}_{i}=\bar{\mathbf{U}}_{i}\mathbf{Q}_{i}$ for
$i\in[m]$, where
$\\{\bar{\mathbf{U}}_{i}\\}_{i=1}^{m}\subset\mathcal{O}_{n_{T}\times 2k}^{m}$
do not depend on $\mathbf{Z}$. Thus we have
$\frac{1}{\sigma^{2}}\sum_{i=1}^{m}\left\|\mathbf{U}_{i}^{\top}\mathbf{z}_{i}\right\|_{2}\sim\chi^{2}(2km)$.
Thus w.p at least $1-\delta^{\prime}$, we have:

$\sum_{i=1}^{m}\left\|\mathbf{U}_{i}^{\top}\mathbf{z}_{i}\right\|_{2}\lesssim\sigma^{2}\left(km+\log\left(\frac{1}{\delta^{\prime}}\right)\right)$
(13)

Hence for the given $\\{\bar{\mathbf{R}}_{i}\\}_{i=1}^{m}$, using the result
from (13) in (12), we have:

$\left\langle\mathbf{Z},\mathcal{X}(\boldsymbol{\bar{\boldsymbol{\Delta}}})\right\rangle\lesssim\sigma^{2}\left(km+\log\left(\frac{1}{\delta^{\prime}}\right)\right)\|\mathcal{X}(\bar{\boldsymbol{\Delta}})\|_{F}$

where
$\bar{\boldsymbol{\Delta}}=[\bar{\mathbf{R}}_{1}\mathbf{r}_{1}\quad\bar{\mathbf{R}}_{2}\mathbf{r}_{2}\ldots\quad\bar{\mathbf{R}}_{m}\mathbf{r}_{m}]$.
Now we consider an $\frac{\epsilon}{m}$-net of $\mathcal{O}_{d\times 2k}^{m}$
denoted by $\mathcal{N}$ of size
$|\mathcal{N}|\leq\left(\frac{6m\sqrt{2k}}{\epsilon}\right)^{2kdm}.$ Using the
union bound, with probability at least $1-|\mathcal{N}|\delta^{\prime}$:

$\left\langle\mathbf{Z},\mathcal{X}(\boldsymbol{\bar{\boldsymbol{\Delta}}})\right\rangle{\lesssim}\sigma^{2}\left(km{+}\log\left(\frac{1}{\delta^{\prime}}\right)\right)\|\mathcal{X}(\bar{\boldsymbol{\Delta}})\|_{F},\,\forall\\{\bar{\mathbf{R}}_{i}\\}_{i=1}^{m}\subset\mathcal{N}$
(14)

Choose
$\delta^{\prime}=\frac{\delta}{20\left(\frac{6m\sqrt{2k}}{\epsilon}\right)^{2kdm}}$,
then the above holds with probability at least $1-\frac{\delta}{20}$. We will
now use the results from the following claim, which is proved in Section 5.1.2
below.

###### Claim 3

Under the assumptions of Theorem 1, the following hold:

  1. 1.

W.p at least $1-\frac{\delta}{20}$,
$\|\mathbf{Z}\|_{F}^{2}\lesssim\sigma^{2}\left(n_{s}m+\log\left(\frac{1}{\delta}\right)\right)$

  2. 2.

If the result in 1) holds and Claim 1 holds , then
$\|\boldsymbol{\Delta}\|_{F}^{2}\lesssim\frac{\sigma^{2}(n_{s}m+\log(\frac{1}{\delta}))}{n_{s}\lambda_{low}}$
where $\lambda_{low}=\min_{i\in[m]}\lambda_{\min}(\boldsymbol{\Sigma}_{i})$

  3. 3.

If the results in 1), 2) above hold and Claim 1 holds, then
$\|\mathcal{X}([\mathbf{R}_{1}\mathbf{r}_{1}\quad\ldots\mathbf{R}_{m}\mathbf{r}_{m}]-[\bar{\mathbf{R}}_{1}\mathbf{r}_{1}\quad\ldots\bar{\mathbf{R}}_{m}\mathbf{r}_{m}])\|\lesssim\frac{\kappa\epsilon^{2}}{m^{2}}\sigma^{2}\left(n_{s}m+\log\left(\frac{1}{\delta}\right)\right)$
for some $\\{\bar{\mathbf{R}}_{i}\\}\subset\mathcal{N}$ where
$\kappa=\frac{\max_{i\in[m]}\lambda_{\min}(\boldsymbol{\Sigma}_{i})}{\min_{i\in[m]}\lambda_{\min}(\boldsymbol{\Sigma}_{i})}$

We now use the results of the Claim 3 to complete the proof of the lemma. We
note that there exists some $\bar{\boldsymbol{\Delta}}$ with
$\\{\bar{\mathbf{R}}_{i}\\}_{i=1}^{m}\subset\mathcal{N}$ such that:

$\displaystyle\frac{1}{2}\|\mathcal{X}(\boldsymbol{\Delta})\|_{F}^{2}\leq\left\langle\mathbf{Z},\mathcal{X}(\boldsymbol{\Delta})\right\rangle$
$\displaystyle=\left\langle\mathbf{Z},\mathcal{X}(\bar{\boldsymbol{\Delta}})\right\rangle+\left\langle\mathbf{Z},\mathcal{X}(\boldsymbol{\Delta}-\bar{\boldsymbol{\Delta}})\right\rangle$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\lesssim}}\sigma\sqrt{\left(km+\log\left(\frac{1}{\delta^{\prime}}\right)\right)}.\|\mathcal{X}(\bar{\boldsymbol{\Delta}})\|_{F}^{2}+\|\mathbf{Z}\|_{F}\|\mathcal{X}(\boldsymbol{\Delta}{-}\bar{\boldsymbol{\Delta}})\|_{F}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\sigma\sqrt{\left(km+\log\left(\frac{1}{\delta^{\prime}}\right)\right)}.\left(\|\mathcal{X}(\boldsymbol{\Delta})\|_{F}+\|\mathcal{X}(\boldsymbol{\Delta}{-}\bar{\boldsymbol{\Delta}})\|_{F}\right)+\sigma\sqrt{\left(n_{s}m{+}\log\left(\frac{1}{\delta}\right)\right)}\|\mathcal{X}(\boldsymbol{\Delta}-\bar{\boldsymbol{\Delta}})\|_{F}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\lesssim}}\sigma\|\mathcal{X}(\boldsymbol{\Delta})\|_{F}\sqrt{\left(km+\log\left(\frac{1}{\delta^{\prime}}\right)\right)}+\frac{\sqrt{\kappa}\epsilon}{m}\sigma^{2}\left(n_{s}m+\log\left(\frac{1}{\delta^{\prime}}\right)\right)$

where $(a)$ follows from (14) w.p $\geq 1-\frac{\delta}{20}$, $(b)$ from 1) in
Claim 3); w.p. $\geq 1-\frac{\delta}{20}$ and $(c)$ uses the fact that
$\delta^{\prime}<\delta,k\leq n_{s}$, and 3) in Claim 3. Since the above
result gives an inequality in terms of
$\|\mathcal{X}(\boldsymbol{\Delta})\|_{F}^{2}$ and
$\|\mathcal{X}(\boldsymbol{\Delta})\|_{F}$, we can conclude the following:

$\displaystyle\|\mathcal{X}(\boldsymbol{\Delta})\|_{F}\lesssim\max$
$\displaystyle\left\\{\sigma\sqrt{\left(km+\log\left(\frac{1}{\delta^{\prime}}\right)\right)},\sigma\sqrt{\frac{\sqrt{\kappa}\epsilon}{m}\left(n_{s}m+\log\left(\frac{1}{\delta^{\prime}}\right)\right)}\right\\}$

We choose $\epsilon=\frac{km}{n_{s}\sqrt{\kappa}}$, and note that $n_{S}\gg
k$, which gives:

$\displaystyle\|\mathcal{X}(\boldsymbol{\Delta})\|_{F}$
$\displaystyle\leq\sigma\sqrt{\left(km+\log\left(\frac{1}{\delta^{\prime}}\right)\right)}$

Substituting the value of
$\delta^{\prime}=\frac{\delta}{20\left(\frac{6m\sqrt{2k}}{\epsilon}\right)^{2kdm}}$
and $\epsilon=\frac{km}{n_{s}\sqrt{\kappa}}$:

$\displaystyle\|\mathcal{X}(\boldsymbol{\Delta})\|_{F}$
$\displaystyle\lesssim\sigma\sqrt{km+kdm\log\left(\frac{mk}{\epsilon}\right)+\log\left(\frac{1}{\delta}\right)}$
$\displaystyle\leq\sigma\sqrt{km+kdm\log\left(n_{s}\kappa\right)+\log\left(\frac{1}{\delta}\right)}$

Hence the following holds with probability at least 1 -
$\left(\frac{\delta}{10}+\frac{\delta}{20}+\frac{\delta}{20}\right)$:

$\displaystyle\|\mathcal{X}(\boldsymbol{\Delta})\|_{F}^{2}\lesssim\sigma^{2}\left[km+kdm\log\left(n_{s}\kappa\right)+\log\left(\frac{1}{\delta}\right)\right]$

$\square$

####  5.1.2 Proof of Claim 3

  1. 1.

This follows from the fact that
$\frac{1}{\sigma^{2}}\|\mathbf{Z}\|_{F}^{2}\sim\chi(n_{s}m)$

  2. 2.

$\displaystyle\|\mathcal{X}$
$\displaystyle(\boldsymbol{\Delta})\|_{F}^{2}=\sum_{i=1}^{m}\|\mathbf{X}_{i}(\widehat{\mathbf{B}}_{i}\widehat{\mathbf{w}}_{i_{0}}-\mathbf{B}^{*}_{i}\mathbf{w}_{i}^{*})\|_{2}^{2}$
$\displaystyle=\sum_{i=1}^{m}(\widehat{\mathbf{B}}_{i}\widehat{\mathbf{w}}_{i_{0}}-\mathbf{B}^{*}_{i}\mathbf{w}_{i}^{*})^{\top}\mathbf{X}_{i}^{\top}\mathbf{X}_{i}(\widehat{\mathbf{B}}_{i}\widehat{\mathbf{w}}_{i_{0}}-\mathbf{B}^{*}_{i}\mathbf{w}_{i}^{*})$
$\displaystyle\gtrsim
n_{s}\sum_{i=1}^{m}(\widehat{\mathbf{B}}_{i}\widehat{\mathbf{w}}_{i_{0}}-\mathbf{B}^{*}_{i}\mathbf{w}_{i}^{*})^{\top}\boldsymbol{\Sigma}_{i}(\widehat{\mathbf{B}}_{i}\widehat{\mathbf{w}}_{i_{0}}-\mathbf{B}^{*}_{i}\mathbf{w}_{i}^{*})$
$\displaystyle\geq
n_{s}\sum_{i=1}^{m}\lambda_{\min}(\boldsymbol{\Sigma}_{i})\|(\widehat{\mathbf{B}}_{i}\widehat{\mathbf{w}}_{i_{0}}-\mathbf{B}^{*}_{i}\mathbf{w}_{i}^{*})\|_{2}^{2}$
$\displaystyle\geq n_{s}\lambda_{low}\|\boldsymbol{\Delta}\|_{F}^{2}$

where $\lambda_{low}:=\min_{i\in[m]}\lambda_{\min}(\boldsymbol{\Sigma}_{i})$.
Since $\|\mathcal{X}(\boldsymbol{\Delta})\|_{F}^{2}\leq
2\left\langle\mathbf{Z},\mathcal{X}(\boldsymbol{\Delta})\right\rangle\leq
2\|\mathbf{Z}\|_{F}\|\mathcal{X}(\boldsymbol{\Delta})\|_{F}$, we have
$\|\mathcal{X}(\boldsymbol{\Delta})\|_{F}\leq 2\|\mathbf{Z}\|_{F}$. Using the
result from part 1. of the claim statement combined with the upper bound
derived above, we have:

$\displaystyle\|\boldsymbol{\Delta}\|_{F}^{2}\lesssim\frac{\sigma^{2}}{n_{s}\lambda_{low}}\left(n_{s}m+\log\left(\frac{1}{\delta}\right)\right)$

  3. 3.

For some $\\{\bar{\mathbf{R}}_{i}\\}\subset\mathcal{N}$ we have
$\sum_{i=1}^{m}\|\mathbf{R}_{i}-\bar{\mathbf{R}}_{i}\|_{F}\leq\sum_{i=1}^{m}\frac{\epsilon}{m}=\epsilon$.
Therefore:

$\displaystyle\|\mathcal{X}(\boldsymbol{\Delta}{-}\bar{\boldsymbol{\Delta}})\|_{F}^{2}$
$\displaystyle=\sum_{i=1}^{m}\|\mathbf{X}_{i}(\mathbf{R}_{i}-\bar{\mathbf{R}}_{i})\mathbf{r}_{i}\|_{2}^{2}$
$\displaystyle\leq\sum_{i=1}^{m}\|\mathbf{X}_{i}\|_{2}^{2}\|\mathbf{R}_{i}-\bar{\mathbf{R}}_{i}\|_{F}^{2}\|\mathbf{r}_{i}\|_{2}^{2}$
$\displaystyle\lesssim\frac{n_{s}\epsilon^{2}}{m^{2}}\sum_{i=1}^{m}\|\boldsymbol{\Sigma}_{i}\|_{2}^{2}\|\mathbf{r}_{i}\|_{2}^{2}$
$\displaystyle\lesssim\frac{n_{s}\epsilon^{2}\lambda_{high}}{m^{2}}\sum_{i=1}^{m}\|\mathbf{r}_{i}\|_{2}^{2}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\frac{n_{s}\epsilon^{2}\lambda_{high}}{m^{2}}\|\boldsymbol{\Delta}\|_{F}^{2}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\lesssim}}\frac{n_{s}\epsilon^{2}\lambda_{high}}{m^{2}}\frac{\sigma^{2}(n_{s}m+\log(\frac{1}{\delta}))}{n_{s}\lambda_{low}}$
$\displaystyle=\frac{\kappa\epsilon^{2}\lambda_{high}\sigma^{2}}{m^{2}\lambda_{low}}\left(n_{s}m+\log\left(\frac{1}{\delta}\right)\right)$

Here, $\lambda_{high}:=\max_{i\in[m]}\lambda_{\max}(\boldsymbol{\Sigma}_{i})$
where to arrive at $(a)$, we have used the fact that $\\{\mathbf{R}_{i}\\}$
have orthonormal columns and used the definition of $\boldsymbol{\Delta}$, and
$(b)$ follows from using 2) from the claim statement.

###  5.2 Proof of Theorem 1

Having established the helper results above, we now provide a proof for
Theorem 1.

[Restating Theorem 1] Fix a failure probability $\delta\in(0,1)$ and further
assume $2k\leq\min\\{d,m\\}$ and the number of samples in the sources and
target satisfy $n_{s}\gg\rho^{4}(d+\log(\nicefrac{{m}}{{\delta}}))$ and
$n_{T_{1}}\gg\rho^{4}(\max\\{l,q\\}+\log(\nicefrac{{1}}{{\delta}}))$,
respectively. Define
$\kappa=\frac{\max_{i\in[m]}\lambda_{\max}(\boldsymbol{\Sigma}_{i})}{\min_{i\in[m]}\lambda_{\min}(\boldsymbol{\Sigma}_{i})}$
where $\lambda_{\max}(\boldsymbol{\Sigma}_{i})$ denotes the maximum eigenvalue
of $\boldsymbol{\Sigma}_{i}$. Then with probability at least $1-\delta$ over
the samples, under Assumptions 1 \- 5, the expected excess risk of the learned
predictor $\widehat{\mathbf{w}}_{T}$ on the target
($\mathbf{x}\rightarrow\mathbf{x}^{\top}\widehat{\mathbf{V}}\widehat{\mathbf{w}}_{T}$)
for Phase 1 satisfies:

$\displaystyle\mathbb{E}[\text{EER}({\boldsymbol{\theta}}_{\text{Phase}_{1}},{\boldsymbol{\theta}}_{T}^{*})]\lesssim\frac{\sigma^{2}}{n_{T_{1}}}(q+\log(\nicefrac{{1}}{{\delta}}))+\epsilon^{2}+\sigma^{2}\left[\frac{1}{rn_{s}m}\log\left(\frac{1}{\delta}\right)+\left(\frac{kd\log(\kappa
n_{s})+k}{rn_{s}}\right)\right]$

Proof: We will first instantiate Lemma 1. We then instantiate Lemma 2 twice,
once with $[\widehat{\mathbf{V}}\,\,-\mathbf{V}^{*}]$ and the other time with
$[\mathbf{B}_{T}^{*}\,\,-\mathbf{V}^{*}]$. Then we assume that the result from
Lemma 2 holds. All these events happen together with probability at least
$1-\frac{2\delta}{5}$. The expected error for the target distribution is given
by:

$\displaystyle\text{EER}({\boldsymbol{\theta}}_{\text{Phase}_{1}},{\boldsymbol{\theta}}_{T}^{*})=\mathbb{E}_{\mathbf{x}\sim
p_{T}}\left[\mathbf{x}^{\top}\mathbf{B}_{T}^{*}\mathbf{w}_{T}^{*}-\mathbf{x}^{\top}\widehat{\mathbf{V}}\widehat{\mathbf{w}}_{T}\right]^{2}$
$\displaystyle=\left\|\boldsymbol{\Sigma}_{T}^{\nicefrac{{1}}{{2}}}\left(\widehat{\mathbf{V}}\widehat{\mathbf{w}}_{T}-\mathbf{B}_{T}^{*}\mathbf{w}_{T}^{*}\right)\right\|_{2}^{2}$
$\displaystyle\lesssim\left\|\boldsymbol{\Sigma}_{T}^{\nicefrac{{1}}{{2}}}\left(\widehat{\mathbf{V}}\widehat{\mathbf{w}}_{T}-\mathbf{V}^{*}\widetilde{\mathbf{w}}_{T}^{*}\right)\right\|_{2}^{2}+\left\|\boldsymbol{\Sigma}_{T}^{\nicefrac{{1}}{{2}}}\left(\mathbf{B}_{T}^{*}\mathbf{w}_{T}^{*}-\mathbf{V}^{*}\widetilde{\mathbf{w}}_{T}^{*}\right)\right\|_{2}^{2}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\left\|\boldsymbol{\Sigma}_{T}^{\nicefrac{{1}}{{2}}}\left(\widehat{\mathbf{V}}\widehat{\mathbf{w}}_{T}-\mathbf{V}^{*}\widetilde{\mathbf{w}}_{T}^{*}\right)\right\|_{2}^{2}+\epsilon^{2}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\lesssim}}\frac{1}{n_{T}}\left\|\mathbf{X}_{T}\left(\widehat{\mathbf{V}}\widehat{\mathbf{w}}_{T}-\mathbf{V}^{*}\widetilde{\mathbf{w}}_{T}^{*}\right)\right\|_{2}^{2}+\epsilon^{2}$
$\displaystyle=\frac{1}{n_{T}}\left\|\mathbf{P}_{\mathbf{X}_{T}\widehat{\mathbf{V}}}\mathbf{y}_{T}-\mathbf{X}_{T}\mathbf{V}^{*}\widetilde{\mathbf{w}}_{T}^{*}\right\|_{2}^{2}+\epsilon^{2}$
$\displaystyle\lesssim\frac{1}{n_{T}}\left\|\mathbf{P}_{\mathbf{X}_{T}\widehat{\mathbf{V}}}(\mathbf{X}_{T}\mathbf{V}^{*}\widetilde{\mathbf{w}}_{T}^{*}+\mathbf{z}_{T})-\mathbf{X}_{T}\mathbf{V}^{*}\widetilde{\mathbf{w}}_{T}^{*})\right\|_{2}^{2}+\frac{1}{n_{T}}\left\|\mathbf{P}_{\mathbf{X}_{T}\widehat{\mathbf{V}}}(\mathbf{X}_{T}\mathbf{B}_{T}^{*}\mathbf{w}_{T}^{*}-\mathbf{X}_{T}\mathbf{V}^{*}\widetilde{\mathbf{w}}_{T}^{*})\right\|_{2}^{2}+\epsilon^{2}$
where (a) follows from Assumption 1 and (b) uses Claim 2. Using the fact that
$\|\mathbf{P}_{\mathbf{X}_{T}\widehat{\mathbf{V}}}\|_{2}\leq 1$ (since
$\mathbf{P}_{\mathbf{X}_{T}\widehat{\mathbf{V}}}$ is a projection matrix) and
using Claim 2, we have:
$\displaystyle\lesssim\frac{1}{n_{T}}\left\|\mathbf{P}_{\mathbf{X}_{T}\widehat{\mathbf{V}}}(\mathbf{X}_{T}\mathbf{V}^{*}\widetilde{\mathbf{w}}_{T}^{*}+\mathbf{z}_{T})-\mathbf{X}_{T}\mathbf{V}^{*}\widetilde{\mathbf{w}}_{T}^{*})\right\|_{2}^{2}+\epsilon^{2}$
$\displaystyle\lesssim\frac{1}{n_{T}}\left\|\mathbf{P}^{\perp}_{\mathbf{X}_{T}\widehat{\mathbf{V}}}\mathbf{X}_{T}\mathbf{V}^{*}\widetilde{\mathbf{w}}_{T}^{*}\right\|_{2}^{2}+\epsilon^{2}+\frac{1}{n_{T}}\left\|\mathbf{P}_{\mathbf{X}_{T}\widehat{\mathbf{V}}}\mathbf{z}_{T}\right\|_{2}^{2}$

where the first inequality follows from Assumption 1 and Claim 2. We can take
the expectation over the distribution of $\mathbf{w}_{T}^{*}$ and use
Assumption 5 to yield:

$\displaystyle\mathbb{E}_{\widetilde{\mathbf{w}}_{T}^{*}}[\text{EER}({\boldsymbol{\theta}}_{\text{Phase}_{1}},{\boldsymbol{\theta}}_{T}^{*})]$
$\displaystyle\lesssim\frac{1}{n_{T}l}\left\|\mathbf{P}^{\perp}_{\mathbf{X}_{T}\widehat{\mathbf{V}}}\mathbf{X}_{T}\mathbf{V}^{*}\right\|_{F}^{2}+\epsilon^{2}+\frac{1}{n_{T}}\left\|\mathbf{P}_{\mathbf{X}_{T}\widehat{\mathbf{V}}}\mathbf{z}_{T}\right\|_{2}^{2}$
(15)

We now make use of the following lemma, which is proved below in Section 5.2.1
that provides a bound for the first term in (15).

######  Lemma 3 (Target Training Guarantee)

Assuming the results in Claim 1, Claim 2 (with
$\mathbf{B}=[\widehat{\mathbf{V}}\quad-\mathbf{V}^{*}]$) and Lemma 2 hold, we
then have:

$\displaystyle\left\|\mathbf{P}^{\perp}_{\mathbf{X}_{T}\widehat{\mathbf{V}}}\mathbf{X}_{T}\mathbf{V}^{*}\right\|_{F}^{2}$
$\displaystyle\lesssim\frac{n_{T}\sigma^{2}}{rn_{s}\sigma_{l}^{2}(\widetilde{\mathbf{W}}^{*})}\left(km{+}kdm\log(\kappa
n_{s}){+}\log\left(\frac{1}{\delta}\right)\right)$

Substituting the result from Lemma 3 in (15) and using
$\sigma_{l}^{2}(\widetilde{\mathbf{W}}^{*})\geq\frac{m}{l}$, the following
bound holds with probability at least $1-\frac{2\delta}{5}$:

$\displaystyle\mathbb{E}_{\widetilde{\mathbf{w}}_{T}^{*}}[\text{EER}({\boldsymbol{\theta}}_{\text{Phase}_{1}},{\boldsymbol{\theta}}_{T}^{*})]\lesssim\frac{1}{n_{T}}\left\|\mathbf{P}_{\mathbf{X}_{T}\widehat{\mathbf{V}}}\mathbf{z}_{T}\right\|_{2}^{2}+\epsilon^{2}+\frac{1}{rn_{s}m}\sigma^{2}\left(km+kdm\log(\kappa
n_{s})+\log\left(\frac{1}{\delta}\right)\right)$

Finally, the last term in above can be bounded by using a concentration
inequality for $\chi^{2}$-squared distribution. In particular, with
probability at least $1-\frac{3\delta}{5}$ we have
$\|\mathbf{P}_{\mathbf{X}_{T}\widehat{\mathbf{V}}}\mathbf{z}_{T}\|_{2}^{2}\lesssim\sigma^{2}(q+\log(\nicefrac{{1}}{{\delta}}))$.
Thus the following bound holds on
$\mathbb{E}_{\mathbf{w}_{T}^{*}}[\text{Err}(\widehat{\mathbf{B}}_{S},\mathbf{w}_{T}^{*})]$
with probability at least $1-\delta$:

$\displaystyle\mathbb{E}_{\mathbf{w}_{T}^{*}}[\text{EER}({\boldsymbol{\theta}}_{\text{Phase}_{1}},{\boldsymbol{\theta}}_{T}^{*})]$
$\displaystyle\lesssim\epsilon^{2}+\frac{1}{n_{T}}\sigma^{2}(q+\log(\nicefrac{{1}}{{\delta}}))+\frac{1}{rn_{s}m}\sigma^{2}\left(km+kdm\log(\kappa
n_{s})+\log\left(\frac{1}{\delta}\right)\right)$
$\displaystyle=\sigma^{2}\left[\frac{1}{rn_{s}m}\log\left(\frac{1}{\delta}\right){+}\left(\frac{kd\log(\kappa
n_{s})+k}{rn_{s}}\right)\right]+\frac{\sigma^{2}}{n_{T}}(q+\log(\nicefrac{{1}}{{\delta}})){+}\epsilon^{2}$

$\square$

####  5.2.1 Proof of Lemma 3

We start the proof by using Proposition 1 and Claim 2:

$\displaystyle\sigma_{l}^{2}(\widetilde{\mathbf{W}}^{*})\|\mathbf{P}^{\perp}_{\mathbf{X}_{T}\widehat{\mathbf{V}}}\mathbf{X}_{T}\mathbf{V}^{*}$
$\displaystyle\|_{F}^{2}\lesssim\sigma_{l}^{2}(\widetilde{\mathbf{W}}^{*})n_{T}\left\|\mathbf{P}^{\perp}_{\boldsymbol{\Sigma}_{T}^{\nicefrac{{1}}{{2}}}\widehat{\mathbf{V}}}\boldsymbol{\Sigma}_{T}^{\nicefrac{{1}}{{2}}}\mathbf{V}^{*}\right\|_{F}^{2}$
$\displaystyle\leq
n_{T}\sum_{i=1}^{m}\left\|\mathbf{P}^{\perp}_{\boldsymbol{\Sigma}_{T}^{\nicefrac{{1}}{{2}}}\widehat{\mathbf{V}}}\boldsymbol{\Sigma}_{T}^{\nicefrac{{1}}{{2}}}\mathbf{V}^{*}\widetilde{\mathbf{w}}_{i}^{*}\right\|_{2}^{2}$

The proof now follows the same procedure as in Proof of Lemma 1 starting from
Equation 5.1.1 and following it up with Lemma 2.

##  6 Proof for Phase 2 training

We now provide a proof for our bound in Theorem 2 which establishes excess
generalization risk for the model obtained after combined Phase 1 and Phase 2
training.

The data for Phase 2 training is given by
$(\mathbf{X}_{T_{2}},\mathbf{y}_{T_{2}})$ where
$\mathbf{y}_{T_{2}}=\mathbf{X}_{T_{2}}\mathbf{B}_{T}^{*}\mathbf{w}_{T}^{*}+\mathbf{z}_{T_{2}}$.
Here ${\boldsymbol{\theta}}_{T}^{*}:=\mathbf{B}_{T}^{*}\mathbf{w}^{*}$ denotes
the true data generating target model. We define
$\mathbf{P}_{\parallel}=\mathbf{X}_{T_{2}}^{\top}(\mathbf{X}_{T_{2}}\mathbf{X}_{T_{2}}^{\top})^{-1}\mathbf{X}_{T_{2}}$
as projection matrix on the row-space of matrix $\mathbf{X}_{T_{2}}$ and
$\mathbf{P}_{\perp}=\mathbf{I}-\mathbf{P}_{\parallel}$.
We first note the following result that establishes where the Gradient Descent
solution converges to, the proof of which is given in Section 6.1.1 below.

###### Lemma 4

Under the assumptions of Theorem 2, performing gradient descent on the
objective (6) with the initialization
${\boldsymbol{\theta}}^{(0)}:={\boldsymbol{\theta}}_{\text{Phase}_{1}}$ and
learning rate $\eta$, yields the solution:

${\boldsymbol{\theta}}_{GD}:={\boldsymbol{\theta}}^{(\infty)}=\mathbf{P}_{\parallel}{\boldsymbol{\theta}}_{T}^{*}+\mathbf{P}_{\perp}{\boldsymbol{\theta}}_{\text{Phase}_{1}}+\mathbf{X}_{T_{2}}^{\top}(\mathbf{X}_{T_{2}}\mathbf{X}_{T_{2}}^{\top})^{-1}\mathbf{z}$

where
$\mathbf{P}_{\parallel}=\mathbf{X}_{T_{2}}^{\top}(\mathbf{X}_{T_{2}}\mathbf{X}_{T_{2}}^{\top})^{-1}\mathbf{X}_{T_{2}}$
is the projection matrix on the row-space of matrix $\mathbf{X}_{T_{2}}$ and
$\mathbf{P}_{\perp}=\mathbf{I}-\mathbf{P}_{\parallel}$.

###  6.1 Proof of Theorem 2

We now use the solution of the gradient descent
$\hat{{\boldsymbol{\theta}}}_{T}:={\boldsymbol{\theta}}_{GD}$ derived in Lemma
4 and find the excess population risk. The excess risk is given by:

EER
$\displaystyle(\hat{{\boldsymbol{\theta}}}_{T},{\boldsymbol{\theta}}_{T}^{*})=\mathbb{E}_{\mathbf{X}_{T_{2}}\sim
p_{T}}(\mathbf{X}_{T_{2}}^{\top}{\boldsymbol{\theta}}_{T}^{*}-\mathbf{X}_{T_{2}}^{\top}{\boldsymbol{\theta}}_{GD})^{2}$
$\displaystyle\quad=\mathbb{E}_{\mathbf{X}_{T_{2}}\sim
p_{T}}\text{Tr}[({\boldsymbol{\theta}}_{T}^{*}{-}{\boldsymbol{\theta}}_{GD})^{\top}\mathbf{X}_{T_{2}}\mathbf{X}_{T_{2}}^{\top}({\boldsymbol{\theta}}_{T}^{*}{-}{\boldsymbol{\theta}}_{GD})]$
$\displaystyle\quad=\|\boldsymbol{\Sigma}_{T}^{\nicefrac{{1}}{{2}}}({\boldsymbol{\theta}}_{T}^{*}-{\boldsymbol{\theta}}_{GD})\|_{2}^{2}$

Substituting the value of ${\boldsymbol{\theta}}_{GD}$ from Lemma 4 we get:

$\displaystyle\text{EER}(\hat{{\boldsymbol{\theta}}}_{T},{\boldsymbol{\theta}}_{T}^{*})$
$\displaystyle\leq
2\|\boldsymbol{\Sigma}_{T}^{\nicefrac{{1}}{{2}}}\mathbf{P}_{\perp}({\boldsymbol{\theta}}_{T}^{*}-{\boldsymbol{\theta}}_{T_{0}})\|_{2}^{2}+2\|\boldsymbol{\Sigma}_{T}^{\nicefrac{{1}}{{2}}}\mathbf{X}_{T_{2}}^{\top}(\mathbf{X}_{T_{2}}\mathbf{X}_{T_{2}}^{\top})^{-1}\mathbf{z}\|_{2}^{2}$
(16)

We focus on the first term for now. We have:

$\displaystyle\|\boldsymbol{\Sigma}_{T}^{\nicefrac{{1}}{{2}}}\mathbf{P}_{\perp}({\boldsymbol{\theta}}_{T}^{*}-{\boldsymbol{\theta}}_{T_{0}})\|_{2}^{2}=({\boldsymbol{\theta}}_{T}^{*}-{\boldsymbol{\theta}}_{T_{0}})^{\top}\mathbf{P}_{\perp}^{\top}\boldsymbol{\Sigma}_{T}\mathbf{P}_{\perp}({\boldsymbol{\theta}}_{T}^{*}-{\boldsymbol{\theta}}_{T_{0}})$
$\displaystyle=({\boldsymbol{\theta}}_{T}^{*}-{\boldsymbol{\theta}}_{T_{0}})^{\top}\mathbf{P}_{\perp}^{\top}\left(\boldsymbol{\Sigma}_{T}-\frac{1}{n_{T}}\mathbf{X}_{T_{2}}^{\top}\mathbf{X}_{T_{2}}\right)\mathbf{P}_{\perp}({\boldsymbol{\theta}}_{T}^{*}-{\boldsymbol{\theta}}_{T_{0}})$
$\displaystyle=\left\|\left(\boldsymbol{\Sigma}_{T}-\frac{1}{n_{T}}\mathbf{X}_{T_{2}}^{\top}\mathbf{X}_{T_{2}}\right)^{\nicefrac{{1}}{{2}}}\mathbf{P}_{\perp}({\boldsymbol{\theta}}_{T}^{*}-{\boldsymbol{\theta}}_{T_{0}})\right\|_{2}^{2}$
$\displaystyle\leq\left\|\boldsymbol{\Sigma}_{T}-\frac{1}{n_{T}}\mathbf{X}_{T_{2}}^{\top}\mathbf{X}_{T_{2}}\right\|_{2}\|\mathbf{P}_{\perp}({\boldsymbol{\theta}}_{T}^{*}-{\boldsymbol{\theta}}_{T_{0}})\|_{2}^{2}$
(17)

The second term in (6.1) can be bounded by
$\|\mathbf{P}_{\perp}({\boldsymbol{\theta}}_{T}^{*}-{\boldsymbol{\theta}}_{T_{0}})\|_{2}^{2}\leq\|({\boldsymbol{\theta}}_{T}^{*}-{\boldsymbol{\theta}}_{T_{0}})\|_{2}^{2}$
by noting that $\|\mathbf{P}_{\perp}\|_{2}\leq 1$. We thus finally get the
bound:

$\displaystyle\text{EER}(\hat{{\boldsymbol{\theta}}}_{T},{\boldsymbol{\theta}}_{T}^{*})$
$\displaystyle\leq
2\left\|\boldsymbol{\Sigma}_{T}-\frac{1}{n_{T}}\mathbf{X}_{T_{2}}^{\top}\mathbf{X}_{T_{2}}\right\|_{2}\|({\boldsymbol{\theta}}_{T}^{*}-{\boldsymbol{\theta}}_{T_{0}})\|_{2}^{2}+2\|\boldsymbol{\Sigma}_{T}^{\nicefrac{{1}}{{2}}}\mathbf{X}_{T_{2}}^{\top}(\mathbf{X}_{T_{2}}\mathbf{X}_{T_{2}}^{\top})^{-1}\mathbf{z}\|_{2}^{2}$
(18)

We now provide a bound for the second term in (18). Note:

$\displaystyle\|\boldsymbol{\Sigma}_{T}^{\nicefrac{{1}}{{2}}}\mathbf{X}_{T_{2}}^{\top}(\mathbf{X}_{T_{2}}\mathbf{X}_{T_{2}}^{\top})^{-1}\mathbf{z}\|_{2}^{2}=\mathbf{z}^{\top}(\mathbf{X}_{T_{2}}\mathbf{X}_{T_{2}}^{\top})^{-1}\mathbf{X}_{T_{2}}\boldsymbol{\Sigma}_{T}\mathbf{X}_{T_{2}}^{\top}(\mathbf{X}_{T_{2}}\mathbf{X}_{T_{2}}^{\top})^{-1}\mathbf{z}$

From [14, Lemma 9], we can get a high probability bound (probability
$>1-e^{-t}$) on this term for some $t>0$ as

$\displaystyle\|\boldsymbol{\Sigma}_{T}^{\nicefrac{{1}}{{2}}}\mathbf{X}_{T_{2}}^{\top}(\mathbf{X}_{T_{2}}\mathbf{X}_{T_{2}}^{\top})^{-1}\mathbf{z}\|_{2}^{2}\leq(4t+2)\sigma^{2}\text{Tr}\left((\mathbf{X}_{T_{2}}\mathbf{X}_{T_{2}}^{\top})^{-1}\mathbf{X}_{T_{2}}\boldsymbol{\Sigma}_{T}\mathbf{X}_{T_{2}}^{\top}(\mathbf{X}_{T_{2}}\mathbf{X}_{T_{2}}^{\top})^{-1}\right)$

To bound the trace term, we use [14, Lemma 13, 18]: For universal constant
$b,c\geq 1$ and $k^{*}:=\min\\{k\geq 0:r_{k}(\boldsymbol{\Sigma}_{T})\geq
bn\\}$, we have

$\displaystyle\textbf{Tr}\left((\mathbf{X}_{T_{2}}\mathbf{X}_{T_{2}}^{\top})^{-1}\mathbf{X}_{T_{2}}\boldsymbol{\Sigma}_{T}\mathbf{X}_{T_{2}}^{\top}(\mathbf{X}_{T_{2}}\mathbf{X}_{T_{2}}^{\top})^{-1}\right)\leq
c\left(\frac{k^{*}}{bn}{+}\frac{bn}{R_{k^{*}}(\boldsymbol{\Sigma}_{T})}\right)$

where
$r_{k}(\boldsymbol{\Sigma}_{T})=\frac{\boldsymbol{\Sigma}_{i>k}\lambda_{i}}{\lambda_{k+1}}$,
$R_{k^{*}}(\boldsymbol{\Sigma}_{T})=\frac{(\boldsymbol{\Sigma}_{i>k}\lambda_{i})^{2}}{\boldsymbol{\Sigma}_{i>k}\lambda_{i}^{2}}$.Substituting
the value of $t=\log\left(\frac{2}{\delta}\right)$ Plugging the resulting
bound in (18), we can finally claim that the following holds with probability
at least $1-\frac{\delta}{2}$:

$\displaystyle\text{EER}(\hat{{\boldsymbol{\theta}}}_{T},{\boldsymbol{\theta}}_{T}^{*})$
$\displaystyle\lesssim\left\|\boldsymbol{\Sigma}_{T}-\frac{1}{n_{T}}\mathbf{X}_{T_{2}}^{\top}\mathbf{X}_{T_{2}}\right\|_{2}\|({\boldsymbol{\theta}}_{T}^{*}-{\boldsymbol{\theta}}_{T_{0}})\|_{2}^{2}+c\sigma^{2}\log\left(\frac{1}{\delta}\right)\left(\frac{k^{*}}{bn}+\frac{bn}{R_{k^{*}}(\boldsymbol{\Sigma}_{T})}\right)$

The covariance approximation error in the first term of above can be bounded
by the result in [34, Theorem 9]. This yields the following bound on the
approximation with probability at least $1-e^{-\delta_{1}}$ over the choice of
data matrix $\mathbf{X}_{T_{2}}$ for some constant $u>0$ and $\delta_{1}>1$

$\displaystyle\left\|\boldsymbol{\Sigma}_{T}{-}\frac{1}{n_{T}}\mathbf{X}_{T_{2}}^{\top}\mathbf{X}_{T_{2}}\right\|_{2}$
$\displaystyle\leq
u\lambda_{1}\max\left\\{\sqrt{\frac{\sum_{i=1}^{d}\lambda_{i}}{n_{T}\lambda_{1}}},\frac{\sum_{i=1}^{d}\lambda_{i}}{n_{T}\lambda_{1}},\sqrt{\frac{\delta_{1}}{n_{T}}},\frac{\delta_{1}}{n_{T}}\right\\}$

Substituting $\delta_{1}=\log\left(\frac{2}{\delta}\right)$, with probability
at least $1-\frac{\delta}{2}$,

$\displaystyle\left\|\boldsymbol{\Sigma}_{T}-\frac{1}{n_{T}}\mathbf{X}_{T_{2}}^{\top}\mathbf{X}_{T_{2}}\right\|_{2}\leq
u\lambda_{1}\max\left\\{\sqrt{\frac{\sum_{i=1}^{d}\lambda_{i}}{n_{T}\lambda_{1}}},\frac{\sum_{i=1}^{d}\lambda_{i}}{n_{T}\lambda_{1}},\sqrt{\frac{1}{n_{T}}\log\left(\frac{1}{\delta}\right)},\frac{1}{n_{T}}\log\left(\frac{1}{\delta}\right)\right\\}$
(19)

Denote the eigenvalues of covariance matrix of the target data as
$\\{\lambda_{i}\\}_{i=1}^{d}$, with $\lambda_{1}\geq\ldots\lambda_{d}$, we
then have:

$\displaystyle\text{EER}(\hat{{\boldsymbol{\theta}}}_{T},{\boldsymbol{\theta}}_{T}^{*})$
$\displaystyle\lesssim\left\|\boldsymbol{\Sigma}_{T}-\frac{1}{n_{T_{2}}}\mathbf{X}_{T_{2}}^{\top}\mathbf{X}_{T_{2}}\right\|_{2}\frac{1}{\lambda_{d}}\|\boldsymbol{\Sigma}_{T}({\boldsymbol{\theta}}_{T}^{*}-{\boldsymbol{\theta}}_{T_{0}})\|_{2}^{2}+c\sigma^{2}\log\left(\frac{1}{\delta}\right)\left(\frac{k^{*}}{bn_{T_{2}}}+\frac{bn_{T_{2}}}{R_{k^{*}}(\boldsymbol{\Sigma}_{T})}\right)$

where
$r_{k}(\boldsymbol{\Sigma}_{T})=\frac{\boldsymbol{\Sigma}_{i>k}\lambda_{i}}{\lambda_{k+1}}$,
$R_{k^{*}}(\boldsymbol{\Sigma}_{T})=\frac{(\boldsymbol{\Sigma}_{i>k}\lambda_{i})^{2}}{\boldsymbol{\Sigma}_{i>k}\lambda_{i}^{2}}$.
Here, constant $b>1$ and $k^{*}=\min\\{k\geq 0:r_{k}(\boldsymbol{\Sigma})\geq
bn\\}$ and the covariance estimation term can be bounded by:

$\left\|\boldsymbol{\Sigma}_{T}-\frac{1}{n_{T_{2}}}\mathbf{X}_{T_{2}}^{\top}\mathbf{X}_{T_{2}}\right\|_{2}\leq
u\lambda_{1}\max\left\\{\sqrt{\frac{\sum_{i=1}^{d}\lambda_{i}}{n_{T_{2}}\lambda_{1}}},\frac{\sum_{i=1}^{d}\lambda_{i}}{n_{T_{2}}\lambda_{1}},\sqrt{\frac{1}{n_{T_{2}}}\log\left(\frac{1}{\delta}\right)},\frac{1}{n_{T_{2}}}\log\left(\frac{1}{\delta}\right)\right\\}$

with probability at least $1-\frac{\delta}{2}$. We now substitute the value of
$\|\boldsymbol{\Sigma}_{T}({\boldsymbol{\theta}}_{T}^{*}-{\boldsymbol{\theta}}_{T_{0}})\|_{2}^{2}$
from Theorem 1 (as
${\boldsymbol{\theta}}_{T_{0}}=\widehat{\mathbf{V}}\widehat{\mathbf{w}}_{T}$
which was obtained by using $n_{T_{1}}$ target samples). Thus the final bound
after Phase 1 and Phase 2 training, after taking the expectation w.r.t the
target model ${\boldsymbol{\theta}}_{T}^{*}$, is given by:

$\displaystyle\mathbb{E}[\text{EER}(\hat{{\boldsymbol{\theta}}}_{T},{\boldsymbol{\theta}}_{T}^{*})]$
$\displaystyle\lesssim\left\|\boldsymbol{\Sigma}_{T}-\frac{1}{n_{T_{2}}}\mathbf{X}_{T_{2}}^{\top}\mathbf{X}_{T_{2}}\right\|_{2}\frac{\sigma^{2}}{\lambda_{d}}\frac{1}{rn_{s}m}\log\left(\frac{1}{\delta}\right)+\left\|\boldsymbol{\Sigma}_{T}-\frac{1}{n_{T_{2}}}\mathbf{X}_{T_{2}}^{\top}\mathbf{X}_{T_{2}}\right\|_{2}\frac{\sigma^{2}}{\lambda_{d}}\left(\frac{kd\log(\kappa
n_{s})+k}{rn_{s}}\right)$
$\displaystyle\qquad+\left\|\boldsymbol{\Sigma}_{T}-\frac{1}{n_{T_{2}}}\mathbf{X}_{T_{2}}^{\top}\mathbf{X}_{T_{2}}\right\|_{2}\frac{1}{\lambda_{d}}\left(\sigma^{2}\left[\frac{1}{n_{T_{1}}}(q+\log(\nicefrac{{1}}{{\delta}}))\right]+\epsilon^{2}\right)+c\sigma^{2}\log\left(\frac{1}{\delta}\right)\left(\frac{k^{*}}{bn_{T_{2}}}+\frac{bn_{T_{2}}}{R_{k^{*}}(\boldsymbol{\Sigma}_{T})}\right)$

where $u,c$ are universal constants. We now substitute the bound for the
covariance estimate from (19) and simplfy the expression by assuming
$\frac{r_{0}(\boldsymbol{\Sigma}_{T})}{n_{T_{2}}}\geq\frac{1}{n_{T_{2}}}\log\left(\frac{1}{\delta}\right)\geq
1$ since we have a few target samples:

$\displaystyle\mathbb{E}[\text{EER}(\hat{{\boldsymbol{\theta}}}_{T},{\boldsymbol{\theta}}_{T}^{*})]$
$\displaystyle\leq\frac{u\lambda_{1}}{\lambda_{d}}\frac{r_{0}(\boldsymbol{\Sigma}_{T})}{n_{T_{2}}}\left(\frac{\sigma^{2}}{n_{T_{1}}}(q+\log(\nicefrac{{1}}{{\delta}}))+\epsilon^{2}\right)+\frac{u\lambda_{1}\sigma^{2}}{\lambda_{d}}\frac{r_{0}(\boldsymbol{\Sigma}_{T})}{n_{T_{2}}}\left(\frac{1}{rn_{s}m}\log\left(\frac{1}{\delta}\right)+\left(\frac{kd\log(\kappa
n_{s})+k}{rn_{s}}\right)\right)$
$\displaystyle+c\sigma^{2}\log\left(\frac{1}{\delta}\right)\left(\frac{k^{*}}{bn_{T_{2}}}+\frac{bn_{T_{2}}}{R_{k^{*}}(\boldsymbol{\Sigma}_{T})}\right)$

####  6.1.1 Proof of Lemma 4

For any time step $t$ of the gradient descent process, the gradient of the
objective in (6) evaluated at ${\boldsymbol{\theta}}^{(t)}$ is given by:

$\displaystyle\nabla
f({\boldsymbol{\theta}}^{(t)})=\frac{2}{n_{T}}\mathbf{X}_{T_{2}}^{\top}(\mathbf{X}_{T_{2}}{\boldsymbol{\theta}}^{(t)}-\mathbf{y}_{T_{2}})$

The gradient update step using step size $\eta$ is given by:

$\displaystyle{\boldsymbol{\theta}}^{(t+1)}$
$\displaystyle={\boldsymbol{\theta}}^{(t)}-\frac{2\eta}{n_{T}}\mathbf{X}_{T_{2}}^{\top}(\mathbf{X}_{T_{2}}{\boldsymbol{\theta}}^{(t)}-\mathbf{y}_{T_{2}})$
$\displaystyle={\boldsymbol{\theta}}_{T_{0}}+\mathbf{X}_{T_{2}}^{\top}\mathbf{a}^{(t)}$

where $\mathbf{a}$ is some vector in $\mathbb{R}^{n_{T}}$. In the limit, the
gradient descent convergence to a solution of the form:

$\displaystyle{\boldsymbol{\theta}}^{(\infty)}={\boldsymbol{\theta}}_{T_{0}}+\mathbf{X}_{T_{2}}^{\top}\mathbf{a}$
(20)

Since the problem in (6) is over-parameterized, there exists a value
${\boldsymbol{\theta}}^{*}$ such that $f({\boldsymbol{\theta}}^{*})=0$. This
follows from the fact that $\mathbf{X}_{T_{2}}$ has full row rank. The
gradient descent solution, under an appropriate choice of the learning rate,
thus converges to this value while yield a zero loss, implying:

$\displaystyle\mathbf{X}_{T_{2}}{\boldsymbol{\theta}}^{(\infty)}=\mathbf{y}_{T_{2}}=\mathbf{X}_{T_{2}}{\boldsymbol{\theta}}_{T}^{*}+\mathbf{z}_{T_{2}}$
$\displaystyle\Rightarrow$
$\displaystyle\mathbf{X}_{T_{2}}({\boldsymbol{\theta}}_{T_{0}}+\mathbf{X}_{T_{2}}^{\top}\mathbf{a})=\mathbf{X}_{T_{2}}{\boldsymbol{\theta}}_{T}^{*}+\mathbf{z}_{T_{2}}$
$\displaystyle\Rightarrow$
$\displaystyle\mathbf{a}=(\mathbf{X}_{T_{2}}\mathbf{X}_{T_{2}}^{\top})^{-1}(\mathbf{X}_{T_{2}}({\boldsymbol{\theta}}^{*}_{T}-{\boldsymbol{\theta}}_{T_{0}})+\mathbf{z}_{T_{2}})$

Substituting this in (20), we get

$\displaystyle{\boldsymbol{\theta}}_{GD}$
$\displaystyle:={\boldsymbol{\theta}}^{(\infty)}$
$\displaystyle={\boldsymbol{\theta}}_{T_{0}}+\mathbf{X}_{T_{2}}^{\top}(\mathbf{X}_{T_{2}}\mathbf{X}_{T_{2}}^{\top})^{-1}(\mathbf{X}_{T_{2}}({\boldsymbol{\theta}}^{*}_{T}-{\boldsymbol{\theta}}_{T_{0}})+\mathbf{z}_{T_{2}})$
$\displaystyle=\mathbf{P}_{\parallel}{\boldsymbol{\theta}}_{T}^{*}+\mathbf{P}_{\perp}{\boldsymbol{\theta}}_{T_{0}}+\mathbf{X}_{T_{2}}^{\top}(\mathbf{X}_{T_{2}}\mathbf{X}_{T_{2}}^{\top})^{-1}\mathbf{z}_{T_{2}}$

##  7 Numerical Results

We now provide numerical simulations for our proposed scheme for optimizing
linear regression objectives in a data scarce regime. To demonstrate the
effectiveness of leveraging pre-trained representations and fine-tuning, we
consider the case where we have access to the true representation matrix
$\mathbf{V}^{*}$ formed by the source representations. We compare the
performance of models obtained after Phase 1 and Phase 2 training for
different parameters of interest and discuss their sample complexity
requirements.

###  7.1 Setup

We generate the $d\times q$ matrix $\mathbf{V}^{*}$ matrix with entries
sampled from the standard normal distribution, with $d=1000$ and $q=50$. We
generate $n_{T_{1}}\in\\{100,200,300,1000\\}$ number of samples for the target
data for Phase 1 to form the matrix $\mathbf{X}_{T_{1}}$, which is generated
with i.i.d Gaussian entries with mean 0 and covariance matrix $\Sigma_{T}$. To
simulate slowly decaying eigenvalues of $\Sigma_{T}$, we set them as
$\lambda_{j}=e^{\frac{-j}{\tau}}+\varepsilon$ for $j\in[d]$, where $\tau=1$ is
the decay factor and $\varepsilon=0.0001$. The true target model
${\boldsymbol{\theta}}_{T}^{*}$ is generated as $\mathbf{u}+\mathbf{v}$ where
$\mathbf{u}\in\mathbb{R}^{d}$ lies in the span of $\mathbf{V}^{*}$ and
$\mathbf{v}$ is Gaussian vector with covariance matrix
$\text{I}\sigma_{T}^{2}$ and zero mean. We call the expected ratio of
$\mathbf{u}$ to $\mathbf{v}$ as the in-out mixture representation ratio.222The
parameter $\sigma_{T}^{2}$ indirectly enables us simulate the value of
$\epsilon$ in Assumption 1, with larger values of $\sigma_{T}^{2}$ implying
that ${\boldsymbol{\theta}}_{T}^{*}$ lies farther away from the subspace
spanned by the columns of $\mathbf{V}^{*}$. A higher $\sigma_{T}^{2}$ values
thus yields a small value for the in-out representation mixture ratio. The
target output vector $\mathbf{y}_{T}$ is generated as
$\mathbf{y}_{T_{1}}=\mathbf{X}_{T}{\boldsymbol{\theta}}_{T}^{*}+\mathbf{z}_{T_{1}}$,
with $\mathbf{z}_{T_{1}}$ being a Gaussian noise vector. Phase 1 training thus
seeks to minimize the objective in (5) (with $\widehat{\mathbf{V}}$ replaced
by $\mathbf{V}^{*}$, since we assume access to complete source
representations) and we denote the output model
${\boldsymbol{\theta}}_{\text{Phase}_{1}}$. For Phase 2 training, we optimize
the objective in (6) using new $n_{T_{2}}\in\\{100,200,300,1000\\}$ number of
target samples with ${\boldsymbol{\theta}}_{\text{Phase}_{1}}$ as
initialization to obtain the final model
${\boldsymbol{\theta}}_{\text{Phase}_{2}}$. We compare the performance of
${\boldsymbol{\theta}}_{\text{Phase}_{1}}$ and
${\boldsymbol{\theta}}_{\text{Phase}_{2}}$ on 500 test samples generated from
the target data. As a baseline, we also consider the performance of the scheme
which takes $n_{T_{1}}+n_{T_{2}}$ number of target samples and trains the
model from scratch, i.e., without leveraging the source representations
$\mathbf{V}^{*}$. We denote the model obtained form this scheme as
${\boldsymbol{\theta}}_{0}$.

Table 1: Performance comparison for learned models after Phase 1 (Pre-training), Phase 2 (Fine-tuning) and learning from Scratch. Sample Configuration | In-Out Representation Mixture Ratio for ${\boldsymbol{\theta}}_{T}^{*}$ (in dB) | Phase 1 | Phase 2 | Scratch
---|---|---|---|---
$n_{T_{1}}=100,n_{T_{2}}=100$ | 50 | 1.01 | 1.01 | 10.17
20 | 3.21 | 3.05 | 10.41
10 | 9.97 | 9.17 | 10.98
5 | 16.13 | 15.84 | 12.74
1 | 28.01 | 26.61 | 15.96
$n_{T_{1}}=200,n_{T_{2}}=200$ | 50 | 1.01 | 1.00 | 9.71
20 | 2.03 | 1.88 | 9.33
10 | 5.71 | 5.14 | 10.33
5 | 10.09 | 9.10 | 11.79
1 | 15.30 | 13.62 | 13.68
$n_{T_{1}}=300,n_{T_{2}}=300$ | 50 | 1.01 | 1.00 | 8.13
20 | 1.90 | 1.69 | 8.35
10 | 5.30 | 4.46 | 9.07
5 | 9.12 | 7.60 | 9.95
1 | 14.55 | 12.12 | 12.13
$n_{T_{1}}=1000,n_{T_{2}}=1000$ | 50 | 1.01 | 1.01 | 1.01
20 | 1.74 | 1.01 | 1.01
10 | 4.72 | 1.09 | 1.01
5 | 7.92 | 1.12 | 1.01
1 | 12.47 | 1.21 | 1.01

###  7.2 Results

The results from Phase 1 and Phase 2 training for different splits for the
number of phase target samples and $\epsilon$ values333The values in the ‘In-
Out Representation Mixture Ratio’ column in Table 1 correspond to the ratio of
the signal in the subspace spanned by columns of $\mathbf{V}^{*}$ and the
added out of subspace signal (of variance $\sigma_{T}^{2}$) added to it to
generate the true target model ${\boldsymbol{\theta}}_{T}^{*}$. Lower values
of this ratio correspond to higher values of $\sigma_{T}^{2}$. are shown in
Table 1. The numerical values, which are averaged over 10 independent runs,
denote the ratio of the error obtained by the learned model after the
respective phase and the error of the underlying true data generation model
${\boldsymbol{\theta}}_{T}^{*}$ for the target data on a test dataset. In a
data-scarce regime,
$(n_{T_{1}},n_{T_{2}})\in\\{(100,100),(200,200),(300,300)\\}$, the performance
of the model learned from scratch (without leveraging source representations;
denoted by column _Scratch_) can be unsatisfactory. As expected, even pre-
training (Phase 1) and fine-tuning (Phase 2) in low data regimes does not
yield good performance if the source models are not useful for the target
data, which is the case when the in-representation mixture to out-mixture
ratio for ${\boldsymbol{\theta}}_{T}^{*}$ is small, as shown by the
performance for values 5dB, 1dB in Table 1. However, utilizing source
representations gives significantly better performance relative to training
from scratch in cases when ${\boldsymbol{\theta}}_{T}^{*}$ doesn’t lie far off
from ${\bf V}^{*}$ as can be seen by comparing the values of Phase 2 and
Scratch training results for in-out signal mixture ratio of 50dB, 20dB, 10dB.
Thus leveraging source representations for target training can be beneficial
in scare-data regimes when source representation are useful for the target
task and thus representation transfer is practical. It can be seen that
training from scratch could perform well for a data-rich regime,
$(n_{T_{1}},n_{T_{2}})=(1000,1000)$. Here, the performance of the learned
model after Phase 1 degrades with decreasing in-out representation mixture
ratio as the source representations become less useful to learn
${\boldsymbol{\theta}}_{T}^{*}$. Meanwhile, performing fine-tuning in addition
to utilizing source representations, as in Phase 2, yields much better
performance of the overall learned model with relative errors much less than
after Phase 1. Thus, fine-tuning on target data (Phase 2) can be essential in
addition to leveraging source models directly by pre-training (Phase 1) when
the true model ${\boldsymbol{\theta}}_{T}^{*}$ lies farther away from the
subspace spanned by the source representations.

##  8 Conclusion

In this work, we proposed a method for training linear regression models via
representation transfer learning in the limited sample regime, when given
access to multiple pre-trained linear models trained on data domains (sources)
different form the target of interest. We established excess risk bounds for
the learned target model when (i) source representations are used directly to
construct a target representation and adapted to the target task, and (ii)
when the entire resulting model is fine-tuned in the over-parameterized regime
using target task samples. Our bounds showed a gain in target sample
complexity compared to the baseline case of learning without access to the
pre-trained models, thus demonstrating the benefit of transfer learning for
better generalization in the limited sample regime. Our provided numerical
results corroborated this fact and showed superior performance of our proposed
scheme compared to learning from scratch in data-scare regimes.

As future extensions to this work, it is of interest to see how non-linear
activation functions can be introduced in the model to analyze more
complicated architectures like Neural Networks (NNs). Analyzing representation
transfer learning with multiple NNs and utilizing recently developed results
in benign over-fitting for this setting [35] is an interesting next step. In
many scenarios of interest, for training the source task models, _unlabeled_
data from the target distribution might be available. While there are
empirical works utilizing unlabeled samples in the context of semi-supervised
adaptation [36, 37, 26], theoretical results on understanding generalization
of representation transfer learning methods (with pre-training/fine-tuning)
and their sample complexity requirements are missing and would be an
interesting direction to pursue.

## Acknowledgments

This work was supported in part by NSF grants 2139304, 2146838 and 2007714,
and Army Research Laboratory grant under Cooperative Agreement
W911NF-17-2-0196.

## References

  * [1] Q. S. Y. Liu, T. Chua, and B. Schiele, “Meta-transfer learning for few-shot learning,” in _2018 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018.
  * [2] Y. Bengio, A. Courville, and P. Vincent, “Representation learning: A review and new perspectives,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 35, no. 8, pp. 1798–1828, 2013.
  * [3] Y. Bengio, “Deep learning of representations for unsupervised and transfer learning,” in _Proceedings of ICML workshop on unsupervised and transfer learning_. JMLR Workshop and Conference Proceedings, 2012, pp. 17–36.
  * [4] Y. Jia, Y. Zhang, R. Weiss, Q. Wang, J. Shen, F. Ren, P. Nguyen, R. Pang, I. Lopez Moreno, Y. Wu _et al._ , “Transfer learning from speaker verification to multispeaker text-to-speech synthesis,” _Advances in neural information processing systems_ , vol. 31, 2018.
  * [5] Z. Liu, Y. Lin, and M. Sun, _Representation learning for natural language processing_. Springer Nature, 2020.
  * [6] J. Blitzer, K. Crammer, A. Kulesza, F. Pereira, and J. Wortman, “Learning bounds for domain adaptation,” _Advances in neural information processing systems_ , vol. 20, 2007.
  * [7] Y. Mansour, M. Mohri, and A. Rostamizadeh, “Domain adaptation: Learning bounds and algorithms,” in _COLT 2009 - The 22nd Conference on Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009_ , 2009. [Online]. Available: http://www.cs.mcgill.ca/%7Ecolt2009/papers/003.pdf#page=1
  * [8] S. S. Du, W. Hu, S. M. Kakade, J. D. Lee, and Q. Lei, “Few-shot learning via learning the representation, provably,” in _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net, 2021. [Online]. Available: https://openreview.net/forum?id=pW2Q2xLwIMD
  * [9] K. Chua, Q. Lei, and J. D. Lee, “How fine-tuning allows for effective meta-learning,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 8871–8884, 2021.
  * [10] N. Tripuraneni, C. Jin, and M. Jordan, “Provable meta-learning of linear representations,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 10 434–10 443.
  * [11] A. Maurer, M. Pontil, and B. Romera-Paredes, “The benefit of multitask representation learning,” _Journal of Machine Learning Research_ , vol. 17, no. 81, pp. 1–32, 2016.
  * [12] M. Belkin, D. J. Hsu, and P. Mitra, “Overfitting or perfect fitting? risk bounds for classification and regression rules that interpolate,” _Advances in neural information processing systems_ , vol. 31, 2018.
  * [13] S. Arora, S. Du, W. Hu, Z. Li, and R. Wang, “Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks,” in _International Conference on Machine Learning_. PMLR, 2019, pp. 322–332.
  * [14] P. L. Bartlett, P. M. Long, G. Lugosi, and A. Tsigler, “Benign overfitting in linear regression,” _Proceedings of the National Academy of Sciences_ , vol. 117, no. 48, pp. 30 063–30 070, 2020.
  * [15] T. Hastie, A. Montanari, S. Rosset, and R. J. Tibshirani, “Surprises in high-dimensional ridgeless least squares interpolation,” _The Annals of Statistics_ , vol. 50, no. 2, pp. 949–986, 2022.
  * [16] V. Shah, S. Basu, A. Kyrillidis, and S. Sanghavi, “On generalization of adaptive methods for over-parameterized linear regression,” _arXiv preprint arXiv:2011.14066_ , 2020.
  * [17] J. Wu, D. Zou, V. Braverman, and Q. Gu, “Direction matters: On the implicit bias of stochastic gradient descent with moderate learning rate,” in _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net, 2021. [Online]. Available: https://openreview.net/forum?id=3X64RLgzY6O
  * [18] S. Gunasekar, J. Lee, D. Soudry, and N. Srebro, “Characterizing implicit bias in terms of optimization geometry,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 1832–1841.
  * [19] C. Finn, P. Abbeel, and S. Levine, “Model-agnostic meta-learning for fast adaptation of deep networks,” in _International conference on machine learning_. PMLR, 2017, pp. 1126–1135.
  * [20] J. Wang, C. Lan, C. Liu, Y. Ouyang, T. Qin, W. Lu, Y. Chen, W. Zeng, and P. Yu, “Generalizing to unseen domains: A survey on domain generalization,” _IEEE Transactions on Knowledge and Data Engineering_ , 2022.
  * [21] D. McNamara and M.-F. Balcan, “Risk bounds for transferring representations with and without fine-tuning,” in _International conference on machine learning_. PMLR, 2017, pp. 2373–2381.
  * [22] T. Galanti, L. Wolf, and T. Hazan, “A theoretical framework for deep transfer learning,” _Information and Inference: A Journal of the IMA_ , vol. 5, no. 2, pp. 159–209, 2016.
  * [23] H. Zhao, R. T. Des Combes, K. Zhang, and G. Gordon, “On learning invariant representations for domain adaptation,” in _International conference on machine learning_. PMLR, 2019, pp. 7523–7532.
  * [24] S. Ben-David, J. Blitzer, K. Crammer, and F. Pereira, “Analysis of representations for domain adaptation,” _Advances in neural information processing systems_ , vol. 20, 2007.
  * [25] P. Stojanov, Z. Li, M. Gong, R. Cai, J. Carbonell, and K. Zhang, “Domain adaptation with invariant representation learning: What transformations to learn?” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 24 791–24 803, 2021.
  * [26] Y. Zhang, T. Liu, M. Long, and M. Jordan, “Bridging theory and algorithm for domain adaptation,” in _International conference on machine learning_. PMLR, 2019, pp. 7404–7413.
  * [27] Y. Mansour, M. Mohri, and A. Rostamizadeh, “Domain adaptation with multiple sources,” _Advances in neural information processing systems_ , vol. 21, 2008\.
  * [28] J. Liang, D. Hu, and J. Feng, “Do we really need to access the source data? source hypothesis transfer for unsupervised domain adaptation,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 6028–6039.
  * [29] S. M. Ahmed, D. S. Raychaudhuri, S. Paul, S. Oymak, and A. K. Roy-Chowdhury, “Unsupervised multi-source domain adaptation without access to source data,” in _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2021, pp. 10 103–10 112.
  * [30] G. Shachaf, A. Brutzkus, and A. Globerson, “A theoretical analysis of fine-tuning with linear teachers,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 15 382–15 394, 2021.
  * [31] M. Belkin, D. Hsu, and J. Xu, “Two models of double descent for weak features,” _SIAM Journal on Mathematics of Data Science_ , vol. 2, no. 4, pp. 1167–1180, 2020.
  * [32] L. Collins, H. Hassani, A. Mokhtari, and S. Shakkottai, “Exploiting shared representations for personalized federated learning,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 2089–2099.
  * [33] S. Boyd and L. Vandenberghe, _Convex optimization_. Cambridge university press, 2004.
  * [34] V. Koltchinskii and K. Lounici, “Concentration inequalities and moment bounds for sample covariance operators,” _Bernoulli_ , vol. 23, no. 1, pp. 110–133, 2017.
  * [35] N. S. Chatterji, P. M. Long, and P. L. Bartlett, “The interplay between implicit bias and benign overfitting in two-layer linear networks,” _Journal of machine learning research_ , vol. 23, no. 263, pp. 1–48, 2022\.
  * [36] A. Singh, “Clda: Contrastive learning for semi-supervised domain adaptation,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 5089–5101, 2021.
  * [37] S. Mishra, K. Saenko, and V. Saligrama, “Surprisingly simple semi-supervised domain adaptation with pretraining and consistency,” in _NeurIPS 2021 Workshop on Distribution Shifts: Connecting Methods and Applications_.