Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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
- 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
- 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)
- 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
- 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
- Their model selection strategy chooses better models across 3 standard datasets (PACS, Office-Home, VLCS), for all combinations of the OOD dataset. 

main_review: After rebuttal: added comments below. I think the paper would be a nice addition to the conference.

---------------------------------------------------------------------------------------

Strengths
- The paper seems technically sound, and well-executed.
- 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.
- 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.
- 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
- 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.

Weaknesses
- There seem to be large gaps between the theory and practice. 
- 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.
- 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?

- I'm not sure if their assumption of learnability seems reasonable for a few reasons
1. 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?
2. 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.
3. 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
4. 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…
5. 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?

- 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
- 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))
- Here we would need (s, \delta) learnability, where \delta = I_{TV}(h, E_avail)
- 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

- 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?

- 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.

More comments:
- 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?
- 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?
- 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?
- 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.
- 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

Overall, 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!

limitations_and_societal_impact: Looks alright!
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
main_review: The work is interesting and it addresses a relevant problem. However I am not certain I completely understood or share some statements.
(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.

(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?

(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?

Experimental 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.

It 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)
limitations_and_societal_impact: No assessment provided as the work is theoretical.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.

${}^{\small 1}$defined over the training domain\
${}^{\small 2}$that forms a relationship between variations of informative features in training and unseen domains\
${}^{\small 3}$that informative features have limited variance in the unseen domain

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)_
- 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)_

limitations_and_societal_impact: There is no discussion of societal impact but limitations are addressed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

However, there are a number of weaknesses:
1. The definition of expansion (3.4) is too strong, so the main results seem immediate from the assumptions. 
2. The main bounds (Theorems 4.1, 4.2) should not hide factors in d.
3. 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?
4. 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.
5. In Algorithm 1 and Figure 1, why do the authors treat each dimension as a separate feature?
6. In the experiment, what happens when we take the sup over d dimensions instead of the average? Does that yield worse model selection performance?
limitations_and_societal_impact: No discussion of societal impact.
review_title: null

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)