Towards a Theoretical Framework of Out-of-Distribution Generalization
Authors: Haotian Ye
Chuanlong Xie
Tianle Cai
Ruichen Li
Zhenguo Li
Liwei Wang
Venue: NeurIPS 2021 Poster (2021)
Keywords: OOD Generalization
Theory
Model Selection

Abstract: Generalization to out-of-distribution (OOD) data is one of the central problems in modern machine learning. Recently, there is a surge of attempts to propose algorithms that mainly build upon the idea of extracting invariant features. Although intuitively reasonable, theoretical understanding of what kind of invariance can guarantee OOD generalization is still limited, and generalization to arbitrary out-of-distribution is clearly impossible. In this work, we take the first step towards rigorous and quantitative definitions of 1) what is OOD; and 2) what does it mean by saying an OOD problem is learnable. We also introduce a new concept of expansion function, which characterizes to what extent the variance is amplified in the test domains over the training domains, and therefore give a quantitative meaning of invariant features. Based on these, we prove an OOD generalization error bound. It turns out that OOD generalization largely depends on the expansion function. As recently pointed out by Gulrajani & Lopez-Paz (2020), any OOD learning algorithm without a model selection module is incomplete. Our theory naturally induces a model selection criterion. Extensive experiments on benchmark OOD datasets demonstrate that our model selection criterion has a significant advantage over baselines.

