# Domain adaptation under structural causal models

Yuansi Chen<EMAIL_ADDRESS>Peter Bühlmann
<EMAIL_ADDRESS>
Seminar for Statistics
ETH Zürich
Zürich, Switzerland

###### Abstract

Domain adaptation (DA) arises as an important problem in statistical machine
learning when the source data used to train a model is different from the
target data used to test the model. Recent advances in DA have mainly been
application-driven and have largely relied on the idea of a common subspace
for source and target data. To understand the empirical successes and failures
of DA methods, we propose a theoretical framework via structural causal models
that enables analysis and comparison of the prediction performance of DA
methods. This framework also allows us to itemize the assumptions needed for
the DA methods to have a low target error. Additionally, with insights from
our theory, we propose a new DA method called CIRM that outperforms existing
DA methods when both the covariates and label distributions are perturbed in
the target data. We complement the theoretical analysis with extensive
simulations to show the necessity of the devised assumptions. Reproducible
synthetic and real data experiments are also provided to illustrate the
strengths and weaknesses of DA methods when parts of the assumptions in our
theory are violated.

Keywords: anticausal, conditionally invariant components, domain
generalization, domain invariant projection, label shift, structural equation
models

##  1 Introduction

Domain adaptation (DA) is a statistical machine learning problem in which one
aims at learning a model from a labeled source dataset and expecting it to
perform well on an unlabeled target dataset drawn from a different but related
data distribution. Domain adaptation is considered a sub-field of transfer
learning and also a sub-field of semi-supervised learning (Pan and Yang,
2009). The possibility of DA is inspired by the human ability to apply
knowledge acquired on previous tasks to unseen tasks with minimal or no
supervision. For example, it is common to believe that humans who learned
driving in sunny days would adapt their skills to drive reasonably well in a
rainy day without additional training. However, the scenario where the source
and target data distribution is different (e.g. sunny vs. rainy) is difficult
to handle for many machine learning systems. This is mainly because the
classical statistical learning theory mostly focuses on statistical learning
methods and guarantees when the training and test data are generated from the
same distribution.

While existing DA theory is limited, more and more application scenarios have
emerged where DA is needed and useful. DA is desired especially when obtaining
unlabeled data is cheap while labeling data is difficult. The difficulties of
labeling data typically arise due to the required human expertise or the large
amount of human labor. For example, to annotate the ImageNet Large Scale
Visual Recognition Challenge (ILSVRC) dataset (Russakovsky et al., 2015) with
more than 1.2 million labeled images, it costs an average worker on the Amazon
Mechanical Turk (www.mturk.com) about 0.5 seconds per image (Fei-Fei, 2010).
Thus, annotating more than 1.2 million images requires more than 150 human
hours. The actual time needed for labeling is much longer, due to the
additional time spent on label verification and on labeling the images which
are not used in the final challenge. Now if one is only interested in a
similar but different task such as classifying objects in oil paintings, one
cannot expect the ILSVRC dataset which contains pictures of natural objects to
be representative. As a consequence, one needs to collect new data. It is
relatively easy to collect digital images for the new task, but it is costly
to label them if human experts have to be involved. Similar situations where
the labeling is costly emerge in many other fields such as part-of-speech
tagging (Ratnaparkhi, 1996; Ben-David et al., 2007), web-page classification
(Blum and Mitchell, 1998), etc.

Despite the broad need of DA methods in practice, a priori it is impossible to
provide a generic solution to DA. In fact, the DA problem is ill-posed if
assumptions on the relationship between the source and target datasets are
absent. One cannot learn a model with good performance if the target dataset
can be arbitrary. As it is often difficult to specify the relationship between
the source and target datasets, a large body of existing DA work are driven by
applications. This line of work often focuses on developing new DA methods to
solve very specific data problems. Despite the empirical success on these
specific problems, it is not clear why DA succeeds or how applicable the
proposed DA methods are to new related data problems. The growing development
of domain adaptation calls forth a theoretical framework to analyze the
existing methods and to guide the design of new procedures. More specifically,
can one formulate the assumptions needed for a DA method to have a low target
error? Can these assumptions be itemized, so that once specified the
performance of different DA methods can be compared? More specifically, does
the causal direction of the data generation or the type and location of data
perturbation (Figure 1) affect the choice of the best DA method?

To answer the above questions, this work develops a theoretical framework via
structural causal models that enables the comparison of various existing DA
methods. Since there are no clear winning DA methods in general, the
performance of DA methods has to be analyzed and compared with precise
assumptions on the underlying data structure. Through analysis on simple
models, we aim to give insights on when and why one DA method outperform
others.

(i) causal prediction$X_{1}$$X_{2}$$Y$

(ii) anticausal$X_{1}$$X_{2}$$Y$

(iii) mixed$X_{1}$$X_{2}$$Y$

Figure 1: (i) causal prediction setting where the label $Y$ is the descendant
of the covariates $X$. The hammers indicate the location of data perturbation.
(2) anti-causal prediction setting where all the covariates $X$ are
descendants of the label $Y$. (3) mixed-causal-anticausal setting where some
covariates are descendants of the label $Y$ and some covariates are ancestors
of $Y$. Would the causal direction of the data generation affect DA
performance? Would changing the location of the perturbation (black hammer vs.
white hammer) cause some DA methods to fail?

##### Our contributions:

Our contributions are three-fold. First, we develop a theoretical framework
via structural causal models (SCM) to analyze and compare the prediction
performance of existing DA methods, such as domain invariant projection (DIP)
(Pan et al., 2010; Baktashmotlagh et al., 2013) and conditional invariance
penalty (CIP) or conditional transferable component (Gong et al., 2016;
Heinze-Deml and Meinshausen, 2021), under precise assumptions relating source
and target data. In particular, we show that under linear SCM the popular DA
method DIP is guaranteed to have a low target error when the prediction
problem is anticausal without label distribution perturbation. However, DIP
fails to outperform the estimator trained solely on the source data when there
are perturbations on the label distribution or when the prediction problem is
either causal or mixed-causal-anticausal. Second, based on our theory, we
introduce a new DA method called CIRM and develop its variants which can have
better prediction performance than DIP in mixed-causal-anticausal DA scenarios
and those with label distribution perturbation. Third, we illustrate via
extensive simulations and real data experiments that our theoretical DA
framework enables a better understanding of the success and failure of DA
methods even in cases where presumably not all assumptions in our theory are
satisfied. Our theory and experiments make it clear that knowing the relevant
information about the data generation process such as the causal direction or
the existence of label distribution perturbation is the key to the success of
domain adaptation.

The rest of the paper is organized as follows. In Section 2 we review previous
ways to mathematically formulate the DA problem and summarize the existing DA
methods. Section 3 contains background on structural causal models, our
problem setup, a formal introduction of the DA methods to study and three
simple motivating examples. In Section 4 we analyze and compare the
performance of three DA methods (DIP, CIP and CIRM) under our theoretical
framework. Based on whether the DA problem is causal, anticausal or mixed and
whether there is label distribution perturbation, we identify scenarios where
these DA methods are guaranteed to have low target errors. Section 5 contains
numerical experiments on synthetic and real datasets to illustrate the
validity of our theoretical results and the implication of our theory for
practical scenarios.

##  2 Related work

Domain adaptation is a sub-field of the broader research area of transfer
learning. More specifically, domain adaptation is also named transductive
transfer learning (Pan and Yang, 2009; Redko et al., 2020). In this paper, we
concentrate on the DA problem without diving into the broader field of
transfer learning. Consequently, many previous work on transfer learning are
omitted for the sake of space. We direct the interested readers to the survey
paper by Pan and Yang (2009) and references therein for a literature review on
transfer learning. Focusing on the DA problem, we first review existing
theoretical frameworks of DA and then provide an overview of DA methods and
algorithms.

##### Theoretical DA frameworks:

The DA problem is ill-posed if one does not specify any assumptions on the
relationship between the source and target data distribution. For this reason,
depending on how this relationship is specified, many ways to formulate the DA
problem have been introduced.

Ben-David et al. (2007) were the first to provide a DA prediction performance
bound via Vapnik-Chervonenkis (VC) theory for classifiers from a generic
hypothesis class. Since this bound is obtained without making explicit
assumptions on the relationship between the source and target data
distribution, it involves a divergence term that characterizes the closeness
of the source and target distribution. A follow-up from Ben-David et al.
(2010) further formally proves the necessity of assuming similarity between
source and target distribution to ensure learnability. Ben-David et al.’s work
laid the foundation of many further studies that attempt to bound the target
and source prediction performance difference via divergence measures (Mansour
et al., 2009; Cortes and Mohri, 2011, 2014; Cortes et al., 2015; Hoffman et
al., 2018). See also the survey paper by Redko et al. (2020) for a complete
review of VC-theory-type DA prediction performance bounds.

One natural way to explicitly relate the source and target data distribution
is to assume that both of them are generated via the same well-specified
generative model and to treat the missing target label problem as a missing
data problem. Given a well-specified probabilistic generative model, the
problem of imputing the missing data is well-studied and it is commonly solved
via the expectation maximization (EM) algorithm (see McLachlan and Krishnan,
2007). This idea of casting a DA problem to a missing data problem has been
introduced in Amini and Gallinari (2003) and Nigam et al. (2006).

It is also possible to loosely relate the source and target data distribution
by assuming that they differ only by a small amount. How to specify this
“small amount” depends on applications. If one assumes that the source data
distribution is contaminated so that it is $\epsilon$ total variation distance
away from the target data distribution, then the problem goes back to the
classical robust statistics literature (Huber, 1964; Yuan et al., 2019). More
recently, Wasserstein distance or $f$-divergence have been considered to
describe the difference between source and target data distribution. These
work and contributions are referred to as distributional robust learning
(Sinha et al., 2018; Duchi and Namkoong, 2018; Gao et al., 2017). A closely
related line of work directly assumes that target data points can be
interpreted as source data points contaminated with arbitrary small additive
noise quantified via norm constraints ($\ell_{1}$ or $\ell_{\infty}$). This
direction is called adversarial machine learning (Goodfellow et al., 2018;
Raghunathan et al., 2018).

Another way to make the DA problem tractable is to assume that the conditional
distribution $Y\mid X$ is invariant across source and target data, where $Y$
and $X$ denote the response (label) and covariates, respectively. The only
difference between source and target distributions comes from the change in
the distribution of the covariates $X$. This type of assumption is called the
covariate shift assumption (Quionero-Candela et al., 2009; Sugiyama and
Kawanabe, 2012; Storkey, 2009). Alternatively, assuming the other conditional
distribution $X\mid Y$ distribution to be invariant is also plausible in
certain applications. This approach has a similar name called the label shift
assumption (Lipton et al., 2018; Azizzadenesheli et al., 2019; Garg et al.,
2020).

Finally on the causality side, it has been pointed out by Pearl and Bareinboim
(2014) that full specification of a structural causal model (SCM) allows to
study transportability of learning methods on the relationship between
variables in the structural causal model. We refer to this approach as full-
SCM transfer learning. The full-SCM transfer learning approach is very
powerful in describing many data generation models. However, the main drawback
of this framework is that the full specification of the structural causal
model might be difficult to learn in many applications with limited data. On
the other hand, the pioneering work by Schölkopf et al. (2012) reveals that
distinguishing between the causal and anticausal prediction may already be
useful to facilitate the selection of DA and semi-supervised learning methods.
Figuring out the right amount of causal information needed to carry out DA is
one of our main motivations in this paper.

##### Previous DA methods:

While it is in general helpful to have theoretical DA frameworks to relate the
source and target data, theory is not essential for the development of new DA
methods. A large number of DA methods and algorithms were introduced with the
focus of addressing DA for specific datasets. Here we highlight several
popular ones.

Self-training (Amini and Gallinari, 2003) is one of the earliest DA methods
which is originated in the semi-supervised learning literature (see the book
by Chapelle et al., 2009). The self-training algorithm begins with an
estimator trained on the source data, and gradually labels a part of unlabeled
target data and then updates the estimator with appropriate regularization
after combining newly labeled target data. It has been shown to have good
empirical performance on several computer vision domain adaptation tasks with
small labeled source datasets (Xie et al., 2020; Carmon et al., 2019). A
theoretical analysis of the performance of self-training under a gradual shift
assumption on Gaussian mixture data was recently provided by Kumar et al.
(2020).

An important line of DA methods relate the source and target data by assuming
the existence of a common subspace. Pan et al. (2010) first came up with the
idea of projecting the source and target data onto a reproducing kernel
Hilbert space to preserve common properties and applied the idea to text
classification datasets. The existence of an intermediate subspace that
relates source and target data was made precise in Gopalan et al. (2011) for
visual objection recognition datasets. This method was further developed and
analyzed for sentiment analysis and web-page classification (Blitzer et al.,
2011; Gong et al., 2012; Muandet et al., 2013). Baktashmotlagh et al. (2013)
simplified the idea of enforcing a common subspace to adding a regularization
term based on the maximum mean discrepancy (MMD) (Gretton et al., 2012). Their
method is named domain invariant projection (DIP) because the regularization
term enforces a projection of the source and target data on the subspace to be
invariant in distribution. Recently, with the development of deep neural
networks and the introduction of generative adversarial nets based
distributional distance measures, the common subspace approach was further
extended to allow for neural network implementations (Ganin et al., 2016; Peng
et al., 2019).

The empirical success of DIP like DA methods and their neural network variants
such as in Ganin et al. (2016) has sparked a wide discussion on the general
validity of these methods. Zhao et al. (2019) constructed a simple
counterexample showing that domain invariant projection is not sufficient to
guarantee successful domain adaptation. Furthermore, Zhao et al. (2019)
provided a lower bound of the target error when the label distribution is
perturbed. Johansson et al. (2019) illustrated via a simple example the danger
of the blind use of distributional distance such as MMD for domain invariant
penalization. Li et al. (2019) and Tachet des Combes et al. (2020) discussed
the failure of DIP in the presence of target label perturbation and proposed
label shift correction using conditional invariant features. However, it is
not clear whether their proposed algorithms have any guarantees for estimating
the conditional invariant features or achieving low target error. The mixed
messages about the success and failure of DIP like DA methods motivate us to
set up rigorous target error comparisons of DIP and other DA methods.

Another line of DA methods that is worth mentioning is the one that only makes
use of source data. Gong et al. (2016) introduced conditional transferable
components which consist of features that are have invariant distributions
given the label. The search of conditional transferable components is achieved
via a penalty that matches the conditional distribution for any label across
source environments. A related idea was proposed by Heinze-Deml and
Meinshausen (2021). They extract the conditionally invariant (or core)
components (CICs) across data points that share the same identifier but have
different style features. The invariance is enforced via adding a conditional
variance penalty to the training loss. Enforcing the conditional invariance
allows them to learn models that are robust across perturbed computer vision
datasets. Later, other concepts of invariance beyond conditional invariance
across source environments were developed, such as invariant risk minimization
(Arjovsky et al., 2019). It should be noted that, though with a different
focus, the idea of using the heterogeneity across multiple source datasets to
learn invariant or robust models has also appeared in the causal inference
literature (Peters et al., 2016; Meinshausen, 2018; Rothenhäusler et al.,
2021). Based on these ideas, Rojas-Carulla et al. (2018) and Magliacane et al.
(2018) provided guarantees for domain adaptation under the assumption that the
conditional distribution of the label given some subset of covariates is
invariant.

There are many other interesting DA methods that are less related to our work.
For the sake of space, we direct the interested readers to the book by
Chapelle et al. (2009) on semi-supervised learning and other surveys (Zhu,
2005; Wilson and Cook, 2020; Wang and Deng, 2018) for additional references.

##  3 Preliminaries and problem setup

In this section, we first provide a brief summary of structural causal models,
which are essential components of our theoretical framework. Then we formalize
our domain adaptation problem setup and introduce the DA methods we study.
Finally, we provide three simple motivating examples to illustrate the need of
a DA theory.

###  3.1 Background on structural causal models

Structural causal models (SCMs) (see Pearl, 2000) are introduced to describe
causal relationships between variables in a system. A SCM integrates the
structural equation models (SEMs) used in economics and social sciences, the
potential-outcome framework of Neyman (1923) and Rubin (1974), and the
graphical models developed for probabilistic reasoning and causal analysis. A
SCM can be seen as a set of generative equations that describe not only the
data generation process of the observational data, but also that of the
intervention data. We refer the readers to Chapter 7 of the book by Pearl
(2000) for a detailed description of SCM for causal inference. In the context
of DA, SCMs can be used to describe both the data generation process of the
source and target domains (or environments). The SCMs are specified via a set
of structural equations with a corresponding causal graph to describe the
relationship between variables.

While SCMs are very powerful tools to describe data generation processes in
interventional environments, fully specifying a SCM for a DA problem has two
main drawbacks in practice: first, defining the functional forms that relate
variables in a SCM can be difficult for data involving many variables; second,
even if the functional forms are specified, learning all the functions from
data may result in a more complicated statistical learning task than the
original DA problem. Focusing on solving DA problems, the way we address the
two main drawbacks differentiates our work from the full-SCM transfer learning
approach by Pearl and Bareinboim (2014).

To address the first drawback and to ease our theoretical analysis, we adopt a
simplification that replaces all the functional models in the SCM with linear
models as in previous work (Peters et al., 2016; Rothenhäusler et al., 2021,
2019). We call this simplified SCM a linear SCM. The simplification allows us
to develop rigorous DA theory and to study more complicated DA problems as
extensions of the linear case. Regarding the second drawback, we focus on DA
methods that can be applied without relying on the full specification of the
SCM. Only when we analyze the performance of these DA methods, we bring in
SCMs to set forth the assumptions needed for the DA methods to have low target
errors.

###  3.2 Domain adaptation problem setup

In this subsection, we set up the domain adaptation problem with $M$ ($M\geq
1$) labeled source environments and one unlabeled target environment. Although
SCMs are general enough to also handle classification problems, we focus our
theory on regression to simplify the presentation. Later in Section 5, we show
the adaptation of our results to the classification setting through numerical
experiments.

