Near-Optimal Linear Regression under Distribution Shift
Authors: Qi Lei
Wei Hu
Jason D. Lee
Venue:  (2021)
Keywords: minimax estimator
covariate shift
model shift

Abstract: Transfer learning is an essential technique when sufficient data comes from the source domain, while no or scarce labeled data is from the target domain. We develop estimators that achieve minimax linear risk for linear regression problems under the distribution shift. Our algorithms cover different kinds of settings with covariate shift or model shift. We also consider when data are generating from either linear or general nonlinear models. We show that affine minimax rules are within an absolute constant of the minimax risk even among nonlinear rules, for a variety of source/target distributions.

Under review conference paper at ICLR 2021
NEAR-OPTIMAL LINEAR REGRESSION UNDER DIS- TRIBUTION SHIFT
Anonymous authors Paper under double-blind review
ABSTRACT
Transfer learning an essential technique when sufficient data comes from the source domain, while no or scarce data is from the target domain. We develop estimators that achieve minimax linear risk for linear regression problems under the distribution shift. Our algorithms cover different kinds of settings with covariate shift or model shift. We also consider when data are generating from either linear or general nonlinear models. We show that affine minimax rules are within an absolute constant of the minimax risk even among nonlinear rules for various source/target distributions.
1 INTRODUCTION
The success of machine learning crucially relies on the availability of labeled data. The data labeling process usually requires much human labor and can be very expensive and time-consuming, especially for large datasets like ImageNet (Deng al. 2009). On the other hand, models trained on one dataset, despite performing well on test data from the same distribution they are trained on, are often sensitive to distribution shifts, i.e., they do not adapt well related but different distributions. Even small distributional shift can result in substantial performance degradation (Recht et al. 2018 et al. 2020).
Transfer learning has been an essential paradigm to tackle the challenges associated with insufficient labeled data (Pan & Yang 2009 Weiss et al. 2016 Long et al. 2017). The main idea is to make use of source domain with lot of labeled data (e.g. ImageNet), and to try to learn model that performs well on our target domain (e.g. medical images) where few or no labels are available. Despite the lack of labeled data, we may still use unlabeled data from the target domain, which are usually much easier to obtain and can provide helpful information about the target domain. Although this approach has been integral many applications, many fundamental questions are left open even in very basic settings.
In this work, we focus on the setting of linear regression under distribution shift and ask the fundamental question of how to optimally learn a linear model for a target domain, using labeled data from a source domain and unlabeled data (and possibly some labeled data) from the target domain. For various settings, including covariate shift (i.e., when p(z) changes) and model shift (i.e., when p(y ()) changes), we develop estimators that achieve near minimax risk (up universal constant factors) among all linear estimation rules. Here linear estimators refer to all estimators that depend linearly on the label vector; these include almost all popular estimators known linear regression, such as ridge regression and its variants. When the input covariances in source and target domains commute, we prove that our estimators achieve near minimax risk among all possible estimators.
1

---

Under review conference paper at ICLR 2021
A key insight from our results is that, when covariate shift is present, we need to apply data- dependent regularization that adapts to changes in the input distribution. For linear regression, this can be given by the input covariances of source and target tasks, which can be estimated using unlabeled data. Our experiments verify that our estimator has significant improvement over ridge regression and similar hcuristics.
1.1 RELATED WORK
Different types of distribution shift are introduced in (Storkey 2009; Squionero-Canden et al. 2009). Specifically, covariate shift occurs when the marginal distribution on P(X) changes from Source to target domain (Shimodaira) 2000 Huang et al.) 2007). Wang et al. (2014); Wang & function of X. Sun et al. (011)) design a two-stage reweighting method based on both covariate shift and model shift. Other methods like the change of representation, adaptation through prior, and instance pruning are proposed in (Jiang & Zhai, 2007). In this work, we focus on the above two kinds of distribution shift. For modeling target shift (P(Y)) and conditional shift (P(X Zhang al. (2013) exploits the benefit of multi-layer adaptation by some location-scale transformation on X.
Schneider (2015) tackle model shift (P(Y X provided the change is smooth
Transfer learning/domain adaptation sub-fields within machine learning cope with distri- bution shift. A variety of prior work roughly falls into the following categories. 1) Importance- reweighting is mostly used in the covariate shift. (Shimodaira) 2000 Huang et al. 2007 Cortes
al. 2010p; 2) One fruitful line of work focuses on exploring robust/causal features domain-
invariant representations through invariant risk minimization (Arjovsky et al. 2019), distributional
robust minimization (Sagawa al., 2019). human annotation (Srivastava et al. 2020), adversarial training (Long et al. 2017] Ganin et al. 2016). or by minimizing domain discrepancy measured
by some distance metric (Pan et al.) [2100] et al. [013 Bakttashmtlaghh et al. 2013 Gong
jet 2013 Zhang et al., 2013; Wang & Schneider] 2014): :3) Several approaches seek gradual
domann adaptation (Gopalan et al. [ Gong et al. | Glorot et al. 2011 Kumar et al. 2020)
through self-training or gradual change in the training distribution.
Near minimax estimations are introduced in Donoho (1994) for linear regression problems with Gaussian noise. For a more general setting. Juditsky et al. (2009) estimate the linear functional using convex programming. Blaker (2000) compares ridge regression with a minimax linear estimator under weighted squared error. Kalan et al. (2020) considers setting similar to this work of minimax estimator under distribution shift, but focuses on computing the lower bound for linear and ane-hidden-layee neural network under distribution shift. A few more interesting results are derived on the generalization lower bound for distribution shift under various settings (David al. 2010, Hanneke & Kpotufe, 2019: Ben-David et al. 2010 Zhao et al., 2019)
2 PRELIMINARY
We formalize the setting considered in this paper for transfer learning under the distribution shift.
Notation and setup. Let (*) and pr (x) be the marginal distribution for x in source and target domain. The associated covariance matrices are Eg, and Σr. We assume to have sufficient unlabeled data to estimate Er accurately. We observe ns, or labeled samples from source and target domain. Data is scarce in target domain: ns >> nT and nr can be Specifically, Xs
[x:] [ ... | T E Band with n; i E [ns) drawn from ps. noise [ 22, *.ngg 1T, 2 (O, 0²). ys = [y1, ".. ynnl' E Ras, with each yi f*;) 2 (Xr Rar and
2

---

Under review conference paper at ICLR 2021
Mr E R are similarly defined). Denote by Es = =X3 X/XSsnn the empirical covariance matrix (Throughout the paper we assume data is centered: Epg [ar] Epr [a]] = 0). The positive part of number is denoted by (.: We consider both linear (f" (a) = a: ( and general nonlinear
ground truth models. When the optimal linear model changes from source to domain we add
subscript for distinction, i.e. B3 and 37. We use bold (æ) symbols for vectors, lower case letter (x) for scalars and capital letter (A) for matrices.
Minimax (linear) risk. In this work, we focus on designing linear estimators B Ays for parameter 3 E B. Our estimator is evaluated by the excess risk target domain, with the worst case 3 in some set Lx(() = ea Eys ((() - B²1 Minimax linear risk and minimax risk among all estimators respectively defined as:
(B)
min LB( RN min Lg(g).
B lincar ys
The subscript "N" or "L" is a mnemonic for "non-linear" or "linear" estimators. Ry is the optimal risk with no restriction placed on the class of estimators. RG, only considers the linear function class for B. Minimax linear estimator and minimax estimator are the estimators that respectively attain Rt and Rx within universal multiplicative constants. Normally we only consider B = /1]
S r}. When there is no ambiguity, we simplify ((ys) by B.
Our meta-algorithm. Our paper considers different settings with distribution shift. Our methods are unified under the following meta-algorithm:
Step I: Find an unbiased sufficient statistic Ase for the unknown parameter.
Step 2: Find ByM. linear operator applied to Bss that minimizes LB(BAM))
For each setting, will show that BMM achieves linear minimax risk Rt (asymptotically in fixed design). Furthermore, under some conditions, the minimax risk Ry is uniformly lower bounded by universal constant times LB (PMM).
Outline. In the sections below, we tackle the problem in different settings. Section we design
algorithms with only covariate shift: 1) mı = 0 and f (x) is linear (Section 3.1 2) = 0
and (xx) is a general nonlinear function (Section 3.2 : 3) nr
and f is linear (Section 3.3
Finally, we cope with the model shift for linear models (3% + 37.) in Section
3 MINIMAX ESTIMATOR WITH COVARIATE SHIFT
In this section, we consider the setting with only covariate shift. That is, only Es (marginal distribution Ps (2)) changes to Er (pr(z)), but f = EØy|= (conditional distribution p(ylæ=) (z)) is shared. We first consider the case when f is a linear map: æ + x 3 and then consider the problem with approximation power.
"A E dRd may depend in an arbitrary way on Xs, ns, or Σr. The estimator is linear in the observation ys. With samples ys. a statistic f = T(ys) is sufficient for the underlying parameter 33 if the conditional probability distribution of the data ys. given the statistic T(ys), does not depend the parameter 3
3

---

Under review conference paper at ICLR 2021
3.1 COVARIATE SHIFT WITH LINEAR MODELS
We observe niş samples from source domain: ys - Xs + 2, o2) and no labeled
samples from the target domain. Our goal is find the minimax linear estimator BMM((s) Ays with some linear mapping A that attains (B).
Following our meta-algorithm, let Ass - ng
X
ys
be an unbiased sufficient statistic for 3
Ass
1 ys
E X
E.g X
Xs3
1 555 X
nn
nn
ns
3 1 1g2 N ng
o² 0
5-1
(1)
ns
The fact that (ys) is sufficient statistic is proven Claim 3.7 for a more general case, using the Fisher-Neyman factorization theorem. Here we consider Xs as fixed values, and randomness only comes from noise z. We prove that the minimax linear estimator is of the form BMM CB3ss and then design algorithms that calculate the optimal C.
Claim 3.1. The minimax linear estimator of the form BMM Cisssfor some C' E [Rdxd
commutative covariance matrices. In order to derive the minimax linear estimator, we first consider the simple case when Σr and Eg are simultaneously diagonalizable. We apply Pinsker's s Theorem (Johnstone) 201T) and get:
Warm-up:
Theorem 3.2 (Linear Minimax Risk with Covariate Shift). Suppose the observations follow se- quence model ys Xg +2, NO, In),). Ef Udiag(t)U and Es X Xs/ng- U Udiag(s)UT, then the minimax linear risk
RB(B)= = min max | 2 (3))2 A=Ays BBEB
0² 4
A
ng 8i
+
where B ||||||||| r) and X()) is determined by linear minimax estimator is given by:
a no
(VE//> +
Σd 1
1)+ 22 The
En Bss, where Bss
1 _ ES X ys.
(2)
125
Since is unknown in practice, we could simply view either or directly À the tuning parameter. We compare the functionality of X with that ridge regression: BAR arg min g E 1 X 2n
1 > || (És X1)-1X3 PPXxys/ns, ys/ns. For both algorithms, À is balance the bias and variance: X = 0 gives an unbiased estimator, and a big À gives a (near) zero estimator with no variance. The difference is. our estimator shrinks some signal directions based on the value of t; The estimator tends to sacrifice the directions of signal where f; is smaller. Ridge regression, however, respects the value of 8; natural counterpart for ridge to also regularize based on t: let S r = arg min 1 /1/>///
(B Σng X ys)ll + |||laa = (Er + In We will compare their performances in the experimental section.
'Throughout the paper Egg could be replaced by pseudo-inverse and algorithm also applies when d.
4

---

Under review conference paper at ICLR 2021
Non-commutative covariance matrices. For con-commutative covariate shift, we follow the same procedure. Our estimator is achieved by optimizing over C: AMM Cßss:
(B) min max E | 2 (3 11 A=Ays BR
o² C
min B=Cps
max
E 1/2 1)3 ns
(Claim 3.1
d² Tr
=min 2
1/2 C ETT s.t. (C E TT.
II
r,C
nsg
Unlike the commutative case, this problem doesn't 't have a closed form solution, but is still solvable:
Proposition 3.3. Problem
3 is convex program and thus solvable.
We achieve near-optimal minimax risk among all estimators under some conditions:
Theorem 3.4 (Near minimaxity of linear estimators). When Es, Er commute, or Er is rank 1, the best linear estimator from or achieves near-optimal minimax risk: L.s (Bs()) R1 S xB)
Note that Rv < Rr by definition. Therefore 1) estimator 3MM is near-optimal, and our lower bound for Rx is tight. Lower bounds (without matching upper bounds) for general non- commutative problem is presented in (Kalan et al. 2020) and improve their result for the commutative case and provide a matching algorithm. Their lower bound scales with d min, & for large r. while becomes ng ΣS fz Our lower bound is always larger and thus tighter, and potentially arbitrarily larger when max; the appendix.
t are very different. We defer our proof to s; ti and min;
Remark 3.1 (Benefit of minimax linear estimator). Consider estimators from ridge regres- sion: 3AR arg ming 2m ||x ysll² + 111B12 There is an example that Ry (B) I
O(d- 1/4 O(d-1/ALB(()) (BBx))) even with the optimal hyperparameter X.
Remark 3.2 (Incorporating the randomness of source and target features). For clean presentation purposes, the main text we assume to have access to Ex- In practice, we will need to estimate Er by finite unlabeled samples from target domain. In Appendix we show that our estimator remains near-optimal if we have >> d unlabeled target samples under some standard light-tail assumptions.
Theorem 3.4 is comparing our estimator with the optimal nonlinear estimator using the same data Xs from the source domain. In appendix C we compare estimator with stronger notion of linear estimator with infinite access to ps and show that our estimator is still within multiplicative factor of it.
3.2 LINEAR MINIMAX ESTIMATOR WITH APPROXIMATION ERROR
Now we consider observations coming from nonlinear models: = (X + Let B = arg ming -==-ps.>~N(0..>2 (ff (f + z 3 } and similarly for By. Notice now even with unchanged across domains, the input distribution affects the best linear model. Approximation error is uz( = (*) x 3 and vice versa for dT.
"Note this goes without saying that our method can also be order-wise better than ordinary least square, which is special case of ridge regression by setting O.
5

---

Under review conference paper at ICLR 2021
Define the reweighting vector w R as wi = =: We form unbiased estimator via
Pr (T;)
BLS = arg min
Σ
(B x; yx) (X diag(w) (Xg diag(w)yy)
3
Claim 3.5. Bis is asymptotically unbiased and normally distributed:
vns(3rs - BT) - (N0, ETT En-er pr(x)) (at/ppps(((((((( + o²) "E
Denote by m(x) ar( (2) + We want to minimize the worst case risk:
min max E || ||>./// 2 (ß 3
B=CAs ET
- min max
d
| /
| (C -1) + Tr(CET Epr
PT (z)
m(x) Exx xx CT ETT
C
ns
ps(x))
min C
[[[C- |[(C-)) 12121 + Tr(CET Epr
1
PT (()) x.
1>7 1 (T)
ns
ps(x))
Therefore estimator is BMM CpSs where è finds
p (x) P (x)
Ex C ET(2AT))
Ö + arg min 7,0
Σ
(y: x. (
(4)
ng
s.t. 1I (C 1) rI.
Claim 3.6. Let B [B||||]] $ r), and f E F is same compact symmetric function class: f F ff E F. Then linear minimax estimator is of the form Cßis for some C. When Ò solves Eqn. [.(((rM)) asymptotically matches R2(B), the linear minimax risk.
By reducing from ys to BLS we eliminate n d dimensions, and this claim says that X ys is sufficient to predict B7. We note that f is more general than linear function and therefore the lower bound could only be larger than R (B) defined the previous section.
3.3 UTILIZE SOURCE AND TARGET LABELED DATA JOINTLY
In some scenarios we have moderate amount of labeled data from target domain as well. Then important utilize the source and target labeled data jointly. Let ys X zs. yr 8r + øT. We consider Xs, Xy as deterministic variables, ΣS X ys/ns ~ NB" o² Σ5 and EST STyy/ur/ ~ N sufficient statistic for 3r Ass == (nsis ut - ys XT
o² nn
=r Therefore conditioned on the observations ys yr, a
Claim 3.7. Bss an unbiased sufficient statistic of B with samples ys. Oss N(B o?(ns + -rr
First consider the estimator Ass = (n + - + XF Next find the best linear function of Ass:
Algorithm:
ANMM = arg min 2 + o Tr( nT ETC,, s.t. IC- C.7
Proposition 3.8. The minimux estimator Iass is of the form C.ys for some C. When choosing C
with our proposed algorithm and when Eg commutes with En and En, we achieve the minimax risk R2 (B) < 1.25Rx (B).
6

---

Under review conference paper at ICLR 2021
4 NEAR MINIMAX ESTIMATOR WITH MODEL SHIFT
The general setting of transfer learning in linear regression involves both model shift and covariate shift. Namely, the generative model the labels might be different: ys = Xs + zs. and yr X,,37 Zy. Denote by ô : 3 37 as the model shift. We are interested in the minimax linear estimator when || I 7 and || I r. Thus our problem becomes to find minimax estimator for B B (33 ||||| S r) from ys, yr-
First consider sufficient statistic (3) for (gi 8). Here As E5 - ys/nss ~ W + 8, a² ns 255)) and 37 Epp X yr/ur ~ NN
Algorithm:
a²
).T2) Then
nr
consider the best linear estimator on top of it: f A A2Br. Write A {ō||08) S 7) and
LB. (3) == max 1| (B 37
(B, =
min A A2
LB (B)
S min
max
2 221/_//2((4 ((A1 A2 T)3711 + 2/15,// 1,
(5)
An.42 ||3 1..111811111 |||
Tr AT) + 0²
Tr 45)
+ ng
(AM-GM)
min A1,A2
(2] {2112// ((A) + + - 1)112r2 ?213/
11122
a² TrA AT) + 0² Tr TTAAsTT' AJ) :BA Aml)
ns
Therefore we optimize over this upper bound and reformulate the problem convex program:
0²
Tr A _ IMAA 43)
A2) + arg min
2ar² + 2b2
AL.
n18
TVT
s.t.
(A1 + 1) A + A - 1) = al, A E, bl.
(6)
Our estimator is given by: AMM Å + A2.rr. Since AMM is relaxation of the linear minimax estimator, it is important understand how well 3MM performs on the original objective:
Claim 4.1. (B, S (B.M)) < (B,
Finally we show with the relaxation we still achieve near-optimal estimator even among all nonlinear rules.
Theorem 4.2. When Eq commutes with E.g, satisfies:
(B.M)) = max
|2 (BUM - -3 < 27 (B,
Here (B( == ::min ((y.ar)) EB
( -3%-11 is the minimax risk.
Proof sketch of Theorem 4.2 For the case of understanding, we provide simple proof sketch when Σs = Li are diagonal. We first define the hardest hyperrectangular subproblem. Let
B(T) (b |& I 7 be subset of B and similarly for (C)). We show that R2 (B, A)
7

---

Under review conference paper at ICLR 2021
maxxEB.ÇE. (BTT), A(C)), and clearly Rx (B, () 2 maxreB.çeA (B(T), Mean- while we show when the sets are hyperrectangles es the minimax (linear) risk could be decomposed linear minimax risk (3, + 6,, and y ~ (3,,, 1) where [3,] S and [6,| ك S. This 1-d problem for linear risk has closed form solution, and the minimax risk can be lower bounded using Le Cam's two point lemma. We show (Ta. St) 1 (Tx, (e) and therefore:
to 1-d problems: Rg (B( T A()) = E, Rs. (T., (.). Each (T,, G)
to estimate 3 from
1 LBA (3MM)
Clain
A))
Lemma B.2
max TEB.CEA
R₁. (B(T).,,
2
Prop B.4
Σ ST)
Lemana B.6
13.5 Σ (N((T.)))
max TEBCEA
max TEB,CAA
Prop B.4
13.5
max Rx(B(T).A(C) & 13.5Rr (B.
TEB.CEA
S199:
C2
(a) covariate eigen-spectrum
(b) signal strength
(c) model shift
Figure 1: Performance comparisons. (a): The x-axis a defines the spread of eigen- eigen-spectrum of Eg: 8; 1/60 tú x 1/i. (b) x-axis is the normalized value of signal strength: || |/r. (c) X-axis is the model shift measured by 7/r. Performance with standard error bar is from 40 runs.
5 EXPERIMENTS
Our estimators are provably near optimal for the worst case Sr. However, it remains unknown whether on average they outperform other baselines. With synthetic data explore the per- formances with random f We are also interested to investigate the conditions when we win
Setup. We set rı = 2000, d = 50, a = 1,r Vd. For each setting, we sample By from standard normal distribution and rescale be norm We assume to know Σy. We compare estimator with ridge regression (S-ridge) and a variant of ridge regression transformed to target domain (T-ridge): PRR,T arg min ||>///// (3 E ) + |||l8| (Er AI) ET
Covariate shift. In order to understand the effect of covariate shift on our algorithm, we consider three types of settings, each with unique varying factor that influences the performance: 1) covari- ate eigenvalue shift with shared eigenspace; 2) covariate eigenspace shift with fixed eigenvalue
We leave this result in appendix since performance appears invariant this factor.
8

---

Under review conference paper at ICLR 2021
3) signal strength change. We also have an additional 200 labeled data from target domain validation set only for hyper-parameter tuning-
Model shift. Next we consider the problem with model shift. We sample random with norm y varying from 0 r vd and observe data generated by ys ( 5) + zg E R20000 2g ((0, 1) and yr Xr + æт E R5500 ーт (0, I). We compare our estimator with two baselines: "ridge-source" denotes ridge regression using only source data, and "ridge-target" is from ridge regression with target data.
Figure demonsttaats the better performance of our estimator all circumstances. From (a) we see that with more discrepancy between Vi and Mn, our estimator tends to perform better. (b) shows our estimator better when the signal is relatively stronger. From (c) we can see that with the increasing model shift measured by 7/r, ridge-source becomes worse and is outperformed by ridge-target that remains unchanged. Our estimator becomes slightly worse as well due to the less utility from source data, but remains the best among others. When 7/r 0.2, our method has the most improvement in percentage compared to the best result among ridge-source and rirge-target.
REFERENCES
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint arXiv:/907.000 2019.
Mahsa Baktashmotlagh,, Mehrtash T Harandi, Brian C Lovell, and Mathieu Salzmann. Unsupervised domain adaptation by domain invariant projection, In Proceedings of the IEEE International Conference on Computer Vision, pp. 769-776, 2013.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wort- man Vaughan. A theory of learning from different domains. Machine learning, 1911-2):5 2010.
Helge Blaker. Minimax estimation in linear regression under restrictions. Journal of statistical planning and inference, 31555555,5, 2000.
Corinna Cortes, Yishay Mansour, and Mehryar Mohri. Learning bounds for importance weighting. In Advances in neural information processing systems, pp. 442 442-450, 2010.
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, pp. 129-1336 2010.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-555. leee, 2009.
David L Donoho. Statistical estimation and optimal recovery. The Annals of Statistics, pp. 238-270 1994.
Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint 2044440000.04434 2020.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Dowaan-adversariil training of neural networks. The Journal of Machine Learning Research,
2030, 2016.
9

---

Under review conference paper at ICLR 2021
Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Domain adaptation for large-scale sentiment classification: A deep learning approach. In ICML, 2011.
Boqing Gong, Yuan Shi, Fei Sha, and Kristen Grauman. Geodesic flow kemel for unsupervised domain adaptation, In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pp. 2066-2073. IEEE, 2012.
Boqing Gong, Kristen Grauman, and Fei Sha. Connecting the dots with landmarks: Discrimina- tively learning domain-invariant features for unsupervised domain adaptation. In International Conference on Machine Learning, pp. 222-230, 2013.
Raghuraman Gopalan, Ruonan Li, and Rama Chellappa. Domain adaptation for object recognition: An unsupervised approach. In 20// international conference on computer vision, pp. 999-1006. IEEE, 2011.
Steve Hanneke and Samory Kpotufe. On the value of target data in transfer learning. In Advances Neural Information Processing Systems, pp. 9871-9881, 2019.
Jiayuan Huang, Arthur Gretton, Karsten Borgwardt, Bernhard Schölkopf, and Alex Smola. Correcting sample selection bias by unlabeled data. In Advances in neural information processing systems, pp. 601-608, 2007.
Jing Jiang and ChengXiang Zhai. Instance weighting for domain adaptation in nlp. In Proceedings of the 45th annual meeting of the association of computational linguistics, pp. 264-271, 2007.
lain M Johnstone. Gaussian estimation: Sequence and wavelet models. Unpublished manuscript, 2011.
Anatoli B Juditsky, Arkadi S Nemirovski, al. Nonparametric estimation by convex programming. The Annals of Statistics, 37(5A))227--2300 2009.
Seyed Mohammadreza Mousavi Kalan, Zalan Fabian, A Salman Avestimehr, and Mahdi Soltanolkotabi. Minimax lower bounds for transfer learning with linear and one-hidden layer neural networks. arXiv preprint arXiv:2006. 10581, 2020.
Takafumi Kanamori, Shohei Hido, and Masashi Sugiyama. A least-squares approach to direct importance estimation. The Journal of Machine Learning Research, 10:1391-1445, 2009.
Ananya Kumar, Tengyu Ma, and Percy Liang. Understanding self-training for gradual domain adaptation. arXiv preprint arXiv:2002.1 11361, 2020.
Mingsheng Long, Jianmin Wang, Guiguang Ding, Jiaguang Sun, and Philip S Yu. Transfer feature learning with joint distribution adaptation. In Proceedings of the IEEE international conference computer vision, pp. 2207,2207, 2013.
Mingsheng Long, Han Zhu, Jianmin Wang, and Michael Jordan. Deep transfer learning with joint adaptation networks. In International conference machine learning, pp. 2208-22111 PMLR, 2017.
Shangyun Lu, Bradley Nott, Aaron Olson, Alberto Todeschini, Hossein Vahabi, Yair Carmon, and Ludwig Schmidt. Harder or different? a closer look at distribution shift in dataset reproduction. In /CML Workshop Uncertainty and Robustness in Deep Learning, 2020.
10

---

Under review conference paper at ICLR 2021
Sinno Jialin Pan and Qiang Yang. A survey on transfer learning. IEEE Transactions on knowledge and data engineering, 12110):1345-339, 2009.
Sinno Jialin Pan, Ivor W Tsang. James T Kwok, and Qiang Yang. Domain adaptation via transfer component analysis. IEEE Transactions on Neural Networks, 22(2):199-22 2010.
Joaquin Quionero-Candela, Masashi Sugiyama, Anton Schwaighofer, and Neil Lawrence.
Dataset shift in machine learning. 2009.
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do cifar- 10 classifiers
generalize to cifar-10? arXiv preprint arXiv: 1806. 1, 2018.
Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generaliza- tion. arXiv preprint arXiv:1911.0877 2019.
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log-likelihood function. Journal of statistical plamning and inference, 90(2):227-244, 2000.
Megha Srivastava, Tatsunori Hashimoto, and Percy Liang. Robustness to spurious correlations via human annotations. arXiv preprint arXiv:2007.0666 2020.
Amos Storkey. When training and test sets are different: characterizing learning transfer. Dataset shift in machine learning, pp. 3-28, 2009.
Qian Sun, Rita Chattopadhyay, Sethuraman Panchanathan, and Jieping Ye. A two-stage weighting framework for multi-source domain adaptation. In Advances in neural information processing systems, pp. 505-513, 2011.
Martin Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
Xuezhi Wang and Jeff Schneider. Flexible transfer learning under support and model shift. In Advances in Neural Information Processing Systems, pp. 1898-1906, 2014.
Xuezhi Wang and Jeff G Schneider. Generalization bounds for transfer learning under model shift. In UAI, pp. 922-931, 2015.
Xuezhi Wang, Tzu-Kuo Huang, and Jeff Schneider. Active transfer learning under model shift. International Conference on Machine Learning, pp. 1305-1313, 2014.
Karl Weiss, Taghi M Khoshgoftaar, and DingDing Wang. A survey of transfer learning. Journal of Big data, 3(1):9, 2016.
Kun Zhang, Bernhard Schölkopf, Krikamol Muandet, and Zhikun Wang. Domain adaptation under target and conditional shift. In International Conference Machine Learning, pp. 819-827, 2013.
Han Zhao, Remi Tachet des Combes, Kun Zhang, and Geoffrey J Gordon. On learning invariant representation for domain adaptation. arXiv preprint trXiv:1901.09453. 2019.
11

---

Under review conference paper at ICLR 2021
A OMITTED PROOF FOR MINIMAX ESTIMATOR WITH COVARIATE SHIFT
A.I PINSKER'S S THEOREM AND COVARIATE SHIFT WITH LINEAR MODEL
Theorem A.1 (Pinsker's Theorem). Suppose the obervations follow sequence model yı = 0 + Ei E > 0, E [d], and ④ is an ellipsoid in R = ((a, C) = {0 h: agO? S ] Then the minimax linear risk
(e)
min max ((( 0- ||
① linear 0" EB
Σ 27 - 02/11)+1
where ((C) is determined by
d Σ
Eail -a,)+ C².
2m1
The linear minimax estimator is given by
(1) c. = (1- (1-a;/u)43,
(7)
and is Bayes for Gaussian prior me having independent components 0, No 7f) with Tf = =f - 1)_.
Our theorem 3.2 is to connect our parameter 3 to the 0* in pinsker's theorem. First we show that reformulating the problem from a linear map of dimensional observations ys to a linear map the d-dimensional statistic Ass is sufficient, i.e., Claim 3.1
Proof of Claim 3.7 This is show that if Byys) == Ays is a minimax linear estimator, each row vector of A E Rdxn is in the column span of Xs. Write A = A + A2W where W E Rax(n columns of which forms the orthonormal complement for the column space of Xs. Equivalently we want to show A₂ = O. have
Ry (B) = min max E ( (B 2²1
A=Ay 3" EB
min max E
| 1/2 ((AIX) + A2W Jys B²
min max E /1///((11))) (Xs0* +2) A&WT =- - (Since W Wxxx-
A.,A, 8.
min max
||>
1/2
(A1 Xs 11 -E|E A x11
An,As E8
+ E
A2W 2 2 E |// 1,
2, -/ A& 2
(Other cross terms vanish since B[z] = 0)
(A1 Xs 1 - A, x12 + EES A.W =11?
min max
A
where the last equation is because
1 AIX] z, E/ Ao x)= =B ال/ A1 HIXxx=WAJE/ ]
12

---

Under review conference paper ICLR 2021
= Tr [ X E|zz WWATT = I A 0.
Clearly, at min-max point, without loss of generality we can take A = 0.
Formally the proof for Theorem 3.2 is presented here:
Proof of Theorem 3.2 To use Pinsker's theorem to prove Theorem 3.2 we simply need to trans-
form the problem match its setting. Let yr E1 >n/² 2 ys /ns Of 2r. where 07 U 1/2 [T>1/" 3 and 2T (0 o² / n.)) The set for B7 is e = (01|) U S r),
i.e., (0) E, /1 }.
Now with Pinsker's 's theorem, Q(yr): = (1 - 1/(uvl:))+ (ur): is the best linear estimator for 0 where μ p()) solves
0² d
(1
1/ )+ =
(8)
Connecting to the original problem, we get that the best estimator for 2 is U(I 1 diig((1//E]] = U(I 1 diig((1/ =/ D' X ys/nn /ns.
A.2 OMITTED PROOF FOR NONCOMMUTE COVARIANCE MATRICES
Convex program.
Our estimator for 3 can achieved through convex programming:
Proof of Proposition 3.3 First note the objective function is quadratic in C and linear in r, there- fore we only need prove the constraint
((C,T) - -)) ") - -)) 3 <T1} a convex set. (1, We simply need (C. -I) Σn (Ca=
Notice for (C1, TI), (C2, 72) E S, i... (C; 1) ET
to prove for C. == aC1 + (1 - a)C2, Ta == +
T for
any [0, 1). First, notice (C1 En (C ł 0. Next,
(C. E,, I) =a(C1 - 1) E,
(Ca -Ca-I)
Ey (C1 - +)+ a) - Er((2 I))
- a(1 - a) - (100))E(( C2)
+(1 a)(C2 1) Er I) <a -
IT
Benefit of estimator. Compared to ridge regression, our estimator could possibly achieve much better (d-1/4) improvements:
Proof of Remark 3.1
We consider diagonal covariance matrices Es = diag(s), Er = diag(t). tt,
= 1. First calculate the expected risk obtained with ridge regression: Bix (X3 X
13

---

Under review conference paper at ICLR 2021
~ (
(t) AA) -ss).
LE(0RR)
max Bys s B.EB
-axx BTEB
E
((Sg + 21) - 'Ég - 1),8112 + Tr( (Ôs + X
ns
- vt.) + 1 4.8
=
8 +
ng (s: 2)2"
Compared to our risk:
RL( = Σ 1/
1
Vlipa )+
1gg 8;
where 1 Ei=1
Li (n-
1
+ 22. Let 2 ns 5; 1, Vi, t, = Vi [do], = 1/2 do <
Ld
Vt.
S d, where do
fd
2 d2/4, Then μ 1, and Rr. (B)
d//4 In this case,
--/-1
min m 2
Viss
vti
2
+ Σ
t,s;
8; +\
TiS (8) + X)
Vd
Vtg
4 ng (1 + A)2
min Vd X² Vd 1
min max
Vti
+
n
1+}
n (1+ A\2 n (1 A)2
vd 2
2n
Therefore min, La( 2 d2/4 (B.)/2
Near minimax risk. minimax risk:
Even among all nonlinear estimators, our estimator is within 1.25 of the
Proof of Theorem 3.4 First we note that for both linear and nonlinear estimators, it is sufficient to use Bss instead of the original observations ys. See Lemma A.2 and its corollary. Therefore it suffices do the following reformulations of the problem.
When Es and Σr commute, we formulate the problem as the following Gaussian sequence model. Recall Es Udiag(s)UT, ET U'diag()UTT Let 0" U ///² 3*, and y U / Ass a² diag(t/s)). Our objective of minimizing 1 - -]))] from linear estimator is ng equivalent to minimizing (((() 0-1 (0 - 0-1 || from linear estimator.
N(
The set for the parameter that satisfies 0* = U // 3-, || is equivalent to || < + |10:/ /Vtlllll < is axis-aligned ellipsoid. Then we could directly derive result from Corollary 4.26 from Johnstone| (201 Note that this result is special case of Theorem [.2 and we have provided a detailed proof in Section B Therefore here save further descriptions.
For the case when En = aa" is rank-1, the objective function becomes:
R₁, (B)
min max E(a (((()s) )²)
8 linear BEB
14

---

Under review conference paper at ICLR 2021
Then the result could be derived from Corollary oo (19944) which reformulate the problem to the hardest one-dimensional problem which becomes tractable.
In the proof above, we equate the best nonlinear estimator on Ys as the best nonlinear estimator on Bss. The reasoning is as follows:
Lemma A.2 (Sufficient statistic is enough to achieve a best estimator). Consider the statistical
problem of estimating 3 B from observations y B E--compact. If S(y) is sufficient statistic of 3r, then the best estimator that achieves ming maxg 1(3, 3*) of the form f ((S())) with some function f, for any loss t y + [0, oo).
This Lemma is restated from Proposition 3.13 from Johnstone (2011).
Corollary A.3 (Corollary Lemma A.2). Under the sume setting of Lemma A.2
Rx(B) is
achieved with the form 3 = f(S()))
A.3 OMITTED PROOF WITH APPROXIMATION ERROR
Unbiased estimator for 37.
Proof of Claim
3.5
Bıs 3 =XX (w) Xx)) dig B7
d(X w) Xx) diag (X) (X ar 2)) - BT
= =(X diag(
( w) Xz) dig (ar z))
Notice Ba-ys (2aT (x) pr(e)] Exppr [xar(x)] = 0. This is due to the KKT condition for
the minimizer of 1(3) == Ex-pr (x) B x0122 at B1: Vaf(B*) = 0 + Exwpr [x(f"
x T B7)] = 0, i.e., Exppr [xar(x))] = 0. Next we have: Ex [X (diaa(w):.)) Xs]
E Exg.<ps -i=1 ps()))
(mx) x Eny-pr E ns2i.. Therefore
BLS - 37 + NO, Ex (pr (pto:p//po( + +o²)xx xx |Σ
Proof of Claim 3.6 Recall Xs = [ [ ... x E Raxd with a; Vi E [n] drawn from ps-
and aT ar
2 or (x ar (2r, ) E TR. y (y( ((F2) v(x))) E RR" noise
== y - fr (X). w = (pT(c:)/ps(z.)
To prove the, only need show the minimax linear estimator Ay is achieved of the form A, X ddiag(w), i.e., the row span of A is in the row span of X diag(w).
(B) = min max Em. 1 (Ay - 11
A BB
max min
1 1)33 + Aar + A2)l12
A EF
15

---

Under review conference paper at ICLR 2021
-mmn max
+E (AX (AX 37 + E ///2 (12%/ - (Aar E[AAr][[ll B|E
+
B, EF
Write A X diag(w)) + A2W where X E Rgxd and W E (ax(n-d) forms the orthogonal complement for the column span of diag un) X. Therefore X diag(w)) = 0, and W WW n--- Also, notice E. xipps [X" diag(w))aT) n n.e-rr [a)( [xar([x]] = 0. Therefore plugging it in
(B), we have:
R2 = min max
S 11 Eps X diag(w)) 3) + A2 W F[WTar)
+ E E A1 (X diag w) E[x
+ E | A2 ( aT E(W ar))11
+o² | A X diagg(w) w) )12 + A2 12
|10// ((]]((((Ans))))))))))))) 1)33 + A E(W ar))
min max
A1.42 3,EB,J EF
+ E |=|/ (X diag(w)X Σr) ||
(W ar - -
B[W [[WT)r)))l ar))l
to 2 || X diag(w) w)l o |
1/2 A2l
We could view T aTl and W T E[W aT] separately. First notice at min-max point, if E[W" arl = O, the minimizer A2 should be 0 since it only appears in the third and last non- negative terms. EE[W" arl A O, the cross term of the bias should be non-negative, otherwise since both f and - ff are in the set, ar, .3. could be replaced by -ar, - and the loss increases. Clearly in this case A₂ should also be 0 min-max point.
A.4 OMITTED PROOF FOR UTILIZING SOURCE AND TARGET DATA JOINTLY
Sufficient statistic.
Proof of Claim 3.7 Denote by Bs ES ES' ys/ns NBB o" e'ك'") and By ==
ns
S.T. X yr/nt NV3 or 1) We use the Fisher-Neyman factorization theorem to derive the sufficient statistics. The likelihood of observing Bs. Br from parameter 3 is:
plBs, Br; =ce " (As 1 (8
=cg(3" ((
(9" Ass) 22 "I "3' Ass) and is some constant. Therefore it's easy to see that T(3*) = Bss is the sufficient statistic for 3
where g(3", (T(") = -
Proof of Claim 3.8 With similar procedure as before, and notice zs and zr are independent, we could first conclude that the optimal estimator is of the form B = Ašs x ys/ns + B X /Tyr ((A + B) o² ns A + o² B )
nr
Ry (B) = min max Ez || |エ -1
A E
16

---

Under review conference paper at ICLR 2021
min max A, E
|| (A+ - [
+o²Tr((
AEg'A AT + BEST B )ETr
ng
min A
112
B 1pp +
Tr((((
AEgg
1
AT
+
-BST BT )ET)
ng
1/
Take gradient w.r A and B respectively we have:
0²
(A 1)1lpp +
ET = 0
ns
σ²
=VB([E>// A - 22) +
Ex BTBT
nr
Notice the first terms equivalent. Therefore AE form C(X5 ys + yTyr) for some matrix C, thus finishing the proof.
B thus the optimal f is of the
n2
nr
B OMITTED PROOF WITH MODEL SHIFT
Definition B.1 (Orthosymmetrr). A set θ is said to be solid and orthosymmetric if 0 θ and Gi [0,| for all implies that θ If a solid, orthosymmetriic O contains point т, then it contains the entire hyperreetangle that T defines: ((T) = [0110,] I Tr, Vi} C θ.
Proof of Claim 4.1 First notice for any estimator B3 it all satisfies
(B,)(3) (B,)(3) s (.).
(9)
The first inequality is straightforward with the same reasoning of AM-GM as the derivation of (5). As for the second inequality, take closer look ( Notice that when cax is achieved, the cross term has to be non-negative, or otherwise one could flip the sign of B
to make the value larger. Therefore at maximum ||=|/ ((A1 + A2 1) + ||]/ A| < (EA) + A2 1) + 1/2 A,51, and notice the remaining parts are all non-negative.
Therefore (B) S (
Now let 3 = arg min 3- Augs (3). We have:
= (B < (gNM))
LBBA (BMM) 1 2L..a = 2R, (B, A).
The incquality (a) is by definition of 3 while (b) is from the definition BMM-
B. LOWER BOUND WITH MODEL SHIFT
In order to derive the lower bound, abstract the problem the following general one:
17

---

Under review conference paper at ICLR 2021
Problem 1. For arbitrary diagonal matrix D Rdxd, two compact solid, orthosymmetric, and quadratically corvex sets θ A C Rd, let
PAAAD N { (1
]. (
0
Let (2( A, D) and Rx (θ, A. D) be the minimax linear risk and minimax risk respectively for estimating 0 within the distribution class Pe,aD:
Ry (O,,A,
min 0.R - linear PEPo,a.D
rP(0),
RN ( (,,,,
min Ô.R
max PEPa.ADD
rp(0).
Here Tp (0) == EppP [1((x))
(P)) We want derive uniform lower bound for Rx with RL, i.e., Rx μ R2, where μr is universal and doesn't 't depend on the choices of D, θ or A.
Before proving the lower bound, we establish its connection to our considered problem:
Remark B.1. Suppose Es = Uddia(s) and Σx Udiag(t)U" share the same eigenspace. Recall our samples a -N (3) + 6), o2), ~ N( o2, Our goal to uniformly lower bound Rx(r, v) by Rr. 7) is essentially Problem 7 where
(r,r,)) min 3 linear
E|
E
( - -
Sr. 8
St
Rx(r,7)
min
E
/ -
B || |t.10o1
Proof of Remark B.1 8), (2
Our target considers samples drawn from distributions x ~ N/EE//// +
1/2 N(= B7, 021).
b N ([
Udiag(s!/2 T + 8)
o² T
0
)
0 θ EA
Udiag(t (122UTTT 3
0
0²1
U Taao
~ N
([diaste//
diag(s (dag(s1/2)05 112)UT (3) 8)
1
0
||3; || sr. sr,1011 E
b/o
diag(t (1/)) Bi
0 T
Let à = U a/a,b U b/ob , θ (0 |ddgg(t 111/))00
S r). A = {lldiag(s 11/2)811 S 7}.
0= -=U 0-UTs//² U T 6. and D
1//2211/33) We get:
U UTalo
N -N(1
((diag(s/ diag(s 1/2)0 (3) 8)
(07)
I
0 () 11,7 Sr. 1r. E
U UTa
diag(t (t" B
0
à Po..D = N
DØ
5
]
I
0
0 E O
b
0
0
Since U is an invertible matrices, observing UT aaa/a, b/o instead of a, b has affect on the performance of the best estimator. Also A, are axis-aligned ellipsoid and thus satisfy orthosymmetry. Therefore our problem essen- tially reduced Problem I
Let Pe,aD = {Po.spl 0 A).
18

---

Under review conference paper ICLR 2021
Lemma B.2. Ler ((T) (018; I Tr Vi, 0 θ) and similarty for A(C) {ő]ó; S 5. A}.
D is some diagonal mulrix.
R A, D)
sup TEB,CEA
(e((())) and
Rx(
sup TEB,CE
Rv (
Write samples drawn from some Po.6.D PE,DD (z. () : 9 NN(.11 Lemma B.3. The minimax linear estimator ô (x. y) + Ax + By has the form (a,((r,)) y) =
Σ, 0:34 Σ, b:y; for some a, E Rd. Namely,
(2( inf
(r(0..))
0n PEPa.A.D
Proof. According to the proof of Proposition B. by discarding off-diagonal terms, the maximum
risk of any linear estimator A,B over any hyperrectangles ((T), ((C is reduced.
max T.P. (0A.)) (EO(T).
max TPo.s.D (Odiag( diagg (EB(T).BEA(C)
Further we have:
min max TPo.S (0A,8) 2 min max A.B 0E
max TPP.s.D (Adiag(A)),dn diagg) (B)) A.B TEO,GEA (E@(T).
min max a.b BE
ToO.D (0a.))
min max Pe...DD ( A.) 05
Therefore all four terms have be equal, thus finishing the proof.
Notice (r)) and ACC) are hyperrectangles in Rd. Therefore could decompose the problem to some 2-d problems:
Proposition B.4. Under the same setting as Problem
a). (()))) Σ
RI(TI, Si, D.).
f v) Ar + By minimax linear estimator over Pe(t). then necessarily A, B must be diagonal.
b). (())) Σ RN(TA,G,
Proof of Proposition
B.4
review notation:
FPa.s.D (0A.))
E(z.y)>Po..D 10, 0
-BankK(DD0H0)))-wweeellllll |A By 01
=IIA(De + 8) 10 30 - I
=I[AAD + B B 1 45 Tr(AA TTBBBT
19

---

Under review conference paper at ICLR 2021
Our objective is
(())) D) == min A,B (E
& (0A,B)
max
We will show that restricting A, B to diagonal will not include the RHS value.
For any 7 E @(T), A(). let set ((F.C) {(0,0) (0,, E {(7,, ča), (-T,, } be the subset of vertices of ((7) x ((). Let (F. be uniform distribution on this finite set. Due
the symmetry of this distribution, we have
(= 0: = 0, E [d],
(x.r) 6, = 0, E [d],
E - x) 0,0g = 1; [d]. (x(() 22) ō,d; 2 E [d], (x(+,.) <) 0.6, = - E [d].
We utilize the distribution to find the explicit value of the maximum (in fact the maximum will only be obtained inside the vertices set V)
max PPP.S.D (0 (,,)) 2 ( PPP.S.D A.))) (F.5)
=Bx(F [I(AD) + B 1)0 + A0 + Tr(AAT) + )
-Tr((AD+ + - T)E E [AD B B- 1) T) (r )+
2Tr((AD+ + 1) E + TT(BBB
-Tr((AD+ -- (AD B Tr(A" Adiag(
+T(((A++B-)) (aliag(F()) TTAAA))+T((BB
I[AA+ B- I(AD+B-1).tt + Cll (
2 E((A,D Bü 1)7, + A,5,,² + 13 + B
= (Ii(gi (A)D diag( B) 1)@ + (A))(A))1 + Tr(diag(A))) + Tr(diag(B)
(v(0,)) V(F. 2))
-max v(r.()
+ diag(BB 1)0 + diag(A)8)) + Tr(diag(A))) + Tr(diag (B)3)
Therefore we have:
(L(O(T),A()).
min
max A, (E0(T),8EA(C)
TPP.s.D. (P....
min max
max T.O..DD (0A.B)
A,B (EV)
min max
max (). TPo.s.D
A,B (EA(C)
min
TPP.s.D (0a.b).
a . (E
20

---

Under review conference paper at ICLR 2021
Next, since the optimal solution on the minimizer always obtained by diagonal A, B, it becomes straightforward that each axis could be viewed in separation, thus finishing the proof for part a.
The nonlinear part a straightforward extension of Proposition 4.16 from fronstonnt (011).
Theorem B.5 (Restated Le Cam Two Point Theorem Wainwright (2019)). Let P be a family of distribution, and 0 : P θ is some associated parameter. Let p x R+ be some metric defined on & and Φ R4 + R2, is monotone non-decreasing function with (() = 0. For any a (0, 1).
max = 2 inf sup [ ((P))
P.PP 2 (1)(((()) 2200)
0 PEP
s.t. PM P IV Sa
Lemma B.6. Consider a class of distribution Pr.c. = (...s..lee.6 == Noss0 [0 12), S
T, | S (). Define
Rr(T,S,8) = min max 10S
Egw u.. (f(x) - 0)?
finear
and RN min
max E Ew (f(zz) 0))
9 0
We have
RE(T,C,s) 2T
(T, VC, -,,,>007>>
Proof of Lemma B.6
We first calculate an upper bound of R2 and connect it to lower bound of
Rg.
R)(T,5,5) = min max (as + b 1)0 + ad]² a² b² 0
=min[las 1/T + la|{)² + a² +
a.
S min 2(as 1) + 2a² a² 1..
a.b
By some detailed calculations, we get the RHS is equal to:
27 1)
2T + 2 +) 202 +1
< mmnn(1,27 1 452
}.
s2 +1
For simplify this form, we could see that
Next, use Le cam two point theorem lower bound Ry 5, where the metric p is Euclidean distance and & is squared function. Therefore
1 1 (0) (1)) - a.)
RT(T,C,8) >
max (E.))
2
s.t. [[[(s0 + 01,01] (1(
+ :2, 02] 1llla S
21

---

Under review conference paper at ICLR 2021
Since the total variation distance is related to Bullback-Leiblee divergence by Pinsker's inequality: I| -llv $ v 2 DKkl(l)) it's sufficient to replace the constraint as:
DEL (N([s0) + 81 01] .22 [[ + 02] ,2)) 2a
1 (01 82) -a)
max
06. 0..1 ((1)) 8
s.t. (s01 + 61 (sfl2 52))2 + (01 -02)² - 2a
δ (1 a)
max
1d$2 8
s.t. (sc d)² + 2² < 20
Recall Rt S
2
1+4 3
We first note that c² < 47 and setting a 0 we have Rx 2 22/222 1/4Rt. For In the following we look at other cases when the bound for c² smaller.
When 2 2 sc, will set d sc and e² 2a Let = 2/3 for large we get: c² - a) 2/27 2 2/27
When 2 < we set d -2 and require (sc - 2() + c² < 2a We have (sc 2()² +
2² 2² + 4r² 4ssc + c² s s²2 + 45² - 862 2 = (8² + 1)e² 452. Therefore as
e² 2n 4 the original inequality is satisfied. Again by setting a 2/3 we have
5²+1
²² 2 8/9
1+4
++1 2 8/9RL. Therefore in this case RN 2 RL. 27
C DISCUSSIONS ON RANDOM DESIGN UNDER COVARIATE SHIFT.
In the main text, we present the results where we consider Xg as fixed and Er to be known. In this section, view both source and target input data random, and generalize the results of Section while training is on finite observations and testing is on the (worst case) population loss, under some light-tail properties of the input data samples.
3
C.1 RANDOM DESIGN ON TARGET COVARIANCE MATRIX
In Section we consider the case when Er is known exactly. This could be viewed the fixed design setting where training and testing are on the same set of data. In this section, our analysis will include the estimation error on observing finite unlabeled samples of target domain. Let Xy [x1 I E Ra xd be ny (Here U stands for unlabeled data and is used to distinguish from ny labeled target samples) data samples where E; ~ pr, and we will use the unlabeled target samples to conduct estimation. We let Er = XT XT/nno
Let LB to denote the worst case excess risk measured on the observed target samples: Ls(3)= = 1 (p(ys) 1² To find the best linear estimator that minimizes Lg, our max EB Eys no
22

---

Under review conference paper at ICLR 2021
proposed algorithm becomes:
2 + a² Tr(E ( s.t. (C-1))
Č- Cim min r,C
(10)
ns
And set | = C.S X5 s ys/ng. want to show that in spite the existence estimation error due to the replacement of Σy with Er, our generated / performs well on the worst-case population risk Ls( == 18 Eys En-pr
| (3 B²) and achieves minimax linear risk (up to
constant multiplicative error).
In this section we assume that the data samples is light tail: Definition C.1 -ubbaauussiin distribution).
call distribution p to be -u-suaguussian when there exists > O such that the random vector a ~ p is pl-subgaussian. is the whitening of p
such that a ~ p is equivalent to a = /1/2 p. where Σ is the covariance matrix of p. 6
Notice that here the subgaussian parameter is defined on the whitening of the data, and p doesn't depend on how large ||>||op is.
Theorem C.2. Fix failure probability subgaussian, and the sample size in target domain satisfies ny > p' + log g) Let
(0.1). Suppose target distribution pr is p²-
B : :ys + - X ys where Ö is defined from Eqn. 10 Then with probability at least 1 - over the unlabeled samples from target domain, and for each fixed X from source domain, our learned estimator B(ys) satisfies:
p²(d+ A(d++og(1/0)) (B))
Lb( s (1+
(11)
Specifically, when Ex commutes with Eg or is rank 1, we have:
LB(ß) < (1.25 +005+0( Oly d + log log(+))((1))) )) (B))
(12)
Similarly all other results in the paper could be extended random design with finite samples XT.
Proof of Theorem C.2 The proof relies on the two technical claims C.3
Let 3R be the optimal linear estimator on LB, i.e., (5(( ming linear in ys LB(33 = (B).
LB( (1 (1+00) (1+0l) (d log(1111///00 (16)) (B))
(Claim C.4
n
Ad log( 1/81] (8(RR)
5(1+0(y O(V
(from definition of ()
"
Ad + log(11111100 (1/6)) ))2 (B(z)
<(1+ 0(V
(Claim C.4
n
(d log(1/))) LB( = (1 (1+
(d log(L/o)) Rr,
5(1+0 O(v
n
" << 1, and definition of 3R)
(from ('(tllg(1/1)
'A random vector is called oussuaaausni if for any fixed unit vector of the same dimension, the random variable u is p -subaaaussa i.e., "fe _ T -[[]]]]]]]] < 222/2 (Vs R).
23

---

Under review conference paper at ICLR 2021
From Theorem 3.4 we know R2 (B) I 1,25RR (B) when Ex is rank-1 matrix or commute with Eg which further finishes the whole proof.
Claim C.3 (Restated Claim A.6 from Du al. (2020)) Fix a failure probability (0, 1), and assume n > p' + log(1/))) Then with probability least 1 if x; ~ p and p a pr -u-suaaussiann distribution, we have
16 over the inputs 21, ..... Zn
&
p (d + 1og(1/0))
pld log ))
(1 (1-0(V
1) x1+
(13)
n
n
where 2 = IEzerpp [x
With the help of Claim C.3 we directly get:
Claim C.4. Fix failure probability (0, 1), and assume ny Ad log((16)), XT
II,,... Fnull Rruxd xd satisfies æs ~ pr where pr is p² -usuaaaussaan. We have for any
estimator B:
p + log(1/6)) (B) < LB(3) S <1+ (1 (1 with high probability 5/10 10 over the random samples Xy-
pddd + log(1/5)) (B)))
nu
nu
Proof of Claim
C.4
Recall
1 [x(((yy)) 33)11
Lx( = max Eys
EB
nu
LB(ß) max Ey ( - 3111 3-E8
Therefore for any estimator B it satisfies
LB(š) (B(
=(B(ys) B²) (Es - Es) 3*)
p²(d + log(1/ (1(()))) (B(yus) T)) -3))
so(v
nu
pa(d 1og(1/0)) LB(
=V(V
nu
which finishes the proof.
"Whe this not satisfied the result is still satisfied by replacing Oly pldd+log(1/0) with (maxx{ V (1a+tog(118)) ((attog(118)) }). For cleaner presentation, we assume large enough and simplify the results.
a a
24

---

Under review conference paper at ICLR 2021
C.2 RANDOM DESIGN ON SOURCE DOMAIN.
In the main text the subsection above, the worst case excess risk is upper bounded by 1.25 which achieved by best estimator that is using the same set of training data (Xs, ys). Here we would like to take into consideration the randomness of Xs and compare the worst case excess risk using our estimator with a stronger notion of linear estimator.
For this purpose, we consider estimators that are linear functionals of yn == 2 Rd = ~ (0, / /nsTa) (this o² /ng is the correct scaling since X3 X Xs/ns is comparable to Es). We consider the minimax linear estimator with y/ and with access to Lis, and we compare our estimator against this oracle linear estimator. This estimator is not computable in practice since Vs must be estimated, but we will show that our estimator within an absolute multiplicative constant in minimax risk of the oracle linear estimator.
E
To recap the notations and setup, let
1 |X (3(s)) BT)
(33 = max E uy nu
LB(3) = max Bys E Eawpy >| (((()))))) B*]13
19-
(B, == max Eyn E Emppr x (ß(yR) B²1
/3
Our target is to find the best linear estimator using (3( (trained with X7) and prove its per- formance on the population (worst-case) excess risk Ls(3) is no much worse compared to the minimax linear risk trained on yR and Σg-
Theorem C.5. Fix a failure probability 5 E (0,1). 1). Suppose both target and source distributions and pr are p²-subgaussian and the sample sizes in source domain and target domain satisfies ns. ny >> p²(d + log 1)). Let Ò be the solution for Eqn.(10) and set B(ys) + E.. X3 ys. Then with probability least 1-6 å over all the unlabeled samples from target domain and all the labeled samples X from source domain, our estimator (yYR) yields the worst case expected excess risk that satisfies:
(d + log (1/8)) + O
pd + log(1/0))
LB( -
1+
min G linear in
LR.
nu
71
Proof of Theorem C.5 For each matrix C E Rdxd, we first conduct bias-variance decomposition and rewrite each worst-case risk with linear estimator in terms of a matrix C., When B(ys) = C.S X3 ys. we have:
-=(0)=111)) -11-1//(C 1) o² n 0² L=(,)=11=)/ -||=_// me 2 n TEE,Ci,"")==100))
=())))))'))==((())
Similarly, when 8n C35 1/2 yR. we have:
[R =1/=/// (C n1 + _ (T
n
25

---

Under review conference paper at ICLR 2021
Claim C.6. Fix a failure probability 8 E (0, 1), and assume ny. ns > p' log(1/6)), ()g()0((11/)) Xs e R X E Ruexd are respectively from ps pr which are both pi-subgaussion. We have for any matrix C E Rdxd:
Ad log(1/6)) ))((C) (C)) = (1+
pd + log(1/6)) ))(
(1 (1-OT)
nu
ny
with high probability 1 - 5/110 over the random samples Xy.
(1 11-1 p² + 1og((1))) ))((C) & (R(C) S (1 (1+01)
pd + log(1/6)) )(()),
ns
ng
with high probability 8/ 10 over the random samples Xs-
Proof of Claim C.6
We omit the proof of the first incquality since it's exactly the same as proof of
Claim C.4
For the second line, we have:
o²
In(C) - ((C)
TT CE -5g)CT)
ns
Ad + log(1 a²
<0(1
ns
ns
p + log( (1/8)) J((C).
<0(1
ng Therefore we prove the RHS of the second inequality. The LHS follows with the same proof techniques.
Now let Ò be the minimizer for i(C), and Cn be the minimizer for RC())
p² + log (1/8)) )(((C)
(()) 11
(w.p. 1 - 6/10; due to Claim C.6
ny (tdd + log(1/8)) ))((CR)
<(1 + $(1+0
V
(Due to the definition of Ć)
nu (d + log(1 (1/))) (((()
<(1 <(1+0 <(1+0(
(w.p. 1 5/5; due to Claim C.6
nu (d + log(1 (1/)) )(((
=(1 + 1
(since ny is large enough)
nu
p= + ((d+log(1/d)) log(1/5)) (]
p + log(1/5)) ()R
<(1 + +0(
0(1
ny
nr
(w.p. - 35/10; due to Claim C.6
26

---

Under review conference paper at ICLR 2021
-1+0 p¹(d log(1/61)
OGV + log (1/(1)
min (C().
nr
C
This finishes the proof.
D MORE EMPIRICAL RESULTS
We include some more empirical studies. In the main text our results have small noise. Here we show some more results with larger noise, and also the case with varied eigenspace. For the following results, we use 10 and r 0.2vd. Other meta data remains the same presented in the main text. Figure (a) show similar phenomenon as the small noise setting presented
Seage
Singg
S-nde
0,71
or-
0.2
024
32
0.2
2.0
1.0
930
3.00
0.39
035
3.50
59
100
11.
covariate eigen-spectrum
(b) signal strength
(c) covariate eigenspace
Figure 2: (a): The x-axis a defines the spread of eigen-spectrum of Eg: x 1/1 4 x 1/i. (b) x-axis the normalized value of signal strength: |Er,"'///r. (c) X-axis the covariate shift due to cigenspace shift measured by |Us Ur F..
the main text. From Figure 2 (c) we see no particular relationship between the performance of each algorithm with eigenspace shift.
D.I EXPERIMENTS WITH APPROXIMATION ERROR
Finally, we conduct empirical studies with nonlinear models.
Setup. We choose ns 2000, d 50. Let Xs E IR 2000 be generated randomly under Gaussian distribution (0, Es). We also gener- ate a small validation dataset from target domain: Xev E 5500x50 sampled from (0, Er), ycv (* + zcv, with žcy ~ (0000 We choose ((Es)
0.20
OLS
teneighhing
5.19
todge
017
9.6
5.5
(Err & 1/i, and the eigenspace for both Eg and Σr are random orthonormal ma- d.) The ground truth model is a one-hidden-layer ReLU network: (*) 1/da T (Wx) where W and a are ran- domly generated from standard Gaussian distribution. We observe noisy labels: ys = f*)) + z. where
trices. E|
|E
0.2
0.5
0..
0.b
0.7
0.8
1.0
Figure The x-axis is noise level and y- axis is the excess risk (with approximation error).
24 (0,
27

---

Under review conference paper at ICLR 2021
Estimating weights Pr (x))/s((z). Since the generated data samples are Gaussian, the absolute weights for pr(x) (r()s/ps((r
v Er exp( (Is² Ex²))²) However, this absolute value has exponential factor and can amplify the noise level. Meanwhile, when one multiplies both Xs, ys by 10, the ground truth doesn't change but the absolute value for pr will change drastically. This discrepancy highlights the importance of relative magnitudes (among samples) instead of the absolute value Kanamori et al. (2099).
To obtain relative score, first estimate the absolute value of pr(x))/s(x)) by ((x) := x T -'g' Σ )a We then uniformly assign the weight for each sample by 10 discrete values 1,2,3 .. 10 based on their scoring ((x) and then rescale the reweighting vector properly.
We implement for the results. The baselines we choose are ordinary least square ("OLS" in Figure (3), ridge regression (Legend "Ridge") and classic weighted least square Kanamori et al. (2009) (Legend is "Reweighting": BLS in our main text). For both ridge regression and our methods, we tune hyperparameters through cross-validation. All results are presented from 40 runs where the randomness comes from f* and the eigenspaces of Σs, Σr.
method (Eqn. using the estimated weights above. Refer Figure 3
28


Reviews:
[{"review_id": "xawwNaYVrWS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper studies the problem of domain adaptation for linear regression problem.\n\n1. First the authors consider a well-specified model where only the distribution of the covariates changes. For this case the authors propose a linear estimator, and show that under assumptions which guarantees the reduction of the problem to Gaussian sequence, this estimator is within a constant factor from the minimax risk of non-linear estimators. \n2. Then, the authors turn their attention to the miss-specified case of the above model. They again develop an estimator whose maximal risk is shown to match the minimax one (for linear estimators).\n3. The authors consider a well-specified model allowing the vector $\\beta^*$ to be changes from source to target. Similar results as for the previous case are derived.\n4. The authors conduct simulation study comparing their estimators with the ridge regression.\n\n\npros: the developed estimators are theoretically grounded\n\ncons: after several readings I still cannot understand why this work is on domain adaptation. Since the authors consider the problem of linear regression with fixed design, the domain adaptation part simply reduces to the re-weighting of the norm.\n\nI am leaning towards rejection, but I am willing to raise the score if the authors are able to address my questions below.\n\nQuestions:\n1. The authors work with the fixed design setup, that is, the expectation in the risk is taken only w.r.t. the signal $y_S$. What is the meaning of source and target data when the designs are fixed? For instance, in section 3.3. can we simply pull together $y_S, y_T$ and $X_S, X_T$ and apply the result of previous section? \n2. The authors should clarify how their first contribution is different from that of **Blaker, Minimax estimation in linear regression under restrictions, 2000** (Theorem 1 and the discussion after it). \n3. In Theorem 3.4 there is a condition that $\\Sigma_S, \\Sigma_T$ should commute. Isn't it $\\hat{\\Sigma}_S$ instead? If not, what is the reason to introduce this assumption if the design is fixed?\n4. If the covariance matrix on the target is unknown, we would have to estimate it using unlabelled sample. Did you investigate a theoretical or empirical impact on the problem?\n\nSuggestion: It might be useful to write few lines explaining why the excess risk on the target reduces to the 2-norm re-weighted by the target covariance.\n\n\nAfter rebuttal: They authors have addressed my questions. I hope that the authors will carefully review classical literature on weighted minimax linear estimator in their final version. I raise my score to marginally above acceptance threshold, since I am still not convinced in the importance of domain adaptation for fixed design regression. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "gokS7YgtSxf", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "### Summary\nThis paper derives estimators for regression under additive Gaussian noise and distributional shift (mostly covariate and also some model shift) that enjoy minimax properties.\n\n### Strengths\n+ Sample complexity bounds, let alone matching lower bounds, are only recently being proposed for various realistic frameworks with distributional shift. This paper is thus timely and well-motivated.\n+ The presentation is clear, and most analysis steps are well-delineated.\n+ The insight that linear sufficient statistics could achieve minimax rates is valuable and the comparison to ridge regression, especially when accounting for the target, is enlightening.\n\n### Weaknesses\n- Some of the assumptions are rather strong. Assuming that the target covariance $\\Sigma_T$ is known is somewhat acceptable. But when dealing with model shift, the paper assumes knowing the entire marginal distributions in the source $p_S$ and target $p_T$ (to get the importance weights $\\mathbf{w}$), which effectively sidesteps the covariate shift entirely.\n- ~~*[Major]* In the proof of Claim 3.1 (page 12), a key step appears wrong to me: namely the step that says “Cross term vanishes”. While it’s true that  $W^\\intercal X_S = 0$, the outer product $X_S W^\\intercal$ is not, and neither is $X_S A_1^\\intercal A_2 W^\\intercal$ that appears in the cross product and which could contribute negatively with varying $A_2$. Now it could be that this claim can be patched, which is why I judge the rest of the paper by assuming it’s true. I do the same for Claims 3.6 and 3.8, which suffer from the same issue. (Claim 3.8 just relies on the previous two, and Claim 3.6 omits the same  cross term on the third line of page 16, which invalidates the argument on the first two lines of the paragraph that follows “it only appears in the third and last non-negative terms”.)~~\n\n### Comments\n* Throughout $X$ is assumed to be centered, I believe. Best to state this explicitly.\n* The definition of a sufficient statistic in footnote 2 is not the right one to use, since we cannot talk of independence when $\\beta^\\star$ is an unknown parameter. (A corresponding justification of (1) as sufficient statistic should then be given, using sufficiency of optimal estimation.)\n* Typos:\n   - the dimension of $X_S$ is $n_S \\times d$ (subscript $S$ missing)\n   - in the last equation of page 4 I believe the reference should be to Claim 3.1\n   - in section 4 $\\bar\\beta_T$ needs a division by $n_T$\n   - in the proof of Claim 3.1, “This is to show […] minimax *linear* estimator”\n   - in the proof of Theorem 3.2, second line, divide $\\mathbf{y}_T$ by $n_S$ and insert a missing $=$ sign before $\\theta^\\star_T$; in the third line change the subscript of $\\Sigma$ to $T$ in the definition of $\\Theta$; generally make sure the bolding convention is kept in this (otherwise rather nice) proof\n\n### Overall\n\nMinimax estimators for distributional shift can be very useful. But the paper has some lack of clarity and potential flaws, which is the only reason behind my current rating.\n\n_[Edit: The authors clarified that the flaw I was talking about isn't there. I updated my review accordingly. The score is based on the fact that the paper can use some polish to improve clarity and the fact that some of the assumptions, even if traditional, are too strong (in essence, sample complexity bound will become meaningless if what is assumed known itself is too sample-intensive to approximate).]_\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZJ_1Qi4LbUb", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "## Summary\nThe authors propose a near minimax optimal linear estimator under distribution shift. They have estimators for when there is a covariate shift (i.e. the underlying data distribution) or model shift (i.e. the distribution of the label given the features of the data).\n\n## Strengths\n* The authors provide bounds for both data coming from linear and non-linear generative models\n* The authors analyze model shift in addition to covariate shift\n* Experiments showing the results on simulated data\n\n## Weaknesses\n* No experiments for the non-linear data generation model\n\nUpdate: after reading the arguments and comments from my fellow reviewers, I was convinced by their reasoning that the paper did not merit my original high score. I would like to therefore change my score to a 6.\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review:  
This paper derives estimators and minimax guarantees for regression under additive Gaussian noise and distributional shift 
Despite, some merits raised, limitations on too strong assumptions (knowing the entire marginal distributions, sample complexity bound that could become meaningless if what is assumed known itself is too sample-intensive to approximate) were considered important drawbacks by the reviewers.
Last but not least, the importance of domain adaptation for fixed design regression was questioned and the answer to that point was not convincing enough. 
Decision: Reject