Spuriosity Didn’t Kill the Classifier: Using Invariant Predictions to Harness Spurious Features
Authors: Cian Eastwood
Shashank Singh
Andrei Liviu Nicolicioiu
Marin Vlastelica
Julius von Kügelgen
Bernhard Schölkopf
Venue: NeurIPS 2023 poster (2023)
Keywords: invariant prediction
spurious correlations
out-of-distribution generalization
domain generalization
domain adaptation
test-time domain adaptation
TL;DR: We show that spurious features can be *safely* harnessed in the test domain *without labels*, using only invariant-feature pseudo-labels, and propose an algorithm for doing so.

Abstract: To avoid failures on out-of-distribution data, recent works have sought to extract features that have an invariant or stable relationship with the label across domains, discarding "spurious" or unstable features whose relationship with the label changes across domains. However, unstable features often carry complementary information that could boost performance if used correctly in the test domain. In this work, we show how this can be done without test-domain labels. In particular, we prove that pseudo-labels based on stable features provide sufficient guidance for doing so, provided that stable and unstable features are conditionally independent given the label. Based on this theoretical insight, we propose Stable Feature Boosting (SFB), an algorithm for: (i) learning a predictor that separates stable and conditionally-independent unstable features; and (ii) using the stable-feature predictions to adapt the unstable-feature predictions in the test domain. Theoretically, we prove that SFB can learn an asymptotically-optimal predictor without test-domain labels. Empirically, we demonstrate the effectiveness of SFB on real and synthetic data.

Spuriosity Didn't Kill the Classifier: Using Invariant Predictions to Harness Spurious Features
Cian Eastwood 112
Shashank Singh
Andrei L. N
Marin Vlastelica'
Julius Küigeggen
Bernhard Schölkopf*
Max Planck Institute for Intelligent Systems, Tübingen
2 University of Edinburgh
UUniverityy of Cambridge
Abstract
To avoid failures -uttof-distribution data, recent works have sought to extract features that have an invariant or stable relationship with the label across domains, discarding "spurious" or unstable features whose relationship with the label changes across domains. However, unstable features often carry complementary information that could boost performance if used correctly in the test domain. In this work, we show how this can be done without gest-domain labels. In particular, we prove that pseudo-labels based on stable features provide sufficient guidance for doing so, provided that stable and unstable features are conditionally independent given the label. Based on this theoretical insight, we propose Stable Feature Boosting (SFB), an algorithm for: (i) learning a predictor that separates stable and conditionally- independent unstable features; and (ii) using the stable-feature predictions to adapt the unstable-
predictions in the test domain. Theoretically, we prove that SFB can learn an asymptoticalll-opiimal predictor without test-domain labels. Empirically, we demonstrate the effectiveness of SFB on real and synthetic data.
Introduction
Machine learning systems can be sensitive distribution shift [26]. Often, this sensitivity due to reliance on "spurious" features whose relationship with the label changes across domains, ultimately leading degraded performance in the test domain of interest [21]. To avoid this pitfall, recent works on domain or out-of- ootf--ddistritttion (OOD) generalization have sought predictors which only make use of features that have a stable or invariant relationship with the label across domains, discarding the spuri- ous or unstable features [45, 1, 35, 15). However, despite their instability, spurious features can often provide additional or complementary information about the target label. Thus, a predictor could be adjusted to use spurious features optimally in the test domain, it would boost performance substantially. That is, perhaps we don't 't need to discard spurious features at but rather use them in the right way.
As a simple but illustrative example, consider the ColorMNIST or CMNIST dataset [1]. This transforms the original MNIST dataset into a binary classification task (digit in 0-4 or 5-9) and then: (i) flips the label with probability 0.25, meaning that, across all 3 domains, digit shape correctly de- termines the label with probability 0.75; and (ii) colorizes the digit such that digit color (red green) is a more informative but spurious feature (see Fig. la). Prior work focused on learning an invariant predictor that uses only shape and avoids using color spurious feature whose relationship with the label changes across domains. However, as shown in Fig. 1b, the invariant predictor is suboptimal test domains where color can be used in a domain-specific manner to improve performance. We thus ask: when and how can such informative but spurious features be safely harnessed without labels?
Equal contribution. Correspondence eastwroodddd ac uk shashankesinggg44@gai..ccm
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

1.00
Xs
Train Domains 0.9
Test -0.9
Accuracy
0.8
0.75
3
3
3
Xu
ERM Invariant
Optimal
X 1L X Y
(Color-Label Correlation)
0.50-
Color-Label Correlation
(b)
(c)
Figure 1: Invariant (stable) and spurious (unstable) features. (a) Illustrative images from CMNIST [1]. (b) CMNIST accuracies (y-axis) over test domains decreasing color-label correlation (x-axis). The 'Oracle' uses both invariant (shape) and spurious (color) features optimally in the test domain, boosting performance over an invariant model (orange region). We show how this can be done without test-domain labels. (c) Generally, invariant models use only the stable component X5 of X, discarding the spurious unstable component Xu- We prove that predictions based on Xş be used safely harness sub-couue caab-commoennt of Xu (dark-orange region).
Our main contribution lies answering this question, showing when and how is possible to safely harness spurious unstable features without test-domain labels. In particular, we prove that predictions based on stable features provide sufficient guidance for doing so, provided that stable and unstable features conditionally independent given the label (see Fig. Ic).
Structure and contributions. The rest of this paper organized as follows. We first discuss related work in $ 2, providing context and high-level motivation for our approach. In $ 3, we then explain how stable and unstable features can be extracted, how unstable features can be harnessed with test-domain labels, and the questions/challlnges that arise when trying to harness unstable features without test-domain labels. In Š 4. we present our main theoretical contributions which provide precise answers to these questions, before using these insights to propose the Stable Feature Boosting (SFB) algorithm 5. In $ 6, we present our experimental results, before ending with a discussion and concluding remarks in 7. Our contributions can be summarized as follows:
Algorithmie: We propose Stable Feature Boosting (SFB), the first algorithm for using invariant predictions to safely harness spurious features without test-domain labels.
SFB is grounded in novel theoretical result (Thm 4.4) giving sufficient conditions for provable test-domain adaptation without labels. Under these conditions, Thm 4.6 shows that, given enough unlabeled data, SFB learns the Bayes-optimal adapted classifier in the test domain.
Theoretical:
Experimental: Our experiments on synthetic and real-world data demonstrate the effectiveness of SFB-ever scenarios where it is unclear if its assumptions are fully satisfied.
2 Related Work
Domain generalization, robustness and invariant prediction. A fundamental starting point for work in domain generalization is the observation that certain "stable" features, often direct causes of the label, may have an invariant relationship with the label across domains [45, 1, 67, 55, 40, 77, 14]. However, such stable or invariant predictors often discard highly informative but unstable information. Rothenhäusler et al. [51] show that we may need to trade off stability and predictiveness, while parameter. The current work is motivated by the idea that one might avoid such a trade-off by changing how unstable features are used test time, rather than discarding them training time.
Eastwood et al. [15] seek such trade-off via an interpretable
babability-oo-ggeerlliii
Test-domain adaptation without labels (unsupervised domain adaptation). In the source-free and test-time domain adaptation literature, it is common adapt new domains using model's own pscudo-labels [20, 36, 39, 71, 30]-see Rusak et al. [52] for a recent review. In contrast, we: (i) use one (stable) model to provide reliable/robust pseudo-labels and another (unstable) model to adapt domain-specifie information; and (ii) propose a bias correction step that provably ensures an accurate, well-calibrated unstable model (Pr ((r)) as well as an optimal joint/combined model (Pr X5, X.r)). Beyond this literature, Bui et al. [12] propose a meta-learning approach for exploiting unstable/domain-speciie in the test domain, which, by definition, is not robust and can degrade performance. Sun et al. [63] share the goal of exploiting unstable features to go "beyond invariance". However, in contrast to our approach, they require labels for the unstable features (rarely available) and only address label shifts.
features. However, they use unstable features in the same way

---

Table 1: Comparison with related work. 'QRM [15] uses a hyperparameter it E [0, balance
probability of robust generalization and using more information from X.
Components of X Used
Method
Stable
Complementary
All
Robust
No test-domain labels
ERM [65]
IRM [1]
QRM [15]
v
DARE [50]
/
ACTIR [31]
/
/
/
SFB (Ours)
Test-domain adaptation with labels (few-shot fine-tuning). Fine-tuning part of model using small number of labeled test-domain examples a common way deal with distribution shift [16, 17. 13]. More recently, it has been shown that simply retraining the last layer of an MeMM-tiiined model outperforms more robust feature-learning methods on spurious correlation benchmarks [50, 32, 74). unstable
Similar to our approach, Jiang and Veitch [31] separate stable and conndtionnally-nddeeeeee features and then adapt their use of the latter the test domain. However, contrast our approach, theirs requires test-domain labels. In addition, they assume data is drawn from anti-causal generative model, which is strictly stronger than our "complementarity" assumption (see $ 4).
Table summarizes related work while App. H discusses further related work.
3 Problem Setup: Extracting and Harnessing Unstable Features
Setup. We consider the problem of domain generalization (DG) [8, 42, 24] where predictors are trained on data from multiple training domains and with the goal of performing well on data from unseen test domains. More formally, we consider datasets D {Xţ;, }= collected from m different training domains or environments Err := {EI,..., Em J. with each dataset De containing data pairs (X5,Y; sampled i.i.d. from PPX Y²). The goal is then to learn predictor f(X) that performs well on a larger set Eall 3 En of possible domains.
Average performance: use all features. The first approaches to DG sought predictors that perform well on average over domains [8. 42] using empirical risk minimization (ERM, [66]). However, predictors that perform well on average provably lack robustness [43, 49], potentially performing quite poorly on large subsets of Eall- In particular, minimizing the average error leads predictors to make use of any features that are informative about the label (on average), including "spurious" or "shortcut" [21] features whose relationship with the label subject change across domains. In test domains where these feature-label relationships change in new or more severe ways than observed during training, this usually leads to significant performance drops or even complete failure [73, 4].
Worst-case or robust performance: use only stable features. To improve robustness, subsequent works sought predictors that only use stable or invariant features, i.c., those that have stable or invariant relationship with the label across domains [45, 1, 47, 70, 58]. For example, Arjovsky al. [1] do so by enforcing that the classifier on top of these features is optimal for all domains simultaneously. We henceforth use stable features and Xş to refer to these features, and stable predictors to refer to predictors which use only these features. Analogously, we use unstable features and Xリ to refer to features with an unstable or "spurious" relationship with the label across domains. Note that Xg and Xu partition the components of X which are informative about Y, as depicted in Fig. 1 and that formal definitions of Xs and Xu are provided in $
3.1 Harnessing unstable features with labels
A stable predictor fs is unlikely to be the best predictor in any given domain. As illustrated in Fig. lb, this is because it excludes unstable features Xu which are informative about Y and can boost per- formance if used in an appropriate, domain-specific manner. Assuming we can indeed learn stable predictor with prior methods, we start by showing how Xu can be harnessed with test-domain labels.
We drop the domain superscript e when referring random variables from any environment.
3

---

Boosting the stable predictor. We describe boosted joint predictions (X) in domain as some combination C of stable predictions fs (x) and domain-specific unstable predictions fü (X), i.e. (X)). (x)). To allow us adapt only the Xu-Y relation, we decompose the stable fx(X) = hs (X)) and unstable (X) ( (Pu(()))))))))) predictions into feature extractors & and classifiers h. &g extracts stable components Xş Φ (X) of X, Φu extracts unstable components Xu (x) of X, hs is a classifier learned on top of Øs (shared across domains), and hy is domain-specijte unstable classifier learned on top of Pu (one per domain). Putting these together, F(X) =
f(() (X),
= ((slss(((x)),,))) M6 (u = Chhs (Xs), M6 (Xu)), (3.1)
where C: [0.1] x [0, + [0. is combination function that combines the stable and unstable predictions. For example. Jiang and Veitch [31, Eq. 2.1] add stable ps and unstable pu predictions in logit space, i.c., C(ps, Pu) = (logit( (ps) + logit( (Pu)). Since it is unclear, priori, how to choose C, we will leave it unspecified until Thm. 4.4 in 4, where we derive a principled choice.
Adapting with labels. Given a new domain e and labels Y", we can boost performance by adapting
hig Specifically, letting& : y y + R be loss function (e.g., cross- cross-entropy) and R R$(f) E (xx,)) f())] e] the risk of predictor f X + y in domain e, can adapt hif to solve:
min R (C Ds a pu)) Ry
(3.2)
3.2 Harnessing unstable features without labels
We now consider the main question of this work- can we reliably hamness Xy without test-domain labels? We could, of course, simply select fixed unstable classifier Mf by relying solely on the training domains (e.g., by minimizing average error), and hope that this works for the test-domain Xu-Y relation. However, by definition of Xy being unstable, this is clearly not robust or reliable approach- -te focus of our efforts in this work, as illustrated in Table 1. As in & 3.1, we assume that we are able to learn a stable predictor fs using prior methods, e.g., IRM [1] QRM [15].
From stable predictions to robust pseudo-labels. While we don't 't have labels in the test domain, we do have stable predictions. By definition, these are imperfect (i.e., noisy) but robust, and can be used to form pseudo-lubels Y; arg max, (X:)); with (fs(X:)); R Pr[Y; j|Xs] denoting the 1th entry of the stable prediction for X,. Can we somehow use these noisy but robust pseudo-labels to guide our updating of bly. and, ultimately, our use of Xu in the test domain?
From joint to unstable-only risk. If we simply use our robust pseudo-labels as if they were truc labels uapatinu kly to minimize the joint risk as in Eq. (3.2) arrive trivial solutions since fs already predicts its own pseudo-labels with 100% accuracy. For example, if we follow [31, Eq. 2.1] and use the combination function C(ps, Pu) = o (logit(p3 (s)) + logit(Pu)). then the trivial solution logit(?(, (-) = 0 achieves 100% accuracy (and minimizes cross-entropy; see Prop. D.1 of App. D). Thus, we cannot minimize a joint loss involving fs's ss predictions when using fs's pseudo-labels. A sensible alternative is to update Hf to minimize the unstable-only risk R (hf @u).
More questions than answers. While this new procedure could work, it raises questions about when it will work, or, more precisely, the conditions under which it can be used to safely harness Xy. We now summarise these questions before addressing them in $ 4:
Does it make sense to minimize the unstable-only risk? In particular, when can we minimize the cettabbl-predicton risk alone or separately, and then arrive at the optimal joint predictor? This cannot always work; e.g., for independent Xs, Xu ~ Bernoulli /2) and Y X5 XOR Xu, Y is independent of each of X5 and Xu and hence cannot be predicted from either alone.
2. How should we combine predictions? Is there principled choice for the combination function in Eq. (3.1)? particular, is there a C that correctly weights stable and unstable predictions in the test domain? As Xu could be very strongly very weakly predictive of Y in the test domain, this seems a difficult task. Intuitively, correctly weighting stable and unstable predictions requires them to be properly calibrated: do we have any reason to believe that, after training on fs's 's pscudo-labels, lf, will be properly calibrated in the test domain?
Can the student outperform the teacher? Stable predictions likely make mistakes-indeed this is the motivation for trying improve them. Is it possible to correct these mistakes with Xu? ? Is it

---

possible to learn an unstable "student" predictor that outperforms its own supervision signal or "teacher"? Perhaps surprisingly, we show that, for certain types of features, the answer is yes. In fact, even very weak stable predictor, with performance just above chance, can be used to learn an optimal unstable classifier in the test domain given enough unlabeled data.
4 Theory: When Can We Safely Harness Unstable Features Without Labels?
Suppose we have already identified a stable feature Xs and a potentially unstable feature Xu (we will return to the question of how to learn/extract X5 and Xu themselves in $ 5). In this section, we analyze the problem of using X5 to leverage Xu in the test domain without labels. We first reduce this to special case of the so-called "marginal problem" in probability theory, i.e., the problem of identifying a joint distribution based on information about its marginals. In the special case where two variables are conditionally independent given third, we show this problem can be solved exactly. This solution, which may be of interest beyond the context of domain generalization/ pataaioonaaaaationnn motivates our test-domain adaptation algorithm (Alg. 1), and forms the basis of Thm. 4.6 which shows that Alg. I converges to the best possible classifier given enough unlabeled data.
We first pose a population-level model of our domain generalization setup. Let E be random variable denoting the environment. Given an environment E. we have that the stable feature Xs. unstable feature X and label Y are distributed according to Y We can now formalize the three key assumptions underlying our approach, starting with the notion of stable feature, motivated in $ 3:
Definition 4.1 (Stable and Unstable Features). Xş is stable feature with respect to Y if Prixs does not depend on E; equivalently, if and E are conditionally independent given Xs (Y IL E] Xs). Conversely, Xu is an unstable feature with respect to Y if Pr|xu depends on E; equivalently, i and E are conditionally dependent given Xu (Y 14 E|Xu).
Next, we state our complementarity assumption, which we will show justifies the approach of separately learning the relationships Xs-Y and Xu-Y and then combining them:
Definition 4.2 (Complementary Features). Xs and Xu are complementary features with respect to Y X5 TT Xul (Y, E); i.e., if Xs and Xu share no redundant information beyond Y and E.
Finally, to provide a useful signal for test-domain adaptation, the stable feature needs to help predict the label in the test domain. Formally, we assume:
Definition 4.3 (Informative Feature). Xg is said to be informative of Y in environment EifXs JA Y|E; Le., X5 is predictive Y within the environment E.
We will discuss the roles of these assumptions after stating our main result (Thm. 4.4) that uses them. To keep our results as general as possible. we avoid assuming a particular causal generative model, but the above conditional (in)dependence assumptions can be interpreted constraints causal model. App. D.2 formally characterizes the set of causal models that are consistent with our assumptions and shows that our setting generalizes those of prior works [49, 68, 31, 69].
such
Reduction to the marginal problem with complementary features. By Defn. 4.1, we have the same stable relationship Py|x,,E= = Pyixx in training and test domains. Now, suppose we have used the training data to learn this stable relationship and thus know Py Xs. Also suppose that we have enough unlabeled data from test domain E to learn Xx and recall that our ultimate goal is to predict Y from (Xs, Xu) in test domain F. Since the rest of our discussion is conditioned on E being the test domain, we omit E from the notation. Now note that, if we could express Xy in terms of Pyix; and Px we could then use Py|x5,Xu to optimally predict Y from (Xs, Xu). Thus, our task thus becomes to reconstruct Py|xs.Xu from Py|xs and Pxs.Xu This is an instance of the classical "marginal problem" from probability theory [28, 29, 19], which asks under which conditions we can recover the joint distribution of set of random variables given information about its marginals. In general, although one can place bounds on the conditional distributions Py!x,, and ' they cannot be completely inferred from Pr|x; and Px,,Xy [19]. However, the following section demonstrates that, under the additional assumptions that X5 and Xu are complementary and Xs informative, we can exactly recover Py(x,, and Xy from Py|x, and Px
5

---

4.1
Solving the marginal problem with complementary features
We now present our main result which shows how to reconstruct Xy from Prixs and Xx when Xs and Xu are complementary and Xş is informative. To simplify notation, we assume the label Y is binary and defer the multi-class extension to App. C.
Theorem 4.4 (Solution to the marginal problem with binary labels and complementary features).
Consider three random variables Xs, Xu. and Y, where (i) Y binary ({0, 1)-valued), (ūi Xs and Xu are complementary features for Y (i.e., X5 _l. Xul Y,, and (ii)) X5 is informative of (Xs M Y). Then, the joint distribution of (Xs, Xu, Y) can be written in terms of the joint distributions of (Xs, Y) and (Xs, Xu)- Specifically, if Y X5 ~ (erroulli(Pr(Y = 1|ss] is a pseudo-label and
60= = Pr[ = O|Y = 0j and 61 == Pr[y = 1|==11
= 1]
(4.1)
are the accuracies of the pseudo-labels on classes 0 and 1, respectively. Then, we have:
ep + 61 > 1,
(4.2)
Pr[Y 1 Xul 6g 1
Pr|Y 1|Xu]
and
(4.3)
60 + 6
Pr[Y = X|x,, Xu] o (logit(Pr(Y== = xsss) +
- logit(Pr(Y=11)) (4.4)
Intuitively, suppose we generate pseudo-labels Ý based on feature X5 and train a model to predict Y using feature Xu. For complementary Xs and Xu. Eq. (4.3) shows how to transform this into prediction of the frue label Y, correcting for differences between Y and Y. Crucially, given the conditional distribution Py|x; and observations of Xs, we can estimate class-wise pseudo-label accuracies Eg and é in Eq. (4.3) even without new labels Y (see App. A.I, Eq. (A.2)). Finally, Eq. (4.4) shows how to weight predictions based on Xs and Xu. justifying the combination function
Cp(ps, Pu) = ((logit(ps) + (Pu) logit(p))
(4.5)
in Eq. (3.1), where p Pr[Y = 1] is constant independent of xs and xu- We now sketch the proof of Thm. 4.4, elucidating the roles of informativeness and complementarity (full proof in App. A.1).
Proof Sketch of Thmn 4.4. We prove Eq. (4.2), Eq. (4.3), and Eq. (4.4) order.
Proof of Eq. (4.2): The informativeness condition (iii) is equivalent to the pseudo- labels having predictive accuracy above random chance; formally, App. A.1 shows:
Lemma 4.5. 6o + E1 if and only if Xg is informative of Y (i.e. Xs 14 Y).
Together with Eq. (4.3), it follows that any dependence between X5 and Y allows us to fully learn the relationship between Xu and Y, affirmatively answering our question from $ 3: Can the student outperform the teacher? While a stronger relationship between Xş and Y is still helpful, it only improves the (unlabeled) sample complexity of learning Py|xa and not consistency (Thm. 4.6 below), mirroring related results in the literature learning from noisy labels [44, 7]. In particular, a weak relationship corresponds to Eo + E1 2 1, increasing the variance of the bias-correction in Eq. (4.3). With bit more work, one can formalize this intuition to show that our approach has a relative statistical efficiency of Eo + E - 1 E [0, 1). compared to using true labels Y.
Proof of Eq. (4.3): The key observation behind the bias-correction (Fq. (4.3)) is that, due to complementarity (Xs TT Y) and the fact that the pseudo-label Y depends only on Xs. y is conditionally independent of Xu given the true label Y (f TLL Xu) formally:
Pr(ý- 1|Xu] pr(Ý- 1 0, Xu) Y 0 Xu]
+ Pr|r = Y = 1, x Pr(Y = 1 [u]
(Law of Total Probability)
= =Pr(ý = Y Pr 0|Xu]
+ Pr = 1 = Pr = 1 X1|
(Complementarity)
+ 11 Pr = = +
Co.
(Definitions of eo and E1)
'Our stochastic pseudo-labels differ from hard (Ý = 1(Pr(Y 1|xs] > 1/2}) pseudo-labels often used in practice [20, 36, 52]. By capturing irreducible eтror in Y. stochastic pseudo-labels ensure is cell-calibrated, allowing combine Pr[Y|Xs] and Pr(Y [x]] in Eq. (4.4).

---

Algorithm 1: Bias-corrected adaptation procedure. Multi-class version given by Algorithm 2.
Input: Calibrated stable classifier fs(xz) = Pr xs]] unlahelled data {(Xs,r Xu,))
Output: Joint classifier f(xs, xu) estimating Pr Y = 1|Xs = xs, Xu = xu]
Compute soft class-1 I count 11 Σ 1= with Y; fs (Xs,)
Compute soft pseudo-labels (PLs) {Y:
Estimate PL accuracies (ε0, = (n-
n- C1 91 fs(Xs;))
E. (ifs(Xsi) // Eq.(4.1)
Fit unstable classifier (xu) to pscudo-labelled data {(Xu, Y)))
11 R Pr[(Y= // (4.3), >r // (q.(4.))((455), Pr|Y=1|Xp = xs. Xu Xyl
Bias-correct fu(xx) + max 0, min {1, fu(xu)+
60téi
return (xxx,xx) (fs (x5), fu(())
Here, complementarity allowed us to approximate the unknown Pr[y = 1 0, Xu] by its average Pr(y- 1|Y 0J = Exy Pr 1|Y 0, Xul]. which depends only the known distribution PxsYY By informativeness, Lemma 4.5 allows us to divide by ED + El 1, giving Eq. (4.3).
Proof of Eq. (4.4): While the exact proof of Eq. (4.4) bit more algebraically involved, the key idea is simply that complementarity allows us to decompose Pr[Y Xs, Xul into separately- estimatable terms Pr[r|Xs) and Pr[Y|Xu]:: for any y E V.
Pr|Y = y|Xs, Xu] Xy Pr Sr Xu = y) Pr = y
(Bayes' Rule)
= Pr|Xs/| Y = y) Pr[Xy] Y = Pr = yl
(Complementarity) (Bayes' Rule)
Pr[Y = y Xs] Pr[Y = Xu
Xy
Pr =
where, X denotes proportionality with a constant depending only on Xş and Xu, not on y. Directly estimating these constants involves estimating the density of intractable without further assumptions. However, in the binary case, since - Pr[Y 1 X| Xu] Pr[Y = 0) Xs, Xu]. these proportionality constants conveniently cancel out when the above relation- ship is written in logit-space, as in Eq. (4.4). In the multi-class case, App. C shows how to use the constraint E Pr = y/ Xs, Xu] = 1 to avoid computing the proportionality constants.
which may be
4.2 A provably consistent algorithm for unsupervised test-domain adaptation
Having learned Py|xs from the training domain(s), Thm. 4.4 implies we can learn PyiXs.Xy in the test domain by learning Xx latter only requiring unlabeled test-domain data. This motivates our Alg. I for test-domain adaptation, which is a finite-sample version of the bias-correction and combination equations (Eqs. (4.3) and (4.4)) in Thm. 4.4. Alg, I comes with the following guarantee:
Theorem 4.6 (Consistency Guarantee, Informal), Assume (i) Xs stable, (ii) Xs and Xu are complementury, and (ii) Xs is informative of in the test domain. As n -> co, if fu - Pr(y
1 1|] then f - Pr(y = 1|Xs,Xul
In words, the amount of unlabeled data from the test domain increases, if the unstable classifier on Line 4 of Alg. learns to predict the pseudo-label Y, then the joint classifier output by Alg. 1 learns to predict the true label Y. Convergence in Thm. 4.6 occurs Xy.e both weakly (in prob.) and strongly (a.s.), depending on the convergence of fu. Formal statements and proofs are in Appendix B.
Algorithm: Stable Feature Boosting (SFB)
Using theoretical insights from $ 4, we now propose Stable Feature Boosting (SFB): an algorithm for safely harnessing unstable features without test-domain labels. We first describe learning stable predictor and extracting complementary unstable features from the training domains. We then describe how to use these with Alg. 1, adapting our use of the unstable features to the test domain.
7

---

Training domains: Learning stable and complementary features. Using the notation of Eq. (3.1), our goal on the training domains is to learn stable and unstable features Dg and Pu. stable predictor fs, and domain-specific unstable predictors fü such that:
1. fs is stable, informative, and calibrated (i.e., fx(x))
2. In domain fu boosts fs 's performance with complementary 4D (X') TT & (X
To achieve these learning goals, we propose the following objective:
min Ri EFE
Σ Rs (hs 2s) + R (C &s hij &u))
(5.1)
As Pstability (D,, R³) + Ac PeondIndep (xs(X"), Pu (X*), Y*)
The first term encourages good stable predictions fs ht 4p (X)) while the second encourages hi (Qu((')) via domain- specific use Hft of the unstable features uu (X*). For binary Y, the combination function C takes the simplified form of Eq. (4.5). Otherwise, takes the more general form of Eq. (C.1). Psuabliity is penalty encouraging stability while Cooddlndep is penalty encouraging complementarity or conditional independence, i.e., (x²) TT &s (X Several approaches exist for enforcing stability [1, 35, 58, 47, 15, 67, 40, 77] (e.g.. IRM [1]) and conditional independence (e.g., conditional HSIC [22]). Às [0, 60) and Ac E [0, 00) are regularization hyperparameters. While another hyperparameter y E 10, 1] could control the relative weighting of stable and joint risks, i.e., y (hs ④3)) and (1 - 7) R (C s hi2 ou)), we found this unnecessary in practice. Finally, note that, in principle, Hy could take any form and we could learn completely separate Ds, Pu. In practice, we simply take Hfy to be a linear classifier and split the output of shared (X) (X)) (X))
improved domain-specific joint predictions f (xx)) (
Post-hoc calibration. As noted in $ 4.2, the stable predictor fs must be properly calibrated to (i) form unbiased unstable predictions (Line 5 of Alg. 1) and (ii) correctly combine the stable and unstable predictions (Line 6 of Alg. 1). Thus, after optimizing the objective (5.1), we apply a post pess-processing step (e.g., temperature scaling [25]) to calibrate fs.
Test-domain adaptation without labels. Given a stable predictor fs = ht o Dg and complementary features T
now adapt the unstable classifier ify in the test domain to safely harness (or make optimal use of) (X). To do so, use the bias-corrected adaptation algorithm of Alg. 1 (or Alg. 2 for the multi-class case) which takes input the stable classifier hş and unlabelled test-domain data (x,),, P(r()) ""r outputting a joint classifier adapted to the test domain.
6 Experiments
We now evaluate the performance of our algorithm on synthetic and real-world datasets requiring out- of-distribution generalization. App. E contains full details these datasets and depiction of their samples (see Fig. 4). In the experiments below, SFB uses IRM [1] for Piumbility and the conditional- independence proxy of Jiang and Veitch [31, $3.1] for PCondIndep- with App. F.1.2 giving results with other stability penalties. App. F contains further results, including ablation studies (F.1.1) and results on additional datasets (F22). In particular, App. F.2 contains results on the Camelyon17 medical dataset [3] from the WILDS package [33], where we find that all methods perform similarly when properly tuned (see discussion App. F.2). Code available at: https://github. com/cianeastwood/stb
Synthetic data. We consider two synthetic datasets: anti-causal (AC) data and cause-effect data with direct Xs-Xu dependence (CE-DD). AC data satisfies the structural equations
Y +- (0.5);
Y
Be
X5 +- Y Rad (0.75);
Xu +- Y Rad(
Xs
X
where the input X (Xs, Xu) and Rad(B) denotes Rademacher random variable that
*Note: while Sections 3 and 5 use J for the classifier and f = h & for the classifier representation composition, Section 4 and Alg. use f for the classifier, since representation @ is being learned.
8

---

Table 2: Synthetic & PACS test-domain accuracies over 100 & 5 seeds cach.
Table 3: CMNIST test ac-
Synthetic
PACS
curacies over 10 seeds.
Algorithm
AC
CE-DD
Algorithm
Test Acc.
ERM
9.1+
11.6 0.7
93.0 + 0.7
79.3 + 0.5
74.3 + 0.7
65.4 1.5
ERM
27.9 1 1,5
ERM + PL
9.9
0.7
9..7
79.6
74.1 = 1.2
63.1 3.1
IRM [1]
69.7 0.9
IRM [1]
4..9
6.
9.3
7..7
754 1.5
65.6
2.5
SFB adpt.
70.6
RR PL.
0.
6.
+..1
78.9
75.1
= 4.6
62.9
4.9
SFB
88.1 +
ACTIR [31]
7.
23.5
94,8
8.
76.6
62.1 1.3
adpt.
74.7
+..
93.7
0.6
78.1+
0.6
69.7
Oracle adpt.
72.1 1: 0.7
SFB
88.6 2.9
95.8 = 0.6
80. 1.3
76.6 0.6
718
Oracie
89.9 1 0.1
0.90
SFBSBB
SFB Rn, CA,
0.85
PL
-+-ERM
SFB Rn,CA
+SBB adpt
Accuracy
0.80
SFB
+BBBB
0.70
0.65
0.9
Color-Label Correlation
Color-Label Correlation
Figure 2: CMNIST accuracies (y-axis) over test domains of decreasing color-label correlation (x-axis). Empirical versions of Fig. lb. Left: SFB baseline methods. Right: Ablations showing SFB without (w/o) bias correc- tion (BC), calibration (CA) and multiple pscudo-labeling rounds (Rn). Numerical results in Table of App. F.1.3.
is 1 with probability 1 - B and +1 with probability B. Following [31, $6.1]. we create two training domains with Be E {0.95, 0.7), one validation domain with B. = 0.6 and one test domain with B.- 0.1. CE-DD data is generated according to the structural equations
Xs + Bern (0.5);
Y + XOR Xs, B0m(0)))));;
Xu + XOR(XXR(Y, (fe)), Xs),
Xs
Xu
where Bern(B) denotes Bernoulli random variable that is 1 with probability B and 0 with probability 1 1- 1-8. B. Note that Xş JA. XulY, since Xş directly influences Xy. Following [31, App. B], we create two training domains with Be E {0.95,0.8
one validation domain with fe = 0.2, and one test domain with P. = 0.1. For both datasets, the idea is that, during training, prediction based on the stable Xs results in lower accuracy (75%) than prediction based the unstable Xu- Thus, models optimizing for prediction accuracy only-and not stability- will use Xu and ultimately end up with only 10% in the test domain. Importantly, while the stable predictor achieves 75% accuracy in the test domain, this can be improved to 90% if Xu is used correctly. Following [31], we use simple 3-layer network for both datasets and choose hyperparameters using the validation-domain performance: see App. G.2 for further implementation details.
On the AC dataset, Table 2 shows that ERM performs poorly as it misuses Xy, while IRM, ACTIR, and SFB-no-adpt. do well by using only Xs. Critically, only SFB (with adaptation) is able to harness Xu in the test domain without labels, leading to near-optimal performance boost.
On the CE-DD dataset, Table again shows that ERM performs poorly while IRM and SFB-no-adpt. do well by using only the stable Xs. However, we now see that ACTIR performs poorly since its assumption of anti-causal structure no longer holds. This highlights another key advantage of SFB over ACTIR: any stability penalty can be used, including those with weaker assumptions than ACTIR's anti-causal structure (e.g.. IRM). Perhaps more surprisingly, SFB (with adaptation) performs well despite the complementarity assumption X5 IL Xul Y being violated. One explanation for this that complementarity is only weakly violated the test domain. Another is that complementarity not necessary for SFB, with some weaker, testtto--beeeeeee we provide a more detailed explanation and discussion of this observation.
condition(s) sufficing. In App. I,
COIOT We now consider the Col orMNIST dataset [1], described in $ and Fig. 1a. We follow the experimental setup Eastwood al. [15, $6.1 see App. G.3 for details. Table shows that: (i) SFB learns a stable predictor ("no adpt.") with performance comparable to other stable/invariant

---

methods like IRM [1]; and (ii) only SFB (with adaptation) is capable of harnessing the spurious color feature in the test domain without labels, leading to a near-optimal boost in performance. Note that "Oracle no adpt." refers to an ERM model trained on grayscale images, while "Oracle" refers to an ERM model trained on labeled test-domain data. Table 6 of App. F.1.3 compares to additional baseline methods, including V-REx [35], EQRM [15]. Fishr [48] and more. Fig. 2 gives more insight by showing performance across test domains of varying color-label correlation. On the left, we see that SFB outperforms ERM and IRM, as well as additional adaptive baseline methods in IRM+ + pseudo-labeling (PL. (36]) and IRM + T3A [30] (see App. G.I for details). On the right, ablations show that: (i) bias (BC), post-hoc calibration (CA), and multiple rounds of ascudo-labeling (Rn) improve adaptation performance; and (ii) without labels, SFB harnesses the spurious color feature near-optimally in test domains of varying color-label correlation the original goal we set out to achieve in Fig. lb. Further results and ablations are provided in App. F.I.
PACS. Table 2 shows that SFB's s stable ("no adpt.") performance is comparable to that of the other stable/invariant methods (IRM, ACTIR). One exception is the sketch domain (S>-the most severe shift based on performance drop where SFB's ' stable predictor performs best. Another is domains and C, where ACTIR performs better than SFB's s stable predictor. Most notable, however, is: (i) the consistent performance boost that SFB gets from unsupervised adaptation; and (ii) SFB performing best or joint-best best on 3 of the 4 domains. These results suggest SFB can be useful on real-world datasets where it is unclear if complementarity holds. In App. I, we discuss why this may be the case.
7 Conclusion & Future Work
This work demonstrated, both theoretically and practically, how to adapt our usage of spurious features to new test domains using only a stable, complementary training signal. By using invariant predictions to safely harness complementary spurious features, our proposed Stable Feature Boosting algorithm can provide significant performance gains compared to only using invariant/stable features or using unadapted spurious features-withe without requiring any true labels in the test domain.
Stable and calibrated predictors. Perhaps the greatest challenge in applying SFB in practice is the need for a stable and calibrated predictor. While stable features may be directly observable in some cases (e.g.. using prior knowledge of causal relationships between the domain, features, and label, as in Prop. D.2), they often need to be extracted from high-dimensional observations (e.g.. images). Several methods for faate-featuree extraction have recently been proposed [1, 35, 58, 70, 15], with future improvements likely to benefit SFB. Calibrating complex predictors like deep neural networks also an active area of research [18, 25, 72, 59], with future improvements likely to benefit SFB.
Weakening the complementarity condition. SFB also assumes that stable and unstable features are complementarity, i.e., conditionally independent given the label. This assumption is implicit in the causal generative models assumed by prior work [49, 68, 31], and future work may look to weaken it. However, our experimental results suggest that SFB may be robust to violations of complementarity in practice: on our synthetic data where complementarity does not hold (CE-DD) and real data where we have reason to believe it holds (PACS), SFB still outperformed baseline methods. We discuss potential reasons for this in App. and hope that future work can identify weaker sufficient conditions.
Exploiting aviil-avallable test-domain features without labels. While focused on domain generalization (DG) and the goal of leariing how to use the same spurious features (c.g.. color) in new way, our solution to the "marginal problem" in 4.1 can be used to exploit completely new set of (complementary) features in the test domain that weren't available in the training domains. For example, given a stable predictor of diabetes based on causal features (e.g., age, genetics), SFB could exploit new unlabeled data containing previously-unse unseen effect features (e.g., glucose levels). We hope future work can explore such uses of SFB.
Acknowledgments and Disclosure of Funding
The authors thank Chris Williams and Ian Mason for providing feedback on an earlier draft, as well as the MPI Tübingen causality group for helpful discussions and comments. This work was supported by the Tübingen AI Center (FKZ: 01 18039B) and by the Deutsche Forschungsgemeinschatf (DFG, German Research Foundation) under Germany's 's Excellence Strategy EEXC number 2064/1 - Project number 390727645. The authors declare no competing interests.
10

---

References
[1] Arjovsky, M., Bottou, L., Gulrajani, L,, and Lopez-Paz, D. (2020). Invariant risk minimization. (XXi:1907.00292 [Cited on pages 1, 3, 4, 8, 9, 10, 26, 27, 29, and 31.]
[2] Ba, J. and Caruana, R. (2014). Do deep nets really need to be deep? Advances in Neural Information Processing Systems, 27. [Cited on page 19.]
[3] Bandi, P., Geessink, O., Manson, Q. Van Dijk, M., Balkenhol, M., Hermsen, M., Bejnordi, B. E., Lee, B., Paeng, K., Zhong, A., et al. (2018). From detection of individual metastases to classification of lymph node status at the patient level: the camelyon17 challenge. IEEE
Transactions on Medical Imaging. 38(2):550 560. [Cited pages 8, 27, 28, and 29.]
[4] Beery, S., Van Hom, G., and Perona, P. (2018). Recognition in terra incognita. In Proceedings of the European Conference on Computer Vision, pages 456 473. [Cited on page 3.]
[5] Ben-David, S., Blitzer, J., Crammer, K., Kulesza, A., Pereira, F., and Vaughan, J. W. (2010). A theory of learning from different domains. Machine Learning, 79(1):151-175. [Cited page 32.]
[6] Bickel, S., Brückner, M., and Scheffer, T. (2009). Discriminative learning under covariate shift. Journal of Machine Learning Research, 10(9). [Cited on page 26.]
[7] Blanchard, G., Flaska, M., Handy, G., Pozzi, S., and Scott, C. (2016). Classification with asymmetric label noise: Consistency and maximal denoising. Electronic Journal of Statistics, 10:2780-2824, [Cited on pages 6, 19, and 32.]
[8] Blanchard, G., Lee, G., and Scott, C. (2011), Generalizing from several related classification tasks unlabeled sample. In Advances in Neural Information Processing Systems, volume 24. [Cited on page 3.]
[9] Blitzer, J., Crammer, K., Kulesza, A., Pereira, F., and Wortman, J. (2007). Learning bounds for domain adaptation. Advances in Neural Information Processing Systems, 20. [Cited on page 32.]
[10] Blum, A. and Mitchell, T. (1998). Combining labeled and unlabeled data with co-training. In Proceedings of the eleventh annual conference on Computational learning theory, pages 92-100. [Cited on page 32.]
[1]] Buciluă, C., Caruana, and Niculescu-Mizil, A. (2006). Model compression. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages
[Cited on page 19.]
[12] Bui, M.-H., Tran, T., Tran, A., and Phung, D. (2021). Exploiting domain features to enhance domain generalization. In Advances in Neural Information Processing Systems, volume 34. [Cited on page 2.]
[13] Eastwood, C., Mason, I., and Williams, C. (2021). Unit-level surprise in neural networks. In I (Still) Can't 't Believe It's Not Better! NeurIPS 202/ Workshop. [Cited on page 3.]
[14] Eastwood, C., Mason, I., Williams, C., and Schölkopf, B. (2022a). Source-free adaptation to measurement shift via bottom-up feature restoration. In International Conference on Learning Representations. [Cited on page 2.]
[15] Eastwood, C., Robey, A., Singh, S., von Kügelgen, J., Hassani, H., Pappas, G. J., and Schölkopf, (2022b). Probable domain generalization quantile risk minimization. Advances Neural Information Processing Systems. [Cited on pages 1, 3, 4, 8, 9, 10, 29, and 31.]
[16] Fei-Fei, L., Fergus, R., and Perona, P. (2006). One-shot learning of object categories. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(4):594-61. [Cited on page 3.]
[17] Finn, C., Abbeel, P., and Levine, (2017). Model-agnostic meta-learning for fast adaptation of deep networks. In International Conference Machine Learning, pages 1126-1135 [Cited on page 3.]
[18] Flach, P. (2016). Classifier calibration. In Encyclopedia of machine learning and data mining. Springer US. [Cited on page 10.]

---

[19] Fréchet, M. (1951). Sur les tableaux de corrélation dont les marges sont données. Ann. Univ. Lyon, 3" serie, Sciences, Sect. A. 14:53-77. [Cited on page 5.]
[20] Galstyan, A. and Cohen, P. R. (2008). Empirical comparison of "hard" and "soft" label propagation for relational classification. In Inductive Logic Programming: 17th International Conference, II. 2007, Corvallis, OR, USA, June 19-21, 2007, Revised Selected Papers 17, pages 98-111. Springer. [Cited on pages 2 and 6.]
[21] Geirhos, R., Jacobsen, J.-H., Michaelis, C., Zemel, R., Brendel, W., Bethge, M., and Wichmann, F. A. (2020). Shortcut learning deep neural networks. Nature Machine Intelligence, 2:665-673. [Cited on pages 1 and 3.]
[22] Gretton, A., Bousquet, O., Smola, A., and Schölkopf, B. (2005). Measuring statistical de- pendence with Hilbert-Schmidt norms. In Algorithmic Learning Theory: 16th International Conference, ALT 2005, Singapore, October 8-11, 2005. Proceedings 16, pages 63-77. Springer. [Cited on page 8.]
[23] Gretton, A., Smola, A., Huang, J., Schmittfull, M., Borgwardt, K., and Schölkopf. B. (2009). Covariate shift by kernel mean matching. Dataset shift in machine learning, 3(4):5. [Cited on page 26.]
[24] Gulrajani, I. and Lopez-Paz, D. (2020). In search of lost domain generalization. arXiv preprint :xXiv20077001444 [Cited on pages 3, 27, 30, and 31.]
[25] Guo, C., Pleiss, G., Sun, Y., and Weinberger, K. Q. (2017). On calibration of modern neural networks, In International Conference on Machine Learning, pages 1321-1330. [Cited on pages 10, 28, 31, and 32.]
[26] Hendrycks, and Dietterich, T. (2019). Benchmarking neural network robustness to common corruptions and perturbations. In International Conference on Learning Representations. [Cited on page I.]
[27] Hinton, G., Vinyals, O., and Dean, J. (2015). Distilling the knowledge in neural network. arXiv preprint arXiv:1503.02555 025331. [Cited on page 19.]
[28] Hoeffding, W. (1940). Masstabinvariante korrelationstheorie. Schriften des Mathematischen Instituts und Instituts fur Angewandte Mathematik der Universitat Berlin, 5:181-233. [Cited on page 5.]
[29] Hoeffding, W. (1941). Masstabinvariante korrelationsmaass für diskontinuierliche verteilungen. Archiv für mathematische Wirtschafts-und Sozialforschung, 7:49-70. [Cited on page 5.]
[30] Iwasawa, Y. and Matsuo, (2021). Test-time classifier adjustment module for aggnoscc domain generalization. In Advances in Neural Information Processing Systems. [Cited on pages 2, 10, 30, and 31.]
[31] Jiang, Y. and Veitch, V. (2022). Invariant and transportable representations for anti-causal domain shifts. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K., editors, Advances Neural Information Processing Systems. [Cited on pages 3, 4,4, 5, 8, 9, 10, 25, 26, 27, 30, 31, and 32.]
[32] Kirichenko, P., Izmailov, P., and Wilson, A. G. (2022). Last layer re- trainini is sufficient for robustness to spurious correlations. In Advances in Neural Information Processing Systems. [Cited on page 3.]
[33] Koh, P. W.. Sagawa, S., Marklund, H., Xie, S. M., Zhang, M.. Balsubramani, A., Hu, W., Yasunaga, M., Phillips, R. L., Gao, I., Lee, T., David, E., Stavness, I., Guo, W., Earnshaw, B. A., Haque, I. S., Beery, S., Leskovee, J., Kundaje, A., Pierson, E.,, Levine, S., Finn, C., and Liang, P. (2021). WILDSS A benchmark of in-the tiie distribution shifts. International Conference on Machine Learning. [Cited on pages 8, 27, and 32.]
[34] Krogel, M.-A. and Scheffer, (2004). Multi-relational learning, text mining, and semi- supervised learning for functional genomics. Machine Learning, 57:61-81. [Cited on page 32.]
12

---

[35] Krueger, D., Caballero, E., Jacobsen, J.-H., Zhang, A., Binas, J., Zhang, D.. Priol, R. L.. and Courville, A. (2021). Out-of -istr---iitiitttinn generalization via risk extrapolation (REx). In International Conference on Machine Learning, volume 139, pages 5815-5826. [Cited on pages 1, 8, 10, 29, and 31.]
[36] Lee, D.-H. et al. (2013). Pseudo-label:
The simple and efficient semi-supervised learning method for deep neural networks. Workshop on Challenges in Representation Learning, ICMI,, volume 3. [Cited on pages 2, 6, 10, and 30.]
[37] Li, D., Yang, Y., Song, Y.-Z., and Hospedales, T. M. (2017a). Deeper, broader and artier domain generalization. In Proceedings of the IEEE International Conference on Computer Vision (ICCV). [Cited on page 27.]
[38] Li, Y., Yang, J., Song, Y. Cao, L.., Luo, J., and L.-J. (2017b). Learning from noisy labels with distillation. In Proceedings of the IEEE international conference on computer vision, pages 1910-1918. [Cited on page 32.]
[39] Liang, J., Hu, D., and Feng, J. (2020). Do we really need to access the source data? Source hypothesis transfer for unsupervised domain adaptation. In International Conference on Machine Learning (ICML), pages 6028-6039. [Cited on page 2.]
[40] Makar, M., Packer, B., Moldovan, D., Blalock, D., Halpern, Y., and D' Amour, A. (2022).
Causally motivated shortcut removal using auxiliary labels. In International Conference on Artificial Intelligence and Statistics, pages 739-766. PMLR. [Cited on pages 2, 8, and 29.]
[41] Mansour, Y., Mohri, M., and Rostamizadeh, A. (2008). Domain adaptation with multiple sources. Advances in neural information processing systems, 21. [Cited on page 32.]
[42] Muandet, K., Balduzzi, D., and Schölkopf, B. (2013). Domain generalization via invariant feature representation. In International Conference on Machine Learning, pages 10-18. [Cited on page 3.J
[43] Nagarajan, V., Andreassen, A., and Neyshabur, B. (2021). Understanding the failure modes out-of-distribution generalization. International Conference on Learning Representations. [Cited on page 3.]
[44] Natarajan, N., Dhillon, S., Ravikumar, P. K., and Tewari, A. (2013). Learning with noisy labels. Advances in neural information processing systems, 26. [Cited on pages 6, 19, and 32.]
[45] Peters, J., Bühlmann, P., and Meinshausen, N. (2016). Causal inference by using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Society, Series B (Statisticul Methodology), pages 947-1012. [Cited on pages 2, and 3.]
[46] Pezeshki, M., Kaba, O., Bengio, Y., Courville, A. C.,, Precup, D., and Lajoie, G. (2021). Gradient starvation: A learning proclivity neural networks. Advances Neural Information Processing Systems, 12:111262222 [Cited on page 29.]
[47] Puli, A. M., Zhang, H., Oermann, E. K., and Ranganath, R. (2022). fut-of-distribution gen- eralization in the presence of nuisance-induced spurious correlations. In International Conference on Learning Representations. [Cited on pages 3, 8, and 29.]
[48] Rame, A., Dancette, C., and Cord, M. (2022). Fishr: Invariant gradient variances for out-of- distribution generalization. In International Conference on Machine Leurning, pages 18347-18377. [Cited on pages 10 and 29.]
[49]
M., Schölkopf, B., Turner, R., and Peters, (2018). Invariant models for causal [Cited on pages 3,
transfer learning. The Journal of Machine Learning Research, 5. 10, 25, and 26.]
[50] Rosenfeld, E.,, Ravikumar, P., and Risteski, A. (2022). Domain-adjusted regression or: ERM may already learn features sufficient for out-of-distribution generalization. arXiv preprint 202.0020...68856. [Cited on page 3.]
13

---

[51] Rothenhäusler, D., Meinshausen, N., Bühlmann, P., and Peters, J. (2021). Anchor regression: Heterogeneous data meet causality. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 83(2):215-244 [Cited on page 2.]
[52] Rusak, E., Schneider, S., Pachitariu, G., Eck, L., Gehler, P. V., Bringmann, O., Brendel, W., and Bethge, M. (2022). your data distribution shifts, use self-leaming. Transactions on Machine Learning Research. [Cited on pages 2 and 6.]
[53] Sagawa, S., Koh, P. W., Hashimoto, T. B., and Liang, P. (2019). Distributionally robust neural networks. In International Conference on Learning Representations. [Cited on page 29.]
[54] Schapire, R. E. (1990). The strength of weak learnability. Machine Learning, 5:197-227. (Cited on page 32.]
[55] Schölkopf, B. (2022). Causality for machine learning. In Probabilistic and Causal Inference: The Works of Judea Pearl, pages 765-804. Association for Computing Machinery. [Cited on pages 2 and 26.]
[56] Scott, C., Blanchard, G., and Handy, G. (2013). Classification with asymmetric label noise: Consistency and maximal denoising. In Conference on learning theory, pages 489-511. PMLR. [Cited on page 32.]
[57] Shi, Y., Scely, J., Torr, P., N. S., Hanmun, A., Usunier, N., and Synnaeve, G. (2022a). Gradient matching for domain generalization. In International Conference on Learning Representations. [Cited on page 29.]
[58] Shi, Y., Seely, J., Torr, P., Siddharth, N., Hannun, A., Usunier, N., and Synnaeve, G. (2022b). Gradient matching for domain generalization. In International Conference on Learning Represen- tations. [Cited on pages 3, 8, 10, and 29.]
[59] Silva Filho, T., Song, H., Perello-Nieto, M., Santos-Rodriguez, R., Kull, M., and Flach, P. (2023). Classifier calibration: survey how assess and improve predicted class probabilities. Machine Learning, pages 1-50. [Cited on page 10.]
[60] Song, H., Kim, M., Park, D., Shin, Y., and Lee, J.-G. (2022). Learning from noisy labels with deep neural networks: A survey. IEEE Transactions on Neural Networks and Learning Systems.
[Cited on page 32.]
[61] Sugiyama, M. and Kawanabe, M. (2012). Machine learning in non-stationary environments: Introduction to covariate shift adaptation. MIT press. [Cited on page 26.]
[62] Sugiyama, M., Krauledat, M., and Müller, K.-R. (2007). Covariate shift adaptation by im- portance weighted cross validation. Journal of Machine Learning Research, 8(5). [Cited on page 26.]
[63] Sun, Q. Murphy, K., Ebrahimi, S., and D' Amour, A. (2022). Beyond invariance: Test-time label- shift adaptation for distributions with" spurious" correlations. arXiv preprint arXiv:2211.15666. [Cited on page 2.]
[64] Tanaka, D., Ikami, D., Yamasaki, T., and Aizawa, K. (2018). Joint optimization framework for learning with noisy labels. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5552-5560. [Cited on page 32.]
[65] Vapnik, V. (1991). Principles of risk minimization for learning theory. Advances in Neural Information Processing Systems, 4. [Cited on pages 3 and 26.]
[66] Vapnik, V. N. (1998). Statistical Learning Theory. Wiley, New York, NY. [Cited on page 3.]
[67] Veitch, V., D' Amour, A., Yadlowsky, S., and Eisenstein, J. (2021). Counterfactual invariance to spurious correlations: Why and how to pass stress tests. In Advances in Neural Information Processing Systems. [Cited on pages 2, 8, and 29.]
[68] von Kügelgen, J., Mey, A., and Loog, M. (2019). Semi-generative modelling: Covariate-shift adaptation with cause and effect features. In The 22nd International Conference on Artificial Intelligence and Statisties, pages 1361-1369. PMLR. [Cited pages 5, 10, 25, and 26.]
14

---

[69] von Kügelgen, J., Mey, A., Loog, M., and Schölkopf, B. (2020). Semi-supervised learning, causality, and the conditional cluster assumption. In Conference on Uncertainty in Artificial Intelligence, pages 1-10. PMLR. [Cited on pages 5 and 26.]
[70] Wald, Y., Feder, A., Greenfeld, D., and Shalit, U. (2021). On calibration and out-of-domain generalization. Advances in neural information processing systems, 34:2215-2227 [Cited on pages 3, 10, and 29.]
[71] Wang, D., Shelhamer, E.,, Liu, S., Olshausen, B., and Darrell, T. (2021a). Tent: Fully test-time adaptation by entropy minimization. In International Conference on Learning Representations. [Cited page 2.]
[72] Wang, D.-B., Feng, L., and Zhang, M.-L. (2021b). Rethinking calibration of deep neural networks: Do not be afraid of overconfidence. Advances in Neural Information Processing Systems, 34:1 110--18800. [Cited on page 10.]
[73] Zech, R., Badgeley, M. A., Liu, M., Costa, B., Titano, J., and Oermann, E. K. (2018). Variable generalization performance of deep learning model detect pneumonia in chest radiographs: a cross-sectional study, PLoS Medicine, 15(11). [Cited on page 3.]
[74] Zhang. J., Lopez-Paz, D., and Bottou, L. (2022). Rich feature construction for the optimization- generalization dilemma. In International Conference Machine Learning. [Cited on pages and 31.]
[75] Zhao, H., Des Combes, R. T., Zhang, K., and Gordon, G. (2019). On learning invariant representations for domain adaptation. In International Conference on Machine Learning, pages 7523-7532. PMLR. [Cited on page 32.]
[76] Zhao, H., Zhang, S., Wu, G., Moura, J. M., Costeira, J. P., and Gordon, G. (2018). Adversarial multiple source domain adaptation. Advances in Neural Information Processing Systems, 31. [Cited on page 32.]
[77] Zheng, J. and Makar, M. (2022). Causally motivated multi-shorteut identification & removal. Advances in Neural Information Processing Systems. [Cited on pages 2, 8, and 29.]
15

---

Appendices
Table of Contents
A Proof and Further Discussion of Theorem 4,4
17
A.1 Proof of Theorem 4.4
17
A.2 Further discussion of Theorem 4.4
19
B Proof Theorem 4.6
C Multiclass Case
22
D Supplementary Results
24
D.1 Trivial solution to joint-risk minimization
24
D.2 Causal perspectives
25
E Datasets
F Further Experiments
27
F.I ColorMNIST
28
F2
Camelyon17
29
G Implementation Details
30
G.1 Adaptive baselines
30
................................
Synthetic
31
G.3 ColorMNIST experiments
................................
31
G.4 PACS experiments
31
G.5 Camelyon17 experiments
32
H Further Related Work
32
Performance When Complementarity is Violated
33
16

---

A Proof and Further Discussion of Theorem 4.4
A.1 Proof of Theorem 4.4
In this section, we prove our main results regarding the marginal generalization problem presented in Section 4, namely Thm. 4.4. For the reader's convenience, we restate Thm. 4.4 here:
Theorem 4.4 (Marginal generalization with for binary labels and complementary features). Consider three random variables Xs. Xu, and Y, where
1. Y is binary ((0, 1 )-alued)), Xs and Xu are complementary features Y (i.e, Xs IL XulY), Y), and 3. Xş is informative of Y (Xg 14 Y).
Then, the joint distribution of (Xs, Xu, Y) can written in terms of the joint distributions of (Xs, Y) and (Xs, Xu). Specifically, if Y BernoulliPPr(Y =1|Xs]) is pseudo-label and
En co: Pr|y O|Y 0] and : Pr|y 1|Y =1]
(A.1)
are the conditional probabilities that Y and Y agree, given Y = 0 and Y = 1, respectively, then,
60 +1 1,
Pr[Y = x Pr 1| + and
Co + 6 - 3. Pr(Y X,,, Xu] = (logit(Pr(Y- 1|Xs]) logit(Pr( 1|xu]) - logit(Pr/Y = 1))).
Before proving Thm. 4.4, we provide some examples demonstrating that the complementarity and informativeness assumptions Thm. 4.4 cannot be dropped.
Example A.1. Suppose Xs and Xu have independent Bernoull((1/2) distributions. Then, Xg is informative of both of the binary variables Y1 = Xu and Y2 = Xs Xu) and both have identical conditional distributions given Xs. but Yı and Y2 have different conditional distributions given Xu:
Pr[Yi 1|X = 0] 0 1/2 Pr[Y2 X =0].
Thus, the complementarity condition cannot be omitted.
On the other hand, Xş and Xu are complementary for both Y/3 Xu and an independent Y4 Bernoulli(122) and both Y3 and Y, both have identical conditional distributions given X5, but Y1 and Y2 have different conditional distributions given Xu:
Pr|Yg- X 1] = 1/2 + 1 = Pr(Y4 = 1|xu 1].
Thus, the informativeness condition cannot be omitted.
Before proving Thm. 4.4, we prove Lemma 4.5, which allows us safely divide by the quantity Co + 6; - 1 in the formula for Pr|Y = 1|Xu], under the condition that Xş is informative of Y.
Lemma 4.5. In the setting of Thm. 4.4, let en and e₁ be the class-wise pseudo-label accuracies defined in in Eq. (A.1). Then, co c1 1 and only if Xs and Y are independent.
Note that the entire result also holds, with almost identical proof, in the multi-enviirnment setting of Sections 3 and 5, conditioned on a particular environment E.
Proof. We first prove the forward implication. Suppose Eg + E = 1. Pr = E {0,1), then Xs and Y are trivially independent, so we may assume Pr(Y 1] E (0,1). Then,
| = e Pr = 1] (1- Pr(Y = 1))
(Law of Total Expectation)
(eo + 61 - -
1 Eo
(Eo + = 1) (Definition of En)
Elply = 0).
17

---

Since Y is binary and Pr(Y = E (0, 1), it follows that E E = 0] = = 1];
E| IL Y. Since Y is binary, its distribution is specified entirely its mean, and so Y 11 Y. It follows that the covariance between Y and Y is 0: B[(Y B[ -
[B[E[(Y ( - XX]]
(Law of Total Expectation)
E[[E[Y - X I[[ X+]]]
(Y T1 Xs
= (E[E [[]])))))
where the final equality holds because Y and Y have identical conditional distributions given Xs. Since the L2 norm of random variable is 0 and only if the variable is 0 almost surely, it follows that, Px. -almost surely,
0 == E|Y - Xs] = X - EM,
so that X|] TT Xs. Since Y is binary, its distribution is specified entirely by its mean, and so IL Xs. proving the forward implication.
To prove the reverse implication, suppose Xs and are independent. Then Y and are also independent. Hence,
E = E = E y = 0] = -1-60 E0,
so that Eo + + 11
We now use Lemma 4.5 prove Thm. 4.4:
Proof. To begin, note that Ý has the same conditional distribution given X5 Y (i.e., P7iXs and that y is conditionally independent of given Xş (Y TT Xs). Then, since Pr(Y- 1] E[[rrYY X|]] Pr[Y =1],
Pr(xs
(A.2)
we have
Pr Y 1, =
6 = Pr|r = 1|Y =
(Definition of e1)
Pr|Y =
Pr Y = 1, 1
(Eq. (A.2))
Pr|Y =1]
Ex, Pr Y = 1, = 1|Xs
(Law of Total Expectation)
Ex, [Pr = X|]
Ex, Pr|Y 1|Xs] Pr|y 1|xs]]
? 11 Y|Xs)
Ex₃ (Pr[ 1|Xs]]
Exg [Pr[Y 1|
(Pyixs -Pyxx))
Ex, Prr|Y = 1|X
entirely in terms of the conditional distribution Py|xe and the marginal distribution Pxş. Similarly,
Ex, 0| Meanwhile, by the law of total expectation, and the Ex, [P][Y=0[Xs]]
6o can be written as cD
assumption that Xs (and hence Y) is conditionally independent of Xu given Y, the conditional distribution Pyxxa of Y given Xy can be written as
Pr(y 1 1|Xul
= =Pr(f = 1|Y = =0, P = 1111---XX-------//-------------- = 1|Xu]
X|xu]
-Pr(Ý- =1|Y- Pr] 00000 -|
=(1-ca)(1- - -Pr/Y
1|Xu]
= (Co
= 1|Xy]] -1
18

---

By Lemma 4.5, the assumption Xs f Y implies eo + * 1. Hence, re arraannggng the above equality gives us the conditional distribution pr|xy of Y given Xu purely in terms of the conditional Py|xs and Px..Xu'
Pr(Y = 1 = Xul Pr = 1 Xul + + -1
60 + -
It remains now to write the conditional distribution Xy in terms of the conditional distributions Py|xs and Py|xu and the marginal Py. Note that
Pr[Y 1s,,, Xul
Pr[Xs, Xu| Y 1) Pr 1]
(Bayes' Rule)
Pr[Y = 0 X,, Xul
Pr[Xs, Xu| Y = 0] Pr Y = 0]
Pr[Xg] Y 1 Pr Pr Y Pr 1
(Complementarity)
Pr[ Pr[Xs|Y Y = 0] Pr(Xuu|Y Y 0] Pr|r 0
Pr 1 X Pr X Pr|Y 0
(Bayes' Rule)
Pr[Y = 0) Xs] Pr[Y = 0) Xul Pr[Y= = 1]
It follows that the logit of Pr[Y- = X| Xu] can be written as the sum of a term depending only on
Xs. a term depending only on Xu. and a constant term:
Pr|Y- 1 Xs,,, Xu]
logit (Pr(Y- 1 Xul) = log 1 - Pr Y = X| Xul
Pr[Y- 1| Xu]
log
Pr[Y = 0|Xs, Xul
Pr[Y- 1[Xs]
+ +log Pr 1|Xu] Pr
log Pr|Y = 0|Xs]
log
Pr|Y = 0|Xu] Pr|Y = 0]
logit (Pr\Y 1| logit (Pr(Y = 1|Xu)) logit (Pr(Y 1))
Since the sigmoid is the inverse of logit.
Pr(Y- 1| Xu] (logit (Pr[Y- 1| logit (Pr(Y 1|xu logit (Pr(Y 1))),
which, by Eq. (4.3), can be written in terms of the conditional distribution Py|xs and the joint distribution Px
A.2 Further discussion of Theorem 4.4
Connections to learning from noisy labels. Thm. 4.4 leverages two theoretical insights about the special structure of pseudo-labels that complement results in the literature on learning from noisy labels. First, Blanchard et al. [7] showed that learning from noisy labels is possible if and only the total noise level is below the critical threshold Eo + E1 > in the case of learning from labels, we show (see Lemma 4.5 in Appendix 1) that this is satisfied if and only if Xs is informative of (i.e., Y 14. Xs). Second, methods for learning under label noise commonly assume knowledge of Ep and e [44], which may be unrealistic in applications where we have absolutely no true (i.e., test-domain) labels; however, for pseudo-labels sampled from a known conditional probability distribution Pyixs. one can express these noise levels in terms of Py|x, and Pxş and thereby estimate them without any true labels, as on line 3 of Alg. 1.
Possible applications Thm. 4.4 beyond domain adaptation The reason we wrote Thm. 4.4 the more general setting of the marginal problem rather than in the specific context of domain adaptation that we envision possible applications a number of problems besides domain adaptation. For example, suppose that, after learning calibrated machine learning model M1 using a feature Xs. we observe an additional feature Xy.. In the case that Xs and Xy are complementary. Thm. 4.4 justifies using the cuudent-teached paradigm [11, 2, 27] to train model for predicting Y from Xu (or from (Xs, Xu) jointly) based on predictions from M1. This could be useful if we don't 't have access to labeled pairs (Xu, Y). or if retraining model using Xs would require substantial computational resources or access to sensitive or private data. Exploring such approaches could be a fruitful direction for future work
19

---

B Proof of Theorem 4.6
This appendix provides proof of Thm. 4.6, which provides conditions under which proposed domain adaptation procedure (Alg. 1) is consistent.
We state formal version of Thm. 4.6:
Theorem 4.6 (Consistency of the bias-corrected classifier). Assume
Xş stable,
Xs and Xu are complementary, and
Xş is informative of Y (i.e., Xs 14 Y).
Let in : :s x Xu > [0, given by In (Xs: = a fs((* (x(ss) + logit
(" (fum((u) + Eo,n - Eo,n + E1,= -1 B1)
for all (xs, E Ass x Xu.
denote the bias-corrected regression fancttioon estimate proposed in Alg. 1, and let hn : Ns x Xu {0, 1) given by
Rn (x), = = 1(7xxxx, > 1/2], for all (xs, xu) E X's x Xu.
denote the corresponding hard classifier. Let nu Au 00,1), given by nu(xu) = Pr|Y 1|Xy= = xu, = 1] for all xu E Xy, denote the true regression function over Xu, and let Uuu denote its estimate assumed in Line of Alg. 1. Then, + 00,
(a) if. for Pxy-almmn almost all xu E Ny, (z,)( + nu(xu) in probability, then in and hn are weakly consistent (i.e., (x5, + ((xxxxx) almost probability).
almost surely and R(h,,) - R(h*) in
(b) if, for Pxy-allmn almost all xu E Xu. funnxx)) + (u(xx) almost surely, then in and hn are strongly consistent (i.e., (x(xx,xu) - (x), Pxy.xy-almost almost surely and R(hx) R(h*) a.s.).
Before proving Thm. 4.6, we provide few technical lemmas. The first shows that almost-everywhere convergence of regression functions implies convergence of the corresponding classifiers in classifi- cation risk:
Lemma B.1. Consider a sequence of regression functions 17, //, u/. X - [0,1]. Let h, h h2.
X >> {0, denote the corresponding classifiers
h(x)- = 1()((x) > 1/2} and hi(x) = 1(mx(x > 1/2], for all E N
(a) (x) - 17(x)) for Px-almost all E X in probability, then R(hn) - R(h*) in probability.
(b) If (x)) (x) for Px-almost all x E X' almost surely n - co, then R(hn) - R(h) almost surely.
Proof. Note that, since nn (x) # h(x) implies (x)(x) (x)] 2 1n(x) - 1/2// 1 1h, (x) # hxx) < (1))((x) (x)) Z (n(x) - 1/21].
(B.1)
We utilize this observation prove both (a) and (b).
Proof of (a)
Let 8 0. By Inequality (B.1) and partitioning X' based on whether [2n 1
8/2,
Ex (X2 [l1 h())]
< Ex [(2 (X) 1[1{(m((X) 7x)] 2 (T( 1/2
Ex (X2 111((mm(() (XX] > (){ - (122)
Ex (1))))))
- -1| 5/2
< (1f11,x)) -x(x] 5/2)] +8/2
20

---

Hence,
lim Pr [rx (X) - (11( ((x)) > 8]
V/
< lim Pr [rx (1(1/(()) - x(() > 6/2)] > 5/2]
11000 Y/
lim
Eng Ex [L( 1xx) 8/2]]]
(Markov's Inequality)
700
lim
Ex En [1 (X) 7/ (x) 8/2H]]
(Fubini's Theorem)
11000
2
Ex
lim Pr [1 (X) 7xx) > 8/2]
(Dominated Convergence Theorem)
8 # 100 V/n
0.
(7 (X) - 7x(),, Px-a.s. in probability)
Proof of (b) For any x E X with (x) + 1/2, if (x) + (x) then (x) - 77(x) 2 [n(x) - 1/2 + O. Hence, by Inequality (B.1), 1), the dominated convergence theorem (with (2)
111[// - xxx)] 2 [x)x) - 1/2 < 1), and the assumption that (n) + (x) for Px-almost
all X' almost surely,
lim Ex (X) 1 (h (X) + h(x)H)
n1000
lim Ex [| (X) 111()1x()) - (xx] 2 In(X) 1/113]
11000
Ex lim / (X) 1/1(1na(x) -n(()] 2 14(x) - 1/213]
0, almost surely.
Our next lemma concerns an edge case in which the features Xs and Xu provide perfect but contradictory information about Y, leading to Equation (4.4) being ill-defined. We show that this can happen only with probability over (Xs, Xu) PXx.Xu can thus safely ignored:
Lemma B.2. Consider two predictors X5 and Xy of binary label Y. Then,
[[[|[Xs] and EE Xu] = 0] = Pr [E[|]Xs] = 0 and E[ =1] =1 Xs.Xu
Xs.Xu
Proof. Suppose, for sake of contradiction, that the event
A :: (u) E[r|Xs xg] and [B[Y|Xu xul = 0} has positive probability. Then, the conditional expectation E|Y|A] is well-defined, giving the contradiction
Ex, E Xs|] E[Y|A]] Ex, E Y Xu]]
The case X[ and E is similar.
We now utilize Lemmas B.1 and B.2 to prove Thm. 4.6.
Proof. By Lemma B.I, it suffices to prove that n(xs, xu) (xs, xu), for Pxs.xy-almost almost all xu) Xs Ny. in probability (to prove (a)) and almost surely (to prove (b)).
Finite case We first consider the case when both Pr[M|Xs= = xs), xul E (0,1), so
that fs(ss) and logit (M(x))+0=1)) are both finite. Since 6ote)-1
(xs, 175,u Xu)
=o (f((xx)) + logit
(xu) + -
BLL) -o (1s(xs) + logit (((xx) 60 -
B1 B1).
Eo é] -1
6o + -
where the sigmoid : -> [0, is continuous, by the continuous mapping theorem and the assumption that fu, (xx) (xxx) prove both of these, it suffices to show:
21

---

(i Eo + eo and ē₁ + é1 almost surely as n + c0.
(ii Bi + fı E (oo,, oo) almost surely as 11 - co.
(iii) The mapping (a, b, c) > logit
[++b-] b+c-1)
is continuous at (o.
We now prove each of these in turn.
Proof of (i) Since Y; TT Xi and 0 < Pr(y 1). by the strong law of large numbers and the continuous mapping theorem,
G
E (fs(((())) n1
1
E. Po (fs(((())) + Y
([) 1H} Hl = = =1
Pr[y =
almost surely as n + co. Similarly, since Pr[ = -1 Pr 8 = 1] > 0, 20 + En almost surely.
Proof of (ii) Recall that
B1 = logit
11 Σ ?
By the strong law of large numbers, 1 -i= Y + Pr|y = 1|E = 1] Pr[Y = 1 1]. Since we assumed Pr[Y = 1 = 1| E (0,1), follows that the mapping + logit(a) continuous at a = Pr = 1 = 1]. Hence, by the continuous mapping theorem, PL. + logit (Pr[Y- E 11) B1 almost surely.
17
Proof of (iii) Since the logit function is continuous on the open interval (0, 1) and we assumed ED E1 > 1. it suffices to show that 0 < î7 (xu) + eo 1 < ep + 1. Since, according to Thm. 4.4,
jxxx) (co + c 1)n" (xu)) + co. this holds as long as 0 < 11" (xu) 1, assumed for -almost all xu Xu-
Infinite case We now address the case where either Pr|y[Xs = xs] E {0,1} or Xu = xu] 1). By Lemma B.2, only one of these can happen once, Px5.Xy almost surely. Hence, since lim, yoe $1,1 is also finite almost surely, if Pr[Y
xs] E {0,1). 1]. then (xs, =
(Pogit(Pr Y Xs = xs])) (xs, xu), while, Pr|Y|Xu = xul E (0, 1}. then (7xxs (Iogit(Pr|Y|Xx) xul)) = (xs, xu), in probability or almost surely, appropriate.
C Multiclass Case
In the main paper. to simplify notation, we presented our unsupervised test-domain adaptation method in the case of binary labels Y. However, in many cases, including several of our experiments in Section 6, the label Y can take more than distinct values. Hence, in this section, we show how to generalize our method to the multiclass setting and then present the exact procedure (Alg. 2) used in our multiclass experiments in Section 6.
2 classes. We "one-he hot encode" these classes, so that Y takes values in the set Suppose we have
y = {(1,0,..., 0), 1, O), (0, (0....0,1)) 0,1)) C {0.1)*.
L E [0, 1 with
Ey.y Pr y =
denote the conssicon confusion matrix of the pscudo-labels. Then, we have
X| = Σ
y y, Xul Pr(Y = y/ Xul
(Law of Total Expectation)
ycy
Σ E = y) Yr = y/ Xu]
(Complementary)
yey
= -\
(Definition of e)
22

---

When is non-singular, this has the unique solution Xu] = [(]]]] giving multiclass
equivalent of Eq. (4.3) in Thm. 4.4. In practice, however, it numerically more stable estimate [E[|] Xu] by the least-squares solution
arg min PEAY
Ep E[
which is what we will do in Algorithm 2. To estimate without observing the label Y in the test domain, note that
Eyy' = Pr(f = y/Y =y- = pr|y= = y, y.
Pr(Y = y41
IE pr -.,=vy1Xs)
IE [Pr[Y== = X/ll
IB Pr(y y/\xs Pr(Y Xs]
E = x|ss
(ig(Xx) (Xs)
EE (X))((s) (Xs)
This suggests the estimate
ey Di Ssy (Xsi) (Ksi)ssA (yysss(Xs (Xs,)
(Xy,(Xs))
Σ Bsy (Xs,)
Psy (Xs,)
D fay (Xs,)
of each Eyy', in matrix notation,
= f (Xs) Nfrmalize(fs(X5))
where Normalize(X) scales each column of X sum to 1. This gives us multiclass equivalent of Line 3 in Alg. 1.
The multiclass versions of Eq. (4.4) and Line 6 of Alg. are slightly less straightforward. Specifically, whereas, in the binary case, we used the fact that Pr[X, Xx, XuJY + 1] = Pr[Xs, Xu|Y 0] Pr|Xs|Y 0] Yr
X F Pr Y * 1] (by complementarity). in the multiclass case, we do not have Pr[Xs, Xul Y + 1 = Pr xx/X Y * Prrr[XulY * 1]. However,
0
following similar reasoning as in the proof of Thm. 4.4, we have
Pr|Y y Xs, XUI, E]
Pr(Y y/ Xs, XU, E] En by Pr|y = y' Xu, E]
Pr|Y ス Xs, Xu,
Pr[Xs, Xul Y = y, EJ Pr(Y = y|E]
(Bayes' Rule)
Ey Pr(Y / Xs, Xu, El Pr(Y YE
Pr|Xs] Y E, Pr Xul Y y, PT E
(Xs Xu|l)
Exty /y Pr(X [x|s Y = y', Pr
Pr y
Pr(Y= = y E) Pr(Y - E]
(Bayes' Rule)
Ey Pr-y y'1Xs, E| Pr|Y = yu
Pr v PrYY E
Hence,
Pr|Y = y/ El Pr y E]
logit(Pr(Y = y/Xs, Xu, El) = log
Ey' Pr(y y' F.
Pr(y
y Xu. F.J
Yr E Y-
Q Q
Qy
Qy |
= =log
log
= logit
En'ty Qy
O
Ey Av
TQQI
23

---

for Q E R'' defined by
fs.y Xs) (uy (X)) (Xu)
Qy
for each y E y.
Pr(Y =
In particular, applying the sigmoid function to each side, we have
Pr|y|Xs, Xul
||Q11
We can estimate Qy by In matrix notation, this is
fsN (Xs) fun) fu, (Xu) (Xs)
2y =
I
n Ei=1 fay( (x,i)
= fx()s) o ful (X1)
π E (Xs,))
where denotes element wise multiplication. It follows that, for p E A (we will use Py Pr(Y
y)), we can use the multiclass combination function C: A x A - A with
PSPU
Cp(ps, Pu) Normalize
(C.1)
where the multiplication and division are performed element-wise and Normalize(x) = x to generalize Eq. (4.5). Putting these derivations together gives multiclass version of Alg. presented in Alg. 2, where A {z [0,1]* Eyey Zy 1} denotes the standard probability simplex over y.
x
Algorithm 2: Multiclass bias-corrected adaptation procedure.
Input: Calibrated stable classifier fs X' A with (sy((s) Pr(Y y|Xs xg), n unlabeled samples {(Xs,i Xu,;)
Output: Joint classifier f: Xs x Xu + A estimating Pr[Y y|Xs xs, Xu xul
Compute soft pseudo-labels [};},- with 9; = fs(Xsi)
Compute soft class counts ñ Σ Y
Estimate cossicoondiional pseudo-label confusion matrix é ff (Xs) Normalize ( (Xs)) 11 ss Pr(Y Xul
Fit unstable classifier (xu) to pseudo-labelled data {(Xu, Y;)] 1=
5 Bias-correction (xu) + arg min PEAD [lep- fu(xx)ll2
// ~ Pr(Y Xul
6 return
1/ Eq. (C.1), & Pr(Y=y|XS, Xul
D Supplementary Results
D.I Trivial solution to joint-risk minimization
In Prop. D.1 below, we assume that the stable fs(X) and unstable fX((X) predictors output logits. In contrast, throughout the rest of the paper, we assume that fx(X) and fu((X) output probabilities in [).
Proposition D.1. Suppose (X)s Bernoull((o(ss())), such that γ IL (x))))fs(X). Then,
E arg min fu=X+R
where (xx,y) x -ology- (1 x) log(1 y) denotes the cross-entropy loss.

---

Proof. Suppose (X) ~ Bermolli(o((s(())) such that Y TT ff((X)lssXX). Then,
E[EE(((
(Law of Total Expectation)
+ |LE77756600))lleeee000044+014110
- fu()))
& 11 (x())((s())
= =Blo(((()))ogg0((50000++0+=
+ (1 -
((s() + fu()))]
(ffs(X) Bernoulli(r
Since the cross-entropy loss is differentiable and convex, any fu(() satisfying
Tull T E(e((, fx( + fu)( is a minimizer. Indeed, under the mild assumption that the ex-
pectation and derivative commute, for fu(X) = 0,
d E(((),((s(()) +u = E (
offs(X))
1- off((X))
+ 1- ofs((() + fu(()) 1- ((f((s(())
= - [(fs(X))
((fs(X)) 11oo(s(X]) =0
D.2 Causal perspectives
The stability, complementarity. and informativeness assumptions in Thm. 4.4 can be interpreted constraints on the causal relationships between the variables Xs. Xu, Y, and E. We conclude this section with result with characterization of causal, directed acyclic graphs (DAGs) that are consistent with these assumptions. In particular, this result shows that our assumptions are satisfied in the "anti-causal" and "cause-effect" settings assumed in prior work [49, 68, 31], as well as work assuming only covariate shift (i.e., changes the distribution of X without changes the conditional Pr(x).
E
X
X
Xs,C
Y
Xs,E
Figure 3: Causal DAGs over the environment E, three types of stable features (causes X5,c, effects Xs, and spouses X),s), unstable fcatures Xu. and label Y, under conditions 1)-6). At least one, and possibly both, of the dashed edges E + Xs,c and + Xu must be included. The dotted edge E Xs,s may may not be included.
Proposition D.2 (Possible Causal DAGs), Consider an enviroument variable E, two covariates Xu and Xs, and a label Y. Assume there are no other hidden confounders (i.e., causal sufficiency). First, assume:
1) E is a root (iee none of Xu, Xs. and an ancestor of E).
2) X is informative Y (ie., Xs V.. Y{E).
3) Xs and Xy are complementary predictors of Y; i.e. Xs 11 Xul(Y,F) E).
4) Xs is stable (i.e., E IL X))s).
25

---

These are the four structural assumptions under which Theorems 4.4 and 4.6 show that the SFB algorithm learns the conditional distribution Py the test domain. Additionally, suppose
5) Xy is unstable (ie., E. JA Y(Xu), This the case in which empirical risk minimization [ERM;
65] may suffer bias due to distribution shift, and hence when SFB may outperform ERM.
6) Xu contains some information about that is not included in Xs (i.e., Xu M Y Xs). This is information expect invariant risk minimization [IRM; 1J is unable to learn, and hence when we expect SFB to outperform IRM.
Then, Yu consists of causal descendants ("effects") of Y, while three types of stable features are possible:
1. causal ancestors Xs,c Y,
2. causal descendants Xs,F Y that are not also descendants of
3. causal spouses Xs,s Y (i.e., causal ancestors of Xs,E).
Notable special cases of the DAG in Figure 3 include:
1. the "cause-effect" settings, studied by Rojas-Carulla et al. [49], von Kügelgen et al. [68, 69], where Xs is cause of Y, Xu is an effect of Y. and E may affect both Xş and Xu but may affect only indirectly through Xs. Note that this generalizes the commonly used "covariate shift" assumption, not only the covariate distribution Pxç.Xu but also the conditional distribution Py|x, can change between environments.
2. the "anti-causal" setting, studied by Jiang and Veitch [31], where Xs and Xu are both effects of Y, but X5 is unaffected by E.
the widely studied "covariate shift" setting [62, 23, 6, 61], which corresponds (see Sections 3 and 5 of Schölkopf [55]) to causal factorization P(X, Y) P(X))((Y\X) (i.e., in which the only stable components Xg are causes Xs,c) of Y or unconditionally independent (e.g., causal spouses Xs,s)) of Y.
However, this model is more general than these special cases. Also, for sake of simplicity, we assumed causal sufficiency here; however, in the presence of unobserved confounders, other types of stable features are also possible; for example, if we consider the possibility of unobserved confounders U influencing Y that are independent of E (i.e., invariant across domains), then our method can also utilize stable features that are descendants of LI (i.e.. "siblings" of Y).
E
Datasets
In our experiments, we consider five datasets: two (synthetic) numerical datasets and three image datasets. We now describe each dataset.
Synthetie: Anti-causal (AC). We consider an anti-causal synthetic dataset based on that of Jiang and Veitch [31, $6.1] where data is generated according to the following structural equations:
Y + Rad
Y
Be
Xs + Y. Rad((..)))
Xu +- Y Rad(
Xs
X
where the input X = (Xs, Xu) and RB)( denotes a Rademacher random variable that is -1 with probability - B and +1 with probability B. Following Jiang and Veitch [31, $6.1], we create two training domains with Be E (0.95, 0.7). one validation domain with Be 0.6 and one test domain with f.- = 0.1.
Synthetic: Cause-effect with direct Xs-Xur dependence (CE-DD). We also consider synthetic cause-effect dataset which there a direct dependence between Xş and Xu- In particular, follow- ing Jiang and Veitch [31, App. B], data is generated according the following structural equations:
26

---

Xş (055;,
Y
Be
Y XOR (e,
Xu XOR(XOR(Y) Bern(B Xs),
Xs
Xu
where the input
(Xs, Xu) and Bern( () denotes a Bernoulli random variable that is with B. Note that Xs Jı Xu since X5 directly influences Xu-
probability B and 0 with probability Following Jiang and Veitch [31, App. BJ. we create two training domains with Be (0.95, 0.8}, one validation domain with Be- 0.2, and one test domain with B.- 0.1.
ColOrMNIST. We next consider the ColorMNIST dataset [1]. This transforms the original MNIST dataset into a binary classification task (digit in 0-4 or 5-9) and then: (i) flips the label with probability 0.25, meaning that, across domains, digit shape correctly determines the label with probability 0.75; and (ii) colorizes the digit such that digit color (red or green) is more informative but spurious feature (see Fig. 4).
PACS. We next consider the PACS dataset [37]- 7-class image-classification dataset consisting of 4 domains: photos (P), art (A), cartoons (C) and sketches (S), with examples shown in Fig. 4. Model performances are reported for each domain after training on the other 3 domains.
Camelyon17. Finally, in the additional experiments of App. F.2, we consider the Camelyon17 [3] dataset from the WILDS benchmark [33]: medical dataset with histopathology images from hospitals which use different staining and imaging techniques (see Fig. 4). The goal is to determine whether or not a given image contains tumor tissue, making a binary classification task across domains (3 training, I validation, 1 test).
Dataset
Domains
+90%
+80%
-90%
3
3
3
ColorMNIST
(degree of
color label)
Art
Cartoon
Photo
Sketch
PACS
hoop tal
Hosoital 2
Hosphal
d Hosp 4
di Hospital 5
Camelyon17
Figure 4: Examples from ColorMNIST [1], PACS [37] and Camelyon17 [3]. Figure and examples
based on Gulrajani and Lopez-Paz [24, Table 3] and Koh et al. [33, Figure 4]. For Col MolorMNIST, we follow the standard approach [1] and use the first two domains for training and the third for testing. For PACS [37]. we follow the standard approach [37, 24] and use each domain in turn for testing, using the remaining three domains for training. For Camelyon17 [3]. we follow WILDS [33] and use the first three domains for training, the fourth for validation. and the fifth for testing.
Further Experiments
This appendix provides further experiments which supplement those in the main text. In particular, provides: (i) an ablation on the ColorMNIST dataset showing the effects of bias correction, post- hoc calibration and multiple rounds of pseudo-labelling SFB's performance (F.1.I); (ii the
27

---

performance of SFB on the ColorMNIST dataset when using different stability penalties (F.1.2); and (iii) results on real-world medical dataset, Camelyon17 [3]. where we find that all methods perform similarly when properly tuned (F.2).
F.1 ColorMNIST
We now provide ablations the ColorMNIST dataset illustrate the effectiveness of the different components SFB. In particular, we focus on bias correction and calibration, while also showing how multiple rounds of pseudo-labeling can improve performance in practice.
F.1.1
Ablations
Bias correction. adapt the unstable classifier the test domain, SFB employs the bias-corrected adaptation algorithm of Alg. I (or Alg. 2 for the multi-class case) which corrects for biases caused by possible disagreements between the stable-predictor pseudo-label, Y and the true label Y. In this (sub)section, we investigate the performance of SFB with and without bias correction (BC).
Calibration. As discussed 4.2, correctly combining the stable and unstable predictions post- adaptation requires them to properly calibrated. particular, it requires the stable predictor fs be calibrated with respect to the true labels Y and the unstable predictor fu to be calibrated with respect to the pscudo-labels Y. In this (sub)section, post-hoc calibration (in particular, simple temperature scaling [25]). More specifically, we investigate the effect of calibrating the stable predictor (CS) and calibrating the unstable predictor (CU).
investigate the performance of SFB with and without
Multiple rounds of pseudo-labeling. While SFB learns the optimal unstable classifier hy in the
test domain given enough unlabelled data, $ 4. discussed how more accurate pseudo-labels Ý improve the sample efficiency of SFB. In particular, in restricted-sample setting, more accurate pseudo-labels result in an unstable classifier hy which better harnesses Xu in the test domain. With this in mind, note that, after adapting, we expect the joint predictions of SFB be more accurate than its stable-only predictions. This raises the question: can we use these improved predictions to form more accurate pseudo-labels, and, in turn, unstable elassifier li that leads to even better performance? Furthermore, can we repeat this process, using multiple rounds of pseudo-labelling to refine our pseudo-labels and ultimately kiy? While this multi-round approach loses the asymptotic guarantees of $ 4.2, we found it to work quite well in practice. In this (sub)section, we thus investigate the performance of SFB with and without multiple rounds of pseudo-labeling (PL rounds).
Table 4: SFB ablations on CMNIST. Means and standard errors are over random seeds. BC: bias correction. CS: post-hoc calibration of the stable classifier. CU: post-hoc calibration of the unstable classifier. PI. Rounds: Number of pseudo-labeling rounds used. GT adpt: "ground-truth" adaptation using true labels in the test domain.
Algorithm
Bias
Calibration
Rounds
Test Acc.
Correction
Stable
Unstable
SFB adpt.
70.6 + 1.8
SFB
78.0 + 2.9
+BC
1
83.4 1: 2.8
+CS
3.4
+CU
76.6 2.4
+BC+C++CU
84.4
+BC+CS
1
84.9 2.6
+BC+CS
2
87.4
+BC+CS
3
88.1 1.8
+BC+CS
88.6 1
+BC+CS
5
88.7 1 1.3
SEB GT adpt.
89.0 + 0.3
28

---

Results. Table 4 reports the ablations of SFB on ColorMNIST. Here we see that: (i) bias correction significantly boosts performance (+BC); (ii) calibrating the stable predictor also boosts performance without (+CS) and with (+BC+CS) bias correction, with the latter leading to the best performance; (iii) calibrating the unstable predictor (with respect to the pseudo-labels) slightly hurts performance without (+CU) and with (+BC+CS+CU) bias correction and stable-predictor calibration; (iv) multiple rounds of pseudo-labeling boosts performance, while also reducing the performance variation across random seeds; (v) using bias correction, stable-predictor calibration and 5 rounds of pseudo-labeling results near-optimal adaptation performance, as indicated by the similar performance of SFB when using true labels Y to adapt Iff (denoted "SFB GT adpt." in Table 4).
F.1.2 Different stability penalties
In our experiments of $ 6, we used IRM for the stability term of our SFB method, given in Eq. (5.1). However, as discussed
5, many other approaches exist for enforeing stability [35, 58, 47, 15, 67, 40, 77], and, in principle, any of these could be used. To illustrate this point, we now evaluate the performance of SFB when using different stability penalties, namely TRM [1], VREx [35], EQRM [15] and CLOvE [70]. For all penalties, we SFB with bias correction, post-hoc calibration of the stable predictor, and rounds of pseudo-labeling (see the ablation study App. E.1.I).
Table 5: CMNIST test-domain accuracies for SFB with different stability penalties. Shown are the mean and standard error over 10 seeds.
Algorithm
Without Adaptation
With Adaptation
SFB w. IRM
70.6 + 1.8
88.7 1.3
SFB w. VREx
72.5 + 1.0
88.7 + 1.5
SEB w. EQRM
69.0 2.8
88.2 2.5
SFB CLOVE
67.0 3.7
77.0 1 6.6
F.1.3 Full results
We now provide extended/full results of those provided in the main text. particular, Table represents an extended version of Table 3 in the main text, comparing against many more baseline methods. In addition, Table 7 provides the full numerical results for adaptive baseline methods (described in App. G.I), which correspond to the plots of Fig. in the main text.
Table CMNIST test-domain accuracies. Mean and standard error are over 10 seeds. Extended/full
version of Table 3 in the main text.
Algorithm
Test Acc.
ERM
27.9 + 1.5
GroupDRO [53]
29.0 1.1
IRM [1]
69.7 0.9
SD [46]
70.3
IGA [57]
3.3
Fishr [48]
70.1
V-REx [35]
71.6
EQRM [15]
7.4
SEB no adpt.
70.6 1.8
SEB
88.1 = 1.8
Oracle no adpt.
72.1 + 0.7
Oraele
89.9 0.1
F22 Camelyon17
We now provide results on the Camelyon17 [3] dataset. See App. E. for a description of the dataset, and App. G.5 for implementation details.
29

---

Algoriham
Domain (Color Label Coreeltion)
0.7
0.5
ERM
4..
885 4.4
706 0.5
617407
=35007
34.7
4.33
16.4
76
ERM-T3A
98.1:02
583 0.4
0.4
0.5
01
517404
=2.
231 1.44
138 0.
4.5
FRM-PI
976+02
0.3
04
0.6+05
61
02
434-07
346+007
25.000
162+03
7.+06
(all)
900 0.4
9022.04
20.100
50.1104
10.0-00
30.1.006
19..00
99103
0011011
202111
694-17
IM--T3A
1.2
70.3
716111
724
7341119 199
(las
708#22
703
70
69
700
IRM+PL (II))
996
894
793213
687
63.32477
635
638
67
76.0
8722
10
90.5 :
0.5 798
710111
70.9:0.. 0.3
04
13 012::03 79.3
88.713
98.91.5
Table 7: CMNIST comparison with other test-time/source-freee unsupervised domain adaptation methods. Means and standard errors are over 10 seeds. The largest mean per column/domain is in bold. "last": only last-layer updated. "all": all layers updated. Fig. 2 gives the corresponding plot.
Table 2 shows that ERM, IRM and SFB perform similarly on Camelyon17. In line with [24], we found that a properly-tur -unned ERM model can be difficult to beat on real-world datasets, particularly when the model is pre-tree trained on ImageNet and the dataset doesn't 't contain severe distribution shift. While we conducted this proper tuning for ERM, IRM, and SFB (see App. G.5), doing so for ACTIR non-trivial. We thus report the result from their paper [31, Table 1], which is likely lower due to sub-optimal hyperparameters. In particular, we found that, for ERM and IRMM, using a lower learning rate (le-5 vs le-4) and early stopping (1 vs 25 epochs) improved performance by 20 percentage points, from around 70% [31, Table 1] to around 90% (Table 8 below). It remains to be seen whether or not ACTIR can improve over a properly-tuned ERM model on Camelyon17.
While it may seem disappointing that SFB does not outperform the simpler methods of IRM and ERM on Camelyon17, we note that SFB can only be expected to do well when there is some gain in citoo--distribution performance from enforcing stability, c.g., when IRM outperforms ERM. The identical performances of IRM and ERM in Table 8 indicate that, with ImageNet pre-training and proper hyperparameter tuning, this is not the case for Camelyon17. Finally, despite the similar performances, note that adapting SFB on Camelyon17 still gives small performance boost and reduces the variance across random seeds.
Table Camelyon17 test-domain accuracies. Mean and standard errors are over random seeds. t; Result taken from [31, Tab. I] and is likely lower due to sub-optimal hyperparameters (they report 700 for ERM and IRM).
Algorithm
Accuracy
ERM
90.2 1.1
IRM
90.2 - 1.1
ACTIR
77.7 + 1.7t
SFB no adpt.
89.8 1 1.2
SFB
90.3 + 0.7
G Implementation Details
Below we provide further implementation details for the experiments of this work. Code is available at: https///gttabbooommminctatttodtt
G.1 Adaptive baselines
For both the synthetic and CMNIST datasets, we compare against adaptive baseline methods by using pseudo-labeling (PI., (36)) and test-time classifier adjustment (T3A, (30]) top of both ERM and IRM, choosing all adaptation hyperparameters using leave-one-domain-our cross-validation:
ERM/RRM PL (last): After training with ERM/IRM, update the last layer using the model's own pscudo-labels [36].
FRM/IRM + PI. (all): After training with FRM/IRM, we update all layers using the model's own pscudo-labels [36].
30

---

ERM/IRM + T3A: After training with ERM/IRM, we replace the classifier (final layer) with the template-based classifier of T3A [30]. This means; (i) computing template representations for each class using pseudo-labeled test-domain data; and (ii) classifying each example based on its distance to these templates.
G.2 Synthetic experiments
Following Jiang and Veitch [31], we use a simple three-layer network with 8 units in each hidden layer and the Adam optimizer, choosing hyperparameters using the validation domain.
For SFB, we sweep over A in {0.01, 0,5, 10,20} and c in {0.01, 0.1, For SFB's unsuper- vised adaptation, employ the bias correction of Alg. and calibrate the stable predictor using post-hoe temperature scaling, choosing the temperature to minimize the expected calibration er- (ECE, [25]) on the validation domain. In addition, learning rate of 0.01, choosing the number of adaptation steps in [1, 20] (via early stopping) using the validation domain. Finally, we report the mean and standard error over 100 random seeds.
use the Adam optimizer with an adaptation
G.3 ColorMNIST experiments
Training details. We follow the setup of Eastwood et al. [15, $6.1] and build on their open-source create training and validation sets for
code". In particular, we use the original MNIST training each domain, and the original MNIST test set for the test sets of each domain. For all methods, we 2-hidden-layer MLP with 390 hidden units, the Adam optimizer, learning rate of 0.0001 with cosine scheduling, and dropout with 002.. In addition, we use full batches (size 25000), 400 steps warm-up
for ERM pre-training (which directly corresponds to the delicate penalty "annealing" periods used by penalty-bas based methods on Col OrMNIST [1, 35, 15, 74]). and 600 total steps. We sweep over stability-penalty weights in (50, 100, 500, 1000, 5000} for IRM, VREx and SFB and a's in 1 1 e-28 e-250 -5000
500 -750 e- 1-00000 } for EQRM. As the stable (shape) and unstable (color) features are conditionally independent given the label, we fix SFB's conditionallindeeeedeen penalty weight Ac 0. As is the standard for Col ColorMNIST, we use a test-domain validation set to select the best settings (after the total number of steps), and then report the mean and standard error over 10 random seeds on a test-domain test set. As in previous works, the hyperparameter ranges of all methods are selected by peeking at test-domain performance. While far from ideal, this is quite difficult to avoid with ColorMNIST and highlights a core problem with hyperparameter selection in DG-as as discussed by many previous works [1, 35, 24, 74, 15].
SFB adaptation details. For SFB's unsupervised adaptation in the test domain, we use batch size of 2048 and employ the bias correction of Alg. 1. In addition, we calibrate the stable predictor using post-hoc temperature scaling, choosing the temperature to minimize the expected calibration error (ECE, [25]) across the two training domains. Again using the two training domains for hyperparameter selection, we sweep over adaptation learning rates in (0.1, 0.01}. choose the best adaptation step in 5,, 5,20] (via early stopping), and sweep over the number of pscudo-labeling rounds in [1, 5). Finally, we report the mean and standard error over random seeds for adaptation.
G.4 PACS experiments
We follow the setup of Jiang and Veitch [31, & 6.4] and build on their open-source code This means using an ImageNet-pretraan
ResNet-18, the Adam optimizer with a learning rate of 10-1, and choosing hyperparameters using (cave-one-oomain-ouu validation, except with domains). In particular, for each held-out test domain, we train 3 models eachh time leaving out 1 of the 3 training domains for validation- and then select hyperparameters based on the best average performance across the held-out validation domains. Finally, we use the selected hyperparameters to retrain the model using all training domains.
crossvvaiddttin (akin K-fold cross-
For SFB, we sweep over Às in {0.01,0.11 1,5, 10, 20). Ac in (0.01,0.1,1) and learning rates in 5504),. For SFB's unsupervised adaptation, we employ the multi-class bias correction of Alg. and calibrate the stable predictor using post-hoc temperature scaling, choosing the temperature
$ http:///ssshh..cmmmmaaaaoodoottt hhtpss//gtthbb.cmmmyyybinnn////t
31

---

to minimize the expected calibration error (ECE, [25]) across the three training domains. In addition, we use the Adam optimizer with an adaptation learning rate of 0.01, choosing the number of adaptation steps in [1, 20] (via early stopping) using the training domains. Finally, we report the mean and standard error over random seeds.
G.5 Camelyon17 experiments
We follow the setup of Jiang and Veitch [31, $ 6.3] and build their open-source code?. This means using an ImageNet-pretrained ResNet-18, the Adam optimizer, and, following [33], choosing hyperparameters using the validation domain (hospital 4). In contrast [31], we use learning rate of 10-3 for all methods, rather than 10 and employ early stopping using the validation domain. We found this to significantly improve all methods. E.g.. the baselines of ERM and IRM improve by approximately 20 percentage points, jumping from = 70% to 2 90%.
For SFB, we sweep over Aş (01, 10, 20) and Ac in 001, 13. For SFB's unsuper- vised adaptation, we employ the bias correction of Alg. and calibrate the stable predictor using post-hoe temperature scaling, choosing the temperature to minimize the expected calibration er- ror (ECE, [25]) on the validation domain. In addition, we use the Adam optimizer with an adaptation learning rate of 0.01, choosing the number of adaptation steps in [1, 20] (via early stopping) using the validation domain. Finally, we report the mean and standard error over 5 random seeds.
H Further Related Work
Learning with noisy labels. An intermediate goal in our work, namely learning model to predict Y from Xu using pseudo-labels based on Xs. is an instance of learning with noisy labels, widely studied problem [56, 44, 7, 60, 38, 64). Specifically, under the complementarity assumption (Xs II. YulY), the accuracy of the pseudo-labels on each class is independent of Xu, placing us in the so-called class-conditiona random noise model [56, 44, 7]. As we discuss in Section 4, our theoretical insights about the special structure of pseudo-labels complement existing results on learning under this model. Our bias-correction (Eq. (4.3)) for Xy is also closely related to the "method of unbiased estimators" [44]. However, rather than correcting the loss used in ERM, our post-hoc bias correction applies to any calibrated classifier. Moreover, our ultimate goal, learning a predictor of Y jointly using X5 and Xu, is not captured by learning with noisy labels.
Co-training. Our use of stable-fcature pscudo-labels to train a classifier based on a disjoint subset of (unstable) features is reminiscent of co-training [10]. Both methods benefit from conditional indepen- dence of the two feature subsets given the label to ensure that they provide complementary informa- tion. The key difference is that while co-training requires (a small number of) labeled samples from the same distribution as the test data, our method instead uses labeled data from a different distribu- tion (training domains), along with the assumption of a stable feature. Additionally, while co-training iteratively refines two pre-trained classifiers symmetrically based on each other's 's predictions, our method only trains the unstable classifier, in single iteration, using the stable classifier's predictions.
Boosting. Our method of building a strong (albeit unstable) classifier using weak (but stable) one is reminiscent of boosting, in which one ensembles weak classifiers to create a single strong classifier [54] and which inspires the name of our approach, "stable feature boosting (SFB)". However, whereas traditional boosting improves weak classifiers by examining how their predictions differ from true labels, our adaptation method utilizes only pseudo-labels and needs no true labels from the test domain. For example, while traditional boosting only refines functions of existing features, SFB can utilize new features that are only available in the test domain.
Learning theory for domain generalization. In addition to often assuming particular kinds of distribution shifts (e.g.. covariate shift), existing error bounds for domain generalization often depend on some notion of distance between training and test domains (which does not vanish as more data collected within domains) [9, 5, 76, 75] or assume that the test domain has a particular structural relationship with the training domains (e.g., is convex combination of training domains [41]).
7 7Se Footnote
8 "ee Krogel and Scheffer [34], Blum and Mitchell [10, Theorem for discussion of this assumption.
32

---

In contrast, under the structure of invariant and complementary features, we show that consistent generalization (i.e., with generalization error vanishing as more data is collected within domains) is possible in any test domain. Additionally, whereas these prior works derive uniform convergence bounds (implying good generalization for ERM), our results demonstrate the benefit of an additional bias-correction step after training. We also note that, in much of this literature, "invariance" refers to invariance of the covariate marginal distribution Px across domains; in contrast, our notion of stable features (Defn, 4.1) refers to invariance of the conditional Py X
I Performance When Complementarity is Violated
Thm. 4.4 justifies the bias correction of Eq. (4.3) under the assumption that stable X5 and unstable Xu features complementary, i.e., conditionally independent given the label Y. In this section, we discuss what happens if this assumption is relaxed and provide some intuition for why the bias correction appears to help even when complementarity is violated (as we observed in some of our experiments). In particular, we provide an argument that, in most cases, the bias correction should improve the accuracy of naive classifier by making it agree more often with the Bayes-optimal classifier. While not rigorous proof, we believe that this argument provides some insight into SFB's strong performance even when complementarity is violated.
In the absence of complementarity, the quantity Pr 1|Y = X, xy] no longer reduces to the class-wise accuracy Pr[Y 1 1); thus write more generally e (xu) Pr Y 1|Y 1, X = xu]. and we write ET = Ex, [er (Xu)) = Pr = 1 = 1] instead of simply ej for the accuracy class 1. Similarly, write cx(xx) Pr[y 0 0, Xx xu). and write 60 = Ex (Xu)] Pr Y 0) instead of simply eo for the accuracy on class 0.
Let fx = Pr|Y X xu] denote the true regression function, and let hx() = (xf( > 0.5} denote the Bayes-optimal classifier. It is well known that the Bayes-optimal classifier ht, has the maximum possible accuracy out of all classifiers. Thus, the sub-optimality of classifier ht can be measured by the probability S(h) = Prxy [h (u) o h, (Xy)l that disagrees with the Bayes-optimal classifier. Our next result expresses S(h) in terms the true regression function fa, the functions eo and c1, and the distribution of Xu, when h is the bias-corrected classifier
yr = 1 Xu = xul ED E1 > 0.5
hBC(Xu)= ==
Eg E1
from Thm. 4.4 or when ht is the "naive" classifier
h NNaiee := 1 Pr|y = 1|xu = xul > 0.5
that simply treats the pseudo-labels as true labels. Proposition I.1.
S (hBC) = Pr If((Xu) 0.5| |eo(Xu) (X() Exy (eo(Xu) (uu) E1 (1(x)]]] 2(co (X() + (Xtr) -
and
lco (X() 61 (Xu)l [fa(Xu) - 0.5l S 2(co(Xu) + c (Xu) 1)
S (INaive)
= Pr Xu
These two formulae for S (hBc) and (NNaae differ only in the numerator of the right-hand side; letting Z := (o(Xu)= E (Xu). the sub-optimality of hBC scales with -Z |B[2]]. whereas the sub-optimality of INNiiee scales with Z]. Intuitively, for all except very pathological random variables Z, |Z- E Z|| is typically smaller than |Z]. Although not rigorous proof that the bias correction is always better than the naive classifier, this analysis provides an argument that, in most cases, the bias correction should improve on the accuracy of the naive classifier, by making it agree more often with the Bayes-optimal classifier.
We conclude by sketching the proof of Proposition I.I:
33

---

Proof. By construction, a thresholding classifier h(xx = 1[f(x) > 0.5) disagress with the Bayes- optimal classifier if and only if
f(x 0.5 fx())
fx(x) - 0.5 < fxx).
Xy= and f(x) = Pr|y = 1|Xu ég |6 1
Expanding these inequalities in the cases f(x) and solving for the quantity (x) 0.5 in each gives Proposition I.1.
34


Reviews:
[{"review_id": "fEtRSCu1oS", "reviewer": "Reviewer_S7EC", "summary": "This paper introduces a method to utilize spurious features when they are assumed to carry complementary information for predictions. A main contribution is to show that with unlabeled test samples, it is possible to learn how to use spurious features in the test domain. Based on the assumption that both stable feature $X_S$ and spurious feature $X_U$ are known, they derived a provably consistent algorithm for unsupervised test-domain adaptation. They further propose a new training objective function to learn $X_S$ and $X_U$ simultaneously when we have multiple training domains, based on the complementarity assumption ($X_S$ ⊥ $X_U$|$Y$). The full algorithm, including training and test domain adaptation, is named Stable Feature Boosting (SFB). The effectiveness of the test adaptation part of SFB is theoretically proved to be consistent. The whole SFB is empirically shown effective on both real and synthetic datasets.", "questions": "- How about the IID performance of SFB?\n- What stability penalty is used to define $P_{Stability}$ in the experiments? How the quality of learning $X_S$ may effect the OOD performance of SFB w. adapt?\n- How this work can be distinguished from existing domain adaptation methods?", "limitations": "The authors have underlined the complementarity assumption as a limitation. Besides, the estimation of $P_{X_S, X_U}$ is challenging in practice when the two variables are high dimensional. Furthermore, this adaptation method is theoretically useful only when $X_S$ is partially predictive.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Originality: good. It is a new exploration on how to harness spurious features.\n- This paper shows a comprehensive theoretical analysis of the adaptation problem.\n- This paper is well written and easy to follow. Experiment settings are well introduced.", "weaknesses": "- Incomplete related works and baselines. As this work assumes the access to a set of unlabeled samples from the test domain, its setting is domain adaptation but not domain generalization. As a result, related works on domain adaption should be discussed and compared so that we can judge the contribution of this work. However, only domain generalization methods are compared, which could be unfair as different knowledge are assumed.\n- IID accuracies are not shown. It is unclear how the SFB affect the IID performance.\n- Missing ablation studies for the new training objective function of SFB.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their comments and suggestions. We hope that we have adequately addressed the concerns below. If the reviewer agrees, we hope that they consider raising their score.\n\n> “Incomplete related works and baselines. As this work assumes the access to a set of unlabeled samples from the test domain, its setting is domain adaptation but not domain generalization. As a result, related works on domain adaption should be discussed and compared so that we can judge the contribution of this work. However, only domain generalization methods are compared, which could be unfair as different knowledge are assumed.”\n\nWe agree that, due to the use of unlabeled test-domain samples, our setting is perhaps most accurately described as multi-source, source-free domain adaptation [8-14]. However, we believe that it is more related to the domain generalization literature, for the reasons outlined below. Having said this, we do agree with the reviewer that related works in (unsupervised) domain adaptation should be discussed and compared in more detail, which we address below.\n\n**Domain generalization or domain adaptation?** Distribution shifts can often be categorised as covariate shift (P(x) changes), label shift (P(y) changes) or condition/correlation shift (P(y|x) changes) [19-21]. While a host of unsupervised domain adaptation (UDA) methods exist for addressing covariate and label shift, few exist for addressing correlation shift. One major reason for this is that, prior to our work, it was unclear how to adapt to such correlation shifts without test-domain labels (e.g., the most related DA method, ACTIR [15], to which we compared SFB in the paper, requires test-domain labels and primarily compares to DG methods themselves). As a result, datasets containing correlation shift have mostly been considered in the DG literature [1–6, 16–18], where the dominant approach has been to learn invariant models (without test-domain adaptation). For this reason, we chose to focus on the DG setting and methods, drawing connections to UDA in the related work.\n\n**Comparing to UDA methods: further experiments.** While UDA methods tend not to consider datasets with correlation shift, there are a few exceptions. One such exception is the test-time adaptation method of T3A [9]. This uses common DG datasets (containing correlation shift) yet adapts in the test domain using unlabelled examples. We have thus added a comparison to T3A on CMNIST (see PDF in general response), as well as a simple but effective pseudo-labeling baseline [7,8]. For the next/final version of the paper, we will add these comparisons for all other datasets (Synthetic, PACS, Camelyon17).\n\n**Comparing to UDA methods: further discussion.** To better highlight the above points, we have pulled up material from the appendix on UDA/pseudo-labelling methods and added further clarifications about the failures on existing UDA methods on severe correlation shifts, as well as their lack of theoretical guarantees on such shifts.\n\n\n> “IID accuracies are not shown. It is unclear how the SFB affect the IID performance.”\n\nFor CMNIST, in-distribution/IID accuracies are depicted in Figure 2 of the submitted text: the 0.9 and 0.8 color-label correlatiions represent the training domains. The corresponding numerical values are now provided in Table 2 of the general-response PDF (newly added). In the next/final version of the paper, we are happy to provide the in-distribution/IID accuracies for SFB and baseline methods on all datasets (unfortunately, we did not save these values so will have to re-run the experiments to get them). This will include both the stable- and joint- predictor performances.\n\n\n> “Missing ablation studies for the new training objective function of SFB.”\n\n**In Appendix F.2**, we provided ablations on the following components of SFB: bias correction, post-hoc calibration and multiple pseudo-labeling rounds. \n\n**In the above PDF (general response)**, we have added ablations showing the performance of SFB when using different objectives for $P_{\\text{Stability}}$ (IRM [1], VREx [2], CLOvE [3]).\n\n**In the next/final version of the paper**, we will also provide ablations for:\n- The $P_{\\text{Stability}}$ and $P_{\\text{Compl.}}$ components of SFB through sensitivity analyses on their hyperparamters ($\\lambda_{\\text{Stability}}, \\lambda_{\\text{Compl.}}$). In particular, we will use 2D contour/heat maps to show performance as a function of these hyperparameters, including the setting where one/both of them are 0.\n- The joint and stable-only risks of SFB in Eq. 5.1.\n\n> “What stability penalty is used to define $P_{\\text{stability}}$ in the experiments? How the quality of learning $X_S$ may effect the OOD performance of SFB w. adapt?”\n\nWe use IRM for $P_{\\text{stability}}$ and have now clarified this in the main text. We have also added ablations showing the performance of SFB with other objectives for $P_{\\text{Stability}}$, namely IRM [1], VREx [2], CLOvE [3] (see general response PDF). These additional ablations elucidate how the quality of learning $X_S$ affects the OOD performance of SFB w. adapt, with poorer stable predictors ultimately leading to poorer post-adaptation performance.\n\n> “the estimation of $P_{X_S,X_U}$  is challenging in practice when the two variables are high dimensional.“\n\nAlthough we described Theorem 4.4 in terms of the more general quantity $P_{X_S,X_U}$, **our pseudo-label approach in fact only requires $P_{\\hat Y|X_U}$**, which is much easier to estimate; any method for calibrated classification can be used for this. We have clarified this in Section 4."}, {"review_id": "HbTdT9GHSN", "reviewer": "Reviewer_NDD6", "summary": "Unlike the common trend in the out-of-distribution generalization literature in the presence of spurious correlation, this paper takes a different approach. They argue that the spurious feature could be utilized to enhance the performance of the classifier. Then they go on to show how unlabelled data in the test domain can be used to train a classifier that adaptively uses the spurious/unstable feature (along with the stable features) to get near optimal prediction performance.", "questions": "**Minor Typos**:\n1. Line 210: X_{S} \\not\\perp Y |E \n2. Line 651: 4th line of the equation: Extra bracket after $\\epsilon_{1}$ and $Pr[Y=1|X_2]$ instead of $Pr[Y=1|X_2]$. ", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "**Clarity**: This paper is very well-written and easy to follow with appropriate connections between theory and experiments. \n\n**Significance**:\n1. The majority of current literature in the OOD generalization in the presence of the spurious correlation is focused on learning a predictor that only uses the stable feature and thus generalizes across different environments. In doing so they throw away (possibly) easy-to-learn and highly predictive features for the given task since their correlation is likely to change across domains. \n2. This work is an important step in the direction of adaptively making use of the spurious feature without any need for extra labels in the test domains. \n\n**Theory**:\n1. Gave sufficient conditions under which we can train an adaptive classifier that could use unlabeled data in the test domain to use the spurious/unstable feature. \n2. Show how to estimate the prediction probability using an individual classifier that only uses stable or unstable features. \n\n**Experiment**:\nDemonstrate that their method achieves near-optimal performance on synthetic datasets where the assumption of their method holds. \n\n\n", "weaknesses": "**Experiment**:\n1. QRM baseline for the syn, Camelyon, and PACS datasets are not available. \n2. Possible experiment on other real-world datasets where we expect the assumption made in the paper to hold: otherwise it is performing almost equivalently on Camelyon17 and PACS.\n\n\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their comments and suggestions.\n\n> “QRM baseline for the syn, Camelyon, and PACS datasets are not available.”\n\nWe are happy to add the QRM baseline for these datasets in the next/final version of the paper.\n\n> “Possible experiment on other real-world datasets where we expect the assumption made in the paper to hold: otherwise it is performing almost equivalently on Camelyon17 and PACS.”\n\nWe are also happy to consider other real-world datasets where our assumptions hold. If we find a suitable candidate, we will run experiments for the next/final version. However, **we note that SFB does not perform almost equivalently (to other methods) on PACS**. In particular, SFB performs best or joint-best on 3 of 4 domains, with a 6-percentage-point improvement on domain S and a 1-percentage-point improvement on domain A (representing a ~25% error reduction compared to the next best method).\n\n\n> “Minor Typos”\n\nThank you for pointing these out – they have been corrected.\n"}, {"review_id": "GTwIIP17F3", "reviewer": "Reviewer_f1Zc", "summary": "This work considers unsupervised domain adaptation, where a learner observes labeled data from multiple source domains and unlabeled data from a target domain, and needs to produce a classifier that works well for data from the target domain. In contrast to the domain generalization setting where no data is available from the target domain, here, the learner can be less conservative and use features that are spurious (unstable or domain-specific) but help improve performance on the target domain. The main challenge is to do this with only unlabeled examples from the target domain.\n\nThe main result of this work (Theorem 4.4) specifies a sufficient condition under which it is possible to use domain-specific features to boost the performance of a conservative classifier that relies on stable features only. Given stable features $X_S$ (i.e., $Y | X_S$ is invariant across domains) and unstable features $X_U$, such that $X_U  \\perp X_S \\mid Y$ (complementarity) and $X_S$ is informative about $Y$, they express $p_\\text{target}(Y | X_S, X_U)$ in terms of $p_\\text{target}(X_S, X_U)$ and $p(Y | X_S)$, both of which can be estimated in the unsupervised domain adaptation setting. Essentially, it reduces to predicting pseudo-labels $\\widehat{Y} \\sim p(Y|X_S)$ from the unstable features $X_U$ and combining it with $p(Y|X_S)$ to construct a classifier that uses both $X_S$ and $X_U$.\n\nBesides this the authors propose a representation learning method that separates stable and unstable features, such that they also satisfy the complementarity assumption. They evaluate their method on a few synthetic datasets, CMNIST, PACS, and Camelyon-17. The results indicate improvement compared to domain generalization methods (i.e., without an adaptation step).", "questions": "- Lines 112 - 116: It should specified what is meant by *relationship* between a feature $X$ and the label $Y$ (i.e., the conditional distribution of $Y|X$). I understand that stable and unstable features are defined later, but at this point of the text reader does not know it and can only guess.\n- Line 115: I think it should be more exact what $X_S$ and $X_U$ are. As I understand from eq. (3.1) they are not subsets of the components of $X$, but rather extracted features: i.e., $X_S = \\Phi_S(X)$ and $X_U = \\Phi_U(X)$.\n- Lines 126-127: This sentence is not rigorous enough.\n- Eq (3.1): It should be $f^e_U(X)$. Also, in (3.1) and (3.2) it should be $h^e_U$ instead of $h^e$.\n- Line 131: $f^s(X)$ -> $f_S(X)$.\n- Lines 137-143: A separate letter should be used to denote the new environment (using $e$ for everything is confusing). Also, the usage of $h_U$ or $h_U^e$ is inconsistent. Why is there a sum over training environments in eq. (3.3)? Shouldn't it be just optimizing for the domain-specific classifier on the target data given already trained $\\Phi_S, \\Phi_U,$ and $h_S$?\n- Line 163: It should be $\\sigma \\circ h_U \\circ \\Phi_U$.\n- Definition 4.3. It should be $X_S \\perp Y \\mid E$.\n- Theorem 4.4: It is worth to mention in the statement that $\\epsilon_0$ and $\\epsilon_1$ can be expressed in terms of $P(Y|X_1)$ and $P(X_1)$.\n- Lines 295-305 (recap and learning goals): I suggest to remove this part. Instead you can bring some parts from the appendix to the main text (e.g., Appendices A.2, H or I).\n- Line 309, objective function: Do I understand correctly that during this first phase you have one domain-specific classifier $h^e_U$ per domain? If so, is the point to make sure that you learn meaningful $\\Phi_U$, rather than a constant function? In that case one can argue that if there is a new kind of spurious features available for the target domain, that might not be picked in this first phase of training.\n- Do the results in the main text use multiple rounds of pseudo-labeling?\n- Are there no suitable unsupervised domain adaptation methods to compare the proposed approach with?", "limitations": "The authors listed assumption of complementarity in Theorem 4.4 as the main limitation of their work. To me this assumption itself is not a big limitation, as it is satisfied in many cases. The main limitation is finding a representation of data that separates stable and unstable features (see my comments on limitations in the \"weaknesses\" section).", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "**Strength #1: Significance.**  Unsupervised domain adaption is an important and relevant setting for the NeurIPS community. The main result (Theorem 4.4) is a solid contribution to the list of conditions under which some form of out-of-domain generalization (with or with adaptation) becomes possible. I like how the problem of label shift that is a challenge for many methods, is handled naturally in the proposed approach.\n\n**Strength #2: Originality.** As far as I know, the main result (Theorem 4.4) is novel. The fact that in population-level analysis even slight informativeness of $X_S$ for $Y$ allows recovering the true conditional distribution $P(Y|X_S,X_U)$ is not trivial.", "weaknesses": "**Weakness #1: Clarity & Presentation.** The clarity of the presentation can be improved. The notation is not consistent in many cases. Many important discussions/details are presented in appendices, while the main text space is not used effectively. Please see more detailed comments below.\n\n**Weakness #2: Limitations.** \n1. In Theorem 4.4, it is assumed that we have access to stable $X_S$ and unstable features $X_U$. This assumption is quite strong, as one can argue that finding stable and unstable features is one of the key steps in out-of-domain generalization. To my best knowledge there are no methods that extract and separate stable and unstable features well.\n2. In Theorem 4.4, it is also assumed that we have access to the Bayes probabilities $P(Y|X_1)$, where $X_1$ are the stable features. In practice this is not easy to achieve.\n3. The proposed algorithm to extract stable and unstable complementary features has many hyper-parameters. It is unclear to me how sensitive is the method to these hyper-parameters and how easy it is to tune them.\n4. The proposed method requires enforcing stability and complementarity, which is challenging. Not only it is hard to enforce these conditions on source domains (e.g., limitations of conditional HSIC), but the same OOD generalization concern arises -- do these conditions enforced on source domains carry over to the target domain? For this reason, the work will benefit significantly from evaluations targeted to reveal how well the proposed representation learning approach achieves stability and complementarity (rather than evaluating only target domain performance after adaptation).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their detailed review, comments and suggestions.\n\n> “Weakness #1: Clarity & Presentation ...”\n\nWe take the reviewer’s point here and acknowledge that there were some notational inconsistencies and that some important material was relegated to the appendix for space reasons. In response, we have:\n- Corrected the typos pointed out by the reviewer.\n- Lines 112 - 116: Added a forward pointer to the formal definitions in Section 4 and been more exact in specifying that $X_S = \\Phi_S(X)$ and $X_U = \\Phi_U(X)$ are extracted features.\n- Lines 126-127: Added a more precise explanation of $\\Phi$ and $h$.\n- Lines 137-143: Used $e^t$ for the new test environment and ensured we are consistent in using $h^e_U$. The reviewer is correct that there should not be a sum over training environments in Eq. (3.3) – this has been removed.\n- Theorem 4.4: Noted that $\\epsilon_0$ and $\\epsilon_1$ can be expressed in terms of $P(Y|X_1)$ and $P(X_1)$.\n- Lines 295-305 (recap and learning goals): Removed.\n- Limitations: Revised the limitations to include the learning/extraction of $X_S$ and $X_U$ as we agree that this is one of the major challenges. We discuss this point further below.\n- Algorithm: Rewritten Algorithm 1 -- please see the general-response PDF.\n\n\n> “Weakness #2: Limitations”\n\nWe now respond to each limitation. In short, we agree with the highlighted limitations and will be sure to discuss them properly in the paper. However, as detailed below, many of these limitations/challenges apply much more widely than just to our method, such as learning a stable predictor, a well-calibrated predictor, or transferring knowledge/functions from source to target domains.\n\n1. _\"In Theorem 4.4, it is assumed that we have access to stable $X_S$ and unstable $X_U$ features. This assumption is quite strong… To my best knowledge there are no methods that extract and separate stable and unstable features well.\"_\n\nWe agree that extracting stable (and unstable) features is one of the key steps in OOD generalization, and very much an open problem (and standalone topic in its own right). We will highlight this open challenge, and note that SFB could benefit from future improvements in invariant/stable-feature learning.\n\n2. _“In Theorem 4.4, it is also assumed that we have access to the Bayes probabilities $P(Y|X_1)$, where $X_1$ are the stable features. In practice this is not easy to achieve.”_\n\nWe agree that, in practice, it is not easy to access Bayes probabilities (i.e., learn a perfectly-calibrated stable predictor). We will highlight this practical difficulty and note that (i) learning well-calibrated predictors is also a topic of active research [22--25] in its own right; and (ii) future improvements in this direction would benefit SFB.\n\n3. _“It is unclear to me how sensitive is the method to hyper-parameters and how easy it is to tune them.”_\n\nWe will conduct a sensitivity analysis for the next/final version of the paper. In particular, we will use a 2D contour/heat map to show SFB’s performance as a function of $\\lambda_{\\text{Stability}}$ and $\\lambda_{\\text{Compl.}}$ on synthetic datasets.\n\n4. _“The proposed method requires enforcing stability and complementarity, which is challenging… do these conditions enforced on source domains carry over to the target domain?”_\n\nWe agree that, like prior works, the goal is for conditions enforced on source domains to carry over to target domains. As with any kind of OOD generalization, carrying properties like stability or complementarity from source to target domains depends on the specific assumptions made about the domains: e.g., IRM [1] assumes that the causal mechanism of $Y$ remains fixed, while QRM [4] assumes IID domains. However, we do not believe that there is a better way to assess this transfer than evaluating target-domain performance (pre and post adaptation). For example, on CMNIST and the synthetic dataset, the near-oracle pre- and post-adaptation performances tell us that (i) stability was indeed transferred to the target domain; and (ii) the unstable features extracted from source domains were successfully transferred to (and exploited in) the target domain. Alternatives include:\n- a. **Conducting a sensitivity analysis**: to see how target-domain performance changes as a function of $\\lambda_{\\text{Stability}}, \\lambda_{\\text{Compl.}}$, i.e., as a function of better-enforced conditions (on the training data). As mentioned above, we will include this sensitivity analysis in the next/final version of the paper.\n- b. **Reporting the magnitude of the conditions/penalties on source and target domains:** This is generally not done in DG (e.g., for [1–3]) as these values are not interpretable/informative.\n- c. **Something else:** Perhaps the reviewer had some other evaluation in mind?\n\n> “Line 309, objective function: Do I understand correctly that during this first phase you have one domain-specific classifier $h^e_U$ per domain? If so, is the point to make sure that you learn meaningful $\\Phi_U$, rather than a constant function? In that case one can argue that if there is a new kind of spurious features available for the target domain, that might not be picked in this first phase of training.”\n\nYes, this is correct. Our method cannot _extract_ a new spurious feature from $X$ at test time, if it was not already included in $\\Phi_U(X)$. However, if a new feature is given to us _directly_ at test time, e.g. patient test results or meta-data to complement imaging results, we can indeed exploit this new feature without labels (so long as it satisfies complementarity). We have added this to our discussion.\n\n> “Do the results in the main text use multiple rounds of pseudo-labeling?”\n\nOnly for CMNIST. We will clarify this in the main text.\n\n> “Are there no suitable unsupervised domain adaptation methods to compare the proposed approach with?”\n\nPlease see the general response and the first part of our response to Reviewer S7EC.\n"}, {"review_id": "OURWgC5jAc", "reviewer": "Reviewer_5BRF", "summary": "The authors present a method for training models that are robust to out-of-distribution data by focusing on stable features. Stable features are those whose conditional relationship with the label do not change across domains. The benefit of their approach is demonstrated 1 synthetic dataset and 3 \"real-world\" datasets. \n", "questions": "How can one know whether two feature sets are complementary? Are there any tests for that?\n\nWhat if the stable features cannot be fully isolated? For example, in Puli et al. the authors need only grab the border of images to define the spurious variables but that leaves the center of the image as a mixture of spurious and non-spurious content. \n", "limitations": "The authors have adequately addressed limitations.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Spurious correlations is a significant problem in many applications, which erodes the power of predictive models and shortens their usable life. The method proposed by the authors helps to mitigate these issues. \n\nThe paper is well written and easy to follow. The proposed algorithm appears easy to use and computationally scalable.\n", "weaknesses": "This work is closely related to Puli et al. (2021). I think the authors should consider comparing against NURD as well.\n\nPuli, Aahlad, et al. \"Out-of-distribution generalization in the presence of nuisance-induced spurious correlations.\" arXiv preprint arXiv:2107.00520 (2021).\n\nDoes line 243 have a typo? What is \\epsilon_1?\n\nAlgorithm 1 (listing) could use some text describing each step.\n\nIn Table 3, please bold the best non-oracle accuracy. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their comments and suggestions.\n\n> “This work is closely related to Puli et al. (2021). I think the authors should consider comparing against NURD as well.”\n\nThank you for pointing out the relevant paper of Puli et al. (2021), which we will cite in the revision. While both their method (NuRD) and ours (SFB) seek to improve OOD generalization, the two approaches are complementary. Specifically, the goal of NuRD is to _remove_ domain-specific information from the predictor, _thereby encouraging stability_. Meanwhile, _SFB builds on top of stability by using it to leverage complementary, domain-specific information_. For example, the representation learned by NuRD could serve as the stable representation/feature $X_S$ used by SFB.\n\nAs a concrete example of how these approaches differ, in our CMNIST experiment (Table 3 of the submission), NuRD (treating color as the nuisance variable) might achieve the 70% test performance of IRM, but NuRD cannot achieve the 90% test performance of SFB, because NuRD _discards_ the unstable but highly informative color feature, whereas SFB _leverages_ color.\n\n> “Does line 243 have a typo? What is $\\epsilon_1$?”\n\nYes, this was a typo; Line 243 should read, “$\\epsilon_0 := \\Pr[\\hat Y = 0|Y = 0]$ and $\\epsilon_1 := \\Pr[\\hat Y = 1|Y = 1]$”. We have fixed this.\n\n> “Algorithm 1 (listing) could use some text describing each step.”\n\nWe agree and have included a clearer version of Algorithm 1 in the general-response PDF above.\n\n> “In Table 3, please bold the best non-oracle accuracy.”\n\nGood point, we have now done so.\n\n> “How can one know whether two feature sets are complementary? Are there any tests for that?”\n\nIf $Y$ takes $K$ values $\\{1,...,K\\}$, then complementarity is equivalent to $X_S \\perp X_U | Y = k$ for all $k \\in \\{1,...,K\\}$. Thus, testing complementarity reduces to performing $K$ tests of independence between $X_S$ and $X_U$ (once using the data from each class). There are many statistical tests for independence, such as $\\chi^2$ tests, kernel- or nearest-neighbor-based tests, etc., which make different assumptions about the distributions of $X_S$ and $X_U$ (discrete vs. continuous, parametric vs. nonparametric, etc.).\n\n> “What if the stable features cannot be fully isolated? For example, in Puli et al. the authors need only grab the border of images to define the spurious variables but that leaves the center of the image as a mixture of spurious and non-spurious content.”\n\nIndeed, as we discuss in the general response, isolating stable features is a challenging and active area of research [1--6]. While the theory supporting SFB assumes $X_S$ is a stable feature, it is agnostic to how $X_S$ is actually learned/extracted/isolated. For example, $X_S$ could be the “uncorrelating representation” learned by NuRD [6], or that learned by IRM [1], VREx [2], CLOvE [3], QRM [4], Fish [5], etc. To illustrate this point, we have added ablations on CMNIST where SFB uses different stability penalties, namely IRM, VREx, and CLOvE (see the general response PDF).\n"}]

Author rebuttal:
We sincerely thank all reviewers for their time and thoughtful feedback.

We were pleased to read that the paper is _“well-written and easy to follow”_ (S7EC, NDD6, 5BRF), has a _“comprehensive theoretical analysis”_ (S7EC), and makes _“an important step in the direction of adaptively making use of the spurious feature without any need for extra labels in the test domains”_ (NDD6).

The main concerns surrounded:
1. Extracting stable $X_S$ and unstable $X_U$ features in practice (f1Zc, 5BRF)
2. Comparing to unsupervised domain adaptation (UDA) baselines (S7EC, f1Zc)

In response, we have:
1. **Added text to our limitations section** on how extracting stable (and unstable) features is very much an active area of research in domain generalization [1–6], and in fact a topic in its own right, with future improvements in this area likely to benefit SFB.
2. **Added comparisons to two UDA baselines** on CMNIST (see attached PDF) and promised to add these baselines for the other datasets in the next version of the paper. In addition, we have **added further discussion of related UDA works**, pointing out that spurious-correlation shifts are typically studied in DG settings rather than UDA settings since, prior to our work, it was not clear how to deal with such shifts (in a principled/guaranteed way) without test-domain labels.

We believe that these clarifications and additional experiments have improved the paper and hope that they have addressed the main concerns of reviewers. We are happy to respond to any further questions/concerns during the discussion phase.

---

We now provide further details on the attached PDF.

### Algorithm 1
We have updated the notation and added comments to make this more readable (as suggested by Reviewer 5BRF).

### Table 1: SFB with different stability penalties
We have added experiments on CMNIST showing the performance of SFB with different stability penalties, namely IRM [1], VREx [2] and CLOvE [3].

### Table 2 & Figure 1: Comparison with UDA baselines
We have added UDA baselines on CMNIST:
- **Pseudo-labeling (PL, [7,8])**: This takes a trained model (e.g., ERM or IRM) and adapts it to unlabeled test-domain data by: (i) predicting; (ii) forming pseudo-labels by taking the maximum class-wise prediction; (iii) updating model weights using the pseudo-labels as if they were true labels; (iv) repeating steps i–iii for t iterations.
- **T3A [9]**: This takes a trained model (e.g., ERM or IRM) and adapts it to unlabeled test-domain data by: (i) predicting; (ii) forming pseudo-labels by taking the maximum class-wise prediction; (iii) forming pseudo-prototype representations for each class (i.e., per-class centroids or mean feature embeddings); (iv) forming new predictions based on the distance to these pseudo-prototypes or centroids.

From Table 2 and Figure 1, we note that:
- SFB performs best on almost all domains.
- When built on ERM, both T3A and PL fail on severe OOD domains (negative color-label correlation). This is no surprise since these methods rely on good initial performance in the test domain, which is not provided by ERM.
- When built on IRM, T3A gives a small but consistent boost on test-domains, particularly when the color-label correlation is strong. However, this boost is far below that of SFB.
- When built on IRM, PL works quite well on test-domains with a very strong color-label correlation (although always below SFB, and with much larger variance). However, on test-domains with a weak or medium color-label correlation, PL actually hurts performance. This is likely because PL does not combine stable and unstable predictions in a principled way (as SFB does; see Eq. (4.2) of the paper), causing issues on domains where a principled prediction-combination is required to achieve good performance.

Note that, to ensure the fairest comparison, we chose UDA methods that can operate in the source-free/test-time setting. Here, there are two distinct phases: (i) training, where methods have access to labeled training-domain data but no test-domain data; (ii) testing/adaptation, where methods have access to unlabeled test-domain data but no training-domain data.

[1] Arjovsky, M., Bottou, L., Gulrajani, I., & Lopez-Paz, D. (2019). Invariant risk minimization. _arXiv preprint arXiv:1907.02893_.

[2] Krueger, D., Caballero, E., Jacobsen, J. H., Zhang, A., Binas, J., Zhang, D., ... & Courville, A. (2021). Out-of-distribution generalization via risk extrapolation (rex). In _International Conference on Machine Learning_ (pp. 5815-5826). PMLR.

[3] Wald, Y., Feder, A., Greenfeld, D., & Shalit, U. (2021). On calibration and out-of-domain generalization. In _Advances in Neural Information Processing Systems_, 34, 2215-2227.

[4] Eastwood, C., Robey, A., Singh, S., Von Kügelgen, J., Hassani, H., Pappas, G. J., & Schölkopf, B. (2022). Probable domain generalization via quantile risk minimization. In _Advances in Neural Information Processing Systems_, 35, 17340-17358.

[5] Shi, Y., Seely, J., Torr, P. H., Siddharth, N., Hannun, A., Usunier, N., & Synnaeve, G. (2021). Gradient matching for domain generalization. _arXiv preprint arXiv:2104.09937_.

[6] Puli, A. M., Zhang, L. H., Oermann, E. K., & Ranganath, R. (2021). Out-of-distribution Generalization in the Presence of Nuisance-Induced Spurious Correlations. In _International Conference on Learning Representations_.

[7] Lee, D. H. (2013). Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. In _Workshop on challenges in representation learning, ICML_ (Vol. 3, No. 2, p. 896).

[8] Rusak, E., Schneider, S., Pachitariu, G., Eck, L., Gehler, P. V., Bringmann, O., ... & Bethge, M. (2022). If your data distribution shifts, use self-learning. _Transactions on Machine Learning Research_.

[9] Iwasawa, Y., & Matsuo, Y. (2021). Test-time classifier adjustment module for model-agnostic domain generalization. In _Advances in Neural Information Processing Systems_, 34, 2427-2440.


Meta-review: The paper shows that spurious features can be harnessed in the test domain without labels, using only invariant-feature pseudo-labels, and propose an algorithm for doing so. Initially reviewers had some concerns about the limitation of the proposed work and comparison with proper baselines. Authors did a good job in addressing these issues during the rebuttal phase. Thus, all reviewers agree the paper is above the bar for being accepted to neurips.
Decision: Accept (poster)