For the $m$-th source environment ($m\in\left\\{1,2,\cdots,M\right\\}$), we
observe $n_{m}$ i.i.d. samples
$S^{\text{\scriptsize$(m)$}}=\left((x_{1}^{\text{\scriptsize$(m)$}},y_{1}^{\text{\scriptsize$(m)$}}),\cdots,(x^{\text{\scriptsize$(m)$}}_{n_{m}},y^{\text{\scriptsize$(m)$}}_{n_{m}})\right)$
drawn from the source data distribution
$\mathcal{P}^{{\text{\scriptsize$(m)$}}}$, with
$(x_{k}^{\text{\scriptsize$(m)$}},y_{k}^{\text{\scriptsize$(m)$}})\in^{d+1}$
for each $k\in\left\\{1,2,\cdots,n_{m}\right\\}$. The $m$-th dataset is also
called the $m$-th source environment. Furthermore, there are $\tilde{n}$
i.i.d. samples
$\tilde{S}=\left((\tilde{x}_{1},\tilde{y}_{1}),\cdots,(\tilde{x}_{\tilde{n}},\tilde{y}_{\tilde{n}})\right)$
from the target distribution $\widetilde{\mathcal{P}}$, but we only observe
the covariates
$\tilde{S}_{X}=\left(\tilde{x}_{1},\cdots,\tilde{x}_{\tilde{n}}\right)$ from
$\widetilde{\mathcal{P}}_{X}$. Here $\widetilde{\mathcal{P}}_{X}$ is used to
denote the marginal distribution of $\widetilde{\mathcal{P}}$ on $X$. The goal
of the DA problem is to estimate a function $f_{\beta}:^{d}\mapsto$, mapping
covariates to the label, parametrized by $\beta\in\Theta$ so that the target
population risk is “small”. Here the parameter space $\Theta$ is a subset of a
finite-dimensional space. The performance metric target population risk for an
estimator $f$ is defined as

$\displaystyle\tilde{R}(f)={\mathbb{E}}_{(X,Y)\sim\widetilde{\mathcal{P}}}\left[l(f(X),Y)\right],$
(1)

where $l$ is a loss function and it is set to the squared loss function
$x\mapsto x^{2}$ if not specified otherwise. Similarly, we can define the
$m$-th source population risk as

$\displaystyle
R^{\text{\scriptsize$(m)$}}(f)={\mathbb{E}}_{(X,Y)\sim\mathcal{P}^{\text{\scriptsize$(m)$}}}\left[l(f(X),Y)\right].$
(2)

In addition to the risk on an absolute scale, one can quantify the target
population risk achieved by an arbitrary estimator on a relative scale by
comparing it with the oracle target population risk
$\tilde{R}(f_{\beta_{\text{oracle}}})$, where $\beta_{\text{oracle}}$ is
defined as

$\displaystyle\beta_{\text{oracle}}\in\operatorname*{arg\,min}_{\beta\in\Theta}{\mathbb{E}}_{(X,Y)\sim\widetilde{\mathcal{P}}}\left[l(f_{\beta}(X),Y)\right].$

If we don’t assume any relationship between the source distribution
$\mathcal{P}^{\text{\scriptsize$(m)$}}$ and the target distribution
$\widetilde{\mathcal{P}}$, the target population risk of an estimator learned
from the source and unlabeled target data can be arbitrarily larger than the
oracle target population risk. Assumptions on the relationship between source
and target distribution are needed to make the DA problem tractable. In this
work, we consider the DA setting where source and target data are both
generated through similar linear SCMs with additional structural assumptions
on the interventions.

##### Domain adaptation under linear SCM with noise interventions:

For $m\in\left\\{1,2,\cdots,M\right\\}$, the data distribution
$\mathcal{P}^{\text{\scriptsize$(m)$}}$ of the $m$-th source environment is
specified by the following data generation equations on
$\left(X^{\text{\scriptsize$(m)$}},Y^{\text{\scriptsize$(m)$}}\right)$ from
$\mathcal{P}^{\text{\scriptsize$(m)$}}$,

$\displaystyle\begin{bmatrix}X^{\text{\scriptsize$(m)$}}\\\
Y^{\text{\scriptsize$(m)$}}\end{bmatrix}=\begin{bmatrix}\mathbf{B}&{b}\\\
{\omega}^{\top}&0\end{bmatrix}\begin{bmatrix}X^{\text{\scriptsize$(m)$}}\\\
Y^{\text{\scriptsize$(m)$}}\end{bmatrix}+g(a^{\text{\scriptsize$(m)$}},\varepsilon^{\text{\scriptsize$(m)$}}),$
(3)

and the target data distribution $\widetilde{\mathcal{P}}$ is specified via
the same equation except for the noise distribution,

$\displaystyle\begin{bmatrix}\widetilde{X}\\\
\widetilde{Y}\end{bmatrix}=\begin{bmatrix}\mathbf{B}&{b}\\\
{\omega}^{\top}&0\end{bmatrix}\begin{bmatrix}\widetilde{X}\\\
\widetilde{Y}\end{bmatrix}+g(\widetilde{a},\widetilde{\varepsilon}).$ (4)

Here $\mathbf{B}\in^{d\times d}$ is an unknown constant matrix with zero
diagonal such that $\mathbb{I}_{d}-{\mathbf{B}}$ is invertible, ${b}\in^{d}$
and ${\omega}\in^{d}$ are unknown constant vectors;
$\varepsilon^{\text{\scriptsize$(m)$}}$ and $\widetilde{\varepsilon}$ are
$d+1$ dimensional random vectors drawn from the same noise distribution
$\mathcal{E}$; $g$ is a fixed function to model the change (or intervention)
across source and target environments; $a^{\text{\scriptsize$(m)$}}\in^{d+1}$
is an unknown (random or non-random) intervention that changes from one
environment to another. Note that the assumption on the invertibility of
$\mathbb{I}_{d}-{\mathbf{B}}$ ensures the uniqueness of the data generation
given a draw of the noise $\varepsilon^{\text{\scriptsize$(m)$}}$. This
assumption is in general weaker than requiring the corresponding causal graph
to be directed acyclic (Rothenhäusler et al., 2019).

The only difference between the source and target data distribution is due to
the difference in intervention $a^{\text{\scriptsize$(m)$}}$ and
$\widetilde{a}$. According to the SCM, the way we specify the difference
between source and target distribution is through the term
$g(\widetilde{a},\widetilde{\varepsilon})$. This type of intervention is often
called noise intervention or soft intervention (Eberhardt and Scheines, 2007;
Peters et al., 2016). As a concrete example, if the mean shift noise
intervention is considered, then we specify the function
$g:^{d+1}\times^{d+1}\rightarrow^{d+1}$ as $(a,\varepsilon)\mapsto
a+\varepsilon$, and define the intervention term with a deterministic vector
in d+1. As another example, if the variance shift noise intervention is
considered, then we specify $g$ as $(a,\varepsilon)\mapsto a\odot\varepsilon$,
where $\odot$ is the element-wise product. We focus our theoretical results on
the mean shift noise intervention. Other types of noise interventions are
discussed in numerical experiments. The linear SCM with noise interventions
clearly does not cover all kinds of perturbations to the data. For example,
our theory does not apply when the matrix $\mathbf{B}$ is no longer invariant
across source and target environments. We show via numerical experiments that
assuming that the perturbations are due to noise interventions is plausible in
many settings.

###  3.3 Oracle and baseline DA methods

As we aim to compare existing and new DA methods rigorously under our
theoretical framework, it is useful to start with several estimators to
establish the basis of comparison.

First, we introduce two oracle estimators. They are defined using the
unobserved information such as target labels or SCM parameters.

  * •

OLSTar: the population ordinary least squares (OLS) estimator on the target
data.

$\displaystyle f_{\text{OLSTar}}(x)$
$\displaystyle:=x^{\top}\beta_{\text{OLSTar}}+\beta_{\text{OLSTar},0}$
$\displaystyle\beta_{\text{OLSTar}},\beta_{\text{OLSTar},0}$
$\displaystyle:=\operatorname*{arg\,min}_{\beta,\beta_{0}}{\mathbb{E}}_{(X,Y)\sim\widetilde{\mathcal{P}}}\left(Y-X^{\top}\beta-\beta_{0}\right)^{2}.$
(5)

This is the oracle target population estimator when we restrict the function
class to be linear. Hence the target risk of OLSTar defines the lowest target
risk that any linear DA estimator can achieve.

  * •

Causal: the population causal estimator via the linear SCM

$\displaystyle f_{\text{Causal}}(x)$
$\displaystyle:=x^{\top}\beta_{\text{Causal}}$
$\displaystyle\beta_{\text{Causal}}$ $\displaystyle:={\omega},$ (6)

where ${\omega}$ appeared in the last row of the SCM matrix in Equation (3).
Note that this formulation of the causal estimator assumes that there is no
intervention on $Y$ and the intercept is also zero. The Causal estimator is
closely related to distributional robust estimators. That is, the Causal
estimator is the robust estimator which achieves the minimum worse-case risk
when the perturbations on the covariates are allowed to be arbitrary
(Bühlmann, 2020). However, in our DA setting where observed target covariates
provide additional information, it is no longer clear whether Causal still
achieves the lowest target risk.

Second, we introduce two population estimators that only use the source data.

  * •

OLSSrc${}^{\text{\scriptsize$(m)$}}$: the population OLS estimator on the
single $m$-th source environment.

$\displaystyle f_{\text{OLSSrc}}^{\text{\scriptsize$(m)$}}(x)$
$\displaystyle:=x^{\top}\beta_{\text{OLSSrc}}^{\text{\scriptsize$(m)$}}+\beta_{\text{OLSSrc},0}^{\text{\scriptsize$(m)$}}$
$\displaystyle\beta_{\text{OLSSrc}}^{\text{\scriptsize$(m)$}},\beta_{\text{OLSSrc},0}^{\text{\scriptsize$(m)$}}$
$\displaystyle:=\operatorname*{arg\,min}_{\beta,\beta_{0}}{\mathbb{E}}_{(X,Y)\sim\mathcal{P}^{\text{\scriptsize$(m)$}}}\left(Y-X^{\top}\beta-\beta_{0}\right)^{2}.$
(7)

  * •

SrcPool: the population OLS estimator by pooling all source data together.

$\displaystyle f_{\text{SrcPool}}(x)$
$\displaystyle:=x^{\top}\beta_{\text{SrcPool}}+\beta_{\text{SrcPool},0}$
$\displaystyle\beta_{\text{SrcPool}},\beta_{\text{SrcPool},0}$
$\displaystyle:=\operatorname*{arg\,min}_{\beta,\beta_{0}}{\mathbb{E}}_{(X,Y)\sim\mathcal{P}^{\text{allsrc}}}\left(Y-X^{\top}\beta-\beta_{0}\right)^{2},$
(8)

where $\mathcal{P}^{\text{allsrc}}$ is the uniform mixture over $M$ source
distributions
$\left\\{\mathcal{P}^{\text{\scriptsize$(m)$}}\right\\}_{m=\left\\{1,\cdots,M\right\\}}$.
We omitted the SrcPool formulation with weighted mixtures because it is not
the main focus of our study.

These two estimators are natural estimators in the classical statistical
learning setting when the source and target data share the same distribution.
A DA method that has larger target risk than SrcPool is clearly unfavorable.
One goal throughout our paper is to understand under which conditions DA
methods are guaranteed to outperform OLSSrc${}^{\text{\scriptsize$(m)$}}$ and
SrcPool.

###  3.4 Advanced DA methods

In this subsection, we introduce three advanced DA methods. The first two have
been introduced previously and the third one is our new DA method.

First, we consider the DA method called domain invariant projection (DIP). DIP
is a subspace-based DA method which aims at learning a common intermediate
subspace that relates the source and target domains. The specific form of DIP
we study follows from Baktashmotlagh et al. (2013). Specifically, the
population DIP estimator involves the following optimization problem

$\displaystyle f_{\text{DIP}}(x)$ $\displaystyle:=u_{\text{DIP}}\circ
v_{\text{DIP}}(x)$ $\displaystyle u_{\text{DIP}},v_{\text{DIP}}$
$\displaystyle:=\operatorname*{arg\,min}_{u\in\mathcal{U},v\in\mathcal{V}}{\mathbb{E}}_{(X,Y)\sim\mathcal{P}^{\text{\scriptsize$(1)$}},\tilde{X}\sim\widetilde{\mathcal{P}}}l{\left(u\circ
v(X),Y\right)+\lambda\cdot\mathcal{D}(v(X),v(\tilde{X}))},$ (9)

where $\mathcal{D}(\cdot,\cdot)$ measures the distance between two
distribution, $\mathcal{U}$ and $\mathcal{V}$ are function classes that are
specified through expert knowledge of the problem and $\lambda$ is a positive
regularization parameter. DIP, in its simple form, only uses a single source
environment. Hence, without loss of generality, we used the first source data
environment.

In Baktashmotlagh et al. (2013), maximum mean discrepancy (MMD) is used as the
distributional distance measure and both $\mathcal{U}$ and $\mathcal{V}$ are
set to be linear mappings. This DIP idea of matching the mappings of source
and target data is extended later in many DA papers with various choices of
distance and function classes (see e.g. Ghifary et al., 2016; Li et al.,
2018). A noteworthy line of follow-up work consist of replacing the
distribution distance and function classes in DIP with neural networks. For
example, Ganin et al. (2016) introduced domain-adversarial neural network
(DANN) which uses generative adversarial nets (GAN) in place of MMD to measure
distributional distance and makes both $\mathcal{U}$ and $\mathcal{V}$ to be
neural networks.

Analyzing the most generic form of DIP is out of the scope of this study.
Instead, we start with a simple DIP formulation.

  * •

DIP${}^{\text{\scriptsize$(m)$}}$-mean: the population DIP estimator where
mean squared difference is used as distributional distance, $\mathcal{V}$ is
linear and $\mathcal{U}$ is the singleton of the identity mapping and
$\lambda$ is chosen to be $\infty$. DIP, in its simple form, only uses the
data from one source environment and the target covariates. This form of DIP
is defined as

$\displaystyle f_{\text{DIP}}^{\text{\scriptsize$(m)$}}(x)$
$\displaystyle:=x^{\top}\beta_{\text{DIP}}^{\text{\scriptsize$(m)$}}+\beta_{\text{DIP},0}^{\text{\scriptsize$(m)$}}$
$\displaystyle\beta_{\text{DIP}}^{\text{\scriptsize$(m)$}},\beta_{\text{DIP},0}^{\text{\scriptsize$(m)$}}$
$\displaystyle:=\operatorname*{arg\,min}_{\beta,\beta_{0}}\
{\mathbb{E}}_{(X,Y)\sim\mathcal{P}^{\text{\scriptsize$(m)$}}}\left(Y-X^{\top}\beta-\beta_{0}\right)^{2}$
$\displaystyle\text{s.t.\
}{\mathbb{E}}_{X\sim\mathcal{P}^{\text{\scriptsize$(m)$}}_{X}}\left[X^{\top}\beta\right]={\mathbb{E}}_{X\sim\widetilde{\mathcal{P}}_{X}}\left[X^{\top}\beta\right].$
(10)

For simplicity, we use the shorthand notation
DIP${}^{\text{\scriptsize$(m)$}}$ to refer to
DIP${}^{\text{\scriptsize$(m)$}}$-mean. The constraint in Equation (• ‣ 3.4)
is called the DIP matching penalty.

Second, we introduce the conditional invariant penalty (CIP) estimator. Unlike
DIP which projects the source and target covariates to the same subspace, CIP
directly uses the label information in multiple source environments to look
for the conditionally invariant components. CIP only makes use of source data.

  * •

CIP-mean: the population conditional invariance penalty (CIP) estimator where
the conditional mean is matched across multiple source environments.

$\displaystyle f_{\text{CIP}}(x)$
$\displaystyle:=x^{\top}\beta_{\text{CIP}}+\beta_{\text{CIP},0}$
$\displaystyle\beta_{\text{CIP}},\beta_{\text{CIP},0}$
$\displaystyle:=\operatorname*{arg\,min}_{\beta,\beta_{0}}\
\frac{1}{M}\sum_{m=1}^{M}{\mathbb{E}}_{(X,Y)\sim\mathcal{P}^{\text{\scriptsize$(m)$}}}\left(Y-X^{\top}\beta-\beta_{0}\right)^{2}$
$\displaystyle\text{s.t.\
}{\mathbb{E}}_{(X,Y)\sim\mathcal{P}^{\text{\scriptsize$(m)$}}}$
$\displaystyle\left[X^{\top}\beta\mid
Y\right]={\mathbb{E}}_{(X,Y)\sim\mathcal{P}^{\text{\scriptsize$(1)$}}}\left[X^{\top}\beta\mid
Y\right]a.s.,\forall m\in\left\\{2,\cdots,M\right\\},$ (11)

where the equality between the conditional expectation is in the sense of
almost sure equality of random variables. Note that CIP naturally requires
$M\geq 2$, because when $M=1$ the CIP constraint becomes vacuous. For
simplicity, we use the shorthand notation CIP to refer to CIP-mean.

CIP puts more regression weights on the conditionally invariant components
from multiple source datasets via the conditional invariance constraint in
Equation (• ‣ 3.4). The idea of conditional invariance penalty in the context
of anticausal learning has appeared in multiple papers with slightly different
settings. Gong et al. (2016) introduced conditional transferable components
which are in fact conditionally invariant features. However, unlike the
formulation above, Gong et al. (2016) propose to learn the conditional
transferable components with only one source environment which requires
assumptions that are difficult to check. On the other hand, the algorithm from
Heinze-Deml and Meinshausen (2021) learns the conditionally invariant features
from a single source dataset if multiple observations of data points that
share the same identifier are present. They use their conditional variance
penalty to enforce their algorithm to learn the conditionally invariant
features in their specific datasets with identifiers. The same idea can be
applied if we replace identifiers with source environments.

Third, we introduce our new DA estimator conditional invariant residual
matching (CIRM).

  * •

CIRM${}^{\text{\scriptsize$(m)$}}$-mean: the population conditional invariant
residual matching estimator that uses all source environments to compute CIP
and the $m$-th source environment to perform risk minimization.

