Partial Transportability for Domain Generalization
Authors: Kasra Jalaldoust
Alexis Bellot
Elias Bareinboim
Venue: NeurIPS 2024 poster (2024)
Keywords: Causal inference
Domain generalization
Transportability
Primary area: causal_inference
TL;DR: A causal perspective on bounding worst-case risk of classifiers for domain generalization.

Abstract: A fundamental task in AI is providing performance guarantees for predictions made in unseen domains. In practice, there can be substantial uncertainty about the distribution of new data, and corresponding variability in the performance of existing predictors. Building on the theory of partial identification and transportability, this paper introduces new results for bounding the value of a functional of the target distribution, such as the generalization error of a classifiers, given data from source domains and assumptions about the data generating mechanisms, encoded in causal diagrams. Our contribution is to provide the first general estimation technique for transportability problems, adapting existing parameterization schemes such Neural Causal Models to encode the structural constraints necessary for cross-population inference. We demonstrate the expressiveness and consistency of this procedure and further propose a gradient-based optimization scheme for making scalable inferences in practice. Our results are corroborated with experiments.

Partial Transportability for Domain Generalization
Kasra Jalaldoust R
Alexis B
Elias Bareinboim
Causal Artificial Intelligence Lab
Columbia University
abeliot950gmail (kasra, eb) (css www.mbia..da...
Abstract
A fundamental task in Al is providing performance guarantees for predictions made in unseen domains. In practice, there can be substantial uncertainty about the dis- tribution of new data, and corresponding variability the performance of existing predictors. Building on the theory of partial identification and transportability. this paper introduces new results for bounding the value a functional of the target distribution, such the generalization error of classifier, given data from source domains and assumptions about the data generating mechanisms, encoded in causal diagrams. Our contribution is to provide the first general estimation technique for transportability problems, adapting existing parameterization schemes such Neural Causal Models to encode the structural constraints necessary for cross-populs pross-populttion inference. We demonstrate the expressiveness and consistency of this procedure and further propose a gradient-based optimization scheme for making scalable inferences in practice. Our results are corroborated with experiments.
Introduction
In the empirical sciences, the value scientific theories arguably depends on their ability to make predictions in a domain different from where the theory was initially learned. Understanding when and how a conclusion in one domain, such as statistical association, can be generalized unseen domain has taken fundamental role in the philosophy of biological and social sciences in the early 21st century. As Campbell and Stanley [8, p. 17] observed in an early discussion on the interpretation of statistical inferences, "Generalization always turns out to involve generalization into a realm not represented in one's sample" where, in particular, statistical associations and distributions might differ, presenting fundamental challenge.
novel,
As society transitions to become are increasingly delegated to automated systems. Such developments make various parts of society more efficient, but also require a notion of performance guarantee that is critical for the safety of AI, in which the problem of generalization appears under different forms. For instance, one critical task the field is domain generalization, where one tries to learn a model (e.g. classifier, regressor) on data sampled from distribution that differs in several aspects from that expected when deploying the model in practice. this context, generalization guarantees must build on knowledge or assumptions on the "relatedness" of different training and testing domains; for instance, if training and testing domains are arbitrarily different, no generalization guarantees can be expected from any predictor [12, 40). The question becomes how to link the domains of data that are used to train a model (a.k.a., the source domains) to the domain where this model is deployed in practice (a. the target domain).
Al centric, many of the every-day tasks based predictions
* "Equal Contribution.
Now at Google DeepMind.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Source domains M M.M
Target domaln M
Selection diagram g
Uwr
Uwy
W
Uwr
W
D N pl D' pa
D = Ø
Given D', D and ø+ Rp-(A))= =?
Figure I: Illustration of the task of evaluating the generalization error of model h. The mechanisms for C' and W vary across domains.
To begin answer this question, a popular type of assumption that relates source and target domains is statistical in nature: invariances in the marginal or conditional distribution of some variables across the source and target distributions. Examples include assumptions of covariate shift and label shift (among others) [35, 34]. Notably, generalization is justified by the stability and invariance of the causal mechanisms shared across the domains [14, 21], since the diistibbutional/ssaaitttee invariances across the domains are consequences of mechanistic/structuur invariances governing the underlying data generating process. Although the induced statistical invariances, once exploited correctly, can be used as bases for generalizability. Broadly, invariance- approaches to domain generalization [27, 29, 2, 40, 24, 20, 7, 6, 13] search for predictors that not only achieves small error on the source data but also maintain certain notions of distributional invariance across the source domains. Since these statistical invariances can be viewed as proxies to structural invariances, in certain instances generalization guarantees can be provided through causal reasoning [17, 31, 39]. This idea can be illustrated in Fig. 1. The value of variables {C, Y, W, 2) are determined as a stochastic function of variables pointing to it, while these functions may differ across domains. The challenge is to evaluate the generalization risk of a model, e.g. Rp (h) := Ep. - =]] for h := f(C, W, Z) Ep! [Y C, W. ZJ, without observations from the target Pa General instances of this challenge have been studied under the rubric of the theory of causal transportability, where qualitative assumptions regarding the underlying structural causal models are encoded in a graphical object, and algorithms are designed to leverage these assumptions and compute certain statistical queries in the target domain in terms of the existing source data [26, 4. 5, 19, 11, 17].
Despite these advances, in practice, the combination of souree data and graphical assumptions is not always sufficient to identify (uniquely evaluate) the desired statistical query, e.g., the average loss of given predictor in the target domain. In this case, the query said be non-transportable" For example, given Fig. 1, Rps (h) is non-transportable for the classifier h := hCC, W, 2). In this paper, we study the fundamental task of computing tight upper-bounds for statistical queries in a new unseen domain. This allows us to assess worst-case performance of prediction models for the domain generalization task. Our contributions are as follows:
Sections 2 & 3. We develop the first general estimation technique for bounding the value of queries across multiple domains (e.g., the generalization risk) in non-transportable settings (Def. 4). Specifically, extend the formulation of canonical models [3, 42] to encode the constraints necessary for solving the transportability task, and demonstrate their expressiveness for generating distributions entailed by the underlying Structural Causal Models (SCMs) (Thm. 1).
We adapt Neural Causal Models (NCMs) [41] for the transportabilityy task via parameter sharing scheme (Thm. 2), similarly demonstrating their expressiveness and consistency for solving the partial transportability task. We then leverage the theoretical findings in sections 2 & 3 to implement a gradient-bast based optimization algorithm for making scalable inferences (Alg. 1), as well as Bayesian inference procedure. Finally, we introduce Causal Robust Optimization (CRO) (Alg. 2), an iterative method to find a predictor with the best worst-case risk.
Section 4.
Preliminaries. We use capital letters to denote variables (X), small letters for their values (x), bold letters for sets of variables (X) and their values (x), and use supp to denote their domains of definition (z s.ppx). A conditional independence statement in distribution P is written as (XJLY Z.p. A d-separation statement in some graph g is written as (X Z). To denote P(Y = y X æz), relies on Structural Causal Models (SCMs) [25, Definition 7.1.1], which are defined below.
the shorthand p(y x)) The basic semantic framework of our analysis
'The notion of non- con-trasspottabliiyy formalizes a type of aleatoric uncertainty [16] arising from the inherent variability within compatible data generating systems for the target domain. In particular, it cannot be explained away with increasing sample size from the source domains.

---

Definition 1. An SCM M is = FV. where each observed variable V E V is a deterministic function of subset of variables Pay C VV and latent variables Uv U. i.e. e : Jv (ppa,, uy); Jv F. Each latent variable U U is distributed according to probability measure P(u). We assume the model to be recursive, i.. that there are no cyclic dependencies among the variables.
SCM M entails probability distribution (M(v) over the set of observed variables V such that [v] pav, uv) ). P(u)) du,
(M SupPu VeV
IT
where the term P(u pay, uy) corresponds to the function fv E F in the underlying structural causal model M. It also induces a causal diagram GM in which each V e V is associated with vertex, and we draw a directed edge between two variables Vú - Vi if Vi appears as an argument of fv, in the SCM, and bi-directed edge V Vj Uv, n Uv, * Ø. that is Vú and V, share an unobserved confounder. Throughout this paper, we assume the observational distributions entailed by the SCMs satisfy the positivity assumption, that is, PM (v) O, for every v. We will also operate non-parametrically, i.e., making no assumption about the particular functional form or the distribution of the unobserved variables.
2 Risk Evaluation through Partial Transportability
In this section, we focus on challenges of the domain generalization problem through a causal lens, in particular regarding assessment of average loss of a given classifier in the target domain. We study system of variables V where Y V is categorical outcome variable and consider classifier h suppx - suppy mapping a set of covariates X
the domain of the outcome. The setting of domain generalization is characterized by multiple domains, defined by SCMs M MM. .M*) that entail distributions P (PM ..... pM' and p.M over V. We are given a classifier h : suppx - suppy, and the objective is to evaluate its risk in the domain M which is defined as,
Rp (h) = Eps [C(Y,
where L suppy suppy - R+ a loss function. The following example illustrates these notions. Example (Covariate shift). A common instance of the domain generalization problem considers source and target domains M. : {M 3² over V (X,Y) and (Ux, Uv defined by
X - (Ux)
X xx (Ux) Y (x,,U)
F*
M'
Y - fr Uy)
M
PL(U) (UX) P(Uv)
ps (U) P(Uy)
Here, because (UXxx) * px) this implies via Eq. that the covariate distributions are different, i.e., (1X * (x). Still, the label distribution conditional on covariates is invariant, i.e, PY X) = (* X), also known as the covariate shift setting. Accordingly, the risk of classifier h = h(x) can be written as
Cly, h(x)) p* (y, x)) dyda S (ly,)(z)) ( P*()))
Rp* (h) =
dydæ.
(3)
suppy xsuppx
suppy xsupXx
We will consider the problem of quantifying the variation in Rp* (h) subject to variation in pa that would be consistent with partial observations from these domains, e.g. samples from PI( X Y). and assumptions about the commonalities and discrepancies across the domains.
To describe more general discrepancies in the mechanisms between the SCMs, we adapt the notion of domain discrepancy and selection diagram introduced in [19].
Definition 2 (Domain discrepancy). For SCMs M', MD (i,j E (,,
defined over V. the domain discrepancy set Aij S V is defined such that for every V e Aij there might exist discrepancy fM # fMM' or PM' (uv) * PMM (uv). For abbreviation, we denote Ais as A. O
In words, an endogenous variable V is not A.j. this means that the mechanism for V (i.e., the function fv and the distribution of exogenous variables P(uv)) are structurally invariant across M MS. What follows integrates the domain discrepancy sets into generalization of causal diagrams to express gualitative assumptions about multiple SCMs [26, 11].
3

---

