{'fraction_non_alphanumeric': 0.04371897958875798, 'fraction_numerical': 0.013788525653597236, 'mean_word_length': 4.393653376729048, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Domain Generalization using Causal Matching

In the domain generalization literature, a common objective is to learn representations independent of the domain after conditioning on the class label. We show that this objective is not sufficient: there exist counter-examples where a model fails to generalize to unseen domains even after satisfying class-conditional domain invariance. We formalize this observation through a structural causal model and show the importance of modeling within-class variations for generalization. Specifically, classes contain objects that characterize specific causal features, and domains can be interpreted as interventions on these objects that change non-causal features. We highlight an alternative condition: inputs across domains should have the same representation if they are derived from the same object. Based on this objective, we propose matching-based algorithms when base objects are observed (e.g., through data augmentation) and approximate the objective when objects are not observed (MatchDG). Our simple matching-based algorithms are competitive to prior work on out-of-domain accuracy for rotated MNIST, Fashion-MNIST, PACS, and Chest-Xray datasets. Our method MatchDG also recovers ground-truth object matches: on MNIST and Fashion-MNIST, top-10 matches from MatchDG have over 50% overlap with ground-truth matches.


Introduction
Domain generalization is the task of learning a machine learning model that can generalize to unseen data distributions, after training on more than one data distributions. For example, a model trained on hospitals in one region may be deployed to another, or an image classifier may be deployed on slightly rotated images. Typically, it is assumed that Proceedings of the 38 th International Conference on Machine Learning, PMLR 139, 2021. Copyright 2021 by the author(s). the different domains share some "stable" features whose relationship with the output is invariant across domains (Piratla et al., 2020) and the goal is to learn those features. A popular class of methods aim to learn representations that are independent of domain conditional on class (Li et al., 2018c;d;Ghifary et al., 2016;Hu et al., 2019), based on evidence of their superiority (Zhao et al., 2019) to methods that learn representations that are marginally independent of domain (Muandet et al., 2013;Ganin et al., 2016).
In this work, we show that the class-conditional domaininvariant objective for representations is insufficient. We provide counter-examples where a feature representation satisfies the objective but still fails to generalize to new domains, both theoretically and empirically. Specifically, when the distribution of the stable features to be learnt varies across domains, class-conditional objective is insufficient to learn the stable features (they are optimal only when the distribution of stable features is the same across domains). Differing distributions of stable features within the same class label is common in real-world datasets, e.g., in digit recognition, the stable feature shape may differ based on people's handwriting, or medical images may differ based on variation in body characteristics across people. Our investigation reveals the importance of considering withinclass variation in the stable features.
To derive a better objective for domain generalization, we represent the within-class variation in stable features using a structural causal model, building on prior work (Heinze-Deml & Meinshausen, 2019) from single-domain generalization. Specifically, we construct a model for the data generation process that assumes each input is constructed from a mix of stable (causal) and domain-dependent (non-causal) features, and only the stable features cause the output. We consider domain as a special intervention that changes the non-causal features of an input, and posit that an ideal classifier should be based only on the causal features. Using d-separation, we show that the correct objective is to build a representation that is invariant conditional on each object, where an object is defined as a set of inputs that share the same causal features (e.g., photos of the same person from different viewpoints or augmentations of an image in different rotations, color or background). When the object variable is observed (e.g., in self-collected data or by dataset augmentation), we propose a perfect-match regularizer for domain generalization that minimizes the distance between representations of the same object across domains.
In practice, however, the underlying objects are not always known. We therefore propose an approximation that aims to learn which inputs share the same object, under the assumption that inputs from the same class have more similar causal features than those from different classes. Our algorithm, MatchDG is an iterative algorithm that starts with randomly matched inputs from the same class and builds a representation using contrastive learning such that inputs sharing the same causal features are closer to one another. While past work has used contrastive loss to regularize the empirical risk minimization (ERM) objective (Dou et al., 2019), we demonstrate the importance of a two-phase method that first learns a representation independent of the ERM loss, so that classification loss does not interfere with the learning of stable features. In datasets with data augmentations, we extend MatchDG to also use the perfect object matches obtained from pairs of original and augmented images (MDGHybrid).
We evaluate our matching-based methods on rotated MNIST and Fashion-MNIST, PACS and Chest X-ray datasets. On all datasets, the simple methods MatchDG and MDGHybrid are competitive to state-of-the-art methods for out-ofdomain accuracy. On the rotated MNIST and Fashion-MNIST datasets where the ground-truth objects are known, MatchDG learns to makes the representation more similar to their ground-truth matches (about 50% overlap for top-10 matches), even though the method does not have access to them. Our results with simple matching methods show the importance of enforcing the correct invariance condition.
Contributions. To summarize, our contributions include: 1). An object-invariant condition for domain generalization that highlights a key limitation of previous approaches, 2). When object information is not available, a two-phase, iterative algorithm to approximate object-based matches. Also, the code repository can be accessed at: https:// github.com/microsoft/robustdg
Among them, several works (Zhao et al., 2019;Johansson et al., 2019;Akuzawa et al., 2019) show that the class-conditional methods (Li et al., 2018c;d;Ghifary et al., 2016;Hu et al., 2019) are better than those that enforce marginal domain-invariance of features (Muandet et al., 2013;Ganin et al., 2016;Li et al., 2018b;Albuquerque et al., 2020a), whenever there is a varying distribution of class labels across domains. We show that the class-conditional invariant is also not sufficient for generalizing to unseen domains.
Causality and domain generalization. Past work has shown the connection between causality and generalizable predictors (Peters et al., 2016;Christiansen et al., 2020). There is work on use of causal reasoning for domain adaptation (Gong et al., 2016;Heinze-Deml & Meinshausen, 2019;Magliacane et al., 2018;Rojas-Carulla et al., 2018) that assumes Y → X direction and other work (Arjovsky et al., 2019;Peters et al., 2016) on connecting causality that assumes X → Y . Our SCM model unites these streams by introducing Y true and labelled Y and develop an invariance condition for domain generalization that is valid under both interpretations. Perhaps the closest to our work is by (Heinze-Deml & Meinshausen, 2019) who use the object concept in single-domain datasets for better generalization. We extend their SCM to the multi-domain setting and use it to show the inconsistency of prior methods. In addition, while (Heinze-Deml & Meinshausen, 2019) assume objects are always observed, we also provide an algorithm for the case when objects are unobserved. In contrast to regularizing based on contrastive loss, our algorithm MatchDG proceeds in two phases and learns a representation independent of the ERM objective. Such an iterative 2-phase algorithm has empirical benefits, as we will show in Suppl. D.4. Additionally, we propose an ideal object-based matching algorithm when objects are observed.
Other work. Others approaches to domain generalization include meta-learning (Li et al., 2018a;Balaji et al., 2018), dataset augmentation (Volpi et al., 2018;Shankar et al., 2018), parameter decomposition (Piratla et al., 2020;Li et al., 2017), and enforcing domain-invariance of the optimal P (Y |Φ(x)) (Arjovsky et al., 2019;Ahuja et al., 2020). We empirically compare our algorithm to some of them. P m (D, X, Y ). The domain generalization task is to learn a single classifier that generalizes well to unseen domains d ∈ D m and to new data from the same domains (Shankar et al., 2018). The optimum classifier can be written as: f * = arg min f ∈F E (d,x,y)∼P [l(y (d) , f (x (d) ))], where (d, x, y) ∼ P over (D, X , Y).

Insufficiency of class-conditional invariance
As mentioned above, a popular line of work enforces that the learnt representation Φ(x) be independent of domain conditional on the class (Li et al., 2018c;d;Ghifary et al., 2016;Hu et al., 2019), Φ(x) ⊥ ⊥ D|Y . Below we present two counter-examples showing that the class-conditional objective is not sufficient.

A simple counter-example
We construct an example where Φ(x) ⊥ ⊥ D|Y , but still the classifier does not generalize to new domains. Consider a two dimensional problem where x 1 = x c + α d ; x 2 = α d where x c and α d are unobserved variables, and α d varies with domain ( Figure 1(a)). The true function depends only on the stable feature x c , y = f (x c ) = I(x c ≥ 0). Suppose there are two training domains with α 1 = 1 for domain 1 and α 2 = 2 for domain 2, and the test domain has α 3 = 0 (see Figure 1(a)). Suppose further that the conditional distribution of X C given Y is a uniform distribution that changes across domains: for domain 1, X c |Y = 1 ∼ U(1, 3); X c |Y = 0 ∼ U(−2, 0); and for domain 2, X c |Y = 1 ∼ U(0, 2); X c |Y = 0 ∼ U(−3, −1). Note that the distributions are picked such that φ(x 1 , x 2 ) = x 1 satisfies the conditional distribution invariant, φ(x) ⊥ ⊥ D|Y . The optimal ERM classifier based on this representation, (I(x 1 ≥ 1.5) has 100% train accuracy on both domains. But for the test domain with α d = 0; X c |Y = 1 ∼ U(0, 2); X c |Y = 0 ∼ U (−2, 0), the classifier fails to generalize. It obtains 62.5% test accuracy (and 25% accuracy on the positive class), even though its representation satisfies class-conditional domain invariance. In comparison, the ideal representation is x 1 − x 2 which attains 100% train accuracy and 100% test domain accuracy, and does not satisfy the class-conditional invariant. However, if P (X C |Y ) changes across domains, then we cannot guarantee the same: H(d|x c ) and H(d|Φ, x c ) may not be equal. For building generalizable classifiers in such cases, this example shows that we need an additional constraint on Φ, H(d|x c ) = H(d|Φ, x c ); i.e. domain and representation should be independent conditioned on x c .

An empirical study of class-conditional methods
As a more realistic example, consider the slab dataset introduced for detecting simplicity bias in neural networks (Shah et al., 2020) that contains a feature with spurious correlation. It comprises of two features and a binary label; (x 1 ) has a linear relationship with the label and the other feature (x 2 ) has a piece-wise linear relationship with the label which is a stable relationship. The relationship of the linear feature with the label changes with domains (A.1); we do so by adding noise with probability = 0 for domain 1 and = 0.1 for domain 2. On the third (test) domain, we add noise with probability 1 (see Figure 1(b)). We expect that methods that rely on the spurious feature x 1 would not be able to perform well on the out-of-domain data.
The results in Table 1 (implementation details in Appendix A.1) show that ERM is unable to learn the slab feature, as evident by poor generalization to the target domain, de-spite very good performance on the source domains. We also show that methods based on learning invariant representations by unconditional (DANN, MMD, CORAL) and conditional distribution matching (CDANN, C-MMD, C-CORAL), and matching same-class inputs (Random-Match) (Motiian et al., 2017) fail to learn the stable slab feature. Note that Proposition 1 suggested the failure of conditional distribution matching (CDM) algorithms when the distribution of stable feature (slab feature) is different across the source domains. However, the slab dataset has similar distribution of stable feature (slabs) across the source domains, yet the CDM algorithms fail to generalize to the target domain. It can be explained by considering the spurious linear feature, which can also satisfy the CDM constraint by "shifting" the y-conditional distributions along the linear feature. We conjecture that the model may first learn the linear feature due to its simplicity (Shah et al., 2020), and then retain the spurious linear feature upon further optimization since it satisfies the CDM constraint. This shows that the CDM methods can empirically fail even when there is an equal distribution of stable features across domains.
How can we ensure that a model learns the stable, generalizable feature x 2 ? We turn to our example above, where the required invariant was that the representation Φ(x) should be independent of domain given the stable feature. We apply this intuition and construct a model that enforces that the learnt representation be independent of domain given x 2 . We do so by minimizing the 2 -norm of the representations for data points from different domains that share the same slab value (details of the PerfectMatch method in Section 4.3). The results improve substantially: out-of-domain accuracy is now 78%.
In the next section, we formalize the intuition of conditioning on stable features x c using a causal graph, and introduce the concept of objects that act as proxies of stable features.

Data-generating process
Figure 2(a) shows a structural causal model (SCM) that describes the data-generating process for the domain generalization task. For intuition, consider a task of classifying the type of item or screening an image for a medical condition. Due to human variability or by design (using data augmentation), the data generation process yields variety of images for each class, sometimes multiple views for the same object. Here each view can be considered as a different domain D, the label for item type or medical condition as the class Y , and the image pixels as the features X. Photos of the same item or the same person correspond to a common object variable, denoted by O. To create an image, the data-generating process first samples an object and view  (Ganin et al., 2016), CDANN (Li et al., 2018d), MMD, C-MMD (Li et al., 2018b), CORAL, C-CORAL (Sun & Saenko, 2016) were computed by using their implementations in DomainBed (Gulrajani & Lopez-Paz, 2020).

Method
Source 1    (domain) that may be correlated to each other (shown with dashed arrows). The pixels in the photo are caused by both the object and the view, as shown by the two incoming arrows to X. The object also corresponds to high-level causal features X C that are common to any image of the same object, which in turn are used by humans to label the class Y . We call X C as causal features because they directly cause the class Y .
The above example is typical of a domain generalization problem; a general SCM is shown in Figure 2(b), similar to the graph in (Heinze-Deml & Meinshausen, 2019). In general, the underlying object for each input x (d) i may not be observed. Analogous to the object-dependent (causal) features X C , we introduce a node for domain-dependent high-level features of the object X A . Changing the domain can be seen as an intervention: for each observed x where d = d , such that all correspond to the same object (and thus share the same X C ). For completeness, we also show the true unobserved label of the object which led to its generation as Y true (additional motivation for the causal graph is in Suppl. B.1). Like the object O, Y may be correlated with the domain D. Extending the model in (Heinze-Deml & Meinshausen, 2019), we allow that objects can be correlated with the domain conditioned on Y true . As we shall see, considering the relationship of the object node becomes the key piece for developing the invariant condition. The SCM corresponds to the following nonparametric equations. (d, o, xa) x := gx(xc, xa, x)y := h(xc, y ) where g o , g xc , g xa , g x and h are general non-parametric functions. The error od is correlated with domain d whereas o , xa , x and y are mutually independent error terms that are independent of all other variables. Thus, noise in the class label is independent of domain. Since x c is common to all inputs of the same object, g xc is a deterministic function of o. In addition, the SCM provides conditionalindependence conditions that all data distributions P must satisfy, through the concept of d-separation (Suppl. B.2) and the perfect map assumption (Pearl, 2009).

Identifying the invariance condition
From Figure 2(b), X C is the node that causes Y . Further, by d-separation, the class label is independent of domain conditioned on X C , Y ⊥ ⊥ D|X C . Thus our goal is to learn y as h(x c ) where h : C → Y. The ideal loss-minimizing function f * can be rewritten as (assuming x c is known): Since X C is unobserved, this implies that we need to learn it through a representation function Φ : X → C. Together, h(Φ(x)) leads to the desired classifer f : X → Y.
Negative result on identification. Identification of causal features is a non-trivial problem (Magliacane et al., 2018). We first show that x C is unidentifiable given observed data P (X, Y, D, O) over multiple domains. Given the same probability distribution P (X, Y, D, O), multiple values of X C are possible. Substituting for o in the SCM equations, we obtain, . By choosing g x and h appropriately, different values of g xc (that determine x c from o) can lead to the same observed values for (y, d, o, x). The proof for the following proposition is in Supp. B.4. Proposition 2. Given observed data distribution P (Y, X, D, O) that may also include data obtained from interventions on domain D, multiple values of X C yield exactly the same observational and interventional distributions and hence X c is unidentifiable.

A "perfect-match" invariant
In the absence of identifiability, we proceed to find an invariant that can characterize X c . By the d-separation criterion, we see that X C satisfies two conditions: 1) X C ⊥ ⊥ D|O, 2) X C ⊥ ⊥ O; where O refers to the object variable and D refers to a domain. The first is an invariance condition: X C does not change with different domains for the same object.
To enforce this, we stipulate that the average pairwise distance between Φ(x) for inputs across domains for the same object is 0, Here Ω : X × X → {0, 1} is a matching function that is 1 for pairs of inputs across domains corresponding to the same object, and 0 otherwise. However, just the above invariance will not work: we need the representation to be informative of the object O (otherwise even a constant Φ minimizes the above loss). Therefore, the second condition stipulates that X C should be informative of the object, and hence about Y . We add the standard classification loss, leading to constrained optimization, Here f represents the composition h • Φ. E.g., a neural network with Φ(x) as its rth layer, and h being the rest of the layers.
Note that there can be multiple Φ(x) (e.g., linear transformations) that are equally good for the prediction task. Since x c is unidentifiable, we focus on the set of stable representations that are d-separated from D given O. Being independent of domain given the object, they cannot have any association with X a , the high-level features that directly depend on domain ( Figure 2b). The proof for the next theorem is in Suppl. B.5.
k )) = 0 contains the optimal Φ(x) = X C that minimizes the domain generalization loss in (1). 2. Assuming that P (X a |O, D) < 1 for every high-level feature X a that is directly caused by domain, and for P-admissible loss functions (Miller et al., 1993) whose minimization is conditional expectation (e.g., 2 or crossentropy), a loss-minimizing classifier for the following loss is the true function f * , for some value of λ.

Past work: Learning common representation
Using the SCM, we now compare the proposed invariance condition to domain-invariant and class-conditional domain-invariant objectives. d-separation results show that both these objectives are incorrect: in particular, the classconditional objective Φ(x) ⊥ ⊥ D|Y is not satisfied by X C , (X C ⊥ ⊥ D|Y true ) due to a path through O. Even with infinite data across domains, they will not learn the true X C . The proof is in Suppl. B.6.
Proposition 3. The conditions enforced by domaininvariant (Φ(x) ⊥ ⊥ D) or class-conditional domaininvariant (Φ(x) ⊥ ⊥ D|Y ) methods are not satisfied by the causal representation X C . Thus, without additional assumptions, the set of representations that satisfy any of these conditions does not contain X C , even as n → ∞.

MatchDG: Matching without objects
When object information is available, Eq.
(3) provides a loss objective to build a classifer using causal features. However, object information is not always available, and in many datasets there may not be a perfect "counterfactual" match based on same object across domains. Therefore, we propose a two-phase, iterative contrastive learning method to approximate object matches.
The object-invariant condition from Section 4.2 can be interpreted as matching pairs of inputs from different domains that share the same X C . To approximate it, our goal is to learn a matching Ω : X ×X → {0, 1} such that pairs having Ω(x, x ) = 1 have low difference in x c and x c . We make the following assumption.
j , y) be any two points that belong to the same class, and let (x (d) k y ) be any other point that has a different class label. Then the distance in causal features between x i and x j is smaller than that between x i and x k or x j and x k : c,k ).

Two-phase method with iterative matches
To learn a matching function Ω, we use unsupervised contrastive learning from (Chen et al., 2020;He et al., 2019) and adapt it to construct an iterative MatchDG algorithm that updates the both the representation and matches after each epoch. The algorithm relies on the property that two inputs from the same class have more similar causal features than inputs from different classes.
Contrastive Loss. To find matches, we optimize a contrastive representation learning loss that minimizes distance between same-class inputs from different domains in comparison to inputs from different classes across domains. Adapting the contrastive loss for a single domain (Chen et al., 2020), we consider positive matches as two inputs with the same class but different domains, and negative matches as pairs with different classes. For every positive match pair (x j , x k ), we propose a loss where τ is Iterative matching. Our key insight is to update the positive matches during training. We start training with a random set of positive matches based on the classes, but after every t epochs, we update the positive matches based on the nearest same-class pairs in representation space and iterate until convergence. Hence for each anchor point, starting with an initial set of positive matches, in each epoch a representation is learnt using contrastive learning; after which the positive matches are themselves updated based on the closest same-class data points across domains in the representation. As a result, the method differentiates between data points of the same class instead of treating all of them as a single unit. With iterative updates to the positive matches, the aim is to account for intra-class variance across domains and match data points across domains that are more likely to share the same base object. In Suppl. D.6, we compare the gains due to the proposed iterative matching versus standard contrastive training.
Obtaining the final representation completes Phase I of the algorithm. In Phase II, we use this representation to compute a new match function based on closest same-class pairs and apply Eq. (3) to obtain a classifier regularized on those matches.
The importance of using two phases. We implement MatchDG as a 2-phase method, unlike previous methods (Motiian et al., 2017;Dou et al., 2019) that employed class-based contrastive loss as a regularizer with ERM. This is to avoid the classification loss interfering with the goal of learning an invariant representation across domains (e.g., in datasets where one of the domains has many more samples than others). Therefore, we first learn the match function using only the contrastive loss. Our results in Suppl. D.4 show that the two-phase method provides better overlap with ground-truth perfect matches than optimizing classification and matching simultaneously.
To implement MatchDG we build a p × q data matrix containing q − 1 positive matches for each input and then sample mini-batches from this matrix. The last layer of the contrastive loss network is considered as the learnt representation (see Algorithm 1; details are in Suppl. C.1).

MDG Hybrid
While MatchDG assumes no information about objects, it can be easily augmented to incorporate information about known objects. For example, in computer vision, a standard practice is to augment data by performing rotations, horizontal flips, color jitter, etc. These self-augmentations provide us with access to known objects, which can included as perfect-matches in MatchDG Phase-II by adding another regularizer to the loss from Eq 3. We name this method MDGHybrid and evaluate it alongside MatchDG for datasets where we can perform self augmentations.

Evaluation
We evaluate out-of-domain accuracy of MatchDG on two simulated benchmarks by Piratla et al. (2020), Rotated MNIST and Fashion-MNIST, on PACS dataset (Li et al., 2017), and on a novel Chest X-rays dataset. In addition, using the simulated datasets, we inspect the quality of matches learnt by MatchDG by comparing them to groundtruth object-based matches. For PACS and Chest X-rays, we also implement MDGHybrid that uses augmentations commonly done while training neural networks. We compare to 1) ERM: Standard empirical risk minimization, 2) ERM-RandMatch that implements the loss from Eq.
(3) but with randomly selected matches from the same class (Motiian et al., 2017), 3) other state-of-the-art methods for each dataset. For all matching-based methods, we use the cross-entropy loss for L d and 2 distance for dist in Eq.
(3). Details of implementation and the datasets are in Suppl. C.1. All the numbers are averaged over 3 runs with standard deviation in brackets. , where each rotation angle represents a domain and the task is to predict the class label. Since different domains' images are generated from the same base image (object), there exist perfect matches across domains. Following CSD, we report accuracy on 0 • and 90 • together as the test domain and the rest as the train domains; since these test angles, being extreme, are the hardest to generalize to (standard setting results are in Suppl. D.1, D.2).

Rotated
PACS. This dataset contains total 9991 images from four domains: Photos (P), Art painting (A), Cartoon (C) and Sketch (S). The task is to classify objects over 7 classes. Following (Dou et al., 2019), we train 4 models with each domain as the target using Resnet-18, Resnet-50 and Alexnet.
Chest X-rays. We introduce a harder real-world dataset based on Chest X-ray images from three different sources: NIH ( Model Selection. While using a validation set from the test domain may improve classification accuracy, it goes against the problem motivation of generalization to unseen domains. Hence, we use only data from source domains to construct a validation set (except when explicitly mentioned in Table 4, to compare to past methods that use test domain validation). MatchDG's accuracy lies between ERM-RandMatch and ERM-PerfMatch, indicating the benefit of learning a matching function. As the number of training domains decrease, the gap between MatchDG and baselines is highlighted: with 3 source domains for rotFashionMNIST, MatchDG achieves accuracy of 43.8% whereas the next best method ERM-RandMatch achieves 38.4%.

Rotated MNIST and Fashion MNIST
We also evaluate on a simpler 2-layer LeNet ( Why MatchDG works? We compare the matches returned by MatchDG Phase I (on Resnet-18 network) to the groundtruth perfect matches and find that it has significantly higher overlap than matching based on ERM loss (Table 3). We report three metrics on the representation learnt: percentage of MatchDG matches that are perfect matches, %-age of inputs for which the perfect match is within the top-10 ranked MatchDG matches, and mean rank of perfect matches measured by distance over the MatchDG representation.
On all three metrics, MatchDG finds a representation whose MatchDG vs. IRM on zero training error. Since neural networks often achieve zero training error, we also evaluate the effectiveness of the MatchDG regularization under this regime. Fig. 3 shows the matching loss term as training proceeds for rotMNIST and rotFashionMNIST. Even  after the model achieves zero training error, we see that plain ERM objective is unable to minimize the matching loss (and thus MatchDG penalty is needed). This is because MatchDG regularization depends on comparing the (last layer) representations, and zero training error does not mean that the representations within each class are the same. In contrast, regularizations that are based on comparing loss between training domains such as the IRM penalty can be satisfied by plain ERM as the training error goes to zero where ERM can minimize IRM penalty on Colored MNIST.

PACS dataset
ResNet-18. On the PACS dataset with ResNet-18 architecture (Table 4), our methods are competitive to state-of-the- ResNet-50. We implement MatchDG on Resnet50 model (Table 5) used by the ERM in DomainBed. Adding MatchDG loss regularization improves the accuracy of DomainBed, from 85.7 to 87.5 with MDGHybrid. Also, MDGHybrid performs better than the prior approaches us- ing Resnet50 architecture, except RSC (Huang et al., 2020), whose results (87.83) are close to ours (87.52). Note that we chose a subset of the best-performing baselines for Table 4, 5; an extensive comparison with other works is in Suppl. E.1. Suppl. E.2 gives the results using AlexNet network, and a t-SNE plot ( Figure 5) to show the quality of representation learnt by MatchDG. Table 6 provides results for the Chest X-rays dataset, where the spurious correlation of vertical translation with the class label in source domains may lead the models to learn an unstable relationship. With RSNA as the target domain, ERM obtains 79.8%, 81.8% accuracy on the source domains while its accuracy drops to 55.1% for the target domain. In contrast, MDGHybrid obtain the highest classification accuracy (8 % above ERM), followed by CSD and MatchDG; while methods like ERM and IRM are more susceptible to spurious correlation. However, on ChexPert as the target domain, CSD and IRM do better than ERM while matchingbased methods are not effective. We conjecture these varying trends might be due to the inherent variability in images in the source domains, indicating the challenges of building domain generalization methods for real-world datasets.

Conclusion
We presented a causal view of domain generalization that provides an object-conditional objective. Simple matchingbased methods perform competitively to state-of-the-art methods on PACS, indicating the importance of choosing the right invariance. The proposed MatchDG uses certain assumptions when objects are unknown. More work needs to be done to develop better matching methods, as indicated by the mixed results on the Chest-Xrays dataset.
Ahuja, K., Shanmugam, K., Varshney, K., and Dhurandhar, A. Invariant risk minimization games. arXiv preprint arXiv:2002.04692, 2020. Dataset The synthetic slab dataset (Section 3.2) consists of a binary label y and 2-dimensional features; one feature has a linear relationship with y while the other has a more complex "slab" relationship with y. The features vary in their simplicity, a measure of the simplicity of the feature is given by the number of linear pieces in the optimal classification/decision curve (Figure 1, (Shah et al., 2020)). Hence, the linear features are simpler as they only have 1 linear piece in the optimal decision boundary, as opposed to the slab features that have k linear pieces in the piecewise linear optimal decision boundary.
The synthetic slab dataset was introduced for detecting simplicity bias in neural networks (Shah et al., 2020), to demonstrate that neural networks trained with SGD learn the simpler linear feature as opposed to the slab feature. We extend this dataset for the domain generalization (DG) task, by making the linear block features spurious due to domaindependent noise addition as described below. The effect of the slab feature on y remains the same across domains. Presence of the spurious linear feature should enable an ideal DG algorithm to differentiate it from the stable slab feature, and break the simplicity bias in neural networks. However, the invariance introduced by different DG methods can have a big impact. Using this dataset, we show that the classconditional distribution matching constraint is not sufficient (section 3.2); it is possible to satisfy the constraint using the spurious linear feature too.
The linear block features contain the positive (y=1) and the negative (y=0) labels sampled from uniform distributions U (0.1, 1.0) and U (−1.0, −0.1) respectively. To make the linear features spurious, we add noise to the linear features s.t. data points are sampled from U (−0.1, 0.1) with probability p, and sampled from U (0.1, 1.0) (y=1) or U (−1.0, −0.1) (y=0) with probability 1 − p. The k-slab feature ranges from [-1, 1] and within it has different "slabs" corresponding to uniform distributions of the feature's value, conditioned on class label y. The labels for these slabs alternate between positive (y=1) and negative (y=0) as the numeric value of the slab feature increases. The length for each slab is given by 2−m * (k−1) k where k is the total number of slabs, and m is the margin between two slabs. Model Architecture The overall architecture consists of a representation network along with a classification network, detailed below. Input Dim refers to the input data dimension, which is 2 dimensional (linear block feature, slab block feature). Num Classes refers to the total number of output classes, which is binary classification for the synthetic slab dataset. We refer a fully connected dense layer by FC layer, with the input and output dimensions for that layer in brackets.

Classification Network
• FC layer: (100, 100)  For RandMatch (Motiian et al., 2017) and PerfMatch, we use l 2 distance for dist in (Eq: 3). The match function Ω in the RandMatch algorithm is defined as randomly matching any two data points across domains with the same class label. For the PerfMatch algorithm, the match function Ω accepts two data points across domains with the same slab id as valid matches (the slab id corresponds to the value of the causal feature: two inputs with the same slab id have similar causal features).
Note on method selection Our objective with the synthetic slab dataset is to compare the performance of conditional distribution matching (CDM) methods to that of Hyperparameter Tuning All the methods were trained using SGD, with batch size 128, learning rate 0.1 and weight decay 5e-4. We train each method for 100 epochs and do early stopping based on the validation loss.
Further details regarding the tuning of hyperparameters specific to each method's regularization technique are provided in Table 7. The loss objective of all the methods can be written as ERM + λ*Regularization Penalty; and we provide the optimal values and grid range for the hyperparam λ in Table 7. Also, some methods like DANN, C-DANN have additional hyperparams, which are specified in the same table. The grid search range for methods that were implemented using DomainBed (Gulrajani & Lopez-Paz, 2020) is taken from the Table 8 in the DomainBed paper.
A.2. Simple counter-example and its relationship to the MatchDG assumption.
The MatchDG method depends on Assumption 1 (Section 5) which requires that same-class inputs across domains are closer in causal features than different-class inputs. Note that the example in Section 3.1 does not satisfy this assumption. However, there exist many variations of the setup that do follow the MatchDG assumption, and still classconditional methods cannot recover the true causal feature. For instance, by setting |x c | = |x c | + κ where κ > 1.5 and α 1 = κ + 1, α 2 = κ + 2 for domain 1 and domain 2 respectively, the train domains satisfy the MatchDG assumption.
Overall, the goal of the simple example in Section 3.1 is to show that there exist datasets where class-conditional methods would not work, but Perfect-Match does. MatchDG's assumption works in a subset of these datasets. In future work, matching-based methods can be developed that relax the MatchDG assumption. Given these differences, we construct a causal graph ( Figure  2) that includes both Y true and Y (as in (Heinze-Deml & Meinshausen, 2019)), and is consistent with both viewpoints about the direction of the causal mechanism. Importantly, all d-separation results reported in the main text hold true irrespective of whether we choose Y or Y true as the class label. We use Y as the label in the main text, since it corresponds to many settings where the observed class label is a result of a (possibly noisy) manual labelling process.
In addition, we chose to represent X C and X A as near-tofinal features, that are combined using a simple operation to generate the observed features X. Under this representation, the object O does cause X A ; X A is produced by combination of the domain and the object. Another equally valid construction is to assume that X A contains only the domain information, and a more complex operation generates the observed features using X C (object information) and X A . The corresponding causal graph will omit the edge from object O to X A . Both these graphs are allowed by our framework. All d-separation results reported in the main text hold true irrespective of whether there exists an edge from O to X A .

B.2. D-separation
We first expand on the d-separation definition, providing a few examples that illustrate conditional independence implications of specific graph structures in Figure 4. We use these three conditions for the proofs below. . Causal graphs with the node C as a chain, fork, or a collider. By the d-separation criteria, A and B are conditionally independent given C in (a) and (b). In (c) however, A and B are independent but become conditionally dependent given C.
Definition 1. d-separation (Pearl, 2009): Let A,B,C be the three non-intersecting subsets of nodes in a causal graph G. For any path between two nodes, a collider is a node where arrows of the path meet head-to-head. A path from A to B is said to be blocked by C if either a non-collider on the path is in C, or there is a collider on the path and neither the collider nor its descendants are in C.
If all paths from A to B are blocked, then A is d-separated from B by C: dsep(A, B, C) ⇒ A ⊥ ⊥ B|C.

B.3. Proof of Proposition 1
Proposition 1 relates to the domain generalization setup, as described in Section 3.1, where the causal feature determines y label without any noise. The distribution of the non-causal feature varies across domains. The proof uses the entropy formulation of distribution-matching methods, as done by Akuzawa et al. (2019). Proposition 1. Under the domain generalization setup as above, if P (X c |Y ) remains the same across domains where x c is the stable feature, then the class-conditional domaininvariant objective for learning representations yields a generalizable classifier such that the learnt representation Φ(x) is independent of the domain given x c . Specifically, the entropy H(d|x c ) = H(d|Φ, x c ).
Proof. We can write class-conditional invariant models as optimizing two objectives: minimize the error on the training data (ERM objective), and learn a representation Φ(x) that is independent of domain given the class label (classconditional invariant).
Let us focus on the second objective, which be interpreted as 2) maximizing the entropy of domain given class label and representation H(d|y, Φ(x)). Let Φ 2 be the optimal representation for the class-conditional invariant. We can write, Since H(d|y, Φ(x)) ≤ H(d|y) using the property of entropy, the optimal Φ 2 satisfies, Now two cases arise; x c ⊥ ⊥ D|Y or x c ⊥ ⊥ D|Y . We assume the former. If X C is independent of domain conditioned on the class label, then Here domain d is independent of both x c and Φ 2 (x), conditional on y. Since causal features x c cannot be caused by the representation Φ 2 (x), it cannot be a collider (Definition 1) in any graph connecting d, x c and Φ 2 (x). Therefore, conditioning on it does not remove the independence between d and Φ 2 (x)|y (conditioned on y). Hence, we condition on Eq 6 with x c and obtain, Plugging it into the above equations, we obtain Also since there is no label noise, x c can achieve zero error for predicting the label y. That is, x c contains all information about y, and thus we can remove y from the above equation, This implies that the learnt representation Φ 2 (x) is independent of the domain given x c ; thus Φ 2 (x) depends on x c and not on any other feature that changes with domain.

B.3.1. REMARKS BASED ON PROPOSITION 1
If x c is not independent of domain given class label. However, if X C is not independent of domain given the class label (i.e., P (x c |y) changes across domains), then H(d|y) > H(d|y, x c ). Using the equality from Eq 8, we obtain, After removing y as in Eq. 10, H(d|x c ) and H(d|Φ 2 , x c ) may not be equal. In particular, the ground-truth representation Φ GT (x) = x c does not satisfy the class-conditional invariant: H(d|y, Φ GT (x)) = H(d|y, x c ) = H(d|y).
Hence, to learn x c as the representation, we need a separate constraint, H(d|x c ) = H(d|Φ, x c ); i.e. domain and representation should be independent conditioned on x c .
Implications for the slab dataset (Section 3.2). In the slab dataset, x c = x 2 and x 2 is independent of the domain given the class label (X 2 ⊥ ⊥ D|Y ). We also see that Φ(x) = x 2 satisfies the class-conditional invariant: H(d|y, x 2 ) = H(d|y) since X 2 ⊥ ⊥ D|Y . By Proposition 1, the classconditional invariant should lead to a representation that satisfies H(d|x c ) = H(d|Φ(x), x c ). However, the same constraint can also be achieved by setting Φ(x) = x 1 by shifting the distribution of x 1 slightly. And since there is a simple, linear correlation between x 1 and the class label y, empirically class-conditional methods end up learning a representation dependent on x 1 .

B.4. Proof of Proposition 2
Proposition 2. Given observed data distribution P (Y, X, D, O) that may also include data obtained from interventions on domain D, multiple values of X C yield exactly the same observational and interventional distributions and hence X c is unidentifiable.
Proof. To prove non-identifiability, it is sufficient to show a counter-example where the same structural equations (and hence same observed and interventional distributions over Y, X, D, O) correspond to two different values of X C .
From Section 4.1, the SCM leads to the following structural equations, Substituting for x c in the SCM equations, we obtain, Given a value of object variable o, note that g xc determines x c . We now proceed to show that different values of g xc are possible given the same structural equations between the observed variables Y, X, D, O. Specifically, by choosing g x and h appropriately, different values of g xc can lead to the same observed values for (y, d, o, x).
A simple counter-example. Suppose the following SCM equations, Introducing h * = h • g xc and g * 1 = g 1 • g xc , we can rewrite the above equations as, then any g xc is applicable as long as we set h such that h(g xc )(o) = h * (o) and set g 1 such that g 1 (g xc (o)) = g * 1 (o). In particular, if the SCM equations are y = o, x = o + o * d, and we define h = g 1 = g −1 xc , then g xc can be any invertible function. Hence, different values of x c = g xc (o) will lead to the same structural equations over Y, X, D, O, and therefore the same observed and interventional distributions.
k )) = 0 contains the optimal Φ(x) = X C that minimizes the domain generalization loss in (1). 2. Assuming that P (X a |O, D) < 1 for every high-level feature X a that is directly caused by domain, and for P-admissible loss functions (Miller et al., 1993) whose minimization is conditional expectation (e.g., 2 or crossentropy), a loss-minimizing classifier for the following loss is the true function f * , for some value of λ.
Proof. CLAIM 1. The matching condition can be written as: where Ω(j, k) = 1 for pairs of inputs x j and x k from two different domains d and d that correspond to the same object. The distance metric dist is non-negative, so the optimal Φ is when C(Φ) is zero. As in the SCM from Figure 2(b), let X c represent a feature vector such that it is generated based only on the object O and that it leads to the optimal classifier in (1). From Sections 4.1 and 4.2, we know that X c ⊥ ⊥ D|O and that x c = g xc (o). Thus, x c is the same for inputs from the same object and we can write: Hence, Φ(x) = x c leads to zero regularizer term and is one of the optimal minimizers for C(Φ).
CLAIM 2. Further, we show that any other optimal Φ is either a function of x c or a constant for all inputs. We prove by contradiction.
Let X A represent the set of unobserved high-level features that are generated based on both the object O and the domain D. From the SCM from Figure 2(b), a feature vector X a ⊆ X A is independent of X c given the object, X a ⊥ ⊥ X c |O, and x a = g xa (d, o, xa ). Further, let there be an optimal Φ a (x) for C(Φ) such that it depends on some X a ⊆ X A (and is not trivially a constant function). Since Φ a is optimal, k ) for all d, d such that Ω(j, k) = 1, where inputs x j and x k correspond to the same object. ). Due to domain-dependent variation, with nonzero probability, the high-level X a features are not the same for these two input data points, x (d) a,i . Since Φ is a deterministic function of x that is not independent of X a , if an input x has a different X a , its value of Φ(x) will also be different. Thus, with non-zero probability, we obtain that ), unless the effect of X a is a constant function. Hence, a contradiction and optimal Φ cannot depend on any X a ⊆ X A that are generated based on the domain.
Therefore, an optimal solution to C(Φ) can only depend on X c . However, any function of X c is optimal, including trivial functions like the constant function (that will have low accuracy). Below we show that using the ERM term in (3) ensures that the optimal solution contains only those functions of X C that also maximize accuracy.
Using (2), the empirical optimizer function can be written as (where we scale the loss by a constant n = d n d , the total number of training data points): where ψ(X c ) denotes all functions of X c that are optimal for (15), and the last equality is because h • ψ can be written as f = h • ψ. Since we assume that L is a P-admissible loss function, its minimizer is the conditional expected value. Thus, for any domain d, arg min f lim n d →∞ The above equation indicates that the loss minimizer function on any domain is independent of the domain. Thus, for the m training domains, we can write: Now (19) can be rewritten as, From the equation above, the loss forf pmatch can be considered as a weighted sum of the average loss on each training domain where the weights are all positive. Since E[Y |X c ] minimizes the average loss on each domain as n d → ∞, it will also minimize the overall weighted loss for all values of the weights. Therefore, for any dataset over m domains in D m , E[Y |X c ] is the optimal function that minimizes the overall loss.
Moreover, we can also write f * as: where we utilize (20) and that the loss function is Padmissible. Hence, f * = E[Y |X c ] is the loss-miniziming function for the loss in (19).
Finally, using a Lagrangian multiplier, minimizing the following soft constraint loss is equivalent to minimizing (18), for some value of λ.
The result follows.
Comment on Theorem 1. In the case where the effect of a domain is also deterministic, it is possible that P (X a |O, D) = 1 (e.g., in artificially created domains like Rotated-MNIST where every object is rotated by the exact same amount in each domain). In that case Theorem 1 does not apply and it is possible to learn a representation Φ a that depends on X a ⊆ X A and still minimizes C(Φ) to attain C(Φ) = 0. For example, with two training domains on Rotated-MNIST dataset (0 • , α • ), it is possible to learn a representation that simply memorizes to "un-rotate " the α angle back to 0 • . Such a representation will fail to generalize to domains with different rotation angles, but nonetheless minimizes C(Φ) by attaining the exact same representation for each object.
In practice, we conjecture that such undesirable Φ a are avoided by model-size regularization during training. As the number of domains increase, it may be simpler to learn a single transformation (representation) based on X c (and independent of X c features like angle) than learn separate angle-wise transformations for each train domain. Class-conditional domain-invariant.
(Φ(x) ⊥ ⊥ D|Y .) (Li et al., 2018c;Ghifary et al., 2016;Li et al., 2018d) Even in the ideal case where we observe Y true , d-separation on the SCM reveals that X C ⊥ ⊥ D|Y true due to a path through O. Thus, having the same distribution per class is not consistent with properties of X C .
Below we prove these results formally.
Proposition 3. The conditions enforced by domaininvariant (Φ(x) ⊥ ⊥ D) or class-conditional domaininvariant (Φ(x) ⊥ ⊥ D|Y ) methods are not satisfied by the causal representation X C . Thus, without additional assumptions, the set of representations that satisfy any of these conditions does not contain X C , even as n → ∞.
Proof. As in the SCM from Figure 2(b), let X c represent an unobserved high-level feature vector such that it is generated based only on the object O and that it leads to the optimal classifier in (1). From Sections 4.1 and 4.2, we know that X c ⊥ ⊥ D|O and that x c = g xc (o). Following a similar proof to Theorem 1 (Claim 1), we check whether Φ(x) = x c satisfies the invariance conditions required by the two methods.
1. Domain-invariant: The required condition for a representation is that Φ DI (x) ⊥ ⊥ D. But using the dseparation criteria on the SCM in Figure 2(b), we find that X c ⊥ ⊥ D due to a path through Object O.

Class-conditional domain-invariant:
The required condition for a representation is that Φ CDI ⊥ ⊥ D|Y . However using the d-separation criteria on the SCM, we find that X c ⊥ ⊥ D|Y due to a path through Object O that is not blocked by Y (nor by Y true if it is observed).
Therefore, under the conditions proposed by these methods, X c or any function of X c is not an optimal solution without making any additional assumptions. Hence, even with infinite samples, a method optimizing for these conditions will not retrieve X c .

C. Evaluation and implementation details
In this section we describe implementation details for our proposed methods. We also discuss the evaluation protocol, including details about hyperparameters and crossvalidation.

C.1. Implementation details
For the implementation of ERM-PerfMatch in Eq.
(3); we use the cross-entropy loss for L d and l 2 distance for dist in Eq. (3). Similarly, we implement the ERM-RandMatch with a match function Ω in Eq.
(3) that randomly matches data points across domains with the same class, For both methods, we consider the representation Φ(x) to be the last layer of the network. That is, we take h to be identity function in Eq. (3) for simplicity. It is also possible to use the second-last or any other previous layer as a representation, but the last layer performed well in our experiments.
Also, given a fixed data point, the match function Ω could select multiple data points as potential matches for it. In this case we use Eq. (3) with stochastic matching, where we randomly select one match out of the potential multiple matches.
We use SGD to optimize the loss for all the datasets, with details about learning rate, epochs, batch size, weight decay etc. provided in the section C.3 ahead. For all the different methods, we sample batches from the data matrix consisting of data points matched across domains; hence we ensure an equal number of data points from each source domain in a batch. When training with MatchDG, the underlying architecture for Phase 2 is kept the same for ERM, RandMatch, PerfMatch for the respective task; with the details mentioned below for each dataset. The details for the Phase-1 architecture are specified in section C.3, Table 9. We sample 1000 data points for each domain and evaluate using the LeNet architecture (Table 11) as per the setup proposed by (Motiian et al., 2017). Similarly, we sample all the 70,000 images in MNIST and evaluate using the custom architecture (Table 12)  Finally, for all the different setups proposed above, we create an additional validation set for each domain with 20% percent size as of the training set for that domain. We use the validation set from the source domains for hyper parameter tuning.
PACS. This dataset contains total 9991 images from four domains: Photos (P), Art painting (A), Cartoon (C) and Sketch (S). The task is to classify objects over 7 classes. Following (Dou et al., 2019), we train 4 models with each domain as the target using Resnet-18 (Table 4), Resnet-50 (Table 5) and Alexnet (Table 18), with each architecture pre-trained on ImageNet. We also the following data augmentations (Gulrajani & Lopez-Paz, 2020) while training: Random Crop, Horizontal Flip, Color Jitter, and Random Gray Scale.
Chest X-ray. We use Chest X-rays images from three dif- ). This leads to a downward shift in the position of lungs in the images for the class 0 as compared to those for class 1, which could lead to models utilizing this spurious relative difference in position of lungs for the classifications task.
C.1.1. MATCHDG IMPLEMENTATION DETAILS: The MatchDG algorithm proceeds in two phases. Initialization: We construct matches of pairs of same-class data points from different domains. Hence, given each data point we randomly select another data point with the same class from another domain. The matching for each class across domains is done relative to a base domain; which is chosen by taking the domain that has the highest number of samples for that class. This is done to avoid missing out on data points when there is class imbalance across domains. Specifically, we iterate over classes and for each class, we match data points randomly across domains w.r.t a base domain for that class. This leads to matrix M of size (N , K), where N refers to the updated domain size ( sum of the size of base domain for all the classes ) and K refers to the total number of domains. We describe the two phases below: Phase 1: We samples batches (B, K) from the matched data matrix M, where B is the batch size. For each data point x i in the batch, we minimize the contrastive loss from (4) by selecting its matched data points across domains as the positive matches and consider every data point with a different class label from x i to be a negative match.
After every t epochs, we periodically update the matched data matrix by using the representations learnt by contrastive loss minimization. We follow the same procedure of selecting a base domain for each class, but instead of randomly matching data points across domains, we find the nearest neighbour for the data point in base domain among the data points in the other domains with the same class label based on the l 2 distance between their representations.
At the end of Phase I, we update the matched data matrix based on l 2 distance over the final representations learnt. We call these matches as the inferred matches.
Phase 2: We train using the loss from Eq. (3), with the match function Ω based on the inferred matches generated from Phase 1 (ERM + Inferred Match). We train the network from scratch in Phase 2 and use the representations learnt in Phase 1 to only update the matched data matrix.
The updated data matrix based on representations learnt in Phase 1 may lead to many-to-one matches from the base domain to the other domains. This can lead to certain data points being excluded from the training batches. Therefore, we construct batches such that each batch consists of two parts. The first is sampled as in Phase 1 from the matched data matrix. The second part is sampled randomly from all train domains. Specifically, for each batch (B, K) sampled from the matched data matrix, we sample an additional part of size B with data points selected randomly across domains. The loss for the second part of the batch is simply ERM, along with ERM + InferredMatch Loss on the first part of the batch.

C.2. Metrics for evaluating quality of learnt matches
Here we describe the three metrics used for measuring overlap of the learnt matches with ground-truth "perfect"  0,5,15,20] matches.
Overlap %: Percentage of matches (j, k) as per the perfect match strategy Ω that are also consistent with the learnt match strategy Ω .
Top-10 Overlap %: Percentage of matches (j, k) as per the perfect match strategy Ω that are among the Top-10 matches for the data point j w.r.t the learnt match strategy Ω i.e. S 10 Ω (j) Mean Rank: For the matches (j, k) as per the perfect match strategy Ω, compute the mean rank for the data point j w.r.t the learnt match strategy Ω i.e. S Ω (j)

C.3. HyperParameter Tuning
To select hyperparameters, prior works (Dou et al., 2019;Carlucci et al., 2019;Li et al., 2018a) use leave-one-domainout validation, which means that the hyperparameters are tuned after looking at data from the unseen domain. Such a setup is violates the premise of the domain generalization task that assumes that a model should have no access to the test domain. Therefore, in this work, we construct a validation set using only the source domains and use it for hyper parameter tuning. In the case of PACS, we already have access to the validation indices for each domain and use them to construct a validation set based on the source domains. For Rotated & Fashion MINST, Chest X-ray datasets, we create validation set for each source domain as described in the section B.1 above. Hence, the model does not have Table 9. MatchDG Phase 1 training details for all the datasets.We did not do hyper parameter tuning as we did for other methods, hence we mention the default value for each hyper parameter that we used. Please note we still did early stopping, the Total Epochs in the table reflects the max budget for training. The specific archiecture used for Phase 1 training is also mentioned for each dataset.

Dataset
Hyper  (Table 2), LeNet (Table 11), Custom CNN (Table 12) PACS We perform a grid search over pre-defined values for each hyper parameter and report the optimal values along with the values used for grid search in Table 8. Further, we do early stopping based on the validation accuracy on source domains and use the models which obtain the best validation accuracy.
For the case of MatchDG Phase-1, we do not perform grid search and use default values for each hyper parameter (Table 9). We still do early stopping for MatchDG Phase-1, based on the metric Top-10 Overlap (Section B.2) over the validation set of source domains. Since we require perfect matches for the evaluation of the metric Top-10 Overlap, we create prefect matches using the self augmentations (Section B.1) for each dataset.

C.4. Reproducing Results from Prior Work
MNIST and Fashion MNIST The results for MASF, CSD, and IRM in Table 2 were computed using their code which is available online 123 . The MASF code was hardcoded to run for PACS dataset; which has 3 source domains that gets divided into 2 meta train and 1 meta test domain. Their code requires atleast 2 meta train domains; which leads to an issue for only 2 source domains (30, 45). In Table 2  The results for prior approaches in Table 11 are taken from (Shankar et al., 2018), (Ilse et al., 2020). For the results using DomainBed setup in Table 12, the results for prior approaches are taken from (Gulrajani & Lopez-Paz, 2020).
PACS We did not generate results for the prior approaches for PACS by developing or using existing implementations. All the results for the prior approaches on PACS were taken from the respective papers as specified in the Table 17, 18.
Chest X-ray The results for the prior approaches CSD, IRM were generated using the implementations of both of the methods available on github 1,3 .

D. Additional Evaluation on Rotated MNIST and Fashion-MNIST
Here we present results for additional experiments on Rotated MNIST and Fashion-MNIST datasets using MatchDG.
D.1. Comparing MatchDG with prior work on the LeNet Network

D.3. Accuracy Results using a fraction of perfect matches
To show the importance of learning a good match function, we present the results of approaches with match function capturing some fixed percentage of perfect matches in the Table 13. For both Rotated & Fashion MNIST, we observe that the approaches that contain a higher proportion of perfect matches perform better in terms of accuracy on target domains. Hence, the quality of the match function leads to monotonic effect on the generalization performance of the matching approaches.

D.4. Quality of representation learnt in the classification phase
In addition to Table 3 that shows metrics for Phase 1 of MatchDG, we compute the metrics for the classification phase (Phase 2) of MatchDG. Specifically, we compute the Overlap, Top-10 overlap and the Mean Rank metrics (Section C.2) for matched pairs of inputs based on the representation learnt at the end of the classification phase.     We compute the metric for the default instantiation of Phase 1 of MatchDG initialized with random matches and compare it to an oracle version of MatchDG initialized with perfect matches. In addition, we compare the metrics for matches generated using baseline ERM (last layer of the network) in order to understand its effectiveness as a matching strategy in Phase 1. Table 15 shows the metrics for Phase 1 of MatchDG with 2K images from the Fashion-MNIST dataset, and reproduces the metrics for the 10K dataset from Table 3 for ease of comparison. We observe that the mean rank of perfect matches improves for the smaller dataset. Similarly, the overlap and top-10 overlap also increase for

D.6. Iterative updating of matches in Phase-1 of MatchDG
In Section 5.1, we proposed Phase 1 of the MatchDG algorithm with iterative updates to the computed matches. Here we compare the quality of matches learnt at the end of Phase 1 with or without using the iterative updating. Without the iterative updates, the matches always remain the same as the random matches with which the algorithm was initialized. Table 16 shows metrics computed at the end of Phase 1 of MatchDG using both an iterative approach vs. a noniterative approach. The iterative approach provides a 2× improvement on the overlap with perfect matches for rotated MNIST and Fashion-MNIST datasets. Since higher overlap in the inferred matches results in better classification accuracy in Phase 2 (as shown in Table 13), we conclude that using the iterative approach improves the domain generalization capability of MatchDG.   Huang et al., 2020). However, as stated in the main paper, DDEC (Asadi et al., 2019) rely on data from additional source like Behance BAM! dataset and we are also not sure about the validation mechanism used by them. If the validation mechanism used by them includes data from the target domain during validation, then MatchDG (Test), MDGHybrid (Test) obtain better accuracy than them.

E.2. AlexNet Results
Finally, we compare RandMatch and MatchDG to prior work on generalization accuracy for the PACS dataset using the AlexNet architecture. As in Table 17, the task is to generalize to a test domain after training on the remaining three domains.
For all test domains, Table 18 shows that both RandMatch and MatchDG outperform the baseline ERM method. Averaging over the test domains, MDGHybrid provides improvement over MatchDG ( (Table 17), we speculate that MatchDG requires a powerful underlying network architecture to use matches effectively for classification.

E.3. T-SNE Plots
Beyond accuracy, we investigate the quality of representations learnt by MatchDG using t-SNE (Maaten & Hinton, 2008) in Figure 5. Comparing the Phase I models for the easiest (Photo) and hardest (Sketch) unseen domains (Figs. 5a,b), we find that MatchDG achieves a higher overlap between train and test domains for Photo than Sketch, highlighting the difficulty of generalizing to the Sketch domain, even as classes are well-separated in the training domains for both models (Figs. 5c,d).