$\displaystyle f_{\text{CIRM}}^{\text{\scriptsize$(m)$}}(x)$
$\displaystyle:=x^{\top}{\beta_{\text{CIRM}}^{\text{\scriptsize$(m)$}}}+\beta_{\text{CIRM},0}^{\text{\scriptsize$(m)$}}$
$\displaystyle{\beta_{\text{CIRM}}^{\text{\scriptsize$(m)$}}},\beta_{\text{CIRM},0}^{\text{\scriptsize$(m)$}}$
$\displaystyle:=\operatorname*{arg\,min}_{\beta,\beta_{0}}\
{\mathbb{E}}_{(X,Y)\sim\mathcal{P}^{\text{\scriptsize$(m)$}}}\left(Y-X^{\top}\beta-\beta_{0}\right)^{2}$
$\displaystyle\text{s.t.\
}{\mathbb{E}}_{X\sim\mathcal{P}^{\text{\scriptsize$(m)$}}_{X}}$
$\displaystyle\left[\beta^{\top}\left(X-\left(X^{\top}\beta_{\text{CIP}}\right)\vartheta_{\text{CIRM}}\right)\right]={\mathbb{E}}_{X\sim\widetilde{\mathcal{P}}_{X}}\left[\beta^{\top}\left(X-\left(X^{\top}\beta_{\text{CIP}}\right)\vartheta_{\text{CIRM}}\right)\right],$
(12)

where

$\displaystyle\vartheta_{\text{CIRM}}:=\frac{{\mathbb{E}}_{(X,Y)\sim\mathcal{P}^{\text{allsrc}}}\left[X\cdot(Y-{\mathbb{E}}[Y])\right]}{{\mathbb{E}}_{(X,Y)\sim\mathcal{P}^{\text{allsrc}}}\left[\left(X^{\top}\beta_{\text{CIP}}-{\mathbb{E}}[X^{\top}\beta_{\text{CIP}}]\right)\cdot\left(Y-{\mathbb{E}}[Y]\right)\right]},$
(13)

with $\mathcal{P}^{\text{allsrc}}$ denoting the uniform mixture of all source
distributions. For simplicity, we use the shorthand notation
CIRM${}^{\text{\scriptsize$(m)$}}$ to refer to
CIRM${}^{\text{\scriptsize$(m)$}}$-mean.

At first glance, the CIRM estimator is a combination of DIP and CIP. CIRM
first uses CIP to compute a linear combination of conditionally invariant
components to serve as a proxy of the label $Y$. To tackle the label
distribution perturbation, CIRM then performs the DIP-type matching on the
residual obtained by regressing $Y$ on its proxy. We can show that the joint
distribution of the residual together with the covariates do not suffer from
the label distribution perturbation. CIRM is designed to be applied in DA
scenarios with label distribution perturbation. Note that the idea of using
domain-invariant features to tackle label distribution shift was proposed
previously in Li et al. (2019) and in Tachet des Combes et al. (2020), while
it was not clear how to formulate the exact algorithm so that its success and
failure conditions can be analyzed. The intuition behind the CIRM construction
becomes clearer after we state Theorem 5.

The comparison of DA methods in the following sections is centered around DIP,
CIP, CIRM and their variants. To keep track of these variants, we provide a
summary of all DA methods appeared in this paper in Table 5 of Appendix A.1.

###  3.5 Simple motivating examples

Before we dive into theoretical comparisons of the DA methods, we go through
three simple examples to illustrate the assumptions needed for DA methods to
have low target risks. The simple examples have data generated via low-
dimensional SCMs so that the DA estimators can be easily computed and
understood.

####  3.5.1 Example 1: causal prediction

Example 1 has one source environment and one target environment. The data in
the source and target environment are generated independently according to the
following SCMs, with the causal diagram on the left and the structural
equations on the right of Figure 2.

$X_{1}$$X_{2}$$X_{3}$$A$$Y$

$\begin{aligned}
X^{\text{\scriptsize$(1)$}}_{1}&=\varepsilon^{\text{\scriptsize$(1)$}}_{X_{1}}+1\\\
X^{\text{\scriptsize$(1)$}}_{2}&=\varepsilon^{\text{\scriptsize$(1)$}}_{X_{2}}+1\\\
X^{\text{\scriptsize$(1)$}}_{3}&=\varepsilon^{\text{\scriptsize$(1)$}}_{X_{3}}+1\\\
Y^{\text{\scriptsize$(1)$}}&=X^{\text{\scriptsize$(1)$}}_{1}+X^{\text{\scriptsize$(1)$}}_{2}+\varepsilon^{\text{\scriptsize$(1)$}}_{Y},\end{aligned}\hskip
28.45274pt\begin{aligned}
\widetilde{X}_{1}&=\widetilde{\varepsilon}_{X_{1}}-1\\\
\widetilde{X}_{2}&=\widetilde{\varepsilon}_{X_{2}}-1\\\
\widetilde{X}_{3}&=\widetilde{\varepsilon}_{X_{3}}+1\\\
\widetilde{Y}&=\widetilde{X}_{1}+\widetilde{X}_{2}+\widetilde{\varepsilon}_{Y},\end{aligned}$

Figure 2: The causal diagram and structural equations for the source and
target environments in Example 1: causal prediction.

Here the noise variables follow independent Gaussian distributions with mean
zero and variance $0.1$ for $X$ and variance $0.2$ for $Y$, namely,
$\varepsilon^{\text{\scriptsize$(1)$}}_{X_{1}},\varepsilon^{\text{\scriptsize$(1)$}}_{X_{2}},\varepsilon^{\text{\scriptsize$(1)$}}_{X_{3}},\widetilde{\varepsilon}_{X_{1}},\widetilde{\varepsilon}_{X_{2}},\widetilde{\varepsilon}_{X_{3}}\sim\mathcal{N}(0,0.1)$,
$\varepsilon^{\text{\scriptsize$(1)$}}_{Y},\widetilde{\varepsilon}_{Y}\sim\mathcal{N}(0,0.2)$.
The type of intervention is mean shift noise intervention. That is, the
function $g$ in Equation (3) is taken to be
$g:(a^{\text{\scriptsize$(1)$}},\varepsilon^{\text{\scriptsize$(1)$}})\mapsto
a^{\text{\scriptsize$(1)$}}+\varepsilon^{\text{\scriptsize$(1)$}}$. The
intervention is
$a^{\text{\scriptsize$(1)$}}=\begin{bmatrix}1&1&1&0\end{bmatrix}^{\top}$ for
the source environment and it is
$\widetilde{a}=\begin{bmatrix}-1&-1&1&0\end{bmatrix}^{\top}$ for the target
environment. This example is called causal prediction, because the covariates
$X$ are parents of the label $Y$. In other words, we are predicting the effect
from the causes as illustrated in the causal diagram in Figure 2.

Given the source and target distribution, the population DA estimators in the
previous subsection can be computed explicitly. We obtain

$\displaystyle\begin{bmatrix}\beta_{\text{OLSTar}}\\\
\beta_{\text{OLSTar},0}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}1&1&0&0\end{bmatrix}^{\top},$
$\displaystyle\begin{bmatrix}\beta_{\text{Causal}}\\\
\beta_{\text{Causal},0}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}1&1&0&0\end{bmatrix}^{\top},$
$\displaystyle\begin{bmatrix}\beta_{\text{OLSSrc}}^{\text{\scriptsize$(1)$}}\\\
\beta_{\text{OLSSrc},0}^{\text{\scriptsize$(1)$}}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}1&1&0&0\end{bmatrix}^{\top},$
$\displaystyle\begin{bmatrix}\beta_{\text{DIP}}^{\text{\scriptsize$(1)$}}\\\
\beta_{\text{DIP},0}^{\text{\scriptsize$(1)$}}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\frac{1}{3}&\frac{1}{3}&-\frac{2}{3}&-2\end{bmatrix}^{\top}.$

Note that OLSSrc${}^{\text{\scriptsize$(1)$}}$, Causal and OLSTar share the
same estimate $\beta$, while DIP${}^{\text{\scriptsize$(1)$}}$ does not. The
corresponding population source and target risks are summarized in the first
two rows of Table 1. DIP${}^{\text{\scriptsize$(1)$}}$ has a larger target
population risk than OLSSrc${}^{\text{\scriptsize$(1)$}}$. In this example of
causal prediction, using the additional target covariate information via DIP
is making the target prediction performance worse. This is because DIP
matching penalty in Equation (• ‣ 3.4) which is not satisfied by the oracle
estimator OLSTar, makes DIP too restrictive.

Risk Methods |  OLSTar (oracle) |  Causal |  OLSSrc${}^{\text{\scriptsize$(1)$}}$ |  DIP${}^{\text{\scriptsize$(1)$}}$ |  DIPAbs${}^{\text{\scriptsize$(1)$}}$
---|---|---|---|---|---
Ex 1, source risk $R^{\text{\scriptsize$(1)$}}$ | 0.200 | 0.200 | 0.200 | 0.333 | -
Ex 1, target risk $\tilde{R}$ | 0.200 | 0.200 | 0.200 | 16.333 | -
Ex 2, source risk $R^{\text{\scriptsize$(1)$}}$ | 2.600 | 0.200 | 0.040 | 0.086 | 0.044
Ex 2, target risk $\tilde{R}$ | 0.040 | 0.200 | 2.600 | 0.086 | 0.667
Ex 3, source risk $R^{\text{\scriptsize$(1)$}}$ | 0.200 | 0.200 | 0.040 | 0.066 | -
Ex 3, target risk $\tilde{R}$ | 0.040 | 1.200 | 0.200 | 4.066 | -
Table 1: Population source and target risks in two motivating examples (the
lower the better). The oracle target risk is highlighted in bold. In Example 1
of causal prediction, DIP${}^{\text{\scriptsize$(1)$}}$ performs worse than
Causal and OLSSrc${}^{\text{\scriptsize$(1)$}}$ in terms of target population
risk. In Example 2 of anticausal prediction, DIP${}^{\text{\scriptsize$(1)$}}$
performs better than Causal and OLSSrc${}^{\text{\scriptsize$(1)$}}$, but it
is still not as good as the oracle estimator.
DIPAbs${}^{\text{\scriptsize$(1)$}}$ is better in terms of population source
risk can have worse target population risk than Causal. In Example 3 of
anticausal prediction with intervention on $Y$,
DIP${}^{\text{\scriptsize$(1)$}}$ performs worse than
OLSSrc${}^{\text{\scriptsize$(1)$}}$ in terms of target population risk.

####  3.5.2 Example 2: anticausal prediction

Example 2 has one source environment and one target environment. The data in
the source and target environment are generated independently according to the
following SCMs, with the causal diagram on the left and the structural
equations on the right of Figure 3.

$X_{1}$$X_{2}$$X_{3}$$A$$Y$

$\begin{aligned}
X^{\text{\scriptsize$(1)$}}_{1}&=Y^{\text{\scriptsize$(1)$}}+\varepsilon^{\text{\scriptsize$(1)$}}_{X_{1}}+1\\\
X^{\text{\scriptsize$(1)$}}_{2}&=Y^{\text{\scriptsize$(1)$}}+\varepsilon^{\text{\scriptsize$(1)$}}_{X_{2}}+1\\\
X^{\text{\scriptsize$(1)$}}_{3}&=\varepsilon^{\text{\scriptsize$(1)$}}_{X_{3}}+1\\\
Y^{\text{\scriptsize$(1)$}}&=\varepsilon^{\text{\scriptsize$(1)$}}_{Y},\end{aligned}\hskip
56.9055pt\begin{aligned}
\widetilde{X}_{1}&=\widetilde{Y}+\widetilde{\varepsilon}_{X_{1}}-1\\\
\widetilde{X}_{2}&=\widetilde{Y}+\widetilde{\varepsilon}_{X_{2}}-1\\\
\widetilde{X}_{3}&=\widetilde{\varepsilon}_{X_{3}}-1\\\
\widetilde{Y}&=\widetilde{\varepsilon}_{Y},\end{aligned}$

Figure 3: The causal diagram and structural equations for the source and
target environments in Example 2: anticausal prediction

Here the noise variables follow independent Gaussian distributions with mean
zero and variance $0.1$ for $X$ and variance $0.2$ for $Y$, namely,
$\varepsilon^{\text{\scriptsize$(1)$}}_{X_{1}},\widetilde{\varepsilon}_{X_{1}},\varepsilon^{\text{\scriptsize$(1)$}}_{X_{2}},\widetilde{\varepsilon}_{X_{2}},\varepsilon^{\text{\scriptsize$(1)$}}_{X_{3}},\widetilde{\varepsilon}_{X_{3}}\sim\mathcal{N}(0,0.1)$,
$\varepsilon^{\text{\scriptsize$(1)$}}_{Y},\widetilde{\varepsilon}_{Y}\sim\mathcal{N}(0,0.2).$
The type of intervention $g$ is mean shift noise intervention, which is the
same as in Example 1. The intervention is
$a^{\text{\scriptsize$(1)$}}=\begin{bmatrix}1&1&1&0\end{bmatrix}^{\top}$ for
the source environment and it is
$\widetilde{a}=\begin{bmatrix}-1&-1&-1&0\end{bmatrix}^{\top}$ for the target
environment. Compared to Example 1, the main difference is that the causal
direction between the covariates $X$ and the label $Y$ has changed. This
example is called anticausal prediction, because the covariates $X$ are
descendants of the label $Y$. We are predicting the cause from the effects as
illustrated in the causal diagram in Figure 3.

In addition to the DA estimators used in the previous example, we introduce
one more variant of DIP, DIPAbs. It is a made-up estimator to show that
arbitrary choice of the function classes $\mathcal{U},\mathcal{V}$ in DIP
formulation (3.4) without consideration on the data generation process is in
general a bad idea.

  * •

DIPAbs${}^{\text{\scriptsize$(m)$}}$-mean: the population DIP estimator where
mean squared difference is used as distributional distance, $\mathcal{V}$ is
element-wise absolute value followed linear mapping and $\mathcal{U}$ is
singleton of identity mapping and regularization parameter $\lambda$ is chosen
to be $\infty$. For the $m$-th source environment, it is defined as

$\displaystyle f_{\text{DIPAbs}}^{\text{\scriptsize$(m)$}}(x)$
$\displaystyle:=\left|x\right|^{\top}\beta_{\text{DIPAbs}}^{\text{\scriptsize$(m)$}}+\beta_{\text{DIPAbs},0}^{\text{\scriptsize$(m)$}}$
$\displaystyle\beta_{\text{DIPAbs}}^{\text{\scriptsize$(m)$}},\beta_{\text{DIPAbs},0}^{\text{\scriptsize$(m)$}}$
$\displaystyle:=\operatorname*{arg\,min}_{\beta,\beta_{0}}\
{\mathbb{E}}_{(X,Y)\sim\mathcal{P}^{\text{\scriptsize$(m)$}}}\left(Y-\left|X\right|^{\top}\beta-\beta_{0}\right)^{2}$
$\displaystyle\text{s.t.\
}{\mathbb{E}}_{X\sim\mathcal{P}^{\text{\scriptsize$(m)$}}_{X}}\left[\left|X\right|^{\top}\beta\right]={\mathbb{E}}_{X\sim\widetilde{\mathcal{P}}_{X}}\left[\left|X\right|^{\top}\beta\right].$
(14)

The population estimators can be computed explicitly

$\displaystyle\begin{bmatrix}\beta_{\text{OLSTar}}\\\
\beta_{\text{OLSTar},0}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\frac{2}{5}&\frac{2}{5}&0&\frac{4}{5}\end{bmatrix}^{\top},$
$\displaystyle\begin{bmatrix}\beta_{\text{Causal}}\\\
\beta_{\text{Causal},0}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}0&0&0&0\end{bmatrix}^{\top},$
$\displaystyle\begin{bmatrix}\beta_{\text{OLSSrc}}^{\text{\scriptsize$(1)$}}\\\
\beta_{\text{OLSSrc},0}^{\text{\scriptsize$(1)$}}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\frac{2}{5}&\frac{2}{5}&0&-\frac{4}{5}\end{bmatrix}^{\top},$
$\displaystyle\begin{bmatrix}\beta_{\text{DIP}}^{\text{\scriptsize$(1)$}}\\\
\beta_{\text{DIP},0}^{\text{\scriptsize$(1)$}}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\frac{2}{7}&\frac{2}{7}&-\frac{4}{7}&0\end{bmatrix}^{\top},$
$\displaystyle\begin{bmatrix}\beta_{\text{DIPAbs}}^{\text{\scriptsize$(1)$}}\\\
\beta_{\text{DIPAbs},0}^{\text{\scriptsize$(1)$}}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}-\frac{2}{5}&-\frac{2}{5}&0&\frac{4}{5}\end{bmatrix}^{\top}.$

For the other four estimators, none of the estimated $\beta$ perfectly agrees
with that of the oracle OLSTar. The corresponding population source and target
risks are summarized in the third and fourth rows of Table 1.
DIP${}^{\text{\scriptsize$(1)$}}$ improves upon Causal and
OLSSrc${}^{\text{\scriptsize$(1)$}}$ on the target population risk. However
its target population risk is not as small as that of the oracle estimator
OLSTar. DIPAbs${}^{\text{\scriptsize$(1)$}}$ also uses the target covariate
information as DIP${}^{\text{\scriptsize$(1)$}}$ does, but
DIPAbs${}^{\text{\scriptsize$(1)$}}$ performs worse than Causal or
DIP${}^{\text{\scriptsize$(1)$}}$ in terms of target population risk.

####  3.5.3 Example 3: anticausal prediction when Y is intervened on

Example 3 is also an anticausal prediction problem similar to Example 2,
except that the label $Y$ is also intervened on. The data in the source and
target environment are generated independently according to the following
SCMs, with the causal diagram on the left and the structural equations on the
right of Figure 4.

$X_{1}$$X_{2}$$A$$Y$

$\begin{aligned}
X^{\text{\scriptsize$(1)$}}_{1}&=Y^{\text{\scriptsize$(1)$}}+\varepsilon^{\text{\scriptsize$(1)$}}_{X_{1}}+1\\\
X^{\text{\scriptsize$(1)$}}_{2}&=-Y^{\text{\scriptsize$(1)$}}+\varepsilon^{\text{\scriptsize$(1)$}}_{X_{2}}+1\\\
Y^{\text{\scriptsize$(1)$}}&=\varepsilon^{\text{\scriptsize$(1)$}}_{Y}+1,\end{aligned}\hskip
56.9055pt\begin{aligned}
\widetilde{X}_{1}&=\widetilde{Y}+\widetilde{\varepsilon}_{X_{1}}-1\\\
\widetilde{X}_{2}&=-\widetilde{Y}+\widetilde{\varepsilon}_{X_{2}}-1\\\
\widetilde{Y}&=\widetilde{\varepsilon}_{Y}-1,\end{aligned}$

Figure 4: The causal diagram and structural equations for the source and
target environments in Example 3: anticausal prediction when Y is intervened
on

