Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: Overview: The authors study the out of distribution generalisation problem in detail wherein a model may incorrectly use spurious correlations in the data to make predictions on data at test time. This is a fundamental problem and very crucial/difficult to tackle across various domains

Quality and Clarity: The paper is fairly well written overall.

Originality and Significance: OOD detection is a well-studied problem that has proven difficult to date; it's highly relevant across applications in high-stake domains. The approach taken in this paper is to a) study tasks that are easy to succeed on, b) show that OOD failure occurs even in these easy settings. The authors subsequently show that geometric and statistical skews are necessary for failure. As such the approach has limited novelty, since it does not offer a concrete solution to the OOD detection problem but rather examines necessary conditions for OOD failure.

Pros: 1) The authors study a highly relevant problem of OOD failures
2) The authors present a fairly rigorous empirical analysis of geometrical and statistical skews on CIFAR and MNIST

Cons: 1) The paper is limited in novelty; while the authors state find that OOD failures result from statistical and geometric skews, they do not provide an adequate solution to overcoming these skews

2) OOD failures are only studied in the context of small theoretical examples or image tasks such as MNIST or CIFAR. However, OOD failures are widespread across various domains and become especially important to study in high risk settings such as in a clinical context etc. I would have liked to have seen some exposition of these problems in a real high-risk setting.
review_title: a fair paper but lacking in novelty

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper investigates the reasons why machine learning models usually fail to generalize out-of-distribution even in easy-to-learn tasks where one would expect these models to succeed. The authors propose two kinds of skews in the data: geometric and statistical, to explain this behavior and theoretically demonstrate it in the linear and easy-to-learn settings. 

Pros:
+ The problem studied in this paper has been one of the most important in the community and this work has a meaningful attempt on the theoretical side.
+ The theoretical results obtained by analyzing the simplest tasks are insightful and could be seemingly drawn on in more general settings. 
+ The experiments are carefully designed based on the constraints, which is well in support of their theoretical claims. 

Major concerns:

I agree with the authors on most of their explanations on the failure modes of OOD generalization from the geometric and statistical perspectives in easy-to-learn tasks. However, the authors claim that these two skews are “not just a sufficient but also a necessary factor for failure of these models in easy-to-learn tasks“, which I think might be overclaimed, even in the easy-to-learn tasks defined in the paper. I do believe that both geometric and statistical skews play a role in the failure of OOD generalization, but they might not be the only reasons. In fact, even if there exist no spurious features, machine learning models might fail to generalize out-of-distribution as well. 

Here is the example. Let us consider a comparison task, where we aim to learn a linear classifier to predict which one of any given two values {x_i, x_j} is larger, i.e., it outputs +1 if x_i >= x_j, and otherwise it outputs -1. For simplicity, let us further assume that -1 =< x_i, x_j =< +1 and x_i^2 + x_j^2 =1. In this case, x_inv = (x_i, x_j) and there is no x_sp. It is also easy to check that this task satisfies the five constraints stated in the paper. Given the training dataset in which all data points (x_i, x_j) are satisfying that 0 =< x_i, x_j =< +1 and x_i^2 + x_j^2 =1, it is easy to learn a linear classifier that can be well generalized to the whole domain [-1, +1]. If we represent  (x_i, x_j) in the polar coordinate system, then (x_i, x_j) is converted to (1, \theta). In this case, we have x_inv = \theta and no x_sp, which also satisfies the five constraints. Although we still can learn a perfect linear classifier in the training data, it is impossible to generalize to the whole [-\pi, +\pi] corresponding to [-1, +1]. The reason is that this task is no longer linearly separable. From the example above, we can see that even without spurious features, some simple transformations only on invariant features would render OOD generalization impossible. This would be another failure mode beyond the geometric and statistical skews. 

Minor concerns:
- The constraint on fully predictive invariant features seemingly simplifies the OOD generalization problem too much, making the theoretical results hard to apply to more general settings. Actually this constraint circumvents two key questions which play a pivotal role in the OOD generalization. One is how to justify whether or not features are fully predictive and invariant across all the domains or environments. This involves the generalization assumption, like Assumption 8 of Arjovsky et al. (2019). The other is how to learn the partially predictive invariant features which, albeit not fully predictive, remains invariant across all the domains. If we want to solve the OOD generalization problem in practice, these two questions have to be answered. 

- The example given in Constraint 3.2 is not suitable. The distribution of invariant features must be identical across all domains, otherwise these features should not be treated as “invariant”. The exact distribution of the shapes of cows and camels vary across domains because they are not the true invariant features. 

- Constraint 3.5 is too strong as well. It circumvents another key question in the OOD generalization: how to identify x_inv and x_sp. If we can identify them, the OOD generalization would be reduced to a simple ERM problem. 

Other comments:
- The last 6th line before section 3.1 says that Pr_{D_test}[x_sp \cdot y >0] = 0.0. I believe this is a typo, right?
- Overall I feel too much content is placed in the appendix and it affects the fluency of reading a bit. I suggest that the authors re-organize the content and put back some stuff to the main text. 

review_title: A good theoretical attempt to explain the failure of OOD generalization 

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: I stand by my initial review that this is a strong submission, and having read through the other reviews and author responses, I am raising my confidence level as well (I think I have a solid grasp of this work's potential import). I disagree with critiques of the paper's novelty and practicality -- I think it provides new insights into OOD problems with substantive theory (not common) and provides actionable insights to boot. Also, the the revised manuscript is much improved. I hope this gets accepted.

-----

This submission presents a rigorous analysis of a subset of ways in which machine learning models can fail when encountering out-of-distribution (OOD) samples (often referred to as train/test skew or as train/scoring skew in industry). As the paper notes, the topic has received a great deal of attention, particularly under other guises ("domain adaptation"). However, much of that attention has aimed at pragmatic or heuristic solutions (various tricks to design or learn "invariant" features), while our fundamental understanding of what goes wrong in OOD situations remains incomplete. This paper aims to fill those gaps in understanding by studying simplified settings, and asking the question: why does a statistical model learn to use features susceptible to shift ("spurious" features) when the task can be solved using only safe ("invariant") features. After formulating five constraints (guaranteed to hold true for easy-to-learn tasks), they go on to show that failures come in two flavors: geometric skew and statistical skew. They analyze and explain each in turn, while also providing illustrative empirical results.

I like this work a lot (though I am more lukewarm on the paper itself, see below), and barring discovery of a fatal flaw during the discussion, I would advocate with some enthusiasm for its inclusion in the conference. The paper's claims are stated at the bottom of page 2 as:
1. Careful design and articulation of "easy-to-learn" settings in which there are few, if any, unmeasured variables that could confound the findings (a weakness in previous work on this topic).
2. Identification of two (but not the only two) distinct types of OOD failures that occur even in easy-to-learn settings, in the form of necessary and sufficient data "skews."
3. Experimental evidence to illustrate and support the analyses from (2.), along with enlightening discussion.

I agree with the paper's claims, though I admit that I was not previously familiar with, e.g., Sagawa 2019 or Tsipras 2019, and so cannot confidently situate this work amongst related research. I also feel my understanding may still be somewhat superficial -- I buy its arguments but don't have a particularly strong intuition yet for the two flavors of skew (particularly in non-toy settings).

This work has a very strong scientific flavor (not always true of machine learning research): I would liken the restriction to carefully designed "easy-to-learn" settings to a well-designed laboratory experiment in which there are few, if any, unmeasured variables that could confound the findings. It is very elegant and satisfying to read and think about. I would anticipate that this paper will inspire a lot of follow-up work, in which other researchers adopt the "easy-to-learn" and "skew" framework and terminology and even utilize the specific experimental designs in this paper. After all, machine learning researchers love adopting intellectual frameworks and benchmarks that they can build upon rapidly.

The "easy-to-learn" constraints articulated in Section 3.1 are sensible and clearly stated, and I am unable to find fault in them thus far. I agree with this statement on page 5: "any algorithm for solving OoD generalization should at the least hope to solve these easy-to-learn tasks well."

The experiments were thoughtful and well-designed, and their results are presented effectively: each plot, it seems, illustrates a particular point or supports a specific argument in the paper. For example, I like how Figures 2 and 3 serve as visual summaries of the geometric and statistical skew sections, respectively. A reader (particularly a savvy one familiar with the relevant related work) could probably skip Sections 4 and 5 (three pages total!) and still get the high level idea simply by skimming the plots and reading the captions of those two figures.

The largest weakness I perceive concerns the clarity and accessibility of the writing: for example, the connection drawn in Section 4 to the work on norms in over-parameterized neural nets is very interesting, but I'm not sure the text fully succeeds in further connecting it to OOD settings. In particular, certain details of the ongoing discussion of majority and minority groups aren't entirely clear (to me, at least)...are minority group samples available during training, just in smaller number? In that case, what is the OOD "shift" -- the prevalence of the minority group at test time?

Likewise, I'm not sure I really connected with the takeaway in Section 5 -- is it that early in the optimization, the "spurious" weights get updated repeatedly by an amount proportional to the spurious correlation, and that it then takes a long time to undo these updates, if at all? The statistical skew section is definitely more abstract and perhaps a little harder to connect to practical settings, vs. geometric skew where the bridge is the previous work on "norms."

My recommendation is to accept this submission, and at the moment, I am willing to advocate for it. However, it is entirely possible I am missing (or misunderstanding) key details, and so I am eager to discuss with the other reviewers.
review_title: Intriguing work that yields potentially fundamental insights about out-of-distribution prediction errorrs

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper studies generalization under distribution shift, and tries to answer the question: why do ERM-based classifiers learn to rely on "spurious" features? They present a class of distributions called "easy-to-learn" that rules out several explanations given in recent work and isolates the spurious correlation phenomenon in the simplest possible setting. Even on "easy-to-learn" distributions, linear models obtained from ERM use spurious features owing to either the dynamics of gradient descent trained on separable data (very slow convergence to the max-margin classifier) or a certain geometric skew in the data.

Pros:
- The paper address a question of great interest to the ICLR community: generalization under distribution shifts.
- The "easy-to-learn" set of instances seems like a reasonable test-case to understand robustness to distribution shifts before moving to more complex setting.
- The fact that spurious feature use can arise on the "easy-to-learn" instances suggests that previous explanations are underpowered in the sense that they're ruled out by this construction, but the pattern still arises.
- The "statistical" skew shows how the dynamics of gradient descent can introduce brittleness  to distribution shift, albeit in a limited setting.

Cons:
- This paper is written is a way that's confusing and frequently difficult to follow. Rather than focus on explicating the core phenomenon well and supporting it with clear theorems and well-justified experiments, the authors at times take a shotgun approach and mention numerous constructions (often in-line), references to empirical results, descriptions of experiments, that seem to obfuscate rather than clarify the core phenomena they're presenting. For instance, the "geometric" skew in Section 4 is never precisely explained.
- In a similar vein, the paper does not justify the experiments they run in light of the phenomena they seek to "intuitively understand." For instance, in Section 4/5, the paper presents a litany of experiments, without explaining how they fit into the "easy-to-learn" framework or relate to a phenomena described by the theorems. It's possible there's a connection, but it's not evident to this reader. 
- The experiments focus on a variety of synthetic distribution shifts. While this may be useful in understanding the constructions in the paper, it's not evident to what extent these 'skews' and the 'spurious/invariant' distinction given here can explain the lack of robustness observed in practice on "real" or "natural" distribution shifts.

==================

Update after rebuttal:
Thank you to the authors for their detailed response. The clarification and updates in the geometric skews section and the more explicit justification and connections between the framework/theoretical results and the experiments improved readability and clarity. I also appreciate putting greater weight on the theoretical contributions and "easy-to-learn" task definitions, which provide a simple but non-trivial test case for robustness research. I'm increasing my score accordingly.
review_title: Interesting simple "test case" for analyzing distribution shift; Poorly presented

Meta-review: This paper studies the reasons for failure of trained neural network models on out of distribution tasks. While the reviewers liked the theoretical aspects of the paper, one important concern is about the applicability of these insights to real datasets. The authors added an appendix to the paper showing results on a real dataset that mitigates this concern to an extent. Further, there are interesting insights in the paper to merit acceptance.
Decision: Accept (Poster)