Towards a Theoretical Framework of Out-of-Distribution Generalization
Haotian Ye Peking University
Chuanlong Xie Huawei Noah's Ark Lab
Tianle Cai Peking University
Pazhou Lab haotianye@pku. edu.
xie. chuanlongohuawei. com
caitiamle edu. cn
Ruichen Li Peking University xk xk-1rc0pku edu.
Zhenguo Li Huawei Noah's Ark Lab Li w...hhnnuo@huaaeiicccmmm
Liwei Wang
Key Laboratory of Machine Perception, MOE, School of EECS, Institute for Artificial Intelligence, Peking University
wanglwOcis, pku. edu, cn
Abstract
Generalization to out-of-distribution (OOD) data one the central problems in modern machine learning. Recently, there is a surge of attempts to propose algorithms that mainly build upon the idea of extracting invariant features. Al- though intuitively reasonable, theoretical understanding of what kind of invariance can guarantee OOD generalization is still limited, and generalization to arbitrary fiitr--dditriittion is clearly impossible. In this work, take the first step towards rigorous and quantitative definitions 1) what is OOD; and 2) what does it mean by saying OOD problem is learnable. We also introduce sion function, which characterizes to what extent the variance is amplified in the test domains over the training domains, and therefore give quantitative meaning of invariant features. Based on these, we prove OOD generalization error bounds. It turns out that OOD generalization largely depends on the expansion function. As recently pointed out by [21]. any OOD learning algorithm without a model selection module is incomplete. Our theory naturally induces model selection criterion. Extensive experiments on benchmark OOD datasets demonstrate that our model selection criterion has significant advantage over baselines.
concept of expan-
Introduction
One of the most fundamental assumptions of classic supervised learning the "i.i.. assumption", which states that the training and the test data are independent and identically distributed. However, this assumption can be easily violated usually have a different distribution than the training data. This motivates the research on the out-of- distribution (OOD) generalization, or domain generalization problem, which assumes access only to data drawn from set Eavast of available domains during training, and the goal is to generalize to larger domain set E.ul including unseen domains.
reality 10
38 48 [56] where the data
To generalize to OOD data, most existing algorithms attempt to learn features that are invariant to a training domains in the hope that such invariance also holds in unseen domains.
certain extent For example, distributional matching-basee the same distribution across different domains; IRM and its variants [
methods 20 35 [55] seek to learn features that have
32 33 learn feature
representations such that the optimal linear classifier on top of the representation matches across domains.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Though the idea of learning invariant features is intuitively reasonable, there is only limited theoretical understanding of what kind of invariance can guarantee OOD generalization. Clearly, generalization to an arbitrary auttof--distibbution domain is impossible and in practice, the features can hardly be absolutely invariant from Eavail to Eolt unless all the domains are identical. So it is necessary to first formulate what OOD data can be generalized to, or, what is the relation between the available training domain set Eavast and the entire domain set Eall. Meanwhile, to what extent the invariance of features Eaviit can be preserved in Ealt should be rigorously characterized.
In this paper, we take the first step towards a general OOD framework by quantitatively formalizing the relationship between Eavail and Eall in terms of the distributions of features and provide OOD generalization guarantees based on our quantification of the difficulty of OOD generalization problem. Specifically, we first rigorously formulate the intuition of invariant features used in previous works by introducing the "variation" and "informativeeesss" (Definition 3.1 and 3.2) of each feature. Our theoretical insight can then be informally stated as: for learnable OOD problems, if feature is informative for the classification task as well as invariant over Exead, then it still invariant over Eau- In other words, invariance of informative features in Eavail can be preserved in Esu. We further introduce a class of functions, dubbed expansion function (Definition (333) to quantitatively characterize to what extent the variance of features on Enviit is amplified on Eall-
Based on our formulation, we derive theoretical guarantees on the OOD generalization error, i.e., the gap of largest eπrоr between the domain in Eavast and domain in Eall. Specifically, we prove the upper and lower bound of OOD generalization error terms of the expansion function and the variation of learned features over Eaveit- Our results theoretically confirm that 1) the expansion function can reflect the difficulty of OOD generalization problem, i.e., problems with more rapidly increasing expansion functions are harder and have worse generalization guarantees; 2) the generalization error gap can tend to zero when the variation of learned features tend to zero, so minimizing the variation in Eaviit can reduce the generalization error.
As pointed out by Gulrajani and Lopez-Paz (21), any OOD algorithm without a specified model selection criterion is not complete. Since Eaul is unseen, hyper-paramett parameters can only be chosen according Eavast- Previous selection methods mainly focus on validation accuracy over Eavail. which is only biased metric of OOD performance. On the contrary, a promising model selection method should instead predictive of OOD performance. Inspired by our bounds, we propose a model selection method to select models with high validation accuracy and low variation, which corresponds to the upper bound of OOD error. The introduction of model's variation relieves the problem of classic selection methods, in which models that overfit Evvoit tend to be selected. Experimental results show that our method can outperform baselines and select models with higher OOD accuracy.
Contributions. We summarize our major contributions here:
We introduce a quantitative and rigorous formulation of OOD generalization problem that charac- terizes the relation of invariance over the training domain set Eavoil and test domain set Estt The core quantity in our characterization, the expansion function, determines the difficulty of an OOD generalization problem.
We prove novel OOD generalization error bounds based formulation. The upper and lower bounds together indicate that the expansion function well characterizes the OOD generalization ability of features with different levels of variation.
We design a model selection criterion that is inspired by our generalization bounds. Our criterion takes both the performance on training domains and the variation of models into consideration and is predictive of OOD performance according to our bounds. Experimental results demonstrate our selection criterion can choose models with higher OOD accuracy.
The rest of the paper is organized as follows: Section 2 is our preliminary. Section 3 we give our theoretical formulation. Section [iiees our generalization bound. We propose our model selection method in Section 5 In Section we conduct experiments on expansion function and model selection.
We review more related works in Section and conclude work in Section g

---

2 Preliminary
Throughout the paper, we consider multi-class classification task X + y1 K) be the domain set we want to generalize to, and Eavait C Eall be the available domain set, i.e., all domains we have during the training procedure. We denote (X) to the input-label pair drawn from the data distribution of domain e. The OOD generalization goal is to find a classifier f* that minimizes the worst-domain loss on Eost:
Let Eait
f argmin L(Eau, f), ((E, - max E E[e(S(X)))Y)) Y*) JEF
eEE
where F - R is the the hypothetical space and E(.,)) is a loss function. Similar to previous assume that f can be decomposed into g h, where g E 9 w. - R is the top classifier and h X' + Rd is d-dimensional feature extractor, i.e.,
works [5 16 27 33
k(ar) = (ch (2), (2(1)).....).. ) Φ E.
Here & is the set of scalar feature maps which map X' to R and is fixed. We will call each é E Φ a feature for simplicity. Given a domain e, we denote the d-dimensional random vector h(X*) as h. oie-dimensional feature (xx") as of, and the conditional distribution of h", 60 given Y y as P(d"l)) For simplicity, we assume the data distribution is balanced every domain, i.e. P(Y y) K. Vy v E Eatl Our framework can be easily extended to the case where the balanced assumption removed, with an additional term corresponding to the imbalance adding to the generalization bounds.
P(h"ly), P(
3 Framework of OOD Generalization Problem
The main challenge of formalizing the OOD generalization problem is to mathematically describe the connection between Eavasl and Eull and how generalization depends on this relation. Towards this goal, we introduce several quantities to characterize the relation of feature distributions over different domains and bridge Eavail and Eall by expansion function (Definition (.3) over the quantities we have introduced. Our framework is motivated by the understanding that, in an OOD generalization task, certain "property" of "good" features in Eavail should be "preserved" in Eaul (the reason is described in Section [ In Section 3.1 we will go into details on what we mean by "property" (variation, Definition "good" (informativeness, Definition B.2p, and "preserved" (measured by expansion function). In Section 6.2 we further illustrate the key concepts in our framework by real-world OOD problem.
3.1 Formalizing OOD Problem by Quantifying Feature Distribution
We first introduce the concepts "variation" and "informativeness" of feature c. The first one is what we expect to be preserved Eall and the second one characterizes what features will be considered. Specifically, let (IP, Q) be symmetric "distance" of two distributions. Note that p have many choices, like Lg Distance, Total Variation and symmetric KL-divergence, etc. The variation and informativeness defined as follows:
Definition 3.1 (Variation). The variation of feature 6(-) across domain set E is
Volo, E) = max sup ((PP(()) (y). PP lv))-
(2)
VEY c,e'
A feature (6-) e-invariant across E, ifE 2 V(o, E) (We omit the subscript p in case of no ambiguity).
Definition 3.2 (Informativeness). The informativeness of feature o6-) across domain set & is
1 I)(dE)= K(K - Σ
min EEE
(3)
9.1/ EY
A feature o(-) is 6-informative across i E).
Note that our framework can be generalized other kinds of problems easily.

---

The variation V( 8) measures the stability of 6(-) over the domains in E and the informativeness I(),E) captures the ability of p(-) to distinguish different labels. We would like highlight that the variation and informativeness are defined on each one-dimensional feature ((-). Unlike previous distance between distributions defined in d-dimensional space, our definitions are more reasonable and practical, since it can be easily calculated and analyzed.
We are now ready to introduce the core quantity for connecting Eavoil and Eau. Our motivation, as elaborated in the introduction section, is that, if a feature is informative for the classification task and invariant over Eavasl, then to enable OOD generalization from Eavast to Exll. it should be still invariant over Eull. So the relation between VØ Eavast) and V( Eati) of an informative feature captures the feasibility and difficulty of OOD generalization. To quantitatively measure this relation, we define the following function class:
Definition 3.3 (Expansion Function). We say a function s Bt U {0} + R U +oo+ is an expansion function, iff the following properties hold: 1) s(.) is monotonically increasing and s(x) 2 z, Va 2 0; 2) lim s(x) = s0) = 0.
This function class gives a full characterization of how the variation between Enoost and Ealt is related. Based on this function class, we can introduce our formulation of the learnability of OOD generalization as follows:
Definition 3.4 (Learnability). Let d be the feature space and p be a distribution distance. We say an OOD generalization problem from Eavail to Eall is learnable if there exists an expansion function s(.) and 6 2 O, such that: for all e E & satisfying I, (ó. Eavait) 2 8, we have s(V,lø, (.,Evaa))) 2 VolØ, Emu)- If such s(-) and 5 exist, we further call this problem generalization problem is not learnable, we call it unlearnable.
learnable. If an OOD
To understand the intuition and rationality of our formulation, several discussions are in order.
highlight two properties of the ex- pansion function. The first property comes naturally from the monotonicity properties of variation: any E1-invariant feature is also Eg-invariant for E2 E1; and V( E1) < Vo, E2) for any E S E2- The monotonicity also implies that larger Eau will induce larger s(: I and it is also harder to be generalized to. From this view, generalization. The second property is more crucial since it formulates the intuition that an informa- tive feature is almost invariant in Eavail, it should remain invariant in Eatt- Without this assumption, OOD generalization can never be guaranteed because we cannot predict whether an invariant and informative feature in Eovail will vary severely in unseen Eall.
Properties of the expansion function. In Definition
3.3
see that the scale of s(-) can reflect the difficulty of OOD
Necessity of informativeness. We include seemingly redundant quantity informativeness in the definition of lcarnability. However, this term is necessary because only informative features are responsible for the performance of classification. Non-informative but invariant features over Envoit may only capture some noise that is irrelevant to the classification problem, and we shall not expect the noise to be invariant over Eall- Moreover, we show in Figure that in practice, many invariant but useless features in Eavail vary a lot in Ealls and adding the constraint of informativeness makes the expansion function reasonable. In addition, there are multiple choices of (s(+), 5) to make an OOD generalization problem learnable: larger 8 will filter out more features, and so s(-) can be smaller (flatter). This multiplicity will result in trade-off between s(.) and 6, which will be discussed in Section 2
Two extreme cases: i.i.d. & unlearnable. To better understand the concept of learnability, we consider two extreme cases. (1) The first example is when all data from different E Ealt are identically distributed, i.e., the classic supervised learning setting. This problem (s(-), -e-lranae with s(x) z, implying no extra difficulty in OOD generalization. (2) As example of unlearnable, consider the following case (modified from Colored MNIST (5)): For e E Eavast. images with label O always has red background while images with label 1 has a blue background. For Eall \ Eavail, this relationship is entirely inverse. Since data from different e E Eavast are identically distributed but different from other Eutt expansion function can make it learnable, i.e., it is O0D-unnearn.ble.
Whhen we talk about the scale of s(-), e.g. it is larger / smaller, we mean the comparison of two expansion function, rather than the comparison along function.

---

The unlearnability of this case also coincides with our intuition: Without prior knowledge. it is not clear from merely the training data, whether the task is to distinguish digit 0 from 1, or distinguish color red from blue. As result, generalization to Eolt cannot be guaranteed.
4 Generalization Bound
In this section, we consider an OOD generalization problem from Eneost to Eatt, and our goal is to analyze the OOD generalization error of classifier f h defined by
err(f) ff C(Eau, f) [(E f),
where we assume the loss function I(:..) is bounded by [0, CJ. We prove two upper bounds (4.1 4.2)
well as lower bound (4.3) for efr(f) based on formulation. Our bounds together provide complete characterization of the difficulty of OOD generalization. Since we expect that an invariant classifier can generalize unseen domains, hope bound err(/) in terms of the certain variation of f. To this end, we define the variation and informativeness of f terms of its features, i.e.,
yup (h, Eavait)
A sup BES
V(3 h, Eavas),
Iiml (h, Eavoat)
I(3 h, Eavait;; BES
inf
where = is feature and Sd (B Rd ||3112 = 13 is the unit (d -p-eeer
Necessity of using supremum over linear combination. One seemingly plausible definition of the variation of classifier can be the supremum over all V(di, E E [d]. However, as is shown in Appendix 1, it is possible that two high-dimennional joint distributions have close marginal distribution each dimension, while they do not overlap. In other words, there exist cases where Vl Eaul = 0, Vi E [d] but after applying the top model g over Φ; s, the distribution varies a lot in Eavail. Our definition comes from the simple idea that the class of top model is at least linear space, so we should at least consider the variation of every (normalized) linear combination of h(-). With this, we can guarantee the joint distribution distance still small.
Theorem 4.1 (Main Theorem). Suppose we have learned a classifier f(x) g(h(x)) such that Ve E Eall and Vy E V. Phely- (hly) (TRd). Denote the characteristic function of random variable 1 as P = Eiexp h²) HY = y]. Assume the hypothetical space F satisfies the following regularity conditions that Ea, M1, M2 > 0, 0. E F, E Eail: y E Y
JhE Pho If (Eovail: Eat) is (s(.), Inn (h, Eavoit) -learnable under with Total Variation then we have err(f) S 0 (V (h, Eavait)) ca-ta)2
dh I M1 and Jrsee Ipnepro (tw)))1 M2. (4)
(5)
Here p is total variation distance, and O()) depends on d, C, M1,
The above theorem holds for general classifier learned by any algorithms. Due to its generality, we need to introduce some technical regularity conditions on the density function. The assumption (4)
assume the decay rate of density and its characteristic function, which is common in the literature. e.g. [14. This theorem demonstrates that, the generalization error can be bounded by function of
the variation of h, and converges to 0 as the variation approaches to O. Under some special but
typical case where the top model is linear,
can further show that even without the regularity conditions in Theorem 4.1 we have a much better (linear) convergence rate.
Theorem 4.2 (Linear Top Model). Consider any loss satisfying E(g. v) = Ek= Rolōk, 3k)
For
any classifier with linear top model g, i.e.,
f(x) Ah(x) +b with AERKxo b be R
Foor distribution Q with probability density function p. q. p(P, Q) 1/2 J, Ip(x)) {(x)
4 'This decomposition is technical assumption to make the proof more convenient. Truncated square loss or Truncated absolute loss satisfy this assumption.
5

---

(Eavast, Eat)) is (s(+), (h, Eavast) -earrable under & with Total Variation p. then we have err(f) S (0((s (s(D (h, Emmait)
(6)
Here O() depends only on d and C.
Discussion. Theorem 4.1 shows that, for any model, the generalization gap depends largely on the model's variation captured by yuu Eavait) The result is irrelevant to the algorithm and provides a guarantee for the generalization gap from Eevoit &all, long as the learned model f is invariant, i.e. (h, Eawast) is small. When s(.) is fixed, a model with smaller youp Eaveit) results in a smaller gap, which matches understanding that invariant features in Evviil are somehow invariant in Eau. When VSHPp (h, Eavast) is fixed, more difficult generalization will generate larger expansion function, which leads a larger gap. For the Gaussian class with bounded mean and variance, > and the convergent rate is almost linear.
However, without any constraint to 9, the convergent rate might be small. Theorem 4.2 then offers generalization bound with a linear convergent rate under mild assumptions when & is linear, which common in reality. It relaxes the concentration assumption (Formula 4 and asks only for the integrability of the density. The convergent rate is identical to the convergent rate of the expansion function, showing that s()) captures the generalization quite well.
Proof Sketch of Theorem 4.1 The proof of the main result, Theorem 4.1 is decomposed into the following steps. First, we transform err(f) into the Total Variation of joint distributions of features in different domains (Step 1). To bound the Total Variation, is sufficient to bound the distance of the corresponding Fourier transform, and further, it equivalent to bound the Radon transform of joint distributions (Step 2). Eventually, we show that ysup h, Enviit) can be used to bound the Radon transform, which finishes the proof (Step 3).
Step The OOD generalization error can be bounded as:
C
err(f) S
sup (e.e')E(Euvvit
Σ
(Phejyr Py (Nlv))
K yEY heRd
Step 2. According to the assumption
the dominant term in is
[ JMEE UuIs: e (i(b,t) (Pnepy= (tly) Pr ly (tlu)))
where 71 and F2 are well-selected scalars that depend on s (V= (h. Eavast)) By the Projection
Theorem B1 42 and the Fourier Inversion Formula, (8) is bounded above by
((rir))
Red (3, u) Re, u)ldu,
where R. (B, is the Radon transform of Ph-jy- (tly).
Step The right-hand side of Formula can be bounded by O (V."" (avass)) We finish the proof by selecting appropriate r1 and 72 to balance the rate of the dominant term and other minor terms. For more details, please see Appendix 2 for the complete proofs.
Now we turn to the lower bound of err(f).
Theorem 4.3 (Lower Bound), Consider 0-1 loss: ((D.v) 110 + v). For any å 0 and any expansion function satisfying 1) 8'a (0) A lim a(x)-a(0) E (10); 2) exists l > 1, > O, ko s(x) < +00, [0, 1), there exists constani Co and OOD generalization problem (Eavait, Eati) that is 6)-eaaalle under linear feature space : w.rl symmetric KI-divergence P. s.t. We [0, z. the optimal classifier f satisfying youp (h, Eovait) will have the OOD generalization error lower bounded by
err(s) 2 Co s(y"HP Eavait).
(10)
Theorem 4.3 shows that err(f) of optimal classifier f lower bounded by its variation. Here "optimal" means the classifier that minimize L(f, Eavoit). Altogether, the above three theorems

---

offer a bidirectional control of OOD generalization error, showing that our formulation can offer fine-grained description of most OOD generalization problem in a theoretical way. To pursue good OOD performance, OOD algorithm should focus on improving predictive performance on Eavait and controlling the variation (h, Eavait) simultaneously. Note that this bound starts from population error, and we call for future works to combine our generalization bound and traditional bound from data samples to population error, giving a more complete characterization of the problem.
5 Variation as a Factor of Model Selection Criterion
As is pointed out in (21). model selection has a significant effect on domain generalization, and any OOD algorithm without a model selection criterion is not complete. [21] trained more than 45,900 models with different algorithms, and results show that when traditional selection methods applied, none of OOD algorithms can outperform ERM (58) by significant margin. This result is not strange, since traditional selection methods focus mainly on (validation) accuracy, which is biased in OOD generalization [2] 633. A very typical example Colored MNIST [5], where the image is colored according to the label, but the relationship varies across domains. As explained in [.) ERM principle will only capture this spurious feature (color) and performs badly in Eail. Since ERM is exactly minimizing loss in Eavail, any model selection method using validation accuracy alone likely to choose ERM rather than any other OOD algorithm 66 Thus no algorithm will have a significant improvement compared to ERM.
use, in addition accuracy? Theorem 4.1 points that, learning feature with small variation across Egvait is important for decreasing OOD generalization error. Once a model f achieves a small Duup pnu Evvait,, then err(f) will be small. If the validation accuracy is also high, we shall know that the OOD accuracy will remain high. To this end, we propose our heuristic selection criterion (Algorithm TT. Instead of considering validation accuracy alone, we combine it with feature variation and select the model with high validation accuracy well as low variation.
natural question arises: what else
Algorithm 1: Model Selection
Input: available dataset Kevail (rraain Yval), candidate models set M, var_acc _ar_acc_rate ro. for f = ht in M do for [d] do
D3 +- max VE Exavast
Total Variation P(d 1y));
DUse GPU KDE
end
V mean a 1 Acc + compute validation accuracy of if using Neat
end
Return argmna (Accy - rr))))
We briefly explain Algorithm heee. For each candidate model, we calculate its variation using the average of cach feature's 's variation, i.e., å Eield] V(ot, When deriving the bounds, use you instead of their average because need to consider the worst case, i.e., the worst top model. In practice, we find out that the average of V(d,, Xavaiit) is enough to improve selection.
Our criterion of model selection is
Acc roVy,
(1I)
ie., select model with high validation accuracy and low variation simultaneoussy. Here To is a hhper--arameee representing the concrete relationship between err(f) and Vy, Although we have already used one typer-parameter to help select multiple hyper-parameter combinations, it natural to ask whether we can further get rid of the selection of ro- Since Fo represents the relationship between variation and accuracy, which is actually determined by the unknown expansion function, explicitly calculating To is not possible. However, we can empirically estimate To using ro Std se Ace, where M M is the model with not bad validation accuracy. We do not use the whole set M because some OOD algorithms will perform extremely bad when the penalty is
V,
7

---

huge, and these models will influence our estimation of the ratio. Since high validation means large informativeness in learned features, the use of .M is an implicit application of informative assumption.
As shown in Section 6.1 our method can select models with higher OOD accuracy in various OOD datasets. We also explain in Appendix 3 why our method can outperform the traditional method in Color MNIST, where the dataset is hand-make and simple enough calculate the expansion function.
6 Experiments
In this section, we conduct experiments compare our model selection criterion (Section with the baseline method [21]. Since both the variation and informativeness in Definition 3.1 are based and design
on one-dimensional features, we can directly estimate these quantities feature-by-feaute model selection method based on them. To verify the existence of the expansion function and to see what it's like in a real-world dataset, we plot nearly million features trained in a common OOD dataset and compute their variation and informativeness. We then draw the expansion function for this problem.
6.1 Experiments on Model Selection
In this section, we conduct experiments to compare the performance of models selected by our method and by validation accuracy. We train models on different datasets, different Eavail, and select models according to different selection criteria. We then compare the OOD accuracy of selected models.
Settings We train our model on three benchmark OOD datasets (PACS [34], OfficeHome [59], VLCS (57)) and consider all possible selections of (Eavait, Eau) We choose ResNet-50 network architecture. We use ERM (58) and four common-used OOD algorithms (CORAL (55), Inter-domain Mixup [62, Group DRO (51), and IRM (5). For each environment setup, train 200 models using different algorithms, penalties, learning rates, and epoch. After training, we employ different selection methods and compare the OOD accuracy of the selected models. As stated in the standard deviation of V and validation accuracy in M to estimate Fo: where M (f E M Acc; Z max; j Acc 0.1}. Note that calculating V(Ø,, Kavvai)) takes calculus many times, so we design a parallel GPU kernel density estimation to speed up the whole process hundred times and manage to finish one model in seconds. For more details about the experiments, see Appendix 4.
Section 5
Table 1: Model Selection Result. "Env" denotes the unseen domain during training. "Val" denotes the OOD accuracy model selected by validation accuracy.
Env
A
avg
acc inc
PACS
Val
85. 35.20%
80.42%
96.17%
77.86%
84.91%
Ours
88.72%
81.74% C
96.83%
79.00%
86.57%
1.66%
Env
A
avg
inc
OfficeHome
Val
61.85%
55.56 %
74.72%
76.25%
67.09%
Ours
65.76% C
55.07%
75.20%
76.31% V
68.09%
1.00%
Env
S
avg
acc inc
VLCS
Val
97.46%
64.83%
69.50 %
70.97% %
75.69%
Ours
97.81% %
66.98 %
69.50%
70.97% %
76.32%
0.63%
Result We summarize our experimental results in Table For each environment setup, we select the best model according to Algorithm [ and validation accuracy. The results show that on all datasets, our selection criterion significantly outperforms the validation accuracy in average OOD accuracy. For more detailed comparison, method improves the OOD accuracy in most of the 12 setups. Our experiments demonstrate that our criterion can help select models with higher OOD accuracy.
*Our experiments conducted DomainBed: https: / wtt.tt/..cmmmmccoooeeeeeeeeeccla
'Notice that some OOD accuracy are the same in the two methods since the same model is selected. This happens when the unseen domain is close Eavail that the validation accuracy metric is close to ours.

---

6.2 Learnability of Real-World OOD Problem
6=
0.15
6 0.30
6= 0.45
The expansion function of the OOD generalization problem on Office-Home, The x-axis stands for V(e, Eevoi) and the y-axis for V(o, Eau). There are approximately 2 million points in each image, with each point representing a feature, and its color represents its informativeness. The solid red line stands for the expansion function under the corresponding 6. When ó increases, the expansion function decreases. When = 0, no expansion function can make it learnable.
Figure 1:
One may wonder if the expansion function really exists and what it will look like for real-world OOD generalization task. In this section, we consider the OOD dataset Office-Home [59]. We explicitly plot millions of features' Vp(Ø, Eavast and (0 Eui)) with Total Variation p to see what the expansion function is like in this task. We take the architecture as ResNet-50 (23), and we trained thousands of models with more than five algorithms, obtaining about million features. The results are in Figure I
Existence of s--). When 8 = O, non-informative features are nearly 0-invariant across Envoit but are varying across Ealls so no expansion function can make this task learnable, i.e., this task is NOT (s()), 0) for any expansion function. But as ö increases, only informative features are left, and now we can find appropriate s(-) to make it learnable. We can clearly realize from the figure that s(-) do exist when ó > 0.15.
Trade-off between s(-) and 8. The second phenomenon is that the slope of s(-) decreases as d increases, showing a trade-off between s(-) and 8. Although this trade-off comes naturally from the definition of learnability, it has a deep meaning. As is shown in Section 4 err(j) is bounded the variation of the model. To make the bound tighter. natural idea is to choose a flatter s..). However, a flatter s(-) corresponds to a larger ö. Typically, learning model to meet this higher informativeness requirement more difficult, and it is possible that the algorithm features, which will therefore increase the variation
by (ss()) where
achieves this by capturing more domain-spect of the model, e. As result, we are not sure whether s(E) will increase decrease. We believe this also the essence of model selection: i.e., to trade-off between the variation and informativeness of model, which done in Formula
More Related Works
Domain generalization 12
39 or OOD generalization, has drawn much attention recently [2] 30
The goal to learn a model from several training domains and expect good performance on unseen test domains. 660 64 offer comprehensive survey. A popular solution is to extract domain-invariant feature representation. 45 and [9] proved that when the model is linear, the invariance under training domains can help discover invariant features on test domains. [5] introduces the invariant prediction into neural networks and proposes a practical objective function. After that, lot works arise from the view of causal discovery, distributional robustness and conditional independence 43 5T 61]. On the other hand, some works point out the weakness of
7 16 15
26
32 33
existing methods from the theoretical and experimental perspectives 2
29
50).
The OOD generalization requires restrictions on how the target domains may differ. A straightforward approach is to define a set of test domains around the training domain using some distribution distance 54 61) Another feasible route is the causal framework which is robust
measure [6] 13
[9 25
to the test distributions caused by interventions 44 46 on variables, e.g., 5 24
36
37
40
49 52
The principle of these methods that a causal model is invariant and can achieve the minimal worst-
case risk
4 22 44 49). Since the test distribution is unknown, additional assumptions are required for

---

generalization analysis. [22 18 39 assume that the domains are generated from hyper- and measures the average risk estimation error bound. [3] derives risk bound for any linear
combination of training domains. For more related results in domain adaptation, a closed field where
the test domains can be seen but are unlabeled, please see 9 I0 28
Conclusion
In this paper, take the first step towards rigorous thcoretical framework of OOD generalization. We propose a mathematical formulation to characterize the learnability of OOD generalization framework, prove generalization bounds and give guarantees for OOD
problem. Based generalization error. Inspired by our bound, we design a model selection criterion to check the model's variation and validation accuracy simultaneously. Experiments show that our metric has significant advantage over the traditional selection method.
Acknowledgments and Disclosure of Funding
Authors are thankful to the anonymous reviewers for their helpful and constructive feedback.
References
[1] Kartik Ahuja, Karthikeyan Shanmugam, Kush Varshney, and Amit Dhurandhar. Invariant risk minimization games. arXiv preprint 200iv:22002.446992 2020.
[2] Kartik Ahuja, Jun Wang, Amit Dhurandhar, Karthikeyan Shanmugam, and Kush Varshney, Empirical or invariant risk minimization? a sample complexity perspective. arXiv preprint arXiv:2010. 16412, 2020.
[3] Isabela Albuquerque, João Monteiro, Tiago H Falk, and Ioannis Mitliagkas. Adversarial ingert-nnvaiiant representation learning for domain generalization. arXiv preprint
2019.
[4] John Aldrich. Autonomy. Oxford Economic Papers, 41(1):15-34, 1989.
[5] Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz Paz. Invariant risk minimization. arXiv preprint arXiv: 1907:029990.3 2019.
[6] Andrew Bagnell. Robust supervised learning. In Proceedings of the national conference on artificial intelligence, volume 20, page 714. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2005.
[7] Haoyue Bai, Rui Sun, Lanqing Hong, Fengwei Zhou, Nanyang Ye, Han-Jia Ye, S-H Gary Chan, and Zhenguo Li. Decaug: Out-of-distribution generalization via decomposed feature representation and semantic augmentation. arXiv preprint arXiv:2012. 09382, 2020.
[8] Sara Beery, Grant Van Horn, and Pietro Perona. Recognition in incognita. In Proceedings of the European Conference on Computer Vision (ECCV), September 2018.
[9] Shai Ben- Ben-David, John Blitzer, Koby Crammer, Femanno Pereira, et al. Analysis of representations for domain adaptation. Advances in neural information processing systems, 19:137, 2007.
[10] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. theory of learning from different domains. Machine learning, 79(1):151-175, 2010.
[11] Yoshua Bengio, Tristan Deleu, Nasim Rahaman, Nan Rosemary Ke, Sehastien Lachapelle, Olexa Bila- niuk, Anirudh Goyal, and Christopher Pal. meta-transfer objective for learning to disentangle causal mechanisms. In International Conference on Learning Representations, 2019.
[12] Gilles Blanchard, Gyemin Lee, and Clayton Scott. Generalizing from several related classification tasks to new unlabeled sample. Advances in neural information processing systems, 24:2178-2181 2011.
[13] Jose Blanchet, Yang Kang, Karthyek Murthy, and Fan Zhang. Data-driven optimal transport cost selection for distributionally robust optimization. In 2019 Winter Simulation Conference (WSC), pages 3740-3751. IEEE, 2019.
[14] Laurent Cavalier. Efficient estimation of density in problem of tomography, Annals of Statistics, pages 630-649 2000.
10

---

[15] Shiyu Chang, Yang Zhang, Mo Yu. and Tommi Jaakkola. Invariant rationalization. In International Conference on Machine Learning, pages 1448-1458. PMLR, 2020.
[16] Elliot Creager, Joern-Henrik Jacohsen, and Richard Zemel. Exchanging lessons between algorithmic fairness and domain generalization, 2021. URI httcps://openreevie
ht:ffformmmdddDD Im3MkGG
[17] Alex DeGrave, Joseph D Janizek, and Su-In Lee. Ai for radiographic covid-19 detection selects shortcuts over signal. medRxiv, 2020.
[18] Aniket Anand Deshmukh, Yunwen Lei, Srinagesh Sharma, Urun Dogan, James W Cutler, and Clayton Scott. A generalization error bound for multi-class domain generalization. arXiv preprint arXiv:190S.10392
2019.
[19] Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the wasserstein metric: Performance guarantees and tractable reformulations. Mathematical Programming, 171(1-2):15-166) 166, 2018.
[20] Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Vietor Lempitsky. comain-adversarti training of neural networks. The journal of machine learning research, (71))2096-20333 2016.
[21] Ishaan Gulrajani and David Lopez-Paz. In search of lost domain generalization. arXiv:2007.01434 2020.
arXiv preprint
[22] Trygve Haavelmo. The probability approach in econometrics. Econometrica: Journal of the Econometric Society, pages 1i5- 1944.
[23] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition (CVPR), June 2016.
[24] Christina Heinze Deml and Nicolai Meinshausen. Conditional variance penalties and domain shift robustness. Machine Learning, 1002))3033334, 2021.
[25] Zhaolin Hu and L. Hong. Kullback-leibler divergence constrained distributionally robust optimization. Available Optimization Online, 2013.
[26] Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Domain extrapolation via regret minimization. arXiv preprint arxiv:2006. 03908, 2020.
[27] Wengong Jin, Regina Barzilay, and Tommi S. Jaakkola. Enforcing predictive invariance across structured biomedical domains, 2021. httpstt:::/// pttttp:://ppnneevvieee http://wwwwwwwwweeeeeeeeeeeeeeee
[28] Fredrik D Johansson, David Sontag, and Rajesh Ranganath. Support and invertibility in domain-invariant representations. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 527-536. PMLR, 2019.
[29] Pritish Kamath, Akilesh Tangella, Danica J Sutherland, and Nathan Srebro. Does invariant risk minimiza- tion capture invariance? arXiv preprint arXiv:2101.01 134, 2021.
[30] Pang Wei Koh, Shiori Sagawa, Hearik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips. Sara Beery, et al. Wilds: A benchmark of in-the-wild distribution shifts. arXiv preprint arXiv:2012.0742: 2020.
[31] Aleksandr Petrovich Korostelev and Alexandre B Tsybakov. Minimax theory of image reconstruction, volume 82. Springer Science & Business Media, 2012.
[32] Masanori Koyama and Shoichiro Yamaguchi. Out-of-distributte generalization with maximal invariant predictor. arXiv preprint arXiv:2008. 01883, 2020.
[33] David Krueger, Ethan Caballero, Joern-Henrik Jacobsen, Amy Zhang, Jonathan Binas, Remi Le Priol, and Aaron Courville. Out-of-distribution generalization via risk extrapolation (rex). arXiv preprint 22Xi:2000300068: 2020.
[34] Da Li, Yongxin Yang, Yi-Zhe Song, and Timothy M Hospedales. Deeper, broader and artier domain gencralization. In Proceedings of the IEFE international conference on computer vision, pages 5542-5550, 2017.
[35] Haoliang Li. Sinno Jialin Pan, Shiqi Wang. and Alex C Kot. Domain generalization with adversarial feature learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5400 $409, 2018.
11

---

[36] Sara Magliacane, Thijs van Ommen, Tom Claassen, Stephan Bongers, Philip Versteeg, and Joris M Mooij. Domain adaptation by using causal inference predict invariant conditional distributions. arXiv preprint arXiv:1707.0644 2017.
[37] Nicolai Meinshausen. Causality from distributional robustness point of view. In 2018 IEEE Data Science Workshop (DSS)) pages 6-10. IEFE, 2018
[38] Jose G Moreno-Torees Troy Raeder, Rocío Alaiz-Rodriguez, Nitesh V Chawla, and Francisco Herrera, A unifying view on dataset shift in classification. Pattern recognition, 45(1):521-530, 2012.
[39] Krikamol Muandet, David Balduzzi, and Bernhard Schölkopf. Domain generalization via invariant feature representation. In International Conference Machine Learning, pages 10-18. 2013.
[40] Jens Müller, Robert Schmier. Lynton Ardizzone, Carsten Rother, and Ullrich Köthe. Learning robust models using the principle of independent causal mechanisms. arXiv preprint arXiv:2010.07167. 2020.
[41] Vaishnavh Nagarajan, Anders Andreassen, and Behnam Neyshabur. Understanding the failure modes of out-of-distribution generalization. arXiv preprint arXiv:2010. 15775, 2020.
[42] Frank Natterer. The mathematics of computerized tomography. SIAM, 2001.
[43] Giamhattista Parascandolo, Alexander Neitz, Antonio Orvieto, Laigi Gresele, and Bernhard Schölkopf. Learning explanations that are hard to vary. arXiv preprint arXiv:2009.00322 2020.
[44] Judea Pearl. Causality. Cambridge university press, 2009.
[45] Jonas Peters, Peter Bühlmann, and Nicolai Meinshausen. Causal inference by using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Society. Series B (Statistical Methodology), pages 947-1012, 2016.
[46] Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: foundations and learning algorithmss The MIT Press, 2017.
[47] Niklas Pfister, Evan G Williams, Jonas Peters, Ruedi Aebersold, and Peter Bühlmann. Stabilizing variable selection and regression. arXiv preprint arXiv:1911.01850, 2019.
[48] Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize to imagenet? In International Conference on Machine Learning, pages 5389-5400. PMLR, 2019.
[49] Mateo Rojas-Carulla, Bemhard Schölkopf, Richard Turner, and Jonas Peters. Invariant models for causal transfer learning. The Journal of Machine Learning Research, 19(1):1309-1322, 2018.
[50] Elan Rosenfeld, Pradeep Ravikumar, and Andrej Risteski. The risks of invariant risk minimization. arXiv preprint 2r0.022010005761, 2020.
[51] Shiori Sagawa, Pang Wei Koh, Tatsunori Hashimoto, and Percy Liang. Distributionally robust neural networks. International Conference on Learning Representations, 2019.
[52] Bernhard Schölkopf. Dominik Janzing, Jonas Peters, Eleni Sgouritsa, Kun Zhang, and Joris Mooij. On causal and anticausal learning. arXiv preprint arXiv: /206.6471, 2012.
[53] Soroush Shafieezadeh Abadeh, Peyman M Mohajerin Esfahani, and Daniel Kuhn. Distributionally robust logistic regression. Advances in Neural Information Processing Systems, 18:1576-1584, 2015.
[54] Aman Sinha. Hongseok Namkoong, and John Duchi. Certifying some distributional robustness with principled adversarial training, In International Conference on Learning Reprexentations, 2018.
[55] Baochen Sun and Kate Saenko. Deep coral: Correlation alignment for deep domain adaptation. In European conference computer vision, pages 443-450. Springer, 2016
[56] Rohan Taori, Achal Dave, Vaishaal Shankar, Nicholas Carlini, Benjamin Recht, and Ludwig Schmidt. Measuring robustness to natural distribution shifts in image classification. Advances in Neural Information Processing Systems, 33, 2020.
[57] Antonio Torralba and Alexei A Efros. Unbiased look at dataset bias. In CVPR 2011, pages 1521-1528. IEEE, 2011.
[58] Vladimir Vapaik. Principles of risk minimization for learning theory. In Advances in neural information processing systems, pages 831-838, 1992.
12

---

[59] Hemanth Venkateswara, Jose Eusebio, Shayok Chakraborty, and Sethuraman Panchanathan. Deep hashing network for unsupervised domain adaptation. In Proceedingy of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5018-5027, 2017.
[60] Jindong Wang, Cuiling Lan, Chang Liu, Yidong Ouyang. Wenjun Zeng, and Tao Qin. Generalizing unseen domains: survey on domain generalization. arXiv preprint arXiv:2103.03097 2021.
[61] Chuanlong Xie, Fei Chen, Yue Liu, and Zhenguo Li. Risk variance penalization. arXiv preprint arXiv:2006.000 07544, 2020.
[62] Shen Yan, Huan Song, Nanxiang Li, Lincan Zou, and Liu Ren. Improve unsupervised domain adaptation with mixup training. arXiv preprint arXiv:2001.00611 2020.
[63] Haotian Ye, Chuanlong Xie. Yue Liu, and Zhenguo Li. influence function. arXiv preprint arXiv:2101. 00w00111.0011.....0111111111 2021.
generalization analysis via
[64] Kaiyang Zhou, Ziwei Liu, Yu Qiao, Tao Xiang, and Chen Change Loy, Domain generalization: A survey. arXiv preprint (rXiv:2103.02500 2021.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contribu- tions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section S
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)?
[Yes] In the appendix.
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We use 21 and we cite it in
Section 6
Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you' 're us-
ing/curating? [Yes]
(e) Did you discuss whether the data you are using/curating contains personally identifiable informa- tion or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include full text instructions given to participants and screenshots, if applicable?
[N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "liRVsE27x1", "reviewer": "Reviewer_MoMA", "summary": "The paper proposes to capture the \"learnability\" of a domain generalization problem via two metrics, the \"variation\" and \"informativeness\" of the features. They use these measures to prove generalization bounds and propose a model selection method which (the authors claim) succeeds in selecting a better-performing model.", "questions": "", "limitations": "", "rating": 4, "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": "I think this is a decent paper theory-wise, and I appreciate the effort to formally study what makes a problem OOD-learnable. I think the technical results, while not themselves particularly interesting, will help push the community towards a more rigorously grounded study of OOD generalization. \n\nBased on the theory alone, I was on the border of weakly recommending an accept, subject to my point below about the language. However, **after looking more closely at the experimental presentation, I feel I must recommend rejection, at a minimum until the issues I found are addressed**.\n\nFirst, my note about the theory:\n\n* I feel this paper repeatedly overclaims their technical contribution.\n\nIn line 174 the paper reads \"Our bounds together provide a complete characterization of the difficulty of OOD generalization\", and this matches language earlier in the paper, which I find totally inconsistent with the actual contribution of this work. The main theorem of this paper is basically saying \"if every feature that is reasonably informative of the label also does not vary too much across *all possible environments*, then we can succeed in generalizing.\" This is obvious; the whole point of OOD generalization is to succeed when this is *not* the case. If we just do standard ERM, it will pick up on features which correlate with the label---if we can somehow magically guarantee that all these features are consistently informative in all domains, then *of course* we can succeed in generalizing. Further, it's clear that the bound is vacuous for DNNs, because conditional feature matching does not improve OOD generalization by much in practice. **I don't mean to downplay the value of formally proving this and giving an explicit bound**; I think this is a good contribution towards formal study of OOD generalization. But it is not remotely a 'complete characterization'. (particularly because the conditions are impossible to ever evaluate).\n\nThe lower bound is alright too, though also extremely loose; the space of *all possible train and test environments* is enormous, even when restricting it to satisfy the conditions in Theorem 4.3. Showing that among these there exists one for which the in-domain optimal classifier fails is perhaps a bit meaningful, but not nearly as clear-cut a characterization as the language would seem to imply.\n\nAgain, I think there is value in being able to state these claims formally. But I think the main results, written in plain English, don't actually give us new information to help us understand in which settings we can expect OOD generalization to succeed or fail. **Ultimately, this paper is (vacuously) formalizing the part of OOD generalization that we already knew: if the features which correlate with the label don't change too much, we can generalize. If they change way too much, we can't without additional assumptions. I don't think it provides any sort of framework for additional insights into generalization, as the title claims. It also gives no insights into the possibility of generalization when there features do shift, but in a structured way, such as when using Invariant Causal Prediction**\n\nNow, I'll explain the main reason I'm currently recommending a rejection:\n\n* The experiments rely on only a specific subset of the DomainBed benchmark, and the presentation is very limited in scope to the point that I believe the experimental methodology is flawed.\n\nThe three datasets chosen to represent this model selection technique are all a particular type of distribution shift in which the underlying distribution of natural images has not changed---rather, the difference across environments is a difference in \"style\" of the image. This type of distribution shift is particularly amenable to generalizing when the models enforce low variation in the feature distribution, because we know a priori that if we recover the \"correct\" features, there should be very little variation. This implies that algorithms which enforce this feature invariance, such as CORAL or MMD penalization, are particularly suited to these specific datasets, whereas Group DRO and Interdomain Mixup are not.\n\nAs further evidence of this, and what makes me particularly suspicious of the reported results: looking at the results by Gulrajani and Lopez-Paz, we see that *CORAL and MMD with the standard validation-set model selection matches or outperforms this paper's method on many environments*, often by a large margin, and ERM with the standard model selection method often does as well. From my understanding of the paper's experimental methodology (please correct me if I'm wrong), it appears that the authors evaluated all algorithms simultaneously, and then used the given model selection method on all results at once. I believe instead the correct method would be to use the proposed model selection method on *each algorithm individually*. I think the current methodology is flawed, both due to this grouping together, and the fact that the evaluation is *only* done on these datasets which are particularly amenable to the \"feature distribution invariance\" idea for generalization. The authors should also compare on different types of shifts, such as TerraIncognita (Beery et al.).\n\nAs I said, I believe the theory, while severely overclaimed, is a decent contribution and of some value to the community. But the language and the (in my mind) flawed experimental methodology should be fixed before this paper is published.\n\n---------------------------\n**Update after rebuttal**\n\nThe author's rebuttal does not remotely address my concerns, and in fact I feel it presents evidence that they are either unaware of or unwilling to acknowledge the weaknesses of this submission. Statements such as \"we doubt the existence of the method that universally outperforms ERM (or validation accuracy) in general OOD settings\" (beyond the truly obvious \"no free lunch\" setting) are vague and have no real evidence behind them; this is not a sufficient reason to fail to thoroughly evaluate a proposed method.\n\nWith no real discussion about the shortcomings of the theoretical results nor a willingness to *properly* evaluate on benchmarks which are not intentionally favorable to their proposed model selection technique, I cannot recommend this work for publication. I've lowered my score from 5 to 4.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Sure", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "fnOIwZH6kOX", "reviewer": "Reviewer_ZmeN", "summary": "This paper provides quantitative definitions for the learnability of OOD problem, and introduce a new concept of expansion function. Based on these, the authors prove OOD generalization error upper and lower bounds, and the bounds largely depends on the expansion function. The theory inspires a model selection method. Extensive experiments partially verify the effectiveness of the proposed model selection and the theory.", "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": "Originality: The paper is based on a well-known insight that variation and informativeness decide the difficulty of ood problem. The paper gives formal definitions for the two terms, and establish generalization bounds based on them.\n\nQuality:\n1. Though the paper is technically sound, I have concerns on the explainability of variation and informativeness, which is the main contribution of this paper to characterize the difficulty of ood generalization. It is a bit hard for me to understand the definitions in (2) and (3). Why do we want to use the conditional probability? In (3), why do we want to sum over different y and y'? The definition is not so intuitive that it might be just artifact.\n2. It is unclear to me why the criterion of model selection is in the form of linear combination between Acc and variation, as in Eqn (11)?\n3. I am expecting the discussion of another extreme case in Line 159, where e_avail=e_all.\n\nClarity: The paper is well-written and organized. One concern is that the abstract is a bit over claiming. I do not think the paper is the first one to give rigorous and quantitative definitions for .what is OOD\n\nSignificance: Theoretical analysis for ood problem is on demand in the community. The paper does a good job towards the goal.\n\nExperiments:\n1. The improvement of proposed model selection is marginal.\n2. Thought the paper has mentioned Colored MNIST in the previous sections, the authors does not conduct the experiments on the Colored MNIST dataset.\n\nMinor comments:\n1. Line 173, l(.,.) -> \\mathcal{L}(.,.)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper fails to discuss any limitation of the work. For example, the paper does not discuss the gap between the current progress on ood and safety-critical applications, such as self-driving car.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "TqkyUeGFuQT", "reviewer": "Reviewer_ZAxY", "summary": "This paper proposes two properties of features, variation and informativeness, that can be used to reason about the level of OOD generalization that can be expected. ", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "Strengths:\n1. The definitions of variation and informativeness proposed are intuitive\n2. The derivations are correct to the best of my knowledge\n\nWeaknesses:\n1. Estimation from finite samples: My understanding is that for the definition of both variation and informativeness, the authors are assuming $\\mathbb{P}(\\phi | y)$ is known. However, this is potentially equivalent to knowing the full joint distribution $(x, y)$ for all the available environments, which is a really strong requirement. Can the authors clarify if this is true? If yes, how did the authors estimate this for their experiments from finite samples? How would the estimation error affect the results? \n2. The definition of 'Learnability' (Def 3.4) requires knowing the variation for $\\mathcal{E}_{all}$ , which again would require knowing the distribution $(x, y)$, but now also for all the expected future environments. So, how is this condition more easily verifiable or useful than actually taking all the feature in $\\phi \\in \\Phi$  and computing the error for all the environments\n\nQuestion:\n1. Can these definitions directly be used to find invariant features by maximizing informative, but minimizing variation? It seems that the feature $\\phi(x) = y$ would achieve the maximum informativeness and minimum variation, so does this mean any model that outputs the label as features for the available environments is a 'good' feature?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hrs"}, "extra_text": {}}, {"review_id": "B38fer5ShYL", "reviewer": "Reviewer_wFmp", "summary": "This paper takes the first step towards rigorous and quantitative definitions of OOD generalization and learnability. A new concept of expansion function, which characterizes to what extent the variance is amplified in the test domains over the training domains, and therefore give a quantitative meaning of invariant features, based on which it proves OOD generalization error bounds. The model selection criterion works well in the several widely used OOD benchmarks.", "questions": "", "limitations": "", "rating": 5, "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": "The paper has some merits in originality and clarity with the initial attempt to formalize OOD generalization with a few well-characterized definitions like Expansion Function, Variation, Informativeness and Learnability. Model selection in domain generalization is under-explored and this work offers a potential solution. The paper is also well-written and consistent. The theoretical results show that the error of optimal classifier is lower bounded by its variation, which also serves as a factor of model selection. However, both the lower and upper bound is not related to informativeness and only to variation, which is counterintuitive. Also, the result still doesn't answer why the proposed method can capture invariant representations essentially and how to combat the learning proclivity to spurious correlations of deep NNs.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It would be nice to discuss the more about the originality and other use cases of expansion function. Moreover, the relationships with representative approaches like DRO, IRM are not well discussed. The proposed framework should be able to explain the learning proclivity and systematically compare those methods under the framework to make more significant contribution to invariant learning. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors give upper and lower bounds on OOD generalization error in terms of an "expansion function". They propose a model selection technique based on these, and validate with experiments. Most reviewers (MoMA, ZmeN, wFmp) agreed that the paper addresses an important problem, namely formalizing notions of OOD generalization. A major concern (from reviewer MoMA, also wFmp somewhat) is that the bounds given aren't particularly insightful, e.g. towards understanding methods which make OOD generalization possible through structural assumptions (e.g. ICP, IRM). Reviewer MoMA also felt that the paper overclaims throughout, e.g. in claiming a "complete characterization" of OOD generalization. I agree with both of these criticisms, the authors' rebuttal notwithstanding, and moreover I think they're important enough to prevent acceptance at this time.
Decision: Accept (Poster)