Achievable distributional robustness when the robust risk is only partially identified
Authors: Julia Kostin
Nicola Gnecco
Fanny Yang
Venue: NeurIPS 2024 poster (2024)
Keywords: distributional robustness
domain generalization
causal inference
partial identification
Primary area: causal_inference

Abstract: In safety-critical applications, machine learning models should generalize well under worst-case distribution shifts, that is, have a small robust risk. Invariance-based algorithms can provably take advantage of structural assumptions on the shifts when the training distributions are heterogeneous enough to identify the robust risk. However, in practice, such identifiability conditions are rarely satisfied – a scenario so far underexplored in the theoretical literature. In this paper, we aim to fill the gap and propose to study the more general setting of partially identifiable robustness. In particular, we define a new risk measure, the identifiable robust risk, and its corresponding (population) minimax quantity that is an algorithm-independent measure for the best achievable robustness under partial identifiability. We introduce these concepts broadly, and then study them within the framework of linear structural causal models for concreteness of the presentation. We use the introduced minimax quantity to show how previous approaches provably achieve suboptimal robustness in the partially identifiable case. We confirm our findings through empirical simulations and real-world experiments and demonstrate how the test error of existing robustness methods grows increasingly suboptimal as the proportion of previously unseen test directions increases.

Achievable distributional robustness when the robust risk is only partially identified
Julia Kostin Department of Computer Science ETH Zurich jkostin@ethz.co ch
Nicola Gnecco
Fanny Yang
Gatsby Computational Neuroscience Unit University College London nicola. gnecco@gmai....c..oo.mmmm com
Department of Computer Science ETH Zurich fan. yang@in.. www.ggiif.eth...... ch
Abstract
In safety-critical applications, machine learning models should generalize well under worst-case distribution shifts, that is, have small robust risk. Invariance- based algorithms can provably take advantage of structural assumptions on the shifts when the training distributions are heterogeneous enough to identify the robust risk. However, in practice, such identifiability conditions are rarely satisfied scenario so far underexplored in the theoretical literature. In this paper, aim to fill the gap and propose to study the more general setting of partially identifiable robustness. In particular,
define new risk measure, the worst-case robust risk. and its corresponding (population) minimax quantity that is an algorithm- independent measure for the best achievable robustness under partial identifiability. We introduce these concepts broadly, and then study them within the framework of linear structural causal models for concreteness of the presentation. We use the introduced minimax quantity to show how previous approaches provably achieve suboptimal robustness in the partially identifiable case. We confirm our findings through empirical simulations and real-world experiments and demonstrate how the test error of existing robustness methods grows increasingly suboptimal the proportion of previously unseen test directions increases.
Introduction
The success of machine learning methods typically relies on the assumption that the training and test data follow the same distribution. However, this assumption is often violated in practice. For instance, this can happen if the test data are collected at later time using different measuring device. Without further assumptions on the distribution, generalization under distribution shift impossible. However, practitioners often have partial information about the set of possible "shifts" that may occur during test time, inducing set of feasible test distributions that the model should generalize to. We refer to the resulting set the robustness set. When probabilistic model for these possible test distributions available or estimable, one may aim for good performance on a "typical" held-out distribution using probabilistic framework. When extra information is available or estimable, one possibility is to find model 3 that has small risk R(3; IP) on the hardest feasible test distribution. More formally, we aim to achieve small robust risk defined by
Reob (3) = sup R(3:P),
(1)
DEP
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Comparison of various distributional robustness frameworks and what kind of assumptions
their analysis can account for (with an incomplete list of examples for each framework).
bounded
partial identifiahility of partial identifiahility of robustness set
Framework accounts for
shifts
model parameters
DRO
[7. 15, 49, 32, 43]
Infinite robustness [35. 17, 30, 39, 6, 2, 46, 54, 28,
Finite robustness [41, 23, 14, 45)
Partially id. robustness (this work)
where Pros (0*) corresponds to the robustness set which depends on some true parameter 0*, In fact, this worst-case robustness aligns with security and safety-critical applications, where a small robust risk is necessary to confidently guarding against possible malicious attacks.
Causality- -rieeted robustness [11, 31, 45] on the other hand is based the idea that some structural parameters (like a graphical structure of the model) remain invariant across distributions, while others may vary. For a given set of training distributions, certain sets of varying parameters induce robust risks that are identifiable. Similarly, for a given set of varying parameters, heterogeneous enough training distributions may identify the robust risk.
In practice, robustness methods aiming at minimizing a pre-defined robust risk often suffer from ineffectiveness. For adversarial robustness for example, it is known that when the perturbations during training and test time differ, the robust risks resulting from adversarial training and standard training may be comparable (see, e.g. [52, 26)). Similarly, unvariance-base methods are often shown to be less robust than vanilla empirical risk minimization that ignores envirieenvroomeentt information. Theoretically, besides being effective only for very specific data-generatee models [1], invariance-baste methods generally are bound to fail when the heterogeneity of the training data is not enough for given set of possible test shifts. Even though this issue of non-identifiability has been pointed out previously [25, 40), prior work so far was primarily satisfied with such a binary statement whether identifiability is given not. We believe that the non-identifiable scenario warrants more detailed discussion. In particular, we aim to formalize how to quantify the best possible robustness for this partially identifiable setting. In particular, we extend the discussion of invariance-basee methods to include the partially identifiable setting, where not only the causal parameter, but the robust risk (1) not determinable using training data either'. Specifically, we aim discuss the following question:
What is the optimal worst-case performance any model can have for given structural relationships between test and training data and how do existing methods compuratively perform in such settings?
When the robust risk is not identifiable from training data, we obtain a whole set of possible objectives that includes the true robust risk. In this case, are interested in the best achievable robustness for any algorithm that we capture in a quantity called the worst-case robust risk:
Rios (3) =
sup possible trae model 8*
sup R(3:P). (E*)
Note that Ryob( (8) is well-defined even when the standard robust risk is not identifiable it takes the supremum over the robust risks induced by all possible true model parameters 6* that are consistent with the given set of training data distributions. Furthermore, the minimal value of the identifiable robust risk corresponds to the optimal worst-case performance in the partially identifiable setting. Spiritually, this minimax population quantity is reminiscent of the classical statistical learning theory [55].2 Even though our partial identifiability framework can be
limits in
'Here, we mean partial identifiability of the robust risk, which is reminiscent of outputting uncertainty sets for quantity of interest in the field of partial identification [50, 18].
IIn particular, extending (2) to its tinie--saple counterpart would introduce a more natural extension of the classical minimax risk statistical learning theory. In this work, we focus on identifiability aspects instead of statistical rates.
2

---

evaluated for arbitrary modeling assumptions on the distribution shift (such as covariate/label shift, DRO, etc.), we present it in a concrete linear setting for clarity of the exposition. Specifically, the setting is motivated by structural causal models (SCMs) with unobserved confounding (ef. Section 2), similar to the setting of IV (instrumental variables) and anchor regression [41, 42]. Concurrently with our work, [24] proposed a framework for partial transportability which is conceptually related to our notion of worst-case robust risk. However, their approach leverages graphical assumptions, i.e., priori knowledge about the structure of causal models, whereas our focus is more agnostic multi-envirommen setting, Additionally, we do not assume a causal data generation process.
The worst-case robust risk (2) not only represents a notion of Aigoritm-inndependen optimality for any combination of training and test shifts. In the linear setting Section 2, we also show theoretically and empirically that the ranking and optimality of different robustness methods change drastically in identifiable vs. partially identifiable settings. The same can be observed in experiments on real-world data. Our experimental results strongly indicate that evaluation and benchmarking on partially identifiable settings are important for determining the effectiveness of robustness methods. Finally, while the worst-case robust predictor derived in the paper is only provably optimal for the linear setting, experiments on real-world data in Section 4 suggest that our estimator may significantly improve upon other invariance-based methods in more realistic scenarios.
2 Setting
In this section, we state the concrete distributional setting on which we introduce our partial iden- tifiability framework. In particular, we consider data generating process, motivated by structural causal models (SCMs), that allows for hidden confounding, i.c., spurious correlations between the covariates X and the target Y. We describe the structure of the distribution shifts occurring in the training and test environments, which is reminiscent of interventions in causal models. Finally, we introduce our framework for distributional robustness that allows for partial identifiability and define the worst-case robust risk for any given model, it corresponds to the maximum robust risk among all possible robust risks induced by the training distributions.
2.1 Data distribution and a model of additive environmental shifts
Data generating process (DGP). We first describe the data-generating mechanism that underlies the distributions of all environments e E & that may occur during train or test time. For each environment E E, we observe the random vector (X,, Ye) P. consisting of input covariates X. E Rd and a target variable Y, E IR which satisfy the following data generating process:
Xe = A +
Y 3 X. E
where Ag Rd, ()) E Rd+1 are random vectors A. P.A. (17,E) ~ pnd with finite first and second moments and for which A. I (n. {) for all e E E.
Invariant mechanism. Note how in this setting, apart from 3 the distribution Pnc of the noise vector (7,, E) remains constant across environments. Without loss of generality, we assume that the noise (77, {) has mean zero. Note how this linear setting is, in general, more challenging than the standard linear regression setting where 1 E: due to possible dependencies between v) and (induced by, e.g., hidden confounding/sparious fealures), classical estimators, such the ordinary least squares, are biased away from the true parameter S*. Denote by Σ* = Cov((n, {)) the joint
covariance of the noise vector (n. which can be written in block form as Σ'
S and which we assume to be full-rank. We then denote the concatenation of these two invariant parameters by 0* = (8* Et) θ Rd x R(d+1)x(d+1) the parameter that remains invariant across all environments.
(o
Structure of the distribution shifts. Note that in the DGP, the distribution shifts between IP-... induced solely by changes in the distribution of the variable Ag, whose mean and covariance matrix allow for degenerate
denote by E [A.] Me and Cov[A.] Σz, respectively. In general, shifts, i.e. the covariance Σ, can be singular. We remark that although the additive shift structure in Equation (3) allows the joint distribution p. P.Y.A.A TP p.. A to change solely via IPA, our distribution shift setting is more general than covariate shift: due to the noise variables 17 and & being
3

---

potentially dependent, both the marginal Pax and the conditional distribution P. P can change across environments.
Training and test-time environments. Throughout the paper, we assume that we are given the collection of training distributions Po PErma _Erroon 3 training environments. We omit 0* when it is clear from the context. Further, for ease of exposition, we assume that Etrain contains a reference (unshifted) environment e = 0 with Ag = a.s. In Appendix B, we discuss how our results apply if this condition is not met. During test time, we expect to observe new, previously unseen distribution Pixs which is induced by the DGP (3) and a shift random variable Aust ~ P.A tostt with corresponding finite mean Mest and covariance Ejest
g* J. where Eerain denotes the index set of
Even though we do not have access to PX during training, the practitioner might have some information about the possible shift distributions IPd test that may occur during test time. As an example, we may only have information about the maximum possible magnitude and direction of the test-time mean shift E [Aea] In this work, we assume that second moment of the shift variable, represented by a positive semidefinite (PSD) matrix Meest ž 0 such that
given an upper bound on the
E Aess " Ejest + MwsHHwst 3 Miest-
(4)
In practice, there may be different degrees of knowledge of the feasible of shifts when no knowledge is available, one can always choose the most "conservative" bound Mrest with the range equal to Rdxd and large eigenvalues. The more information is available, the smaller the feasible set of test distributions would become. On the other hand, when the test distribution P of X is available during training (as in the domain adaptation setting [47]), one can directly compute the optimal shift upper bound via Muest = E [Xtes Xlest ]. In existing literature, Mustt is often proportional to the pooled first or second moment of the training shifts, for instance Miest = 7 Eee Eusin WeMeeli in discrete anchor regression [41] or Miest = Ee (eeMe + E.) in cuusality-orientee robustness with invariant gradients [45]. Here, we are the weights representing the probability of datapoint being sampled from the environment e. As will become apparent in the next sections, our population- level results are not impacted by the distribution of the environment variable, which we thus omit in the following.
We now provide example based on structural causal models (SCM) that falls under the aforemen- tioned distrubtion shift setting.
Example 1. Consider the structural causal model and its induced graph in Figure 1. In this model, the variable Z is soft intervention on the covariates X. Additionally, the exogenous noise vector (Ex,Ev,En and the intervention variable Z are mutually independent. This model is the basis of multiple cousality-oriente robustness works, e.g. [41, 45]. Let 9 = Byx and { = By H + EY. Then, from (5), we obtain Y = Xyx X + (By H + Ex) = XT + E. Suppose that I B invertible and let C == (I B) with entries Cxx,Cxy, etc. Define A Cxx and = Cxx²x + Cxyey + CxHêн. Then, we can write X = A + Since shifts in distribution of Z induce shifts in the distribution of A, collection of interventions {ZeJeEruni translates into a collection of additive shifts environment e. In summary, our DGP Equation (3) includes the classical setting of causality-oriented robustness as depicted in Figure 1.
and gives rise to training distributions varying with the
X
Bxx Byx
BXY
BxH Byн 0
7
+ex
H
Y H
=
0
Y H
+
EY
(5)
0
CH
X
Figure 1: (Left) SCM with hidden confounding and (Right) induced graph. The model allows for an arbitrary causal structure of the observed variables (X, , Y), as long as B is invertible, ie. the underlying graph is acyclic. The shifts across different distributions are captured via shift interventions on X, however, the model does not allow for interventions the target variable hidden confounders.
2.2 The robust risk
Our goal to find an estimator using the training data that has a small risk, in this paper exclusively the expected square loss R(8;1) == Er((Y- 33" =)) over the robustness set. In our setting, given

---

a test shift upper bound Meest defined in Equation (4), the robustness set corresponds to
Pp- (Mrest) yielding the corresponding robust risk that reads
{ 0t,tt test
E Arest
'] Mrest
(6)
Roob (3:0", Meest) ,
=
sup PEP (Mos))
R(3;P).
We call the minimizer of the robust risk 38 == arg min BERs (ra 0*, MMest) the robust predictor. For the squared loss and linear model, the robust risk can be computed in closed form and solely depends on Mist and the invariant parameters f = (3*,"*) )²), and not on other properties of the distributions:
Reob (3,0", MMest) (B* (27 (8 3) +)+ -B) - (at)²
(8)
This observation motivates us define an equivalence relation between two data-generating processes that holds whenever they induce the same robust risk for any model 3 and shift upper bound Myest- Specifically, observe that DGP1 and DGP2 induce the same robust risks for all Mtest and iff 31 = 32 and p = I where denotes equivalence of distributions based on equality of their first and second moments. Thus, in the following, we treat our data-generating process as uniquely defined by 0* up to this equivalence relation.
In practice, the model parameters 0* typically cannot be identified from the training distributions, and the robust risk Roob can only be computed for specific combinations of training and test shifts, studied, e.g., in [41, 45]. In the next section, we describe concepts that allow us to reason about robustness in the case when the robust risk is only partially identifiable.
2.3 Partially identifiable robustness framework
We start by formally introducing the general notion of partial identifiability for the robust risk. The following notion of observational equivalence of parameters reminiscent of the corresponding notion in the econometrics literature [16]:
Definition 1 (Observational equivalence). Two model parameter vectors 01 = -31, En) and 0₂ = (B2, E2) are observationally equivalent with respect
of shift distributions (TA E Etrain) } if they induce the same set Po,E.ran of training distributions over the observed variables (Xe, Ye) as described in Section 2. i.e.
P X.Y
= for all E Etrain-
By observing Po- Euain we can identify the model parameters 0* up to the observationally equivalent set defined as
: 10 (8, E O Po.Eu.in Po- Piraiiiin
In general, observationally equivalent set is singleton, that is, O* is not identifiable from the collection of training environments Ppr.Eu... However, prior work has exclusively considered test shifts Mrett that still allow identifiability of the robust risk nonetheless, depicted in Figure 2a and discussed again in Section 3.2. In this work we argue for analyzing the more general partially identifiable setting, where set-identifiability of the invariant parameter 0* only allows us compute superset of the robustness set
Pen, (Mreat)
= U Po(Messt) Pa (Meeat) O
and correspondingly, set robust risks {Rrob (3; 0, Mteat) : teq In this case, would still like to achieve the "best thest-possible" robustness, that is the test shift robustness for the "hardest-possible parameters that could have induced the observed training distributions.
'The distributions PA are be understood up to the equivalence relation s In general, the distributions PA are unknown, since the shift variables A. are unobserved, However, in our setting. PA can be identified up to the second moment because of the reference environment.
5

---

0
Bo M.a.::."MMammm
Bcg
Bras (B, Mancoen
model parameter space
set of robust risks of B
model parameter space O
set of robust risks of
(a) Identifiable robust risk
(h) Partially identifiable robust risk
Figure 2: Relationship between identifiability of the model parameters and identifiability of the robust risk. (a)
The classical scenario where the test shift upper bound Meest Maea is contained in the span of training shifts so that the robust point- pointideetiffed. (b) The more general scenario this paper, where Miest Munsees contains new shift directions and where only a set can be identified in which the robust risk lies.
Definition (Worst-case robust risk and the minimax quantity). For the data model in Equation (3), the worst-case robust risk defined as
Reob oeg Meest) = sup (3,
The optimal robustness on test shifts bounded by Muest given training data Po Exran is described by the minimax quantity
Otq Miest)
inf Rra (3; Ooq. MLest).
(10)
BERd
When the minimizer of Equation (10) exists, we call the worst-case robust predictor defined by
gzob = arg min (B: Ong: Must)
(11)
In the next sections, we explicitly compute these quantities for the linear setting of Section 2. This will allow us to compare the best achievable robustness in the partially identified case with the guarantees of prior methods in this setting.
Theoretical results for the linear setting
We now compute the worst-case robust risk (9) and derive lower bound for the minimax quantity (10) in the linear additive shift setting of Section We then compare the worst-case robust risk of some existing robustness methods and ordinary least squares (OLS) with the minimizer of the worst-case robust risk both theoretically and empirically.
3.1 Minimax robustness results for the linear setting
The degree to which the model parameters 0* in the linear additive shift setting (3) can be identified depends the number of environments and the total rank of the moments of the additive shifts. For structural causal models, this is well-studied, for instance, in the instrumental variable (IV) regression literature [4, 9]. As we show in Proposition the true parameter 8 can only be identified along the directions of the training-time mean and variance shifts and Σ.. Therefore, if not enough shift directions are observed, 3* merely set-identifiable leading set-identifiability of the robust prediction model (8). More formally, we denote by S the subspace consisting of all additive shift directions seen during training:
Σ LeEE
(Ee motte)
S : range
(12)
and by S- its orthogonal complement. The definition of the space S induces an orthogonal decompo-
sition of the true parameter 8 35 + +55 The identifiable part &s then uniquely defines a set of identified model parameters that reads
g. (BS SSS SS E (oī)²) = (5S, S0S,I0 Er E + 3 (at) + 2(E (5S (0,,E
that can be computed from the training distributions. For the following results, we assume a similar decomposition of the test shift upper bound Mrest which essentially a decomposition into "seen" and "unseen" directions.

---

Assumption 3.1 (Structure of Mest). We assume that Muest Meeen where y 2 0, Maren PSD matrix satisfying range Macen S and R is a semi-orthogonal matrix satisfying range R C S+.
In the next proposition, we show that the model parameters and robust predictor can be identified up to neighborhood around 8
Proposition (Identifibiility of model parameters and robust predictor). Suppose that the set of training and test distributions is generated according to Section 2.1 and Assumption 3.1 holds. Then, (a) the model parameters generating the training distribution (3) can be identified up to the following observationally equivalent set:
mg = + +a, Eq SS Eja, (o -2a E
ToTT + +a T E a st ;0 (13)
(b) the robust predictor 35 as defined in Equation (8) is identified up to the set
n (B + (Miest + - + (Meest + 21) range R} e 3800
(14)
where Begg = {Bgob: : E Ooa)-
The proof of Proposition is provided in Appendix F.1. Proposition implies two well-known settings: If we observe rich enough set P of training environments such that S R the model parameters are uniquely identified, corresponding to the setting of full-rank instruments [4]. From a dual perspective, for a given set of training environments, the robust predictor is identifiable whenever the test shifts are in the same direction as the training shifts, i.e. range M C S and R = 0 this holds even when the invariant parameters are not identifiable and S * Rd. This the setting considered e.g. in anchor regression [41] and discussed again in Section 3.2 and Appendix C.
So far, have described how the identifiability of the robust prediction model depends on the structure of both the training environments (via the space S) and the test environments (via Mtest). ). We now aim to compute the smallest achievable robust loss for the general partially identifiable setting, which allows for R * O. In particular, we provide a lower bound on the best-possible achievable distributional robustness formalized by the minimax quantity (10). First observe that without further assumptions on the parameter space O, the observationally equivalent set is unbounded, and the worst-case robust risk (9) can infinite. The following boundedness assumption allows us to provide fine-grained analysis of robustness in a partially identified setting.
Assumption 3.2 (Boundedness of the causal parameter). There exists constant C >>> 0 such that any parameter 33 in the DGP (3) is norm-bounded by C, i.e. || S.C. C.
Furthermore, define Oket VC2 2 ||8S|2 the maximum norm of the non-identified part of the linear parameter B*. Finally, recall that the reference distribution P.X.Y observed and hence identifiable.
Theorem 3.1. Assume that the training and test data follow the data- eatta-generating mechanism in Section 2.1 and Mues satisfies Assumption 1 for some Maceny R with range Maeen C S, range R C S'. Further, let Assumption 3.2 hold with parameter C. The worst-case robust risk (9) is then given by
(B; Deq: Mies)) = (Oker + || 8112) + +888 -3) " (3S - R(
X.Y. (15)
The minimax quantity in Equation (10) is lower bounded as follows:
My Mrest) { = /C2 ker + min $=0 Riob (3; 0$ >Mooen), if 2 Tni else,
(16)
/C minser" ( (3; 0 Mscon),
(M(E))+))JRRT DE Moreover, for small unseen shifis
where Tht
Cher
lim Mc Mist.) (Oker + |RR Ex 2
(17)
"x denotes the conditional number of the covariance matrix >";
7

---

We prove Theorem 3.1 in Appendix F.2. First, in the case of no new test shifts where y' = 0 (as it appears in prior work [41, 45]) we can plug in the robust risk Equation (7) into Equation (16) to observe the following: as the strength of the shift grows, the optimal robust risk saturates. On the other hand, if * O, i.e., the test shift contains new directions w.r.t. to the training data, the best achievable robustness Wi(()e have tight expression for the minimax quantity and the worst-case robust predictor Agol, can be explicitly computed (ef. Appendix F.2) and is orthogonal to the space range R of non-identifiable test shift directions. In other words, for large shifts in non-identified directions, the optimal robust model would "abstain" from prediction in those directions. For smaller y'. S gradually utilizes less information in the non-identified directions, thus interpolating between maximum predictive power (OLS) and robustness w.r.t. new directions (abstaining). The model & is a population quantity that is identifiable from the collection of training distributions. When only finite samples available, we discuss in Appendix D how we can compute the worst-case robust estimator by minimizing an empirical loss function that can be computed from multi-enviromment data.
eq: Mest)) grows linearly with y' Further note that for 7 2 2hh we
3.2 Theoretical analysis of existing finite robustness methods
We now evaluate existing finite robustness methods in our partial identifiability framework and characterize their (sub)optimalltyy in different scenarios. A spiritually similar systematic comparison of domain adaptation methods is presented in [12], however, in our setting, the robust risk is not identifiable from data. Concretely, we compare discrete anchor regression [41] and pooled OLS estimators with the minimax quantity in Theorem 3.1. We consider the same scenario in discrete anchor regression, which is a the specific case of the setting in Equation (3), where for each environment e, A. is just mean shift with variance O. In addition, discrete anchor regression assumes that the environment variable F E Etrain follows a probability distribution with IPE = e] = We- The discrete anchor setting then corresponds setting a test shift upper bound Meet Manchor for some 7 > 0 (cf. Equation (4)) with Manchor = Enefunin WeMeele. The (oracle) discrete anchor regression estimator minimizes the robust risk and reads
fanchor = arg min (2; (
(18)
BERd
The pooled ordinary least squares (OLS) estimator BoLs corresponds to fanchar with 7 = 1. We observe that the test shifts bounded by yManchor are fully contained in the space of identified directions S, since S = range Leedigan MeMe = range Manchor. Thus, according to Proposition I, the robust risk and robust predictor Banchor are identifiable for all y > O. In the next corollary, we compute worst-case robust risk of both Bagchor and BOLS with respect to the more general shifts bounded by Miest == 7 Mauchor + Y/RR", thus possibly including unseen shifts consisting of additional unseen shifts range R C CS..
Corollary 3.2 (Worst-case robust risk of the anchor regression estimator). Assume that the test shift upper bound is given by Mest := Manchhr + Let trein. E. w.P.X.Y be the pooled training distribution. Then the general worst-case robust risk is given by
RBob((; Oeq, Muest) = (Ckerr + ||TT B112) + ( (1- 1)(88
T) Manchor (8 33) + R(B, R XY
Furthermore, the the anchor and OLS predictor, respectively, it holds that there exists constants Ci, C22 C3 independent of T, such that
Riob Rrob (Banchori Oeqp Mrest) = (Oxer ||R (2 + MMnnhhr
-1255 10 + c1i
Rrob (BOLs: Oeg; Meest) = (Oker || |RR (E; + Manchor)
155
111 + C2. mis
In contrast, the best achievable robustness reads
(M Mrest) = Char + C3. if 2 Thin
lim M( MMess) )/7 (Cker + ||RR (E) + Mauchor )
m 1))²
'In Appendix C we show that analogous results hold for continuous anchor regression and the method of distributionally robust invariant gradients (DRIG) [45].
8

---

Observe that the worst-care robust risk in the extended anchor regression setting is equal to the anchor regression risk with an additional coniieetifiability penalty term y' || 3l12)² The anchor regression estimator is optimal in the limit of vanishing unseen shifts but (for any 7) significantly deviates from the best achievable robustness for larger unseen shifts y 2 V/a- Moreover, case of completely new shifts (7 = 0), pooled OLS and the anchor estimator achieve the same rate in Y', showcasing how finite robustness methods can perform similarly to empirical risk minimization if the assumptions on the robustness set are not met. We provide additional performance comparisons for the more general shift in Appendix C and the proof the corollary in Appendix F.3.
Experimental results
In this section, we provide empirical evidence of our theoretical conclusions in Sections 3.1 and 3.2. In particular, we compare the prediction performance of multiple existing robustness methods the (estimated) minimax robustness in identifiable and partially identifiable settings. We observe that both on synthetic and real-world data, in the partially identified setting, empirical risk minimization and invariance-basse robustness methods not only have significantly sub-optimal test loss, but also perform more similarly, thereby aligning with our theoretical results in Section 3.2. This stands in contrast to the identifiable setting, where the anchor predictor is optimal up to finiee effects. Furthermore, we observe that even though the minimizer of the worst-case robust risk is optimal only for the linear causal setting in Section 2. it surprisingly outperforms existing methods in real-world experiment.
Experiments on synthetic Gaussian data We simulate Gaussian covariates according to Equa- tion (3) with multiple environments differing by linearly independent randomly selected mean shifts. For a randomly sampled collection of mean shifts, we evaluate a proxy for the worst-case robust risk by picking the most adversarial (8+, 2 ) for the shifts, and then computing its robust risk (7). We describe the full details of the data generation and loss evaluation in Appendix E.1. We consider the identifiable case in (see Figure 2a), the test environment is only perturbed by bounded shifts in training directions with increasing strength 7, as considered in prior work [41, 45]. In the non-identiffable case (see Figure 2b), the test environment is perturbed by a mixture of training shifts and shifts in previously unobserved directions, where 7 is fixed and 7 varies (cf. Assumption 3) We compute the empirical minimizers BoLS, Banchor and S of the OLS, anchor regression and worst-case robust losses, respectively, and compare their worst-case robust risk (mean squared error) in Figure 3. In the identifiable setting - Figure 3 (left) - the robust risk is asymptotically constant across y for both robust methods, while the error for the OLS, vanilla ERM, estimator increases linearly. In contrast, in the second, partially identified, setting - Figure (right) all estimators exhibit linearly increasing test errors; however the slopes of the anchor and OLS estimator are much steeper and lead to larger errors than the empirical minimizer of (15) that closely matches the analytic theoretical lower bound.
two shift scenarios:
Identilable case (y' 0)
Partially identifiblle case (fxed y
mo (hea))
15
Methods:
10
Worst-case Rob.
1.00
Anchor
0.75
OLS
0.50
Lower bound
2.5
5.0
10.0
0.5
1.0
2.0
Figure 3: Worst-case robust risk of the baseline estimators BoLS, fanehor (using the "correct" ?), the worst-case robust predictor in (mean-shifted) multi-environmeon finite-sample experiments and thcoretical population lower bound in the classical identified setting with varying shift strength y (left) and the partially identifiable setting with fixed 7 but varying 7 (right). The details of the experimental setting be found in Appendix E.
Real-world data experiments We evaluate the performance of OOD methods using single-cell gene expression data from [38], consisting of d 622 genes across observational and interventional environments. As in [44], we focus on 28 genes active the observational environment. For each gene j = 1, ,,.... 28, we define the target variable y == X, and select the three genes most strongly
'Notiee that the term ||R (2;, + Manchore - S generally only goes to zero as + oc (yielding the minimax risk) if Manchor is full-rank. otherwise, can be strictly bounded from below as > is full-rank.

---

correlated with Y as covariates. This yields 28 prediction problems indexed by j. each consisting of data from an observational environment O and three interventional environments Iyz In3 representing the gene knockout on single covariate. For each prediction problem, we consider three training datasets D1,, y2,, Djs. obtained by combining data from O with a single interventional environment I11. Σ2z- ΣJz, respectively. For each training dataset Djk. k = 1, 2, 3, we evaluate the mean-squared error (MSE) at test time using four datasets consisting of varying proportions of unseen shifts (e.g.. "33% unseen directions" in Figure 4 represents test dataset with 67% observations sampled from Zjæ and 33% from Zje with + k). Hence, for each prediction problem predicting a gene j. we evaluate on 12 configurations (three training and four test datasets)." Figure illustrates the test MSE of the worst-case robust estimator (Worst-case Rob.) alongside anchor regression, invariant causal prediction (ICP), DRIG, and OL., as function of perturbation strength s. For a given proportion of unseen shifts, controls the distance of the test data points from the observational mean, acting as a proxy for shift strengths y and y/. We observe that the performance ranking of the robustness methods significantly varies with the proportion of new test shift directions. As expected, when no new shift directions are present at test time (0%), anchor regression and DRIG are optimal, since they protect against shifts observed training time. However, soon as unseen directions are present, their performance becomes inferior to OLS/ERM and the gap to the worst-case robust predictor (in the linear setting described in Section 2) grows with the proportion of unseen shifts. Further, while the MSE the previous invariant methods increases significantly with the strength of the test shift 8, the test loss of the worst-case robust predictor remains relatively stable.
0% unseen directions
33% unseen directions
67% unseen directions
100% unseen directions
0.5
Test MSE
0.4
0.3
0.2
0.1
0.25
0.50
0.75
0.25
0.50
0.75
0.25
0.50
0.75
0.25
0.50
0.75
Perturbation strength s
Methods:
Worst-case Rob. Anchor
Figure 4: The figures show the performance of the worst-case robust predictor (Worst-case Rob.) compared to other methods as function of perturbation strength s. Different panels correspond to the proportion of unseen shift directions at test time. For each panel and perturbation strength s, cach point represents average over the 28 target genes and three experiments (i.c., training environments).
5 Conclusion and future directions
This paper introduces the worst-case robust risk a quantity that well-defined even in settings where the usual robust risk is not computable from training distributions, and in identifiable scenarios [41, 45] reduces to the conventional robust risk. We instantiate our general framework for linear models with additive distribution shifts and compute tight lower bounds for this setting. Further, robustness methods strongly decrease in the partially identifiable setting; and ii) this suboptimality increases with perturbation strength and proportion of previously unobserved test shifts.
we demonstrate how i) the benefits of invariance-base
The main limitation of our paper is its reliance on linear setting to explicitly compute the worst-case robust risk and estimate the minimax quantity. However, we expect that the results and intuition developed in this paper can be extended to linear shifts in lower-dimensional latent space via suitable parametric or non-linear map [51, 10]. Important future directions include extending our results to more general shift models, non-line non-linear functional relationships and the classification setting, Further, a potential use of our work is in the field of active intervention selection (e.g. [57, 20J). By obtain an
computing the most adversarial model parameter for given estimator, e.g., OLS, intervention which minimizes the worst-case robust risk of the estimator on the next unseen shift.
An illustration of the training and test setups can be found in Figure 5.
6 Details on the tuning parameter for each method are in Appendix E.2.
Mooe details the shift strength can be found in Appendix E.2.
10

---

Acknowledgements
JK was supported by the SNF grant number 204439. NG was supported by the SNF grant number 210976. We thank Kasra Jalaldoust and Yixin Wang for helpful discussions and feedback on the manuscript.
References
[1] Kartik Ahuja, Ethan Caballero, Dinghuai Zhang, Jean- Christote Gagnon-Audet, Yoshua Bengio, Ioannis Mitliagkas. and Irina Rish. Invariance principle meets information bottleneck for distri-idistiuuttion generalization. Advances in Neural Information Processing Systems, 34:3438 14:3438-3450, 2021.
[2] Kartik Ahuja, Karthikeyan Shanmugam, Kush Varshney, and Amit Dhurandhar. Invariant risk minimization games. In International Conference on Machine Learning, pages 145-155. PMLR, 2020.
[3] Kartik Ahuja, Jun Wang, Amit Dhurandhar, Karthikeyan Shanmugam, and Kush R. Varshney. Empirical or invariant risk minimization? sample complexity perspective. In International Conference Learning Representations, 2021.
[4] Takeshi Amemiya. Advanced Econometrics. Harvard University Press, 1985.
[5] Joshua D Angrist, Guido W Imbens, and Donald B Rubin. Identification causal effects using instrumental variables. Journal of the American Statistical Association, 91(44)):444-555 1996.
[6] Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk mini- mization. arXiv preprint arXiv: 1907.0289.. 2019.
[7] Aharon Ben-Tal, Dick den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Management Science, 5942)341--377, 2013.
[8] Andrew Bennett, Nathan Kallus, and Tobias Schnabel. Deep generalized method of moments for instrumental variable analysis. Advances Neural Information Processing Systems, 32, 2019.
[9] Roger J Bowden and Darrell Turkington. Instrumental variables. Number Cambridge university press, 1990.
[10] Simon Buchholz, Goutham Rajendran, Elan Rosenfeld, Bryon Aragam, Bernhard Schölkopf, and Pradeep Ravikumar. Learning linear causal representations from interventions under general nonlinear mixing. Advances in Neural Information Processing Systems, 36, 2024.
[11] Peter Bühlmann. Invariance, causality and robustness. Statistical Science, 35(3):404-445 2020.
[12) Yuansi Chen and Peter Bühlmann. Domain adaptation under structural causal models. Journal of Machine Learning Research, 22(261):1-80. 2021.
[13] Mathicu Chevalley, Yusuf Roohani, Arash Mchrjou, Jure Leskovec, and Patrick Schwab. Causal- bench: A large-scale benchmark for network inference from single-cell perturbation data. arXiv preprint 2rXiv:2210.17288 2022.
[14] Rune Christiansen, Niklas Pfister, Martin Emil Jakobsen, Nicola Gnecco, and Jonas Peters. A causal framework for distribution generalization. IEEE Transactions on Pottern Analysis and Machine Intelligence, 44(10):6614-6630, 2021.
[15] John C Duchi and Hongscok Namkoong. Learning models with uniform performance via distributionally robust optimization. The Annals of Statistics, 1978):1378-1406 2021.
[16] Jean-Marie Dufour and Cheng Hsiao. Identification, pages 65-77. Palgrave Macmillan UK, London, 2010.

---

[17] Jianqing Fan, Cong Fang, Yihong Gu, and Tong Zhang. Environment invariant linear least squares. arXiv preprint wrXiv2333.03302, 2023.
[18] Justin Frake, Anthony Gibbs, Brent Goldfarb, Takuya Hiraiwa, Evan Starr, and Shotaro Yam- aguchi. From perfect to practical: Partial identification methods for causal inference in strategic management research. Available at SSRN 4228655, 2023.
[19] Charlie Frogner, Sebastian Claici, Edward Chien, and Justin Solomon. Incorporating unlabeled data into distributionally robust learning. Journal of Machine Learning Research, 22((6): 2021.
[20] Juan L Gamella and Christina Heinze-Deml. Active invariant causal prediction: Experiment selection through stability. Advances in Neural Information Processing Systems, 33:15464- 15475, 2020.
[21] Ishaan Guirajani and David Lopez-Paz. In search of lost domain generalization. In International Conference on Learning Representations, 2021.
[22] Jason Hartford, Greg Lewis, Kevin Leyton-Brown and Matt Taddy. Deep IV: A flexible approach for counterfactual prediction. In International Conference on Machine Learning, pages 1414-1423. PMLR, 2017.
[23] Martin Emil Jakobsen and Jonas Peters. Distributional robustness of k-class estimators and the pulse. The Econometrics Journal, 25(2):404 432, 2022.
[24] Kasra Jalaldoust, Alexis Bellot, and Elias Bareinboim. Partial transportability for domain generalization. In The Thirty-ightt Annual Conference on Neural Information Processing Systems, 2024.
[25] Pritish Kamath, Akilesh Tangella, Danica Sutherland, and Nathan Srebro. Does invariant risk minimization capture invariance? In International Conference on Artificial Intelligence and Statistics, pages 4069-4077. PMLR, 2021.
[26] Daniel Kang, Yi Sun, Tom Brown, Dan Hendrycks, and Jacob Steinhardt. Transfer of adversarial robustness between perturbation types. arXiv preprint arXiv: A.Kiv:1905.0003:5 2019.
[27] Lucas Kook, Beate Sick, and Peter Bühlmann. Distributional anchor regression. Statistics and Computing, 32(3):39, 2022.
[28] David Krueger, Ethan Caballero, Joem- Jacobsen, Amy Zhang, Jonathan Binas, Dinghuai Zhang, Remi Le Priol, and Aaron Courville. Out-of-distribution generalization via risk extrap- olation (REx). International Conference on Machine Learning, pages 5815-5826. PMLR, 2021.
[29] Jiashuo Liu, Jiayun Wu, Bo Li, and Peng Cui. Distributionally robust optimization with data geometry. Advances in Neural Information Processing Systems, 35:33689-33701, 2022.
[30] Sara Magliacane, Thijs Van Ommen, Tom Claassen, Stephan Bongers, Philip Versteeg, and Joris M Mooij. Domain adaptation by using causal inference to predict invariant conditional distributions. Advances in Neural Information Processing Systems, 31, 2018.
[31] Nicolai Meinshausen. Causality from a distributional robustness point of view. In 2018 IEEE Data Science Workshop (DSW), pages 10. IEEE, 2018.
[32] Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations, Mathemati- cal Programming. 171(1):115-166, 2018
[33] Krikamol Muandet, Arash Mehrjou, Si Kai Lee, and Anant Raj. Dual instrumental variable regression. Advances in Neural Information Processing Systems, 33:2710-2721, 2020.
[34] Judea Pearl. Causality: Models, Reasoning and Inference. Cambridge University Press, USA, 2nd edition, 2009.
12

---

[35] 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, 78(5):947-1012, 2016.
[36] Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: founda- tions and learning algorithms. 2017.
[37] Lei S Qi, Matthew H Larson, Luke A Gilbert, Jennifer A Doudna, Jonathan Weissman, Adam P Arkin, and Wendell A Lim. Repurposing CRISPR as an RNA-guided platform for sequence-specific control of gene expression. Cell, 152(5): 113-11111111113 183, 2013.
[38] Joseph M Replogle, Reuben A Saunders, Angela N Pogson, Jeffrey A Hussmann, Alexander Lenail, Alina Guna, Lauren Mascibroda, Eric J Wagner, Karen Adelman, Gila Lithwick-Yanai, et al. Mapping information-rice genotype-phenotye landscapes with genome-scale Perturb-seq. Cell, (8((14))2559-255)) 2575, 2022.
[39] Mateo Rojas-Carulla, Bernhard Schölkopf, Richard Turner, and Jonas Peters. Invariant models for causal transfer learning. Journal of Machine Learning Research, 19(36):1-34, 2018.
[40] Elan Rosenfeld, Pradeep Kumar Ravikumar, and Andrej Risteski. The risks of invariant risk minimization. In International Conference on Learning Reprexentations, 2021.
[41] Dominik Rothenhäusler, Nicolai Meinshausen, Peter Bühlmann, and Jonas Peters. Anchor regression: Heterogeneous data meet causality. Journal of the Royal Statistical Society Series B: Statistical Methodology, 83(2))215-226. 2021.
[42] Sorawit Saengkyongam, Leonard Henckel, Niklas Pfister, and Jonas Peters. Exploiting indepen- dent instruments: Identification and distribution generalization. In International Conference on Machine Learning, pages 18935-18958. PMLR, 2022.
[43] Shiori Sagawa*, Pang Wei Koh* Tatsunori B. Hashimoto, and Percy Liang. Distributionally robust neural networks. In International Conference on Learning Representations, 2020.
[44] Christoph Schultheiss and Peter Bühlmann. Assessing the overall and partial causal well- specification of nonlinear additive noise models. Journal of Machine Learning Research, 25(159):1-41, 2024.
[45] Xinwei Shen, Peter Bühlmann, and Armeen Taeb, causality-orientee robustness: exploiting general additive interventions. arXiv preprint arXiv:2307.10299 2023.
[46] Yuge Shi, Jeffrey Seely, Philip Torr, Siddharth N, Awni Hannun, Nicolas Usunier, and Gabriel Synnaeve. Gradient matching for domain generalization. In International Conference on Learning Representations, 2022.
[47] Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log-likelihood function. Journal of statistical planning and inference, 90(2):227-244, 2000.
[48] Rahul Singh, Maneesh Sahani, and Arthur Gretton. Kernel instrumental variable regression. Advances in Neural Information Processing Systems, 32, 2019.
[49] Aman Sinha, Hongseok Namkoong, and John Duchi. Certifiable distributional robustness with principled adversarial training. In International Conference on Learning Representations, 2018.
[50] Elie Tamer. Partial identification econometrics. Annu. Rev. Econ., 2(1):167-195, 2010.
[51] Nikolaj Thams, Michael Oberst, and David Sontag. Evaluating robustness to dataset shift via parametric robustness sets. Advances in Neural Information Processing Systems, 35:16877- 16889, 2022.
[52] Florian Tramèr and Dan Boneh. Adversarial training and robustness for multiple perturbations. In NeurlPS, pages 5858-5868, 2019.
[53] Aad W Van der Vaart. Asymptotic statistics, volume 3. Cambridge University Press, 2000.
13

---

[54] Chuanlong Xie, Haotian Ye, Fei Chen, Yue Liu, Rui Sun, and Zhenguo Li. Risk variance penalization. arXiv preprint arXiv:2006.077 07544, 2020.
[55] Bin Yu, Assouad, Fano, and le Cam. In Festschrift for Lucien Le Cam: Research papers in probability and statistics, pages 423-435. Springer, 1997.
[56] Yi Yu, Tengyao Wang. and Richard J Samworth. A useful variant of the Davis-Kahan theorem for statisticians. Biometrika, 102(2)3315-22) 2015.
[57] Jiaqi Zhangg Louis Cammarata, Chandler Squires, Themistoklis P Sapsis, and Caroline Uhler. Active learning for optimal intervention design in causal models. Nature Machine Intelligence. 1075, 2023.
14

---

Appendix
The following sections provide deferred discussions, proofs and experimental details.
Table of contents
A Extended related work
16
Extension to the general additive shift setting
16
C Comparison to finite robustness methods continued
17
C.1 The setting of continuous anchor regression [41]
17
C.2 Distributionally robust invariant gradients (DRIG) [45]
18
D Empirical estimation of the worst-case robust predictor
18
D.I Computing the worst-case robust loss
19
D.2 Consistency the worst-case robust predictor
20
D.3 Proof of Proposition 3.
21
D.4 Proof of auxiliary lemmas
................................
22
D.4.1 Proof of Lemma D.1
22
D.4.2 Proof of Lemma D.2
22
D.4.3 Proof of Lemma D.3
23
Details on finite-sample experiments
24
E.1 Synthetic experiments..
24
E.2 Real-world data experiments
25
Proofs
26
F.1 Proof of Proposition
26
F22 Proof of Theorem 3.1
26
F3 Proof of Corollary 3.2
29
15

---

A Extended related work
To put our work into context, first, we discuss relevant distributional robustness literature organized according structural assumptions the desired robustness set. Second, we summarize existing views on partial identifiabiliyy in the causality and econometrics literature and how our findings connect to their perspective.
No structural assumptions on the shift. DRO: Distributionally robust optimization (DRO) tackles the problem of domain generalization when the robustness set is ball around the training distribution w.r.t. some probability distance measure, e.g., Wasserstein distance [49, 32] or f-divergences [7, 15]. Considering all test distributions in a discrepancy ball can lead to overly conservative predictions, and therefore, alternatives have been proposed in, e.g., the Group DRO literature [43, 19, 29]. However, these methods cannot protect against perturbations larger than the ones seen during training time and do not provide a clear interpretation of the perturbations class [45].
Structural assumptions on the shift. Robustness from the lens of causality takes step further, by assuming a structural causal model [34] generating the observed data (X, Y). Infinite robustness methods: The motivation of causal methods for robustness is that the causal function is worst-case optimal to predict the response under interventions of arbitrary direction and strength on the covariates [31, 11]. For this reason, causal models achieve what we call infinite robustness. Depending on the assumptions of the SCM, there are different ways to achieve infinite robustness. When there are no latent confounders, several works [35, 17, 30, 39, 2, 6, 46, 54, 28, 1] aim to identify the causal parents and achieve infinite robustness by exploiting the heterogeneity across training environments. In the presence of latent confounders, it is possible achieve infinite robustness by identifying the causal function with, e.g.. the instrumental variable method [5, 22, 48, 8, 33]. There are different limitations to infinitely robust methods. First, the identifiability conditions of the causal parents and/or causal function are often challenging to verify in practice. Second, ERM can outperform these methods when the interventions (read shifts) at test time are not arbitrarily strong or act directly on the response or latent variable [3, 21]. Finite robustness methods: In real data, shifts of arbitrary direction and strength in the covariates are unrealistic. Thus, different methods [41, 23, 27, 45, 14] trade off robustness against predictive power to achieve what we call finite robustness. The main idea of finite robustness methods is to learn function that is as predictive as possible while protecting against shifts up to some strength in the directions that are observed during training time. These methods, however, only provide robustness guarantees that depend on the heterogeneity of the training data and do not offer insights into the limits of inniithnn-ideeeddeen robustness under shifts in new directions.
Partial identifiabiltyy The problem of identification is at the center of the causal and econometric literature [36, 4]. It studies the conditions under which the (population) training distribution uniquely determines the causal parameters of the underlying SCM. Often, the training distribution only offers partial information about the causal parameters and. therefore, determines a set of observational equivalent parameters. This setting is known as partial or set identification and is used in causality and econometrics to learn intervals within which the true causal parameter lies [50]. In this work, we borrow the notion of partial identification to study the problem of distributional robustness when the robustness set itself only partially identified.
B Extension to the general additive shift setting
We discuss how our setting changes when we relax the assumptions on the existence of the reference
environment. We consider the data-generating process in Equation (3), where Etrain = [m]], m E N. If no environment e exists with f4c and Σx O. we first pick an arbitrary distribution P.X.Y as the reference environment We denote Σ, := Σ Eyet-
First, we show we can express the space S of training additive shift directions defined in Equation (12) in the general case. We center all distributions by Pref to obtain centered distributions Pr that
In practice, it is useful to pick distribution with the smallest covariance, i.c. tr Cov S tr (X.)
for all e.
16

---

E xx [X] 0. With respect to the arbitrary reference environment, we now define
S = range
- + (Me - (Me - (reet )) C IR U
eEErvain
We now consider test shifts with respect to the environment P.X.II, We define the test shift upper ref bound Mrest = -yM + +>RR"* where range Mseen C S and range R C S+. Again, we can decompose the parameter 3 as 3 = 3 + 3 The projection 3 of the causal parameter onto the relative training shifts induces the following observationally equivalent parameters corresponding to the reference distribution:
)). Again, 8 can be identified from the training distributions and is referred to as the identified model parameters. The following adapted version of Proposition shows that assuming shifts on XPY the robust prediction model is only identifiable if the test shifts are in the direction of the relative training shifts:
0² = ( Eny DS (oē)²)= (BS, Eny - E,33" ( + 3
+ (BS
Proposition 2 (Identifiability of reference distribution parameters and robust prediction model). Suppose that the set of training and test distributions is generated according to Equations (3) and (4). Then, 8 is observationally equivalent O and computable from training distributions. Furthermore, holds that
(a) the model parameters generating the reference distribution can be identified up to the following observationally equivalent set:
eg { + az Ex DS -
- 2a - + T Efa: }
(b) the robust prediction model grash as defined in Equation (8) is identified up the -
3s + (nIIM (xIIM++,))+>> n. + {(TlII + -a a E range R} 9 grob
The proof is analogous Appendix F.1. A version of Theorem 3.1 for perturbations the reference environment follows accordingly.
C Comparison to finite robustness methods continued
C.1 The setting of continuous anchor regression [41]
In this section, we evaluate the worst-case robust risk of the continuous anchor regression estimator. In the continuous anchor regression setting, during training we observe the distribution according to the process X = M MA+ + 7; Y = 3 X + &, where is an observed g-dimensional anchor variable with mean and covariance Σς and M Rd is known matrix. Note that this setting, we do not have a reference environment, but, since the anchor variable is observed, the distribution of the additive shift M A known. The test shifts are assumed be bounded by Muss MME,, Since range Meest C S range M, no new directions are observed during test time, in other words, R Thus, both the corresponding robust loss and the anchor regression estimator can be determined from training data. It holds that
Banchor = arg min Roob(B: 0*, 7MEAM
BERd
Again, the pooled OLS estimator corresponds to Banchor with = 1. Similar to the discrete anchor case, in case the test shifts are given by Mnew = M +YRRR" the worst-case robust risk (9) is given by
Rlob (B: Oeq. Mnew) = 7 + || B112)² + Reob "B."
77MEMM)
and for the best worst-case robustness the anchor estimator holds
ProobBBancoo Oegi Mress) = (Cker + |RR (2) + +MMEM T 'y5
2 - >ngell> 2l / + const;
lim Rioh (Banchor Oegi Mnew)/ /////////// lim M0( Mnew)) ) 7'-00
70 The above results follow by analogy with Appendix F33
In other words, we require that the test distribution is shifted version of the (arbitrarily) chosen reference distribution.
17

---

C.2 Distributionally robust invariant gradients (DRIG) [45]
DRIG [45] introduce more general additive shift framework, where collection of additive shifts Ae is given with moments (ft: ).). For each environment we observe data (Xe. Ye) distributed according to the equations X, = Ag + 7) Ye , T X Ç. where the noise is distributed like in Equation (3), This DGP arises from the structural causal model assumption as described in Figure 1. DRIG consider more more general intervention setting, additionally allowing additive shifts of Y and hidden confounders H. However, their identifiaiility results can only be shown for the case of interventions on X, and since identifiability of the causal parameter is crucial part of our analysis, we only consider shifts on the covariates. DRIG assumes existence a reference environment e = 0 with A4g 0 and for which it is required that the second moment of the reference environment is dominated by the second moment of the training mixture:
Eo
We (Ee + Mefle
<E/m]
This assumption allows [45] derive the DRIG estimator which is robust against test shifts upper bounded by MDRIG == 7 Eee(m) We(Ce - Eo + Helle) ). The following lemma allows us to make
further statements about MDRIG: Lemma C.I. Let A and B be positive semidefinite matrices such that B 3 A. Then it holds that range B range A.
Proof. It suffices to show that ker A C ker B. (ker A C ker B implies that range A = (ker A) C
(ker B)- rrange B.) Consider x E ker A, x * O. Then it holds that x (A B)x = x. Ax
x T Bx = 0 x Bx 2 O, from which follows that x Ba = and thus x E ker B.
Because of the assumption Eo 3 Eeelm) Wee T) by Lemma C. it follows that range Eg C Ue2trange (Ee + ) and thus
range MDRIG range
Σ We (Ee + Molie
Hence, the robustness directions achievable by DRIG in the "dominated reference environment" setting are the same as the ones under the assumption Eg =. Again, we observe that the test shifts bounded by >MDRIG are fully contained in the space of identified directions S. If the test shifts including some unseen directions range R C S the robust risk in the DRIG setting is only partially identified. The worst-case robust risk (9) is given by
instead bounded by M
7MRRIG + 7 RRT,
Riob (8; Oeq: Mnew) = ('(ker + ||RT B112)² + Rro 0- MMRRG)) and again, the DRIG estimator is optimal for infinitesimal shifts 7 and suboptimal for larger y/:
Rrob (BDDIG: θeq: Maew) (Cher +|RRT (E; - - 1))8'' const;
Mi(Oeq Mnew) Cheer if if 2 Khi
whereas
7'
Me.eeq Muew). (Ower + |RR (E + MDDII) "n 1)
lim 7000
7/
The above results follow by plugging Mnew with M MDRIG into the proof of Corollary 3.2 in Appendix F.3..
D Empirical estimation of the worst-case robust predictor
In this section, we discuss how to compute the worst-case robust loss and its minimizer from finite- sample multi entiromenninnnnenttt training data. We first describe the unite-sample setting and provide high-level algorithm. We then discuss some parts of the algorithm in more detail. Finally, we show that the empirical worst-case robust loss consistent under certain assumptions. For simplicity, in this section, we assume that Mist YSS + + RR where 7, 2 0, SS is soti-ortlogonal matrix satisfying range SS C S and R a semi-orthogonal matrix satisfying range R C St. However, the results and strategies in this section can be easily applied more general Mest.
18

---

D.1 Computing the worst-case robust loss
Algorithm 1 Computation of the worst-case robust loss
1: Input: celtiienvironmentt data = UeEErran De, test shift strength y > 0, test shift directions
M Rdxdd causal parameter upper bound C >
2: Step I: Estimate the training shift directions S(D), its orthogonal complement (D), and
identified causal parameter 3S.
3: Step 2: Estimate the identified and non-identified test shift directions S, ft and their projections
SS and RRT..
4: Step 3: Estimate the norm Öker of the non-identified causal parameter.
5: Step 4: Compute the worst-case robust loss function
(3; SST _iRTT + (3; + (B; SST 7) + (ia Ckors Ri 7)
reference loss
invariance penalty term
non identifability penalty term
6: Return: worst-case robust predictor and the estimated minimax "hardness" of the problem:
grob +
arg min (3; ".SSB RRT);
SER*
WT(D, M) + min (3; S3, "
DER*
Training data. We observe data from m + 1 training environments indexed by E E Etrain (O. m. where E represents the reference environment. We impose discrete probability distribution PE on the training environment E Etrains resulting in the joint distribution (X,Y, E) px,VE P For each environment E = c, we observe the samples D. = {(X,,. Y,, ) where (Xe,s, Ye,i) are independent copies of (Xe, Y.) ~ |==,Y|E=e, Then, the resulting dataset is D UecEnrii De with no + 7m Furthermore, for each environment E e, define
the weights We == na/n.
present high-level scheme for computing the worst-case robust loss from multi- nnutii-enviromment data, which consists of multiple steps. First, nuisance parameters related to the training and test shift directions estimated, which describe in more detail below. Afterwards, the three terms of the loss are computed: the (squared) loss Cret (3; Do) on the reference environment is computed
Computation of the worst-case robust loss. In Algorithm
Lre (B: = > (Y,. B Xo.)
2=1
The invariance penalty term Liv (3: ; gs S5T 77) (which increasingly aligns any estimator 3 in the direction of the estimated invariant causal predictor gs as - oo) can be computed as following in the linear SCM setting:
Cinv SSS .7) = > (B 3
Finally, the non connidentifiabiiityy penalty term (ia(3; Öker, RiR.T .7) can be computed as follows:
(3; Ówec, RRR. ,) (Cker + |RR B112)²
The non-identifiability term, with increasing 7, penalizes any predictor / towards zero on the subspace R of non-identified test shift directions. total. the worst-case robust loss (in the linear SCM setting) equals
no
C..3335.55 SST RR =
(Y. (Yo.
xo.))²
( 7(Cker + IRR (RRT311)) 312)
where suppress dependence on C and and only leave the dependence the nuisance parameters.
19

---

Choice/Estimation of nuisance parameters. We now provide more details on the empirical estimation of the nuisance parameters S, , R, and 3
The constant C &corresponds to the upper bound on the norm of the true causal parameter 3r. Thus, the practitioner chooses C in advance to ensure that (with high probability) 1 S C.
The training shift directions S can be computed via
S(D) range Σ (Cov(X Cov(X²) + Malt Hopo )
(19)
where for e E Eirinn the matrix Cov(X*) the empirical covariance matrix estimated within the training environment E and Me IR is the empirical mean of the covari- ates within the training environment E' = Additionally, we compute the orthogonal complement $ (D) of the space S(D)
The decomposition of the test shift directions M into identified and non-identified shift directions (and their corresponding projection matrices) can be computed as follows. Let Ig and llg. denote the projection matrices on S(D) and S (D). respectively. Consider the singular value decompositions M = UgISVV and II M = Ug Ega V3 Then, define
$ = Ug+
The subspaces range (IlgAM and range (IIga M) are minimal subspaces contained in S and $+, respectively, such that range (M) range (Ig @ range M)) The matrices SST and RRT are their corresponding projection matrices.
The identified causal parameter A (approximately) equals the true causal parameter 3 on the space of training shift directions S. As conjectured in the anchor regression literature [41, 45, 23] (see, for example, the discussion right after Thcorem 3.4 [23] and Appendix H.3 therein) for r - co, the estimators 3 anchor and GRIG converge to the causal parameter 3 on S. Thus, the identified causal parameter can be estimated as
g Il g
A ggg
for the setting of mean mean+variance shifts, respectively.
D.2 Consistency of the worst-case robust predictor
For any estimator 3 E Rd and given the estimated nuisance parameters & (SST, RR. , R define the sample worst-case robust risk as
we
(n) = Σ - Xo.)) + + -3)12 + (vC- ||s 1 + j B||2 DDDD
(20)
Correspondingly, define the estimator of the worst-case robust predictor by
grob = arg min (3,
(21)
BEB
where B C Rd is some compact set whose interior contains the true parameter Arob
To show the consistency (21), we first require consistency of the nuisance parameter estimators, which we state an assumption.
In general, ((D) is proper subspace of gd and the RHS of (19) corresponds to sum low-rank second moments. This can be consistently estimated if, for instance, the rank of each shift is known (e.g. in the mean shift setting), the covariances have spiked structure, allowing to off small eigenvalues.
20

---

Assumption D.1. The estimated nuisance parameters & = (SST, .RRT.. ,BS) are consistent, that is, for n 00, |SS -SS |F 0, |RR RRR || F 0, 3 3, =
where for any matrix A E R= |A]| = /tr (AT A) denotes the Frobenius norm, and SST, RR are the corresponding population projection matrices onto ITs,,, ll. M respectively.
Depending on the assumptions of the data-generating process, Assumption D.I can be shown to hold. For example, in the anchor regression setting [41]. the consistency of the projection matrices SST RRT, and I holds if the dimension of S is known (due to the mean shift structure). The proof relies on the Kahan theorem (see, for example, [56]) and the consistency of the covariance matrix estimator. Moreover, in the anchor regression setting, it is conjectured that the estimator 3 converges to its population counterpart (as discussed right after Theorem 3.4 in [23] and Appendix H.3 therein) which implies that A = Ilg.Pachoo consistently estimates 3 IIs
Under the assumption of the consistency of the nuisance parameter estimators, we now show that (21) is a consistent estimator of the worst-case robust predictor.
Proposition 3. Consider the estimator Beoh of the worst-case robust predictor defined in (21).
Suppose the optimization problem is over compact set B C IR whose interior contains the true minimizer Pe Moreover, suppose Assumption D.I holds. Finally, assume that the covariance
matrix E [XoX > with bounded eigenvalues and E [Y]] < J0. Then, Brob is consistent, i.e., as n, no + 00 it holds that
ārob P grob P P
D.3 Proof of Proposition?
For ease of notation define 90 == f and | Booh For any parameter of interest B and nuisance parameters = PRs b). define the function
(z.y) 93.p (z, y) (y- - 3 2)² Pb 3)1 +> (VC- ||61 ||
2
(22)
Using (22), the robust identifiable risk and its sample version defined in (20) can be written, respec- tively
= =(3,4)=El9a ( (Xo. Yo)l, (x( = Σ
( Yo,s).
iEDo
Our goal is to show that 33 F, Bo First, show that the minimum of the loss is well-separated. Lemma D.1. Suppose that [X,XX] XJ] > 0. Then, for all 8 > 0, holds that inf (C(B, po): || Bullz 8} > L(3u, (P))-
(23)
Fix > From the well-separation of the minimum from Lemma D.I, there exists >> such that (1.3 Bollz }} { L(B,, sP) })
Therefore,
P (113 Boll2 > 6) s (c(B, vo) L(Bo, sPo) > 2s)
(c(3, =P(C(3, pp) - C, (3, po) + C,, (P)) L, (3. ()
P
(B. ②) L, (8o. 3) + L. (Bo, +) - L(Bo, sPo) > >6)
< F [(3, (po) L.. (3, v0) > 8/4 + IP (3, :0o) - Cn(3, > 8/4)
(24)
+ P C,, ;) (3o, 3) 8 8/4 + IP (C,, (Bu, 3) - L(Bu, pp) > 8/4).
(25)
We now want to prove convergence the four terms in (24) and (25). For this, we use the following statements proved in Appendix D.4.
21

---

Lemma D.2. Suppose B S Rd is compact set. Moreover, assume that the covariance matrix [X > with bounded eigenvalues and [Y cc. Then, as n. no - it holds that
sup C. (8, C(3,5p)) 3 0.
(26)
BEB
Lemma D.3. As 0o, holds that
- gool S 0.
sup SEB
(27)
The two terms (24) converge to 0 by Lemma D.2 and Lemma D.3, respectively, The first term in (25) equals since 3 minimizes 3 + CB, Φ). Finally, we observe that
sup (3. () ((3, 5 0, BEB
(28)
since we have that
sup (8, - C(B, sPo) S sup (3, f.n (0)) + sup (8, so) - L(3,, SEB
BEB
BEB
where the first term converges in probability by Lemma D.3, and the second term converges in probability by Lemma D.2. This implies that the second term in (25) converges to zero. Since 6 was arbitrary, it follows that 3 So-
D.4 Proof of auxiliary lemmas
D.4.1 Proof of Lemma D.1
By definition,
- -) + (Vc- 1|5-1 1 + |RR 8112
[(3, = E(6 - T
Since E [X O, the first term is strongly convex in 3. Moreover, the second and third terms are convex in B. Therefore, L(3, (P) strongly convex in 3. Since L(3, also continuous in B, it follows that there exists unique global minimum. Let 80 denote the global minimizer of L(B, sPo). By the fact that C(So, po) is global minimum, and by definition of strong convexity, there exists positive constant >> 0 such that, for all / E B.
C33 2 L(3,, PP) + m 1/ - Bull2.
(29)
Fix Then, by (29), for all such that ||3 Boll2 > holds that
md² > LB,, (o).
[B, Po) 2 C(9,, PP)
Since the inequality holds for all [ E such that || - -oll2 6, we conclude that
inf vo): ||B Boll2 8} > L(Bo, sp)
Since 8 > 0 was arbitrary, the claim follows.
D.4.2 Proof of Lemma D.2
Recall that for any 3 E B
1 Σ no IDD
[(3,50) sP) E [98.90 (No, Yo)], (n,
g8.po (Xa,is Yo.).
To show the result, we must establish that class of functions {99. 3 E B} is Glivenko-Cantelli From [53], a set of sufficient conditions for being Olivenko-Canted class is that (i) B is compact, (ii) 3 >> go (ar, y) is continuous for every (a, y), and (iii) >> g8 dominated by an integrable function. By assumption, (i) holds. Moreover, by (22), it follows that 3 + 93. is continuous
22

---

for all (x, y) and thus (ii) holds. We now show that (iii) holds. Since B is compact we have that sup |5112 C oc. For fixed y > O, and all (z, y), we have that
98.00 (1,, v) S sup po (zc, y) BEB
S
sup(v x²2 + 2 |/. BEB
1199
sup sup BEB
1
(30)
2
+ VC-118811 ||351|2 + |R | supll
BEB
$ 2y + 20 + = G(z v),
where K < oo a finite constant not depending on (x., y). Furthermore, we have that
[G Yo]] = 2E [X]] + 20 tr (E [x,x, + K < 0o, since E [ < 0o and E X has bounded eigenvalues by assumption. From (30) and (31), follows that (iii) holds.
(31)
D.4.3 Proof of Lemma D.3
For fixed y > 0, we have that
sup (B, ()- (3, (0)) - sup SEB
[ISST(BS - B)11 ||SS (8S -)]12
(32)
7 μEB
(VC-11885)) 1|-5111113 + |RR (112 2
(VC || 112 + + B112
sup BEB
(33)
We can upper bound (32) as follows,
||SST (BS 1) - ||SS (3S B))1
sup
BEB
(8S T)T SST (35 B) (BS 3) SS (0S - -3]
sup
BEB
(35 SST (BS - BBS) + (BS T (BS - 3)
= sup BEB
+(BS B) T - SS (BS SSS)(BB- 3)
< 2 sup
supp1 ||35 - 3112 11ŠŠT |F 1135 -Bs BEB
122
sup 1|88 - 312 1|SS BEB
SST ||F
(34)
< <1 - 311 + C3IISS SST | 3.,
(35)
where (34) follows from the Cauchy-Schwarz inequality and that ||A||2 I ||A|e, the constants C₁ C2 0o in (35) follow from compactness of B, and the convergence in probability follows from Assumption D.1. Furthermore, we can upper bound (33) as follows,
CV-
|| +
||R
8112)
(VC-
-15511111 + |RR Bl12
sup BEB
sup PEB
C
|| 112
|RAR 312 2/ C- -|33 JRR B112
|RR 3112 2/ //c- - ||35||3 ARR 3112
-C+ ||8
< sup BEB
|| 12
118
sup BEB
3T TTRRR R.R.. )3
+ sup
c - |
RR B11 - -1
RRR 312
BEB
= = + (IT) + (IIT).
23

---

By Assumption D.1, (I) converges in probability to zero. Regarding (II), we have
sup
T TRR - -RR ) S
supli SEB
IRAT RRR' ||= 5 0,
BEB
where the inequality follows from Cauchy-Schrye and that || S ||||| and the convergence in probability follows from Assumption D.1 along with the compactness of B. It remains to upper bound (1I1). We have that
(IIT)
V C
||
|RR
B112 VC C || P| B|12
sup BEB
+ sup SEB
v c - ||
IRR B112 VC - -1135 |RR Bl1
|VC VC- 11,331113
sup BEB
|||2 ||RR ||.)
(VC- 11--1888133
+ sup 3EB
V B RR B V STRR
1/2
1/2
S C33 ||,3$113 113 + || 112
+ VC sup BEB
(TRR RR )
(36)
1/2
1/2
$ CC3
|| 11
+ 1| 12
+ VC
sup BEB
PRA RR |F
0.
(37)
The inequality in (36) follows from the compactness of B, the fact that R...T T has bounded eigenvalues, and that V vyl < Ix y/2/2 for all x; 2 0. The inequality in (37) follows from Cauchy- Schwarz and that | 2 S || The convergence in probability follows form Assumption D.1 and the compactness of B.
E Details on finite-sample experiments
In this section, we provide more details of the data generation for our synthetic finite-sample experiments as well as data processing for the real-world data experiments.
E.1 Synthetic experiments
For the synthetic experiments, we generate a random SCM which satisfies our assumptions. For d = 15, we randomly sample the joint covariance E of (17, (), fixing its total variance and the eigenvalues. We consider 7 environments including the reference environment, and for each environment except the reference, we randomly generate mean shifts μe of fixed norm 1. Since we have 6 non-zero random Gaussian mean shifts, it holds a.s. that dim S = 6. We then randomly generate an "initial guess" for 3 Ed of fixed norm C 10. Now, with respect to the space S of the identifiable directions induced by the mean shifts, we choose the most "adversarial" causal parameter 3 which is equal to 3* on S, but on S has the opposite direction of the noise OLS estimator - - We ensure that || | C. Note that under the observed shifts, 3* and Biny are observationally equivalent. We complete Bt.y to the set Oady of observationally equivalent model parameters and generate the multi- enntrmmenvirnntntttt training data according Padv and the collection of mean shifts.
For Figure (left), we define the test shift upper bound as Manchor = 7 E. PeM. We vary ? from 0 to 10, and for each y, we compute the oracle anchor regression estimator by minimizing the discrete anchor regression loss with the correct ? Additionally, we compute the pooled OLS estimator and the worst-case robust predictor Brob as described in Appendix D. Finally, we generate test data with
a Gaussian additive shift A ~ (0, Manchor). We evaluate the loss of BOLS, Bauchor and grab this test environment and include the population lower bound.
Pegg on
For Figure 3 (right), we define the test shift upper bound as Mnew = Ee MeHe + + RRR, where R is a 2-dimensional subspace of the space S We fix the magnitude 7 of the "seen" test shift
24

---

directions at Y 40 and set vary 7 from O to 2 to showcase the effect of small unseen shifts compared to large identified shifts. We compute the oracle anchor regression estimator by minimizing the discrete anchor regression loss. Additionally, we compute the pooled OLS estimator and the worst-case robust predictor & as described in Appendix D, for which we use the oracle y', given
Manchor and empirical estimates of the spaces S, S+, R.
Finally, we generate test data with a Gaussian additive shift Aust ~ (O, Mnew). We evaluate the loss of BoLs: Sanchor and P on this test environment, plot the resulting test losses for different estimators and include the population lower bound.
E.2 Real-world data experiments
ENSO00 12308
ENSC000001 12306
ENS0000011 12006
ENSC000009000 Envtronment EN60X00003300
ENSG0000081109
ENSG000009009
Setting
Setting
Heet
mmnn
Figure 5: The figures illustrate the structure of the (a) training-time shifts and (b-c) test-time shifts for different perturbation strengths on the example of two covariates. Panel (a) shows the training data containing two enviromments-observttonn (blue) and shifted (orange) corresponding to the knockout the gene ENSG00000099009, Panels (b) and (c) show the training data in grey and test data from previously unseen environment (green). Panel (b) depicts the top 10% test data points closest to the training support (perturbation strength 0.1). Panel (c) illustrates the full test data (perturbation strength = 1.0).
We consider the K562 dataset from [38] and perform the preprocessing as done in [13]. The resulting dataset consists of n 162, 751 single-cell observations over d 622 genes collected from observational and several interventional environments. The interventional environments arise by knocking down single gene at time using the CRISPR interference method [37]. Following [44], we select only always-active genes in the observational setting, resulting in smaller dataset of 28 genes. For each gene j = 1, ..... 28, we set Y ;= Xj as the target variable and select the three genes XR, ........ Xby most strongly correlated with Y (using Lasso), resulting in prediction problem over XK,,..... follows. Let O denote the 10,691 observations collected from the observational environment, and let I, denote the observations collected from the interventional environment where the gene k; was knocked down. We will denote by I,,, the 100 percent of datapoints in I, that are closest to the mean of gene k; in the observational environment O. For example, I,,.1 consists the 10% of datapoints I; closest to the observational mean of gene k; Thus, the parameter E [0, 1] acts as a proxy for the strength of the shift. Denote by Ii a random sample of IG,- of certain size. For each E (1, we fit the methods on the training data Dirain O U Iy,, with [T 20. Figure 5(a) illustrates an example training data Dirain Having fitted the methods on Ditain we evaluate them on test datasets constructed as follows. For each shift strength and proportion x E {0, .3,, 67, 1). define the test dataset Dr,, consisting of π observations from Ue and - π cout-of-training observations from Ii.- An example of a test dataset for different shift strengths and previously unseen directions (i.e., 1) shown in Figure 5(b-c). We compare our method Worst-case Rob., defined as the minimizer of the empirical worst-case robust risk (20), with anchor regression [41], invariant causal prediction (ICP) [35], Distributional Robustness via Invariant Gradients (DRIG) [45], and OLS (corresponding to vanilla ERM). We use the following parameters for Worst-case Rob.: 7 = 50, Cker = 1.0, and M ld. For anchor regression and DRIG, select y 50. For ICP, set the significance level for the invariance tests = 0.05.
Xky. Given this prediction problem, we construct the training and test datasets as
(..1...., 0.9}
25

---

These numerical experiments are computationally light and can be run in = 5 minutes on a personal laptop.
F
Proofs
F.1
Proof of Proposition 1
For every environment Etrain, we observe the first moments (X,) and E (Y.), and second moments E (X,X)) E (Y²2) and E (X.Y.). Since it holds by assumption that μio 0 and En we have that IE (XoX,) Mn and can identify 2n uniquely. Furthermore, it holds that
(XxY) = g + 2
(38)
E (X.Y.) = EE. + Mell +2, + E
(39)
By taking the difference between Equation (39) and Equation (38), can identify (Ee + Mel. ) Thus, the parameter 8 is identifiable on the subspace S defined in Equation (12) and is not identifiable on its orthogonal complement S Thus, for any vector a E S the vector 8 = 3 a is consistent with the data-genent gentratgnnraiing process. It remains to compute the covariance parameters induced by an arbitrary B := 3 + for E St. For every environment e E Etrain, the second mixed moment between Xe and Y. has to satisfy the following equality
E (X,Y)) (E, + Moltl ," + E
(E, + MoMe +E,) + +.nss
from which follows that En,e = Di - Ejj. a. By computing (Y?") and inserting = 3" + a and Eng,, similarly obtain
oे = ( -2 E a E TT
Thus, we obtain the following set of observationally equivalent model parameters consistent with Puramum
Ozg (8
Eja, (o²) -a E + a
Since the observationally equivalent set identifiable from the training distribution, but model parameters 3*, E (a²)² are not, is helpful to re-express the observationally equivalent set through
identifiable quantities. For this, we note that the "identifiable linear predictor" 85 = g5 induces an observationally equivalent model given by
0s = (88 2g s (a (BS, Mi 2 + 27,3 (a;))² 2 88 } (88' -,233' )).
From this reparameterization, we infer the final form of the observationally equivalent set:
Oon 135 E E 20, 2xx En + +a + E, E S 0"
Therefore, Equation (13) follows. To find the robust predictor grab, we write down the robust loss with respect to Miest and any 0₂ from the observationally equivalent set
Rrob [3; On Muest) (g8 + BB (Muest + (35 + aa-a B3)
+ 2 + a - B) (E E,,0) + (oe)² 2ax T + a Ttao
inserting a E S and rearranging, Equation (14) follows.
F.2 Proof of Theorem 3.1
We structure the proof as follows: first, we quantify the non-identifiability of the robust risk by explicitly computing its supremum over the observationally equivalent set the model parameters (referred to as the worst-case robust risk). Second, we derive a lower bound for the worst-case robust risk by considering two cases depending on how a predictor 3 interacts with the possible test shifts Mest-
We use 2020 13-inch MacBook Pro with a 1.4 GHz Quad-Core Intel Core i5 processor, 8 GB of RAM, and Intel Iris Plus Graphics 645 with 1536 MB of graphics memory.
26

---

Computation of the worst-case robust risk. For any model- generating parameter = (.,E) it holds that the robust risk the model Equation (3) under test shifts Mustt = 0 given by
Rrob (3; 0, Mtstt (B -8- (M + 2,, 3) 2(3 B) En, (at)².
We recall that the observationally equivalent set of model parameters after observing the multi- environment training data Equation (3) given by
eg 1 a, 27, -n.55 - 2ija. ( 2a 2. + Σiya : : a E
(40)
where S is the span of identified directions defined in Equation (12). Moreover, we recall that by Assumption 3.2, for any causal parameter 3 should hold that || = || + all2 S C, which translates into the following constraint for the parameter at
||al2 S V C ||35||3 Cker.
Inserting Equation (40) in Equation (9), obtain
Reub (B; egg Musst)
sup
Reob Ua; Mest),
aes!. ||allaSCan
SS where Oa is a short notation for (BS + a, Mi, 2 - -7, (o - 2a T 23 + T a)) We now compute the supremum explicitly in case Mistt has the form Must 7M + + A/RR_ where Maven is a PSD matrix with range M C S and R is a semi-orthogonal matrix with range R S+ For any a E S-, we write down the robust loss
Reob (3; Meest)
(BS - -3) (Mest + 13) -3) + 2(B - -3) + (o
+ a Miest + 2a T -B
= Ryob (3; 05, .Meea) + a Miest + 2a Mrest(0 - -B).
The first term is the robust risk of 3 under test shift Mtest and the identified model generrtgnn parameter 85, thus it does not depend on a. By the structure of Mrest, we obtain that
f(a) == a Mrest + 2a Mrea( - B) = naaa aaRa--aa RRT B.
If = 0, i.e., the test shifts consist only of the identified directions, we have f(a) O, independently of a, and thus
Riob (3; Oeq Mrest) RBo 0$, MMest).
This implies the first statement of the theorem.
We now consider the case where R * 0, i... RR is nen-degenerate projection. Our goal is to maximize f(a) subject to constraints a E S ||al22 I Cker. Let R be an orthonormal extension of R such that range (R) (R) R) = L Then, we can parameterize a S as = (R) ( and the corresponding Lagrangian reads
C(a, = aaaa T RR a --yaaaa ATTRRT 3 X(C ||a|1))
= >> - > RT3 + X(C2.r - [1( 1)
Differentiating with respect to w, à yields
7 R 7' X
"
3
After differentiating w.r.t. X, we obtain comparing, we obtain the value the worst-case robust risk: 22=xx
C A1l
By inserting in the objective function and
Rrob( Oeq, Meest) = 2'2 + 2 B112 + Rrob 05, Mtest)
(41)
= =CCh.r + 2 B112 B RR B + 788 g - B3 Maren (BS -3) + Ro (B, 08).
(42)
27

---

Putting together the two cases and simplifying, we obtain
Ryob (3; Deq Meest) (Cker + || B112)² Rrob 00 Mseen)
(43) where Ryob (5; 8 (M is the robust risk of the estimator 3 w.r.t. the "identified" test shift yM and the identified model parameter 0s, whereas Ru(3, 08) is the risk of 3 on the reference environment e O.
= (Oke + || 3112) + - 33 ( - ).)
Derivation of the lower bound for the worst-case robust risk. Now that we have explicitly computed the worst-case robust risk, we devote ourselves to the computation of the lower bound for its best possible value
inf Reob (B: Ogg. Meest).
BER*
In this part, we will only consider the case o O, since the case R = 0 corresponds to the (discrete) anchor regression-like setting, where both the robust risk and its minimizer are uniquely identifiable, and computable from training data. We will distinguish between
cases.
Case 1: || || B12 = O. In this case, B is fully located in the orthogonal complement of R, which
consists of S and Rt (the orthogonal complement or R in S²). We will denote (the basis of) this subspace by Stot = S @ R. Thus, Stot is the "total" stable subspace consisting of identified directions in S and non-identified, but unperturbed directions R. We will parameterize B as 3 S. W. Thus, we are looking to solve the optimization problem
Se = arg min (88 - r) (y seen + 2 Stort)) - 2(3 - Seat T D + (o))²
Setting the gradient to zero yields the asymptotic worst-case robust estimator
peen = 3 + StoalStoe (T:M + -
(44)
which corresponds to the loss value of
Reob (Btoll Oeqs Musa) 7' Cher + ( 2 T Stor StotlS (To + En)Sstol''SS S
Stot SS
As we observe, this quantity grows linearly n However, as y + oc, the quantity saturates and upper-bounded by (o
Case R B|12 * O. Since for || B112 O, the objective function is differentiable, we compute its gradient to be
VR. Oegi Mrsst) RR' 8/||RR B11 + R//RR 8 (Reob 0 >MMeeau)
=R' R/| B B|| 2-/RRR 3 2(2,, Masee) (B 3 2>% This equation is, in general, not solvable w.r.t. 39 in closed form. Instead, provide the limit of the optimal value of the function when the strength of the unseen shifts is small, i.c. 7 + O. We know that for 7 0, the minimizer of the worst-case robust risk is given by the anchor estimator
Banchor = 3 + (2); + M -1 2
Instead, we lower bound the non-differentiable term 2 || B|| by the scalar product 2r'Oher (R 3, R. Banchar) / || and expect it to be tight for small 7/. After inserting this lower bound Equation (41) we obtain the minimizer of the lower bound of form
BLB = S + (E; + 7M + ('RRT)
-ESS - -Kerr RR. (E, + +M)
5 5.
We can now lower bound |RR BLal|as as
||R BLBlI 2 |RR (E,, - - const. Thus, the 7rrate of the worst-case robust risk of BLB is at least Y(Creer + ||R (E; yM)-
(45)
2 11, + 2),)), )))?)) from which the claim for small y follows. For Section 3.2, the lower bound directly implies optimality of the worst-case robust risk of the anchor estimator when the strength of the unseen shifts 7 is small. Additionally, if i = 0, i.e. only unseen test shifts occur, we conclude that the OLS and anchor estimators have the same rates.
28

---

Lower bound Váh for y'. Finally, we want to derive a lower bound on the shift strength > such that for all 7 2 7hh Case 1 of our proof is valid, i.c. it holds that S is given by the closed form "abstaining" estimator (44). For this, we find Y/ such that for all y 2 Yi zero is contained in the subdifferential oo ; eeq Mest) at g Then the KKT conditions are met, and g is the unique minimizer of the worst-case robust risk due to strong convexity of the objective. We compute the subdifferential to
S == n'ker
( ( (RR B: 118112 S 13 + To ( 0 -YM).
Since agch is the minimizer of Rrob (8; 08 7 Moson)) under the constraint R O, the gradient is zero in I-- and it remains to show that
|RR VRrob 08, >MMeen)l S Skees
or
/ |RR (Rrob(PB 08, 7rMMsen)ll/Oeer
Via an upper bound on the projected gradient, we derive the stricter condition
|RR ES 9. 111
Oker
where Ks k(E))) is the condition number of the covariance matrix.
F.3 Proof of Corollary 3.2
To obtain a new formulation for the worst-case robust risk, we start with (46) and expand
Rrob( Seg Meest)
7 Y(Ckerr + | 11) + 7(88 -B) Manchor (08 - -3) + Ro(3,
(Ckeer ker + |R B112) + 7(8 -3) Manchor (8S- -
+ (88 - -3) T (35 - -3)+ 2
+
-B) + (o
=C'(Cker + | 1122) + (r- 1)(3 -B) Mauchor (BS - 3) R(B, P.X.
(46)
where we have used that the pooled second moment of X equals to Σ + E. we(Hette) Σ; y Manchor - (7 Manhhrr This reformulation shows that the worst-case robust risk is equal to the anchor population loss (cf. [41]) with an additional non-identifiabilit penalty term y'(Cker | 3
We now want to evaluate the rates of the anchor and OLS estimators in terms of the magnitude > of unseen shift directions. We observe that only the non-identifiability term depends on y' whereas the second term only depends y. First, we compute the closed-form anchor regression estimator, which reads
Banchor = arg min (3, 05, >aancho)) = = + (E, + +0,,++MM Manchor) - m
-
(47)
BERd
Since BoLS equals to the anchor estimator with 7 1, we obtain
BolS 3 + (2, M 2n.
The claim of the corollary now follows by computing || |R Bancherll and RR BolS and observing that the rest of the terms is constant /
Comparing to the lower bound (45) for the minimax quantity for the case of n + 0, we observe that the anchor estimator is optimal (achieves the minimax rate) in the limit y + 0. Additionally, i = 0 (only new shifts occur during test time), anchor and OLS have identical rates in 7 and, in particular, OLS (corresponding to vanilla empirical risk minimization) is minimax-optinal in the limit of small unseen shifts.
29

---

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: We state our contributions relative to prior work in the abstract, in Section and in Appendix A.
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 the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation 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: In the abstract and in Section 1, we highlight the setting that we consider. We explicitly describe the assumptions in Section 2 and summarize the limitations in Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a 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 (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on 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 on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 to address problems of privacy and faimesss.
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?
30

---

Answer: [Yes]
Justification: Appendix contains proof' of all results appearing in the main paper. Ap- pendix B, Appendix C, and Appendix D are self-contained and contain derivations and proof the results.
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 the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofss provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Appendix E provides all the necessary information to reproduce the experi- mental results presented Section 3.2. We provide details on empirical estimation of the proposed loss function in Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is 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 novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is 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 NeurlPS does not require releasing code, the conference does require all 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 to reproduce that algorithm.
(b) 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 reproducibility may be tricky in some cases, in which case authors are welcome 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 (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
31

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [No]
Justification: While we do not provide the code, the paper provides all necessary information on reproducing the experiment in Appendices D and E.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
Seriidees/CoeeSubisssiiic.
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //n /nips..cccc https/ccccbbcc/gucieeeeeeeeec wwwiiiigggue////eeeeeeeeee Sateee//doeSSueeeeeee wwsssnooicccyyi 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. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: We specify all details understand the experimental results in Section 3.2 and Appendix E.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to 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
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
In the numerical experiment, shown in Figure 3, we provide the average test MSE and its 5% and 9 over 100 repetitions for each method.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
32

---

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 run with given experimental conditions).
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).
It should be clear whether the error bar is the standard deviation 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 range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question:
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?
Answer: [Yes]
Justification: The numerical experiment described in Section 3.2 computationally very light and can be
personal laptop in few minutes. We describe this in Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or 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 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 make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https :tttps://nuurs htt////eeurrppeeeeee cc htcp/pubiiccthhcssueeeeeeeeeeeee
Answer: [Yes]
Justification: We have read the NeurlPS Code of Ethics and confirm that our work conforms to in all aspects.
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 circumstances that require deviation from the Code of Ethics.
The authors should make 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 socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification: Even if our work addresses the theoretical limits of distributional robustness, we mention in the abstract and in Section that the topie of distributional robustness central to safety-critical applications.
33

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymemt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to 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 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 ML).
11. Safeguards
Question:
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)?
Answer: [NA]
Justification: The work develops theoretical framework and considers synthetic experi- ments. Therefore, explicit safeguards do not seem applicable this stage.
Guidelines:
The answer NA means that the paper poses no 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 to 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses 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: In the numerical experiment in Section 4, we cite the existing work that we compare framework and the dataset used. In running the numerical experiment, reimplemented all the methods (including existing ones) for ease of comparison.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
34

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset'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:
At this stage, the paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mmoel as part of 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 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 as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing experiments research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing experiments or research with human subjects.
35

---

Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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 to 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.
36


Reviews:
[{"review_id": "uyeppiVqOm", "reviewer": "Reviewer_PdW8", "summary": "The paper studies a linear Structural Causal Model (SCM) for prediction under distribution shifts due to an an additive term to covariates that changes at test time, and an unobserved confounder between the covariates and the label. The key difference between the proposed analysis and those presented in other works (e.g. those in anchor regression, invariant causal prediction etc.) is that the shift is bounded in its strength. Another difference is that the optimal robust predictor w.r.t the entire uncertainty set is not identifiable. Hence, instead of the optimal robust error, the paper studies the optimal error that can be achieved from observable data. This corresponds to the robust error over an uncertainty set that is generated by all SCM parameters that could have produced the training data, which is in general a larger set than the uncertainty set we are interested in (i.e. of bounded additive shifts to the covariates).\n\nOnce the problems is set up, a parametric form for the set of parameters that can generate the training data is derived, along with the corresponding set of possible robust predictors. Then under a mild assumption on boundedness of the ground truth regression parameters, the following are derived: 1) a closed form is derived for the robust loss in the case where test distributions only induce shifts in directions that have been observed at training. The loss grows linearly with the strength of the shift; 2) a lower bound on the achievable risk from observed data, which is tight (and thus can be learned from observed data) for large enough shifts.\n\nFurther analysis and simulations with Gaussian data are done to compare the risk of the derived estimator with that of ERM and anchor regression (which does not exploit the boundedness of shifts to achieve better prediction). The results verify that the risk obtained by the proposed empirical estimator are close the lower bound given in the theorem, and outperform the two baselines as shifts grow large.", "questions": "* It could’ve been nice to derive upper bounds on the robust loss in addition to the lower bounds proved in the theorem. That is, assuming these bounds can be calculated from observable data, I’d imagine that most practitioners would be more interested in an upper bound as it gives a strong guarantee on the risk worst possible risk. Do you think this is a reasonable goal, and do you perhaps have any insights on this? \n* Could you perhaps discuss the differences between the empirical optimization problem you derived in the paper and those derived in prior work? For instance, looking at eq. 19 in appendix D, it seems like there is a term that penalizes $\\|\\| \\hat{S}^\\top(\\hat{\\beta}^{\\mathcal{S}} - \\hat{\\beta}) \\|\\|$ which I read as the weights in the “invariant directions” should be the same across the environments. This seems quite similar to ICP, IRM etc. Then the other term limits the projection on the shifting directions, but it might be useful for readers to have a short discussion on the conceptual similarities between this and penalized versions of other methods. Also, there might be a typo in that equation, $\\mathrm{arg}\\min_{\\beta\\in{\\mathbb{R}^d}}$ should be $\\mathrm{arg}\\min_{\\hat{\\beta}\\in{\\mathbb{R}^d}}$ instead.", "limitations": "The authors have adequately discussed limitations.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* Overall I enjoyed reading the paper, it is clear and written with care. Generally, I also like the direction of formalizing bounded shifts and unidentifiable settings in detail. Finally, the analysis is well performed and easy to follow.\n\n* The work is original in formally analyzing bounded distribution shifts, where even in population the optimal robust predictor might still have non-zero projection on directions that shift at test time. \\\nSmall note on this: I think that for finite sample guarantees boundedness assumptions on the strength of the shift must be made, and they are made in works that give sample complexity results. I believe the reason is that with unbounded shifts, any small weight on a shifting feature can be magnified unboundedly to yield a large robust error. With finite samples, it is usually impossible to guarantee strictly zero weights on the shifting directions. Therefore it might be worthwhile clarifying that considering the population loss is an important component for the analysis.\n\n* Beyond the points mentioned above, the bounds on the robust risk, closed form solutions, and the formalism used in the work, can be useful for future theoretical analyses. In terms of practical significance, the approach derived from these results to explicitly account for bounded shifts might be useful in the future, if it is generalized beyond linear models.", "weaknesses": "* As mentioned above and the authors mention in describing the limitations of their work, it is restricted to linear models. Intuitively, a considerable challenge in learning robust models is to identify the ``directions” that shift between domain. Under linear models it is rather straightforward, and the method proposed in the paper depends on linearity of the model in order to find these directions. This is unlike some other methods in the domain generalization literature, where certain formal results are provided on linear models but the methods can easily be tested in the non-linear case.\n*  Even within the realm of linear models, I am not throughly convinced that the method is useful in real world problems. To make this more convincing, it might have been nice to run simulations over non-synthetic data and some more variants of methods. E.g. using several methods that learn invariant models when hyper-parameter tuning is performed with the objective proposed in this work may be of interest. That is to see whether boundedness of the shift should be taken into account during training, or is it enough to simply use it for model selection. Yet the most significant drawback is still of course, the limitation to linear models.\n\nSome other/smaller comments:\n* In line 60 prior work is cited to claim \"that even minor violations of the identifiability assumptions can cause invariance based methods to perform equally or worse than ERM\". However, I am not sure that the failures portrayed in these works are strictly due to identifiability violations. At least not the ones alluded to in this paper, which is the lack of heterogeneity in the training environments. In Kamath et al. 21, the predictor is identifiable but the problem is specifically in the IRMv1 objective, see also [1] who point out an objective that solves this issue. In Rosenfeld et al. 20, only one failure is due to not having enough environments (and arguably, this is since they consider the uncertainty set that includes shifts in all directions. I will also touch on this in the next minor comment), and the second one is due to non-linearity.\n* Regarding analysis under lack of heterogeneity or unidentifiable optimal robust predictor: I think that the part of the analysis that touches upon the insufficient heterogeneity of the environments in order to identify the robustness set/robust predictor can be slightly reframed. If I am not mistaken, even in works that give results about identifiable robustness sets (e.g. when the number of environments is linear in the number of shifting features, or stronger ones like [2]), it is most likely possible to draw guarantees about robust risks, but only with respect to a smaller uncertainty set which is restricted to dimensions that shifted between the training environments. That is since the methods still enforce constraints which restrict weights in certain directions. While it is true that most of these prior works did not consider unidentifiable uncertainty sets, it might be related to choice of presentation, and not strictly because the methods are technically limited in that sense. Further, in lines 168-169 it is claimed that “prior work only considers scenarios where the robustness set and hence also the robust prediction model are still identifiable”. I am not sure this is entirely true. There are different formalisms that were considered for spurious correlations, such as those in [3]. In their setting, when the association is not what they call “purely spurious”, then the robust predictor cannot necessarily be recovered. Also [4] study a similar setting where due to similar reasons no guarantee can be given on identifying the robust predictor, but only a lower bound on the error is given.\n* It might be worth mentioning in lines 112-113 that in case $H$ in figure 1 is a selection variable (I assume it can be since both edges are bi-directional) then the shift reduces to covariate shift, if I am not mistaken.\n* Personally, I found the notation in the introduction which uses $\\mathrm{shift}\\in{\\mathrm{shift set}}$ etc. somewhat redundant and confusing. The more formal notation in section 2 onwards was much easier to understand, so in my opinion it might be worth considering to go straight ahead into that notation.\n\n[1] Wald Y, Feder A, Greenfeld D, Shalit U. On calibration and out-of-domain generalization. Advances in neural information processing systems. 2021 Dec 6;34:2215-27.\n\n[2] Chen Y, Rosenfeld E, Sellke M, Ma T, Risteski A. Iterative feature matching: Toward provable domain generalization with logarithmic environments. Advances in Neural Information Processing Systems. 2022 Dec 6;35:1725-36.\n\n[3] Veitch V, D'Amour A, Yadlowsky S, Eisenstein J. Counterfactual invariance to spurious correlations in text classification. Advances in neural information processing systems. 2021 Dec 6;34:16196-208.\n\n[4] Puli AM, Zhang LH, Oermann EK, Ranganath R. Out-of-distribution Generalization in the Presence of Nuisance-Induced Spurious Correlations. In International Conference on Learning Representations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating the overall direction and clarity of our paper, as well as originality of our work. We are grateful for the constructive comments and will incorporate the minor points in the revised version of the paper. We now respond to some of the major points and questions.\n\n**Linearity of the model** We acknowledge that understanding which shift directions are “learned” and which are “unobserved” during training time for more general, nonlinear models is an important direction for future work. We further recognize the linearity of our setting as a limitation. We would like to clarify that the main contribution of our paper is not primarily to propose a new method for domain generalization (that can then also be tested in non-linear settings), but to introduce and make a first step towards quantifying the limits of robustness in a partially identifiable setting. On this note, we expect that the results and intuition developed in this paper for the linear case can be utilized beyond linear models, since realistic distribution shifts can be often reduced to linear shifts in a lower-dimensional latent space via a suitable parametric or non-linear map [5, 6]. \n\n**Evaluation of the method in real-world settings** Even though the method is not necessarily the focus of our paper, we agree that our work could benefit from a more thorough evaluation on real-world data. To this end, in the attached PDF, we present preliminary results of experiments on real-world single-cell gene expression data [7]. The dataset consists of single-cell observations of over 622 genes from observational and several interventional environments, arising through a knockdown of each unique gene. We pre-select always-active genes in the observational setting, resulting in a smaller dataset of 28 genes. We measure the performance of our method, the identifiable robust predictor (Rob-ID), compared to other algorithms [10, 11, 12], as follows. We select each gene once as the target variable $Y$ and select the three genes most strongly correlated with $Y$ (using Lasso), resulting in a smaller dataset. \nGiven this dataset, we test on all combinations of training (observational + one shift) and test environments (other shift).  \nWe train the algorithms on the training environments and evaluate them on the test environments using mean square error (MSE). The results in Figures 2(a) and 2(b) indicate that Rob-ID outperforms existing distributional robustness methods, particularly for larger shifts in new directions.\n\n**Failure cases of IRM as motivation for our work** We agree that while the cited papers include non-identifiability as failure cases (Kamath et al. ‘21 Section 4 and Rosenfeld et al. ‘20), they also discuss other possible reasons for failure. We can clarify this in the revised version by adding that multiple failure cases have been discussed in the literature (citing these papers), one of which is non-identifiability, the focus of this work.\n\n**Application of existing work for partially identifiable case** We agree that prior methods can be applied and evaluated in the non-identifiable setting even though prior analysis so far has focused on the case where the robust risk was identifiable (including your described case when the ”uncertainty set which is restricted to dimensions that shifted between the training environments”). In fact, one of the goals of our paper was exactly to evaluate prior methods in this new setting.\n\n**Existing formalisms for spurious correlations**\nWe thank the reviewer for pointing us to relevant and interesting works [3] and [4]. Although these works describe cases where the optimal robust predictor cannot be recovered, they seem to be binary negative statements in that they do not provide a quantification of this failure nor a proposed method for robustness in this failure case.\n\n**Q1 (upper bounds)** In our result, for $\\gamma > \\gamma_{th}$, the value of the inf sup is exact, thus, in Theorem 3.1, Case (b) line 2 it is both a lower and an upper bound (we will clarify this in the main text). For small $\\gamma$, the loss of the anchor regression estimator is a tight upper bound – which for the practitioner means that if the shifts in unknown directions are expected to be very small, the anchor estimator is optimal.\n\n**Q2 (connections to invariance objectives and regularizers)** Thanks for the suggestion, we will include a more intuitive interpretation of the individual terms in the revised manuscript. In particular, we will discuss the population objective (13) that corresponds to the empirical objective in (19) when we replace $S$, $\\beta^S$, $R$ by their empirical estimates. The objective  consists of three parts: 1) loss on the reference environment (without any distribution shift), 2) the term $||S^\\top (\\beta^S - \\beta)||$ that “aligns” $\\beta$ in the directions of the true causal parameter $\\beta^\\star$ projected on S, and 3) the term $(C_{ker} + || R^\\top \\beta ||_2)^2$  that shrinks $\\beta$ in the directions unseen during training. Since $\\beta^\\star$ is the optimal invariant predictor (although unknown), the second term can be interpreted as aligning the estimator towards the true invariant predictor along the observed shifts (and hence corresponds to inducing invariance across training environments, spiritually corresponding to the invariant literature as the reviewer pointed out).\n\nFor citations, please refer to the general rebuttal out of space reasons.", "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": "30LuP4EMPs", "reviewer": "Reviewer_iX3g", "summary": "This paper proposes a new framework for distributionally robustness under the linear causal setting. Specifically, the authors minimize the so-called identifiable robust risk, which corresponds to the maximum of the robust risk for parameters in the observationally equivalent set. Under such partially identifiable robustness framework, they discuss the lower bound of the risk and show that some estimated identifiable robust predictor can achieve that lower bound risk, where the corresponding empirical version can approximate the lower bound risk well. They also validate the better performance with finite sample numerical experiments.", "questions": "-\tCan the authors highlight a bit more on the (approximated) real-world example when the predictor is partially identifiable? Since it may be a bit unfamiliar to the general DRO audience for these notations and their relevance in practice.\n-\tCan the authors elaborate more on how the empirical estimations for the space of the training shift direction $\\hat S$ and $\\hat R$ are computed, as compared with the current version in Appendix D? From my preliminary understanding, this space determination is important for subsequent estimation.\n-\tThe potential utility of **active intervention selection** is also interesting, and it seems aligned with some recent relevant work on distribution shifts. For example, in causal explanation [1] and incorporating specific features in improving distributional robustness [2]. I am wondering if the authors can provide more details on how their own intervention is and the connections with these existing literature, which can be potentially incorporated in the main body and appendix.\n\n[1] Quintas-Martinez, Victor, et al. \"Multiply-Robust Causal Change Attribution.\" arXiv preprint arXiv:2404.08839 (2024).\n\n[2] Liu, Jiashuo, et al. \"On the Need for a Modeling Language Describing Distribution Shifts: Illustrations on Tabular Datasets.\" arXiv preprint arXiv:2307.05284 (2023).", "limitations": "The authors discuss the main limitation of this paper, which I think is reasonable compared with existing literature.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-\tThe motivating illustration and results are very clear;\n-\tThe direction the authors study is interesting in bridging the structure and non-structure of distributional robustness.", "weaknesses": "-\tSome paragraph in the training and testing data part can be reorganized as some formal assumptions, such as the assumption of M_{test} and linear assumption as well as the discussion in Section 3.2 in terms of the definition of S and M. This gives a clear picture on what some key conditions (and possible relaxations) are in this paper.\n-\tThere are a few missing details (see Questions as follows), which I hope the authors can explain them a bit more.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for pointing out the novelty of the direction of our study. We are happy to fill in on the missing details below: \n\n**Q1 (real-world example of partial identifiability)** Indeed we can give a toy example that illustrates our abstract setting in Section 3.1: suppose that we are conducting a long-term medical study, where data is collected from the same group of patients over the years to predict a health parameter $Y$, e.g., cholesterol level in blood, from a group of covariates $X = (X_1, …, X_n)$ such as age, blood pressure, physical activity, resting pulse, BMI etc. We assume that the data $(X, Y)$ are generated by an underlying causal model, in which not every variable is observed (i.e. there might exist latent confounding). During training time, we are given data $(X^e, Y^e)$ for $e \\in E_{train}$ from multiple past studies, where $E_{train} = \\{2010, 2015\\}$ are the years in which the studies were conducted. We now want to train a model which generalizes best on data $X^{2020}$ collected in 2020. \n\nIn such a setting, we can expect that the distribution shift between the data in 2010, 2015 and 2020 is not entirely arbitrary: for example, the covariates such as age ($X_1$) might shift similarly between 2010 to 2015 and 2015 to 2020, whereas other covariates such as physical activity ($X_2$), BMI ($X_3$) or resting pulse ($X_4$) may exhibit unseen, but bounded shifts (e.g. due to a disease outbreak such as Covid). This is an example of a structured distribution shift. We observe that we can identify the causal parameter $\\beta^\\star$ in the direction of $X_1$, since there is a shift of age across the training environments. However, the causal parameter is not identifiable for $X_2$ if the distribution of physical activity has not shifted in previous studies. This renders the causal parameter, and (since the test data shifts in the direction of $X_2$) the robust risk of the problem, partially identifiable. In this setting, only $X_1$ is guaranteed to give an invariant prediction, but an estimator which just uses the age might not have enough predictive power. Instead, we suggest to also utilize the spurious correlations between $X_2,...,X_4$ and $Y$ to predict the target variable, but penalize the predictor in their directions based on the strength of the expected test shift (e.g., we do not expect the average resting pulse to shift by more than 10). \n\n**Q2 (empirical estimation of S and R)** Indeed, empirical estimation of the subspaces $S$ and $R$ is an important part of the practical application of our method. We will add to the manuscript that the space $S$ can be computed from the second moments of the observed distribution via $S := \\text{span} \\cup_{e \\in E_{train}} [(\\Sigma_e - \\Sigma_0) + (\\mu_e - \\mu_0)(\\mu_e - \\mu_0)^\\top]$, and can be estimated via empirical means and covariances of the training distributions. Results on the consistency of estimation of the eigenvectors when the dimension is fixed and eigenvalues are finite are given, for example, by [1]. For the test shift, there’s either prior information on their direction available via a subspace $M$, which we can incorporate by setting $R = \\Pi_{S^{\\perp}} M$, or, if not, we may take the conservative estimate of $R$ being the orthogonal complement of $S$. The downside of this choice is that the robustness requirements might be more restrictive than necessary. \n\n**Q3a (active intervention selection)** Thanks a lot for this comment. Although we plan to have a longer elaboration of this topic in the full manuscript, we briefly discuss here how our approach might be utilized for active intervention selection. In Equation (31), the identifiable robust risk is given by a supremum over the possible true causal parameters from the observationally equivalent set. The argmax of the supremum (which depends on the estimator) utilizes partial identifiability to find the “most adversarial” direction for the test shift, along which the given estimator will suffer the highest test risk. One can actively sample the next dataset by performing an intervention along this direction, which will maximally decrease the identifiable robust risk (31) of a given estimator (e.g., OLS). This procedure can then be repeated.\n\n**Q3b connections to listed literature** In [2] (causal change attribution), the main difference seems to be that the causal graph is known and the objective is, instead of robust prediction, causal change attribution. A conceptual similarity seems to be that [2] allows for recovery of the target parameter under partial misspecification. However, in our framework this would mean that although some components of the model might be misspecified (or, in our words, underidentified), the target parameter is still identifiable – thus, we would call the setting in [2] identifiable under the listed assumptions, similarly to the case of anchor regression. [3] is fairly related to our work motivation-wise: our model allows for $Y|X$-shifts in addition to $X$-shifts, consistent with the observation that $Y|X$-shifts frequently occur in tabular data and cannot be neglected. \n\n\n[1]: Anderson TW. Asymptotic theory for principal component analysis. The Annals of Mathematical Statistics. 1963 Mar;34(1):122-48.\n\n[2]: Quintas-Martinez V, Bahadori MT, Santiago E, Mu J, Janzing D, Heckerman D. Multiply-Robust Causal Change Attribution. arXiv preprint arXiv:2404.08839. 2024 Apr 12.\n\n[3]: Liu J, Wang T, Cui P, Namkoong H. On the need for a language describing distribution shifts: Illustrations on tabular datasets. Advances in Neural Information Processing Systems. 2024 Feb 13;36.", "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": "g3rHvTpyiA", "reviewer": "Reviewer_faJC", "summary": "This paper investigates the optimal minimax risk of a robust predictor when the robustness set is partially observable, under a structural causal model with hidden confounders. By decomposing the test covariance matrix of latent parameters into a component spanned by the training distributions and the orthogonal component, it is shown that the robust predictor is only identifiable if the test shifts are in the direction of the training shifts. While for unobserved test shifts, the best achievable minimax risk grows linearly with shift scale. The theory is applied to show sub-optimality of OLS and anchor regression with partially observable test shifts.", "questions": "1. Typo: L137, the sub-space.\n2. In Fig 1, bidirectional edges don't make sense for causal graphs, and it's not explained either. Moreover, is there exact equivalence between Fig 1 and the SCM in Eq 2?", "limitations": "The author has addressed limitations with regarding to the model, e.g., linear structure and additive noises.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I am not familiar with the field of causal inference, but it appears from the paper that it has made contributions as the first result for distributional robustness or invariant causal prediction when the robustness set is partially identifiable. Particularly, it shows that infinite robustness is impossible under this scenario, and finite robustness methods can show performances reduced to ERM. This echoes empirical evidence and provides a possible theoretical explanation for reported failure of distributional robustness methods under wild environments.", "weaknesses": "The structural causal model in Eq 2 and the resulting explicit solution in Eq 6 shows that the model is biased even without distribution shifts. To see this, take $\\gamma =0$ in Eq 6 and the predictor does not reduce to $\\beta^\\star$. The model is unbiased only when the cross covariance between $\\eta$ and $\\xi$ vanishes, which implies no hidden confounder and only covariate shift. In contrast, the classic approach for invariant causal prediction [1] produces unbiased estimation beyond covariate shift.\n\n[1] Arjovsky, M., Bottou, L., Gulrajani, I., & Lopez-Paz, D. (2019). Invariant risk minimization. arXiv preprint arXiv:1907.02893.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating the contribution of the paper and precisely summarizing its main idea. \n\n**Bias of the structural causal model** The reviewer is correct that the causal effect estimate would be biased when the cross-correlation between the noises $\\xi$ and $\\eta$ is not 0. We would now like to argue that this is a feature rather than a bug. First, we would like to clarify that this paper considers the prediction performance, or MSE, during test time. Therefore, having a biased causal effect estimate does not necessarily affect the test performance, which is still optimal for $\\gamma=0$ (no shift). Furthermore, allowing for latent confounding (expressed via cross-correlation of $\\eta$ and $\\xi$) only makes our model more general and the problem much more challenging to solve. The presence of confounding creates a tradeoff between predictive power and robustness (see, e.g., [2]).\nFurthermore, we would like to highlight that even IRM might not always produce unbiased estimates of the causal coefficient. For example, in [1], the synthetic data experiment shows that IRM and OLS have a bias of similar magnitude in a confounded setting with homoskedastic noise. \n\n**Q2 (bidirectional edges)** Normally, a bidirectional edge $X \\leftrightarrow Y$ between two nodes indicates latent confounding. In Figure 1, we explicitly list the latent confounder $H$, resulting in the notation $X \\leftrightarrow H \\leftrightarrow Y$,  to express that the latent confounder can be both an ancestor and descendant of $X$ and/or $Y$. More precisely, we allow for the following scenarios: $X  \\rightarrow H \\rightarrow Y$, $X \\leftarrow H \\rightarrow Y$, $X \\rightarrow H \\leftarrow Y$ (the fourth one is excluded due to the acyclicity constraint). \n\n**Q2 (equivalence of Figure 1 and the SCM)**  To see the equivalence between the SCM and DAG, it is helpful to consider the three configurations discussed before. When $X \\leftarrow H \\rightarrow Y$, the causal coefficient $\\beta^\\star$ equals the weight of the path $X \\rightarrow Y$. In this setting, $\\eta$ and $\\xi$ are correlated via $H$. When $X \\rightarrow H \\rightarrow Y$, the causal coefficient $\\beta^\\star$ equals the sum of the weights along the paths $X \\rightarrow Y$ and $X \\rightarrow H \\rightarrow Y$. In this setting, $\\eta$ and $\\xi$ are independent. When $X \\rightarrow H \\leftarrow Y$, the causal coefficient $\\beta^\\star$ equals the weight of the path $X \\rightarrow Y$. In this setting, $\\eta$ and $\\xi$ are independent. \n\n[1]: Arjovsky M, Bottou L, Gulrajani I, Lopez-Paz D. Invariant risk minimization. arXiv preprint arXiv:1907.02893. 2019 Jul 5.\n\n[2]: Rothenhäusler D, Meinshausen N, Bühlmann P, Peters J. Anchor regression: Heterogeneous data meet causality. Journal of the Royal Statistical Society Series B: Statistical Methodology. 2021 Apr;83(2):215-46.", "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": "q310WHcCLY", "reviewer": "Reviewer_2y9v", "summary": "This paper proposed a general framework of partially identifiable robustness to evaluate robustess in scenarios where the training distributions are not heterogeneous enough to identify the robust risk. They define 'the identifiable robust risk' and its correspondig minimax quantity. They show previous approaches achieve suboptimal robustness in this scenario.  Finally, they propose the empirical minimizer of the identifiable robust risk and show that it outperforms existing methods in finite-sample experiments.", "questions": "1. On line 135-137, the $M_{\\text{test}}$ is defined as  $M_{\\text{test}}=\\gamma\\Pi_{M}$. What's the reasoning behind this choice?", "limitations": "yes", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is crealy written. The idea of establishing partially identifiability to fill the gap between an \"all-or-nothing\" view on robustness in the SCM framework is interesting.", "weaknesses": "I am not an expert in this field so I cannot point out many weaknesses. Maybe one thing is the lack of motivation from real-world application, such as in what applications or when the proposed framework is usefull in practice?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are glad that the reviewer appreciated the main idea of our paper. In the following, we hope to clarify the real-world motivation for our study and some theoretical assumptions. \n\n**On real-world applications** The main motivation for our paper was expanding the existing assumptions in distribution shift literature to allow for a statement in a more realistic setting, particularly in safety-critical applications. We wanted to account for the fact that distribution shifts are mostly bounded in the real world and occur in “realistic” directions. Contrary to many existing results, in the real world, we rarely have access to enough training environments to achieve point identification of the “best” robust predictor. Instead, we aim to study the “best” model if only a few training environments are given, but the distribution shift (in potentially new directions) is not too large. In the following, we provide a **toy example**, motivated by medical applications, that illustrates our setting. \n\nSuppose we are conducting a long-term medical study, where data is collected from the same group of patients over the years to predict a health parameter $Y$, e.g., cholesterol level in the blood, from a group of covariates $X = (X_1, …, X_n)$ such as age, blood pressure, physical activity, resting pulse, BMI, etc. We are given data $(X^e, Y^e)$ for $e \\in E_{train}$ from multiple past studies, where $\\mathcal{E}_{train} = \\{2010, 2015\\}$ are the years in which the studies were conducted. We assume that the data $(X, Y)$ are generated by an underlying causal model in which not every variable is observed (confounded setting). In this example, we can identify the causal effect of the covariate $X_1$, age, on the cholesterol level since age has a mean shift of 5 years across the studies. Suppose, however, that the distribution of $X_2$, physical activity, remains relatively stable across the studies. The causal effect of $X_2$ on $Y$ is then not identifiable. We now want to train a model that generalizes best on the data $X^{2020}$ collected in $2020$. The age variable shifts again by 5 years; however, the physical activity variable now also shifts a bit (e.g., due to COVID-19), which is a shift we have not observed previously. In this situation, both the causal parameter and the robust predictor are only partially identifiable. \n\n**Assumption on $M_{test}$**: Often, practitioners will have some information on the strength and direction of the distribution shift (for instance, we might know that only the resting pulse will shift across studies, and at most by 20). This knowledge is what we tried to formalize in our assumption on $M_{test}$ (lines 134-137). The parameter gamma corresponds to the maximum strength of the shift, whereas the subspace $M$ corresponds to the expected direction of the shift (if one doesn’t know, one can take $M$ to be the whole covariate space). Equations (3) and (4) bound the second moment of the test distribution shift by $\\gamma \\Pi_{M}$, effectively bounding the mean and variance of the shift, as well as constraining it geometrically to the subspace $M$.", "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:
We express sincere gratitude to all reviewers for their detailed reviews. It is encouraging to hear that the reviewers appreciate the novelty and overall direction of our work, especially its attempt to formalize partially identifiable robustness. 

We also appreciate constructive feedback and  we have carefully addressed and answered all points raised by the reviewers in the revised manuscript. For convenience, we summarize some important points that were mentioned by several reviewers and elaborate on some of them in more detail in the individual rebuttals.

- **Evaluation of the method on real-world data**: In the answer to Reviewer PdW8, we expand the empirical evaluation of our method to real-world single-cell gene expression data [7] – please see the attached PDF for preliminary results.
- **Meaning of “partial identifiability”**: It seemed that there might have been some remaining confusion about the way we use the term “partial identifiability”, also in the context of previous work.  We would like to stress that in this paper, we focus on partial identifiability of the *robust risk* that arises through the non-identifiability of the causal/model parameters. In particular, we distinguish between partial identifiability of the robust risk (not considered in prior work) and partial identifiability of the causal parameter (considered in prior work, e.g. [10]). For example, existing literature [10] often considers cases where, although the model parameters are not fully identifiable, the robust predictor can still be computed. In the language in our paper, we call such a setting fully instead of partially identifiable, since the robust risk and its minimizer can be computed from data, as opposed to our case, where neither the model nor the robust risk can be identified. 
- **Relation to invariance-based literature**: In the answer to Reviewer PdW8, we explain how existing literature (e.g., [14,15]) on the failure of invariance-based methods (such as Invariant Risk Minimization) can be related to lack of identifiability and thus motivates our study. 
- **Real-world examples/motivation**: In the answers to Reviewers iX3g and 2y9v, we describe a motivating toy example based on medical data where the robust predictor is partially identifiable.

Here we add the references for this general response and the rebuttal to Reviewer PdW8:

[1] Wald Y, Feder A, Greenfeld D, Shalit U. On calibration and out-of-domain generalization. Neurips 2021 

[2] Chen Y, Rosenfeld E, Sellke M, Ma T, Risteski A. Iterative feature matching: Toward provable domain generalization with logarithmic environments. Neurips 2022

[3] Veitch V, D'Amour A, Yadlowsky S, Eisenstein J. Counterfactual invariance to spurious correlations in text classification. NeurIPS 2021

[4] Puli AM, Zhang LH, Oermann EK, Ranganath R. Out-of-distribution Generalization in the Presence of Nuisance-Induced Spurious Correlations. In ICLR 2021

[5]: Thams N, Oberst M, Sontag D. Evaluating robustness to dataset shift via parametric robustness sets. NeurIPS. 2022 

[6]: Buchholz S, Rajendran G, Rosenfeld E, Aragam B, Schölkopf B, Ravikumar P. Learning linear causal representations from interventions under general nonlinear mixing. NeurIPS 2023

[7]: Chevalley M, Roohani Y, Mehrjou A, Leskovec J, Schwab P. Causalbench: A large-scale benchmark for network inference from single-cell perturbation data. arXiv preprint 2022

[9]: Schultheiss C, Bühlmann P. Assessing the overall and partial causal well-specification of nonlinear additive noise models. JMLR 2024

[10]: Rothenhäusler D, Meinshausen N, Bühlmann P, Peters J. Anchor regression: Heterogeneous data meet causality. JRSSB. 2021 

[11]: Shen X, Bühlmann P, Taeb A. Causality-oriented robustness: exploiting general additive interventions. arXiv preprint 2023

[12]: Peters J, Bühlmann P, Meinshausen N. Causal inference by using invariant prediction: identification and confidence intervals. JRSSB 2023

[13]: Arjovsky M, Bottou L, Gulrajani I, Lopez-Paz D. Invariant risk minimization. arXiv preprint 2019

[14]: Rosenfeld E, Ravikumar P, Risteski A. The risks of invariant risk minimization. arXiv preprint 2020

[15]: Kamath P, Tangella A, Sutherland D, Srebro N. Does invariant risk minimization capture invariance?. AISTATS 2021.

Meta-review: The paper received positive reviews, with the reviewers appreciating the novelty of the results and the quality of the presentation. Consequently, I recommend acceptance of this paper. When preparing the camera-ready revision, please pay close attention to the reviewers’ feedback and include the additional explanations provided during the rebuttal period.
Decision: Accept (poster)