Lost Domain Generalization Is a Natural Consequence of Lack of Training Domains
Authors: Yimu Wang
Hongyang Zhang
Venue: Submitted to ICLR 2023 (2023)
Keywords: Domain Generalization
Domain Complexity

Abstract: We show a hardness result for the number of training domains required to achieve a small population error in the test domain. Although many domain generalization algorithms have been developed under various domain-invariance assumptions, there is significant evidence to indicate that out-of-distribution (o.o.d.) test accuracy of state-of-the-art o.o.d. algorithms is on par with empirical risk minimization and random guess on the domain generalization benchmarks such as DomainBed. In this work, we analyze its cause and attribute the lost domain generalization to the lack of training domains. We show that, in a minimax lower bound fashion, \emph{any} learning algorithm that outputs a classifier with an $\epsilon$ excess error to the Bayes optimal classifier requires at least $\mathrm{poly}(1/\epsilon)$ number of training domains, even though the number of training data sampled from each training domain is large. Experiments on the DomainBed benchmark demonstrate that o.o.d. test accuracy is monotonically increasing as the number of training domains increases. Our result sheds light on the intrinsic hardness of domain generalization and suggests benchmarking o.o.d. algorithms by the datasets with a sufficient number of training domains.

Under review as a conference paper at ICLR 2023
LOST DOMAIN GENERALIZATION IS A NATURAL CON- SEQUENCE OF LACK OF TRAINING DOMAINS
Anonymous authors Paper under double-blind review
ABSTRACT
We show hardness result for the number of training domains required to achieve small population error the test domain. Although many domain generalization algorithms have been developed under various there is significant evidence to indicate that out-of-distribution (o.o.d.) test accuracy of sfte-offtheearr o.o.d. algorithms is on par with empirical risk minimization and random guess on the domain generalization benchmarks such as DomainBed. In this work, analyze its cause and attribute the lost domain generalization the lack of training domains. We show that, in a minimax lower bound fashion, any learning algorithm that outputs classifier with excess error to the Bayes optimal classifier requires at least poly(1/c) number of training domains, even though the number of training data sampled from each training domain is large. Experiments on the DomainBed benchmark demonstrate that 0.0.d. test accuracy is monotonically increasing as the number of training domains increases. Our result sheds light on the intrinsic hardness of domain generalization and suggests benchmarking o.o.d. algorithms by the datasets with sufficient number of training domains.
assumptions,
INTRODUCTION
Domain generalization (Mahajan et al., 2021; Dou et al., 2019; Yang et al., 2021; Bui et al., 2021;
Robey et al., 2021: Wald et al.. 2021: Recht et al., 2019)-where the training distribution different from the test distribution has been a central research topic in machine learning (Blanchard et al., 2021; Chuang al., 2020; Zhou et al., 2021), computer vision (Piratla et al., 2020; Gan et al., 2016; Huang et al., 2021; Song et al., 2019; Taori et al., 2020), and natural language processing (Wang et al., 2021; Fried et al., 2019). machine learning. the study of domain generalization has led significant advances in the development of new algorithms for out-of-distributio (o.o.d.) generalization (Li et al., 2022b; Bitterwolf et al., 2022: Thulasidasan et al., 2021). In computer vision and natural language processing. new benchmarks such DomainBed (Gulrajani & Lopez-Paz, 2021) and WILDs (Koh et al., 2021; Sagawa et al., 2021) are built toward closing the gap between the developed methodology and real-world deployment. In both cases, the problem can be stated as given set of training domains |._ which are drawn from a domain distribution P and given a set of training data {(x,, )f which are drawn from Pe. the goal is to develop an algorithm based on the training data and their domain labels so that the algorithm in expectation performs well on the unseen test domains drawn from P.
Despite progress on the domain generalization, many fundamental questions remain unresolved. For example, in search of lost domain generalization, Gulrajani & Lopez-Paz (2021) conducted extensive experiments using DomainBed and found that, when carefully implemented, empirical risk minimization (ERM) shows state-of-the-an performance across all datasets despite many algorithms are carefully designed for the out-of-distribun on the "+90%" and "+80%" domains of the ColoredMNIST dataset (Arjovsky et al., 2019) and is tested on the "-90%" domain, the best-known o.o.d. algorithm achieves test accuracy no better than a random- guess algorithm under all three model selection methods in Gulrajani & Lopez-Paz (2021). Thus, it is natural to ask what causes the lost domain generalization and how to find it?
tasks. For example, when the algorithm is trained
'The number refers to the degree of correlation between color and label.

---

Under review as a conference paper at ICLR 2023
Table 1: The number of domains in the o.o.d. benchmarks WILDs (Koh et al., 2021: Sagawa et al., 2021) and DomainBed (Gulrajani & Lopez-Paz, 2021). It shows that most of the datasets in the two benchmarks suffer from small number of domains, which might not be sufficient learn classifier with good domain generalization.
WILDS
WWidCam
Camelyoo17
RaRx
OGB-MaIPCRA
BlobalWieat
CielConmmnns
FMol
Powarty
Amsroc
151
domains
120,084
2,586
8,421
DanainRed
CMNIST
RMNIST
VLCs
PACS
Officx-Home
Torm Incogoita
DomainNel
domains.
In this paper, we attribute the lost domain generalization to the lack of training domains. Our study is motivated by an observation that off-the-shelf benchmarks often suffer from few training domains. For example, the number of training domains in DomainBed (Gulrajani & Lopez-Paz, 2021) 1) for all its 7 datasets is at most 6; in WILDs (Koh et al., 2021; Sagawa et al., 2021). 7 out of 10 datasets have the number of training domains fewer than 350 (see Table 1). Therefore, one may conjecture that increasing the number of training domains might improve the empirical performance of existing domain generalization algorithms significantly. In this paper, we show that, information theoretically, one requires at least poly(1/22) number of training domains in order to achieve small excess error for any learning algorithm. This is in sharp contrast to many existing benchmarks in which the number of training domains is limited.
RELATED WORK
Out-of-distribution (o.o.d) generalization (Hendrycks & Dietterich, 2019; Shankar et al., 2018; Zhou et al., 2021) has received extensive attention in recent years. One representative way is the causal modelling inspired by Invariant Risk Minimization (IRM) (Arjovsky et al., 2019). IRM tries to learn an invariant feature representation to capture the underlying causal mechanism of interest across domains such that the classifier based on this invariant feature representation shall be invariant across all domains. Given multiple training domains, IRM learns invariant representations approximately by adding a regularization. The results of IRM indicate that failing to generalize to o.o.d. data comes from failing to capture the causal factors of variation in different domains. Following IRM, Risk Extrapolation (REx) (Krueger et al., 2021) proposes to reduce differences in risk across training domains. Derivative Invariant Risk Minimization (DIRM) (Bellot & van der Schaar, 2020) maintains the invariance of the gradient of training risks across different domains.
Another line of research uses different metrics to tackle the o.o.d problem. For example, Maximum Mean searepancy-Adversaaaee
AutoEncoder (Li et al., 2018b) employs Generative Adversarial Networks and the maximum mean discrepancy metric (Gretton et al., 2012) to align different feature distributions. Mixture of Multiple Latent Domains (Matsuura & Harada, 2020) learns domain- invariant features by clustering techniques without knowing which domain the training samples belong to. Recently, Meta-Learning Domain generalization (Li et al., 2020) employs a lifelong learning method tackle the sequential problem of new incoming domains.
To explore the o.o.d problem, one line of research focuses on the case where only one training domain is accessible. Causal Semantic Generative model (CSG) (Liu al., 2021) uses two sets of correlated latent variables, i.e., the semantic and non-semantic features, to model the relation between the data and the corresponding labels. In their assumption, the semantic features relate the data to their corresponding labels while the non- non-semaatic features only affect the generation of data. CSG decouples the semantic and non-semantic features improve o.o.d generalization given only one training domain.
However, recent work (Gulrajani Lopez-Paz, 2021) claims that all existing algorithms cannot capture the true invariant feature and observes that their performance is par with ERM and random guess on several datasets. In this paper, to explain why it occurs, we theoretically analyze the o.o.d. generalization problem and provide minimax lower bound for the number of training domains required to achieve a small population error in the test domain. Massart & Nédélec (2006a) have proved that it requires at least 22(1/²2) samples from distribution estimate the success probability of a Bernoulli variable with an e error. Motivated by this, we observe a similar phenomenon and prove that the learning algorithms need at least 2(1/62) number of training domains. Recently,
2

---

Under review as a conference paper at ICLR 2023
concurrent work (Li et al., 2022a) presents upper bound on the expected excess error of the ERM algorithm using the Rademacher complexity. Similarly, another work (Blanchard et al., 2021) gives an upper bound on the excess enror of general learning algorithms with high probability and shows that the sample size of each domain is inversely proportional to the excess error. On the other side, while previous work (Li al., 2022a; Blanchard al., 2021) showed positive results the domain generalization, we present a negative result (i.e., a lower bound regarding the number of training domains) on the expected excess error for all possible learning algorithms.
MINIMAX LOWER BOUND FOR DOMAIN GENERALIZATION
In this section, we provide minimax lower bound for domain generalization. Our results lower bound the number of training domains required for good o.o.d. generalization.
Notation. We will use bold capital letters such X represent a random vector, bold lower-case letters such as X to represent the implementation of random vector, capital letters such as Y to represent a random variable, and lower-case letters such as y to represent the implementation of random variable. Specifically, we denote by X the random vector of instance, denote by the implementation of random vector X, denote by Y the random variable of label, and denote by y E {0, } the implementation of random variable Y. We will use L(f) to represent the expected 0-1 loss of classifier w.r.t. the mixture data distributions of all domains, i.e., L(f) = Pr Throughout the paper, will frequently use P to represent the distribution of distribution, i.e., the domain distribution, will use Pe to represent the data distribution of the e-th domain, and will use (x", y²) to represent the data sampled from the e-th domain Pa. We call f1,2,3.... the domain labels, which are accessible to the learner.
+ Y).
Problem setups. In hard instance, view the e-th domain data distribution P. given by Pr(X, YJB, = b,), where e is the domain label and B 's represent i.i.d. Bernoulli random vectors that parameterize the data distribution of the e-th domain. In this paper, we will regard Pr(X, Y Y|B,) and Pr(X, Y Y|B.g) as two different domains as long as ei j 62. We assume that each domain is sampled from a domain distribution P (i.e., the distribution of Bz), and the data in the e-th domain are sampled from a data distribution Pe given by Pr(X, Y YBB = ). Let f be the Bayes optimal classifier of the mixture of data distributions across all domains, and assume f F, where F can be any function class such deep neural networks. For any h E [0, 1], we define class of domain distributions by P(h, == (P | Pr
- 2 h]. Note that the margin parameter determines the randomness of the domain: large l (e.g.. h 1) means Pr(B. 1) is bounded away from 1/2. We will investigate the following minimax risk:
Rg F) == inf P
((F2,)) L(F*)
(1)
JE,EEF P
where E is the number of training domains, is the number of training samples from each domain, and the two expectations taken the sampling of training data and domains leam fg... The minimax problem in Equation (1) characterizes the access risk of the best learning algorithm with an access to É training domains and n data samples under the worst-case domain distribution.
Let V be the VC dimension of F. which is defined as the maximum number of points that can be arranged so that F shatters them. Our main results are as follows:
Theorem 1. For co, any h [0, 1] and any E 2 V. have the lower bound
V
V-11
V -1-1
0 (h 2 emin
Eh
where e >> 0 is an absolute constant.
We defer the proofs of Theorem I to Appendix A. The theorem provides lower bound on the number of training domains required to achieve small population error, even though one can sample many data points as possible from each domain. The case of n = ac captures the "casiest" case for the learner, where the learning algorithm can access full knowledge about each training domain. The case of finite n is harder than n = oo, as the learner has only partial knowledge about each training domain and RE (h,F) 2 R F). Therefore, Equation (2) provides a universal lower bound
3

---

Under review as a conference paper at ICLR 2023
a))a))
(2. az)
(55)
(x3,ag) az)
Sampling Domain
(Xg,, (at))
(Ng. bo.e)
Sampling
(x9.
(x,
Training Data
(Xs, as)
(xg. (e2)
bev)
(gs a6)
(K8, Y2)
(xs, Dya))
(Ky,ay)
(Kg Km)
Supporting Space
Training Duta Sampled from Domain Pe
Domain Distribution P
Domain P.
Estimating a by the Estimation of b
Estimating Domain-Specific bb
Data Generation
Learning Procedure
Illustration of our o.o.d. generalization problem. We show how data is sampled and how learning algorithms learn the knowledge. When generating training data, E' domain from the data distribution P first sampled, and after that for each domain, training data sampled to form the training dataset which will be fed into learning algorithm. The learning algorithm recovers the underlying label a by the estimation of the underlying label b e E [E] under the observation of training data.
Figure/ 1:
for general 2 1. Theorem I implies that, number training domains order to achieve a small excess error for any learning algorithm of F. This is in sharp contrast to many existing benchmarks which the number of training domains is limited (see Table 1). For example, in the celebrated ColoredMNIST dataset (Arjovsky et al., 2019), there only training domains. When the algorithm is trained the "+90%% and "+80%% domains and is tested on the "-90%" domain, the best-known o.o.d. algorithm achieves test accuracy better than random guess under all three model selection methods in Gulrajani & Lopez-Paz (2021). Theorem I predicts the failures of future algorithms on these datasets and attributes the poor performance of existing o.o.d. algorithms to the lack of training domains.
one requires least poly pVly(V)))
Differences between our work and Massart & Nédélec (2006b). The major differences include: 1) the construction of the hard instance, i.e., a two-stage data generative procedure, and 2) the strategy of splitting the hard problem into two sub-urobi problems (see Figure 1). These two aspects are original and separate our contributions with previous works. For 1), our data generative model first samples E domains from the domain distribution PP by generating the domain-specift. label be, Ve E [F] and then samples the training data from each sampled domain. On the other hand, Massart & Nédélec (2006b) considered totally different scenario: they investigated the effect of training sample size on the excess risk in the single-domain problem when the training and test data are i.i.d. For 2), proof has to deal with two expectations given that we have designed novel two-stage recovery strategy. Our two-stage problem splits the hard problem into two simpler problems which estimate binary string and b., Ve E [E], while Massart & Nédélec (2006b) only considered one binary string estimation problem. The two binary string estimation problems are entangled, making our analysis more challenging.
EXPERIMENTS
Theorem shows that any learning algorithm that outputs a classifier with an e excess error to the Bayes optimal classifier requires least poly(1/e) number of training domains, even though the number of training data sampled from each training domain large. In this section, we complement theoretical results with an empirical study to evaluate the impact of number of training domains.
4.1 DATASETS
We conducted extensive experiments datasets from DomainBed, i.e., ColoredMNIST (Ar- jovsky et al., 2019) and RotatedMNIST (Ghifary et al., 2015). We notice that there are other popular domain generalization datasets, e.g., PACS (Li et al., 2017), VLCS (Fang al., 2013), Office-
4

