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(: ' 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
V(3 h, Eavas), BES
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 Phely=(tly) = 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(.), Ind (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(ss) (s(D (h, Exvai))
(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 Eay. 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
Σ
(Phejyo 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 yy (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 T]. 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 ff 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: 190::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, Femannd 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:::/// URttttssstsoooooeeeeeeeeeee /ttttp:s//operrwiieee http://wwwwwwwweeeeeeeeeeeeeeeee
[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::000300068: 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.0309, 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.0061 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": "vtcVbvfkb9K", "reviewer": "Reviewer_MbMa", "summary": "In this paper, the authors focus on understanding out-of-distribution (OOD) generalization through the variation of informative${}^{\\small 1}$ features in training and unseen domains. Towards that, they introduce measures such as _variation_ and _informativeness_ as well as an _expansion function_, which are in turn used to introduce the concept of _learnability_. Providing generalization bounds, the authors show that OOD generalization can be characterized by the expansion function${}^{\\small 2}$ under certain conditions on the _learnability_ property${}^{\\small 3}$. Moreover, based on the findings, they propose a strategy for model selection (Algorithm 1). They further illustrate through experiments that their model selection strategy outperforms the ones selected using validation accuracy, and the constraint of informativeness is crucial to reason OOD generalization through variation.\n\n${}^{\\small 1}$defined over the training domain\\\n${}^{\\small 2}$that forms a relationship between variations of informative features in training and unseen domains\\\n${}^{\\small 3}$that informative features have limited variance in the unseen domain\n", "questions": "", "limitations": "", "rating": 8, "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": "- I very much enjoyed reading this paper. I do not have much knowledge about the prior work in regards to OOD generalization, but I find the paper very clear and well-written which is important especially for those who do not have a complete background on the topic _(clarity)_\n- To my assessment, this work is original. That is, I am not aware of any prior work that forms a rigorous understanding of OOD generalization through variations of features. Moreover, the model selection strategy that is built upon this understanding is demonstrated to be effective through numerical experiments _(originality, significance, quality)_\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no discussion of societal impact but limitations are addressed.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not see any ethical issues within this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "C3p_Rj0TBq", "reviewer": "Reviewer_Ja6b", "summary": "- They consider an OOD generalization setting, where we have a set of available domains we train on, E_avail, and a superset of test domains, E_all. They define L(f, E), the worst case loss of f on a set of domains E\n- They define informativeness (how predictive a feature is for the label, worst case across domains) and variability (how much P(feature | y) varies across domains\n- They define learnability: roughly speaking that all features that don't vary much in the available domains E_avail, also don't vary much in the E_all (for all features that are somewhat informative)\n- Their main theorem roughly says that L(f, E_all) - L(f, E_avail) can be upper bounded by the variability of P(features | y) in E_all. By learnability this can be upper bounded by the variability of P(features | y) in E_avail. The notion of variability is the max TV distance between P(features | y) in different domains\n- This inspires a model selection heuristic: look at the accuracy of a model on E_avail, but penalize models where the variability of the features is high, because this means the models may mess up OOD\n- Their model selection strategy chooses better models across 3 standard datasets (PACS, Office-Home, VLCS), for all combinations of the OOD dataset. \n", "questions": "", "limitations": "", "rating": 6, "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": "After rebuttal: added comments below. I think the paper would be a nice addition to the conference.\n\n---------------------------------------------------------------------------------------\n\nStrengths\n- The paper seems technically sound, and well-executed.\n- I looked through the proof of Theorem 1 fairly carefully / line-by-line, and it looks correct. The only part I wasn't able to verify was the relation between Radon transform and the pdf, but they say this is from prior work.\n- The experimental results are nice. The procedure looks simple, with not much potential for tuning, and seems to get improvements across 3 datasets, and combinations of OOD datasets.\n- The idea of looking at variability of the features across domains, besides just accuracy, seems intuitive and reasonable, if you're interested in worst case accuracy across test domains\n- The proof I read (Theorem 1) in the Appendix is very well written and easy to follow, more so than many other submissions. It looks like a complete piece of work.\n\nWeaknesses\n- There seem to be large gaps between the theory and practice. \n- Average vs worst case: as one example, looking at variability makes sense to me if we are interested in **worst-case** error across test domains. For example, if f1 and f2 have the same worst-case accuracy in the available domains, but f1's features vary much less, I'd expect the worst-case accuracy on test domains to be better for f1. But it's not clear that it makes for *average* accuracy.\n- The title is too general and strong. There are many theories for OOD generalization. I'd even view \"A theory of learning from different domains\", by Ben-David et al, as a theory for OOD generalization. It says if we train on a source domain, and the H-Delta-H divergence between source and target (OOD) is small, then you generalize well to the target (the model doesn't need to use any target data). Can you change it to something more specific? Something that conveys that you're studying feature variability and using it as a model selection strategy?\n\n- I'm not sure if their assumption of learnability seems reasonable for a few reasons\n1. It seems quite strong - to start with, could you give some reasonable examples where we would have a bound on learnability? For example, maybe suppose we have a distribution over domains, and we sample some domains randomly for E_avail. Under what conditions would we have learnability?\n2. Let's look at the case where we have a distribution over domains. If variability was averaged across domains, then showing learnability holds seems like a standard concentration result. But in this case variability takes the max over domains, which doesn't concentrate as easily.\n3. In addition, learnability requires the relation between the variability over E_all and E_avail to hold over **all** features, which could make the concentration much harder\n4. My intuition also is that the harder problem is to show learnability. Once we show learnability, it isn't too surprising that the conclusion holds. If the features don't vary much in TV distance, then yeah the accuracy can't vary too much across domains…\n5. I could also define other notions of learnability: for example a feature that gets high accuracy on all the available domains (that is the worst case accuracy over domains E_avail is high), gets high accuracy on all domains in E_all. In that case, my heuristic would be to pick a model that gets the best worst case loss on E_all. Why is this notion of learnability based on variability (more) interesting?\n\n- For Theorem 1 and its proof: I'm not sure why you couldn't take the following simpler approach: Up to line 28 of the proof, you show that it suffices to bound C * I. I can be immediately bounded by taking the sup over e' \\in E_all, e \\in E_all, since this is a larger set since originally we had e' \\in E_all, e \\in E_avail, with E_avail \\subset E_all\n- But sup_{e, e' \\in E_all} I = sup_{e, e' \\in E_all} TV( P(h^e | y) , P(h^e' | y) ) \\leq V_{TV}(h, E_all) \\leq s(V_{TV}(h, E_avail))\n- Here we would need (s, \\delta) learnability, where \\delta = I_{TV}(h, E_avail)\n- The main change is we're using V_{TV}(h, E_avail) in the upper bound instead of V^sup as defined in the paper. It's a bit unclear why the additional complexity of defining V^sup, V^inf, and bounding various properties of the characteristic function was warranted\n\n- They pick r_0 based on the standard deviations of accuracy and variability on the available datasets. This looks mathematically nice, but why is it a good choice?\n\n- It could be nice for the theory to explain why using variability in model selection gives better models than just using the accuracy. I'm not quite able to piece together the existing theorems for this.\n\nMore comments:\n- In equation 4, right, can't the characteristic function be complex? In that case, can't the integral be complex? If that's true then it may not make sense to upper bound by a scalar?\n- In line 39 of the proof, in the supplement, the integral is over h, so should it be a dh instead of dv? If not, what is v?\n- In the supplement, can you give more details on what models were chosen by your model selection procedure for each of the 12 cases in table 1?\n- On line 297, it says \"we design a parallel GPU kernel density estimation to speed up the whole process\". I'm not sure I got any details of this (didn't find it in the Appendix), so I'm not sure how to factor this as a contribution.\n- Maybe consider giving some background about the Radon transform in the Appendix, maybe even just copying over some of the basic properties from the lemma. This is very minor, but I think it can make things more readable\n\nOverall, I like the idea of using feature variability to choose models, the experimental results are compelling, and they have some initial theoretical results. Good job!\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Looks alright!", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6+1 hours"}, "extra_text": {}}, {"review_id": "7_nwcZifRyo", "reviewer": "Reviewer_eZ4t", "summary": "This paper discusses a formalized approach to generalize to OOD data. It proposes assessing differences in the domains relying on distributional distances designed to account for variation in the feature distribution and informativeness of features. Generic bounds, and bound in the specific case of a linear classifier, are offered. Finally a practical heuristic algorithm is designed to perform model selection and experimentally evaluated.", "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 work is interesting and it addresses a relevant problem. However I am not certain I completely understood or share some statements.\n(line 123-125): \"If a feature is informative for the classification task and invariant over \\Epsilon_avail, then to enable OOD generalization from \\Epsilon_avail to \\Epsilon_all, it should be still invariant over \\Epsilon_all\" - I am not sure here about the meaning of \"enable\"; it seems to me that a feature that is informative for the classification task and invariant over \\Epsilon_avail still does not tell us anything about generalization (as clearly shown by the colored MNIST example); if it is also invariant over \\Epsilon_all, then it is a good feature for generalization. This seems to me to be better captured in line 145-148.\n\n(line 128): \"Expansion function\": it seems to me that the expansion function could simply be swapped with a constant. I suppose the s() function is introduced to provided tighter bounds, is that so?\n\n(line 155-156): \"In addition, there are multiple choices of (s(), \\delta) to make an OOD generalization problem learnable: larger \\delta will filter out more features, and so s() can be smaller (flatter)\": this may be clearer if stated mathematically, because larger \\delta implies smaller or equal (<=) not necessarily smaller (<) expansion function (again thinking about the coloured MNIST example). In a sense the learnability of a problem seems to me not just something up to us tuning (s(), \\delta), but a consequence of the problem itself. Also the wording \"smaller\" recalls the idea of expansion function as a constant. \"with smaller derivative\" may describe it better?\n\nExperimental results are illustrative, although further validation of the theoretical results would have been interesting. Also more precise consideration on the computational complexity (beside line 297-298 that delegate KDE to a GPU) in relation to other algorithms would have been useful.\n\nIt would have been interesting to have a better connection with work done in the covariate shift adaptation (the setup of the problem seems to me to fit the covariate shift framework) as well as comparison with other classical theoretical work on assessing learning from different domains (Ben-David)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No assessment provided as the work is theoretical.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "6qagtE-hLnF", "reviewer": "Reviewer_8ktt", "summary": "This paper proves an error bound on domain generalization based on the a new concept of expansion function, which characterizes the extent that any useful feature's variance is amplified in the test domains over the training domains. The theory motivates a model selection criterion which has good empirical performance on benchmarks.", "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": "This paper studies the theoretical foundations of domain generalization, which is an important direction. The theoretical derivations are rigorous; presentation is clear, and the experiments support the theory.\n\nHowever, there are a number of weaknesses:\n1. The definition of expansion (3.4) is too strong, so the main results seem immediate from the assumptions. \n2. The main bounds (Theorems 4.1, 4.2) should not hide factors in d.\n3. The model selection criterion (equation 11) and the choice of $r_0$ should have more rigorous theoretical guarantees. Can the authors prove a theorem about the quality of this selection criterion?\n4. It seems that every model selection criterion could be used to regularize the model during training. Based on this theory, one should regularize the conditional feature variance across training domains. However, algorithms based on this idea, e.g. conditional DANN, do not improve over ERM. This suggests that in realistic scenarios there are plenty of informative features with high OOD variances, so the main bounds are likely to be vacuous. In my opinion, a truly useful bound should include the complexity of feature extractor h.\n5. In Algorithm 1 and Figure 1, why do the authors treat each dimension as a separate feature?\n6. In the experiment, what happens when we take the sup over d dimensions instead of the average? Does that yield worse model selection performance?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No discussion of societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper investigates a variety of theoretical questions relating to out-of-distribution generalization. The reviewers found this paper to be very strong and well executed. The reviewers found the theoretical results to be sound, clearly explained, and compelling. Therefore, I recommend acceptance of this paper.

In the discussion, there are many suggestions for improvements to the story and the description of the motivation and intuition between some of the results and claims in the paper. I would encourage the authors to think about this, and other comments from the discussion, when writing the next version of the paper.
Decision: Accept (Poster)