Definition 3 (Selection diagram). The selection diagram G is constructed from G' (i (1.2..... by adding the selection node S; the vertex set, and adding the edge S, V for every V E A, The collection G (g* [ ie..,......TT encodes the graphical assumptions. Whenever the causal diagram is shared across the domains, single diagram can depict go. O
Selection diagrams extend causal diagrams and provide a parsimonious graphical representation of the commonalities and disparities across a collection of SCMs. The following example illustrates these notions and highlights various subtleties in the generalization error of different predictors.
Example 2 (Generalization performance of classifiers), Consider the SCMs .M' (i (1, +)) over the binary variables X {C1, C2 (W: 2) and Y, defined as follows:
V1 E j & 10: Uc,- ~ (ern(0.1) if = Bern(0.5) if = 2 Bern(0.7) 7. if Uyw (0.)
PI(U):
Uw ~ (orn(0.01)) if 1 Bern(0.02) if (0.)( if =
Uz ~ Bern(0.9)
F Uc. Y - Uyw + ① C, W - Urw OUw, Z - Y Uz + W (1- (1-UU) Uz)
CEC
+ denotes the xor operator, i.e. A ① B evaluates to 1 if A * B and evaluates to 0 if A = B. Notice that the distribution of exogenous noise associated with C1.10 and {W} differs across the domains.
Consider three baseline classifiers h2 (c. w) == w @ Dree c, h2(c) == + cEC C. hz(2) = 2 evaluated on data from PL p2 pa with the symmetric loss function C(Y, h(X)) = 1(Y * h(x)). Their errors are given in Table 1. Notice that h1 has almost perfect accuracy on both source distributions, but does not generalize to .M' as it uses the unstable feature W. incurring 50% loss. This observation indicates that mere minimization of the empirical risk might yield arbitrarily large risk in the unseen target domain. h2 uses the features C' that are the direct causes of Y, also known as the causal predictor [27, 2]. and yields a stable loss of 20% across all domains. On the other hand, h3 uses only Z that is a descendant of Y, yet achieves a small loss across all domains as the mechanism of Z is assumed to be invariant. This observation is surprising, because h3 is neither a causal predictor nor the minimizer of the empirical risk, yet it performs nearly optimally on all domains.
Example 2 illustrates potential challenges of the do- main generalization problem, particularly regarding the variation of the risk of classifiers across the source and target domains. The following definition intro- duces the problem of "partial transportability" which is the main conceptual contribution of our paper. The objective is bounding a statistic of the target distribu- tion using the data and assumptions available about related domains.
Classifier
Rpm
R Rpm2
R Pps*
wi) hz(c) hg(2)
1%
4%
49%
20%
20%
20%
3%
5%
4%
Table 1: Classifiers in Example 2.
Definition 4 (Partial Transportability). Consider a system of SCMs MI AMM .M?.....M .M' that induces the selection diagram g over the variables V and entails the distributions IP {PI(w. (v). (P(()) (n)) and pa (v). A functional t/ Ωy - IR is partially transportable from given Gà if,
IE MM L6 (V)]
& 4max, V SCMs Ml, that entail IP and induce A
(4)
where Gmax E IR. is constant that can be obtained from P given gA.
For instance, finding the worst-case performance of classifier based on the source distributions given the selection diagram a special case partial transportability with (xx y) := Cly. h(x)). In principle, this task is challenging as the exogenous distribution p* (Uv) and structural assignments It of variables V e V that do not match with any of the source domains could be arbitrary. In the following section, we will define tractable parameterization of (P(U),F) to derive systematic approach to solving partial transportability tasks.
3 Canonical Models for Partial Transportability
We begin with an example to illustrate how one might approach parameterizing query such as p [sb( [V]],, e.g., the generalization error, to consistently solve the partial transportability task.

---

Example 3 (The bow model), Let x= {X] Consider two source domains defined by the following SCMs:
:=
be a single binary variable, and Y be a binary label.
Ux Bern(0.2)
Ux Bern(0.9)
PI(U):
: Uy ~ Bern(0. 0.05)
P?(
Uy ~ Bern(0.05)
M
Uxy (orm(0.95)
MR
UXy ~ (0rn(0.955
Fl: X Ux @Uxy
X Ux @ UXy
F²
Y (X + Uxx) @y
Y (X (xx) Uy
The task is to evaluate the generalization error of the classifier h(z) -. h can be shown optimal in both source domains: achieving Rp (h) > 0.11 and (h) a 0.06. However, is unclear whether it generalizes well to target domain M given the domain discrepancy sets A (X), A2 (Y).
UKY
Balke and Pearl [3] derived canonical parameteri- zation of SCMs such as ,M, _M) in Exam- ple 3. They showed that it is sufficient to parame- terize P(U) with correlated discrete latent variables Rx. Ry, where Rx determines the value of X, and Ry determines the functional that decides Y based on X. The causal diagrams are shown in Figure 2. Canonical SCMs entails the same set of distributions as the true underlying SCMs, i.e. are equally expressive. In particular, Zhang and Bareinboim [42] showed that for every SCM M, there exists an SCM of the described form specified with only a distribution P(rx, Ty), where, supPR, {0. 1}, supPR, {y = 0. y 1, 2, y -r}. The joint distribution P(rx, ry) can be parameterized by vector in 8- 8-dimensional simplex, and entails all observational, interven- tional and counterfactual variables generated by the original SCM.
Uy
Uv
Rx
(a) 9
(b) gMV
Figure 2: Selection diagram & Canonical param.
The following definition by Zhang et al. [42] provides a general formulation of canonical models.
Definition 5 (Canonical SCM). A canonical SCM is an SCM N {U, V. F(,))() defined as follows. The set of endogenous variables V is discrete. The set of exogenous variables U = {Ry V V), where supPRy = (I....: my) and my = [[hv supPpav suppy J. For each V V, fv E F is defined as (p( = h1rr) (pay).
Example 3 (continued). Consider extending the canonical parameterization to solve the partial transportability task by optimization. Each SCM M M'M ,MM,, is associated with a canonical SCM N',2² //* with exogenous variables ( Rxx, Ry } as above. The domain discrepancy sets A indicate that certain causal mechanisms need to match across pairs of the SCMs. For example, A = (X), which does not contain Y, and this means that (1) the function fy is the same across M' and (2) the distribution of unobserved variables that are arguments of fr, namely, Uxy: Uy remains the same across M M Imposing these equalities
the canonical parameterization is straightforward as (I) the function fy is the same across all canonical SCMs by construction, and (2) the only unobserved variable pointing to variable V is Ry (for V (X, Y)). Following the selection diagram shown in Fig. 2a, M MM agree on the mechanism of Y, which translates to the constraint p.V" (ry) P.** (ry). Similarly, M2,M* agree on the mechanism of X that translates to the constraint pv² (rx) p.**(x=))) (rx). Putting these together, the optimization problem below finds the upper-bound for the risk Rps (h) for the classifier h(x) = =2
PVV (Y * -X)
max NY.""
s.t. PM (ry) = pM* (ry), pa (rx) pat (rx)
(Y $ Ar, and X A2) (matching source dists)
pN (x, v) = P', pv pV P((x,)
Notably, the above optimization has linear objective with linear equality constraints.
This example illustrates more general strategy, in which probabilities induced by an SCM over discrete endogenous variables V may be generated by canonical model. What follows is the main result this section, and provides a systematic approach to partial transportability using the canonical models.
5

---

Theorem 1 (Partial- TR with canonical models), Consider the tuple of SCMs M. that induces the selection diagram G over the variables V, and entails the source distributions P. and the target distribution P*. Let 1p fty - T be functional of interest. Consider the following optimization
scheme:
max
E pawe [b)(V]
pa ( (p)
Vi (1,2,.... K₂+}
(6)
NO , N'
pr p PN' (rv), Vi,j f1.2....,K, VV
where each N is canonical model characterized by joint distribution over Ry Rvev.. The value of the above optimization is a tight upper-bound for the quantity [p*[v(V (V) among all tuples of SCMs that induce G and entail I..
In words, this Theorem states that one may tightly bound the value of target quantity Eps [ (V) by optimizing over the space of canonical models subject to the proposed constraints, without any loss of information. An implementation of Thm. approximating the worst-case error, by making inference on the posterior distribution of the target quantity, is provided in Appendix A.
4 Neural Causal Models for Partial Transportability
In this section we consider inferences in more general settings by using neural networks as a generative model, acting as a proxy for the underlying SCMs M with the potential scale to real-world, high- nigh-dimensional settings while preserving the validity and tightness of bounds. For this purpose, consider Neural Causal Models [41] and adapt them for the partial transportabillty task. What follows is instantiation of [41, Definition 7].
U
W
W:
W.
Definition 6 (Neural Causal Model). A Neural Causal Model (NCM) corresponding to the causal diagram g over the discrete variables V is is an SCM defined by the exogenous variables:
Figure Selection diagram for Example 4.
(7) and the functional assignments V < fov (avr, Uv), where Uv = (Uw E U : VE W). The function for is feed-forward neural network parameterized with By that outputs in suppy- The distribution entailed by an NCM is denoted by P(D: 0), where 0 = [dv]vev.
U (Uw un) W = V s.t. A BEG, BA,BeW).
To illustrate how one might leverage this parameterization to define an instance of partial transporta- bility task consider the following example.
Example 4. Let SCMs M'MM .M2.M .M induce G shown in Fig. 3 over the binary variables X, Y, where X {C1. C2 Z1, Zz, Wi...., ... Ws). Let 01, ,8, 8* be the parameters of NCMs constructed based on the causal diagram in Fig. 3 (without the s-nodes). The objective is to constrain these parameters simulate a compatible tuple of NCMs Maa that equivalently entail v), (2x, y) and induce ga.
0,820*
Pl (1(x,, (x,,))
For instance, the fact that S2 is not pointing Y suggests the invariance f f6 and p* (uy) pa ("(y)) for the true underlying SCMs. That same invariance may be enforced in the corresponding NCMs by relating the parameterization of M i.e., imposing that 67 B2 for the NN generating Y. Similarly, the observed data D1 22 from the source distributions pl (ar, y). P² y), respectively, impose constraints on the parameterization of NCMs as plausible models must satisfy P(x, y; 0²) = pl (x, y) and P(æ, y, 62) = (x, y). This may be enforced, for instance, by maxi- mizing the likelihood of data w.r.t. the NCM parameters: 0¹ arg max, Ex.yED log P(x, y 0'), for i 21, By extending this intuition for all constraints imposed by the selection diagram and data, we narrow the set NCMs Mgr MM2,.Ma to a set that is compatible with our assumptions and data. Maximizing the risk of some prediction function Rp (h) in this class of constrained NCMs might then achieve an informative bound.
Motivated by the observation in Example 4, we now show a more formal result (analogous to Thm. 1) that guarantees that the solution to the partial transportability task in the space of constrained NCMs achieves a tight bound given target quantity Ep (p=[<((V))

---

Theorem 2 (Partial-TR with NCMs). Consider tuple of SCMs M. that induces G P and P over the variables V. Let D' (z, y) denote the samples drawn from the i-th source domain. Let o denote the parameters of NCM corresponding to M E M. Let R [p((y((V))))))) be the target quantity. The solution to the optimization problem,
aig max @ 62
Σ ((()) Σ
P(((00)) vie0
(8)
8 .88
S.I. By = By,
Vi,j E
V Aij log P():0), Vie (1, K}.
0 arg max Σ
VED*
a tuple of NCMs that induce g entails P. In the large sample limit, the solution yields a tight upper-bound for Ep [ [.
Theorem establishes the expressive power of NCMs for solving partial transportability tasks. This formulation is powerful because it enables the use of gradient-base -ased optimization of neural networks for learning and, in principle, might scale to large number of variables.
4.1 Neural-TR: An Efficient Implementation
We could further explore the efficient optimization of parameters by exploiting the separation between variables in the selection diagram. Rahman al. [28], for instance, show that the NCM parameterization is modular w.r.t. the c-components of the causal diagram. We can similarly elaborate on this property, and leverage it for more efficient partial transportability.
In the following, we build towards an efficient algorithm for partial transportability using NCMs by first showing example that describes how given target quantity Ess (V)] might be decomposed for learning more efficiently.
Example 4 (continued). P(æ, yi 0*) in the objective in Eq. (8) may be decomposed as follows:
P(x, y: 8*) = p* (c1, C22 W1, Wz2; ) P( y. W/3
C22 Wy ( P( 22, W4, Ws
y. W3
a1
b9
bg
where the subsets A1, A2, Ag are the c-components of g*. Notice, S2 is not pointing to any of the variables A2, which means that their mechanism is shared across
and therefore,
P(az by; 0%,) = P(a. by; (22,) ~ p² b2).
(9)
This property is the basis of transportability algorithms [4. 10], and known as the s-admissibility criterion [26], which allows us to deduce distributional invariances from structural invariances. By Eq. (9), we can replace the term P(az b2; 0%,) in the objective with the probabilistic model
P(a2 b2; that is trained with D2 to approximate p² b2) and plug it into the objective Eq. (8) as a constant.
As a consequence, we do not need optimize over the parameters 02 02 2,,00 transportability optimization problem. Similarly, since S₁ does not point to A1, we can substitute P(a;; 6*) with ((a1:1"). and pre-train with data D In the context of Example 4 and the evalua- tion of Rp (h), the objective in Eq. (8) may be simplified to the substantially lighter optimization task:
0* Aa from the partial
max
EAI-P(asn (E [Ag 2)
P(as by: 0%,0% 1(h(a1, a2, as}(v)) # vi]]
O2y 0 8+ As
ag
s.t. 0% E arg max
Σ Di
log P(as OA,), forie (1,2).
(10)
BA
In general, the parameter space of NCMs can be cleverly decoupled and the computational cost of the optimization problem can be significantly improved since only a subset of the conditional distributions need to be parameterized and optimized. This observation motivates Alg. 1 designed to exploit these insights. It proceeds by first, decomposing the query, second, computing the identifiable components, and third, parameterizing the components that are not point identifiable and running the NCM optimization routine. The following proposition demonstrates the correctness of this procedure.
7

---

Algorithm 1 Neural-TR
Require: Source data DJ, D2 ..... DK; selection diagram G functional dp fww [0. 1].
Ensure: Upper-bound for Ep [xb( [)]
{A,])= + c-components of A == Ang* * (W) in causal diagram g
2: 6 Cexpen + Ø
Ldaa 0
3: P*(w) := Emy,
1-11 PM(a, do(pa A))))
4: for j = to m do
5: if di E 21, K such that A, n Dei Ø then
6: V'A, arg max naj E Laj,pen, ED log P(a; (o(ppa,):11)
7:
p* (ww),, replace (* do(pa A,)) with P(aj do(pa A, ):A,))
8:
else
9:
a ( (i.............) K..)
In P*(w), p* (aj do( da(pa, A with Pla,do(po po A, A,
11:
Cexpent - Cexpen U 1100 = 0 VEA, /
12: Likelihood Liikelibood + Eaj,po a. EDi log P(aj, (a pa A, 0;)))))
13:
end if
14:
end for
15:
Return Ô arg maxe En, Pa (s:; θ) (w) A Likelihood ( subject to Cexpert
Proposition 1. Neural-TR (Algorithm 1) computes a tuple of NCMs compatible with the source data and graphical assumptions that yields the upper-bound for Eps [+) [W) in the large sample limit. O
This result may be understood as enhancement of Thm. 2 in which the factors that readily transportable from source data are taken care of in a pre- preeerocessing step. The hybrid approach is especially useful in case researchers have pre-trained probabilistic models with arbitrary architecture that they can use aff-the-shell and avoid unnecessary computation.
4.2 Neural-TR for the Optimization of Classifiers
The Neural-TR algorithm can be viewed as an adversarial domain generator that takes a classifier h(2) as the input, and then parameterizes collection of SCMs to find plausible target domain that yields the worst-case risk for the given classifier, namely, 0=, By flipping h(z) for some z we can reduce the risk of h under 6+
Interestingly, we can exploit Neural-TR to generate adversarial data for a given clas- sifier and introduce iterative procedure to progressively train classifiers with with minimum risk upper-bound. Algorithm 2 describes this approach. At each iteration, CRO uses Neural-TR as subroutine to ob- tain an adversarially designed NCM 6 that yields the worst-case risk for the classifier at hand. Next, it collects data D* from this NCM and adds it collection of datasets DR Finally, it updates the classifier to be robust to the collection ID* by minimizing the maximum of the empirical risk Rn(h)= : > VD Cly, h((z)) across all D E D We repeat this process until convergence of the upper-bound for risk. The following result justifies optimality of CRO for domain generalization; more discussion is provided in Appendix C.2.
Algorithm CRO (Causal Robust Optimization)
Require: IB : <D' D D*); g 5 >>> 0
Ensure: (X) with the best worst-case risk.
Initialize h randomly and ID* Ø
Ô Neural-TR(ID, ف vb L(h(x), v))
3: while R R(..,g0 (h) maxx Rp(h) > 8 do
4:
I - D U{D* ~ P(æ, y; 0z)²}}
h arg min, max RD(h)
6:
Neural-TR(D, A .b: ((h(())))))
7: end while
8: Return
Theorem (Domain generalization with CRO). Algorithm returns a worst-cuse optimal solution;
CRO(D,,C A arg min
max
R Rescy (h).
(11)
1:90x tuple of SCMs Me that entoils & induces ga
In words, Thm. 3 states that the classifier returned by CRO, in the large sample limit, minimizes worst-case risk in the target domain subject to the constraints entailed by the available data and induced by the structural assumptions.

---

N,00
8,00
Ng00
36
15 Thaiigg spocre Prousd
Turinn spoote (ooaa (1)
Traning sporte Jrossl trt
Thaking spochs Oluars
(a) Example 2
(b) Example 3
(c) CMNIST
(d) Example 2
(c) Example 3
Figure 4: (a-c): worst-case risk evaluation results as a function of Neural-TR (Alg. 1) training iterations. (d,e): worst-case risk evaluation of CRO.
5
Experiments
This section illustrates Algs. I and 2 for the evaluation and optimization of the generalization error on several tasks, ranging from simulated examples to semi-synthetic image datasets, The details of the experimental set-up and examples not fully described below, along with additional experiments, can be found in the Appendix.
5.1 Simulations
Worst-case risk evaluation Our first experiment revisits Examples 2 and 3 for the evaluation of the worst-case risk Rp* of various classifiers with Neural-TR (Alg. 1).
In Example we had made (anecdotal) performance observations for the classifiers hi w) := in selected target domain _M". We now consider providing a worst-case risk guarantee with Neural-TR for any (compatible) target domain. The main panel in Fig. 4a shows the convergence of the worst-case risk evaluator iterations (line 15, Alg. 1), repeated 10 times with different model seeds and solid lines denoting the mean worst-case risk. The source performances Rp. Rp, are given in the two right-most panels for reference. We observe that the good source performance of h2(c) and hz(z) generalizes to all possible target domains consistent with our assumptions, while the classifier (c, w) diverges, with an error of 90% in the worst target domain. In Example 3, we consider the evaluation of binary classifiers h E (h1(x) := z, (2(2) == =z, hag (x) O, h4(x) == 1}. h2(x)) =z. Our results are given in Fig. 4b, highlighting the extent to which source performance need not be indicative of target performance. With these results, we are now in a position confirm the desirable performance profile of h22 even in the worst-case, as hypothesized in Example 3.
@ Droe h2(c)) := Dee (2))
successive training
Worst-case risk optimization For each one of the examples above, we implement CRO (Alg. 2) to uncover the theoretically optimal classifier in the worst-case. The worst-case risks of the classifiers learned by CRO, denoted liçRo. are given by 0.05 for Example 2 and 0.18 for Example 3. The worst-case risk evaluation results (with Neural-TR, as above) are given in Figs. 4d and 4e. It is interesting to note that these errors coincide with the best performing classifiers considered in the previous experiment, i.c. ha(2) := for Example and h2(x)
for Example 3. In fact, by comparing the outputs of CRO liCR with these classifiers, we can verify that the classifiers learned by CRO in these examples are precisely the mappings hCRO(2) ;= and hCRO(I)) - which is remarkable. By Thm. 3, h2((2) == 2 and hz(x)) = -x are the theoretically best worst-case classifiers among all possible functions given the data and assumptions.
5.2 Colored MNIST
Our second experiment considers the colored MNIST (CMNIST) dataset that is used in the literature to highlight the robustness of classifiers to spurious correlations, e.g. [2]. The goal of the classifier is to predict a binary label Y E {0, 1} assigned to an image Z E 2828x28 x3 based on whether the digit in the image is greater equal to five. MNIST images W 28228 are grayscale (and latent), and color C' e (red, green] correlates with the class label Y.
Following standard implementations, we construct datasets from three do- mains with varying correlation strength between the color and image label: set to 90% agreement between the color C =red and label Y = 1 in source domain M and 80% in source domain M² We consider performance evaluation and optimization in a target domain * with potential discrep-
Figure 5: G

---

T+L
Yel
7
5
0
S
g
O
3
A21
2
4
7
Tsann spart Macee1
Taiing socda Jaact
(a) Iteration
(b) Iteration 2
(c) Iteration
Figure 6: Illustration the CRO training process (Alg. 2) on colored MNIST task.
ancies in the mechanism for C, rendering the correlation between color and label unstable. The selection diagram is given in Figure 5.
Worst-case risk evaluation Consider a setting in which we are given classifier h fz Gly, and the task is to assess its generalizability with a symmetric 0-1 loss function. We use data drawn from p1.2 [, y) to train predictors using Empirical Risk Minimization (ERM) [38], Invariant Risk Minimization (IRM) [2], and group Distributionally Robust Optimization (group DRO) [32], namely hERM A ()) and hDRO respectively; more detailed discussion about the role of invariance and robustmess in domain generalization is available in appendix D. Using Neural-TR, we observe in Fig. 4c that the worst-case risk of /IRM in a target domain with a discrepancy in the color assignment is approximately 0.95, IDRO achieves 0.90 worst-case risk, and fRRM achieves 0.65 worst-case risk. Either method perform worse than the baseline, that is random classification with risk 0.5. On this task, a classifier trained on gray-scale images W achieves worst-case error of 0.25.
Worst-case risk optimization We now ask whether we could learn a theoretically optimal classifier in the worst-case with CRO (Alg. 2). Fig. 6 illustrates the training process over several iterations. Specifically, given a randomly initialized h, we infer the NCM (* that entails worst-case performance of h (in this case, chance performance Ry* (h) 0.5) and generate data D* from 0*, shown in Fig. 6a. In second iteration, a new candidate h is trained to minimize worst-case risk on ID D* Note that in D* we observe an almost perfect association between the color -grenn and label Y = 1: h therefore is encouraged to exploit color for prediction. Its worst-case error (inferred with Neural-TR) is accordingly close to 1, and the corresponding worst-case NCM 8* entails distribution of data in which the correlation between color and label is flipped: with a strong association between the color C' crd and label Y = 1. as shown in Fig. 6b. In a third iteration, a new candidate h is trained to minimize worst-case risk on the updated IT with data samples from the previous two iterations (exhibiting opposite color-label correlations). By construction, this classifier is trained to ignore the spurious association between color and label, classifying images based on the inferred digit which leads better behavior in the worst-case: achieving final error of approximately 0.25, as shown in Fig. 6c, which is theoretically optimal. Note, however, that the poor performance of the baseline algorithms not directly comparable to that of CRO, since CRO has access to background information (selection diagrams) that can not be communicated with the baseline algorithms. CRO may thus be interpreted as a ceta--lgorithm that operates with a broader range of assumptions encoded in a certain format (i.c., the selection diagram) that enable it to find the theoretically optimal classifier for domain generalization, in contrast to the baseline algorithms.
Conclusion
Guaranteeing the performance of MI. algorithms implemented in the wild is a critical ingredient for improving the safety of AL. In practice, evaluating the performance of a given algorithm is non-trivial. Often the performance may vary as a consequence of our uncertainty about the possible target domain, also called trantsasseo setting. In this paper, we provide the first general estimation technique for bounding an arbitrary statistic such as the classification risk across multiple domains. More specifically, we extend the formulation of canonical models and neural causal models for the transportability task, demonstrating that tight bounds may be estimated with both approaches. Building on these theoretical findings, we introduce a Bayesian inference procedure as well as a gradient-based optimization algorithm for scalable inferences in practice. Moreover, we introduce Causal Robust Optimization (CRO), an iterative learning scheme that uses partial transportability as a subroutine to find predictor with the best worst-case risk given the data and graphical assumptions.
10

---

7 Acknowledgement
This research was supported part by the NSF, ONR, AFOSR, DARPA, DoE, Amazon, JP Morgan, and The Alfred P. Sloan Foundation.
References
[1] Isabela Albuquerque, João Monteiro, Tiago H Falk, and Ioannis Mitliagkas. Adversarial target- invariant representation learning for domain generalization. arXiv preprint vrXiv:9111000044 2019.
[2] Martin Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Paz. Invariant risk mini- mization. arXiv preprint 1907.02990.2293, 2019.
[3] Alexander Balke and Judea Pearl. Bounds on treatment effects from studies with imperfect compliance. Journal of the American Statistical Association, 92(439):1171-177 1997.
[4] Elias Bareinboim, Sanghack Lee, Vasant Honavar, and Judea Pearl. Transportability from multiple environments with limited experiments. Advances in Neural Information Processing Systems, 26, 2013.
[5] Elias Bareinboim and Judea Pearl. Transportability from multiple environments with limited experiments: Completeness results. Advances in neural information processing systems, 27, 2014.
[6] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jen- nifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 79:151-175, 2010.
[7] Shai Ben-David John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. In B. Schölkopf, J. Platt, and T. Hoffman, editors, Advances Neural Information Processing Systems, volume 19. MIT Press, 2006.
[8] Donald T Campbell and Julian C Stanley. Experimental and quasi-experimental designs for research. Ravenio books, 2015.
[9] J. Correa and F. Bareinboim. A calculus for stochastic interventions: Causal effect identification and surrogate experiments. In Proceedings the 34th AAAI Conference on Artificial Intelligence, New York, NY, 2020. AAAI Press.
[10] J. Correa and E. Bareinboim. General transportabiliity of soft interventions: Completeness results. In H. Larochelle, M. Ranzato, Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 10902-10912, Vancouver, Canada, Jun 2020. Curran Associates, Inc.
[11] Juan D Correa and Elias Bareinboim. From statistical transportability to estimating the effect of stochastic interventions. In ISCAI, pages 1661-1667, 2019.
[12] Shai Ben David, Tyler Lu, Teresa Luu, and Dávid Pâl. Impossibility theorems for domain adaptation. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pages 19-1136. JMLR Workshop and Conference Proceedings, 2010.
[13] Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, Francois Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adversarial training of neural networks. The Journal of Machine Learning Research, 17(1):2096-200 2030, 2016.
[14] Stuart S Glennan. Mechanisms and the nature of causation. Erkenntnis, 44(1):49-71, 1996.
[15] Ishaan Gulrajani and David Lopez-Paz. In search of lost domain generalization. arXiv preprint arXiv:2007.01434, 2020.
[16] Eyke Hüllermeier and Willem Waegeman. Aleatoric and epistemic uncertainty in machine learning: An introduction to concepts and methods. Machine learning. 11033)4577-06,, 2021.
11

---

[17] Kasra Jalaldoust and Elias Bareinboim. Transportable representations for domain generalization. Proceedings of the AAAI Conference on Artificial Intelligence, 38(11)112700-1280, Mar. 2024.
[18] David Krueger, Ethan Caballero, Joem-Henrik Jacobsen, Amy Zhang, Jonathan Binas, Dinghuai Zhang, Remi Le Priol, and Aaron Courville. Out-of-distribution generalization via risk extrapo- lation (rex). In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5815-5826. PMLR, 18-24 Jul 2021.
[19] Sanghack Lee, Juan D Correa, and Elias Bareinboim. Generalized transportability: Synthesis of experiments from heterogeneous domains. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, 2020.
[20] Ya Li, Mingming Gong, Xinmei Tian, Tongliang Liu, and Dacheng Tao. Domain generalization via conditional invariant representations. In Proceedings of the AAAI conference artificial intelligence, volume 32, 2018.
[21] Peter Machamer, Lindley Darden, and Carl F Craver. Thinking about mechanisms. Philosophy of science, 17(1):1-25, 2000.
[22] Sara Magliacane, Thijs Van Ommen, Tom Claassen, Stephan Bongers, Philip Versteeg, and Joris M Mooij. Domain adaptation by using causal inference predict invariant conditional distributions. Advances in neural information processing systems, 31, 2018.
[23] Mehdi Mirza and Simon Osindero. Conditional generative adversarial nets. arXiv preprint arXiv:1411.178A 2014.
[24] Krikamol Muandet, David Balduzzi, and Bernhard Schölkopf. Domain generalization via invariant feature representation. In International Conference on Machine Learning, pages 10-18. PMLR, 2013.
[25] Judea Pearl. Causality. Cambridge university press, 2009.
[26] Judea Pearl and Elias Bareinboim. Transportability of causal and statistical relations: A formal approach. In Twenty-fifth AAAI conference on artificial intelligence, 2011.
[27] Jonas Peters, Peter Bühlmann, and Nicolai Meinshausen. Causal inference by using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 7845):947-1112, 2016.
[28] Md Musfiqur Rahman and Murat Kocaoglu. Modular learning of deep causal generative models for high-dimensional causal inference. In Forty-first International Conference on Machine Learning, 2024.
[29] Mateo Kojas-Carulla, Berharrd Schölkopf, Richard Turner, and Jonas Peters. Invariant models for causal transfer learning. The Journal of Machine Learning Research, 19()):100-1132, 2018.
[30] Elan Rosenfeld, Pradeep Kumar Ravikumar, and Andrej Risteski. The risks of invariant risk minimization. In International Conference on Learning Representations, 2021.
[31] Dominik Rothenhäusler, Nicolai Meinshausen, Peter Bühlmann, and Jonas Peters. Anchor regression: Heterogeneous data meet causality. Journal of the Royal Statistical Society: Series (Statistical Methodology), 83(2):215-246, 2021.
[32] Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. arXiv preprint arXiv:
2019.
[33] Xinwei Shen, Peter Bühlmann, and Armeen Taeb. Causality-oriented robustness: exploiting general additive interventions. arXiv preprint arXiv:2307.10299 2023.
[34] Amos Storkey. When training and test sets are different: characterizing learning transfer. 2008.
12

---

[35] Masashi Sugiyama, Matthias Krauledat, and Klaus Robert Müller. Covariate shift adaptation by importance weighted cross validation. Journal of Machine Learning Research, 8(5), 2007.
[36] Jin Tian and Judea Pearl. A general identification condition for causal effects. eScholarship, University of California, 2002.
[37] US Department of Health and Human Services. The health consequences of smoking- 500 years of progress: report of the surgeon general, 2014.
[38] Vladimir Vapnik. Principles of risk minimization for learning theory. Advances in neural information processing systems, 1991.
[39] Yoav Wald, Amir Feder, Daniel Greenfeld, and Uri Shalit. On calibration and out-of-domain generalization. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances Neural Information Processing Systems, 2021.
[40] Jindong Wang, Cuiling Lan, Chang Liu, Yidong Ouyang, Tao Qin, Wang Lu, Yiqiang Chen, Wenjun Zeng, and Philip Yu. Generalizing to unseen domains: A survey on domain generaliza- tion. IEEE Transactions on Knowledge and Data Engineering, 2022.
[41] Kevin Xia, Kai-Zhan Lee, Yoshua Bengio, and Elias Bareinboim. The causal-neurg connection: Expressivenesss learnability, and inference, Advances Neural Information Processing Systems, 34:108233-0836, 2021.
[42] Junzhe Zhang, Jin Tian, and Elias Bareinboim. Partial counterfactual identification from observational and experimental data, arXiv preprint 10..5:21 2021.
13

---

Appendix
Table of Contents
A Partial Transportability as a Bayesian Inference Task
15
A.1 Gibbs Sampling
15
A.2 Implementing Constraints
B Additional Experiments and Details
17
B.1 Additional Examples
17
B.2 More Colored MNIST
20
B.3 Reproducibility
20
Extended Discussion on Algorithms
21
Examples Neural-TR (Algorithm 1)
21
C.2 Illustration of CRO (Algorithm
................................
23
D Extended Related Work
23
D.1 Invariant Learning for Domain Generalization
Ceee..a....o....................
23
D.2 Group Robustness for Domain Generalization
25
E Proofs
25
Proof Theorem
28
F.2 Proof of Proposition
................................
29
E.3 Proof of Theorem 3
31
F Broader Impact and Limitations
32
14

---

A Partial Transportability as a Bayesian Inference Task
Consider a system of multiple SCMs M .MM MM M < .M that induces the selection diagram gÂ, and entails the source distributions Pl, "p_ ..... PK and the target distribution p over the variables V. Let db S2x be functional of interest. Consider the following optimization scheme:
Gmax
max N N N*
E PN [x)
(12)
s.t. pa (rv) = pad (rv),
Vijj E (1, ,, V Vi E (1, .,,,,,.., *,,,,
p. (w) PP)
where each A is a canonical model characterized by a joint distribution over (Ry Vvev.
This section describes an Markov Chain Monte Carlo (MCMC) algorithm to approximate the optimal scalar Jmax upper bounding the query ΦN** := Epw* [x)( above from finite samples drawn from input distributions Pl p2 ..,..., pK Formally, we aim to infer value,
4max P(Φx < 9max 5)
(13)
where = (ūpt..... Bpt), Up. (1 :j -..=-..... n.) denote n, independent sampled drawn from p
We consider setting in which we are provided with prior distributions (possibly uninformative) over parameters the family of compatible CMs ,,, N'*, ??,N? CM, probabilities of P(U), U U are drawn from uninformative Dirichlet priors; and JF are drawn uniformly from the finite class of possible structural functions. That is, for every U U and every VeV.
particular, we assume that for each
P(U) ~ (rriichle Jv ~ Uni form(AAr x Sty - Ωv)
(14)
where dy = NVEPa(C.) [Ωy] and an = =..- adv 1.
The total collection of parameters given by the set {(eN) ((0N" (OV* 5V Among them 0 -Ou [0, 1] du U U} define the parameterization of exogenous probabilities while & [E (e(pav.uv) E suppy PAv c Uv c U define the structural functions, one set of each CM separately.
We design a Gibbs sampler to evaluate posterior distributions over these parameters. For simplicity, describe each step of the gibbs sampler for single domain and input dataset, and consider the implementation of constraints below.
A.1 Gibbs Sampling
The Gibbs sampler iterates over the following steps, each parameter conditioned on the current values of the remaining terms in the parameter vector.
1. Sample u. Let u E 2r, U. For each observed data example across all domains (")) e ö, 1,..., E, ni. sample corresponding exogeneous variables U e U from the conditional distribution,
(n) (0))), oc ((u("), E)
(pa sa(")) II VeV
v(m)) I Ow. (15)
UeU
Sample g. Parameters & define deterministic causal mechanisms. For given parameter 8. ū) 1 if there (n) (n) for some where n iterates over the samples of u from step and v associated with the subsel of domains in which exogeneous probabilities match the target
Sv ((par.uv)
(pav uv) its conditional distribution is given by P(glpav.uv.
exists a sample (v(a), pay
(n)
domain, such that c
(paa"" (e) (u("))
((n), Otherwise, ((c(pav.uv)
0, ú)) is given by a uniform
discrete distribution over its support suppy.
15

---

3. Sample 0.
Let 0y (fI...., 0dg)) 0 be the parameters that define the probability vector of possible values of variables U Uc. Its conditional distribution given by,
Ou v, u Dirichlet (a1 + BI...., Odg + (dd))
where 3: := hn (( = w Similarly, iterates over the samples of u from step I associated with the subset of domains in which exogeneous probabilities match the target domain.
A.2 Implementing Constraints
lterating this procedure forms a Markov chain with the invariant distribution P(u, E, 0). This naturally enforces the soft constraint pv* (v) ( E 21. K, for the CMs defined by the sampled parameters. The posterior distributions of the subset of (ØV* - ) for which invariances across domains are assumed are then matched with the posterior distribution inferred from source
data. The constraint pM* (rv) PA** (rv), 21,2, ..... K, #], V A,,
s is enforced by generating
B from the prior such that pN* (rv) == Eueo 8 = Euen BN" = PN (rv), V & Ai where
Ω denotes the partition of suppr, that expressed by Rv.
The query is then approximated by plugging the T MCMC samples into the query Φ사** to obtain (1) N
(T) Na and
Fmax = supfæ: xx 11 NO < <) = a).
(16)
for a chosen value of confidence value a.
Example 5 (Example continued). Consider again the evaluation of the risk Rp* (h) PN* (Y #
MxX)) given the classifier h((r)) -r. We are data sampled from Pt v). P² 1). For every SCM M, there exists an SCM of the described format specified with only a distribution Pyrx,ry), where,
supPax = {0, 1}. suppn, = (v= = 0 = 1, = z, = -z].
(17)
Thus, the joint distribution P(uxy) = P(rx, ry) can be parameterized by a vector in 8-dimensional
simplex. The canonical SCMs associated with each of the SCMs .M _M,M², MMM** are denoted N=,N",N' for which = [X, Y), U = {Uxy} and supPtxy = {l.....8)) 8). The partial task can be translated into optimization problem aiming to to find the upper-bound for the risk Rp (h)
for the classifier h(x) = -:
PV* (Y + -X) N WIAN
max
(18)
s.t. PM (rv) = pM* (ry) pao (rx) pA** (rx)
(Y $ A1, and X A2)
pvt (x. = Pl v), pv3 (z. p²(x,, u)
(matching source dists)
With the Gibbs sampler outlined above, we obtain samples from the posterior distribution P(ON" AN . _/ o). gV", g, encode the probabilities P.V" (Uxy = u), PV² (Uxy = u) and are instantiated as two-dimensional arrays of shape (2, 4) such that, e.g., P.V' (rr) Edti. AN" with ry (1,2,3,4 4) and similarly Pv1 (Tx) = Eam. AV with rx E (1,
To enforce the constraints P.dt (ry) = PV* (ry), (rx = pN*((x) it thus suffices to sample A~ from the prior Dirichlet distribution (as it has not been updated with data) and re-scale the outcomes such that the partial row and column sums satisfy the corresponding partial row and
column sums computed from the MCMC samples of P(OV* _0v2 σ). The resulting MCMC
parameters (6'* _**)) are then valid samples from the posterior distribution P(pV* .gN** 6) subject to assumed constraints, and the risk could be computed by plugging those samples into Rp* (h) = pa* (Y + h(()) (X)) to obtain Rpe (1) Rps (h) and evaluating
imax := sup(a: 1( x) a).
(19)
for chosen value of confidence value a.
16

---

Ny(e,w)
Ay(e)
Ry(0
Rp
1.0
Rp
0.0
0.5
0.8
02
0.2
nm110
6m200
m=1000
n=2000
Figure 7: Violin plots that describe MCMC samples of Rp* (h) for Example 2. The upper end-point an estimate of max Rp* (h). n stands for the number source domain samples used as a conditioning set in the posterior evaluation.
The following Theorem shows that fmax converges to the true (tight) bounds qmax for the unknown query R.pa (h).
Theorem 4. Úmax defined in Eq. (19) is valid upper bound qmax for any sample size, and coincides with 9max as the sample size increases to infinity.
Proof. Let θ denote the collection of parameters &, 0 of discrete SCMs that generate the observed We assume that the prior distribution on &, 0 has positive support the domain of @. That is, the probability density function p(E) > 0 and p( (0) > 0 for every possible realization of 0. By the definition of O, for every pair of parameter (E, 0) O must be compatible with the dataset G, i.c., P( & 0) > 0. Similarly, given that the prior has positive support in O, (E
data from pl, p2
0.
Note that parameters (E. 0) E @ fully determine the optimal upper bound Juax for Rp (h). And so this implies that P(Rpt (h) < quax Φ) O, which by definition of 100% credible interval means that Rps (h) < Fmax.
Next we show convergence of the posterior by way of convergence of the likelihood of the data given one SCM M. For increasing sample size the posterior will, with increasing probability, be low for any parameter configuration, i.c. for any (E, 0) @ By the definition of the optimal upper bound Qmax given by the solution to the partial identification task,
P( Rps (h) 4max) -pp 1.
(20)
Therefore if the prior on parameters (E, 0) defining SCMs is non-zero for any M compatible with the data and assumptions, also the posterior converges,
P(Rp*(h) 4max
6 >pppl 1,
(21)
which is the definition the credible value Qmax as the 1h0th quantile of the posterior distribution, which coincides with 4max asymptotically.
B Additional Experiments and Details
This section includes experimental details not covered in the main body of this paper well as additional examples to illustrate our methods, including the Bayesian inference approach.
For the approximation of credible intervals and expectations required for the Bayesian inference approach, we draw 10,000 samples from posterior distributions P(- 8) after discarding 2, 000 samples as burn-in. The results will be given violin plots that encode the full posterior distribution of the query of interest, here the target error Rpe (h) a classifier h. The worst-case target error can then be read as the upper end-point of the posterior distribution.
For completeness, we provide MCMC results for Examples 2 and 3, analyzed in the main body of this paper, in Figs. 7 and 8, respectively. One could check that the upper bounds match with the analysis in the main body of this paper.
B.1 Additional Examples
This section adds additional synthetic examples to illustrate our methods.
17

---

By(00)
Ry(0))
Rp
I
Rp-
80
04-
06-
1-0
500
n-2326
1-0 -C0
n-1993
n-2395
B=2000 1=2000
(w-0000 TM2000
Figure 8: Violin plots that describe MCMC samples of Rp* (h) for Example 3. The upper end-point is an estimate of max Rp* (h). stands for the number of source domain samples used conditioning set in the posterior evaluation. Recall that (2)) x, ha(x) =x, ha hz) 0, (x) 1.
hyls,t, w) hylt, w)
A.(w)
Kip w)
Ay(w)
Rp
Rp
Ry
0.8
0.3
0.6
0.4
0.4
0.2
0.0
50
75
100
0.0
50
100
Training apachs
Training opoahs
(a) Example 6
(b) Example 7
Figure 9: NCM experimental results Examples 6 and 7.
Example 6. This experiment is inspired by the debate around the relationship between smoking and lung cancer in the 1950's [37], and the corresponding selection diagram is shown in Figure 12a. We consider M { that describe the effect of an individual's smoking status S on lung cancer C. including related measured variables such presence of in the lungs T,, and demographic factors W. The data generating mechanism is given by
V
( -WW,STT S,T,C)
=
U
= (Uw, Us, Ur. Uscl fw(ww)
uw, for W E W, Uw E Uw
1,
if Σ d + usc 1.5 U2 1> 0 1
fs(w,, us, us, usc)
1,
Σ
wi + usc us and d
M
0,
otherwise
F
1,
if 0.5ur - 1> 0
fr(,,
0.
otherwise
1,
if Σ, di + usc 1
Solw, uc, usc) =
1.
otherwise
P(U) defined such that Us, Ur, Use (ern(0.5), Uw ~ WeW.
Note that A = (S) as the mechanism for differs across domains while the mechanisms for other variables assumed invariant. The quantity upper-bound is the target mean squared
error: Rp (h) = Ep [(C - 2 of cancer prediction algorithms E C w. t, hsww) Er- w]] given data from pl and G
{/1 (w, s, t) Ep
w, s, k,t],
The results for the NCM approach are given in Fig. 9a. We observe that despite the discrepancy in S, all methods maintain an error of close to 0.4.
The results for the Gibbs sampling approach are given in Fig. 10. The violin plots encode the full posterior distribution of the query of interest, here the target error Rp (h) of a classifier h. The worst-case target error then be read the upper end-point of the posterior distribution. We observe that the upper- upper-bounds from the NCM and MCMC approach approximately match.
O Example This experiment considers the design of prediction rules for the development of Alzheimer's ss disease in target hospital MM in which no data could be recorded, and the cor- responding selection diagram is shown in Figure 12b. The observed variables are given by
V (X1, X2, W, Y, Z). Among those, X, and X, are treatments for hypertension and clini- cal depression, respectively, both known to influence Alzheimer's disease Y, and blood pressure W. Z is symptom of Alzheimer's. s. Their biological mechanisms are somewhat understood, e.g. the
18

---

11,3,,, w)
hg66, w)
ky(w)
Rim
Rp
Rym
100
nmb0g
1m1000
m=2000
n-100
5-500
n-1000
r-2000
n=100
n00500
n=1000
n=2000
Figure 10: Violin plots that describe MCMC samples of Ap (h) for Example 6. The upper end end-point is an estimate of max Rp* (h). stands for the number of source domain samples used conditioning in the posterior evaluation.
h Kg w)
hy(w)
hy(a)
1.0
10
Rps
Ry
Rps
0.5
08
0.8
0.5
0.4
100
5-0
1=0000
n=0000
f=-500
I=5500 n=00000 n=20
Figure 11: Violin plots with MCMC samples for Example n stands for the number of source domain samples used as conditioning set in the posterior evaluation.
effect of hypertension is mediated by blood pressure W, although several unobserved factors, such as physical activity levels and diet patterns, expected to simultaneously affect both conditions. We assume that hypertension and clinical depression are not known to affect each other, although it's common for patients with clinical depression to simultaneously be at risk of hypertension (expressed through the presence of an unobserved common cause). More specifically, investigators have access data from related study conducted in domain M SCMs M M*) are given as follows,
V
X2,, W,Y,2)
U
(UwY, Ux,, Uw, Ux U2)
1,
if Ux, >
(xx(UX)
0,
otherwise
1,
if Ux + Ux, > 0
[x,(UX,Xx; Uxa)
0,
otherwise
1,
if X1 + UWY + 1.50w 1>> 0 and
M
F
fw UWXK,U Uw)
1,
if +WyY - Uw + 0 and
0,
otherwise
1,
if -UwY + 0.1X 1>
fv,
0,
otherwise
1,
if + Uz > 0.5
f2(Y.U2)
0, otherwise
P(U) defined such that UWY, Ux,, Uw, Ux,x,, Uz N(O, 1),
Note that A {W} as the mechanism for W differs across domains while the mechanisms for all other variables assumed invariant. In this example, aim upper- bouedrig the target mean squared error: Rp (h) := Ep [(C - h] of cancer prediction algorithms h e (h1(x1, I2, w) = Eyi(Y 22, w], h2(w) Em [Y wr). hz, Ext [Y] =]} given data from pl and ga+1,
The results for the NCM approach are given in Fig. 9b. We observe that the discrepancy W leads to poor performance for all methods (chance level) except for ha that outperforms.
The results for the Gibbs sampling approach are given in Fig. 11. The violin plots encode the full posterior distribution of the query of interest, here the target error Rp (h) of a classifier h. The worst-case target error can then be read the upper end-point of the posterior distribution. We observe that the upper- upper-bounds bounds from the NCM and MCMC approach approximately match. O
19

---

W
X W
C
X
Z
(a) Example
(b) Example
Figure 12: Selection diagrams for additional experiments
B.2 More on Colored MNIST
Consider handwritten grayscale digits W [0, _| that are annotated with Y E {0, 10....... 9} and colored with C E fred, green), resulting in colored images E [0,1] [282283, What follows describes the underlying SCM for domain i 21,
W, UyU,, Uc. Uz P(w)- P(wy)- P(uc) P(uz)
Y [r(W, Uv)
(The annotation mechanism)
M'
Fi:
C fe(YUe))
(The choice of color based on digit)
Z- C + Uz (Coloring image W with color ()
In words, the grayscale image of handwritten digits W is generated according a distribution P(w) shared across all domains. The label Y is the annotation of the image with the corresponding digit through mechanism fy shared across all domains; the variable Uy accounts for the possible error in annotation. Next, the color is chosen based on the digit Y following some stochastic policy fol-, Uc) that changes across the source and target domains. Finally, the colored image is produced by product of the grayscale image W and the color C; exogenous variable Uz accounts for possible noise in coloring.
We have classifier h: Pzz - Sy at hand, and the task is to assess its generalizability. Consider the following derivation:
pc (z. v)
Σ p* pt(y.c,2
(22)
Σ Pt)) (*(e v) P* c,
(23)
Py) pt(c pp.2(x) lc,y)
S2 C,Y
(24)
pl) Σ pt v) (1 e,y)
S2
(25)
Motivated by the above derivation, we use the source data drawn from pl, p2 and train the generative models P(y; f) P(z y, c; 722) to approximate sampling from the distributions (1.2(y), pl.2(z y, c). respectively. The former generates a random digit Y according to the distribution of label in the source domain, and the latter generates a colored picture Z by taking color and digit Y as the input. Also, we use NCM with parameter 0g to model the c-factor p* (c do(y)) ps (c v).
can now rewrite the risk as follows:
Rp* (h)
Σl Mz)) (1) Σ (c v) (1.2 (c
(26)
Z.
Ey Ey-
Σ P(c y 0t) B2- h())]]]-
(27)
By maximizing the above w.r.t. the free parameter f8. achieve the worst-case risk of the classifier.
B.3 Reproducibility
For the synthetic experiments, we used feed-forward neural networks with 7 layers and 128 128 neurons in each layer. The activation for all layers is ReLu, but for the last layer which is sigmoid since Jay outputs the probability of V For evaluation, at each epoch, we used 1000 samples from the joint distribution. The data generative process for all experiments is provided in the corresponding
20

---

S
W
Figure 13: Selection diagram of Example 8
example. We used Adam optimizer for training the Neural networks. CMNIST example, we used standard implementation of a conditional GAN [23] trained over 200 epochs with a batch-size of 64. The learning rate of Adam was set to 0.0002. The architecture of the generator given by a layer feed-forward neural network with Batch normalization and Leaky-ReL.J activations.
C Extended Discussion on Algorithms
In this section, we elaborate more on the algorithms presented the paper.
C.1 Examples of Neural-TR (Algorithm
In the next examples, we follow Algorithm to compute the worst-case risk of a classifier. Example 8 (Simplify). Consider system of SCMs MM over X {C, Z, W) and that induces the selection diagram shown in Figure 13. Suppose we would like to assess the risk of classifier h22). Following Theorem 2, the naive approach requires us to parameterize three NCMs 0¹,02, 8 over the variables X, Y, and then proceed with the maximization of the target quantity R Rows (h) Ep [1(Y = h(Z)}]. Notably, the latter depends only on p* (y, 2). We can rewrite the
risk of as follows:
Ey PP [1 # h(Z)}1
[1
Σ 1(y # h(2)) (y,,2)
(28)
Σ 1ly * h(=)) p* (*()) P* (=(11)
(factorization) (29)
Σ ( * h(z)) (1) p²((2 (v)
(Y 21) (30)
2.
Σ 1 (=)) (2 v) Σ (v, 2.8
(31)
This new expression for the objective function depends only on the unknown P* (y. c). a ca-cll ancestral c-factor, that can generally be expressed as p*(a d)) A {C, Y). In the following, we argue that to partially transport the risk we only need to parameterize the SCMs over ancestral e-factors that restated as follows:
transportable. Specifically, the partial transportation problem can be
max 21,82.00 #
EUoY Σ
Ply,e Ucy;0*). P(z 11: 1ly h(2))]
(32)
V.C.2
+ +A.
Σ
BUeY [log Ply.e c UcY; 0*) Σ
Euey flg c Ucx; (2)1
DI
V.0E 12
s.t. 8 [C] = 0º[C].
[²] = [Y]
In the above, D' ~ (' y. z, w) denotes the source data, and P(z y: 172 is a probabilistic model of (2 8) learned using the data D
O
Example 9 (Partial-TR illustrated). Consider a system of SCMs M M M over the binary variables X (X1,X2,- {9} and Y that induces the selection diagram shown in Figure 14. Consider the classifier h(21, = D1 v Iz. The objective is partial transportation of the risk of h, expressed as follows:
Rps (h) = P*(Y * 1((X, X4)) = -x [1(Y # X, v XaI..
(33)
(34)
21

---

X
X
S
S
Figure 14: Selection diagram of Example
The latter indicates that (X,,, Y) 1(Y
X1 X4} must be passed to the algorithm. The
objective function then expressed as:
Rps (h) Ex [ X4,
Σ
1(Y X1 v X4)
P* (21,
(35)
Next, we focus on transporting p (z1, v). First, we compute the ancestral set using the selection diagram;
A An(X1, = (X,, X2, X4. Y, X5, X6. X8, X9).
(36)
and decompose this set into e-components:
A = (X1, X2), A (X4, Ag = (Xo: Xs,
(37)
Next, we form the expression below:
P* (*1,, = Σ
(*121,02 do(g)) P* (y, do(xx)) p* (I6,..., (38)
Notice,
pa (* do(ss)) mile 2 do-cale.
p* xz)
v pl pl x6);
(39)
SadlyAsixe (2()))
p (*(as)
(40)
Thus, we use the source data D D2 to learn the generative model P(aş =o: P(as: 12a)) to approximate sampling from (1 wa), p2 respectively. We plug these models as constants into Eq.
Since S+1, Sa2 are pointing to the variables X2, X1, respectively, the first term P* (*)1, do(y)) Eq. 38 can not be directly transported from neither of the source domains. Thus, we need to parameterize this e-factor using NCMs across all domains. We require the following properties:
1. Parameter sharing: Since X4, Y, Xs, X7, Xg, X9 are not pointed by St, we share their mecha- nisms across all domains. Also, since X2, X, not pointed by S2, we 0+ (Xa.Xo) These constraints are stored in Coxpert in the Algorithm.
0
XX))
2. Source data: To enforce 81 8² to be compatible with the source data D D2 we compute the likelihood of the data w.r.t. the parameters, as follows:
Liikelihood = Σ
Σ
E EX blog P(21, y, U Ux,xx;
(41)
(a) (D
We plug 1( do(y): 0% ) into Eq. 38. Finally, we use stochastic gradient ascent to maximize the objective function in Eq. 35 regularized by an additive term Liikelihood that encourages the likelihood of the data w.r.t. the parameters of the source NCMs.
22

---

C.2
Illustration of CRO (Algorithm 2)
First, we initialize with random classifier. One may also warm start with reasonable guess such as empirical risk minimizer defined as,
hERM E arg min h: -y
Σ D.
(42)
Throughout the runtime of the algorithm we accumulate instances of distributions that we obtain via Neural-TR (Alg. 1). At each step, these distribution are aimed maximize the risk the classifier at hand. In this sense, Neural-TR can be viewed as an adversary, and the CRO can be viewed as a game between two players:
1. Neural-TR. Searches over the spaces of plausible target domains that are characterized by the source data and the domain relatedness encoded in the selection diagram, to find distribution that is hard to generalize using the classifier at hand.
2. group DRO [32] Updates the classifier at hand by minimizing the maximum risk over the distributions produced by Neural-TR so far, that is,
min k:fxx -y DEDS
max
Σ a.EE
Cly. h(x)).
(43)
D
For more information about group DRO, see Appendix D.2.
The equilibrium of the above happens if the worst-case risk obtained by Neural-TR almost coincides with the risk obtained by group DRO, i.c.,
Rp(a.y:0) (h)
Σ
C(y,h(x) < 8.
(44)
DED
D
2.ye
Once this is achieved, stop the search and return the classifier at hand. When the game is not equilibrium, we would have difference larger than 8, meaning that the new target domain 0* has enough novelty to forces the classifier at hand to perform at least ô worse than what it achieves over the existing distributions in D Therefore, we draw samples D P(x, 6) and add them to our collection ID As shown Theorem this game reaches the equilibrium in finitely many steps, and the classifier that return has the best worst-case risk w.r.t. the selection diagram G and the source distributions P. The conceptual Figure 15 shows the process convergence of CRO.
It is important to note that although we employ group DRO as a subroutine in our CRO algorithm, do use the source distributions directly. Instead, we use group DRO on the distributions obtained from Neural-TR. Note that under the assumptions encoded in the selection diagram, the target distribution distribution may be geometrically unrelated to the source distributions; the reason is that mechanistic relatedness of the target domain to the source domains (as indicated by the graph) do translate directly closeness of the entailed distributions under known distributional distance measures.
D Extended Related Work
In this section, we discuss some learning schemes based on invariant and robust learning that proposed for domain generalization. including IRM and group DRO that discussed in the experiments.
D.1 Invariant Learning for Domain Generalization
Several common invariance criteria are extensively studied in the literature and proposed for the domain generalization task. prominent idea label conditional distribution invariance that seeks representation ø such that Pi(Y Φi X)) )) is equal across the source domains [29, 1, 13, 22). These notions do not explicitly rely on an underlying structural causal model (SCM), although invariances
often justified by an underlying causal model [27, 2, 39, 31, 33]. Jalaldoust & Barcinboim
23

---

(a) Iteration
(b) Iteration 2
(c) Iteration
(d) Equilibrium
Figure 15: Conceptual illustration of CRO. The rectangle represents the space of all distributions over.x, Y. and the circle inside it represents the subset of that plausible target distributions, characterized by the source distributions and selection diagram. Iteration 1: At first we start with some classifier that may may perform well for distributions in the plausible subset; the darker spots indicate distributions that yield higher risk for the classifier at hand. Neural-TR uses gradient ascend steps to find an SCM that entails distribution which yields the highest risk for the classifier at hand, i... the darkest spot within the plausible subset (likely at the boundary of it). shown by the star blue in Fig. (a). We register this distribution by taking samples from update the classifier at hand to have group robustness
and adding them to the collection ID. Iteration to the collection distributions D*; in this case, only risk minimizer, since there is only one distribution in the collection. Now the distributions that are close to the registered distribution would entail small risk, thus, the region around the first star is brighter. Once again, using Neural- high risk for the classifier at hand. Iteration 3: We update the classifier, this time minimize the risk on both registered distributions indicated with yellow starts using group DRO. Now the risk is smaller most parts of the plausible set, though Neural-TR still finds another distribution at the boundary with high risk. Equilibrium: We update the classifier using group DRO over the three registered distributions. This time, the registered distributions correctly represent the plausible set, meaning that the maximum risk inside the plausible set is not significantly larger than what is achieved the registered points through group DRO.
find distribution that yiclds
[17] studied the implicit assumptions that license generalizability of representations that satisfy the probabilistic relation P'(Y 6( ())). Although searching for such representation is practically challenging and in cases theoretically intractable. Thus, may resort achieving approximate notion that serve as a proxy to invariance of P ((X)); A well-known instance of such effort is invariant risk minimization [2], discussed below.
The paper [2] studies a constrained optimization problem called invariant risk minimization (IRM) in the context of domain generalization. In the notation of our paper, the IRM problem can be written as follows:
min 6.
Σ E * ho (()]
s.t.
h E arg Epp ( * h (XX) Vi, (0
(45)
Where Qx - aR is representation, and h a2 {0, 1} is classifier defined based on it. In words, a pair h, o satisfies the invariant risk minimization property if h Φ attains the minimum risk across all classifiers defined based o, across all source domains. The search procedure suggests choosing the classifier that satisfies the mentioned constraint, and achieves minimum risk on the pooled source data. The constrained optimization program above is highly non-convex and hard to solve in practice. To approximate the solution, the paper considers the Langrangian form below:
K Ep:(Y * ho ho( + X VOE * hg (X)1
hIRM E
min ha:0xx (0.1)
(46)
In this program, 0 parametrizes the classifier h, and the penalty term À accounts for how restrictive one wants to enforce the IRM constraint. In the extreme À 0 the objective equates to the vanilla ERM with all data pooled; on the other extreme, for À - ac ascertains that the solution is guaranteed to satisfy the IRM constraint.
Consider a representation that satisfies the original IRM constraint in Eq. 45. The optimal classifier defined over this representation is the bayes classifier, that uses / level set of P*(Y as the decision boundary. This means that satisfying the IRM constraint implies a match between level-sets of P²(Y 1 o(X)) across all source domains. On the other hand, invariance of
o X))
24

---

PY (()) requires coincidence of every level-set across the source domains, and in this sense. the IRM constraint can be viewed as a proxy to the invariance property of Pi(Y o()).. One
can speculate that since IRM yields proxy to invariance of P'(Y & ())), it might still exhibit
generalization, though slightly weaker than what derived from invariance of Pi(Y (()).
However, IRM is shown to have poor domain generalizability both theoretically (e.g., [30]) and
empirically (e.g.. [15]). Still, due to popularity of this method in the literature, we find it insightful to use the Neural-TR algorithm to find out what would be the worst-case risk of IRM. As shown in Fig. 4c, the worst-case performance of IRM is much worse than what is reported by [2] and [15]; the reason is that Neural-TR -RR does not commit one held-out domain, and instead it constructs an SCMs that is tailored to yield the poorest performance subject to the graph and source distributions.
D.2 Group Robustness for Domain Generalization
Group Distributionally robust optimization (group DRO) [32] has been employed in the broad context of learning under uncertainty. In group DRO one seeks a single classifier that minimizes the risk on multiple distributions simultaneously. More specifically, the objective is minimizing the maximum risk among the source distributions, i.e.,
1DRO arg min max
Rp. (1.........K
(47)
This approach ensures that the learned classifier is optimal w.r.t. unknown target domain that lies in the convex hull the source distributions. this sense, group DRO objective interpolates the perturbations that are represented in the source data to define uncertainty set for the target distribution. On the other hand, in invariant learning the objective is to extrapolate the perturbations that are observed among the source domain by learning a representation that shields the label from these changes. In particular, [18, 31, 33] highlight the invariant-robur spectrum, and propose methods considered that have free parameter which allows interpolating the two. In our experiments, group DRO as a representative of methods in this category, and evaluated its worst-case performance in the Colored MNIST task, as shown in Figure 4c. Once again, we emphasize that this worst-case risk is much larger than what is shown in the benchmarks, e.g., by [15]. The reason is that the worst-case performance is obtained by Neural-TR that operates as adversary, seeking plausible target domain that is hardest to generalize to, subject to the assumptions encoded in the graph and the source data.
E Proofs
Proof of Theorem
Our results rely on the expressiveness of discrete SCMs, i.c. defined over variables {V, U} with finite cardinalities. Discrete SCMs, introduced first in [3] and then in [42] have been shown to be "canonical" in the sense that they could represent all counterfactual distributions entailed by any SCM with the same induced causal diagram defined over finite V. The following example illustrates this observation.
Example 10 (The double bow). Let (X,Y, be binary variables. Consider source domains defined based on the following SCMs:
Ux ~ Normal (0, 1)
Ux Normal 1)
P²(U):
Uxy ~ Normal 1)
P*(U):
UXY Normal(O,
UZY Normal
UZy ~ Normal 1)
M
M
X 1(Ux + +xx > 0}
X - 11Ux + Uxx > 0}
Fl
Y - 1fX- - Uxy > 0}
F :
Y - 1{-Uxy + 0.5 > 0)
2 - 1[Y Uzy > 0)
Z - 1(Y Uzy 0}
The SCM M induces a counterfactual probabilities, e.g. PM (x, Mz. zy) for outcomes x, Mr. Zy (0, 13. [3] observed that such probabilities, defined over finite set of events, may be generated with an equivalent model with a potentially large but finite set of discrete exogenous variables. [3] derived a canonical parameterization for the SCMs that induces the same graph but instead involves possibly correlated discrete latent variables Rx Ry, Rz, where Rx determines the functional that decides
25

---

X, Ry determines the functional that decides Y based on X, and Rg determines the functional that decides Z based Y. [3] showed that for every SCM M with the same induced graph as M' there exists an SCM of the described format specified with only a distribution P(rx, rY, where,
supP = {0, 1],
SupPRy {y/ 0. y 1, 2, -x)
supPay (z 0, 1,2 y,
Thus, the joint distribution Py rz) can be parameterized by an 32- 52-dimensional vector.
This example illustrates a more general procedure, in which probabilities induced by an SCM over discrete endogenous variables V may be generated by canonical model. This is formalized in the following lemma.
Definition 7 (Canonical SCM). A canonical SCM is an SCM
(U,, defined as
follows. The set of endogenous variables V is discrete. The set of exogenous variables U = {Ry V E V}, where suppRy = {l...., my (where my / supPpav suppv })) for each V V. For each V e V. fv F is defined as fv(pay, (4r"((pa)))) (pav).
The following lemma establishes the expressiveness of canonical SCMs.
Lemma (Thm. 2.4 [42])- For an arbitrary SCM M = (U,V. F, P(U)), there exists a canonical SCM N such that I. M and N are associated with the same causal diagram, i.e., GMs Gx. 2. For any set of counterfactual variables Yz...., Zw. PM (Y....., F Zw) PM (Y....., Zw)
In words, finite exogenous domains in canonical SCMs sufficient for capturing all the uncertainties and randomness introduced by the (potentially) continuous latent variables in SCMs. Our goal will be to adapt the canonical parameterization of SCMs such that they entail the equality constraints specified by G The next example illustrates the implication of the constraints induced by g on the construction of canonical SCMs.
Example 11 (Example 10 continued.). Consider M and M given in Example 10. The domain discrepancy set A indicates that certain causal mechanisms need match across pairs of the SCMs. For example, Ais (YY), which does not contain (XX 2), and this implies that the functions fx. fz are invariant across M and that the distribution of unobserved variables that are arguments of fy, fz. namely, {Ux. Uxx, Uyz] are invariant across M M* The canonical parameterization of M is given by
V
= (X,Y)
U
{Rx, Ry, Rz}
f suppax suppx
Fl
fy supp RY x suppx suppy
fz suppax suppy suppz
('(U) = P Ry,R2,
Analogously, the canonical parameterization of M is given by
V
= (X.Y}
U
[Rx, Ry, Rz}
f supPRx suppx
F
1T suppRy x suppx Suppy
12 supPRy suppy suppz
P*(U)
Pa (Rx, Ry Rz)
With these definitions, the restrictions in Ais impose straightforward constraints on the parameteri- zation the canonical models given directly from the definition of discrepancy set:
(x(x)) (Xxx), p* (rx), X $ A
f2(y.r2) = P3) Pr)), Z A
for any input æ, FX,
26

---

The next lemma formalizes the observation made in the example above, showing that if a pair SCMs and a pair of associated canonical models induce the same distributions and causal diagram, their discrepancies must also agree.
Lemma 2. For pair of SCMs M MP (i,j 1, T}) defined V with discrepancy set Aij - V. let N*,N* Na be associated canonical SCMs that induce the same causal graphs and entail the distributions over V. Then the discrepancy sets of the pairs of SCMs and canonical SCMs must agree, i.e. V Dij if anndd only if either fV # JV or pNd (uv) pNd (uv).
Proof. Let Ve E Aij. and fix M', M such that PM (u do(pay)) * PM6 (v do(pay)) ))- This is possible since the interventional probabilities are parameterized by the mechanism of V which could vary across M M Assume for contradiction that f - ft and PN (uv) -pN (uv) for two canonical models N Ná constructed match all La statements induced by M M' implies in particular that paV (v do(pav))
MM. This
pa (v do(pav)) and therefore N N A do not induce the same probabilities as M .M.. This contradicts the assumption that the pair of canonical SCMs matches the pair of SCMs in all L3 statements.
For the converse, we proceed similarly. For fixed M", M assume for a contradiction that IV * fV or PN* (uv) * PN' (uv) such that p.t (v do(pay)) * p.7 (u do(pay)) for two canonical models , constructed to match all Ly statements induced by M .M3, but nevertheless V & Aij. p-sp( (u do(pav)) but the same relation
The discrepancy set ensures that pM (v do(pav)) not true for N N as PN* (v do(pav)) # pAd (v do(pav)) by assumption and therefore N "N' do not induce the same probabilities as M', .M.. This contradicts the assumption that the pair of canonical SCMs matches the pair of SCMs in all Ly statements.
MK _M*} that induces selection diagram and entails the source distributions P {pl p2 pk p*} over the variables
Lemma Consider a system of multiple SCMs M. (M
V. Then there exists system of canonical SCM N: (N1 ,N2 "..,,,,,kk ,N*} such that
1. M and N are associated with the same set of causal diagrams and selection diagrams.
2. For any set of counterfactual variables Ya,..., Zw PN* (Y..... Zw).
PM* (Ya,..., Zoo)
..M*) and canonical SCMs N [W',N2 , A,K No) induce the same causal diagrams. Lem. gives that for every pair of SCMs M M (i.j {+, 1,....... T)), their discrepancy set is the same as that of A/i .A ji,j E {+, 1, 2, ,,...,,Ty,.. TT). As selection diagrams are constructed deterministically from causal diagrams and discrepancy sets, MI and N must share the same of selection diagrams.
Proof. For (1), Thm. 2.4 [42] gives that SCMs M
(2) is given by Thm. 2.4 [42].
Theorem 1 (restated). Consider a system of multiple SCMs M .M...... MK, MM that induces the
selection diagram G and entails the source distributions P1 p2 pa....,PP' PK. and the target distribution ps over the variables V. Let (p*)) E [0,1] be the target quantity. Consider the following optimization scheme:
th (PN2
Gmax
max No N
(48)
N*
N*
pv' (rv) -PN
Vi,j E (1,2,..., K,+) AA Ais
pvt (p)=
ViE (1,2...., K, K,+},
where each N is canonical model characterized by joint distribution over (Rvivev. The value of the above optimization, namely @mass is a tight upper-bound for the quantity sp( ps among all tuples of SCMs that induce the selection diagram and entail the source distributions at hand. O
27

---

Proof. Note that,
20 (PMM*
max 9max MI MIM M
(49)
s.t. pMt (uv) = pMb (uv), ft =VV Vi,j (1, (1, K,,, VV W D. Wi 11,,,..,K,$11.
pMt (v) = PP())
is tight upper bound to the target r (PMM)) among all tuples of SCMs that induce the selection diagram and entail the source distributions at hand, by construction. It follows from Lem. that for any tuple of SCMs (M* ,M* that induce the selection diagram and entail the source distributions, there exists a tuple of canonical SCMs N ,',,, ....,.', that induce the selection diagram and entail the source distributions such that,
pMd (Y Zw) PP'* (Y Zw)
The reverse direction of the above equations also holds since family of canonical SCMs is an instance of a family of SCMs. This means that solutions for optimization problems in Eq. (48) and Eq. (49) must coincide.
E.1 Proof of Theorem 2
To prove this result, need show the following:
1. Necessity. Every tuple of NCMs θ that are constraint by conditions in Eq. 8 represents a tuple of SCMs that entails P and induces GA.
2. Sufficiency. For every tuple of SCMs MI that entails IP and induces G there exists tuple NCMs θ that admits the constraints in Eq, and for every i E {x, 1, 2.... KJ, we have P(yz, zw; 0*) p.M (yz zw), where ye, Zwo-
Necessity, Consider a tuple of NCMs ④ that are constraint by the conditions in Eq.
ge-consistency. Since these NCMs are constructed based on the common causal diagram G, they all induce G (Theorem 2 by Xia al. [41]). Moreover, the parameter sharing constraint states that V $ Aij if and only if 02 0y. This implies that the NCMs parameterized by θ induce the same domain discrepancy sets as G Thus, the selection diagram induced by the NCMs parameterized by e is exactly G
P-expressivity. The data likelihood condition for source distribution Pi(v) states the following:
0' arg max 9 e-constrained
Σ we
log P(o;
(50)
For large enough samples size |D' ~ (v)), and enough model complexity in 6, Theorem by Xia et al. [41] shows that there exists G-constrained NCM 9 that induces the distribution entailed by the true SCM M'. Thus, by imposing Eq. (50) we assure that P(v; 0¹) = (v) By imposing all data likelihood conditions, in the limit of sample size and model complexity, we ensure that the source NCMs induce the source distributions.
In conclusion, the tuple of NCMs necessarily representing plausible target domain since (1) they induce ف and (2) they entail P.
Sufficiency. Consider tuple of SCMs MI = (M- LMMAA MM....,MKK MM* that induce eà and entail P. Theorem by Xia et al. [41] shows that for every SCM M that induces G. there exists a G-constraint NCM parameterized by 0 such that (M
P(v; 0) (as consequence of L3 L3-consistency). The proof is constructive, and for every V E V the construction of the neural network Oy depends on (1) the function fv and (2) the distribution p.M(vv)
Consider two SCMs M', M (i.j E {+, 1,2, .... K}) that induce domain discrepancy set Asj-
Follow the construction by Xia al. [41] to obtain the corresponding NCMs parameterized by 6$ 66. For every V $ A., we have, 0z = of since the construction depends on fi = R and PM' (uv) = PMe (wv). Thus, the domain discrepancy set induced by 05, o matches with As,; induced by the
28

---

SCMs MiM Therefore, By constructing the NCM 8' from M (i f,,1.2..... KY), we are guaranteed have a tuple of NCMs N that (1) induce ف and (2) entails
Partial-TR via NCMs. Due to necessity and sufficiency above, we conclude that a tuples of NCMs satisfies the parameter sharing and data likelihood conditions stated in Eq. 8, if and only if there exists a tuple SCMs M that induce G and entail such that P(v; 0*) = pM (v) for i E {+, 1,, KJ. Therefore, by solving the following optimization problem.
arg max
Σ ((w))
Σ viw
P(e; 0*)
(51)
@: 8 .88
s.t. 8 0
Vi, (1,,...,K,,t) VV Arj
0' E arg max
Σ
log P(v;0),
Vie {1, (1.2..... Kj.
DE
we achieve a tight upper-hound for the query Ep* [b([ w.r.t g P.
E.2
Proof of Proposition
Consider the objective of Theorem 2;
θ
arg max
Σ Evww) P(;
(52)
@:(01, _.......*
_00
vlw
s.t. 0 = By,
Vi,j E (1,2...., VV $ A.j
0' arg max
Σ
log P(v;0), vie {1, K}.
me Di
No need to parameterize non-ancestors of W. Let V\Ang* (W). By applying Rule 3 of a-calculus [9] we realize that,
P(w: (. 07,) = P(w; 0 (V.T))))
(53)
The latter indicates that the parameters (0f are irrelevant to the joint distribution P(w), and therefore, be dropped from the NCMs used for partial transportability of Eps (W)] En p* (ww) (Ww).
Let A Anga (W). We drop the non-ancestors, and rewrite the objective as follows:
θ^ arg max
Σ (ww) Σ P(a; 0*)
(54)
0A:(0 .0
OK 0
a'w
s.t. 0r of
VV $ Ais Vi,j (1,2....,
0¹A arg max
Σ
log P(a;OA), Vie {1, 2, K}.
D
Next, add the likelihood terms the main objective regularized by coefficient A to achieve single-objective optimization.
K Σ Ev(w): Σ P(a; 0*) +A. Σ Σ log P(a; 0%)
θ^ E
arg max
(55)
θ ( .2.....
00 10
ae
s.t. 8 By
Vi 21,2,...
K,+} VV A
29

---

For A - s, the new optimization problem matches with that of Thm. 2. Now, we focus on the likelihood expression, and rewrite following causal order of g*, namely, A A2 AN.
log P(a: (P))
Σ log P(ai a1-1,-... aa a1:0%) 0%x)
(factorization)
(56)
log BU [P(at v--1...., ,,, 0:O')]
(conditioning U)
(57)
Σ log UUA LP(a pa 0A
(Rule 1 of do-cale)
(58)
Σ log UU, [P(a) A. UA
(Rule 3 of do-cale)
(59)
1 Let {A be the c-components of GaAp which is the graph induced by nodes A. We rewrite the above objective in terms of the c-factors:
log P(a: 0%
log Bu [P(a ya UA: 0%
(c-factor decomp.)
(60)
A
log
IT AEA,
Bu, [P(a pa Un: UA)
(sum-of-log to log-of-prody
(61)
log EU
I P(a po UAi 61)1 (mutually indep. UA)
(62)
AcA,
log P(ay do(pa A, ): 0a
(trunc. fact. prod.)
(63)
From the last expression, we can observe that the NCM parameterization modular w.r.. the c-components, Rahman et al. [28] also discusses. We rewrite the full optimization program again:
m
arg max @A 82 ax gh)
Σ expl Σ
log P(aj do(pa pa a, a,)::% 0);0)) +((a)
(64)
K
Σ aDED
log P(aj dd)
(65)
s.t. 0 By.
Vi.j E , K,*} VV A
Let A, be c-component that S, is not pointing to it in ii., Aj n Ø. The latter means that the parameter sharing 0t 0% is enforeed for all V Aj; we call these parameters 0AA We notice that 0¹ only appears through the term log P(a,) do( (o(pa A;); 0;) in the score function; once in the main objective as 0% and once in the regularizer as 0'A, For A - co, the regularizer enforces gi to satisfy the following criterion: A,
gi.*
E arg max A;
Σ
log P(ay do(po A;)0AA
(66)
BAj
ajED*
This criterion is in fact an interventional (I.2) constraint [41] enforced on 0%,², that requires 0 to approximate P'(a; do(p" (,) )) using the observational data D'. Since P'(a, do)(pa is complete f-cctorr, it is identifiable from Pi(a,, pa A,) [36]. Therefore, by increasing the sample size D - ac and the model complexity of B¹A,- satisfying the criterion in Eq. 66 guarantees arbitrarily accurate approximation of the interventional quantities Pi(a, do(ppa A,)) [41]. This implics that replace the terms involving the parameters 0¹,²* with any consistent approximation
30

---

of Pi(a do(pa )) as constants. To get the approximation, we are free to use any probabilistic model and architecture depending on the context; this includes the option to train the NCM parameters A, in the pre-training.
This adjustment gets us to the exact procedure pursued Algorithm 1, thus proves consistency of with what would achieve via Theorem 2.
E.3
Proof of Theorem 3
For this proof, it is useful to define the worst-case risk w.r.t. the selection diagram and the source distributions.
Definition (Worst-case risk). For selection diagram G and source distributions P. the worst-case risk of classifer Qx fly is denoted by Rga p(h) and defined as the solution of partial transportation task for the query pp [(Y, (Y, h [)], where L(y, 5) is a loss function. Formally,
(g), =
R tuple SCMs Mo that entails induces ga p (h).
max
(67)
Theorem 3 (restated). For discrete X, Y CRO terminates. Furthermore, for large enough data across all source domain, the worst-case risk of CRO at most away from the worst-case optimal classifier w.r.t. selection diagram g and source data I.. Formally,
lim P(Rgap((e phe (RO) n-=00
min R c) -0
(68)
10x Sy
where CRO = CRO(D,, g and Dn = (D), D2 , ,R> is collection of datasets that each contain at least n. datapoints.
Proof. Soundness of CRO relies on consistency of Neural-TR (Alg. as subroutine; we pick the data size large enough to satisfy this condition according Theorem 2.
Termination. Let 07 03 ... be the sequence of target NCMs produced during the runtime of CRO, and let h1, /2..... be the sequence of classifiers obtained after each iteration. Let II denote the space of all distributions over X, Y. For discrete X, Y, the space II is compact subspace of some Euclidean space. Thus, every sequence in II has a convergent subsequence, especially the sequence [P(x, (%)),. II; let (Pi), be this convergent subsequence. Every convergent subsequence is Cauchy, which means,
Vr 0 in 0 V1,1 > n: d(P Py) t,
(69)
where d is an appropriate metric over the probability space. Choose t small enough w.r.t the convergence tolerance 8 ensure.
VP. P' where d(P, <T = vh Ωx - By [R((h) - Rp)(h)) <
(70)
The above possible, since the mapping (h) is a bounded and continuous mapping on the space I1. Now, we are guaranteed to find an index ( such that,
R [R(ee.r (11) - R R (hi) < 6.
(71)
Notice that by definition, 0+ is obtained by Neural-TR (Alg. 1) attain the worst-case risk of his i.e.,
R R (ha) Rga,e(hi)
(72)
Moreover,
R R (hr) & max RD (hi)- Putting the last three equations together we have,
(73)
(5.1......!)
(hi, is (e(1.2....)
max RD 6,
(74)
which invokes the termination.
31

---

Worst-case optimality. Suppose h. CRO is returned by CRO, and let h* be the true worst-cass optimal classifier defined as,
h fuflx-sty
min (g),p(h).
(75)
Let IDD denote the collection of datasets collected by the algorithm before termination. We know that h &COO is robust to D i.e..
(D CRO) ope. A CRO
h CRO
arg min max (b) k:lx Syy DED*
max DE
max
(D()*)
(76)
DE
Moreover, every distribution D* entailed by an NCM that represents a possible target domain. Therefore, the worst-case risk is at least as large the worst-case empirical risk on the set of distribution DD, i.c.
max RD(h*) p())((h))
(77)
DeDs
Since that algorithm has terminated we have,
Rga p(h (RC) < max
(D CRO) +
(78)
DE
where 5 >> O is the tolerance for the convergence condition in the algorithm. Putting all inequalities together, we have,
Rga,r(h (RO < max RD(h CRO)
(79)
DED*
max Rn(h**
(80)
DE
E (h*)(("))
(81)
which indicates that the worst-case risk of CRO is at most 5 larger than the optimal worst-case risk.
F Broader Impact and Limitations
Our work investigates the design of algorithms and conditions under which knowledge acquired in one domain (e.g.. particular setting, experimental condition, scenario) can be generalized a different one that may be related, but is unlikely to be the same. As alluded to in this paper, issues and the difficulty of stating realistic assumptions that are conducive extrapolation guarantees are pervasive throughout the data sciences. Our hope is that our analysis with more surgical encoding of structural differences between domains that allow the empirical investigator to determine whether (and how) her/his understanding of the underlying system is sufficient to support the generalization of prediction algorithm is an important addition towards safe and reliable AI. This approach is not without limitations, however. We have shown that selection diagrams consistent domain generalization (through bounds instead point estimates) but arguably restrict the analysis to narrow class of problems graphs or super-structures need to be defined. This stands in contrast with representation learning methods that operate on nigher-dimensiona, spaces, e.g. text, images, which are difficult reason about in a causal framework. The trade-off is that guarantees for consistent extrapolation are difficult to define and that one-size- fits-all all assumptions are difficult to justify in practice. Partial transportability may be understood as complementary view-point on this problem, applicable in a different class of problems in which structural knowledge is available implying that non-trivial guarantees for extrapolation can be established. Pushing the boundaries of methods based on causal graphs to reach compelling real-works applications is arguably one the most important frontiers for the causal community whole. In this work, there is scope for improving posterior estimation and for introducing assumptions on the class of SCMs that are modelled, e.g. linear Gaussian models, etc., that could lead efficient predictors in higner-dimensional spaces. Similarly. relaxations of selection diagrams, e.g. in the form of equivalence classes or partially- known graphs, could be developed for applications in domains where knowledge of graph structure is unrealistic.
sufficient to ensure
32

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Please see the contribution bullets.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See appendix F.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
33

---

Justification: All proofs are provided in the appendix with more detailed restatement of the theorems and needed assumptions.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [No]
Justification: The code will be accessible through git-hub after publication. We ensured that the results are reproducible; please see Appendix B.3 for some details the used architecture.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
34

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
Code is provided.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines tbttps://nippe cc/
public/ guides/CodeSubmi cemmmissioonn ssionsolccyyyyycooooooooooooiiic for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: i mnsps. cc/publiccccccccccccpccccccccc c/gu des / CCodeooduubooo ss onPol cyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: See the corresponding examples for each experiment, and the reproducibility note in B.3.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[NA]
Justification:
All the examples are small, so it is not applicable.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
35

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: All experiments were executed on a Macbook Pro M2 GB RAM.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http///eurrippp cc httpaa/pppp...pp...e//eee....a.e
Answer: [Yes]
Justification:
We respect NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
See appendix F.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
36

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work is theoretical and bears no such risk.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All related and used results are cited properly.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, papers nraw aw! thcode com dat set. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
37

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The code is annotated and provided.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
38


Reviews:
[{"review_id": "rwoQvQdBGq", "reviewer": "Reviewer_S6HF", "summary": "This paper studies the problem of domain generalization through the lens of partial transportability, and introduces some new results for bounding the value of a functional of the target distribution, given data from source domains and assumptions about the data generating mechanisms.  Authors adapt existing parameterization schemes such as Neural Causal Models to encode the structural constraints necessary for cross-population inference. Some experiments and examples are also provided.", "questions": "Based on my understanding, authors consider bounding the queries of generalization errors in non-transportable settings, by obtaining a bound for the worst-case losses. Authors use the formulation of canonical  models as a way of encoding constraints to derive such a bound. \n\n1. I believe there are existing works that assume some prior information regarding target domain and then derive bounds for the target loss in DG problems. If my understanding is correct, then I would like to treat the current work as **an alternative way** of encoding information about the target domain. Then the current way of presentation and organization indeed make  it complicated to understand the paper. In particular, I feel that examples 1 and 2 somehow distract reader's attention, while it is better to directly formulate the central problem of the paper. \n\n2. Other questions: \n   1. line 125:  what does $j$ indicate in the notation $S_{ij}$?\n   2. definition 4: is there any constraint on $q_{max}$ ? there may exist trivial but useless upper bound for some loss functions.\n   3. Suggest give more introductions about canonical SCM, to make the paper more self-contained.\n3. about Colored MNIST experiment: I don't get how this experiments serves. Do you want to show the proposed bound is correct? However, there is no mention of the value of $R_{P*}(h)$ here.", "limitations": "see above.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Introducing partial transportability and canonical SCM to domain generalization is novel.\n\n- The theoretic results are sound and have complete proofs. They are potentially useful.", "weaknesses": "- The paper organization and presentation seem complicated to convey the idea of the paper (see below).\n- It is not clear how this bound can in turn help improve general DG problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review, we appreciate the positive feedback. In the following response we address comments and concerns pointed out by the reviewer. Please let us know if we can help clarify any part of it.\n\n> **Q 1.1.** *The paper organization and presentation seem complicated to convey the idea of the paper (see below). I believe there are existing works that assume some prior information regarding target domain and then derive bounds for the target loss in DG problems. If my understanding is correct, then I would like to treat the current work as an alternative way of encoding information about the target domain.*\n\nThe current work (and the field of causal transportability as a whole) can be interpreted as a more general version of the transfer learning problem that operates using qualitative information about the commonalities and differences among the causal mechanisms of different domains (instances are [3,4,9,16,22] in the paper). As the reviewer suggests, other lines of research make different types of assumptions. One alternative is invariance learning methods, mentioned in the introduction, that exploit statistical invariances to induce robustness guarantees. We make sure to include more details in the related work section of the Appendix.\n\n\n> **Q 1.2.** *Then the current way of presentation and organization indeed make it complicated to understand the paper. In particular, I feel that examples 1 and 2 somehow distract reader's attention, while it is better to directly formulate the central problem of the paper.*\n\nPlease notice that introducing Def. 4 earlier in the manuscript is challenging since it involves notions of transportability and partial identification. We believe that Examples 1 and 2 can be a useful for contextualizing the problem for the general reader and illustrate the definition of domain discrepancies, selection diagrams, etc. to set a common ground for discussing the challenge of the domain generalization problem.\n\n> **Q 1.3** *”It is not clear how this bound can in turn help improve general DG problems.”*\n\nThank you for this question. \n\nInterpreting your question literally: “How does the bound returned by Neural-TR in Alg. 1 help improve the task of learning a predictor with robustness guarantees?” The bound improves general DG in the sense that Neural-TR is used explicitly by CRO in Alg. 2 that provably returns a predictor with optimal worst-case performance. In other words, finding the worst-case performance of predictors gives us a basis for comparing them, and eventually finding the one with the minimum worst-case risk, through CRO.\n\nInterpreting your question at a higher level: “How practical is CRO and its assumptions in real-world problems of domain generation?” We could start by noting that to solve any instance of the domain generalization problem, some notion of relevance between target domain and the source domains is required – as if domains are allowed to be arbitrarily different, transfer learning would be impossible. The advantage of CRO in practical problems is that it is completely non-parametric, making no assumptions on the distributional family of the variables involved. Moreover, selection diagrams only require the qualitative specification of commonalities and discrepancies across domains without needing to specify the underlying functional form of the domains. \n\nIn case we didn’t fully grasp the intended meaning of “general DG”, could you please rephrase your question?\n\n> **Q 2.** *”Other questions: line 125: what does j indicate in the Sij notation? definition 4: is there any constraint on q_max? there may exist trivial but useless upper bound for some loss functions. Suggest give more introductions about canonical SCM, to make the paper more self-contained.”*\n\n$S_{ij}$ should read $S_i$, apologies for the typo. Def. 4 does not constrain $q_{max}$ a priori. Indeed, trivial upper bounds exist for all problems, e.g. fix $q_{max}$ be the upper end-point of the range of the loss function.  Note that $q_{max}$ obtained by the Neural-TR algorithm is guaranteed to be a tight bound in the limit, meaning that there exists no better (valid) upper bound, as shown in Thm. 2.\n\n> **Q 3.** *“about Colored MNIST experiment: I don't get how this experiments serves. Do you want to show the proposed bound is correct? However, there is no mention of the value of R_P* here.”*\n\nThe motivation behind the Colored MNIST example is to compute the worst-case risk of different classifiers, as characterized by the source data and the selection diagram; these classifiers in our experiments are ERM and IRM, but the same analysis applies to any arbitrary classifier. The upper-bound for the risk (i.e., the worst-case risk) that is obtained with Neural-TR procedure, as suggested by Thm. 2, is asymptotically tight.\n\nIn our analysis, we report in line 343 the value $R_{P^*}(h)$ of the classifiers $h:=\\\\{h_{ERM},h_{IRM}\\\\}$ on the worst-case $P^*$ found by Neural-TR. In addition, we supplement this analysis with an evaluation of CRO's classifier on all datasets. Those experiments are described and reported in the global rebuttal. In short, our experiments on evaluating CRO for simulated examples and on the Colored MNIST examples highlight the fact that CRO's output has the best worst-case risk among all classifiers, and its performance is contrasted to ERM and IRM.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5X9M2DMKKv", "reviewer": "Reviewer_fw9Z", "summary": "The paper extends the formulation of canonical models to encode the constraints for the transportability tasks. Then it adapts Neural Causal Models for the transportability task and introduces an iterative method Causal Robust Optimization to find a predictor with the best worst-case risk.", "questions": "1. What does $\\bigoplus$ mean?\n2. Could you provide some experimental results for CRO and also compare it with other algorithms?", "limitations": "The authors have adequately addressed the limitations.", "rating": 6, "confidence": 1, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "- The paper presents a unified framework for addressing transportability problems using canonical models and neural causal models. These transportability problems are broad and highly relevant in the field of machine learning.\n- I appreciate the examples illustrated throughout the main text, as they greatly help the reader understand the definitions and intuitions.\n- The theorems are solid and the experiments align well with the theories.", "weaknesses": "Disclaimer: I am not familiar with this field, so my observations and suggestions are based on my general understanding on the paper.\n\n- Some definitions are not provided, making it difficult for readers to understand certain parts of the paper. For example line 133, 134 $\\bigoplus$.\n\nMinor:\n1. Page 1 line 9, “such as”.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the positive assessment of our work, thank you. The following response answers each question sequentially. We would be happy to expand on it if needed.\n\n> **Q 1.** *”Some definitions are not provided, making it difficult for readers to understand certain parts of the paper. For example line 133, 134 (xor operator)”*\n\nThe $\\bigoplus$ denotes the xor operator: $A\\bigoplus B$ evaluates to 1 if $A\\neq B$ and evaluates to 0 if $A=B$.\n\n> **Q 2.** *”Could you provide some experimental results for CRO and also compare it with other algorithms?”*\n\nYes, thank you for this suggestion. We have added experimental results for CRO for all experiments, including for the synthetic simulations (Examples 2 and 3) and for Colored MNIST. This analysis is provided in more detail in the global rebuttal and attached pdf, with figures describing the learning process of CRO as well as explicit comparisons with baseline algorithms. As a summary, recall that the CRO algorithm uses Neural-TR as a subroutine to iteratively enhance a classifier and arrive at the best worst-case classifier. In our experiments, CRO converges in 4 iterations or less. In both the simulated and the Colored MNIST experiment we verify in every case that CRO achieves the best possible worst-case performance (known in these examples by construction), as suggested by Thm. 3.\n\nWe also note that the poor performance of the baseline algorithms should not be blatantly compared to that of CRO, since CRO has access to background information that can not be communicated with the baseline algorithms. In this sense, CRO can be viewed as a meta-algorithm that operates with a broad range of assumptions encoded in a certain format (i.e., the selection diagram), while the baseline algorithms lack this capacity, and therefore, CRO is able to find the theoretically optimal classifier for domain generalization while the baseline algorithms fail to achieve that and perform poorly in the worst-case scenario.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "R9NTIA3O6D", "reviewer": "Reviewer_SwAx", "summary": "This paper tackles to problem of transportability in domain generalization. Multiple datasets are provided together with graphical information stipulating which causal mechanisms are shared across domains and which mechanisms are going to remain invariant in the target domain. The goal is then to estimate the error committed by a given classifier in the target domain. More specifically, the authors propose a way to estimate the worst-case error of the classifier given the observed distributions as well as the graphical information. A first result shows how the problem can be simplified using canonical SCMs and a second result shows how Neural Causal Models (NCM) can be used to estimate this bound. Furthermore, an approach named Causal Robust Optimization (CRO) is proposed to learn a classifier that minimizes the worst-case risk. Experiments experiments with the NCM approach to estimate the upper-bound of various classifiers, but does not tackle the CRO approach to learn a robust optimizer.", "questions": "See above.", "limitations": "I didn't find any discussion of the limitations of the approach in the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper reads nicely (even for a fairly technical paper) and gives a good background on SCMs and graph terminology for the non-expert. The choice of notation is good and remains consistent throughout the paper.\n- The problem appears to be very important, and the approach to tackle it seems principled.\n- The approach appears to be novel and interesting. However, I don't have a good knowledge of the literature on transportability and domain generalization and thus my judgment's credibility is limited.\n- Many examples are provided to make the discussion more concrete, I enjoyed that.", "weaknesses": "- Some theoretical results, in their current form, seems unlikely to be true. Specifically in Theorem 2, I was surprised to see that this result does not mention anything about the expressive power of the NCM, what if the neural networks do not have enough capacity to express the causal mechanisms? Clearly what you would end up with wouldn’t be an upper bound right? I was also surprised to see that the optimization problem is formulated in a finite-sample fashion, but the conclusion concerns the actual expectation (i.e. not finite-sample), this sounds unlikely, no? Don’t you need to take a limit as the dataset grows for this bound to hold?\n\n- Confusion surrounding canonical SCM: At line 181, it is mentioned that [41] showed that every SCM M can be written in a canonical form (with discrete exogenous variables)... However, after quickly skimming through the paper, I could not find something resembling that statement. What am I missing? Overall I thought the discussion on canonical SCM was confusing. I’m left unsure as to which type of SCM can be cast to a canonical form (definition 5) and which paper showed this fact.\n\n- Some section were hard to parse. Mainly lines 270 to 289, including Algorithm 1. I'm not sure I got the point. I was following up to that point. I give some minor suggestions to improve clarity below.\n\n- Algorithm 2 (Causal Robust Optimization) is interesting, but it looks quite costly. Do the authors believe it could be made applicable? I was a bit disappointed to see it was not implemented in the experimental section. It would be nice to have experiments for CRO. Could this approach be applied to the Coloured MNIST dataset?\n\n- The background is very well written, but the end of the paper felt a bit less polished. Since these are the most important part, I believe they deserve more space. For instance, I had a hard time understanding the experiments with colored MNIST. \n\nMinor:\n- Example 1: Why using arrows for assignment? The symbol “:=” was used earlier…\n- Definition 3: Should S_{ij} be in fact S_i here? (line 125)\n- Example 2: Long sequences of “if”s would benefit from some punctuation. The “circled plus sign” is an XOR right?\n- Definition 4: Might be helpful to spell out \\mathbb{M}_0 completely in (4), since \\mathcal{M}^*_0 appears in the expectation but is not defined (the reader has to deduce that this is the target SCM belonging to  \\mathbb{M}_0) \n- Definition 5: might be useful to end with “where h_V^{(r_V)} is a function from supp_{pa_V} to supp_V”. I’m actually not certain the very last sentence adds something to the definition, since it is already obvious that f_V(pa_V, r_V) is a function of pa_V for all r_V… I’m also a bit confused by this sentence: “The set of endogenous variables V is discrete.” What does it mean for a set to be discrete? Do you mean the endogenous variables are discrete? Also, I’m a bit confused by the way the word “support” is used here. Usually it means the set of values for which the random variable has positive probability (at least for discrete variables that’s the definition), but here I believe this is not how “support” is used, correct?\n- Theorem 1: I believe the first constraint should not include the case i = *, no? I thought P* was not observed. In fact, you don’t have the case i=* on line 248 and in Theorem 2\n- Figure 1 is unclear, what does the color mean?\n- Line 353: Bayesian inference procedure?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the time and effort for reviewing our paper and the positive assessment that our paper “reads nicely”, “the problem appears important” and that our approach is “principled”. Please find below our response to the review, and let us know if you have any further concerns.\n\n> **Q 1.** *”Theorem 2, expressive power of the NCM. Don’t you need to take a limit as the dataset grows for this bound to hold?”*\n\nThank you for raising this point. The claim of Theorem 2 holds in the limit of data from the source domains, and increasing expressivity of the feed-forward Neural Networks that parameterize the NCMs. This fact was more clearly stated in the proof of Theorem 2 (line 610 and 615) and we will correct the statement in the main body of the paper, thank you for pointing this out. \n\nAs an additional observation, we could note that with finite data (provided that the Neural Networks are expressive enough) we would achieve a valid upper bound, since the set of SCMs compatible with finite data is a superset of the set of SCMs compatible with the underlying distributions. The important distinction, however, is that with finite data the bound will not be tight in general.\n\n> **Q. 2.** *”Confusion surrounding canonical SCM: At line 181, it is mentioned that [41] showed that every SCM M can be written in a canonical form (with discrete exogenous variables)... However, after quickly skimming through the paper, I could not find something resembling that statement. What am I missing? Overall I thought the discussion on canonical SCM was confusing. I’m left unsure as to which type of SCM can be cast to a canonical form (definition 5) and which paper showed this fact.”* \n\nThank you for your careful reading. The reference [41] should be labeled as [42] referring to Zhang et al. “Partial counterfactual identification from observational and experimental data”. Specifically, Theorem 2.4 shows that for any SCM defined over a set of discretely-valued (and finite) endogenous variables, there exists a canonical SCM (as defined in our Def. 5) that is equally expressive, i.e., it generates the same observational, interventional, and counterfactual distributions.\n\nTo answer your question more directly: any SCM over discretely-valued (and finite) endogenous variables can be cast as a canonical model without loss of generality. Having said that, and since this is a fundamental part of the background, we will add a new appendix introducing these results to make the presentation more self-contained.\n\n> **Q 3.** *”Some section were hard to parse. Mainly lines 270 to 289, including Algorithm 1. I'm not sure I got the point. I was following up to that point. I give some minor suggestions to improve clarity below.”* \n\nLines 270 to 289 refer to Example 4 that we use to convey the fact that joint distributions $P^*(\\boldsymbol V)$ may be factorized into several terms (as in line 217). Given the assumptions encoded by the selection diagram and the source data, some of those terms may be point identifiable and evaluated uniquely through the source data, i.e. no bounding necessary, while others may not be evaluated uniquely. More broadly, the point of example 4 is to show that the parameter space can be cleverly decoupled and the computational cost of the optimization problem can be significantly improved: since only a subset of the conditional distributions need to be parameterized and optimized. This component of our work is a contribution over the existing work by Xia et al. 2021 ([35] in the paper) where the entire SCMs are parameterized by neural networks rather than only non-identifiable components. \n\nThis observation motivates Alg. 1, that (1) decomposes the query, (2) computes the identifiable components, and (3) parameterizes the components that are not point identifiable, and then proceeds with NCM optimization. We have added a more thorough discussion and illustration of Alg. 1 in the Appendix.\n\n> **Q 4.** *”Algorithm 2 (Causal Robust Optimization) is interesting, but it looks quite costly. Do the authors believe it could be made applicable? I was a bit disappointed to see it was not implemented in the experimental section. It would be nice to have experiments for CRO. Could this approach be applied to the Coloured MNIST dataset?”* \n\nWe appreciate the suggestion and we have now implemented CRO and conducted experiments on synthetic examples (Example 2 and 3) and Colored MNIST. Please find all performance details in the global rebuttal and attached pdf. We have observed CRO to terminate in less than 4 iterations in all experiments (3 iterations for Colored MNIST) which we believe makes it very practical even in higher-dimensional problems such as image classification.\n\nIndeed, we did not provide any guarantees for the number of iterations it takes for CRO to terminate; the concern about efficiency is quite valid from the theoretical perspective and a deeper analysis would be interesting. \n\n> **Q 5.** *”The background is very well written, but the end of the paper felt a bit less polished. Since these are the most important part, I believe they deserve more space. For instance, I had a hard time understanding the experiments with colored MNIST.”* \n\nWe appreciate the comment. With the additional experiments on CRO and additional space in the camera-ready version of the paper, we will better describe the setting and results of our experiments. Please find a recap of CRO and the colored-MNIST example in the global rebuttal.\n\n> **Q 6.** *”Minor comments.”*\n\nThank you for pointing these out. We will make sure to clarify / correct as required.\n\n> **Q 7.** *\"I didn't find any discussion of the limitations of the approach in the paper.\"*\n\nBroader impact and limitations are discussed in Appendix B.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
In this global rebuttal, we take the opportunity to discuss experimental results of CRO using the figures in the attached pdf as a support.

**Summary.** In the domain generalization task, the source domains $\mathcal{M}^1,\mathcal{M}^2,\dots,\mathcal{M}^K$ ,and the target domain $\mathcal{M}^*$ must be related for any learning to take place. The relatedness of the domains is expressed via a causal graph called selection diagram $\mathcal{G}^\Delta$ that encodes assumptions about the causal structure within each domain, as well as match/mismatch of mechanisms across the source and target domains. The source data $\mathbb{P} = \\{P^1,P^2,\dots,P^K\\}$ together with the selection diagram $\mathcal{G}^\Delta$ characterize the set of SCMs that are compatible as the target domain. Through canonical (Thm. 1) and neural (Thm. 2) parameterization, we implement procedures that obtain an upper-bound w.r.t. $\mathbb{P},\mathcal{G}^\Delta$ for an arbitrary target quantity; a especial case of our interest is the risk of a given classifier $h$ under the target distribution denoted by $R_{P^*}(h)$. This risk upper-bound is tight in the limit of data and expressivity of the parameterization, and represents the worst-case performance of the classifier at hand w.r.t. $\mathbb{P},\mathcal{G}^\Delta$. Neural-TR enhances the optimization procedure by cleverly decomposing the optimization objective, and computing the terms that are readily available from the source data to reduce parameter size and increase sample efficiency. Further, we introduce the CRO algorithm that uses Neural-TR as a subroutine and searches for a classifier with small worst-case risk. We prove that CRO terminates and outputs a classifier ideal for the domain generalization task which has the smallest worst-case risk across all classifiers. Below, we describe in detail how CRO operates.

**CRO.** We start with a random classifier; one might start with an ERM warm-start or any classifier of choice. At the first iteration, we use Neural-TR to compute the worst-case performance of the classifier at hand, witnessed by an NCM that entails the source data $\mathbb{P}$ and induces the selection diagram $\mathcal{G}^\Delta$. Next, we draw samples $D^{*1}$ from this NCM, and add them to a collection of datasets $\mathbb{D}$ that we maintain through the CRO procedure. Finally, we update the classifier at hand to be the minimizer of the maximum [empirical] risk over the datasets in $\mathbb{D}$. Since $\mathbb{D} = \\{D^{*1}\\}$ has only one dataset, the classifier updates to be the ERM of $D^{*1}$. We repeat the above process; at the second iteration, we use Neural-TR again to find yet another NCM that is compatible with  $\mathbb{P}, \mathcal{G}^\Delta$ while it incurs the worst risk on the classifier at hand. We draw samples $D^{*2}$ from this NCM, and add them to a collection of datasets $\mathbb{D}$. Finally, we update our classifier to be the minimizer of the maximum [empirical] risk over the datasets $\mathbb{D} =  \\{D^{*1}, D^{*2}\\}$. The process continues util the maximum risk witnessed by datasets in $\mathbb{D}$ converges to the true worst-case risk witnessed by Neural-TR. 

In the attached pdf, you can find:

- **Figure 1: CRO on Colored-MNIST.** In section 5.2. we discussed Colored-MNIST, an instance of domain generalization task where the learner must classify the digits based on their colored image. The relationship between the color and the label is prone to change across the domains, and classifiers that rely on the color feature fail to generalize. In the two source domains, we intentionally set a high correlation between the color and the digit, thus classifiers that seek optimizing for risk in the source domains inevitably pick color as a determinant feature. We use this example to illustrate both the training process of CRO as well as the performance of the final classifier $h_{\mathrm{CRO}}$. We find that CRO converges in three iterations to an optimal predictor (in the worst-case sense) that ignores the color of the digit and instead makes a prediction based on the shape of the digit. CRO achieves an error of approximately 0.25, as shown in Figure 1d, which is theoretically optimal in this experiment. For comparison, the worst-case errors of ERM and IRM were evaluated to be 0.9 and 0.6 respectively. We also note that the poor performance of the baseline algorithms should not be blatantly compared to that of CRO, since CRO has access to background information that can not be communicated with the baseline algorithms. In this sense, CRO can be viewed as a meta-algorithm that operates with a broad range of assumptions encoded in a certain format (i.e., the selection diagram), while the baseline algorithms lack this capacity, and therefore, CRO is able to find the theoretically optimal classifier for domain generalization while the baseline algorithms fail to achieve that and perform poorly in the worst-case scenario.

- **Figure 2: CRO on Examples 2 & 3.** Examples 2 and 3 are synthetic instances of the domain generalization task that are small enough to be analyzed in fine granularity. In Example 2, three classifiers are considered (Table 1); total feature set, causal feature set, and non-causal feature set. Surprisingly enough, the non-causal feature set yields the best risk in the held-out domain. In Example 3, we considered a simple example with binary $X$ and $Y$. In this example, the considered classifiers are $0,1,X,\neg X$. Using Neural-TR, we compute the worst-case risk of considered classifiers in both examples, as reported in Figures 4a \& 4b in the original manuscript, and 2b \& 2d in the attached pdf. We also run CRO in both examples, and find that it discovers the best worst-case classifier in both examples; non-causal feature set in Example 2 and $\neg X$ in Example 3. Figures 2a \& 2c in the attached pdf demonstrate runs of Neural-TR for the classifier generated by CRO.

Meta-review: This paper presents a novel and principled approach to addressing transportability problems within domain generalization. The theoretical results are sound and potentially useful. Given the positive feedback from all reviewers, I recommend this paper for acceptance.
Decision: Accept (poster)