Here the noise variables follow independent Gaussian distributions with
$\varepsilon_{X_{1}},\widetilde{\varepsilon}_{X_{1}}\sim\mathcal{N}(0,0.1)$,
$\varepsilon_{X_{2}},\widetilde{\varepsilon}_{X_{2}}\sim\mathcal{N}(0,0.1)$,
$\varepsilon_{Y},\widetilde{\varepsilon}_{Y}\sim\mathcal{N}(0,0.2)$. The type
of intervention is still mean shift noise intervention. The intervention is
$a^{\text{\scriptsize$(1)$}}=\begin{bmatrix}1&1&1\end{bmatrix}^{\top}$ for the
source environment and it is
$\widetilde{a}=\begin{bmatrix}-1&-1&-1\end{bmatrix}^{\top}$ for the target
environment. Compared to Example 2, the main difference is that the
intervention on $Y$ is nonzero as illustrated in the causal diagram in Figure
4.

The population estimators can be computed explicitly

$\displaystyle\begin{bmatrix}\beta_{\text{OLSTar}}\\\
\beta_{\text{OLSTar},0}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\frac{2}{5}&-\frac{2}{5}&-\frac{1}{5}\end{bmatrix}^{\top},$
$\displaystyle\begin{bmatrix}\beta_{\text{Causal}}\\\
\beta_{\text{Causal},0}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}0&0&0\end{bmatrix}^{\top},$
$\displaystyle\begin{bmatrix}\beta_{\text{OLSSrc}}^{\text{\scriptsize$(1)$}}\\\
\beta_{\text{OLSSrc},0}^{\text{\scriptsize$(1)$}}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\frac{2}{5}&-\frac{2}{5}&\frac{1}{5}\end{bmatrix}^{\top},$
$\displaystyle\begin{bmatrix}\beta_{\text{DIP}}^{\text{\scriptsize$(1)$}}\\\
\beta_{\text{DIP},0}^{\text{\scriptsize$(1)$}}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}0&-\frac{2}{3}&1\end{bmatrix}^{\top}.$

Note that DIP${}^{\text{\scriptsize$(1)$}}$ has zero weight on the first
coordinate but non-zero weight on the second because
$X^{\text{\scriptsize$(1)$}}_{2}$ and $\widetilde{X}_{2}$ share the same
distribution. The corresponding population source and target risks are
summarized in the last two rows of Table 1. In Example 3 when $Y$ is
intervened on, DIP${}^{\text{\scriptsize$(1)$}}$ is again worse than
OLSSrc${}^{\text{\scriptsize$(1)$}}$ on the target population risk.

####  3.5.4 Lessons from the simple motivating examples

The three simple motivating examples reveal three observations. First, even
though DIP has a low target risk in the anticausal prediction setting (Example
2), DIP is not likely to outperform OLSSrc in the causal prediction setting
(Example 1). The fact that the additional target covariate information is not
useful in causal prediction problem was previously pointed out by Schölkopf et
al. (2012). Consequently, DIP-type methods (Baktashmotlagh et al., 2013; Ganin
et al., 2016) which make use of the additional target covariate information
can make target performance worse in causal prediction problems. Second, not
all DIP variants have low target risks in the anticausal prediction setting.
DIPAbs${}^{\text{\scriptsize$(1)$}}$, despite using the target covariate
information as DIP${}^{\text{\scriptsize$(1)$}}$ does, performs worse than
Causal and DIP${}^{\text{\scriptsize$(1)$}}$. In general, it is dangerous to
treat DA methods as generic solutions that always work without consideration
on the data generation process. We remark that
DIPAbs${}^{\text{\scriptsize$(1)$}}$ is a made-up method. But one could
imagine a case where the first part $\mathcal{V}$ in
DIP${}^{\text{\scriptsize$(1)$}}$ is set to be a neural network that can
approximate a large class of functions, then it is no longer clear the DIP
matching penalty that matches the source and target covariate distributions
always helps to improve the target population risk. This danger of learning
blindly invariant representations was pointed out previously via a simple
nonlinear data generation model by Zhao et al. (2019). Third, when $Y$ is
intervened on, DIP can perform worse than OLSSrc. Actually, none of the DA
methods in Table 1 can handle the intervention on $Y$ well. The weakness of
DIP in the presence of label perturbation has been observed previously in Zhao
et al. (2019); Li et al. (2019); Tachet des Combes et al. (2020). Especially,
Tachet des Combes et al. (2020) proposed the idea of using conditional
invariant components for label shift correction. However, since their proposed
method has no guarantees for estimating the conditional invariant components,
it is not clear whether their methods have any guarantees for correcting the
label shift.

The three examples are designed to demonstrate that the popular DA method DIP
does not always outperform baseline methods such as OLSSrc or Causal. Besides,
it also shows that the assumption of both source and data being generated from
linear SCMs is not sufficient to guarantee DIP to have a low target risk.
Additional assumptions on the data generation or on the intervention are
needed. For example, knowing the causal direction of the data generation model
or whether the label distribution is perturbed are all crucial information.
Based on these examples, we ask the following questions:

  1. 1.

In addition to the linear SCM assumption, what other assumptions are needed
for DIP to perform better than Causal or OLSSrc? If such assumptions exist,
can one quantify the gap between the target risk achieved by DIP and the
oracle target risk?

  2. 2.

If there is label distribution perturbation like in Example 3, are there DA
methods that can outperform OLSSrc and have target risk guarantees?

  3. 3.

If the prediction direction is a mix of causal and anticausal, is domain
adaptation still beneficial?

In the sequel, we address these questions one by one. The first question is
addressed in Section 4.1. The second question is dealt with in Section 4.2 via
the introduction of CIP and CIRM. The general solution to the third question
remains open. Naive applications of DIP and CIRM are not optimal. We provide a
partial answer to the third question in Section 4.3 and show that the mixed-
causal anticausal DA problem can be reduced to the anticausal DA problem when
the causal variables have been already identified.

##  4 Domain adaptation with theoretical guarantees

In this section, to answer the three questions in the last section with rigor,
we establish target risk guarantees for the DA estimators DIP, CIP and CIRM in
three settings. Subsection 4.1 focuses on the DIP performance in the
anticausal DA setting without intervention on $Y$. Subsection 4.2 demonstrates
the difficulty of DIP in the anticausal DA setting with interventions on $Y$
and then proves the advantage of CIP and CIRM over DIP when multiple source
environments are available. Subsection 4.3 shows how domain adaptation is
still possible in the mixed causal anticausal DA setting.

###  4.1 Anticausal domain adaptation without intervention on Y

In this subsection, we study the anticausal domain adaptation with the
additional assumption that the intervention on the covariates $X$ is a mean
shift noise intervention and there is no intervention on the label $Y$. In the
anticausal domain adaptation, all the covariates $X$ are descendants of the
label $Y$ in the SCM. First, we derive the target risk bound for DIP under
these assumptions with a single source environment. Then we show how to make
use of more source environments to improve the performance of DIP. Finally, we
discuss ways to relax the mean shift noise intervention assumption.

####  4.1.1 Target risk guarantees of DIP with a single source environment

Before we state the main theorem, we introduce another oracle estimator to
simplify the theorem statement. DIPOracle minimizes the mean squared error on
target data while it uses the same matching penalty as DIP.

  * •

DIPOracle${}^{\text{\scriptsize$(m)$}}$-mean: the population DIP estimator
which uses target labels and the covariate distribution from the $m$-th source
and target environment.

$\displaystyle f_{\text{DIPOracle}}^{\text{\scriptsize$(m)$}}(x)$
$\displaystyle:=x^{\top}\beta_{\text{DIPOracle}}^{\text{\scriptsize$(m)$}}+\beta_{\text{DIPOracle},0}^{\text{\scriptsize$(m)$}}$
$\displaystyle\beta_{\text{DIPOracle}}^{\text{\scriptsize$(m)$}},\beta_{\text{DIPOracle},0}^{\text{\scriptsize$(m)$}}$
$\displaystyle:=\operatorname*{arg\,min}_{\beta,\beta_{0}}\
{\mathbb{E}}_{(X,Y)\sim\widetilde{\mathcal{P}}}\left(Y-X^{\top}\beta-\beta_{0}\right)^{2}$
$\displaystyle\text{s.t.\
}{\mathbb{E}}_{X\sim\mathcal{P}^{\text{\scriptsize$(m)$}}_{X}}\left[X^{\top}\beta\right]={\mathbb{E}}_{X\sim\widetilde{\mathcal{P}}_{X}}\left[X^{\top}\beta\right].$
(15)

Next, we state the data generating assumptions needed for DIP to have target
risk guarantees. Since a single source environment is considered in this
subsection, without loss of generality, we assume that the first source
environment is used.

###### Assumption 1

Each data point in the source environment is generated i.i.d. according to
distribution $\mathcal{P}^{\text{\scriptsize$(1)$}}$ specified by the
following SCM

$\displaystyle\begin{bmatrix}X^{\text{\scriptsize$(1)$}}\\\
Y^{\text{\scriptsize$(1)$}}\end{bmatrix}=\begin{bmatrix}\mathbf{B}&{b}\\\
{\omega}^{\top}&0\end{bmatrix}\begin{bmatrix}X^{\text{\scriptsize$(1)$}}\\\
Y^{\text{\scriptsize$(1)$}}\end{bmatrix}+\begin{bmatrix}a^{\text{\scriptsize$(1)$}}_{X}\\\
a^{\text{\scriptsize$(1)$}}_{Y}\end{bmatrix}+\begin{bmatrix}\varepsilon^{\text{\scriptsize$(1)$}}_{X}\\\
\varepsilon^{\text{\scriptsize$(1)$}}_{Y}\end{bmatrix},$

each data point in the target environment is generated i.i.d. according to
distribution $\widetilde{\mathcal{P}}$ specified with the same SCM except for
the mean shift intervention term

$\displaystyle\begin{bmatrix}\widetilde{X}\\\
\widetilde{Y}\end{bmatrix}=\begin{bmatrix}\mathbf{B}&{b}\\\
{\omega}^{\top}&0\end{bmatrix}\begin{bmatrix}\widetilde{X}\\\
\widetilde{Y}\end{bmatrix}+\begin{bmatrix}\widetilde{a}_{X}\\\
\widetilde{a}_{Y}\end{bmatrix}+\begin{bmatrix}\widetilde{\varepsilon}_{X}\\\
\widetilde{\varepsilon}_{Y}\end{bmatrix},$

where $\mathbb{I}_{d}-\mathbf{B}\in^{d\times d}$ is invertible, the prediction
problem is anticausal i.e. ${\omega}=0$, ${b}\in^{d}$, the intervention terms
$\begin{bmatrix}a^{\text{\scriptsize$(1)$}}_{X}\\\
a^{\text{\scriptsize$(1)$}}_{Y}\end{bmatrix}$ and
$\begin{bmatrix}\widetilde{a}_{X}\\\ \widetilde{a}_{Y}\end{bmatrix}$ are
vectors in d+1, the noise terms
$\begin{bmatrix}\varepsilon^{\text{\scriptsize$(1)$}}_{X}\\\
\varepsilon^{\text{\scriptsize$(1)$}}_{Y}\end{bmatrix}$ and
$\begin{bmatrix}\widetilde{\varepsilon}_{X}\\\
\widetilde{\varepsilon}_{Y}\end{bmatrix}$ share the same distribution with

$\displaystyle{\mathbb{E}}\left[\varepsilon^{\text{\scriptsize$(1)$}}_{X}\right]={\mathbb{E}}\left[\widetilde{\varepsilon}_{X}\right]=0,\quad{\mathbb{E}}\left[\varepsilon^{\text{\scriptsize$(1)$}}_{X}{\varepsilon^{\text{\scriptsize$(1)$}}_{X}}^{\top}\right]={\mathbb{E}}\left[\widetilde{\varepsilon}_{X}{\widetilde{\varepsilon}_{X}}^{\top}\right]=\Sigma\in^{d\times
d},$
$\displaystyle{\mathbb{E}}\left[\varepsilon^{\text{\scriptsize$(1)$}}_{Y}\right]={\mathbb{E}}\left[\widetilde{\varepsilon}_{Y}\right]=0,\quad{\mathbb{E}}\left[{\varepsilon^{\text{\scriptsize$(1)$}}_{Y}}^{2}\right]={\mathbb{E}}\left[{\widetilde{\varepsilon}_{Y}}^{2}\right]=\sigma^{2}\in.$

Additionally, the noise terms on $X$ and $Y$ are uncorrelated
${\mathbb{E}}\left[\varepsilon^{\text{\scriptsize$(1)$}}_{Y}\cdot\varepsilon^{\text{\scriptsize$(1)$}}_{X}\right]={\mathbb{E}}\left[\widetilde{\varepsilon}_{Y}\cdot\widetilde{\varepsilon}_{X}\right]=0$.

Note that Assumption 1 does not require $\Sigma$ to be diagonal, meaning that
the noise terms of $X$ can be correlated. Consequently, this assumption allows
for unobserved confounders affecting the $X$ variables to exist. Under the
assumptions above and that there is no intervention on $Y$, we obtain the
following theorem on the target risk of DIP.

###### Theorem 1

Under the data generation Assumption 1 and the assumption of no intervention
on $Y$ i.e. $a^{\text{\scriptsize$(1)$}}_{Y}=\widetilde{a}_{Y}=0$, the target
population risks of OLSTar, OLSSrc${}^{\text{\scriptsize$(1)$}}$ and
DIP${}^{\text{\scriptsize$(1)$}}$-mean satisfy

$\displaystyle\tilde{R}\left(f_{\text{OLSTar}}\right)$
$\displaystyle=\frac{\sigma^{2}}{1+\sigma^{2}{b}^{\top}\Sigma^{-1}{b}},$ (16)
$\displaystyle\tilde{R}\left(f_{\text{OLSSrc}}^{\text{\scriptsize$(1)$}}\right)$
$\displaystyle=\frac{\sigma^{2}}{1+\sigma^{2}{b}^{\top}\Sigma^{-1}{b}}+\frac{\left(\sigma^{2}{b}^{\top}\Sigma^{-1}\left(a^{\text{\scriptsize$(1)$}}_{X}-\widetilde{a}_{X}\right)\right)^{2}}{\left(1+\sigma^{2}{b}^{\top}\Sigma^{-1}{b}\right)^{2}},$
(17)
$\displaystyle\tilde{R}\left(f_{\text{DIP}}^{\text{\scriptsize$(1)$}}\right)$
$\displaystyle=\tilde{R}\left(f_{\text{DIPOracle}}^{\text{\scriptsize$(1)$}}\right)=\frac{\sigma^{2}}{1+\sigma^{2}{b}^{\top}\Sigma^{-\frac{1}{2}}{G_{\text{\tiny
DIP}}^{\text{\scriptsize$(1)$}}}\Sigma^{-\frac{1}{2}}{b}},$ (18)

where ${G_{\text{\tiny
DIP}}^{\text{\scriptsize$(1)$}}}=\Sigma^{1/2}{Q_{\text{\tiny
DIP}}^{\text{\scriptsize$(1)$}}}\left({Q_{\text{\tiny
DIP}}^{\text{\scriptsize$(1)$}}}^{\top}\Sigma{Q_{\text{\tiny
DIP}}^{\text{\scriptsize$(1)$}}}\right)^{-1}{Q_{\text{\tiny
DIP}}^{\text{\scriptsize$(1)$}}}^{\top}\Sigma^{1/2}$ is a projection matrix
with rank $d-1$; ${Q_{\text{\tiny DIP}}^{\text{\scriptsize$(1)$}}}\in^{d\times
d-1}$ is a matrix with columns formed by the vectors that complete the vector
$u^{\text{\scriptsize$(1)$}}$ to an orthonormal basis. Here
$u^{\text{\scriptsize$(1)$}}=\frac{a^{\text{\scriptsize$(1)$}}_{X}-\widetilde{a}_{X}}{\left\|a^{\text{\scriptsize$(1)$}}_{X}-\widetilde{a}_{X}\right\|_{2}}$
when the source and target distribution is not identical i.e.
$a^{\text{\scriptsize$(1)$}}_{X}\neq\widetilde{a}_{X}$. When
$a^{\text{\scriptsize$(1)$}}_{X}=\widetilde{a}_{X}$, meaning that the source
distribution equals the target distribution, then
$u^{\text{\scriptsize$(1)$}}=0$ and we have
$\tilde{R}\left(f_{\text{DIP}}^{\text{\scriptsize$(1)$}}\right)=\tilde{R}\left(f_{\text{OLSSrc}}^{\text{\scriptsize$(1)$}}\right)=\tilde{R}\left(f_{\text{OLSTar}}\right)$.

The proof of Theorem 1 is provided in Appendix B.1. Comparing Equation (18)
with Equation (16), the target population risk of
DIP${}^{\text{\scriptsize$(1)$}}$ is larger than that of OLSTar but it is
lower than the target population risk of the Causal estimator (which equals to
$\sigma^{2}$). The target population risk of
OLSSrc${}^{\text{\scriptsize$(1)$}}$ depends on the magnitude of the
difference in intervention
$\left\|a^{\text{\scriptsize$(1)$}}_{X}-\widetilde{a}_{X}\right\|_{2}$, while
the target risk of DIP${}^{\text{\scriptsize$(1)$}}$ is independent of that
magnitude. Consequently when the difference in intervention becomes large,
DIP${}^{\text{\scriptsize$(1)$}}$ can outperform
OLSSrc${}^{\text{\scriptsize$(1)$}}$. Moreover, the first equality of Equation
(18) shows that DIP${}^{\text{\scriptsize$(1)$}}$ achieves the same target
population risk as DIPOracle${}^{\text{\scriptsize$(1)$}}$.
DIPOracle${}^{\text{\scriptsize$(1)$}}$ differs from OLSTar by only one linear
constraint. The connection between DIP${}^{\text{\scriptsize$(1)$}}$ and
DIPOracle${}^{\text{\scriptsize$(1)$}}$ intuitively explains why
DIP${}^{\text{\scriptsize$(1)$}}$ target risk should be close to that of
OLSTar.

In fact, with additional assumptions on how the interventions
$a^{\text{\scriptsize$(1)$}}_{X}$ and $a_{X}$ are positioned and
simplifications on the covariance matrix $\Sigma$, we obtain the following
corollary which clearly highlights the difference between the target
population risk of DIP and the oracle target population risk of OSLTar.

###### Corollary 2

In addition to the assumptions in Theorem 1, suppose
$\Sigma=\frac{\sigma^{2}}{\rho}\mathbb{I}_{d}$ with $\rho>0$, then

$\displaystyle\tilde{R}\left(f_{\text{OLSTar}}\right)$
$\displaystyle=\frac{\sigma^{2}}{1+\rho\left\|{b}\right\|_{2}^{2}},$ (19)
$\displaystyle\tilde{R}\left(f_{\text{OLSSrc}}^{\text{\scriptsize$(1)$}}\right)$
$\displaystyle=\frac{\sigma^{2}}{1+\rho\left\|{b}\right\|_{2}^{2}}+\frac{\left({u^{\text{\scriptsize$(1)$}}}^{\top}{b}\right)^{2}\left\|a^{\text{\scriptsize$(1)$}}_{X}-\widetilde{a}_{X}\right\|_{2}^{2}}{\left(1+\rho\left\|{b}\right\|_{2}^{2}\right)^{2}},$
(20)
$\displaystyle\tilde{R}\left(f_{\text{DIP}}^{\text{\scriptsize$(1)$}}\right)$
$\displaystyle=\frac{\sigma^{2}}{1+\rho\left\|{b}\right\|_{2}^{2}-\rho\left({u^{\text{\scriptsize$(1)$}}}^{\top}{b}\right)^{2}},$
(21)

where
$u^{\text{\scriptsize$(1)$}}=\frac{a^{\text{\scriptsize$(1)$}}_{X}-\widetilde{a}_{X}}{\left\|a^{\text{\scriptsize$(1)$}}_{X}-\widetilde{a}_{X}\right\|_{2}}$
if $a^{\text{\scriptsize$(1)$}}_{X}\neq\widetilde{a}_{X}$ and
$u^{\text{\scriptsize$(1)$}}=0$ otherwise.

Additionally, if $a^{\text{\scriptsize$(1)$}}_{X}-\widetilde{a}_{X}$ is
generated randomly from the Gaussian distribution
$\mathcal{N}(0,\tau\mathbb{I}_{d}^{2})$, then for a constant $t$ satisfying
$0<t\leq\frac{d}{2}$, with probability at least $1-\exp(-t/16)-2\exp(-t/4)$,
we have

$\displaystyle\tilde{R}\left(f_{\text{OLSSrc}}^{\text{\scriptsize$(1)$}}\right)$
$\displaystyle\leq\frac{\sigma^{2}}{1+\rho\left\|{b}\right\|_{2}^{2}}+\frac{\tau^{2}t\left\|{b}\right\|_{2}^{2}}{2\left(1+\rho\left\|{b}\right\|_{2}^{2}\right)^{2}},$
$\displaystyle\tilde{R}\left(f_{\text{DIP}}^{\text{\scriptsize$(1)$}}\right)$
$\displaystyle\leq\frac{\sigma^{2}}{1+\rho\left(1-\frac{t}{d}\right)\left\|{b}\right\|_{2}^{2}}.$
(22)

The proof of Corollary 2 is provided in Appendix B.2. Under the conditions of
Corollary 2, Equation (21) shows that the gap between the target population
risks of DIP${}^{\text{\scriptsize$(1)$}}$ and OLSTar is smaller when the
direction of the difference in intervention $u^{\text{\scriptsize$(1)$}}$
becomes less aligned with the vector ${b}$. When the intervention is generated
randomly from a Gaussian distribution, the bound (2) shows that the gap
between the target population risks of DIP${}^{\text{\scriptsize$(1)$}}$ and
OLSTar is small with high probability. The gap only comes from an order
$\frac{1}{d}$ term in the denominator of the target risk. So when the
dimension $d$ is large, this difference in target population risk between
DIP${}^{\text{\scriptsize$(1)$}}$ and OLSTar becomes negligible. As for
OLSSrc, it is now clear from Corollary 2 that the target risk of
OLSSrc${}^{\text{\scriptsize$(1)$}}$ depends on the magnitude of the
difference in intervention $\tau$. For brevity, we only provided the target
risk upper bound of OLSSrc${}^{\text{\scriptsize$(1)$}}$. The lower bound
should hold similarly up to constant factors because the risks are derived
with equality in Equation (20)-(21) and tight Gaussian concentration bounds
are used to obtain the upper bounds. As the magnitude of the difference in
intervention $\tau$ increases, OLSSrc${}^{\text{\scriptsize$(1)$}}$ will
eventually have a larger target risk than DIP${}^{\text{\scriptsize$(1)$}}$.

The intuition behind the success of DIP${}^{\text{\scriptsize$(1)$}}$ over
OLSSrc${}^{\text{\scriptsize$(1)$}}$ is that the DIP matching penalty in
Equation (• ‣ 3.4) allows the DIP${}^{\text{\scriptsize$(1)$}}$ estimator to
equalize the source and target covariate intervention by projecting it to a
common space. As a result, given the DIP matching penalty, computing least
squares on the source data is the same as computing least squares on the
target data. This observation also explains why the target risk of
DIP${}^{\text{\scriptsize$(1)$}}$ matches that of
DIPOracle${}^{\text{\scriptsize$(1)$}}$. Having this intuition in mind, it is
not hard to imagine extending the guarantees of
DIP${}^{\text{\scriptsize$(1)$}}$ to the generic form of DIP in Equation (3.4)
under appropriate assumptions. Specifically, under Assumption 1, as long as
the function class $\mathcal{V}$ is chosen such that the DIP matching penalty
$\mathcal{D}(v(X),v(\tilde{X}))$ ensures the conditionals $v(X)\mid Y$ and
$v(\tilde{X})\mid Y$ to have the same distribution, then no matter how
$\mathcal{U}$ is chosen we always match the target risks of DIP and DIPOracle.
Moreover, we know that target risk of DIPOracle is close to the oracle target
risk over the function class $\left\\{u\circ v\mid
u\in\mathcal{U},v\in\mathcal{V}\right\\}$. So the target risk of DIP in this
extended setting is also close to the oracle one.

####  4.1.2 Benefit of more source environments for DIP

We show how to make use of more independent source environments to improve the
performance of DIP. Here we consider $M$ ($M\geq 2$) source environments,
where for each $m\in\left\\{1,\ldots,M\right\\}$ the $m$-th source environment
is generated independently according to the source environment in Assumption 1
except for the unknown interventions $a^{\text{\scriptsize$(m)$}}_{X}$ and we
still have $a^{\text{\scriptsize$(m)$}}_{Y}=0$. First, we state a corollary
revealing that it is possible to pick the best source environment for DIP
based on the best source risk. Second, we discuss the reason behind the
performance improvement after picking the best source environment.

First, based on the proof of Theorem 1, we derive the following corollary on
the source population risk.

###### Corollary 3

Under the data generation Assumption 1 and the assumption of no intervention
on $Y$ i.e. $a^{\text{\scriptsize$(1)$}}_{Y}=\widetilde{a}_{Y}=0$, the source
population risk of DIP${}^{\text{\scriptsize$(1)$}}$-mean as defined in
Equation (2) satisfies

$\displaystyle
R^{\text{\scriptsize$(1)$}}\left(f_{\text{DIP}}^{\text{\scriptsize$(1)$}}\right)=\tilde{R}\left(f_{\text{DIP}}^{\text{\scriptsize$(1)$}}\right).$
(23)

The proof of Corollary 3 is provided in Appendix B.3. According to Corollary
3, one can read off the target population risk directly from the source
population risk. Since the choice of source environment 1 is arbitrary, the
same result holds for any of the $M$ source environments. We have
$R^{\text{\scriptsize$(m)$}}\left(f_{\text{DIP}}^{\text{\scriptsize$(m)$}}\right)=\tilde{R}\left(f_{\text{DIP}}^{\text{\scriptsize$(m)$}}\right)$
for any $m\in\left\\{1,\ldots,M\right\\}$. Consequently, having more source
environments allows one to apply DIP between each source environment and the
target environment one by one, and then pick the estimator
$f_{\text{DIP}}^{\text{\scriptsize$(m)$}}$ with the lowest source population
risk to reduce the target population risk.

Second, we reason about the type of source environments that reduces the
target population risk the most. According to Equation (16) and (18) in
Theorem 1, the projection matrix ${G_{\text{\tiny
DIP}}^{\text{\scriptsize$(1)$}}}$ is the term that makes the target population
risks of DIP${}^{\text{\scriptsize$(1)$}}$ and
DIP${}^{\text{\scriptsize$(m)$}}$ different ($m\neq 1$). If the vector
$\Sigma^{-1/2}{b}$ is in the span of the projection matrix ${G_{\text{\tiny
DIP}}^{\text{\scriptsize$(1)$}}}$, then DIP${}^{\text{\scriptsize$(1)$}}$
achieves the oracle target population risk. Otherwise, the target population
risk of DIP${}^{\text{\scriptsize$(1)$}}$ depends on the norm of the component
of $\Sigma^{-1/2}{b}$ outside the span of the projection matrix
${G_{\text{\tiny DIP}}^{\text{\scriptsize$(1)$}}}$.

The above intuition becomes clearer under the additional assumptions of
Corollary 2. There we obtain a simple form for the projection matrix
${G_{\text{\tiny
DIP}}^{\text{\scriptsize$(1)$}}}=\mathbb{I}_{d}-u^{\text{\scriptsize$(1)$}}{u^{\text{\scriptsize$(1)$}}}^{\top}$,
where
$u^{\text{\scriptsize$(1)$}}=\frac{a^{\text{\scriptsize$(1)$}}_{X}-\widetilde{a}_{X}}{\left\|a^{\text{\scriptsize$(1)$}}_{X}-\widetilde{a}_{X}\right\|_{2}}$
assuming $a^{\text{\scriptsize$(1)$}}_{X}\neq\widetilde{a}_{X}$. Under the
same assumptions, the denominator in the DIP target risk in Equation (18)
becomes
$1+\left\|{b}\right\|_{2}^{2}-\left({u^{\text{\scriptsize$(1)$}}}^{\top}{b}\right)^{2}$.
If $a^{\text{\scriptsize$(1)$}}_{X}-\widetilde{a}_{X}$ is orthogonal to ${b}$
then DIP${}^{\text{\scriptsize$(1)$}}$ achieves the oracle target population
risk. Otherwise, DIP${}^{\text{\scriptsize$(1)$}}$ has larger target
population risk than OLSTar. With more source environments, it is more likely
to find a source environment $m$ such that
$a^{\text{\scriptsize$(m)$}}_{X}-\widetilde{a}_{X}$ is closer to be orthogonal
to ${b}$.

Based on the above intuition, we propose the following DIP variant that
provides a weighting choice to take advantage of multiple source environments.

  * •

DIPweigh-mean: the population DIP estimator that makes use of multiple source
environments based on the source risks.

$\displaystyle f_{\text{DIPweigh}}(x)$
$\displaystyle:=\frac{1}{\sum_{m=1}^{M}e^{-\eta\cdot
s_{m}}}\sum_{m=1}^{M}e^{-\eta\cdot
s_{m}}\left(x^{\top}\beta_{\text{DIP}}^{\text{\scriptsize$(m)$}}+\beta_{\text{DIP},0}^{\text{\scriptsize$(m)$}}\right)$
$\displaystyle s_{m}$
$\displaystyle:=R^{\text{\scriptsize$(m)$}}\left(f_{\text{DIP}}^{\text{\scriptsize$(m)$}}\right).$
(24)

$\eta>0$ is a constant. Choosing $\eta$ to be $\infty$ is equivalent to
choosing the source estimator with the lowest source risk. DIPweigh weights
all the source predictions based on the source risk of each source
environment.

Here we introduce the weighted version of DIP rather than directly selecting
the source estimator with the lowest source risk. The main intuition is that
in finite sample, averaging the predictions from several source environments
with low source risks can take advantage of a larger sample size. For example,
in the presence of a less related source environment with very large sample
size, one might still include it if the reduction in variance outweighs the
increase in bias.

####  4.1.3 Failure scenarios of DIP

The target population risk guarantees of DIP in Theorem 1 rely on the
anticausal data generation Assumption 1 and the assumption of no intervention
on $Y$. We already showed in Example 1 that DIP cannot outperform OLSSrc in
the causal prediction setting. Even in the anticausal prediction setting, we
identify two scenarios where DIP${}^{\text{\scriptsize$(1)$}}$-mean might have
large target risk: when the DIP matching penalty is not well-suited for the
underlying type of the intervention that generates the data and when there is
intervention on $Y$.

Consider the following data generation model where the source environment is
generated from the following SCM with interventions on the variance

$\displaystyle\begin{bmatrix}X^{\text{\scriptsize$(1)$}}\\\
Y^{\text{\scriptsize$(1)$}}\end{bmatrix}=\begin{bmatrix}\mathbf{B}&{b}\\\
{\omega}^{\top}&0\end{bmatrix}\begin{bmatrix}X^{\text{\scriptsize$(1)$}}\\\
Y^{\text{\scriptsize$(1)$}}\end{bmatrix}+\begin{bmatrix}a^{\text{\scriptsize$(1)$}}_{X}\odot\varepsilon^{\text{\scriptsize$(1)$}}_{X}\\\
\varepsilon^{\text{\scriptsize$(1)$}}_{Y}\end{bmatrix},$

and the target environment is generated from the same SCM except that the
intervention on $X$ takes the form
$\widetilde{a}_{X}\odot\widetilde{\varepsilon}_{X}$. Here $\odot$ denotes the
$d$-dimensional element-wise multiplication. This intervention is called
variance shift noise intervention. The intervention term
$a^{\text{\scriptsize$(1)$}}_{X}$ and $\widetilde{a}_{X}$ are fixed vectors in
d, and the noise terms are kept the same as in Assumption 1. Under the data
generation model in this subsection, the matching penalty in
DIP${}^{\text{\scriptsize$(1)$}}$-mean (• ‣ 3.4) is always satisfied because
both the left and right hand sides are zero. Consequently,
DIP${}^{\text{\scriptsize$(1)$}}$-mean becomes the same estimator as OLSSrc.
Matching the mean between source and target distribution in this case is no
longer a good idea, because the intervention is on the variance rather than
the mean.

To adapt to the new type of intervention, one can consider DIP-std which puts
the matching penalty on the standard deviations, DIP-std+ which puts the
matching penalty on the means, standard deviations and 25% quantiles, or DIP-
MMD which uses more generic distributional matching via MMD. The exact
formulations consist of replacing the DIP mean matching penalty in Equation (•
‣ 3.4) with the appropriate matching penalties and they are formally
introduced in Appendix A.1.

If the assumptions are set up such that the intervention type agrees with the
matching penalty in DIP, analyzing the theoretical performance of DIP-std,
DIP-std+ or DIP-MMD under linear SCMs works similarly as analyzing that of
DIP-mean. Hence we leave out the theoretical guarantees of DIP-std, DIP-std+
or DIP-MMD for brevity. The empirical performance of DIP-std+ and DIP-MMD is
shown through simulations and real data experiments in Section 5.

The second failure scenario of DIP is when there is intervention on $Y$. This
failure scenario of DIP is already noticeable from Example 3 in Section 3.5.3.
Here we provide a corollary that quantifies the additional target population
risk made by DIP if there is intervention on $Y$.

###### Corollary 4

Under the data generation Assumption 1, the target population risk of OLSTar
and DIP${}^{\text{\scriptsize$(1)$}}$-mean satisfy

$\displaystyle\tilde{R}\left(f_{\text{OLSTar}}\right)$
$\displaystyle=\frac{\sigma^{2}}{1+\sigma^{2}{b}^{\top}\Sigma^{-1}{b}}$
$\displaystyle\tilde{R}\left(f_{\text{DIP}}^{\text{\scriptsize$(1)$}}\right)$
$\displaystyle=\frac{\sigma^{2}}{1+\sigma^{2}{b}^{\top}\Sigma^{-\frac{1}{2}}G_{2}\Sigma^{-\frac{1}{2}}{b}}+\left(a^{\text{\scriptsize$(1)$}}_{Y}-\widetilde{a}_{Y}\right)^{2},$
(25)

where $G_{2}=\Sigma^{1/2}Q_{2}\left(Q_{2}^{\top}\Sigma
Q_{2}\right)^{-1}Q_{2}^{\top}\Sigma^{1/2}$ is a projection matrix with rank
$d-1$. $Q_{2}\in^{d\times d-1}$ is a matrix with columns formed by the vectors
that complete the vector
$\frac{a^{\text{\scriptsize$(1)$}}_{X}+a^{\text{\scriptsize$(1)$}}_{Y}{b}-\widetilde{a}_{X}-\widetilde{a}_{Y}{b}}{\left\|a^{\text{\scriptsize$(1)$}}_{X}+a^{\text{\scriptsize$(1)$}}_{Y}{b}-\widetilde{a}_{X}-\widetilde{a}_{Y}{b}\right\|_{2}}$
to an orthonormal basis.

The proof of Corollary 4 is provided in Appendix B.3. According to Equation
(4) in Corollary 4, the target population risk has an extra term that depends
on the difference between target and source $Y$ intervention. The target
population risk of DIP is increases as the difference between target and
source $Y$ intervention increases. This corollary highlights the result that
DIP has a large target risk when the intervention on $Y$ is large.

###  4.2 Anticausal domain adaptation with intervention on Y

In this subsection, we study the anticausal domain adaptation where there is
intervention on the label $Y$. As illustrated in Example 3 in Section 3.5.3
and in the last section, the intervention on $Y$ can cause DIP to have a large
target population risk. In fact, allowing arbitrary intervention on both $X$
and $Y$ can also lead to unidentifiable cases where two data generation models
result in the same target covariate distribution in the anticausal domain
adaptation. If it were the case, any DA estimator based solely on the target
covariate distribution will have large target risk. The following example
illustrates one concrete unidentifiable case.

##### A simple unidentifiable example:

The target data is generated form the following SCM

$\displaystyle\widetilde{Y}$
$\displaystyle=\widetilde{\varepsilon}_{Y}+\widetilde{a}_{Y}$
$\displaystyle\widetilde{X}$
$\displaystyle=2\widetilde{Y}+\widetilde{\varepsilon}_{X}+\widetilde{a}_{X},$

where $\widetilde{X}$ is $1$-dimensional random variable,
$\widetilde{\varepsilon}_{Y}\sim\mathcal{N}(0,1)$ and
$\widetilde{\varepsilon}_{X}\sim\mathcal{N}(0,0.1)$. Assume we observe the
target covariate distribution $\widetilde{X}\sim\mathcal{N}(3,1.1)$. Without
observing the target label $\widetilde{Y}$ distribution, it is impossible to
tell whether the intervention is
$(\widetilde{a}_{X},\widetilde{a}_{Y})=(0,1.5)$, $(1,1)$ or $(3,0)$. This is
because all three interventions result in the same target covariate
distribution. However, the conditional distribution
$\widetilde{Y}\mid\widetilde{X}$ are different. Consequently, any estimator of
the conditional mean ${\mathbb{E}}\left[\widetilde{Y}\mid\widetilde{X}\right]$
without access to the target label distribution can not get it correct.

To make the anticausal domain adaptation problem with intervention on $Y$
tractable, additional assumptions on the structure of the interventions is
needed. Here we adopt one type of assumptions introduced by Gong et al.
(2016); Heinze-Deml and Meinshausen (2021). This line of work assumes the
existence of conditionally invariant components (CICs) across all source and
target environments. That is, there exists an unknown transformation
$\mathcal{T}$ of the covariates such that the conditional distribution
$\mathcal{T}(X)\mid Y$ is invariant across source and target environments.

In the following, we first prove target population risk guarantees for CIP and
CIRM under the conditionally invariant components assumption. We show that the
CIP and CIRM target risks are much less dependent on the $Y$ intervention than
the DIP target risk. Finally we discuss extensions and variants of CIP and
CIRM.

####  4.2.1 Target risk guarantees of CIP and CIRM with multiple source
environments and conditionally invariant components

We start by stating the data generation assumptions for CIP and CIRM to have
target risk guarantees, namely a SCM and the existence of conditionally
invariant components.

###### Assumption 2

There are $M$ ($M\geq 2$) source environments. Each data point in the $m$-th
source environment is generated i.i.d. according to distribution
$\mathcal{P}^{\text{\scriptsize$(m)$}}$ specified by the following SCM

$\displaystyle\begin{bmatrix}X^{\text{\scriptsize$(m)$}}\\\
Y^{\text{\scriptsize$(m)$}}\end{bmatrix}=\begin{bmatrix}\mathbf{B}&{b}\\\
{\omega}^{\top}&0\end{bmatrix}\begin{bmatrix}X^{\text{\scriptsize$(m)$}}\\\
Y^{\text{\scriptsize$(m)$}}\end{bmatrix}+\begin{bmatrix}a^{\text{\scriptsize$(m)$}}_{X}\\\
a^{\text{\scriptsize$(m)$}}_{Y}\end{bmatrix}+\begin{bmatrix}\varepsilon^{\text{\scriptsize$(m)$}}_{X}\\\
\varepsilon^{\text{\scriptsize$(m)$}}_{Y}\end{bmatrix}.$

Each data point in the target environment is generated i.i.d. according to
distribution $\widetilde{\mathcal{P}}$ specified with the same SCM except for
the mean shift intervention term

$\displaystyle\begin{bmatrix}\widetilde{X}\\\
\widetilde{Y}\end{bmatrix}=\begin{bmatrix}\mathbf{B}&{b}\\\
{\omega}^{\top}&0\end{bmatrix}\begin{bmatrix}\widetilde{X}\\\
\widetilde{Y}\end{bmatrix}+\begin{bmatrix}\widetilde{a}_{X}\\\
\widetilde{a}_{Y}\end{bmatrix}+\begin{bmatrix}\widetilde{\varepsilon}_{X}\\\
\widetilde{\varepsilon}_{Y}\end{bmatrix},$

where $\mathbb{I}_{d}-\mathbf{B}$ is invertible, the prediction problem is
anticausal ${\omega}=0$, the intervention term
$\begin{bmatrix}a^{\text{\scriptsize$(1)$}}_{X}\\\
a^{\text{\scriptsize$(1)$}}_{Y}\end{bmatrix}$ and
$\begin{bmatrix}\widetilde{a}_{X}\\\ \widetilde{a}_{Y}\end{bmatrix}$ are
vectors in d+1, the noise term
$\begin{bmatrix}\varepsilon^{\text{\scriptsize$(m)$}}_{X}\\\
\varepsilon^{\text{\scriptsize$(m)$}}_{Y}\end{bmatrix}$ and
$\begin{bmatrix}\widetilde{\varepsilon}_{X}\\\
\widetilde{\varepsilon}_{Y}\end{bmatrix}$ share the same distribution with

$\displaystyle{\mathbb{E}}\left[\varepsilon^{\text{\scriptsize$(m)$}}_{X}\right]={\mathbb{E}}\left[\widetilde{\varepsilon}_{X}\right]=0,\quad{\mathbb{E}}\left[\varepsilon^{\text{\scriptsize$(m)$}}_{X}{\varepsilon^{\text{\scriptsize$(m)$}}_{X}}^{\top}\right]={\mathbb{E}}\left[\widetilde{\varepsilon}_{X}{\widetilde{\varepsilon}_{X}}^{\top}\right]=\Sigma,$
$\displaystyle{\mathbb{E}}\left[\varepsilon^{\text{\scriptsize$(m)$}}_{Y}\right]={\mathbb{E}}\left[\widetilde{\varepsilon}_{Y}\right]=0,\quad{\mathbb{E}}\left[{\varepsilon^{\text{\scriptsize$(m)$}}_{Y}}^{2}\right]={\mathbb{E}}\left[{\widetilde{\varepsilon}_{Y}}^{2}\right]=\sigma^{2}.$

In addition, the noise terms on $X$ and $Y$ are uncorrelated
${\mathbb{E}}\left[\varepsilon^{\text{\scriptsize$(m)$}}_{Y}\cdot\varepsilon^{\text{\scriptsize$(m)$}}_{X}\right]={\mathbb{E}}\left[\widetilde{\varepsilon}_{Y}\cdot\widetilde{\varepsilon}_{X}\right]=0$.
The interventions do not span the whole space (to ensure the existence of
conditionally invariant components)

$\displaystyle\text{dim}\left(\text{span}\left(a^{\text{\scriptsize$(2)$}}_{X}-a^{\text{\scriptsize$(1)$}}_{X},\ldots,a^{\text{\scriptsize$(M)$}}_{X}-a^{\text{\scriptsize$(1)$}}_{X}\right)\right)=p\leq
d-1,$ (26)

and the target $X$ intervention is in the span of source $X$ interventions

$\displaystyle\widetilde{a}_{X}-a^{\text{\scriptsize$(1)$}}_{X}\in\text{span}\left(a^{\text{\scriptsize$(2)$}}_{X}-a^{\text{\scriptsize$(1)$}}_{X},\ldots,a^{\text{\scriptsize$(M)$}}_{X}-a^{\text{\scriptsize$(1)$}}_{X}\right).$
(27)

Compared to Assumption 1, Assumption 2 involves multiple source environments
instead of one. Also, the way the source and target environments are generated
up to Equation (26) is the same as in Assumption 1. Equation (26) assumes that
the $X$ interventions do not span the whole covariate space d. It ensures the
existence of a invariant linear projection of the covariates given the label
$Y$. More precisely, this assumption allows us to find a vector $v$ which is
orthogonal to the
$\text{span}\left(\left(\mathbb{I}_{d}-\mathbf{B}\right)^{-1}\left(a^{\text{\scriptsize$(2)$}}_{X}-a^{\text{\scriptsize$(1)$}}_{X}\right),\ldots,\left(\mathbb{I}_{d}-\mathbf{B}\right)^{-1}\left(a^{\text{\scriptsize$(M)$}}_{X}-a^{\text{\scriptsize$(1)$}}_{X}\right)\right)$
and the projection of the covariates $X^{\top}v$ has the same intervention
term across source environments. This particular linear projection of the
covariates becomes one conditionally invariant component. To make sure the
same conditionally invariant component is also valid in the target
environment, Equation (27) requires that the target $X$ intervention is in the
span of source $X$ interventions.

Given the data generation assumption above, we have the following theorem on
the target risk of CIP and CIRM.

###### Theorem 5

Under the data generation Assumption 2, the population target risks of CIP-
mean and CIRM${}^{\text{\scriptsize$(m)$}}$-mean for any
$m\in\left\\{1,\ldots,M\right\\}$ satisfy

$\displaystyle\tilde{R}\left(f_{\text{OLSTar}}\right)$
$\displaystyle=\frac{\sigma^{2}}{1+\sigma^{2}{b}^{\top}\Sigma^{-1}{b}},$ (28)
$\displaystyle\tilde{R}\left(f_{\text{CIP}}\right)$
$\displaystyle=\frac{\sigma^{2}+\Delta_{Y}}{1+\left(\sigma^{2}+\Delta_{Y}\right){b}^{\top}\Sigma^{-\frac{1}{2}}G_{\text{\tiny
CIP}}\Sigma^{-\frac{1}{2}}{b}}+\frac{\left(\widetilde{a}_{Y}-\bar{a}_{Y}\right)^{2}-\Delta_{Y}}{\left(1+\left(\sigma^{2}+\Delta_{Y}\right){b}^{\top}\Sigma^{-\frac{1}{2}}G_{\text{\tiny
CIP}}\Sigma^{-\frac{1}{2}}{b}\right)^{2}},$ (29)
$\displaystyle\tilde{R}\left(f_{\text{CIRM}}^{\text{\scriptsize$(m)$}}\right)$
$\displaystyle=\frac{\sigma^{2}}{1+\sigma^{2}{b}^{\top}\Sigma^{-\frac{1}{2}}{G_{\text{\tiny
DIP}}^{\text{\scriptsize$(m)$}}}\Sigma^{-\frac{1}{2}}{b}}+\frac{\left(a^{\text{\scriptsize$(m)$}}_{Y}-\widetilde{a}_{Y}\right)^{2}}{\left(1+\sigma^{2}{b}^{\top}\Sigma^{-\frac{1}{2}}{G_{\text{\tiny
DIP}}^{\text{\scriptsize$(m)$}}}\Sigma^{-\frac{1}{2}}{b}\right)^{2}},$ (30)

where $\bar{a}_{Y}=\frac{1}{M}\sum_{j=1}^{M}a^{\text{\scriptsize$(j)$}}_{Y}$,
$\Delta_{Y}=\frac{1}{M}\sum_{j=1}^{M}\left(a^{\text{\scriptsize$(j)$}}_{Y}-\bar{a}_{Y}\right)^{2}$.
$G_{\text{\tiny CIP}}=\Sigma^{1/2}Q_{\text{\tiny CIP}}\left(Q_{\text{\tiny
CIP}}^{\top}\Sigma Q_{\text{\tiny CIP}}\right)^{-1}Q_{\text{\tiny
CIP}}^{\top}\Sigma^{1/2}$ is a projection matrix with rank $d-p$ where
$Q_{\text{\tiny CIP}}\in^{d\times(d-p)}$ is a matrix with columns formed by an
orthonormal basis of the orthogonal complement of
$\text{span}(a^{\text{\scriptsize$(2)$}}_{X}-a^{\text{\scriptsize$(1)$}}_{X},\ldots,a^{\text{\scriptsize$(M)$}}_{X}-a^{\text{\scriptsize$(1)$}}_{X})$.
${G_{\text{\tiny DIP}}^{\text{\scriptsize$(m)$}}}$ is a projection matrix
defined in the same way as ${G_{\text{\tiny DIP}}^{\text{\scriptsize$(1)$}}}$
in Theorem 1.

The proof of Theorem 5 is provided in Appendix C.1. Comparing the target
population risk of CIRM${}^{\text{\scriptsize$(m)$}}$ in Equation (30) with
that of DIP${}^{\text{\scriptsize$(m)$}}$ in Equation (4),
CIRM${}^{\text{\scriptsize$(m)$}}$ reduces the dependency on the difference in
$Y$ intervention $a^{\text{\scriptsize$(m)$}}_{Y}-\widetilde{a}_{Y}$. This is
because we always have
$1+\sigma^{2}{b}^{\top}\Sigma^{-\frac{1}{2}}{G_{\text{\tiny
DIP}}^{\text{\scriptsize$(m)$}}}\Sigma^{-\frac{1}{2}}{b}>1$. The target
population risk of CIRM${}^{\text{\scriptsize$(m)$}}$ when there is
intervention on $Y$ in Equation (30) has an additional term depending on
$a^{\text{\scriptsize$(m)$}}_{Y}-\widetilde{a}_{Y}$ when compared to that of
DIP${}^{\text{\scriptsize$(m)$}}$ when there is no intervention on $Y$ in
Equation (18). The additional term becomes close to zero when
$\sigma^{2}{b}^{\top}\Sigma^{-\frac{1}{2}}{G_{\text{\tiny
DIP}}^{\text{\scriptsize$(m)$}}}\Sigma^{-\frac{1}{2}}{b}$ is large.

In fact, without additional assumptions to Assumption 2, the dependence on
$a^{\text{\scriptsize$(m)$}}_{Y}-\widetilde{a}_{Y}$ or similar terms is
unavoidable for any DA estimator. Because the Assumption 2 does not prevent
${b}$ from being in the
$\text{span}\left(a^{\text{\scriptsize$(2)$}}_{X}-a^{\text{\scriptsize$(1)$}}_{X},\ldots,a^{\text{\scriptsize$(M)$}}_{X}-a^{\text{\scriptsize$(1)$}}_{X}\right)$,
it can still result in a slightly unidentifiable example similar to the one
presented at the beginning of Section 4.2. See Appendix D for ways to get rid
of the $a^{\text{\scriptsize$(m)$}}_{Y}-\widetilde{a}_{Y}$ dependence at the
cost of small additional target risk.

In the same spirit of Corollary 2, we present a corollary that puts additional
assumptions on the positions of the interventions
$a^{\text{\scriptsize$(m)$}}_{X}$ and $\widetilde{a}_{X}$ to make the results
in Theorem 5 easier to understand.

###### Corollary 6

In addition to Assumption 2, suppose
$\Sigma=\frac{\sigma^{2}}{\rho}\mathbb{I}_{d}$ with $\rho>0$, then

$\displaystyle\tilde{R}\left(f_{\text{OLSTar}}\right)$
$\displaystyle=\frac{\sigma^{2}}{1+\rho\left\|{b}\right\|_{2}^{2}},$ (31)
$\displaystyle\tilde{R}\left(f_{\text{CIP}}\right)$
$\displaystyle=\frac{\sigma^{2}}{1+\rho\left\|{b}\right\|_{2}^{2}-\rho\left(P_{\text{\tiny
CIP}}^{\top}{b}\right)^{2}}+\frac{\left(\widetilde{a}_{Y}-\bar{a}_{Y}\right)^{2}-\Delta_{Y}}{\left[1+\rho\left\|{b}\right\|_{2}^{2}-\rho\left(P_{\text{\tiny
CIP}}^{\top}{b}\right)^{2}\right]^{2}},$ (32)
$\displaystyle\tilde{R}\left(f_{\text{CIRM}{\text{\scriptsize$(m)$}}}\right)$
$\displaystyle=\frac{\sigma^{2}}{1+\rho\left\|{b}\right\|_{2}^{2}-\rho\left({u^{\text{\scriptsize$(m)$}}}^{\top}{b}\right)^{2}}+\frac{\left(\widetilde{a}_{Y}-a^{\text{\scriptsize$(m)$}}_{Y}\right)^{2}}{\left[1+\rho\left\|{b}\right\|_{2}^{2}-\rho\left({u^{\text{\scriptsize$(m)$}}}^{\top}{b}\right)^{2}\right]^{2}},$
(33)

where $\bar{a}_{Y}=\frac{1}{M}\sum_{m=1}^{M}a^{\text{\scriptsize$(m)$}}_{Y}$,
$\Delta_{Y}=\left(\widetilde{a}_{Y}-\bar{a}_{Y}\right)^{2}-\frac{1}{M}\sum_{m=1}^{M}\left(a^{\text{\scriptsize$(m)$}}_{Y}-\bar{a}_{Y}\right)^{2}$,
$P_{\text{\tiny CIP}}=Q_{\text{\tiny CIP}}^{\perp}\in^{d\times p}$ is the
matrix with columns formed by the orthonormal basis of
$\text{span}\left(a^{\text{\scriptsize$(2)$}}_{X}-a^{\text{\scriptsize$(1)$}}_{X},\ldots,a^{\text{\scriptsize$(M)$}}_{X}-a^{\text{\scriptsize$(1)$}}_{X}\right)$
and
$u^{\text{\scriptsize$(m)$}}=\frac{a^{\text{\scriptsize$(m)$}}_{X}-\widetilde{a}_{X}}{\left\|a^{\text{\scriptsize$(m)$}}_{X}-\widetilde{a}_{X}\right\|_{2}}$.
Additionally, if
$a^{\text{\scriptsize$(2)$}}_{X}-a^{\text{\scriptsize$(1)$}}_{X},\ldots,a^{\text{\scriptsize$(M)$}}_{X}-a^{\text{\scriptsize$(1)$}}_{X},\xi$
are generated independently from Gaussian distribution
$\mathcal{N}\left(0,\tau^{2}\mathbb{I}_{d}\right)$ and
$\widetilde{a}_{X}-a^{\text{\scriptsize$(1)$}}_{X}=P_{\text{\tiny CIP}}\xi$,
$d\geq 6M$, a constant $0<t\leq d/2$, then with probability at least
$\left(1-2\exp(-d/32)-2\exp(-M/32)\right)\cdot\left(1-\exp(-t/16)-2\exp(-t/4)\right)$,
we have
$\text{dim}\left(\text{span}\left(a^{\text{\scriptsize$(2)$}}_{X}-a^{\text{\scriptsize$(1)$}}_{X},\ldots,a^{\text{\scriptsize$(M)$}}_{X}-a^{\text{\scriptsize$(1)$}}_{X}\right)\right)=M-1$
and additionally

$\displaystyle\tilde{R}\left(f_{\text{CIP}}\right)$
$\displaystyle\leq\frac{\sigma^{2}}{1+\rho\left(1-\frac{3(M-1)}{d}\right)\left\|{b}\right\|_{2}^{2}}+\frac{\left(\widetilde{a}_{Y}-\bar{a}_{Y}\right)^{2}-\Delta_{Y}}{\left[1+\rho\left(1-\frac{3(M-1)}{d}\right)\left\|{b}\right\|_{2}^{2}\right]},$
(34) $\displaystyle\tilde{R}\left(f_{\text{CIP}}\right)$
$\displaystyle\geq\frac{\sigma^{2}}{1+\rho\left(1-\frac{(M-1)}{3d}\right)\left\|{b}\right\|_{2}^{2}}+\frac{\left(\widetilde{a}_{Y}-\bar{a}_{Y}\right)^{2}-\Delta_{Y}}{\left[1+\rho\left(1-\frac{(M-1)}{3d}\right)\left\|{b}\right\|_{2}^{2}\right]},$
(35)
$\displaystyle\tilde{R}\left(f_{\text{CIRM}{\text{\scriptsize$(m)$}}}\right)$
$\displaystyle\leq\frac{\sigma^{2}}{1+\rho\left(1-\frac{t}{d}\right)\left\|{b}\right\|_{2}^{2}}+\frac{\left(\widetilde{a}_{Y}-a^{\text{\scriptsize$(m)$}}_{Y}\right)^{2}}{\left[1+\rho\left(1-\frac{t}{d}\right)\left\|{b}\right\|_{2}^{2}\right]}.$
(36)

The proof of Corollary 6 is provided in Appendix C.2. Under the assumptions of
Corollary 6, it is clear that for $M$ and $d$ sufficiently large, with high
probability, CIRM${}^{\text{\scriptsize$(m)$}}$ has smaller target population
risk than CIP when all $Y$ interventions are equal
$a^{\text{\scriptsize$(1)$}}_{Y}=\ldots=a^{\text{\scriptsize$(M)$}}_{Y}=\widetilde{a}_{Y}$.
This is because the last term in Equation (32) become zero can be ignored and
$\frac{M-1}{3d}\geq\frac{t}{d}$ when $M\geq 3t+1$. Intuitively, CIP only uses
the conditionally invariant components (roughly $d-p$ coordinates) to build
the estimator, while CIRM${}^{\text{\scriptsize$(m)$}}$ takes advantage of the
other coordinates of $X$ (roughly $d-1$ coordinates).

The intuition behind CIRM becomes apparent after the theorem statement.
CIRM${}^{\text{\scriptsize$(m)$}}$ is indeed a combination of
DIP${}^{\text{\scriptsize$(m)$}}$ and CIP: it applies CIP in the first step to
obtain the conditionally invariant component which serves as a proxy of the
label $Y$ to correct for the intervention on $Y$, then it applies
DIP${}^{\text{\scriptsize$(m)$}}$ with the corrected target covariate
distribution to improve the target prediction performance. The conditionally
invariant components identified by CIP are useful to constitute a proxy of $Y$
but they alone do not predict $Y$ very well especially when there are only a
few of them. DIP has good target risk guarantees when there is no $Y$
intervention. When there is $Y$ intervention, CIRM uses CIP to correct for the
$Y$ distribution perturbation and to create a residual which does not suffer
from intervention, then apply DIP on the residual.

Since CIRM can be seen as applying DIP on the label-distribution-corrected
source and target data, it is natural to introduce a weighted version of CIRM
called CIRMweigh similar to DIPweigh (• ‣ 4.1.2). A precise formulation of
CIRMweigh can be found in Appendix A.1.

Under the assumptions of Corollary 6, we summarize the target risk upper
bounds of all DA methods in this paper in Table 2. For brevity, we only
present the target population risk upper bounds under high probability when
the interventions are generated i.i.d. Gaussian
$\mathcal{N}\left(0,\tau^{2}\mathbb{I}_{d}\right)$. The upper bounds are tight
up to constant factors in the denominators because we first proved the exact
target risks with equality and then applied Gaussian concentration to obtain
the upper bounds. Consequently, the upper bounds serve the comparison purpose.

|  Estimator |  Target population risk upper bound interventions under general position
---|---|---
|  OLSTar (oracle) | $\displaystyle\frac{\sigma^{2}}{1+\rho\left\|{b}\right\|_{2}^{2}}$
No intervention on $Y$ (Corollary 2) |  OLSSrc${}^{\text{\scriptsize$(1)$}}$ | $\displaystyle{\frac{\sigma^{2}}{1+\rho\left\|{b}\right\|_{2}^{2}}+\frac{c\cdot\tau^{2}\left\|{b}\right\|_{2}^{2}}{\left[1+\rho\left\|{b}\right\|_{2}^{2}\right]^{2}}}$
DIP${}^{\text{\scriptsize$(1)$}}$ | $\displaystyle\frac{\sigma^{2}}{1+\rho(1-\frac{c}{d})\left\|{b}\right\|_{2}^{2}}$
DIP${}^{\text{\scriptsize$(m)$}}$ | $\displaystyle\frac{\sigma^{2}}{1+\rho(1-\frac{c}{d})\left\|{b}\right\|_{2}^{2}}+\left(\widetilde{a}_{Y}-a^{\text{\scriptsize$(m)$}}_{Y}\right)^{2}$
Intervention on $Y$ with CICs $M$ sources (Corollary 6) |  CIP | $\displaystyle\frac{\sigma^{2}}{1+\rho(1-\frac{c(M-1)}{d})\left\|{b}\right\|_{2}^{2}}+\frac{\left(\widetilde{a}_{Y}-\bar{a}_{Y}\right)^{2}-\Delta_{Y}}{\left[1+\rho(1-\frac{c(M-1)}{d})\left\|{b}\right\|_{2}^{2}\right]^{2}}$
CIRM${}^{\text{\scriptsize$(m)$}}$ | $\displaystyle\frac{\sigma^{2}}{1+\rho(1-\frac{c}{d})\left\|{b}\right\|_{2}^{2}}+\frac{\left(\widetilde{a}_{Y}-a^{\text{\scriptsize$(m)$}}_{Y}\right)^{2}}{\left[1+\rho(1-\frac{c}{d})\left\|{b}\right\|_{2}^{2}\right]^{2}}$
Table 2: Summary of target population risk for DA estimators for anticausal
domain adaptation under the assumptions of Corollary 2 and Corollary 6. Here
$c>0$ is a generic constant to improve readability, which can be different for
different methods. For simplicity, we only present the target population risk
upper bounds holding with high probability when the interventions are
generated i.i.d. Gaussian $\mathcal{N}(0,\tau^{2}\mathbb{I}_{d})$ and when
both $M$ and $d$ are large. Under the assumptions of Corollary 2, the target
risk of OLSSrc${}^{\text{\scriptsize$(1)$}}$ depends on the magnitude of the
difference in intervention $\tau$, while the other DA methods in the table do
not: DIP${}^{\text{\scriptsize$(1)$}}$ outperforms
OLSSrc${}^{\text{\scriptsize$(1)$}}$. Under the assumptions of Corollary 6,
when intervention on $Y$ becomes large, DIP${}^{\text{\scriptsize$(m)$}}$ is
worse than CIP or CIRM${}^{\text{\scriptsize$(m)$}}$.
CIRM${}^{\text{\scriptsize$(m)$}}$ slightly outperforms CIP.

####  4.2.2 On relaxing the assumptions needed for CIP and CIRM

We discuss two different relaxations of Assumption 2.

First, the two assumptions (26) and (27) in Assumption 2 can be replaced by a
single assumption, namely there exists a non-zero vector $v\in^{d}$ such that
$v^{\top}X^{\text{\scriptsize$(1)$}},\ldots,v^{\top}X^{\text{\scriptsize$(M)$}}$
and $v^{\top}\widetilde{X}$ all have the same distribution. This is also
equivalent to saying that the projection of the covariates on the direction
$v$ is a conditionally invariant component. Stating the CIC assumption as we
did in Assumption 2 has the advantage of separating the assumptions on the
source interventions from those on the target intervention.

When the dimension $d$ is larger than the number of source environments $M$,
the assumption (26) on the dimension of the span of the source $X$
interventions is always satisfied. In the case of $M<d$, the more source
environments there are, the more likely that the target $X$ intervention is in
the span of the source $X$ interventions.

Second, the mean shift noise intervention in Assumption 2 can be relaxed to
other types of noise interventions. For example, the noise intervention can be
the standard deviation shift as we did for DIP in Section 4.1.3. We may
consider CIP-std which puts the conditional invariance penalty on the standard
deviations, CIP-std+ which puts the conditional invariance penalty on the
means, standard deviations and $25\%$ quantiles or CIP-MMD which uses generic
distributional matching to make sure the conditional distribution of
$v^{\top}X$ is invariant across source environments. CIRM can be extended
similarly. We do not provide theoretical guarantees of these extensions and we
only show their empirical performance through simulation and data experiments
in Section 5.

###  4.3 Mixed-causal-anticausal domain adaptation

In this subsection, we consider the mixed-causal-anticausal DA setting where
both causal and anticausal variables are present. In terms of the SCMs,
neither the vector ${b}$ nor ${\omega}$ in Equation (3) is assumed to be zero.
In terms of the graph associated with the SCM, some variables are descendants
of the label $Y$ and some variables are ancestors of $Y$. As we have seen in
Example 1 and Example 2 in Section 3.5, DA methods such as DIP perform worse
than Causal or OLSSrc in the causal setting, while DIP can have smaller target
population risk than Causal or OLSSrc in the anticausal setting. When both
causal and anticausal variables are present, it is no longer clear whether
more sophisticated DA methods would be better than Causal or OLSSrc. To gain
some intuition, we first show a simple mixed-causal-anticausal DA example to
illustrate how the standard DIP, CIP and CIRM can have worse target risk than
Causal. Then we introduce new algorithms to tackle the mixed-causal-anticausal
DA problem.

####  4.3.1 A mixed-causal-anticausal DA example to illustrate the failure of
the standard DIP, CIP and CIRM

Here we provide a simple mixed-causal-anticausal DA problem to illustrate the
difficulty of the mixed-causal-anticausal setting. Example 4 is a DA problem
with a large number of source environments ($M\geq 4$) and one target
environment. The data in the source and target environment are generated
independently according to the following SCMs, with the causal diagram on the
left and the structural equations on the right of Figure 5.

$X_{1}$$X_{2}$$X_{3}$$A$$Y$

$\begin{aligned}
X^{\text{\scriptsize$(m)$}}_{1}&=\varepsilon^{\text{\scriptsize$(m)$}}_{X_{1}}+a^{\text{\scriptsize$(m)$}}_{X_{1}}\\\
X^{\text{\scriptsize$(m)$}}_{2}&=Y^{\text{\scriptsize$(m)$}}+\varepsilon^{\text{\scriptsize$(m)$}}_{X_{2}}+a^{\text{\scriptsize$(m)$}}_{X_{2}}\\\
X^{\text{\scriptsize$(m)$}}_{3}&=Y^{\text{\scriptsize$(m)$}}+\varepsilon^{\text{\scriptsize$(m)$}}_{X_{3}}\\\
Y^{\text{\scriptsize$(m)$}}&=X^{\text{\scriptsize$(m)$}}_{1}+0+a^{\text{\scriptsize$(m)$}}_{Y}\end{aligned}\hskip
14.22636pt\begin{aligned}
\widetilde{X}_{1}&=\widetilde{\varepsilon}_{X_{1}}+0\\\
\widetilde{X}_{2}&=\widetilde{Y}+\widetilde{\varepsilon}_{X_{2}}+0\\\
\widetilde{X}_{3}&=\widetilde{Y}+\widetilde{\varepsilon}_{X_{3}}\\\
\widetilde{Y}&=\widetilde{X}_{1}+0+0\\\ \end{aligned}$

Figure 5: The causal diagram and structural equations for the $m$-th source
($m\in\left\\{1,\ldots,M\right\\}$) and target environments in Example 4

Here the noise variables follow independent Gaussian distributions with
$\varepsilon^{\text{\scriptsize$(m)$}}_{X_{i}},\widetilde{\varepsilon}_{X_{i}}\sim\mathcal{N}(0,0.1)$,
$i\in\left\\{1,\ldots,3\right\\}$. The noise variable of $Y$ is set to zero.
The type of intervention is mean shift noise intervention. The variable
$X_{3}$ is never intervened on, so $X_{3}$ is conditionally invariant. For the
first source environment, the intervention
$a^{\text{\scriptsize$(1)$}}=\begin{bmatrix}1&1&0&1\end{bmatrix}^{\top}$. For
$m\geq 2$,
$a^{\text{\scriptsize$(m)$}}=\begin{bmatrix}a^{\text{\scriptsize$(m)$}}_{X_{1}}&a^{\text{\scriptsize$(m)$}}_{X_{2}}&0&a^{\text{\scriptsize$(m)$}}_{Y}\end{bmatrix}^{\top}$
where each coordinate is generated i.i.d. from $\mathcal{N}(0,10)$ and we
ensure that the $M-1$ interventions span a subspace of dimension 3. For the
target environment, the intervention is
$\begin{bmatrix}0&0&0&0\end{bmatrix}^{\top}$. Compared to Example 3, the
inclusion of the causal covariates $X_{1}$ and $X_{2}$ makes the DA problem
more complicated.

The population estimators when $M$ tends to $\infty$ can be computed
explicitly

$\displaystyle\begin{bmatrix}\beta_{\text{OLSTar}}\\\
\beta_{\text{OLSTar},0}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}1&0&0&0\end{bmatrix}^{\top},$
$\displaystyle\begin{bmatrix}\beta_{\text{Causal}}\\\
\beta_{\text{Causal},0}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}1&0&0&0\end{bmatrix}^{\top},$
$\displaystyle\begin{bmatrix}\beta_{\text{SrcPool}}\\\
\beta_{\text{SrcPool},0}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}0&0&1&0\end{bmatrix}^{\top},$
$\displaystyle\begin{bmatrix}\beta_{\text{DIP}}^{\text{\scriptsize$(1)$}}\\\
\beta_{\text{DIP},0}^{\text{\scriptsize$(1)$}}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\frac{4}{3}&-\frac{1}{3}&-\frac{1}{6}&2\end{bmatrix}^{\top},$
$\displaystyle\begin{bmatrix}\beta_{\text{CIP}}\\\
\beta_{\text{CIP},0}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}0&0&1&0\end{bmatrix}^{\top},$
$\displaystyle\begin{bmatrix}{\beta_{\text{CIRM}}^{\text{\scriptsize$(1)$}}}\\\
\beta_{\text{CIRM},0}^{\text{\scriptsize$(1)$}}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}1&0&0&1\end{bmatrix}^{\top}.$

Note that with a large number of source environments, CIP and SrcPool both
identify the conditional invariant component $X_{3}$. The Causal estimator is
the best because we made the noise variable on $Y$ to be $0$ and the
intervention on $Y$ in the target to be 0. DIP${}^{\text{\scriptsize$(1)$}}$
does not find the Causal estimator because the $Y$ intervention makes it
difficult to align the covariate interventions between source and target.
CIRM${}^{\text{\scriptsize$(1)$}}$ does not find the Causal estimator because
even if it can correct for the label intervention, matching on the causal
covariate $X_{1}$ is not a good idea due to similar reason we have seen
applying DIP for causal prediction in Example 1. The corresponding population
source and target risks are summarize in Table 3. We conclude that unlike in
the anticausal DA setting, in the presence of both causal and anticausal
covariates, CIRM which is based on the idea of domain invariant projection
after label correction no longer outperforms SrcPool.

Risk Methods |  OLSTar (oracle) |  Causal |  SrcPool |  DIP${}^{\text{\scriptsize$(1)$}}$ |  CIP |  CIRM${}^{\text{\scriptsize$(1)$}}$
---|---|---|---|---|---|---
Ex 4, source risk $R^{\text{\scriptsize$(1)$}}$ | 1.000 | 1.000 | 0.100 | 0.000 | 0.100 | 0.000
Ex 4, target risk $\tilde{R}$ | 0.000 | 0.000 | 0.100 | 4.000 | 0.100 | 1.000
Table 3: Population source and target risks in Example 4 (the lower the
better). The oracle target risk is highlighted in bold. In Example 3 of mixed-
causal-anticausal prediction with intervention on $Y$,
DIP${}^{\text{\scriptsize$(1)$}}$, CIP and CIRM${}^{\text{\scriptsize$(1)$}}$
all perform worse than Causal in terms of target population risk.

One might argue that the superior performance of Causal over SrcPool is made
up because we set the target label intervention $\widetilde{a}_{Y}$ to be
zero. The concern is valid in general. However, it is not difficult to observe
that no matter how we set $\widetilde{a}_{Y}$ there exist better estimators
than SrcPool. In fact, if we know $X_{1}$ is the only causal variable, we can
regress $Y,X_{2},X3$ on $X_{1}$ and consider the prediction problem on the
residuals. The resulting prediction problem is anticausal with intervention on
$Y$. Consequently, it can be solved with DA methods discussed in Section 4.2.
We formulate this idea precisely in the next subsection.

####  4.3.2 New DA methods for mixed-causal-anticausal domain adaptation

Instead of studying the most general mixed-causal-anticausal domain
adaptation, we first restrict ourselves to the setting where the “rough causal
structure around $Y$” is known. That is, we know which covariates are the
descendants of $Y$, denoted as $X_{\text{D}}$, and we also know which
covariates are the parents of $Y$ or the parents of $X_{\text{D}}$ (denoted as
$X_{\text{P}}$) as shown in Figure 6. Assuming the “rough causal structure”,
we show that this mixed-causal-anticausal problem can be reduced to the
familiar problem in the previous subsections. Assumption 3 makes data
generation requirements precise.

$X_{\text{P}}$$X_{\text{D}}$$A$$Y$ Figure 6: The causal diagram for our mixed-
causal-anticausal domain adaptation setup.

###### Assumption 3

There are $M$ ($M\geq 1$) source environments. Each data point in the $m$-th
source environment is generated i.i.d. according to distribution
$\mathcal{P}^{\text{\scriptsize$(m)$}}$ specified by the following SCM

$\displaystyle\begin{bmatrix}X^{\text{\scriptsize$(m)$}}_{\text{P}}\\\
X^{\text{\scriptsize$(m)$}}_{\text{D}}\\\
Y^{\text{\scriptsize$(m)$}}\end{bmatrix}=\begin{bmatrix}\mathbf{B}_{\text{P}}&0&0\\\
\mathbf{B}_{\text{D-P}}&\mathbf{B}_{\text{D}}&{b}_{\text{D}}\\\
{\omega}_{\text{P}}^{\top}&0&0\end{bmatrix}\begin{bmatrix}X^{\text{\scriptsize$(m)$}}_{\text{P}}\\\
X^{\text{\scriptsize$(m)$}}_{\text{D}}\\\
Y^{\text{\scriptsize$(m)$}}\end{bmatrix}+\begin{bmatrix}a^{\text{\scriptsize$(m)$}}_{X,\text{P}}\\\
a^{\text{\scriptsize$(m)$}}_{X,\text{D}}\\\
a^{\text{\scriptsize$(m)$}}_{Y}\end{bmatrix}+\begin{bmatrix}\varepsilon^{\text{\scriptsize$(m)$}}_{X,\text{P}}\\\
\varepsilon^{\text{\scriptsize$(m)$}}_{X,\text{D}}\\\
\varepsilon^{\text{\scriptsize$(m)$}}_{Y}\end{bmatrix}.$

Each data point in the target environment is generated i.i.d. according to
distribution $\widetilde{\mathcal{P}}$ specified with the same SCM except for
the mean shift intervention term

$\displaystyle\begin{bmatrix}\widetilde{X}_{\text{P}}\\\
\widetilde{X}_{\text{D}}\\\
\widetilde{Y}\end{bmatrix}=\begin{bmatrix}\mathbf{B}_{\text{P}}&0&0\\\
\mathbf{B}_{\text{D-P}}&\mathbf{B}_{\text{D}}&{b}_{\text{D}}\\\
{\omega}_{\text{P}}^{\top}&0&0\end{bmatrix}\begin{bmatrix}\widetilde{X}_{\text{P}}\\\
\widetilde{X}_{\text{D}}\\\
\widetilde{Y}\end{bmatrix}+\begin{bmatrix}\widetilde{a}_{X,\text{P}}\\\
\widetilde{a}_{X,\text{D}}\\\
\widetilde{a}_{Y}\end{bmatrix}+\begin{bmatrix}\widetilde{\varepsilon}_{X,\text{P}}\\\
\widetilde{\varepsilon}_{X,\text{D}}\\\
\widetilde{\varepsilon}_{Y}\end{bmatrix},$

where $\mathbf{B}_{\text{P}}\in^{r\times r}$,
$\mathbf{B}_{\text{D}}\in^{(d-r)\times(d-r)}$ and
$\mathbf{B}_{\text{D-P}}\in^{(d-r)\times r}$ are unknown constant matrices
such that $\mathbb{I}_{d}-\begin{bmatrix}\mathbf{B}_{\text{P}}&0\\\
\mathbf{B}_{\text{D-P}}&\mathbf{B}_{\text{D}}\end{bmatrix}$ is invertible,
${\omega}_{\text{P}}\in^{r}$ and ${b}_{\text{D}}\in^{d-r}$ are unknown
constant vectors, the intervention terms
$\begin{bmatrix}a^{\text{\scriptsize$(m)$}}_{X,\text{P}}\\\
a^{\text{\scriptsize$(m)$}}_{X,\text{D}}\\\
a^{\text{\scriptsize$(m)$}}_{Y}\end{bmatrix}$ and
$\begin{bmatrix}\widetilde{a}_{X,\text{P}}\\\ \widetilde{a}_{X,\text{D}}\\\
\widetilde{a}_{Y}\end{bmatrix}$ are vectors in d+1, the noise terms
$\begin{bmatrix}\varepsilon^{\text{\scriptsize$(m)$}}_{X,\text{P}}\\\
\varepsilon^{\text{\scriptsize$(m)$}}_{X,\text{D}}\\\
\varepsilon^{\text{\scriptsize$(m)$}}_{Y}\end{bmatrix}$ and
$\begin{bmatrix}\widetilde{\varepsilon}_{X,\text{P}}\\\
\widetilde{\varepsilon}_{X,\text{D}}\\\
\widetilde{\varepsilon}_{Y}\end{bmatrix}$ share the same distribution with

$\displaystyle{\mathbb{E}}\begin{bmatrix}\varepsilon^{\text{\scriptsize$(m)$}}_{X,\text{P}}\\\
\varepsilon^{\text{\scriptsize$(m)$}}_{X,\text{D}}\end{bmatrix}={\mathbb{E}}\begin{bmatrix}\widetilde{\varepsilon}_{X,\text{P}}\\\
\widetilde{\varepsilon}_{X,\text{D}}\end{bmatrix}=0,$
$\displaystyle\quad{\mathbb{E}}\left[\begin{bmatrix}\varepsilon^{\text{\scriptsize$(m)$}}_{X,\text{P}}\\\
\varepsilon^{\text{\scriptsize$(m)$}}_{X,\text{D}}\end{bmatrix}\begin{bmatrix}\varepsilon^{\text{\scriptsize$(m)$}}_{X,\text{P}}\\\
\varepsilon^{\text{\scriptsize$(m)$}}_{X,\text{D}}\end{bmatrix}^{\top}\right]={\mathbb{E}}\left[\begin{bmatrix}\widetilde{\varepsilon}_{X,\text{P}}\\\
\widetilde{\varepsilon}_{X,\text{D}}\end{bmatrix}\begin{bmatrix}\widetilde{\varepsilon}_{X,\text{P}}\\\
\widetilde{\varepsilon}_{X,\text{D}}\end{bmatrix}^{\top}\right]=\begin{bmatrix}\Sigma_{\text{P}}&0\\\
0&\Sigma_{\text{D}}\end{bmatrix},$
$\displaystyle{\mathbb{E}}\left[\varepsilon^{\text{\scriptsize$(1)$}}_{Y}\right]={\mathbb{E}}\left[\widetilde{\varepsilon}_{Y}\right]=0,$
$\displaystyle\quad{\mathbb{E}}\left[{\varepsilon^{\text{\scriptsize$(1)$}}_{Y}}^{2}\right]={\mathbb{E}}\left[{\widetilde{\varepsilon}_{Y}}^{2}\right]=\sigma^{2}.$

Additionally, the noise terms on $X$ and $Y$ are uncorrelated, namely,
${\mathbb{E}}\left[\varepsilon^{\text{\scriptsize$(m)$}}_{Y}\cdot\begin{bmatrix}\varepsilon^{\text{\scriptsize$(m)$}}_{X,\text{P}}\\\
\varepsilon^{\text{\scriptsize$(m)$}}_{X,\text{D}}\end{bmatrix}\right]={\mathbb{E}}\left[\widetilde{\varepsilon}_{Y}\cdot\begin{bmatrix}\widetilde{\varepsilon}_{X,\text{P}}\\\
\widetilde{\varepsilon}_{X,\text{D}}\end{bmatrix}\right]=0$.

Compared to the SCMs in Assumption 1 and 2, Assumption 3 introduces additional
covariates $X_{\text{P}}$ which are the parents of $Y$ or $X_{\text{D}}$ and
are located at the first $r$ coordinates. In the most general DA problem, this
information of which covariates are parents may not be available. The
information about causal relationships can be obtained for example from domain
experts or from the causal discovery literature. The causal discovery problem
is well studied and we refer the readers to Glymour et al. (2019) for a review
of the causal discovery methods. We leave the most general mixed-causal-
anticausal domain adaptation and the design of new DA methods to future work.

Based on Assumption 3, we can introduce the intermediate random variables

$\displaystyle X^{\text{\scriptsize$(m)$}}_{\mathcal{I}}$
$\displaystyle:=X^{\text{\scriptsize$(m)$}}_{\text{D}}-\left(\mathbb{I}_{d-r}-\mathbf{B}_{\text{D}}\right)^{-1}\mathbf{B}_{\text{D-P}}X^{\text{\scriptsize$(m)$}}_{\text{P}}-\left(\mathbb{I}_{d-r}-\mathbf{B}_{\text{D}}\right)^{-1}{b}_{\text{D}}{\omega}_{\text{P}}^{\top}X^{\text{\scriptsize$(m)$}}_{\text{P}}$
$\displaystyle Y^{\text{\scriptsize$(m)$}}_{\mathcal{I}}$
$\displaystyle:=Y^{\text{\scriptsize$(m)$}}-{\omega}_{\text{P}}^{\top}X^{\text{\scriptsize$(m)$}}_{\text{P}}$
$\displaystyle\widetilde{X}_{\mathcal{I}}$
$\displaystyle:=\widetilde{X}_{\text{D}}-\left(\mathbb{I}_{d-r}-\mathbf{B}_{\text{D}}\right)^{-1}\mathbf{B}_{\text{D-P}}\widetilde{X}_{\text{P}}-\left(\mathbb{I}_{d-r}-\mathbf{B}_{\text{D}}\right)^{-1}{b}_{\text{D}}{\omega}_{\text{P}}^{\top}\widetilde{X}_{\text{P}}$
$\displaystyle\widetilde{Y}_{\mathcal{I}}$
$\displaystyle:=\widetilde{Y}-{\omega}_{\text{P}}^{\top}\widetilde{X}_{\text{P}}.$
(37)

The intermediate random variable can be seen as the residuals after regressing
on the parent variables $X_{\text{P}}$. We observe that the intermediate
random variables satisfy the following SCMs

$\displaystyle\begin{bmatrix}X^{\text{\scriptsize$(m)$}}_{\mathcal{I}}\\\
Y^{\text{\scriptsize$(m)$}}_{\mathcal{I}}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\mathbf{B}_{\text{D}}&{b}_{\text{D}}\\\
0&0\end{bmatrix}\begin{bmatrix}X^{\text{\scriptsize$(m)$}}_{\mathcal{I}}\\\
Y^{\text{\scriptsize$(m)$}}_{\mathcal{I}}\end{bmatrix}+\begin{bmatrix}a^{\text{\scriptsize$(m)$}}_{X,\text{D}}\\\
a^{\text{\scriptsize$(m)$}}_{Y}\end{bmatrix}+\begin{bmatrix}\varepsilon^{\text{\scriptsize$(m)$}}_{X,\text{D}}\\\
\varepsilon^{\text{\scriptsize$(m)$}}_{Y}\end{bmatrix}$
$\displaystyle\begin{bmatrix}\widetilde{X}_{\mathcal{I}}\\\
\widetilde{Y}_{\mathcal{I}}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\mathbf{B}_{\text{D}}&{b}_{\text{D}}\\\
0&0\end{bmatrix}\begin{bmatrix}\widetilde{X}_{\mathcal{I}}\\\
\widetilde{Y}_{\mathcal{I}}\end{bmatrix}+\begin{bmatrix}\widetilde{a}_{X,\text{D}}\\\
\widetilde{a}_{Y}\end{bmatrix}+\begin{bmatrix}\widetilde{\varepsilon}_{X,\text{D}}\\\
\widetilde{\varepsilon}_{Y}\end{bmatrix}.$

Using the intermediate random variables
$(X^{\text{\scriptsize$(m)$}}_{\mathcal{I}},Y^{\text{\scriptsize$(m)$}}_{\mathcal{I}})$,
the mixed-causal-anticausal DA problem can be reduced to the anticausal DA
problem. Intuitively, it works as follows. First, regress $Y$ and
$X_{\text{D}}$ on the first $r$ covariates $X_{\text{P}}$. Second, create a
transformed dataset with new covariates and new labels from the corresponding
residuals like how we define the intermediate random variables. Third, apply
the DA methods in the anticausal DA setting to the transformed dataset.
Finally, bring back the original covariates and labels in the final estimator.

Based on the above intuition, we introduce the following estimators for the
mixed-causal-anticausal DA setting.

  * •

DIP$\diamondsuit^{\text{\scriptsize$(m)$}}$-mean: the population domain
invariant projection estimator for the mixed-causal-anticausal DA setting.

$\displaystyle f_{\text{DIP}\diamondsuit}^{\text{\scriptsize$(m)$}}(x)$
$\displaystyle:=x^{\top}\begin{bmatrix}\gamma^{\text{\scriptsize$(m)$}}-\Gamma^{\text{\scriptsize$(m)$}}\beta_{\text{DIP}\diamondsuit}^{\text{\scriptsize$(m)$}}\\\
\beta_{\text{DIP}\diamondsuit}^{\text{\scriptsize$(m)$}}\end{bmatrix}+\beta_{\text{DIP}\diamondsuit,0}^{\text{\scriptsize$(m)$}}$
$\displaystyle\beta_{\text{DIP}\diamondsuit}^{\text{\scriptsize$(m)$}},\beta_{\text{DIP}\diamondsuit,0}^{\text{\scriptsize$(m)$}}$
$\displaystyle:=\operatorname*{arg\,min}_{\beta,\beta_{0}}\
{\mathbb{E}}_{(X_{\text{P}},X_{\text{D}},Y)\sim\mathcal{P}^{\text{\scriptsize$(m)$}}}\left(Y_{\mathcal{I}}-X_{\mathcal{I}}^{\top}\beta-\beta_{0}\right)^{2}$
$\displaystyle\text{s.t.\
}{\mathbb{E}}_{\left(X_{\text{P}},X_{\text{D}}\right)\sim\mathcal{P}^{\text{\scriptsize$(m)$}}_{X}}\left[X_{\mathcal{I}}^{\top}\beta\right]={\mathbb{E}}_{\left(X_{\text{P}},X_{\text{D}}\right)\sim\widetilde{\mathcal{P}}_{X}}\left[X_{\mathcal{I}}^{\top}\beta\right],$
(38)

where
$Y_{\mathcal{I}}:=Y-X_{\text{P}}^{\top}\gamma^{\text{\scriptsize$(m)$}}$,
$X_{\mathcal{I}}:=X_{\text{D}}-{\Gamma^{\text{\scriptsize$(m)$}}}^{\top}X_{\text{P}}$,
and the regression weights $\gamma^{\text{\scriptsize$(m)$}}$ and
$\Gamma^{\text{\scriptsize$(m)$}}$ are defined as

$\displaystyle\gamma^{\text{\scriptsize$(m)$}},\gamma_{0}^{\text{\scriptsize$(m)$}}$
$\displaystyle:=\operatorname*{arg\,min}_{\gamma,\gamma_{0}\in^{r}\times}{\mathbb{E}}_{\left(X_{\text{P}},X_{\text{D}},Y\right)\sim\mathcal{P}^{\text{\scriptsize$(m)$}}}\left(Y-X_{\text{P}}^{\top}\gamma-\gamma_{0}\right)^{2},$
(39)
$\displaystyle\Gamma^{\text{\scriptsize$(m)$}},\Gamma_{0}^{\text{\scriptsize$(m)$}}$
$\displaystyle:=\operatorname*{arg\,min}_{\Gamma,\Gamma_{0}\in^{r\times(d-r)}\times^{d-r}}{\mathbb{E}}_{\left(X_{\text{P}},X_{\text{D}}\right)\sim\mathcal{P}^{\text{\scriptsize$(m)$}}_{X}}\left\|X_{\text{D}}-\Gamma^{\top}X_{\text{P}}-\Gamma_{0}\right\|_{2}^{2}.$
(40)

###### Corollary 7

Under the data generation Assumption 3, $M=1$ and the assumption of no
intervention on $Y$ i.e.
$a^{\text{\scriptsize$(1)$}}_{Y}=\widetilde{a}_{Y}=0$, the target population
risks of OLSTar and DIP$\diamondsuit^{\text{\scriptsize$(1)$}}$-mean satisfy

$\displaystyle\tilde{R}\left(f_{\text{OLSTar}}\right)$
$\displaystyle=\frac{\sigma^{2}}{1+\sigma^{2}{b}_{\text{D}}^{\top}\Sigma_{\text{D}}^{-1}{b}_{\text{D}}},$
(41)
$\displaystyle\tilde{R}\left(f_{\text{DIP}\diamondsuit}^{\text{\scriptsize$(1)$}}\right)$
$\displaystyle=\frac{\sigma^{2}}{1+\sigma^{2}{b}_{\text{D}}^{\top}\Sigma_{\text{D}}^{-\frac{1}{2}}{G_{\text{\tiny$\text{DIP}\diamondsuit$}}^{\text{\scriptsize$(1)$}}}\Sigma_{\text{D}}^{-\frac{1}{2}}{b}_{\text{D}}},$
(42)

where ${G_{\text{\tiny$\text{DIP}\diamondsuit$}}^{\text{\scriptsize$(1)$}}}$
is a projection matrix with rank $d-1$.

The proof of Corollary 7 is provided in Appendix C.4. The target risk results
in Corollary 7 is very similar to those in Theorem 1. This is because we
reduce the mixed-causal-anticausal DA problem without intervention on $Y$
under Assumption 3 to the anticausal DA problem without intervention on $Y$
under Assumption 1. According to Equation (42), the target population risk of
DIP$\diamondsuit^{\text{\scriptsize$(1)$}}$ is lower than the target risk of
Causal (which equals to $\sigma^{2}$).

Based on the intuition of DIP$\diamondsuit$, a similar strategy can be applied
to extend CIP and CIRM to the mixed-causal-anticausal DA problems. The precise
formulations of the extensions CIP$\diamondsuit$ and CIRM$\diamondsuit$ are
introduced in Appendix A.1.

Just as Corollary 7 serves as the equivalent of Theorem 1 in the mixed-causal-
anticausal DA setting, the equivalent of Theorem 5 can be established for
CIP$\diamondsuit$ and CIRM$\diamondsuit$. Additionally, we can also introduce
the weighted version of CIRM$\diamondsuit$, called CIRM$\diamondsuit$weigh,
following the discussion of CIRMweigh. The details are omitted.

##  5 Numerical experiments

In this section, we numerically compare DA methods in simulated, synthetic and
real datasets. The experiments are used to validate our theoretical results in
finite sample data, to illustrate DA failure modes when assumptions are
violated and to provide ideas of adapting DA methods to scenarios where not
all assumptions are satisfied. Section 5.1 formulates the finite-sample DA
estimators from the population DA ones to make sure our implementations are
reproducible. Section 5.2 contains simulation experiments from deterministic
or randomly generated linear SCMs. Section 5.3 discusses the performance of DA
estimators on the MNIST dataset with synthetic interventions. Finally, Section
5.4 illustrates through a real data experiment that DA can be difficult in
practice when not much domain knowledge about the data generating model is
available.

Our code to reproduce all the numerical experiments is publicly available in
the Github repository https://github.com/yuachen/CausalDA.

###  5.1 Finite-sample formulations and hyperparameter choices

Here we introduce the regularized formulations of the finite-sample DIP, CIP
and CIRM. The DIP matching penalty in Equation (• ‣ 3.4) and the conditional
invariance penalty in Equation (• ‣ 3.4) are enforced via regularization
terms. The finite-sample versions of their variants can be formulated
similarly after translating the constraints to regularization terms. For the
sake of space, they are presented in Appendix A.2.

  * •

DIP${}^{\text{\scriptsize$(m)$}}$-mean-finite: the finite-sample formulation
of the DIP${}^{\text{\scriptsize$(m)$}}$-mean estimator (• ‣ 3.4). The mean
squared difference is used as distributional distance and is enforced via a
regularization term,