---

Under review as a conference paper at ICLR 2023
Home (Venkateswara et al., 2017). and Terra Incognita (Beery et al., 2018). However, these datasets are hard to generate more training domains synthetically as their data generation process cannot be parameterized by single variable (e.g.. correlation between color and label in ColoredMNIITT or rotation degree in RotatedMNIST), Thus, in our paper we do not consider these datasets.
CoNST (Arjovsky et al., 2019) is a variant of the MNIST hand written digit classification dataset (LeCun et al., 1998). It is a synthetic dataset containing three domains Pe E 0.2, 0.9) colored either red or blue formalizing 70, 000 examples of dimension (2, 28, 28) and 2 classes. The label is a noisy function of the digit and color, such that color bears correlation PE with the label and the digit bears correlation 0.75 with the label. Inspired by the protocol introduced in DomainBed repository, we randomly split the training dataset into 10 subdatasets with equal training samples. Each domain of ColoredMNISS is generated as follows: 1) Assign a preliminary binary label y to the image based on the digit: y' = 0 for digits 0- - 4 and y/ 1 for 5 9: 2) Obtain the final label y by flipping y' with probability 0.25; 3) Sample the color id = by flipping y with probability Pe: 1 or green if z O. The only parameter of training domain is pe- We use the domain with P. = 0.5 as the test domain and uniformly sample E parameters Pe from (0, 1)/{0.5) to form E training domains. Each domain randomly uses subset from 10 subdatasets of the whole MNIST to generate the data.
4) Color the image red if
RotatedMNIST (Ghifary et al., 2015) is another variant of MNIST with 6 domains containing digits rotated by (0. 15, 30, 45, 60, 75) degrees. It contains 70, 000 examples of dimension (1, 28, 28) and 10 classes. Similar to ColoredMNIST, and uniformly sample E' rotation degrees from [0, (455 to form E' training domains.
use the domain with 45 degrees rotation as the test domain
4.2 ALGORIITM
To validate our theoretical results, evaluate the effect of number of training domains on o.o.d. algorithms, including ERM (Empirical Risk Minimization) (Vapnik, 1991), IRM (Invariant Risk Minimization) (Arjovsky al., 2019), GroupDRO (Sagawa et al., 2020), Mixup (Xu al., 2020), MLDG (Li et al., 201 8a). CORAL (Sun & Saenko, 2016), MMD (Li et al., 2018b), DANN (Ganin al., 2016), and C-DANN (Li et al., 2018c). The details of the algorithms are shown in the appendix.
For each algorithm, we employ the default hyper parameter introduced in Section D.2 of Do- mainBed (Gulrajani & Lopez-Paz, 2021), as our goal is not to show the best performance of algorithms but to show the correlations to our theoretical results. Following DomainBed (Gulrajani & Lopez-Paz, 2021), we use MUNIT (Table 4) for ColoredMNIST and RotatedMNIST.
4.3 EVALUATION SETTINGS
We train models using 9 different Domain Generalization algorithms, with a varying number of training domains on ColoredMNIST and RotatedMNIST. Each trial is done with 5 different random seeds, and we present the average results. We use the code repository of DomainBed (Gulrajani & Lopez-Paz, 2021) with PyTorch (Paszke et al., 2019).
Model Evaluation. Following DomainBed (Gulrajani & Lopez-Paz, 2021), we employ and adapt three different model selection methods for training algorithms as shown below.
Leave-one-domain-ouu cross cross-validation. E' models are trained on E' training domains with equal hyperparameters, while each experiment holds out one of the training domains. The evaluation of each model is conducted on its held-out domain and we choose the model when maximizing the accuracy on the held-out domain. This method has an assumption that training and test domains are drawn from a mela-distribution over domains, and that our goal is to maximize the expected performance under this meta- distribution. This method corresponds our data generation model. But it requires huge computational resources. We only use this method to select model with the number of domains varying from 2 to 30.
Training-domani validation set. Each training domain is split into training and validation subsets and the overall validation set consists of the validation subsets of each training domain. Finally, we choose the model maximizing the accuracy on the overall validation set. This method has an assumption that the training and test examples follow similar distributions.
5

---

Under review as a conference paper at ICLR 2023
Table 2: The experimental results on ColOredMNIIT with ERM, IRM, GroupDRO. Mixup, MLDG, and CORAL w.r. the number of training domain using the caining-domain validation set model selection method.
[#
ERM
IRM
GroupDRO
Mixup
MLDG
CORAL
0.6697+0.0120
0.5500=0.0091
0.6710=0.0134
0.6081=0.0144
0.674420.0046
0.658620.0139
6
0.7135+0.0027
0.5910#0.0072
0.7158=0.0013
0.6703=000088
0.7107=0.0035
0.7141#0.0020
0.7183+00.0118 0.6278+0.0031
0.7199=0.0016
0.7129=0.0017
0.7195=0.0005
0.7199#0.0013
10
(17226*00.0005 0.6685#0000066
0.7220=00.0004
0.7155==0.0066
0.7271=0.0011
0.7228+0.0004
12
0.7280#0.0011 0.6968#0.0034
0.7288=0.00122
0.7223=0.0015
0.7287=0.0008
0.7278#0.0010
14
0.7289#0.0016 0.6709=0.0123
0.7284=0.0016
0.7215=0.0007
0.7316=0.0015
0.7285#0.0015
16
0.7268+0.0011 0.6777=0.0055
0.7272=0.0010
0.7230=0.0014
0.7322
0.7258=0.0010
18
0.7304+0.0017 0.7031
0.7292=0.00015
0.7255=0.0015
0.7338#0.0009
0.7297#0.0008
20
0.7305+0.0015 0.695720.0069
0.7321=0.0011
0.7239=0.0010
0.733620.0008
0.7311=0.0013
0.7333++0.0011 0.6935#0.0078
0.7298=00.001
0.7276#0.0012
0.7368=0.0014
0.7296#0.0011
24
0.7330=0.0015 0.6908=0.00$6
0.7358=0.0007
0.7269=0.0014
0.7366=0.000
0.7354=0.000
0.7350#0.0019 0.6995=0.0022
0.7343=0.0016
0.7323=0.0013
0.7366=0.0011
0.7353+0.0015
28
0.7336#0.0016 0.6997=0.0076
0.7347=0.0014
0.7327=0.0011
0.7370=0.0011
0.7332#0.0014
0.7331+0.0023 0.7113=0.0027
0.7326=0.002 0.032
0.7297=0.0020
0.7391=0.0012
0.7329#0.0020
48
0.7386+0.0014 0.7219#0.0007
0.7398#0.0013
0.7352=0.0011
0.7410#0.0011
0.7385#0.000
0.7427+0000114 0.7182+000015
0.7424+0.0013
0.7399=0.0012
0.7444=0.0011
0.7424H0.0014
192
0.7437+0.0014
0.7287=0.0012
0.7443=0.0014
0.7424=0.0013
0.7461#0.0010
0.743740.0014
Test-domain validation set (oracle). We choose the model maximizing the accuracy on validation set that follows the distribution of the test domain. All the models are trained for the same fixed number of steps and the final checkpoints are used for evaluation. assumes and requires that models have the access to the test domain which might not be possible in the real-world application.
4.4 EXPERIMENTAL RESULTS ON COLOREDMNIST AND ROTATEDMNIST
We first introduce the average results on two different datasets using 9 algorithms with the number of training domains varying from 2 to 192 and then present the results with limited number of domains. Due to the limitation of space, we present the most important results in our paper while leaving the left results in the Appendix.
4.4.1 EVALUATING THE EFFECT OF NUMBER OF TRAINING DOMAINS
Results. We run the experiments on ColoredMNIST and RotatedMNIST with ERM, IRM, Group- DRO, Mixup, MLDG, CORAL, MMD, DANN and C-DANN while the number of training domains varies from
192. The average accuracy w.r.t the number of training domains is shown in Tables 2 and 3 in the main paper. Tables 6, and 8, and Figures 4 and 5 in the Appendix. It shows that the test accuracy is proportional to the number of training domains with all the algorithms on both ColoredMNIST and RotatedMNIST which is consistent with our theoretical results (Theorem 1).
Training-domain validation set analysis. The results are shown in Tables 2 and 8 and Figure 5. We observe that the test accuracy of almost all the algorithms on both ColoredMNIST and RotatedMNIST monotonically increasing as the number of training domains grows while the accuracy of IRM on both datasets, MMD on ColoredMNIST, DANN and CDANN on RotatedMNIST experiences slight drops for certain number of training domains. We also find that the standard deviations of MMD quite big which might be due to the hyperparameter setting hyperparameters to gain the best performance. Besides, the standard deviations of all the algorithms on the first experiments (the least number of training domains) are quite large. That is because the
did not try to tune the

---

Under review as a conference paper at ICLR 2023
Table 3: The experimental results on ColOredMMIIS with ERM, IRM, GroupDRO. Mixup. MLDG, and CORAL w.r.t the number of training domain using the test-domain validation set (oracle) model selection method.
|#
ERM
IRM
GroupDRO
Mixup
MLDG
CORAL
4
0.6697+0.0120
0.5517+0.0085
0.6710=0.0134
0.6081=0.0144
0.6750=0.0046
0.658640.0139
6
0.7138+0.0027
0.5915=0.00033
0.7158=0.0013
0.6703=000088
0.7133#0.0033
0.7141#0.0020
0.7203+0.00144 0.6278+0.0031
0.7205=0.0017
0.7129=0.0017
0.7213#0.0009
0.7209#0.0010
10
(..24440..0012 0.6685#00.0066
0.7236=+0.0012
0.71.59=0.0006
0.7271=0.0011
0.7244H0.0012
12
0.7284+0.0009 0.6968+0.0034
0.7288=0.00122
0.7224#0.0015
0.7302=0.0010
0.7280#0.0010
14
00.291 0.6709=0.0123
0.7284=0.0016
0.7216=000000
0.7317=0.0015
0.7286#0.0015
16
0.7274=0.0011 0.6777=0.0055
0.7274=0.0010
0.7230=0.0013
0.7326:0.0010
0.7265#0.0011
18
0.7314+0.0012 0.7031
0.0011
0.7260=0.0016
0.7343#0.0008
0.7307=0.0010
20
0.7311=0.0015 0.695810.0069
0.7321=0.0011
0.7259=0.0010
0.7341=0.0010
0.731340.0012
22
0.7323++0.0011 0.6935+0.00778
0.7305+00.0012
0.7278=000011
0.7371=0.0014
0.7306#0.0014
24
0.7357=0.0013 0.6908=0.0086
0.7358=000009
0.7281=0.0018
0.7372=0.0012
0.7354#0.0012
0.7051#0.0018 0.6995#0.0026
0.7345=0.0015
0.7323=000013
0.7368=0.0011
0.7353#0.0015
28
0.7041 0.6997=0.0076
0.7351=0.0014
0.7331=0.0011
0.7370=0.000
0.7338#0.0012
0.7333+0.0023 0.7113=0.0027
0.7338=0.0022 0002
0.7300=0.0018
0.7396=0.0014
0.7334#0.0021
48
0.7390#0.0012 0.7219#0.0007
0.7398=0.00115
0.7362
0.7415
0.7390 0.014
0.7432+0.0014
0.7182+0000155
0.7425+0000013
0.7401=0.0011
0.7446=0.0011
0.7427=0.0014
192
0.7439H0.0012
0.7287=0.0012
0.7448:00.0022
0.7426=0.0014
0.7468=0.0010
0.7439#0.0013
number of training domains is limited and the algorithms are hard to capture general patterns. As the number training domains grows, the standard deviations of almost all the algorithms decrease.
Test-domain validation set (oracle) analysis. Figure 4 and Tables 3, 6 show the results using the oracle model selection method. Similar observations can be obtained. The accuracy of ERM, DANN, CDANN, CORAL. GroupDRO and Mixup CoIST and RotatedMNIST is proportional to the number of training domains while there are fluctuations in the lines of MMD and IRM on both datasets, which might be due to the fact that MMD and IRM are sensitive to the hyperparameters as we did not tune the hyperparameters for the best performance. The line of IRM on RotatedMNIST drops slightly when the number of training domains is over 100. That might be caused by the limited number of training images n in our theorem. In that case, algorithms might not be able to extract general patterns and might learn biased information, which causes the performance drop. Besides, as we only conduct 5 trials for each experiment, the randomness of the experiments might be also another reason why the performance of IRM on RotatedMNIST drops slightly. Overall, the results using test-domain validation set and training-doman validation set model selection methods are the same, which supports our theoretical results.
4.4.2 EVALUATING ON THE LIMITED NUMBER OF TRAINING DOMAINS
As the -ouma-no- cross- vooss-valiattoon requires huge computational resources, we only conduct the experiments with the number of training domain from 2 to 30 with step of 2. The results are shown Figure 2 in the main paper, Figure 6, Table 9 and Table 10 the Appendix. The reason why we only choose the even numbers is that we are trying to sample the domains evenly. For example, for ColoredMNIST, we use training domains and test on the 0.5 domain, we may have to sample either two domains whose hyper-parameterss are bigger than 0.5 smaller than 0.5, and only one domain whose hyper-parameter is smaller than 0.5 or bigger than 0.5, which might cause domain sampling drift and further we observe biased results.
Analysis of leave-one-domain-out cross-validation results. Observed from two tables and the figure, we conclude that the test accuracy of most algorithms is proportional to the number of training domain, while there are some exceptions. e.g., IRM on ColoredMNIST and GroupDRO on NISS.. For all the results on RotatedMNIST, we observe that the results perfectly match
7

---

Under review as a conference paper at ICLR 2023
ERM ColoredMNIST
ERM RotatedMNIST
IRM ColoredMNIST
IRM on RoGatedMNIST
Accuracy
0.15
Testnng Accuracy
Testing Accuracy
Testing Accuracy,
0:70
0.29
0.65
0.40
0.25
0.00
3.-
9.-
0.50
20
15
10
25
of Training Domain
of Training Domain
# Training Domain
# of Training Domain
DANN on ColoredMNIST
DANN on RotatedMNIST
CDANN on ColeredMNIST
CDANN on RotatedMNIST
Testing Accuracy
Tosting Accurary
Testing Accuracy
0.30
0.78
0.5
0.5
0.50
13
20
10
10
30
15
20
20 30
+ of Training Domain
# of Training Domain
# of Training Domain
8 of Training Domain
The experimental results on ColoredMNIST and RotatedMINST using ERM, IRM, DANN and C-DANN w.r. the number of training domain using the leave-one-domain-out cross- validation method.
Figure 2:
our theoretical results even without any hyper-parameter tuning, especially for the experiments on IRM. But we still can observe exactly the same fact that without any hyper-parameter tuning, the test accuracy of IRM on RotatedMNIST grows with the increase of the number of training domain. There are some fluctuations in the line of GroupDRO, CORAL and Mixup, which might be due to only conduct 5 experiments for each trial. On the other
the randomness of the experiments hand, the results on ColoredMNIST are still proportional to the number of training domains on all algorithms except IRM. And we also observe fluctuation due to the fact that the number of data from each domain, n. is 1, 000, which is much smaller than that for RotatedMNIST, which 10, 000. The limited number of data from each domain might hinder algorithms from learning enough patterns and thus the algorithms can only capture biased patterns due the lack of training data from each domain. For IRM, similarly, the importance of hyper-paramett parameter tuning causes the accuracy to go up and down with the increase of the number of training domains and one might have utilize as much as possible computational resources for tuning it. Comparing with other two model selections methods, as this one requires more trials, the standard deviations are smaller.
almost every algorithm. That may be
4.5 ABLATION STUDY
Analysis on different architecture. test how our theoretical results generalize to other archi- tecture of neural networks, we further conduct experiments ColoredMNIST (Table 4) with VGG11 (Simonyan & Zisserman, 2014) with the oracle model selection method. We use the learning rate of 5e 5 while remaining other hyparameters the same. The corresponding results are shown in Tables 15, 16, 17, and 18 and the left two figures in Figure 3. Similar conclusion can be summarized that the test accuracy still grows with the increase of number of training domain while using total different architecture. But we observe more fluctuation in the line with VGGI I as we only conduct trail for VGGII. There is big "valley" around E 100 in the experiments of ERM on MoLSTT which is quite unusual as it is too big compared with other fluctuation. That might be caused by the randomness or the failure of hardware as we only see that situation once. We also conducted experiments on Resnet18 (He et al., 60. But after we tried different set of hyper-parameters, ResNet18 seems not to converge on any set of hyperparamters.
Analysis on the number n of data from each domain. To testify the effect of the number of data from each domain, we conduct experiments on ColoredMNIST using ERM and IRM with n from 1000 to 20000 and the oracle model selection method, while the original is set to be 7000. The experimental results are shown in Tables 11, 12, 13, and 14 and the right two figures in Figure 3. It shows that when is relatively small compared with the original number 7000, especially when n = 1000, the line of the accuracy experiences lots of fluctuations. The randomness may be the biggest reason as we only conducted one trail for the ablation study, while we still observe that, the
8

---

Under review as a conference paper at ICLR 2023
ERM on ColoredMNIST
IRM on ColoredMNIIST
ColoredMNIST
ColomaMNNST
Testing Accurity
Testino Accuracy
Testing Accuracy
1000
ass.
6.00
0.00
VoGk2
att-
VOOL4
10000
5500
2-20000
Training Domain
Training Domain
of Training Domain
Training Domain
72000
TECASOT)
Figure 3: The experimental results ColoredMNIST using ERM and IRM, w.r.t the number of training domain with the oracle model selection method. The left two figures show the results with different architectures, i.e., MUNIT and VGGIl (Simonyan & Zisserman, 2014), while the left three figures present the corresponding results with different number of n.
test accuracy is "overall" proportional to the number of training domain. When n 2 2000, the line of test accuracy is absolutely proportional to the number of training domain, which fits our theoretical results well. But that also arises a question that, what is the minimal requirement n. for achieving similar theoretical result.
Discussion on E < V. When E < V, there would be a lot of domains that the learning algorithm has never seen in the training phase. Under this assumption, the lower bound on the excess error might be higher than the current results (Theorem 1). But we might be able have the similar conclusion with our theoretical result. The experimental results shown in Table 9, Table 10 and Figure 2 indicate that, even when the number of domains (less than 30) is relatively small compared with the dimension of the training data in the case < V, the performance is still proportional to the number of training domain E in the most of cases, which supports our theoretical results (Theorem 1).
5 CONCLUSION
In this paper, we investigated the out-of-distribution problem and analyzed how many training domains were required to achieve a small population error in the test domain under reasonable assumptions. Our results theoretically characterized the phenomenon of the lost domain generalization which had been found by Gulrajani & Lopez-Paz (2021) in 2021. And our work showed that in a minimax lower bound fashion, any learning algorithm with an e excess error to the Bayes optimal classifier required at least poly(1/e (1/c) number of training domains, even when the number of training data sampled from each training domain was large. There were strong correlations between our work and some empirical results (Arjovsky et al., 2019; Liu et al., 2021; Krueger et al., 2021) in the o.o.d area. Besides, though we used Bernoulli (discrete) random variables to present our theoretical results, our lower bounds hold true for broader distribution class as we look at the worst-case distributions.
To complement our thcoretical results, we conduct experiments on two OOD benchmarks, i.e., ColoredMNIST and RotS,edMNISTT with several OOD methods, showing that for the methods used in this paper, the test accuracy on the test domain was proportional to the number of training domains under three different model selection methods. That matched our theoretical results perfectly.
There are several future directions of our work. Our theorem assumed that the number of data samples from each domain was xc. This assumption was used lower bound the case of general because intuitively, the case of n oo should be simpler than the case where n is a finite number. It is interesting to understand how n affects a tight minimax lower bound. Another future direction is to explore the case where the numbers of samples from each domain are different. It would be interesting to see which domain dominates the training procedure and how to design o.o.d training algorithms under this scenario. Moreover, in our case, the instance support (feature space) was shared across domains. Another case we should consider is that each domain only has its own instance support. This kind of domain shift is frequently observed in real-world scenarios and it would help us understand the o.o.d problem further. Besides, we would also like to explore the upper bound of o.o.d problems see whether our lower bound results match the upper bound. Last, though multi-class classification can be seen as a combination of multiple binary classification problems (e.g., one-vs.-res classifier), it is interesting extend our results the multi- custiiclassiiiiaaiion problem.
9

---

Under review as a conference paper at ICLR 2023
ETHICS STATEMENT
We did not see obvious negative ethical impacts in our work. In contrast, our work might have a positive impact on society regarding the fairness (Barocas et al., 2019) and security (Zhang al., 2019; Kawaguchi et al., 2017; Bubeck el al., 2020) of machine learning. Achieving a small population error in the test domain ensures fairness regarding the bias of the dataset in the race, gender, age, etc., as most of the public datasets, e.g, CelebA (Liu et al., 2015), have bias and that will lead to the bias of machine learning models (Barocas et al., 2019). Moreover, security issues such as adversarial robustness (Hendrycks et al., 2020; 2021) are also related to our study of domain generalization, where clean examples and adversarial examples are from different domains. Improving the population error of machine learning models in the test domain may lead to robust models against adversarial attacks.
REFERENCES
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint vrXiv:/907.02890 2019.
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning. fairml- book.org, 2019.
Sara Beery Grant Van Horn, and Pietro Perona. Recognition in Terra Incognita. In European Conference Computer Vision, Lecture Notes in Computer Science, pp. 472-489, 2018.
Alexis Bellot and Mihaela van der Schaar. Accounting for Unobserved Confounding in Domain Generalization, arXiv preprint arXiv:2007. 2020.
Julian Bitterwolf,, Alexander Meinke, Maximilian Augustin, and Matthias Hein. Revisiting out-of- distribution detection: A simple baseline is surprisingly effective, 2022.
Gilles Blanchard, Aniket Anand Deshmukh, Urun Dogan, Gyemin Lee, and Clayton Scott. Domain generalization by marginal transfer learning. Journal of Machine Learning Research, 22(2):1-55, 2021.
Sebastien Bubeck, Ronen Eldan, Yin Tat Lee, and Dan Mikulincer. Network size and size of the weights in memorization with two-layers neural networks. Advances Neural Information Processing Systems, pp. 4977-4986, 2020.
Manh-Ha Bui, Toan Tran, Anh Tran, and Dinh Q Phung. Exploiting domain-specifer features to enhance domain generalization. In Advances in Neural Information Processing Systems, pp. 21189-21201, 2021.
Ching-Yas Yao Chuang, Antonio Torralba, and Stefanie Jegelka. Estimating generalization under distribu- tion shifts via domain-invariant representations. In International Conference on Machine Learning, pp. 1984-1994, 2020.
Qi Dou, Daniel Coelho de Castro, Konstantinos Kamnitsas, and Ben Glocker. Domain generalization via aones-agnostic learning of semantic features. In Advances in Neural Information Processing Systems, pp. 6447-6458, 2019.
Chen Fang, Ye Xu, and Daniel N. Rockmore. Unbiased Metric Learning: On the Utilization of Multiple Datasets and Web Images for Softening Bias. In IEEE International Conference on Computer Vision, pp. 1657-1664, Sydney, Australia, 2013.
Daniel Fried, Nikita Kitaev, and Dan Klein. Cross-domain generalization of neural constituency parsers. In Annual Meeting of the Association for Computational Linguistics, pp. 323-330, 2019.
Chuang Gan, Tianbao Yang, and Boqing Gong. Learning attributes equals multi-source domain generalization. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 87-97, 2016.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario March, and Victor Lempitsky. Adversardd Training of Neural Networks. Journal of Machine Learning Research, 17(59):1-355 2016.
10

---

Under review as a conference paper at ICLR 2023
Muhammaa Ghifary, W. Bastiaan Kleijn, Mengjie Zhang, and David Balduzzi. Domain Generalization for Object Recognition with Multi-task Autoencoders. In IEEE International Conference on Computer Vision. pp. 2551-2559 2015.
Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernaard Schölkopf, and Alexander Smola.
A Kernel Two-Sample Test. Journal of Machine Learning Research, 13(25):723-777 2012.
Ishaan Gulrajani and David Lopez-Paz. In search of lost domain generalization. In International Conference on Learning Representations, 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In IEEE Conference Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness common corruptions and perturbations. In International Conference on Learning Representations, 2019.
Dan Hendrycks, Norman Mu, Ekin Dogus Cubuk, Barret Zoph, Justin Gilmer, and Balaji Lakshmi- narayanan. Augmix: A simple method to improve robustness and uncertainty under data shift. In International Conference Learning Representations, 2020.
Dan Hendrycks, Steven Basart, Norman Mu, Saurav Kadavath, Frank Wang, Evan Dorundo, Rahul Desai, Tyler Zhu, Samyak Parajuli, Mike Guo, Dawn Song. Jacob Steinhardt, and Justin Gilmer. The many faces of robustness: A critical analysis of ouutt--distribution generalization. In IEEE International Conference on Computer Vision, pp. 8320-8329, 2021.
Jiaxing Huang, Dayan Guan, Aoran Xiao, and Shijian Lu. FSDR: frequency space domain randomiza- tion for domain generalization. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 6891-6902, 2021.
Kenji Kawaguchi, Leslie Pack Kaelbling, and Yoshua Bengio. Generalization in deep learning. arXiv preprint 171.v:1710.05466, 2017.
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsub- ramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, Tony Lee, Etienne David, Ian Stavness, Wei Guo, Berton Earnshaw, Imran Haque, Sara M. Beery, Jure Leskovee, Anshul Kundaje, Emma Pierson, Sergey Levine, Chelsea Finn, and Percy Liang. WILDS: A Benchmark in-the-Wild Distribution Shifts. In International Conference on Machine Learning, pp. 5637-5664, 2021.
David Krueger, Ethan Caballero, Joern-Henrik Jacobsen, Amy Zhang, Jonathan Binas, Dinghuai Zhang, Remi Le Priol, and Aaron Courville. lation (REx). In International Conference on Machine Learning, pp. 5815-5826, 2021.
Generalization via Risk Extrapo-
Lucien LeCam. Convergence of estimates under dimensionality restrictions. The Annals of Statistics, pp. 38-53, 1973.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, and others. Gradient-based learning applied to document recognition. Proceedings of the IEEE,
-2224, 1998.
Da Li, Yongxin Yang, Yi-Zhe Song, and Timothy M. Hospedales. Deeper, Broader and Artier Domain Generalization. In IEEE International Conference on Computer Vision, pp. $543-5551, Venice, Italy, 2017.
Da Li, Yongxin Yang. Yi-Zhe Song, and Timothy Hospedales. Learning to Generalize: Meta-Learning for Domain Generalization. In AAAI Conference on Artificial Intelligence, 201 8a.
Da Li, Yongxin Yang, Yi-Zhe Song, and Timothy Hospedales. Sequential learning for domain generalization. In European Conference on Computer Vision, pp. 603-619. Springer, 2020.
Da Li, Henry Gouk, and Timothy Hospedales. Finding lost DG: Explaining domain generalization via model complexity. arXiv preprint arXiv:2202.00563. 2022a.

---

Under review as a conference paper at ICLR 2023
Haoliang Li, Sinno Jialin Pan, Shiqi Wang, and Alex C. Kot. Domain Generalization with Adversarial Feature Learning. In JEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. $400-5409 2018b.
Xiaotong Li, Yongxing Dai, Yixiao Ge, Jun Liu, Ying Shan, and LINGYU DUAN. Uncertainty modeling for -istt--disti generalization. In International Conference on Learning Repre- sentations, 2022b.
Ya Li, Xinmei Tian, Mingming Gong, Yajing Liu, Tongliang Liu, Kun Zhang, and Dacheng Tao. Deep Domain Generalization via Conditional Invariant Adversarial Networks. In European Conference on Computer Vision, pp. 647-663, 2018c.
Chang Liu, Xinwei Sun, Jindong Wang, Haoyue Tang, Tao Li, Tao Qin, Wei Chen, and Yan Liu. Learning Causal Semantic Representation for iit-o--Distribution Prediction. In Advances in Neural Information Processing Systems, pp. 6155-6170, 2021.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes the wild. In International Conference Computer Vision, pp. 3730-3738, 2015.
Divyat Mahajan, Shruti Tople, and Amit Sharma. Domain generalization using causal matching, In International Conference on Machine Learning, pp. 7313-7324, 2021.
Pascal Massart and Élodie Nédélec. Risk bounds for statistical learning. The Annals of Statistics, 34 1-2322-23366 2006a.
Pascal Massart and Élodie Nédélec. Risk bounds for statistical learning. The Annals of Statistics, 34 (5):2326-234) 23666, 2006b.
Toshihiko Matsuura and Tatsuya Harada. Domain Generalization Using Mixture of Multiple Latent Domains. AAAI Conference on Artificial Intelligence, pp. 11749-111 11449-11756, 1756, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style. High- high-Perffrmance Deep Learning Library. In Advances Neural Information Processing Systems, pp. 8024-8035, 2019.
Vihari Piratla, Praneeth Netrapalli, and Sunita Sarawagi. Efficient domain generalization via common- specific low-rank decomposition. In International Conference on Machine Learning, pp. 7728- 7738, 2020.
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do ImageNet classifiers generalize to ImageNet? In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), International Conference on Machine Learning, pp. 5389-5400, 2019.
Alexander Robey, George J. Pappas, and Hamed Hassani. Model-based domain generalization. In Advances in Neural Infomation Processing Systems, pp. 20210-20223 2021.
Shiori Sagawa, Pang Wei Koh, Tatsunori B. Hashimoto, and Percy Liang. Distributionally Robust Neural Networks. In International Conference on Learning Representations, 2020.
Shiori Sagawa, Pang Wei Koh, Tony Lee, Irena Gao, Sang Michael Xie, Kendrick Shen, Ananya Kumar, Weihua Hu, Michihiro Yasunaga, Henrik Marklund, Sara Beery, Etienne David, lan Stavness, Wei Guo, Jure Leskovec, Kate Saenko, Tatsunori Hashimoto, Sergey Levine, Chelsea Finn, and Percy Liang. Extending the WILDS Benchmark for Unsupervised Adaptation. In International Conference on Learning Representations, 2021.
Shiv Shankar, Vihari Piratla, Soumen Chakrabarti, Siddhartha Chaudhuri, Preethi Jyothi, and Sunita sarawagi. Generalizing across domains via coos--gradient training. In International Conference on Learning Representations, 2018.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv: 1409. 1556, 2014.
12

---

Under review as a conference paper at ICLR 2023
Chuanbiao Song, Kun He, Liwei Wang, and John E. Hoperoft. Improving the generalization of adver- sarial training with domain adaptation. In International Conference on Learning Representations. 2019.
Baochen Sun and Kate Saenko. Deep CORAL: Correlation Alignment for Deep Domain Adaptation. In European Conference on Computer Vision, Lecture Notes in Computer Science, pp. 443-450, 2016.
Rohan Taori, Achal Dave, Vaishaal Shankar, Nicholas Carlini, Benjamin Recht, and Ludwig Schmidt. Measuring robustness to natural distribution shifts in image classification. In Advances in Neural Information Processing Systems, pp. 18583-18599, 2020.
Sunil Thulasidasan, Sushil Thapa, Sayera Dhaubhadel, Gopinath Chennupati, Tanmoy Bhattacharya, and Jeff Bilmes. A simple and effective baseline for out-of-distiibuttin detection using abstention, 2021.
V. Vapmik. Principles of risk minimization for learning theory. In Advances in Neural Information Processing Systems, 1991.
Hemanth Venkateswara, Jose Fusebio, Shayok Chakraborty, and Sethuraman Panchanathan. Deep Hashing Network for Unsupervised Domain Adaptation. In JEEE Conference Computer Vision and Puttern Recognition, pp. 5385-5394, 2017.
Yoav Wald, Amir Feder, Daniel Greenfeld, and Uri Shalit. On calibration and out-of-domain generalization. In Advances in Neural Information Processing Systems, pp. 2215-2227, 2021.
Bailin Wang, Mirella Lapata, and Ivan Titov. Meta-learning for domain generalization in semantic parsing. In Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 366-379, 2021.
Minghao Xu, Jian Zhang, Bingbing Ni, Teng Li, Chengjie Wang, Qi Tian, and Wenjun Zhang Adversarial Domain Adaptation with Domain Mixup. In AAAI Conference on Artificial Intelligence, pp. 6502-65099 2020.
Fu-En Yang, Yuan-Chia Cheng, Zu-Yun Shiau, and Yu-Chiang Frank Wang. Adversarial teacher- student representation learning for domain generalization. In Advances Neural Information Processing Systems, pp. 19448-19460, 2021.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing, Laurent El Ghaoui, and Michael I. Jordan. Theoretically principled trade-off between robustness and accuracy. International Conference on Machine Learning, pp. 7472-7482, 2019.
Kaiyang Zhou, Yongxin Yang. Yu Qiao, and Tao Xiang. Domain generalization with mixstyle. In International Conference on Learning Representations, 2021.
13

---

Under review as a conference paper at ICLR 2023
A PROOF OF THEOREM
A. PREPARATION
We first construct a "hard" instance over the supremum to lower bound the minimax problem and then reduce it into a label recovery problem. We begin with the definition of domain distribution and some lemmas, and we assume h > 0 throughout our proof.
Definition 2. A domain distribution is said to satisfy the Massart noise condition with margin h if (2n(X) - 1| Z h with probability We denote the set of domain distributions satisfying the Massart
noise condition by F), = {P F) (22n(X) 11 Z h with probability 1}.
Lemma 3. For any classifier f : X {0, 1}, any distribution P on X x {0, 1} and the Bayes optimal classifier f on P, we have
L()) I(S" EX) (1|5(X)- - (x())
Specifically, i E P(h, we have
L() - L()) ((X) -
where the L1 norm is computed w.E. the distribution of X. i.c., |lf - -f ExEx Pr(X fx) (x)) X is drawn from a discrete distribution or ||f f" =xxxx(xx)f((X
(x) dx if X is drawn from continuous distribution.
Lemma 4. Let f be any learning algorithm satisfying F. be the learning algorithm which closest to fā in L1 norm w.rt the distribution of sampled data x, i... argmin JEF |lf fālle, where f3 is a classifier given by a binary string 3 on X1, ...... XV-1 such that / = fx(vV-1) For any B 13V we have
Iff - fāllz, S 2 --1--fllla.
The goal of fE.n is estimate the ground-trun truth label of the supporting data by observing and learning from E n data points sampled from E domains. We observe that, given any domain distribution D F), the minimax risk RE (h, (1) can be lower-bounded as
RE F)2 inf sup Br. [(JE,.)) T(S*))
(3)
D will be constructed such that the supporting space (X, a) of D contains V data points (x;, a;), E [V- space, respectively. The label space of 'D can be indexed by the vertices of binary hypercube and the expected excess risk can be reduced to the problem of label recovering. The feature support X1, X2,..., Xy is shared by all the domains in D. All learning algorithms f with the VC dimension bigger than V can shatter these data points.
- 1]. We denote by {x and -a the feature space and the label
Theorem Let (Pg 0 E 10 be a collection of probability distributions on some set index by the vertices of the binary hypercube ④ =)0,1) Suppose that there exists some constant 0. such that
Pp) (dd((,,0)=1)
(4)
Consider the problem of estimating the parameter 0 E θ based on i.i.d observations from Po- where the loss is measured by the Hamming distance. Then the corresponding minimax risk, which we denote by M,.(),, is lower-bounded as
Mn 2 m 2
(1- - -Vo))
(5)
A.2 CONSTRUCTING HARD INSTANCE
In this part, we lower bound this minimax problem by constructing a "hard" domain distribution D E P(h, F). We first show how to sample E training domains from the domain set D. Then, illustrate the procedure of sampling data points from the domain e by picking the marginal distribution Prx of feature X while specifying the condition distributions Prş of the binary label Y given X
14

---

Under review as a conference paper at ICLR 2023
and the domain. Finally, we show that the label space a E {0, 1 which is the underlying label of X, of can be naturally indexed by the vertices of binary hypercube of dimension -
Generating E domains from the set D. As the data generation procedure of o.o.d generalization is of two stages, we show how to sample domains based on the feature space X. The Nooainn-speciine
label b, of the e-th domain is generated by the Bernoulli
(2a 1)/
distribution as
1 +
1; a
Pr(Be.j 1)
2
1 h
af 0,
2
Sampling data from e-th domain. Now, E domains are sampled from D and we present how to sample the training data from the e-th domain. Given p E [0, 1/(V 1)}, which will be defined later, Pr' is constructed follows,
if s
xx 11- 1)p,
otherwise.
In this way, we ensure that Prx Prx((x),.... xv = 1. The labels of the samples follow the distribution
Pr(Y|X, B.) given B. = b (0, and X x Similarly, for a fixed b. E {0, 13 the conditional distribution of Y given x" is given by two Bernoulli distributions as
1 + (2bo.) - 1)/
Bernoulli
if = x, and j E (V 1];
2
Bernoulli(O).
otherwise,
where bo.j is the j-th entry of b Thus, we have
1 - h
if xx=xx] xj.J E (V 1] and b = 0;
2
n6. (x) Pr(Y 1|X x, Be =b))= =
1+
if = xj.j E (V 1] and b..j otherwise.
2
0,
The corresponding Bayes optimal classifiers on the e-th domain and on the mixed data distribution over all domains, denoted by f6, and f*, respectively, are given by
if x E [V - and b = 0; ifx = x j E [V - 1] and b = 1; (x(x) = 1.
0. if x,,J E V - 1] and a, = 0;
fb. (x) =
1,
if xj, E VV - 1] and a, 1;
0.
otherwise,
0.
otherwise.
From each domain, we i.i.d draw n samples. That is, the learning algorithm fE.. can access E samples in total. Next, we have the following lemma show that D (Pb. b E (0, 1) e [E' - 1}} is in F).
Lemma (Property of "Hard" Case). All the instances of DD satisfy the Massart noise condition with margin h. The distribution 'D belongs to P(h, F), i..., D F).
Now, the domain distribution D has been constructed. In the following part, will show that the problem of learning a classifier in our setting is at least as difficult as recovering the label a. With the Bayes optimal classifier Eq. (7) on the domain set D, we can reduce the problem to a label recovery problem.
A.3 ANALYZING THE O.O.D. MINIMAX PROBLEM BY REDUCING IT TO LABEL RECOVERY PROBLEM
We show that the o.o.d minimax problem can reduced to a label recovery problem by the following theorem.
15

---

Under review as a conference paper at ICLR 2023
Theorem 7 (Reducing A Label Recovery Problem). Given set of domains D E P(h, constructed as in Section A.2, then o.o.d minimax problem can be reduced to an estimation problem on a binary hypercube whose vertices index the label space of D, i.c., which is the underlying label of X, and the minimax risk RE (h, F) (1) satisfes
RE (h. 22
inf ((0.) (0.11)
max
f
(0.1)
where the L1 norm is computed w.r.t the distribution of X, and 3 and 3 are two strings.
Proof. We first apply Lemma Now, the o.o.d generalization minimax risk RE F) (1) becomes
inf sup f (EP(
Ep, PRANDExx,,yY T(ffEn)-TAA r(F')]
max B [fE. - f/ -ālle,
E (E(0.))V)
where the L1 norm is w.r. the distribution of samples Prx fE, and f3 are any classifier in F and the Bayes optimal classifier trained on the En training samples from E domains, respectively.
Next, by using Lemma with f == J... and f -EE we have
inf max. BreweExx [iEn - sall
fR pe (o.a))
h
inf 2 B El..iyV VE Ep, B ||ã
where 3F,n [5 Be, (xi)....,J fn... (xv-1)) is the binary string that indexes the element of (f 3E, E 1V,1) Hence, we have reduced the o.o.d minimax problem to an estimation problem on a binary hypercube (i.e., label recovery problem).
L
By definition, given n = oc, we have the following results
E | 1ālla
inf
åg (00.1V se(0.1)
h
max EraND |B.. - fā sollen
2 2 8R, (0,1) (0.3))
inf
h
Ep |i s/l sálles
inf
max (0(1)))
2 o0
where Eş represents the expectation with respect to Præ-
Now, are ready to analyze the L1 norm fee. sällen VBEE,0, ,3 E 13,11 By definition, derive the following results,
|Ro. - Sillea Σ Px = x;) (3) - Sās =
35,00.s - BB) =p-d du (3E.0..))
where du is the Hamming distance, i.e., dy (B1,8)) = E, 181, 32 and $1.5 and B2, are the j-th items of 81 and 3z. Now, the minimax problem becomes as measuring the distance between two strings Br., and 8,
inf sup
E [(. us]
jE EF PCP().T) ph
2 inf
Eædh (BR.a..).
To analyze this problem, we apply Theorem and have the following theorem:
16

---

Under review as a conference paper at ICLR 2023
Theorem (Minimax Bound), Given H² (Prøg.. .rg) aa= 2p (1 v1 - -h3) - 2phh,, we have the following lower bound for the o.o.d minimax problem,
V-1
inf sup Dr - fe. EF (CP(
54Eh
with E 10V1/(V 1)].
Proof. We need to upper-bound the squared Hellinger distance? H² (Pre... Pro) VB & that
satisfies du (B 1. Based the definition of the squared Hellinger distance, have
(v Pr (xi, - / (ro(xx,))
1² (Pree..PPs
Σ Σ
1=1 (E(0,13
V-1 p 112 Bernoulli
+ (23 1)h
+ (2,3g - 1)h
Bernoulli
2
2
the j-th term the above summation is nonzero and only Bg # By. in which case it equal to the squared Hellinger distance between the Bernoulli (La²) and Bernoulli (L+h) distributions. Thus,
For j E -V-VV
1]. -1,,
H² (Prge.. Pro) du (BE.N. H!2
Bernoulli
1 - h
Bernoulli
1+ h
2
2pp . dı (BE.00:)
1-h
+ h
V
2
2
= =p du (BE,O. B)
1 - /1 112
Inserting Theorem 5 with H (P Pr3) =2p (1 v1- -1-) = a S 2ph?, we obtain
inf
sup
ER.NDE y9) [((E,x))) -(())
f0 (EF(
ph
inf
V- Egdu(
sup
E(0.1
ph V ( VaE
2
P(V
1)/
v 2Fph?
We let p E and now we have
V-1
inf
sup
Ep, Ep - 2
J8 DEP(H.F)
54Eh
Next, we discuss the above theorem for different choices of h. First, given >
V-1
we have
E
V - if h
R
54Eh
E
"The squared Hellinger distance (P)QQQ) between and Q defined as H²
SA
(V 4P da
dx.
dx
17

---

Under review as a conference paper at ICLR 2023
When 0 S h < V consider = / V
As
we have
1
V
--1 if
cE (F)
54Eh
54
E
E
Combine the two cases of h. The proof is completed.
B PROOFS OF USEFUL LEMMAS AND THEOREMS
B. PROOF OF LEMMA 3
For any classifier f f - {0, 1) and any distribution P on x {0, 1}. we have
L()- - (()) = E ( # y) 1 (f* + Y) = ( -
(8)
where 1-) is the indicator function. If cond holds, 1(cond) = 1. Otherwise, ((cond) = 0.
Assuming that P ((h, F), have
L(F) L( [xx]]] f"
where the L1 norm is computed wxt the distribution of sampled data x, i.e. Ilf f"ll.,
Σx Pr(X xx] fx (x)..
B.2 PROOF OF LEMMA 4
Let f be any learning algorithm in F, and f be the learning algorithm which is closest to fă in L norm, i.e., f = argmin (e,1)E [lf fflll,, where f is indexed by B E {0,1) For any 3 E {0, V1,, we have
- fšll,, I 11 fll,, + + fālle, 2 - fōll..
(10)
where the first one is by the triangle incquality and the second one due to the definition of f.
B.3 PROOF OF LEMMA 6
First, by Eq. (6), we have [2th, (x) - 1| 2 h, Vx E X. Second, all learning algorithms with VC dimension bigger than V shatter these data point. There exists at least I E F, such that (x f(x) for all x E {x),...,yv) Thus, D C F),
B.4 PROOF OF THEOREM 5
As the total variation distance can be both upper- and lower-bounded by the Hellinger distance, we have
|P SIP Qlivv S (P..Q).
(11)
/
For any E θ let Ph denote the product of n copies of Po. i.e., the joint distribution of n i.i. samples from Pg. For any two 0, o' O with d (0, by letting P P and Q PR we have the following results
P - Pp lTV SH(PP Q7).
(12)
Besides, for any n pairs of distributions (Po.1, Po ..................... (Po.no Po where Po.. and Po are copies of Po and po', we have
H(PP, Q3) = H(Po. x ... x Po.n. Pø ... x Pe .n) S
Σ
HP
(13)
1=1
18

---

Under review as a conference paper at ICLR 2023
With the assumption (4) on the square of Hellinger, we have
| - Poller lrrv S
(PoPo)) Po S van.
(14)
With Theorem 11, the proof is completed.
B.5 BACKGROUND AND LEMMAS
We begin this section with some definitions.
The minimax risk M(0) is defined as
M(@)- inf sup Eold(O, (()),, ae
(15)
where θ a parameter set, A= ((Z) is an estimator to recover 9 from the observation of sample
Z sampled from indexed set {Po 0 E Q} of probability distributions finite set E. Eg represent the expectation with respect to Po, i.e.
Eg|d(0, (())) = Σ Po(s)d(0,0(=)) EEZ
(16)
Besides, the distance metric d(.;)) )) : x + R+ a pseudometric on Q and satisfies the following three properties,
Symmetry. d(0,0' d(0', 0)), V0,0 O; 2. Triangle inequality. d(e, 6') I d(f, 0*) + "''",,'),"" 40, 0r E Non-negative. d(0, 8') 2 0, v0,0 0 e.
The minimax risk (Eq. (16)) takes the infimum over all estimators Ô Ó(Z). In another word, this risk tries to find an estimator 0 to minmmize the worst-case risk supace Eg [d((0, (0))
We introduce the total variance distance based on the previous definitions. Definition 9 (Total Variation Distance). For any two probability P,Q P(Z), the total variation distance is
|P PP-QUIrv = Σ
Q(=)]
(17)
2
#E2
And it can be expressed as follows,
PP- Qliv= = Σ
min (()((()))(0)))))
(18)
2E2
In the literature, there is an important lemma named two-point method introduced by LeCam (1973) for getting lower bounds on the minimax risk,
Lemma 10 (LeCCam's Lemma). For any 0, 0' E O and any estimator Ô, we have
Eg|d(0, Egld(0,0(Z))] Eo[d((', (())) 2d(0,0') Σ min(Po(2),
2E
(19)
=d(0, 0' (1 - || - Po lrv).
Proof. Given point 2 E Σ, assuming Po(z) 2 Pg (2), we have
Po(2)d(0,0(()) + Por (=)d((( (())) (e(2))d(0,8(2))) + d(e', ((Z))) + (P) - (o()))d(e',8(12 (Po())(d(,0(())) a (()))
(20)
19

---

Under review as a conference paper at ICLR 2023
Similar, if Po(z) (2), have
Po(z)d(O, (()) 2 Pp)
(21)
Sum over Z with the definition of total variation distance. The proof is completed.
Next, we introduce important lemma.
Lemma 11. Supposing θ {0. 1)m, v0,0 8 E O, we consider the Hamming metric
(0.06')=
Σ 10, 0,1.
(22)
iE/ml
where 0g and 02 are i-th entries of and 0'. Then, we can lower-bound the minimax problem as
M (1
max (8,00 ==1
Po Po (ITTV)
(23)
Proof. Let be the uniform distribution on θ {0, 1)th and μii be the joint distribution of random pair (0,0') ) θ O, Vi E [m], such that the marginal distributions of both and 0 are equal to Then, the minimax risk can be lower-bounded as,
M(0) 2 inf E. [d( 0 (())) inf Σ E, (d(o,, (Z)))
8
vE(m)
inf E Inf,,,(((,
(24)
sE[m]
Σ kE(ms
E,g [d(O,, 0/) -1 1 Porllrv))
The first inequality is due to the supremum over all the prior distribution on θ while the third one is by definition and Eq. (18).
Next, since d(O,, 0,), E [m]. we have
M(O) 23
1
Σ
Ep, [d(O,, 01) (1 PPP Pe [v]]
iE|m]
Ep.
[1
PP Po [|rv]
2
iE(m]
(25)
min
[1 PP Po [|vv]
8,0' :d (0
iE(m]
(1
max 9.0' (g )=1
PP - Pe llv)).
2
C EXPERIMENTS
Due to the limitation space, we present the rest the experiments in this part.
C.I DETAILS OF ALGORITIIMS
include the following algorothms for two multi-domain image classification tasks:
ERM (Vapnik, 1991) is a famous machine learning algorithm that minimizes the sum errors across domains and examples.
20

---

Under review as a conference paper at ICLR 2023
IRM (Arjovsky et al., 2019) tries to learn invariant feature representation o(-) to capture the underlying causal mechanism of interest across domains such that the optimal linear classifier on top of that representation matches across domains.
GroupDRO (Sagawa et al., 2020) learns models minimizing the worst-case training loss over set of pre-defined groups while increasing the importance domains with larger errors.
Mixup (Xu et al.. 2020) guarantees -nnainnnnvvriance in continuous latent space and guides the domain discriminator in judging samples' difference relative to source and target domains.
MLDG (Li et al., 20) simulates train/test domain shift during training by synthesizing virtual testing domains within each mini-batch.
CORAL (Sun & Saenko, 2016) aligns correlations of layer activations in deep neural networks to learn domain-invenn invariinn features.
MMD (Li et al., 2018b) extend adversarial autoencoders by imposing the Maximum Mean Discrep- ancy (MMD (Gretton al., 2012)) measure to align the distributions among different domains, and matching the aligned distribution to an arbitrary prior distribution via adversarial feature learning.
DANN (Ganin et al., 2016) encourages the emergence of features that are discriminative for the main learning task on the source domain and indiscriminate with respect to the shift between the domains with an adversarial network.
C-DANN (Li al., 2018c) a variant of DANN matching the conditional distributions on features and labels across domains, for all labels.
C.2
DETAILS OF MUNIT
Table 4: Details of MUNIT architecture. We use MUNIT for the experiments.
#
Layer
1-3
Conv2D (in=d, out=64, kernels 3 x 3, padding=1) ReLUO
4-6
Conv2D (in=64, out=128, kernels = 3 x 3, padding=1) ReIUU + GroupNormmgeurrps--)
7-9
Conv2D (in= 128, 128, kermels = 3 x 3, padding=l) + ReLUU) + GroupNorr(ggurpps--)
10-12
Conv2D (in=128, out=128, kernels = 3 3, padding=1) + ReLU() + GroupNormtggurrps=3)
13
Global Average-Poolingg2D() x 1)
21

---

Under review as a conference paper at ICLR 2023
C.3 RESULTS FOR THE TEST- TEST-DOMAIN VALIDATION SET (ORACLE) MODEL SELECTION METHOD
ERM ColoredMNIST
ERM RotatedMNIST
IAM ColoredMNIST
RoiatedMNIST
Accuracy
Testing Accuracy
Testing Accuracy
Accuracy
0.50
0.10
0.72
0.70
0.9
0.00
0.00
0.44
0.60
9.-
0.5
102
10
of Training Domain
of Training Domain
# Training Domain
# of Training Domain
SoISredMNIST
DANN on RotatedMNIST
CDANN on ColoredMNIST
COANN on RotatedMNIST
meiiig Accuracy
Testing Accuracy
0.60
Testing Accuracy
Testing Accuracy
0.30
0.7
0.26
0.
0.r
0:40
0.60 0.6
0:34
050
042
10
100
Training
Training Domain
Training Domain
Training
on CaloredMNIST
on RetatedMNIST
GroupDRD CaloredMNIST
GroupDRO on RotatedMNIST
Testing Accuracy
Testing Accuracy
Testing Accuracy
0.24
Testur Accurcy
0.72 0.m0
0.66
338
234
032
1P?
10
LP Training Domain
of Training Domain
of Training Domain
of Training Domain
Testing Accuracy
Mixup on ColoredMNIST
Teszing Accuracy
1.0
Mixup RolatedMNIST
Tecting Accuracy
6.752
CaleredMNIST
Testing Accuracy
1.-
MMD on RolatedMN ST
6.725
8.700
0.
0.55
6.692
6.233
0.7
Training Domain
Training Domain
Training
Training Domain
MLDG on ColoredMNIST
MLDG RotatedMNIST
Testing Accuracy
Texting Accuracy
0.22
03r
0.70
0.50
0.c
167
of Training Domain
# of Training Domain
Figure 4: The experimental results on ColoredMNIST and RotatedMINST using ERM (Vapnik, 1991), IRM (Arjovsky al., 2019), GroupDRO (Sagawa et al., 2020), Mixup (Xu et al., 2020), CORAL (Sun & Saenko, 2016), MMD (Li et al., 8b), MLDG (Li et al., 201 8a), DANN (Ganin et al., 2016) and C-DANN (Li et al., 2018c) w.r. the number of training domain using the test-domain validation set (oracle) model selection method.
22

---

Under review as a conference paper at ICLR 2023
Table 5: The experimental results on ColOred.MNIST with MMD, DANN and C-DANN w.r.t the number of training domain using the test-domain validation set (oracle) model selection method.
MMD
DANN
C-DANN
4
0.6371540.02492
0.65319#0.00740 0.62982+0.01211
6
0.6717040.02795
0.69513=0.00170)
0.70268#0.00291
8
0.68003+0.02788 0.71480#0.00151
0.71387+0.00174
10
0.6831440.02778 0.72152+0.00100
0.7196540.0008/
12
0.68391+0.02993 0.71994+0.00107
0.71965+0.00088
14
0.6951640.02376 0.72537=0.00143
0.7257340.00121
16
0.6831440.02948 0.72692#0.00172
0.7252540.00140
18
0.69082+0.02680 0.72663+0.00101
0.72637+0.00087
20
0.68658+0.03038 0.7298420.00125
0.73000+0.00128
22
0.6851440.03015 0.7289100.00109
0.7312940.00095
24
0.69025#0.03098 0.73077#0.00072
0.73061+0.001322
26
0.6878440.03208 0.73238+0.00123
0.73113+0.00130
28
0.69278+0.02767 0.73090#0.00085
0.73084+0.00115
30
0.68967+0.03090 0.73126#0.00056
0.73206+0.00108
48
0.73923+0.00130 0.73479#0.00106
0.73534+0.00135
96
0..0581 0.73919#0.00111
0.7390620.00112
192
0.7439240.00127
0.74257#0.00109
0.7429540.00116
Table 6: The experimental results on RotatedMNIST with ERM, IRM, GroupDRO, Mixup. MLDG, CORAL, MMD, DANN and C-DANN w.r. the number of training domain using the test-domain validation set (oracle) model selection method.
FRM
IRM
CoopeRO
Micap
MLDD
CORAL
MMD
DANN
C-DANN
00951440000044
03592810.005
0103092000037
089972000019
0.898
000555500004400
04743500:00622
0.9945aa 00486
000099500000177
09678226000098
0.7975900
0.9494500.03333
0,940440:.0007
1016
01973350000100
20
08066100 10W
09000400.00111
019490140.00144
0191322000000
0000070000100
099874106000
99099-000007
0.001948:00122
0991364000077
099405-000100
0.9811740000
109777400000000
089485-0 11497
0.9942-0..0022
0.9614140.00661
14
0.976600000002 0.9921988.1199
0093814000003
0.9760000 00077
06833196000000
09700550000000
0.8055300.11500
10.00110
0.948840.001300
01099000000000 07559990004000
01934422000112
(305
099796250000100
030040001155
0:9788990000366
19966
0191004000011
0.885554 (0062
08187240 10M07
0.9677740:0111
20
0000110000004
0:488218.01690
1197371000000
0.9904 RO0R9
0985F720000077
09913920000115
0.8073.00.1159
|
0.000221..000m
0.877310000026
00936290000007 0.996560000077
0,911475000004
0.9226620
09966
009530930000033
1552
0:677764000007
0.9690583.00135
0.667550-00322
00833880000003
050005e0
019115260000062
26
0617210000077
119991 10
008800/0000006
00957710000077
0.099
11.6
0.900:5:100017
0.9110100.000t
000012220000007
0.8962200:1338
0.9396600000144
0.98345a
0.877960000046
00991122000079
080000a0
0.9724420000011
0.9995083000116
0990
0.98759e0
00964026000005
0309775001155
0.9729440
0.912229000669
092685-801540
11901660000044
009841-0000044
081125-0111000
0.97515-000177
08915440.00099
(106385un.0000
6052258001177
0.98467
0.9679220
0:91991200003
0.9880 20.00029
08140620
0.9969000.00.55
6.971189000191
2400022
0.955655000045
019887720 0002
019906720000033
0.9904555
0.9005420
0.9620770000074
23

---

Under review as a conference paper at ICLR 2023
C.4
RESULTS OF THE TRAINING-DOMAIN VALIDATION SET MODEL SELECTION METHOD
ERM on ColoredMNIST
ERM on RatatedMNIST
IRM on ColoredMNIST
IRM on RocatedMNIST
Texting Accuracy
Teating Accuracy
Testing Accuracy
0.22
36
0.70-
0.- M
0.00
6.60
0.44
12a
307
10
10
Training Demain
of Training Demain
#
Training Domain
# Training Domain
DANN on ColoredMNIST
RotatedMNIST
CDANN ColoredMNIST
CDANN RatatedMNIST
Tacting Accuracy
Testing Accuracy
Testting Accuracy
0.
Masgeon Accuracy
0.725
0.
0.72
0,700
0.
0.70
5.75
0.2
6.99
2.535
0.7
0.64
10"
10
102
10"
12t of Training Domain
30
of Training Domain
of Training Domain
# of Training Domain
CORAL on ColoredMNIST
CORAL on RotatedMNIST
GroupDRD on ColoredMNIST
GroupDRO on RotatedMNIST
0.4
Testing Accuracy
Testing Accuracy
0.14
0.2
0.0
0.26
Testing
0.00
0.66
0.
0.00
334
0.66
0.60
Training Domain
Training Domain
Training Domain
Training Domain
Mixup ColOredMNIST
Mixup RotatedMNIST
MMD on ColoredMNIST
MMD on RotatedMNIS
Accuracy
0.75
Sesting Accuracy
Testing Accuracy
sangng sastin Accuracy
0.30-
0.
0.70
8.435
3.
0.65
0.3
6.435
122
16
10
of Training Domain
# of Training Demain
of Training Domain
# of Training Domain
MLDG on ColoredMNIST
MLDG RotatedMNIST
Testing Accuracy
Testing Accuracy
0.00
0.0
Training
Training Domain
Figure 5: The experimental results on ColoredMNIST and RotatedMINST using ERM (Vapnik, 1991), IRM (Arjovsky et al., 2019), DRO (Sagawa et al., 2020), Mixup (Xu et al., 2020), MLDG (Li al., 2018a), CORAL (Sun & Saenko, 2016), MMD al., 2018b), MLDG (Li et al., 201 (a), DANN (Ganin et al., 2016) and C-DANN (Li et al., 2018c) w.r.t the number of training domain using training-domain validation set model selection method.
24

---

Under review as a conference paper at ICLR 2023
Table The experimental results on CoLOTedMNIIT with MMD, DANN and C-DANN w.r.t the number of training domain using the suining-domain validation set model selection method.
MMD
DANN
C-DANN
4
0.63538+0.02599
0.62982=0.01211
0.65068+0.00695
6
0.66993+0000212 0.69510#0.00172
0.69963#0.00317
8
0.67565+0.03004 0.71342+0000234
0.7134540.00196
10
0.6815440.02749 0.72152+0.00100
0.71956+0.00081
12
0.6818640.03106 0.71911+0.00109
0.71891+0.00122
14
0.69503#0.02374 0.72483+0.00140
0.7257340.00121
16
0.6826340.02939 0.72692#0.00172
0.7247640.00154
18
0.6898340.02663 0.7256330.00133
0.72598+0.00089
20
0.6848140.03156 0.7294940.00117
0.72901+0.00111
22
0.6823440.08114 0.72862+0.00115
0.73109+0.00105
24
0.6884840.03216 0.73055#0.00059
0.73061+0.001322
26
0.6878410.03208 0.73190#0.00146
0.7311340.00130
28
0.69221#0.02758 0.7308740.00084
0.73003+0.00086
30
0.6873940.03204 0.73068+0.00036
0.73132+0.00108
48
0.73826#0.00150 0.73373+0.00128
0.73453+0.00114
96
0.6938840.03278 0.73868#0.00131
0.7389040.00117
192
0.74353+0.00140 0.74228+0.00118
0.74247+0.00124
Table 8: The experimental results RotATedMNIST with ERM, IRM, GroupDRO. Mixup. MLDG, CORAL, MMD, DANN and C-DANN w.r.t the number of training domain using the training-domain validation set model selection method.
ERM
IKM
GouyORO
Misap
MLDG
CORAL
MMD
DANN
CANNN
0.55014000445
0070005-0 17661
0.707740 10825
0.077660000000 00
1096622000111
04739500002440
0199941000225
00969900/00448
09690030.00999
062999003168
O 09550289001044
0U6744 00181
09953220 00105
09911990000023
10659
034604601000211
03475860000133
1097006110011
0075860001914
05778k00 00100
61747740060053
000076-0011000
0.9778700 18
0.995094000005
01984400000044
03005560000132
14
0097800e.000022 0.922990031993
0,9331690000300
0.96602n 00077
0:922020 00052
0.9783330.00115
11.50
0.903110000000
0.9648460.00180
16
199921501001 0.7899960001000
099872211 0092714000003
(0110
0S5ibiee (006)
U1T10000000000
0.96099900000866
20
0.99065un.00000 03488228.31469
0997128900123
099999un 00100
09635 160 09053
0.9812686:00116
0.0713a0 11535
0.9699220.000 0030
0.967340000125
22
10000 03999550000007
00766550000085
019557720
0.930050000007
0.099666111150
0.6073511000991
0.9672240000444
(196115u 90066
00000111.0060
09990040000044
0.667Sun 00061
00839900 00056
009856100:005)
080045a0 11573
0.000/500:00333
0.9975400.00440
28
18155/00000166
D 109796600000744
0.9835 00000
019776/0000066
10030010.00011
0,0919
11:5
0.9734400.0001
0.964410.0011
0.9634Rn 00064
09205540,00477
0.980220000009
0:97472200000
00999999000006
13577
0.9729400.00000
0.9741969:0019
01987750100411
09268550-0220
29600000
1996611010000
01965220000006
05000maa 11594
0.9731598..00255
09937749:00000
W
13 1098555
90745-00 (00MW
019015400/0041
019000 40.020079
0181405440 11690
0.97660-0.0011
019771540.00111
119078an.0000)
09001120.08022
0.998560000052
0:9035420.000300
(0.906720::0003
0.990450000000
0.9004350.00062
0.96207 10000070
25

---

Under review as a conference paper at ICLR 2023
C.5 RESULTS OF -OWNE--NE-DOMINNCCOO COOSS-VALIAATONN METHOD
Table 9: The experimental results on ColOredMNIST with ERM, IRM, GroupDRO. Mixup, MLDG, CORAL, MMD, DANN and C-DANN w.r.t the number of training domain with the lnave-one-
domain-out cross-validee coss-validation method.
BRM
IRM
GrigUR0
Micap
MEDG
DORAL
MMD
DANN
C-DANN
0.70399000911
0.708
019944
0.704050000000 104
0.663 229007858
0.9922500000099
0.721 363
00243
01150050000011
0 M0475
0669
0771922000000
0.714450 9000)
0.7222900
(198208900554)
0.731964 30000
(171688-4) 00753
(733166090000
110000400 (8530
12
0.72922 00041
0865490002.00 mo
8.7286300 00485
0 073433000000
702006000000572
B.6 (111155000000 0844
0 (21511000000))
0.72634000017
065743en 02509
0.1225500000133
00570
0729222000455
(1099250011220
02855
0.2279
0.72455a 0634
00405
0.7266220
0.73048:0 00533
0.702280000000 00550
(189557000854
72332220
72255500.00665
0.
0.7264 02564
02331
0 0722188510042
07208221100017
0 87744440180024
0. 7206775000003
0697124000778
0.73MB4 DM
01786-001011
010440000 69874
077228000726
06708330:02748
0723680
(172554.0180474
0172912200038
00221550000042
01911990007661
22500200880222
7278010000088
34
007069 000435
068145000125
079718-000971
(.72782 000613
0173155 (0/044
(1344010.00000
08911410000061
0 000995
735966 007077
26
007385
066972002262
A7325528
0.7279920000001
0.73215:h 00307
0.7226020
(19550000006677
0 0.728220 00023
0.277550000000
0.722320 0663
0.7845441 10011
(1085220000896
017759900000070
017817-900079
006116000100
0178999010077
(172939-0000666
0171565-010000
(173160-0:0067
07117740000331
Table 10: The experimental results RotatedMNIST with ERM, IRM, GroupDRO, Mixup, MLDG, CORAL, MMD, DANN and C-DANN w.r.t the number of training domain with the leave-one-
domain-out cross-validation method.
BRM
IRM
GragDRO
Missp
MLDG
CORAL
MMD
DANK
CADAN
0170155000007
0.766556 12000
517555-0015900
71007-0087750
099889-000144
438900009000
000112-000088
0 0.9012-0 000574
(1968000010 -000000000000
0. 109998-00000 90036
881156-003111 31199
01990000000744
0996
8
01973778000166
0.967545 00272
0.9002 003004
0.971880 00291
0.9445500000236
08171330.31556
0.9554820 00060
000535920.000122
0127
0.9720al
0.97322e (035)
(19038900 0121
0UN6 (043)))
(1971229000000
013100000166
(197595-4) 00003
09963-000075
(199386690199
080565500 31519
09672446 D00
14
019789t
0.6695511 777
(1999225100136
019005551
D190T000 00196
0.9834 00206
08895400004441
8.99641
00:0066
0.97954 00221
0.9454
010010000.00001
17901
969655 10,0195
9000 00.0085
0:969009000221
09977050 0495
0.9815500:0055
(9931990.00225)
01844230031812
019695720
0.9727200000544
20
0 (190042g1)
0.5 01969555000185
08232460) 31930
0 (17000a))
0.50 19916690-00126
0196500000001
0.9705-00
000266
(196743-0
019547-000064
(190166-0000000
018130044 17666
090133-000177
00 0198
0198676611102255
119660
0.96511
000057
00479500 264
0.9996 i 001774
0 0096223 / 00007
0198763 (0/0012)
0198767 00188
0.9350000 000002
99554 10100160
0.98562 00188
09852920
00000
0.961 00185
0 0,9832220 0018
0.90062:00 00009
0.9868920.00113
0.82336at) 32499
0 0.9750820
099757780.0047
0.90099ea
019099761
1000
(19859901)
015897221)
(10649990000034
26

---

Under review as a conference paper at ICLR 2023
on CaloredMNIST
Testin Accursc)
1.00
0.55
on
Accuracy
0.72
0.73
GrrupDDO ColoredMNIST
Testing Accuracy
GroupDRO on RotatedMNIsT
0:50
Testing
0.00
3.5
2.0
0.0
3.75
20
20
13
20
20
* of Training Domain
of Training Domain
of Training Domain
* of Training Domain
Mixup on ColoredMNIST
Mixup on RotatedMNIST
MMD on ColoredMNIST
MMD on RotatedMNIST
Testing Accuracy
Testing Accuracy
0.65
0.50
0.65
0.00
0.0
Testing
0.00
0.65
0.5
0.00
0.55
0.79
Training Domain
Training Domain
Training Domain
of Training Domain
ColoredMNIST
MLDG RotatedMNIST
Testing Accuracy
0.75
Accuracy
0.70
0.00
0.6
of Training Domain
# Training Domain
Figure The experimental results on ColoredMNIST and RotatedMINST using DRO (Sagawa et al., 2020), Mixup (Xu et al., 2020), MLDG (Li et al., 2018a), CORAL (Sun & Saenko, 2016), MMD (Li et al., 2018b), and MLDG (Li al., 2018a) w.r.t the number training domain with the leave-one-domain-ouu cross-validation method.
C.6 RESULTS OF ABLATION STUDY
ERM ColoresMNIST
ColoredMNIST
ERM on ColoredMNIST
IRM on ColoredMNIST
Tosting Accurary
Dostion sccurais
375
Besting Accuracy
mi Testing Accuracy
c.
278- ass-
mm
202000
M.M
M.MT
2--20000
* of Training Domain
of Training Domain
of Training Domain
1P
of Traininn Domain
365
10P
10000
Figure 7: The experimental results on ColoredMNIST using ERM (Vapnik, 1991) and IRM (Arjovsky et al., 2019) w.r.t the number of training domain using the waining-domate validation model selection method. The left two figures show the results with different architectures, iee., MUNIT and VGG11 (Simonyan & Zisserman, 2014), while the left three figures present the corresponding results with different number of n.
27

---

Under review as a conference paper at ICLR 2023
Table 11: The experimental results on ColoredMNIST with ERM w.r. the number of training domain using the test-domain validation set (oracle) model selection method with changing the number of training images from each domain.
1000
2000
4000
7000 (ori)
8000
10000
20000
40000
70000
4
0.5150
0.5050
0.5815
0.6697
0.7080
0.6976
0.7261
0.7324
0.7372
0,5350
0.5463
0.6719
0.7138
0.7146
0.7194
0.7308
0.7381
0.7414
0.5150
0.5988
0.7129
0.7203
0.7133
0.7251
0.7318
0.7392
0.7421
10
0.5587
0.6506
0.7314
0.7244
0.7194
0.7252
0.7369
0.7399
0.7432
12
0.5913
0.662.5
0.7202
0.7284
0.7241
0.7264
0.7379
0.7417
0.7447
14
0.5387
0.6944
0.7211
0.7291
0.7237
0.7296
0.7405
0.7435
0.7468
16
0.5637
0.6969
0.7329
0.7274
0.7237
0.7296
0.7391
0.7434
0.7465
18
0.6300
0.6981
0.7375
0.7314
0.7261
0.7264
0.7416
0.7447
0.7469
20
0,5913
0.6850
0.7229
0.7311
0.7267
0.7319
0.7409
0.7449
0.7477
22
0.5150
0.7150
0.7396
0.7323
0.7271
0.7314
0.7418
0.7455
0.7478
24
0.6713
0.6969
0.7335
0.7357
0.7294
0.7320
0.7413
0.7463
0.7486
26
0.6425
0.6956
0.7366
0.7351
0.7281
0.7335
0.7435
0.7463
0.7486
28
0.6800
0.7044
0.7405
0.7341
0.7300
0.7348
0.7432
0.7465
0.7486
30
0.6300
0.7144
0.7372
0.7333
0.7270
0.7334
0.7426
0.7464
0.7489
48
0.6950
0.7231
0.7436
0.7390
0.7347
0.7370
0.7459
0.7477
0.7501
96
0.6725
0.7331
0.7414
0.7432
0.7376
0.7408
0.7492
0.7499
0.7518
192
0.6650
0.7306
0.7514
0.7439
0.7419
0.7439
0.7505
0.7512
0.7525
Table 12: The experimental results on ColOredMNIST with IRM w.r.t the number of training domain using the test-domain validation set (oracle) model selection method with changing the number of training images from each domain.
#
1000
2000
4000
7000 (ori)
8000
10000
20000
40000
70000
4
0.5675
0.5519
0.5760
0.5517
0.6206
0.5889
0.6425
0.6562
0.6598
0,5513
0,5363
0.6382
0.5915
0.6253
0.6354
0.6535
0.6793
0.6974
8
0.5150
0.5587
0.6452
0.6278
0.6647
0.6663
0.6578
0.6976
0.7031
10
0.5275
0.6225
0.6625
0.6685
0.6684
0.6915
0.6876
0.6987
0.7093
12
0.5200
0.6106
0.6859
0.6968
0.7020
0.6846
0.7006
0.7049
0.7144
14
0,5150
0.6444
0.6989
0.6709
0.6864
0.6687
0.6976
0.7089
0.7136
16
0.5387
0.6312
0.7077
0.6777
0.6961
0.6994
0.6966
0.7086
0.7200
18
0.6462
0.6825
0.7083
0.7031
0.6737
0.6860
0.7019
0.7146
0.7175
20
0.5737
0.6400
0.6938
0.6958
0.7000
0.6935
0.7064
0.7148
0.7212
22
0.6200
0.6706
0.6980
0.6935
0.6964
0.7004
0.7144
0.7101
0.7203
24
0.6138
0.6550
0.7241
0.6908
0.7024
0.7007
0.7063
0.7183
0.7238
26
0.6100
0.6625
0.6917
0.6995
0.7121
0.7034
0.7128
0.7177
0.7239
28
0.6375
0.6787
0.7190
0.6997
0.7067
0.7200
0.7086
0.7224
0.7224
30
0.5787
0.5844
0.7284
0.7113
0.7063
0.7063
0.7134
0.7190
0.7244
48
0.6488
0.6825
0.7153
0.7219
0.7016
0.7081
0.7161
0.7221
0.7249
96
0.6488
0.7019
0.7308
0.7182
0.7157
0.7163
0.7211
0.7286
0.7334
192
0.6475
0.7031
0.7196
0.7287
0.7213
0.7271
0.7265
0.7310
0.7345
28

---

Under review as a conference paper at ICLR 2023
Table 13: The experimental results on ColoredMINIST with ERM w.r.t the number of training domain using the training-domen domain validation set model selection method with changing the number of training images from each domain.
1000
2000
4000
7000 (ori)
8000
10000
20000
40000
70000
4
0.5150
0.5050
0.5815
0.6697
0.7080
0.6916
0.7258
0.7323
0.7372
0.4850
0,5463
0.6719
0.7135
0.7146
0.7165
0.7303
0.7381
0.7409
0.4888
0.5988
0.7129
0.7183
0.7081
0.7251
0.7311
0.7383
0.7417
10
0.5587
0.6506
0.7314
0.7226
0.7194
0.7250
0.7369
0.7399
0.7430
12
0.5913
0.662.5
0.7202
0.7280
0.7241
0.7264
0.7379
0.7417
0.7441
14
0,5212
0.6944
0.7208
0.7289
0.7169
0.7296
0.7405
0.7431
0.7468
16
0.5637
0.6969
0.7329
0.7268
0.7237
0.7276
0.7391
0.7434
0.7462
18
0.6300
0.6981
0.7375
0.7304
0.7261
0.7264
0.7409
0.7447
0.7467
20
0,5913
0.6850
0.7229
0.7305
0.7254
0.7306
0.7409
0.7449
0.7477
22
0.5000
0.7150
0.7387
0.7323
0.7259
0.7309
0.7418
0.7450
0.7478
24
0.6713
0.6969
0.7335
0.7330
0.7277
0.7304
0.7413
0.7463
0.7483
26
0.6425
0.6956
0.7360
0.7350
0.7281
0.7335
0.7435
0.7463
0.7486
28
0.6800
0.7044
0.7405
0.7336
0.7257
0.7348
0.7432
0.7465
0.7480
30
0.6300
0.7144
0.7372
0.7331
0.7266
0.7316
0.7426
0.7456
0.7487
48
0.6950
0.7231
0.7436
0.7386
0.7347
0.7370
0.7459
0.7477
0.7501
96
0.6725
0.7331
0.7399
0.7427
0.7363
0.7394
0.7492
0.7499
0.7518
192
0.6650
0.7306
0.7514
0.7437
0.7419
0.7438
0.7505
0.7512
0.7525
Table 14: The experimental results on ColoredMNISS with IRM w.r.t the number of training domain using the training- validation set model selection method with changing the number of training images from each domain.
#
1000
2000
4000
7000 (ori)
8000
10000
20000
40000
70000
4
0.5675
0.5281
0.5760
0.5500
0.6126
0.5889
0.6425
0.6562
0.6598
0,5513
0,5363
0.6382
0.5910
0.6253
0.6354
0.6535
0.6793
0.6974
8
0.4913
0.5587
0.6452
0.6278
0.6647
0.6663
0.6576
0.6976
0.7031
10
0.5200
0.6225
0.6625
0.6685
0.6684
0.6915
0.6876
0.6987
0.7093
12
0.4750
0.6106
0.6859
0.6968
0.7004
0.6846
0.7006
0.7049
0.7144
14
0.4963
0.6444
0.6989
0.6709
0.6864
0.6687
0.6976
0.7089
0.7134
16
0.4850
0.6312
0.7077
0.6777
0.6961
0.6994
0.6966
0.7086
0.7200
18
0.6462
0.6825
0.7083
0.7031
0.6724
0.6830
0.7010
0.7146
0.7167
20
0.5737
0.6400
0.6938
0.6957
0.7000
0.6904
0.7064
0.7148
0.7212
22
0.5825
0.6706
0.6944
0.6935
0.6964
0.7004
0.7143
0.7101
0.7203
24
0.6138
0.6550
0.7241
0.6908
0.7024
0.7007
0.7063
0.7183
0.7238
26
0.6100
0.6625
0.6917
0.6995
0.7121
0.7034
0.7128
0.7177
0.7239
28
0.6375
0.6787
0.7190
0.6997
0.7067
0.7200
0.7086
0.7224
0.7224
30
0.5625
0.5844
0.7284
0.7113
0.7063
0.7063
0.7134
0.7190
0.7226
48
0.6488
0.6825
0.7153
0.7219
0.6959
0.7081
0.7160
0.7221
0.7249
96
0.6488
0.7019
0.7308
0.7182
0.7157
0.7133
0.7211
0.7285
0.7334
192
0.6475
0.7031
0.7196
0.7287
0.7213
0.7271
0.7265
0.7306
0.7335
29

---

Under review as a conference paper at ICLR 2023
Table 15: The experimental results ColoredMINIST with ERM w.r. the number of training domain
using the training-domain validation set model selection method with MUNIT and VGG11.
MUNIT
0.6697
0.7135
0.7183
0.9226
0,7280
0,7289
0.7268
0.7330
0.7305
0.7323
0.7330
0.7350
0.7336
0.7331
0.7386
0.7427
0.7433
VGG11
0.7085
0.7324
0,7417
0.7413
0.7428
0.7507
0.7810
0.7997
Table 16: The experimental results ColoredMNIST with IRM w.r.t the number of training domain
using the training-domain validation set model selection method with MUNIT and VGGI1.
MUNIT
0.5500
0.5910
0.6278
0.6685
0.6968
0,6709
0.6777
0,7031
0.6957
0.6935
0.6908
0.6995
0.6997
0.7113
0.7219
0.7182
0.7287
VGGIL
0.5589
0.5716
0.6585
0.6571
0.6743
0.7379
0.7603
Table 17: The experimental results ColOredMNIST with ERM w.r. the number of training domain
using the test-domain validation set (oracle) model selection method with MUNIT and VGG11.
MUNIT
0.6697
0.7138
0.7200
0.7244
0,7284
0.7291
0.7274
0,7314
0.7311
0,7323
0.7357
0.7351
0.7341
0,7333
0.7390
0.7432
0.7439
VOGIL
0.7087
0.7324
0.7417
0.7442
0.7456
0.7507
0.7553
0.7810
0.7997
Table 18: The experimental results ColOredMNIST with IRM w.nt the number of training domain
using the test-domain validation set (oracle) model selection method with MUNIT and VGG11.
26
MUNIT
0,5517
0.5915
0.6278
0.6685
0.6968
0,6709
0.6777
0,7031
0.6958
0.6935
0.6908
0.6995
0.6997
0.7113
0.7219
0.7182
0.7287
VGGUL
0.5589
0.5803
0.6659
0.6608
0.6548
0.6571
0.6743
0.7036
0.7382
0.7603
30


Reviews:
[{"review_id": "hM5QwGRCR1", "reviewer": "Reviewer_qD5b", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper undertakes a minimax analysis of a formulation of the domain generalisation problem. When considering an optimistic case where one has access to infinite data from a finite number of domains, it is determined that the number of required domains to obtain a solution within performance of the Bayes optimal classifier scales as $poly(1/\\epsilon)$. In addition, the paper includes an empirical investigation into how well existing algorithms scale with the number of training domains, and it is shown that the empirical behaviour agrees with the theoretical analysis.", "summary_of_the_review": "Both the theoretical and empirical contributions make this a good paper, but the presentation of the experimental results could be improved.\n\nI will increase my score to 8 if all weaknesses are addressed.", "strength_and_weaknesses": "### Strengths\n* Given that a lot of papers in the DG community make dubious claims about the efficacy of their methods, investigation into fundamental hardness of DG is a very timely and significant research direction. To my knowledge, this is the first such paper that provides this kind of hardness result in a DG setting.\n* The result it quite intuitive and provides further support from a different perspective to a quite new thread on theoretical DG research pointing to model complexity being a significant factor in determining the o.o.d. performance of a model.\n* There is good discussion of prior work on theoretical analysis of domain generalisation, and the related work on constructing minimax bounds using similar techniques.\n* The experimental results provide a nice corroboration of the theoretical findings.\n\n### Weaknesses\n* The paper could use a bit more in the way of a problem definition; a more explicit definition of $\\mathcal{P}$ and $P_e$ would make the paper much more readable. The current problem setup jumps immediately into defining the specific form of distribution used in the process of proving the minimax bound. While it is useful to introduce this family of distributions at some point, I think it would be good to first set the scene a bit by introducing the form of bound that will be proved first. It would then make sense to introduce the hard instance, mentioning that it is of course contained in the set of all possible instances that the bound maximises over.\n* The presentation of the experimental results is not very easy to understand. It would be better if the domain-efficiency measurements were not reported in tables or many plots that each present a single dataset-method combination. Instead, it would be both more compact and easier to interpret if the tables were discarded and the results summarised by constructing a single plot for each dataset, with multiple lines---one for each method.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "OzuGm-qLyJd", "reviewer": "Reviewer_8Svr", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper asks the question: Is the poor performance of domain generalization (DG) algorithms a consequence of not having access to sufficiently many training domains?  The authors prove a lower bound which suggests that the answer to this question is \"yes.\"  They then provide experiments meant to reinforce this theory.", "summary_of_the_review": "In summary, this paper takes an interesting perspective on DG.  Namely, it seeks to show impossibility results based on the number of training domains.  Unfortunately, I found it quite challenging to read this paper given that the construction used in the main result is not described in sufficient detail in the main text.  Without defining key quantities, e.g. the domain generalization Bayes optimal classifier and the dependence on $E$ and $n$, I find it rather challenging to interpret the main result.  I also feel that the experiments have the following flaw: it's either the case that (a) the experiments invalidate the theory, as strong performance is achieved with fewer domains than the VC-dimension of $\\mathcal{F}$, or (b) the assumptions of the theorem do not apply in the experiments, in which case the experiments have no real bearing on the contribution of this paper.  For these reasons, while this paper makes some interesting points, I am going to recommend that this paper not be accepted.", "strength_and_weaknesses": "### Strengths\n\n**Approach to DG.**  In some sense, this is an insightful way of thinking about DG in my opinion.  To elaborate, in general, DG is impossible, given that the training and test domains could be arbitrarily different.  In this way, lower bounds can provide concrete settings where DG is impossible, which may give us insights into when DG is theoretically possible.  I think the direction of this paper is promising for this reason -- it seeks to give a simple, theoretical setting which can shed light on the problem.\n\n### Weaknesses\n\n**Problem setup.**  Section 3 is not written in an accessible way.  In this sentence:\n\n> \"We will use $L(f)$ to represent the expected 0-1 loss of classifier f w.r.t. the mixture of data distributions of all domains\" \n\nWhat do the authors mean by \"the mixture of data distributions of all domains?\"  The notion of \"domains\" has not been introduced yet in this paper.  And even if they had, the authors do not define what they mean by \"mixture.\"  The authors then introduce $\\mathcal{P}$ as the \"distribution of distribution.\"  Having read the paper several times over, I'm still not sure what this means.  Are the authors making an assumption that the domains are drawn from a probability distribution over domains?  Should it be obvious what the \"domain distribution\" is without defining it?  \n\nFurthermore, I don't understand the relationship between $(X,y)$ and $(x^e,y^e)$.  $(X,y)$ take on the distribution over the \"mixture of data distributions\" whereas $(x^e,y^e)$ are defined with respect to a particular distribution.  So again, the question is, how does the mixing work WRT $P^e$ (the distribution over the $e$th domain's data)?\n\nIt's also unclear why the authors define $\\mathcal{P}$ in the way that they do in the \"Problem setups\" section.  One point of confusion is that $\\mathcal{P}$ is referred to as a \"domain distribution,\" whereas earlier $P^e$ was referred to as \"the data distribution of the $e$-th domain.\"  So from the perspective of the reader, it's now unclear whether $\\mathcal{P}$ is a distribution over data in a particular domain or the distribution of data in a particular domain.  The \"definition\" of $\\mathcal{P}$ does not clear this up, as $\\mathcal{P}(h,\\mathcal{F})$ reflexively uses $\\mathcal{P}$ without defining it.   Furthermore, from the definition it's not clear how $\\mathcal{P}(h,\\mathcal{F})$ depends on $\\mathcal{F}$, or whether it depends on $\\mathcal{F}$ at all -- $\\mathcal{F}$ never appears in the definition.  A similar point could be made regarding how $h$ relates to $\\mathcal{P}$.  If $\\mathcal{P}$ is not a distribution over data in a particular domain (as is suggested in various places and contradicted in others), then how id $\\mathcal{P}$ related to $h$.  If, on the other hand, $\\mathcal{P}$ is a domain distribution, what is the relevance of $P^e$?\n\nPutting all this aside, it's also unclear why the authors consider this model.  What makes this Bernoulli setting interesting.  The authors are interested in showing impossibility for domain generalization.  Therefore, one would assume that they would want to convince the reader that their model is natural and flexible, in the sense that this model is one in which we might hope that DG would be theoretically possible.  However, no such discussion is given.  Without convincing the reader that this is the right model to study, it's much harder for the reader to get a sense for why this result makes a contribution.  To this end, a strong point of reference is the paper *The Risks of Invariant Risk Minimization* (https://arxiv.org/pdf/2010.05761.pdf), in which the authors prove impossibility results for IRM.  This paper has gained traction in part due to the fact that the Gaussian model they consider is natural -- meaning that it is one in which one would hope DG would be possible.  The authors spend a considerable amount of the preliminaries section discussing why this model is natural, and they propose various extensions to validate this.  I think that adding a similar discussion to this paper would strengthen the contribution.\n\nThe problem setting would be clearer if the authors could define what they mean by the Bayes optimal classifier in this setting. Is the Bayes optimal classifier defined WRT the average over some family of distributions?  Is it defined as the classifier that can do well on domains in the minimax sense (vis-a-vis (1))?  Without knowing this, it's hard to judge the significance of the results.  Relatedly, it's not clear how $E$ and $n$ factor into (1).  The optimization problem in (1) is a population-level problem.  If the authors have another problem in mind wherein there are only finitely many domains and finitely many data points sampled per domain, they should state this problem and discuss its relationship to (1).\n\nOther questions: \n\n- What does it mean for $x$ to be the \"implementation\" of $X$?  Does this mean that $x\\sim X$?  \n- What do the authors mean when they call this setting \"our hard instance?\"  What is hard about it?  Is this in contrast to an easier instance?\n\n**Implications of the lack of preliminaries on understanding Thm. 1.**  As described above, I expect that many readers would be confused after reading the preliminaries in Section 3.  The result of this is that it's difficult to grok Thm. 1.  For instance, it's unclear what it means for $n=\\infty$ vis-a-vis eq. (1).  As $n$ does not seen to play an explicit role in this problem, there's no way to interpret $n=\\infty$.  Furthermore, as the Bayes optimal classifier has not been defined in this domain generalization setting, it's unclear what (2) means.  \n\nFurthermore, it's not clear what is \"information theoretic\" about this bound, as mentioned by the authors.  Is this due to the proof technique, i.e. were techniques from information theory used to prove the result?\n\nThe authors say that their result stands in contrast to the results of DomainBed, where few training domains are available.  I think that this statement is not necessarily true.  Consider the sentence: \n\n> \"Theorem 1 predicts the failures of future algorithms on these datasets and attributes the poor performance of existing o.o.d. algorithms to the lack of training domains.\"\n\nThis would only be true if the theory directly applies to DomainBed.  Clearly, as the domains are not generated by this Bernoulli model, the lower bound in Thm. 1 does not hold for datasets like ColoredMNIST.  A more nuanced analysis of the implications of this result is needed, rather than claiming that this bound uniformly explains away the poor performance of algorithms used on DomainBed.\n\n**Comparison to past work.**  The authors discuss the differences between their work and that of another paper in Section 3.  However, due to the lack of details given about their approach, it's hard to understand these differences.  For instance, the authors say that they have a \"two-stage data generative process.\"  Why is this an important difference?  What was done in past work?  What is the so-called \"supporting space\" and how is it relevant to thsi problem?  \n\n**Experimental presentation.**  It would seem necessary to disentangle the effect of having finitely many data points from having finitely many domains in these experiments as well.  Could it not be the case that test accuracy rises given more domains simply because the classifier has more data points to train on.  It would seem necessary to try an experiment where the total number of data points is fixed, and so as the classifier has access to more domains, it simultaneously has access to fewer samples per domain.\n\nHow did the authors pick the number 192 -- the maximum number of training domains?\n\nThe authors show that the test performance increases as a function of the number of domains used at training time.  Indeed, on ColoredMNIST, the authors achieve results near to the optimal score of 75% (given that there is label-flipping) in Table 2.  This indicates that given only ~200 training domains, DG is possible in this setting.  This seems to violate the theory, because Thm. 1 indicates that $E$ must be larger than the VC dimension of $\\mathcal{F}$.  As ColoredMNIST uses neural networks, the VC dimension is rather larger here -- certainly larger than 192 given that a linear classifiers would have a VC-dimension of 784+1 for MNIST, and NNs should have a larger VC-dimension than do linear classifiers.  Of course, one could argue that the setting of the theorem does not apply to Colored/Rotated-MNIST.  However, if this argument is used, then it begets the question: How are these experiments serving to reinforce the message given in Thm. 1?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "DslavbG0b9_", "reviewer": "Reviewer_2RNe", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper argues the existing drawback of OOD learning algorithms is because of lacking sufficient domains. The authors provide a hardness result that all learning algorithms require at least $poly (1/\\epsilon)$ number of training domains to achieve an $\\epsilon$ excess error.", "summary_of_the_review": "See the comments above", "strength_and_weaknesses": "\n### Strength\n- The authors provide theoretical and empirical evidence to justify their claims.\n\n### Weaknesses\n- Main assumptions made are not clearly stated. It is not clear what kind of properties of the DG problem you have used for deriving the theory (Thm. 1).  It would nice if the authors could re-organize the writtings, especially the proof techniques, so that one can follow the details in an easier way.  \n-  There have been plenty of works on analyzing the domain complexity (or related ones) for DG or unsupervised domain adaption, to name a few [Zhao et al. 2019, Wang et al. 2022, Chen et al. 2021].   They have derived bounds by taking into account refined properties of distribution shift problem being studied. For example, the discrepancy between source and target domains, difference of the underlying labeling processed et al.  This kinds of “refined” conclusions would benefit more for studying the DG/DA problems. So would it be possible to improve your conclusion by considering more refined properties of DG?  If so, what would you do then?  \n\n- Tightness of the bound in Thm. 1.     The tightness of the bound matters a lot. Have you studied the tightness by considering some well-designed problem instances of DG?   This might also be related to the above concerns, if more refined assumptions are taken into account, the bound would become sharper.  \n\n- More discussions with related works are needed to understand/justify  the main theoretical result of this paper. \nFirst, the original IRM settting [Arjovsky et al., 2019], including those who argue about the drawbacks of IRM [Kamath et al, 2021; Rosenfeld et al., 2021; Ahuja et al., 2021] all obey the general definitions of OOD generalization (thus the settings in this paper as well). However, they generally have results that prove IRM is sufficient to find the underlying optimal classifier, given certain a mild number of environments (e.g., linear w.r.t. the number of feature dimensions). These conclusions do not appear to be in line with the conclusion in this paper. Can you explain about the implications of this observation?   \n\n### References  \n\nZhao, H., Des Combes, R. T., Zhang, K., & Gordon, G. (2019, May). On learning invariant representations for domain adaptation. In International Conference on Machine Learning (pp. 7523-7532). PMLR.\n\nWang, H., Si, H., Li, B., & Zhao, H. (2022). Provable Domain Generalization via Invariant-Feature Subspace Recovery. arXiv preprint arXiv:2201.12919. \n\nChen, Y., Rosenfeld, E., Sellke, M., Ma, T., & Risteski, A. (2021). Iterative feature matching: Toward provable domain generalization with logarithmic environments. arXiv preprint arXiv:2106.09913.\n\nKamath et al., Does Invariant Risk Minimization Capture Invariance? AISTATS 2021.\n\nRosenfeld et al., The Risks of Invariant Risk Minimization. ICLR 2021.\n\nAhuja et al., Invariance Principle Meets Information Bottleneck for Out-of-Distribution Generalization. NeurIPS 2021.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject