The Power and Limitation of Pretraining-Finetuning for Linear Regression under Covariate Shift
Authors: Jingfeng Wu
Difan Zou
Vladimir Braverman
Quanquan Gu
Sham M. Kakade
Venue: NeurIPS 2022 Accept (2022)
Keywords: covariate shift
linear regression
risk bound
pretraining
finetuning

Abstract: We study linear regression under covariate shift, where the marginal distribution over the input covariates differs in the source and the target domains, while the conditional distribution of the output given the input covariates is similar across the two domains. We investigate a transfer learning approach with pretraining on the source data and finetuning based on the target data (both conducted by online SGD) for this problem. We establish sharp instance-dependent excess risk upper and lower bounds for this approach. Our bounds suggest that for a large class of linear regression instances, transfer learning with $O(N^2)$ source data (and scarce or no target data) is as effective as supervised learning with $N$ target data. In addition, we show that finetuning, even with only a small amount of target data, could drastically reduce the amount of source data required by pretraining. Our theory sheds light on the effectiveness and limitation of pretraining as well as the benefits of finetuning for tackling covariate shift problems.

The Power and Limitation of Pretraining-Finetunng for Linear Regression under Covariate Shift
Jingfeng Wu" Johns Hopkins University uuujf@jhu. edu
Difan Zou' The University of Hong Kong dzou@cs hku.
Vladimir Braverman
Johns Hopkins University vovaêcs jhu.
edu edu
Quanquan Gu
Sham M. Kakade
University of California, Los Angeles qguêcs. ucla. edu
Harvard University
sham@seas harvard. edu
Abstract
We study linear regression under covariate shift, where the marginal distribution over the input covariates differs in the source and the target domains, while the conditional distribution of the output given the input covariates is similar across the two domains. We investigate transfer learning approach with pretraining the source data and finetuning based on the target data (both conducted by online SGD) for this problem. We establish sharp intance-dependers excess risk upper and lower bounds for this approach. Our bounds suggest that for a large class linear regression instances, transfer learning with O source data (and scarce or no target data) is as effective as supervised learning with N target data. In addition, show that finetuning, even with only small amount of target data, could drastically reduce the amount of source data required by pretraining. Our theory sheds light on the effectiveness and limitation of pretraining as well the benefits of finetuning for tackling covariate shift problems.
Introduction
In transfer learning [Pan and Yang 2009 (Sugiyama and Kawanabe, 2012 algorithm is provided with abundant data from a source domain and scarce or no data from a target domain, and aims to train model that generalizes well the target domain. A simple yet effective approach is pretrain a model with the rich source data and then finetune the model with the available target data via, e.g.. stochastic gradient descent (SGD) (see, e.g., Yosinski al. (2014)) ). Despite its wide applicability in based transfer learning framework is
practice, the power and limitation of the pretraining wwwtiiiinn-fieetunin not fully understood in theory. The focus of this work is consider this issue in specific transfer learning setup known as covariate shift [Pan and Yang. 2009 Sugiyama and K Kawanabe) 2012). where the source and target distributions differ their marginal distributions over the input, but coincide in their conditional distribution of the output given the input.
Regarding the theory of learning with covariate shift, there exists rich set of results Ben-David
et al. 2010 Germain et al.
2013
Mansour et al., 2009 Mohri and Muñoz Medinal 2012 Cortes and
Mohri 2014 Cortes et al.
Cortes
2019
K Kpotufe and Martinet 2018 Hanneke and Kpotufe 2019 Ma et al.
2022 for the (regularized) empirical risk minimizer, which minimizes the empirical loss over the
source data and target data (if available) with potential regularization terms (e.g., fg-regularizzaton))
However, in most of these works [Bn--aavdd et al. 2010 Germain et al., 2013) Mansour el al. 2009
Mohri and Muñoz Medinal 2012
Cortes and Mohri 2014 Cortes al. 2019], the generalization
"Equal Contribution
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

error on the target domain is bounded by the sum of a vanishing term (e.g.. the training error) and divergence between the two domains (see, e.g.. discussions in Kpotule and Martinet (2018], J, with few notable exceptions that we will discuss later). Such bounds are very pessimistic because the additive error contributed by the source-target divergence only captures the worst case performance gap caused by distribution mismatch [David et al. 2010] and is too crude to describe the intriguing properties pretraining-finttune
across different domains.
In this paper, we take a different approach to directly study the generalization performance of the pretraining finetuning method. In particular, we consider linear regression under covariate shift, and an online SGD estimator which is firstly trained with the source data and then finetuned with the target data. We derive target domain risk bound that is stated as a function of (i) the spectrum of the source and target population data covariance matrices, (ii) the amount of source and target data, and (iii) the (initial) stepsizes for pretraining and finetuning (see Theorem 3.1 for more details). Moreover, nearly matching lower bound is provided to justify the tightness of our upper bound. The derived bounds comprehensively characterize the effects of pretraining and finetuning for each covariate shift problem and each algorithm configuration, based on which we make the following important observations:
We compare the generalization performance (i.e., target domain excess risk) of pretraining (with source data) vs. supervised learning (with target data). We show that, for a large class of problems, O(N2) source data is sufficient for pretraining to match the performance of supervised learning with N target data.
We next show the benefits of finetuning with scarce target data. In particular, for the problem class considered before, finetuning can reduce by at least constant factors the amount of source data required by pretraining. Moreover, there exist problem instances for which the pretraining- finetuning approach requires polynomially less amount of total data than pretraining (with source data) or supervised learning (with target data).
Finally, our bounds can also be applied to the supervised learning setting, i.e.. linear regression with last iterate SGD. In this case, our upper bound sharpens that of Wu al. [2021] by a logarithmic factor, and as consequence we close the gap between the upper and lower bounds for last iterate SGD when the signal-to-noise ratio is bounded.
Notation. For two positive-value functions f(x) and g(z) we write f(x) S g()) or f(x) Z g(x) if f(x) S cg(x) or fxr 2 cg(z) for some absolute constant e > 0 respectively, and we write f()) ~ g(x) if fxx) S g(z) S f(x). For two vectors u and v in a Hilbert space, their inner product is denoted by (u, v) or equivalently, =vv. For matrix A, its spectral norm is denoted by ||Al| 2 For two matrices A and B of appropriate dimension, their inner product is defined as (A, B) == tr(A B). For positive semi-definite (PSD) matrix A and a vector v of appropriate dimension, we write ||v| :=v Av. For symmetric matrix A and PSD matrix B, we write | := | 3 AB à I12. The Kronecker/tensor product is denoted by @. For a set S, we use [S] to
())
denote its cardinality.
1.1 Additional Related Work
We review some additional works that are mostly related to ours.
Learning under Covariate Shift. Kpotufe and Martinet [2018) Pathak et al. (2022) proposed new similarity measures to the source and target domains, and proved covariate shift bounds that do not contain an additive error of the divergence between the source and target distribution. Compared to results, theirs can be applicd to nonlinear regression/Classifccatee of linear regression, our bounds are more fine- inne-grained and are tight upto constant factors for a broad class of problems (see Theorem 3.2), beyond being only optimal in the worst case.
well; however in the case
is worth noting that Hanneke and Kpotufe [2099] studied the value of target data in addressing covariate shift problems. Their discussion is based on the minimax risk bounds afforded by given number of source and target data. In contrast, our discussion on the benefits of finetuning with target data is based on a completely different perspective, which is by comparing the sample inflation [Bahadur 1967 1971 Zou et al. [2021a] between cetraaning-finetunii vs. pretraining vs. supervised learning, I.c.. for each covariate shift problem instance, how much source (and target) data

---

are necessary for pretraning (and finetuning) to match the performance of supervised learning with certain amount of target data.
More recently, Ma et al. [022)] studied covariate shift problem in the nonparameteric kemnl regression setting, with the assumption that the density ratio (or second moment ratio) between the target and source distribution is bounded. Their results are similar to ours in that their bounds reflect the effect of the spectrum of the source population data covariance. Since our results are dimension-free, our bounds can also be applied in the nonparameteric kernel regression setting. There are two notable differences: firstly, their estimator is (weighted) ridge regression and ours is given by SGD; moreover, our results do not rely on the bounded density ratio or bounded second moment condition.
In addition, there is a vast literature constructing e.g., importance weighting methods [Shimodaira] 2000, Cortes et al., 2010) and learning invariant representations [Arjovsky et al. 2019: Wu al. 2019]. mention few. Along this line, Lei et al. [202T] proposed nearly minimax optimal estimator for linear regression under distribution shift, but their method relies on the knowledge of target population covariance matrix. Developing new transfer learning algorithms is beyond the agenda in this paper.
cample-efffciiee transfer learning algorithms,
The pretraining and finetuning discussed in this work are both conducted by online SGD, therefore our results are closely related to the generalization analysis of online SGD for linear regression in the supervised learning context [Bach and Moulines 2013] Dieuleveut et al. 2017 Jain
SGD.
et a Ge et al., (019 Zou et al. [021b]] Varre et al,] Wu et a [001]]. From technical
point of view, theoretical results be viewed as extension of the SGD analysis from the supervised learning setting to the covariate shift setting.
2 Problem Setup
Transfer Learning. We use denote covariate in Hilbert space (that can be d-dimensional or countably infinite dimensional), and E IR to denote its response. Consider a source and target data distribution, denoted by Decurce and Pearget respectively. In the problem of transfer learning, we are given with M data sampled independently from the source distribution, and N data sampled independently from the target distribution (where N & M or even N 0), denoted by
M-N where (x;, vi) ~ { (Dsource i= I,.....,AA M; (x,, MT
( (Deagees i= M +
M
The goal of transfer learning is to learn a model based on the M + N data that can generalize on the target domain. We are particularly interested in the covariate shift problem in transfer learning, where the source and target distributions satisfy: Decurce = - (y x) but Peource(X) of Dearget(x).
Linear Regression under Covariate Shift. A covariate shift problem is formally defined in the context of linear regression by Definitions 1 Z
Definition 1 (Covariances conditions). Assume that each entry and the trace of the source and target data covariance matrices are finite. Denote the source and target data covariance matrices by
G
E Exrare [xx
==
E Exaar [xx ].
respectively, and denote their eigenvalues by (14) and (A:)221, respectively. For convenience assume that both G and H are strictly positive definite. Definition 2 (Model conditions). For parameter w, define its source and target risks by
1 Risksource (w) E.D.nra (y w xx),, Riskearger (w) 2 E. (y w wTwx
xx)²
Assume that there is a parameter w that simultaneously minimizes both source and target risks. i.e., w E arg min Riskgource (w) O arg minw Riskearges (w). For convenience assume that w" unique.
respectively.
We remark that the strict positive definiteness of G and H in Definition and the uniqueness of w² in Definition are only made for the ease of presentation. Otherwise one can set w" to be the minimum-nome solution, i.c., w" m E arg min Ri Riskgouree (w)

---

arg minw Risktarget (wergeet()):.r) [w). and our results still hold. This argument also holds in reproducing kernel Hilbert space [Schölkopf al.) 2002].
Our definitions of linear regression under covaraite shift follow from Lei et al. 2021 Ma et al. (2022). In the literature, covariate shift problem often assumes the source and target distributions differ in their marginal distributions over the input, but coincide in their conditional distribution of the output given the input (see, e.g., Sections 1.3.3 and 1.3.4 in Sugiyama et al.) (2022). When applied to the well-specified linear regression models, i.e., Ely x X w for some parameter w", the latter condition turns out to require the optimal parameter w identical for both source and target domains. Therefore, the problems described by Definitions [ linear regression problems under standard covariate shift conditions.
and 2 incclude at least all well-specified
Excess Risk. For linear regression under covariate shift, the performance of a parameter w is measured by its target domain excess risk, i.e.,
ExcessRisk(w) w) Riskgarget (w) Risktarget (w") (H. (w w") & (w w")).
SGD. The transfer learning algorithm of our interests is pretraining finetuning via online stochastic gradient descent with geometrically decaying stepsize ( (SGD). Without lose of generality, we assume the SGD iterates initialized from Wo O. Then the SGD iterates sequentially updated as follows:
W - M- M-1 (x:x, Wi-1 x,y:), t= I,....,, M N,
10/22 0st M, f= [t/log(M]];
(SGD)
where 7/- 1TM/2', M MSLKN. 8= == 1(1 M)/log(N)]
and the output is the last iterate, i... WM+N- Here "No and YM two hyperparameters that correspond to the initial stepsizes for pretraining and finetuning, respectively. In both pretraining and finetuning phases, the stepsize scheduler in (SGD is epoch-wisely constant and decays geometrically every certain number of epochs, which widely used in deep learning (He et al. 2015 We note that such (SCD) for linear regression has been analyzed by [e al. 2019], Wu al. [021 in the context of supervised learning. Our goal this work to understand the generalization of (SGD) in
the covariate shift problems.
Assumptions. The following assumptions Zou et al. 2021b Wu et al. 2021 are crucial in our analysis.
Assumption (Fourth moment conditions). Assume that for both source and target distribution the fourth moment of the covariates is finite. Moreover:
A There is constant a: > such that for every PSD matrix A it holds that
[Xx Axx 1 3 a tr(GA) -G, Ex [xx] Axx (rA)) H. a
Clearly, it must hold that 1
B There is constant 3 > 0 such that for every PSD matrix A it holds that
E. [xx] Axx 1- - B-tr(GA).G. B [xx Axx 1-HAH Z (-tr(HH)
Assumption 1 holds with 3 and 8 = given that Daourea (x) = NO G) and D Drangat (x)
(O, H). Moreover, Assumption IA holds if both H 1. . Deource(x) and G Deargor (x) have sub-Gaussian tails [Zou al. 202166 For more exemplar distributions that satisfy Assumption we refer the reader to Wu et al. 20221.
Assumption (Noise condition). Assume that there is constant 0² such that
E D [ly (w", x) )xx 22. G, EDarne 1'y (w" x)) xx 1 02 H H.
Assumption 2 puts mild requirements on the conditional distribution of the response given input covariates for both source and target distribution. In particular, Assumption 2 is directly implied by the following Assumption 2 for well-specified linear regression model under covariate shift.
For the conciseness of presentation we focus on SGD with geometrically decaying stepsizes. With the provided techniques, our results can be easily extended to SGD with tail geometrically decaying stepsizes Wu
al. 2021 as well.

---

Assumption2 2 (Well-specified noise). Assume that for both source and target distributions, the response (conditional on input covariates) is given by
= w' + where (0, o²) and is independent with x.
Additional Notation. Let N 2,.. }. For an index set IK N+, its complement is defined by K = N+ K. Then for an index set C N4 and scalar a 2 0, we define
Hg Σ XEX
ENNT H = = v.y, alg Hg = Σ av.V + EANAS EK
TEK
where (A.)a21 and (v:)121 are corresponding eigenvalues and eigenvectors of H. One can verify that H is equivalent to the (pseudo) inverse of Hg. Similarly, we define Gj. Gj and aIj - Gje according to the eigenvalues and eigenvectors G.
Main Results
An Upper Bound. We begin with presenting upper bound for the target domain excess risk achieved by the pretraining-fietuiing method.
Theorem 3.1 (upper bound), Suppose that Assumptions AA and hold. Let WM+N be the output of SCD Ler Mess == M/ log(M), Nest == N/ No Suppose that Yo: YM s
min(1/(4a tr G),, 1/(4a tr (H))). Then it holds that
ExcessRisk| (MM+)) & BiasError + VarError. Moreover, for any two index sets J,K. KK C. N4, it holds that
Diinatuee Dest Most
VarError $ 0².
Norr
I M+N-1 (I I (I) I M-1 (I G-):))(Wo wi)l -
BiasError
H
Finatuna
t Woo - -w" w=|
Metroo
+G
Mett
t [ (I- G) w*) 1
[o w011
Datt
NerrM
Ix
Hg=
Marroo
GJc
Nost
where
Dinetune off
:= tr (II HI- (GJ + +M Gj+)),
Dort == |K| + N2 72 Σigk X3
In particular, the upper bounds are optimized when
== =j: 2 Mart),
K= (k d 2 1/(TM Nott))-
(2)
The upper bound in Theorem 3.1 contains a bias error stemming from the incorrect initialization We * w", and variance error caused by the additive label noise y- T w* * In particular, Mott and Nott are the effective number of source and target data, respectively, due to the effect of the geometrically decaying stepsizes in (SCD) Moreover. Dest can be regarded the effective dimension of supervised learning [Wu et al. 2021 and Dfinetune can be regared as the effective dimension of finriiininn-itttuningg.. Note that Di Denee is determined jointly by the spectrum the source and target population covariance matrices as well as the stepsizes for pretraining and finetuning.
To better illustrate the spirit of Theorem 3.1
let us consider an example where |/wo w w 0² 7o ~ 1, and (r( = (H) x 1 (so that the spectrum of G and H must decay fast), then the bound in Theorem 3.1 vanishes provided that
Dott = o(Ness),
D
Finetune = o( o(Mots).
(3)
For the first condition in to happen one needs
K
o(N/ log N),
TM Σ o(log N/N),

---

which can be satisfied when (i) the number of target data N is large and the finetuning stepsize Yar or when (ii) N is small and YM is also small (which can depend on N). The second condition in (3) can happen under various situations, e.g., when (i) N is large and yM 1, or when (ii) N, 7MM are small but the amount of source data M is large and that
tr(HG = / log M), tr(HG = ollog M/M),,
which will hold when G aligns well with H (as sanity check these hold automatically when G = H and M is large). To summarize, in case (i) the amount of target data is plentiful so that finetuning with large stepsize leads to generalization (which is essentially supervised learning); and in case (ii), even though the target data scarce, pretraining with abundant source data can still generalize given that the source and target population covariance matrices are well aligned.
A Lower Bound. The following theorem provides a nearly matching lower bound.
Theorem 3.2 (lower bound). Suppose that Assumptions ABand
and hold. Let WM4N be the output of SSDD. Let Mort == M/ (M), Nott :- N/ log(N), and suppose that Motts Nott 10. Suppose that To < 1/|| G
2. YM < H| Then it holds that
ExcessRisk (M++)) BiasError VarError.
Moreover, for the index sets K. and defined in it holds that
VarError 20² 0².
( Mees
Dilpotume Dott
Not1
BiasError 2
M
M4N-1N (I- HH) Mo (I- 1 G w')l"
+ |wo w" 1
Diinetune
off
+ 8-
M-1 || 1=0 (I 71 Gwo w*)
w')l
Dost
Merr
Hg Nott
where Datt and Dtinatuna are as defined in ① att
The lower bound in Theorem 3.2 suggests that the upper bound in Theorem 3.1 is tight upto constant factor in terms of variance error, and is also tight in terms of bias error except for the following additional parts in the respective places:
t 7 (wo w*)
Wo
Wo
w
GG
Natt"ar
Marr"o
In partieular, the upper and lower bounds match ignoring constant factors provided that
Iwo w o?
|| 7: G)( -
(G)(w)/w")] o²
which hold in a statistically interesting regime where the signal-to-noise ratios, [W w w=112/022
[Wo w /2 are bounded and G commutes with H.
Implication for Pretraining. If target data is unavailable, Theorems 3. and 3.2 imply the following corollary for pretraining.
Corollary 3.3 (Learning with only source data). Suppose that Assumptions and 2 hold. Let WM+0 be the output of (SGD) with M >> 100 source data and target data. Suppose that ? == % < 1/(4oxt((H) Then it holds that
ExcessRisk(Wai. <
[ M- (I GG) w"]l (allwo w'l Marry GG
+ +022
Mul
where Deretrain = tr( Mats yr(H) and I N+ can be any index set. If in
addition Assumptions 10 and 2 hold, then for the index set defined in (2) it holds that
ExcessRisk(
MIM-- (I w*) + (B1l w' +
D
Marr
Corollary 3.3
sharply characterizes the generalization of pretraining method, and is tight upto constant factors provided with a bounded hignal-to-noise ratio, i.e., || w S o². Corollary 3.3 can be interpreted in similar way Theorem 3.1 Moreover, these sharp bounds for pretraining and meerainnin-finetunnng enable us to study the effects of pretraining and finetuning thoroughly, which will do in Section[4
Implication for Supervised Learning. As bonus, we can also apply Theorems 3.1 and 3.2 in the setting of supervised learning.

---

and hold. Let Wo+N be the output of (SGD) with 0 source data and N 100 target data. Suppose that y == 7M < 1/(4a(tr(Gi)) Then it holds that
Corollary 3.4 (Learning with only target data). Suppose that Assumptions AL
ExcessRisk(wo-H) &
N- I (W w + (allwo-ww1f
+ o²
Dure Nore
Hge
Notth
where Deet is as defined in [ and K. Nr can be any index set. If in addition Assumptions and
hold, then for the index set K. defined in ② it holds that
ExcessRisk(Wo+N) 2
I ( H) - wn) + w" + o²)
Dase Nott
We remark that the upper bound in Corollary 3.4 improves the related bound in Wu et al. logarithmic factor, and matches the lower bound upto constant factors given that WW w
2021 by
H of.
For more detailed comparison between the bounds in Theorem 3.1 Corollaries the reader to Table iin Appendix A
and
we refer
4 Discussions
With the established bounds, we are ready to discuss the power and limitation of pretraining and finetuning by comparing them to supervised learning.
The Power of Pretraining. For covariate shift problem, pretraining with infinite many source data can learn the true model. But when there are only finite number of source data, it is unclear how the effect of pretraining compares to the effect of supervised learning (with finite many target data). Our
next result quantitatively address this question by comparing Corollary 3.3 with Corollary 3.4
Theorem 4.1 (Pretraining vs. supervised learning). Suppose that Assumptions and 2 hold. Let
Wo+ND be the output of (SGD) with optimally tuned initial stepsize, source data and N 100
target data. Let WM+0 be the output of (SGD) with optimally tuned initial stepsize, M source data
and 0 target data. Let Mest == M/ log log(M), Naa == Nat log( (.t). Suppose all SGD methods are initialized from O. Then for every covariate shift problem instance (w", H. G) such that H. G commute, holds that
ExcessRisk(WMHH) $ (1 + /22//) ExcessRiss(WoHar
provided thut
|| |G aD=1
Mots 2 (Nel eff!
where
K (k: d 2 1/(Net
KK*| + (Nal oft??
22
X2
aff
ig
and 2 < ||/ refers to the optimal initial stepsize for supervised learning.
We now explain the implication of Theorem 4.1 First of all, it of statistical interest to consider signal-to-noise ratio bounded from above, i.e., ||
/02 1/////// S 1. Note that De) 2 1 when Nel
large. Moreover, recall that |K* < De = ((Ne) eft) when supervised learning can achieve a vanishing excess risk. Finally, |[g- |G = |
S 1 can be satisfied if the top K o( (Ne),) eigenvalues subspace of H mostly falls into the top eigenvalues subspace of G. Under these remarks, Theorem 4.1 suggests that: in the bounded signal-to-noise cases, pretraining with ((N²) source data no worse than supervised learning with N target data (ignoring constant factors), for every covariate shift problem such that the top eigenvalues subspace of the target covariance matrix aligns well with that of the source covariance matrix.
The Power of comparing Theorem 3.1 with Corollary 3.4
www.hiinnn--neuuninnn..m We next discuss the effect of pretraining-fnettningg by
Theorem 4.2 (Pretraining- finnrinngnietunnnggggg vs. supervised learning). Suppose that Assumptions 7 Nand 2 hold. Let Wo+N= be the output of (SCD) with optimally tuned initial stepsize, source data and Nel 100 target data. Let WM+N be the output of (SGD) with optimally tuned initial stepsize,
7

---

M source data and N target data. Let Mest == M/ (M), Nest == N/log(N) Nate == / /lgg((")))). Suppose all SGD methods are initialized from O. Then for every covariate shift problem instance (w", H. G) such that H, G commute, it holds that
(roosRRis(WM4+h) 2 (1 a a|| ll ExcessRisk(WoxNaa)
provided that
4 H ||
Mott 2 aerr) )2
a
off
where
Ki = {k: Net log(
[Net att) tr tr(H) > d 2 1/ ? C CK,
and K", D yoh are as defined in Theorem 4.7
Theorem can be interpreted in similar way Theorem 4.1 The only difference is that Theorem puts milder condition regarding the alignment of H and G than Theorem 4.1 In particular, Theorem[422 only requires the "middle" eigenvalues subspace of H mostly falls into the top eigenvalues subspace of G. Moreover, the index set K shrinks (hence ||Hgr ||c decreases) as the number of target data for finetuning increases. This indicates that finetuning can help save the amount of source data for pretraining.
The Limitation of Pretraining vs. the Power of Finetuning. The following example further demonstrates the limitation of pretraining and the power of finetuning.
Example 4.3 (Pretraining-fiettune sufficiently small constant. Consider a covariate shift problem instance given by
vs. pretraining vs. supervised learning). Let > be a
11,1,0,0,.... _T, o² o==1,
H =
diag(1, 0.5
0.5 0, O.O....):
G diag( (,,,,0,,....))
2.5 copies
One may verify that (r(H) ~ (r(GrG ~ and that |w" for the (SGD) outpul:
H ~ w l1 R = R 1. The following holds
supervised learning: for ExcessRisk(wo,) < e, it is necessary to have that N 2 e c-5,
pretraining: for ExcessRisk(WMHH) < it is necessary have that M Z 22
pretrain-finctuning: for ExcessRisk(WMHN < it suffices to set no TM e, and M = - log(e N -
It is clear that whenever target data are available, the optimally tuned pretraining meeraining-finetuning method always worse than the optiamlly tuned pretraining method, one can simply the finetuning stepsize to be small (or zero) so that the former reduces to the latter. Moreover, Example 4.3 shows covariate shift problem instance such that pretraining Secrraning--inetuningg can save polynomially amount of data compared to pretraining (or supervised learning). This example demonstrates the limitation of pretraining and the benefits of finetuning. As a final remark for Example 4.3 direct
computation implies that K = (1,2,.... 2.- -05 + 1) and Kt (2.3....,24 -0.5 + }. therefore
2c
>
H |c 0... so the implication of Example 4.3 is consistent consstennt with Theorems
4.1 and 4.2
Numerical Simulations. We perform experiments synthetic data to verify our theory. The code and data for our experiments can be found on Github Recall that the effectiveness of pretraining and finetuning depends on the alignment between source and target covariance matrices, therefore we design experiments where the source and target covariance matrices are aligned at different levels. In particular, we consider commutable matrices and H with eigenvalues {ur2> {i 2)22 and respectively. To simulate different alignments between G and H. we first sort
(A))21 = (i-1.5 (i-1.5) 1 them so that both of their eigenvalues are descending order, and then reverse the top-k eigenvalues
https//ggihhbb.com/ccllam/pppeee finetune-Seee
8

---

Source Data
Targel Data
Source Data
Target
0.5
Source Data
Target
Excees Riak
0.3
Protrain
Excess Risk
Protrain
0.4
Finetune
finetune
0.3
0--
Supervise
Supervise
0.2
Pretrain
01-
Finetune
40
60-
0
2000
4000
2000
4000
2000
4000
2000
4000
0
2000
4000
2000
4000
Sampie Size
Sample Size
Sample Size
(a) Problem P(A 5)
(b) Problem P(k 10)
(c) Problem P(k 20)
Figure 1: generalization comparison between pretraining, pretraining-finetninngg and supervised learning. For cach point in the curves, its x-axis represents the sample size and its y-axis represents the excess risk achieved by an algorithm with the corresponding amount of samples under the optimally tuned stepsizes. For the pretraining curves, the sample size refers the amount of source data and the sample size appeared in the right half of the plots should be added by 5, 000. The finetuning curves are generated from an initial model pretrained with 5, 000 source data and its sample size refers the amount of target data. For supervised learning curves, the sample size refers to the amount of target data. The problem instances P(A: 5). P(k = 10), and P(k 20) The problem dimension is 200. The results averaged over 20 independent
are designed according repeats.
of G. In mathematics, for given l > 0, the problem instance P(k) := (w" H, G, G is designed as follows:
(k 1)15..... ... G diag
1
H diag
1.
2 1,
(k: + 1)2 15a....)
21.5 22.5'... ... k1.5
k2
(4)
w = (1.1,.... 1/(k + 1), 1/(1/ + 2).....
=
k cupies
One can verify that (r(H) x tr(() ~ 1 and that ||w | ~ ||w" ~ 0² ~ 1. Clearly, a larger k implies worse alignment between G and H. We then test three problem instances P(k 5). P(k = 10), and P(k = 20), and compare the excess risk achieved by pretraining, pretraining- finetuning, and supervised learning. The results are presented in Figure which lead to the following informative observations:
For problem P(k 5) where H and G are aligned very well, pretraining (without finetuning!) can already match the generalization performance supervised learning. This verifies the power of pretraining for tackling transfer learning with mildly shifted covariate.
For problem (A = 10) where H and G are moderately aligned, there is a significant gap between the risk of pretraining and that of supervised learning. Yet, the gap is closed when the pretrained model is finetuned with scarce target data. This demonstrates the limitation of pretraining and the power of finetuning for tackling transfer learning with moderate shifted covariate.
For problem P(k = 20) where H and G are poorly aligned, the risk of pretraining can hardly compete with that of supervised learning. Moreover, for finetuning match the performance of supervised learning. it requires nearly the same amount of target data as that used by supervised learning. This reveals the limitation of pretraining and finetuning for tackling transfer learning with severely shifted covariate.
5 Concluding Remarks
We consider linear regression under covariate shift, and a SGD estimator that is firstly trained with source domain data and then finetuned with target domain data. We derive sharp upper and lower bounds for the estimator's 's target domain excess risk. Based on the derived bounds, we show that for a large class of covariate shift problems, pretraining with O(N²) source data can match the performance of supervised learning with N target data. Moreover, we show that finetuning with scarce target data significantly reduce the amount of source data required by pretraining. Finally, when applied to supervised linear regression, our results improve the upper bound in [Wu et al. 2021] by logarithmic factor, and close its gap with the lower bound (ignoring constant factors) when the signal-to-noise ratio is bounded.
Several future directions worth discussing.

---

Model Shift. An immediate follow-up problem is to extend our results from the covariate shift setting to more general transfer learning settings, e.g., with both covariate shift and model shift, where the true parameter w" could also be different for source and target distributions. Under model shift,
the power of pretraining with source data is limited, and we expect that finetuning with target data becomes even more important.
Ridge Regression. For anfinite-dimensiinn least-squares in the supervised learning context, instance- wisely tight bounds for both ridge regression and SGD have been established by |Bartlett et al. (2020), least- wisely tight bounds for SGD. As ridge regression is popular in covariate shift literature (see Ma al. [2022] and references herein), an interesting future direction is studying the settance-wislly tight bounds for ridge regression in the setting unfnite-dimensionn least-squares under covariate shift tight bias analysis of particular interest.
Tsigler and Bartlett 2020 Zou al. [2021b], Wu et al. [202T]. For
squares under covariate shift, this paper presents nearly
Unlabeled Data. In this work we assume the provided source and target data are both labeled. However in many practical scenarios, additional unlabeled source and target data are also available. In this case our results cannot be directly applied remains unclear how to utilize unlabeled data with SGD. An important future direction is to extend our framework to incorporate with unlabeled source and target data.
Acknowledgments and Disclosure of Funding
We would like to thank the anonymous reviewers and area chairs for their helpful comments. This work done when DZ was Ph.D. student at UCLA. DZ is partially supported by Bloomberg data science Ph.D. fellowship and his startup funding in the institute of data science, the University of Hong Kong. JW and VB are supported by the Defense Advanced Research Projects Agency (DARPA) under Contract No.
QG partially supported by the National Science Foundation award IIS- 19061696 and IIS- 200998. J. SK acknowledges funding from the Office of Naval Research under award N00014-22-15 1--377 and the National Science Foundation Grant under award CCF-1700577 The views and conclusions contained in this paper those of the authors and should not be interpreted as representing any funding agencies.
References
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint arXiv:
2019.
Francis Bach and Eric Moulines. Non-strongly-conwe smooth stochastic approximation with convergence rate o(1 (1/n). Advances in neural information processing systems, 26.773-781,
Raghu Raj Bahadur. Rates of convergence estimates and test statistics. The Annals of Mathematical Statistics, 38(2):303-322 1967.
Raghu Raj Bahadur. Some limit theorems in statistics. SIAM, 1971.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 2020.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 19(5):111-77, 2010.
Corinna Cortes and Mehryar Mohri Domain adaptation and sample bias correction theory and algorithm for regression. Theoretical Computer Science, 519:103-126, 2014.
Corinna Cortes, Yishay Mansour, and Mehryar Mohri. Learning bounds for importance weighting.
Advances in neural information processing systems, 23, 2010.
Corinna Cortes, Mehryar Mohri, and Andrés Munoz Medina. Adaptation based on generalized discrepancy. The Journal of Machine Learning Research, 20(1):1330, 2019.
10

---

Shai Ben David. Tyler Lu, Teresa Luu, and Dávid Pál. Impossibility theorems for domain adaptation. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pages 129-136. JMLR Workshop and Conference Proceedings, 2010.
Aymeric Dieuleveut, Nicolas Flammarion, and Francis Bach. Harder, better, faster, stronger con- vergence rates for least-squares regression. The Journal of Machine Learning Research, 18(1): 3520-3570, 2017.
Rong Ge, Sham M Kakade, Rahul Kidambi, and Praneeth Netrapalli. The step decay schedule: A optimal, geometrically decaying learning rate procedure for least squares. arXiv preprini arXiv: 12838, 2019.
Pascal Germain, Amaury Habrard, François Laviolette, and Emilie Morvant. A pac-bayesian approach for domain adaptation with specialization to linear classifiers. In International conference on machine learning, pages 738-746. PMLR, 2013.
Steve Hanneke and Samory Kpotufe. On the value of target data in transfer learning. Advances in Neural Information Processing Systems, 32, 2019.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. corr abs/ thbs/11120 5512.0338 (2015), 2015.
Prateek Jain, Sham M Kakade, Rahul Kidambi, Praneeth Netrapalli, Venkata Krishna Pillutla, and Aaron Sidford. A markov chain theory approach to characterizing the minimax optimality of stochastic gradient descent (for least squares). arXiv preprint arXiv:1710.0945: 09430, 2017a
Prateek Jain, Praneeth Netrapalli, Sham M Kakade, Rahul Kidambi, and Aaron Sidford. Parallelizing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecifiiation. The Journal of Machine Learning Research, 18( (1:8))8888299) 2017b.
Samory Kpotufe and Guillaume Martinet. Marginal singularity, and the benefits of labels in covariate- shift. In Conference On Learning Theory, pages 1882-1886. PMLR, 2018.
Qi Lei, Wei Hu, and Jason Lee. Near-optimal linear regression under distribution shift. In Interna- lional Conference on Machine Learning, pages 6164-6174. PMLR, 2021.
Cong Ma, Reese Pathak, and Martin Wainwright. Optimally tackling covariate shift in rkhs-based nonparametric regression. arXiv preprint arXiv:2205.02988. 2022.
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. arXiv preprint arXiv:0902.3333) 2009.
Mehryar Mohri and Andres Muñoz Medina. New analysis and algorithm for learning with drifting distributions. In International Conference Algorithmic Learning Theory, pages 124 138. Springer, 2012.
Sinno Jialin Pan and Qiang Yang. A survey transfer learning. IEEE Transactions on knowledge and data engineering, 22(10): (110)):345-11 1345-13599999 2009.
Reese Pathak, Cong Ma, and Martin J Wainwright. A new similarity measure for covariate shift with applications to nonparametric regression. arXiv preprint arXiv:2202.02837, 2022.
Bernhard Schölkopf, Alexander Smola, Francis Bach, et al. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of statistical planning and inference, 90(2):227-244, 2000.
Masashi Sugiyama and Motoaki Kawanabe. Machine learning in ota-stationary environments: Introduction covariate shift adaptation. MIT press, 2012.
Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori. Density ratio estimation in machine learning. Cambridge University Press, 2012.

---

Alexander Tsigler and Peter L Bartlett. Benign overfitting in ridge regression. arXiv preprint arXiv:2009.14286 2020.
Aditya Varre, Loucas Pillaud-Vivien, and Nicolas Flammarion. Last iterate convergence of sgd for least-squares in the interpolation regime. arXiv preprint arXiv:2102.03118. 2021.
Jingfeng Wu, Difan Zou, Vladimir Braverman, Quanquan Gu, and Sham M Kakade. Last iterate risk bounds of sgd with decaying stepsize for overparameterized linear regression. arXiv preprint arXiv:2110.06195, 2021.
Yifan Wu, Ezra Winston, Divyansh Kaushik, and Zachary Lipton. Domain adaptation with asymmetricall--relxxdd distribution alignment. International Conference on Machine Learning, pages 6872-6881. PMLR, 2019.
Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson. How transferable are features in deep neural networks? Advances in neural information processing systems, 27, 2014.
Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, Dean P Foster, and Sham Kakade. The benefits of implicit regularization from sgd in least squares problems. Advances in Neural Information Processing Systems, 34:5456-5468, 2021a.
Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham Kakade. Benign overfitting of constant-stepsize sgd for linear regression. In Conference on Learning Theory, pages 4633-4633 PMLR, 2021b.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethies review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions nceded to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [No] The reported mean behaviors in our experiments are sufficient support our theoretical results
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] Resources are not concern for our purpose of numerically verifying our theoretical results
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
12

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "tgMXbmuhhp2", "reviewer": "Reviewer_5qgQ", "summary": "This paper presents a theoretical study of the generalization performance of the pretraining-finetuning method with linear regression setting under covariate shift. Especially, this paper derives the upper and lower bounds for the generalization achieved by the pretraining-finetuning method. With the bounds, this paper characterizes the power of the pretraining, the pretraining-finetuning method, and the limitation of the pretraining compared to supervised learning.", "questions": "In line 263, \"middle\" eigenvalues subspace of H falls into the top eigenvalues subspace of G. Can you explain in more detail?", "limitations": "The paper seems fine to me in this regard.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is interesting and well-written. I think that this is a good paper that should be accepted. One minor concern is how standard Assumption1 is. If the assumption is standard or applies to any common distributions under covariate shift, it would be better to state it with some examples. \n\nIt would be better to summarize the bounds by showing a detailed comparison between only pretraining, pretraining-finetuning, and finetuning.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "IZbcYIg4ry7", "reviewer": "Reviewer_XiiA", "summary": "This paper investigates a transfer learning approach with pretraining on the source data and finetuning based on the target data and establishes sharp instance-dependent excess risk upper and lower bounds for this approach. ", "questions": "The regression problem is very old. What is the factual applications of the theoretical analysis?", "limitations": "The limitations of the presented analysis could be discussed in more detail.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Originality\n\nThe paper's idea is very novel. To the best of my knowledge, the theoretical analysis of the transfer learning paradigm remains unclear.\n\n### Quality\n\nThe technical part of the paper seems correct as far as I can see.\n\n### Clarity \n\nThe paper is well-written. \n\n### Significance\n\nThe question studied in the paper is significant. Understanding the power and limitation of pretraining-finetuning for linear regression under covariate shift is meaningful. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BnOZbALsc6K", "reviewer": "Reviewer_a3cN", "summary": "This paper studies the performance of one-pass SGD when pre-trained on a large linear regression source task and fine-tuned on a smaller linear regression target task with a mild degree of covariate shift. In this setting, O(N^2) data points from the source data are as effective as O(N) data points from the target task. The study is mostly theoretical based on a bias-variance decomposition where the bias term is due to limited iterations of the single-pass algorithm and the variance term is due to noise. An experiment verifies the results on a synthetic problem.", "questions": "See weaknesses section", "limitations": "See weaknesses section", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written and well organized. The proofs are in the appendix which was not checked but the arguments in the main paper are intuitive and convincing. The choice of algorithm and the domain shift make the findings less surprising as I will elaborate below, but the theoretical characterization in the paper may pave to way for more interesting results. Altogether I am voting for acceptance but I strongly recommend highlighting the following limitations in the introduction.\n\n1. All the results are on a quite benign form of covariate shift where the model reaches the same solution on both the source and the target task. Even if no data point is available from the target task, the model can reach zero error by training on the first task. This is where the power of pretraining largely comes from. The question is then how much training on the source task can slow down the optimization or hurt generalization compared to training on the target task.\n\n2. The studied algorithm is one-pass SGD. Optimization and generalization of this algorithm are connected together in a way that the insights from this paper may not extend to the more commonly used multi-pass SGD. The number of data points in one-pass SGD determines the number of iterations and how far the parameters can move towards the optimal solution. The limitation of pretraining appears to largely come from the fact that reducing the loss on the target task requires more iterations if training is on the source task instead of the target task. In single-pass SGD, since the number of iterations is equal to the number of data points, more iterations means more data points. Multi-pass SGD with limited data points can make up for this slow convergence with more epochs even if the number of data points is limited. I am not sure then if these findings on one-pass SGD about the number of required data points extend to multi-pass SGD. I suggest clarifying in the intro and abstract that this is a study of the performance of one-pass SGD under covariate shift and using applications of one-pass SGD in ML to highlight the significance.\n\nMinor comments:\n\n(i) Line 241 states that a bounded signal-to-noise ratio is of statistical interest. Is the ratio bounded from above here? And could you provide citations for the claim about statistical interest?\n\nTypos:\n- Line 262: regarding\n- Line 273: Supervised\n-----------------------------\nUpdate: The revision addressed my second comment and so I increased the score to 7. As for the first comment, although this assumption limits the applicability of the current result, I think analyzing the behavior of single-pass SGD under this assumption is still valuable.\n\nNote on clarity: Covariate shift has a rather standard definition in machine learning: The two tasks have the same conditional distribution p(y|x) but different marginal distribution p(x). See \"key assumption 1\" in [1] for example. As the reviewer df3S explained, if there is a chance of model misspecification, the assumption that the two tasks share the same optimal parameters does not follow from this definition. (An elaborate discussion is provided in [2].) Currently, the submission is including the assumption of shared optimal parameters in the definition of covariate shift. Even if some previous papers have defined covariate shift in this way, doing this would confuse a majority of readers who expect the standard definition of covariate shift. I strongly recommend separating this assumption from the definition of covariate shift and editing the corresponding statements in the paper to help with readability. One example is the sentence \"For covariate shift problem, pretraining with infinite many source data can learn the true model\" in line 230 in the revision.\n\n[1] Huang, Jiayuan, et al. \"Correcting sample selection bias by unlabeled data.\" NeurIPS, 2006\n\n[2] Shimodaira, Hidetoshi. \"Improving predictive inference under covariate shift by weighting the log-likelihood function.\" Journal of statistical planning and inference, 2000", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7XKQbqnb1z8", "reviewer": "Reviewer_df3S", "summary": "This paper investiage the covariate shift problem in a linear regression task. They assume there exits a w* that can simutanously achieves the optimal in both training and testing (target) domain.  They show a model trained on the training domain (with O(N^2) samples) can match the one trained on the target domain (with N samples). Also, they also show the benefits of finetuning on the target domain with limited data. From the technical side, they provide a sharpened upper bound (by a logarithmic factor)  and matched lower bound . ", "questions": "See Weakness.", "limitations": "See Weakness.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n    1) the paper is well motivated and clearly written.\n    2) I didn't check the proof, but the results seem correct to me.\n    3) the bounds are sharp and complete.\n\nMajor Weakness:\n    1) From my perspective, it is strong to assume a w* that is optimal for both domains (or the optimal set of the two domains overlap). This assumption is crucial for the main results such that a model trained with sufficient data in the training domain matches the performance of the one trained on target domain. Given the vast empirical results on the domain adaptation and generalization, there is no evidence that such w* exists or minimizing the training domain loss can lead to testing domain performance gain. I suggest the authors  the provide more supports for the this assumption.  I will change my rate after the rebuttal phase depending on the authors response to this concern. \n     \nMinor Weakness:\n    1) the notation is dense and the main thereom 3.1 is hard to follow, I suggest the authors to reformulate the results for better readability. \n    2) I think (if I am not wrong) the techniques used in this paper is not novel. It is an application of existing methods on the M+N setting.\n\n### Post Rebuttal Comment\n\nAfter the discussion with the authors, I thinks this paper makes an unreasonable assumption on the training and testing domains share the same optimal $w^*$ in a linear case.  **Though the conditional distribution can be the same in training and testing domain,  the optimal $w$ can still be different due to model misspecification (which is commonly the case in linear models).** In other words, if there is model misspecification, the optimal $w^*$ for the source domain is not optimal for the target domain. By assuming model misspecification, we mean the residual of $y-x^\\top w^*$ is not independent of $x$. So let assume $\\mathbb{E}_{\\mathbb{P}(y|x)}(y-x^\\top w^*)=g(x)$, where $g(x)$ is the non-linear part that can't be explained by a linear model. \n\nDenote the source domain with $s$ and target domain with $t$. Because $w^*$ is optimal for the source domain, then we have $\\mathbb{E}_s [x (y-x^\\top w^*)]=\\mathbb{E}_s [x g(x)] = 0$. However, because $P_s(x) \\neq P_t(x)$ and further $\\mathbb{E}_t [x g(x)] \\neq \\mathbb{E}_s [x g(x)] $, we have $\\mathbb{E}_t [x (y-x^\\top w^*) ] = \\mathbb{E}_t [x g(x)] \\neq 0$.\n\nIn conclusion, the $w^*$ optimal for source domain is **NOT** optimal for the target domain due to model misspecification and the shift of $P(X)$.\n\nIf one assumes $w^*$ is simutanously optimal for both domains, then we must assume $E_s [x g(x)] = E_t [x g(x)]$ even when $P_s(X) \\neq P_t(X)$, which is a prohibitively strong assumption that I have not seen in the existing literature. I think it only holds in rare cases. \n\nDue to this concern that the results of the paper only hold in well specified linear cases, I heavily doubt whether the implication is true for the real applications. I changed score from 6 to 4. I highly suggest the authors to consider different optimal $w^*$ for training and testing domains.\n\n### Post Rebuttal Comment 2\n\nI have read the literature [1]. And it indeed assume the same optimal $w^*$ for both training and testing domains. Though I don't like this assumption and it has problems with model misspecification under distributional shift, my claim \"a prohibitively strong assumption that I have not seen in the existing literature\" is inaccurate. I raise the score from 4 to 5. \n\n[1] Near-Optimal Linear Regression under Distribution Shift", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept