Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors re-check the invariance principle and show that out-of-distribution generalization is much harder for linear classification tasks, requiring much stronger restrictions in the form of support overlap assumptions on the distribution shifts. They propose an approach combining both information bottleneck constraints and the invariance principle to addressing the OOD generalization in both regression and classification tasks. 
main_review: I pretty like the theoretical analysis presented in this paper, from which we could get very insightful thoughts. 

In this paper, the authors use 0-1 loss for binary classification $\mathcal{Y}=\{0, 1\}$ and square loss for regression $\mathcal{Y}=\mathbb{R}$. I am curious if all the results in this paper can be extended to the other losses and to multi-class classification tasks. 

Although the authors admit in the final section that the proposed method mainly focuses on linear models. I would like to hear more from the authors about what the main challenge is when their theory is extended to nonlinear models.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work gives an indepth analysis to the sufficient conditions on the generalization of invariant risk minimization (IRM) in classification setting. Authors show that in order to guarantee good generalization, the support overlap condition of invariant features is required. Further, authors also show and validated that if the support overlap condition does not satisfied for spurious features, the combination of IRM objective and information bottleneck regularization (i.e., minimzing the mutual information $I(X; \Phi(X))$) is a reliable remedy.  
main_review: In general, this work made a few theoretical contributions. It specifies some conditions to guarantee good generalization of IRM in classification, especially the support overlap of invariant (or spurious) features. Some theorems (like Theorem 4) also partially explains why information bottleneck can improve generalization, which is less investigated before. 

However, I still have some concerns:
1. Authors combine the objective of IRM and the minimizing of entropy of representation $H(\Phi(X))$. However, instead of directly optimizing the differential entropy (which is usually hard), authors made a Gaussian assumption and alternatively minimize the variance. I am not so sure how practical is this assumption in real-world data or applications. Because the experiments in this work is just on simple synthetic data or MNIST-like data. 

Can you provide more justifications on this approximation or more empricial results on recent domain generalization benchmarks (i.e., the DomainBed [1] or WILDS [2]) in which both IRM and ERM are baselines. 

[1] Gulrajani, Ishaan, and David Lopez-Paz. "In search of lost domain generalization." arXiv preprint arXiv:2007.01434 (2020).

[2] Koh, Pang Wei, et al. "Wilds: A benchmark of in-the-wild distribution shifts." International Conference on Machine Learning. PMLR, 2021.

2. Similar to the information bottleneck, I feel the hyperparameter $\gamma$ (in Eq. (7)) controls a trade-off and plays a significant role to the performance. Here, there is another hyperprameter $\lambda$ that controls the degree of invariance. Can you give a more indepth analysis on the trade-offs between these terms or how different values of $\gamma$ or $\lambda$ influence the performance of the combined objective?

3. I still feel there is a jump from your analysis in Section 3 to the introduction of information bottleneck regularization (i.e., $\min H(\Phi(X))$) in Section 4. Just focusing on your illustrative example, when $\Phi$ only picks invariant features, the entropy is minimum. However, it does not mean when the entropy is minimized, $\Phi$ exactly picks the invariant features. For example, the suprious features only also gives the minimum entropy. My question is how can you guarantee this regularization alone is sufficient for IB-IRM to only focus on invariant features, rather than other combinations of invariant and suprious features? or did I miss something?

Finally, some minor suggestions:
1. It would be much better if authors can give some illustrative examples on "fully" informative features and "partially" informative features. 
limitations_and_societal_impact: Authors clearly mentioned limitations and future work directions.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper investigates the conditions that are needed to provably generalize OOD in the linear classification tasks. Comparing with the linear regression tasks, linear classification tasks need more strong conditions to guarantee the OOD generalization. 

The paper first proposes the overlap assumptions on both invariant and spurious feature and analyze the OOD generalization guarantee under these assumptions. The theorem shows that only both two types of features satisfy the support overlap assumption can we expect the IRM to solve the OOD generalization problems. Then the paper study the possibility of solving the problem only with the support overlap assumption on the invariant features. The proposed method uses both information bottleneck and invariance constraints. Theoretical results show that the proposed IB-IRM can successfully solve the problem in both fully and partially informative invariant features situations. The experiment results are consistent with the theoretical results.

main_review: This paper is well organized and easy to follow. The theoretical results are presented in a logical order and the conclusions are quite clear. Although all the proofs are in the appendix, authors provide the intuitions by examples and discussed the significance of the theorems. 
With these theorems, the proposed IB-ERM is well-motivated. Some relaxations are involved from the original formulation in (6) to the final objective in (7). The influence of the IB term to optimization is discussed in Theorem 5. 

Overall, this paper is well-written, with comprehensive theoretical analysis to support the proposed IB-ERM for linear classification. 
Detailed comments/questions:
1.	Although we can construct tasks like CS-CMNIST and the model in assumption 2, is it true that, with high-probability, the oracle in real world is PIIF? Since the conditional independency is a special case of the conditional dependency. Then, what is the advantage of IB-IRM, comparing to other methods designed for PIIF, e.g., (Rosenfeld et al. 2021)?
2.	The proposed IB-IRM in eqn (6) takes IB as the objective and ERM and invariance as constraints. Will theorem 4 still holds if one take IB as an additional constraint in IRM? Can we have more insights to design the relaxed objective later?
3.	How did you tune the coefficient of the two penalty terms at the equation (7) in real experiments? Any ablation study to show the influence of these two penalties in a different situation?
4.	In sec 5, authors make discussion about the results on CMNIST tasks. How about the experimental results on linear unit tests? Why only make comparison on three and six training environments? Do we have any prior knowledge about which tasks are PIIF and which tasks are FIIP? IB-IRM is not the best across all the tasks.
5.	Minors: 1) put the DAG into Figure 2? 2) ref the definition of “support overlap invariant/spurious features” in table 1; 3) Is the observation in figure 3 general for different values of \lambda and \gamma? 4) In Theorem 3, “some of the ERM and IRM solution..” is not rigorous. “these exist”?

limitations_and_societal_impact: See the detailed questions in the main review, especially question 3 and 4.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: - The authors first argue that IRM is insufficient to obtain good test performance (only using invariant features) on OOD data at test time when the OOD support is not in the ID support
- Then they prove for a particular distributional assumption on the spurious features, that (additionally) limiting the differential entropy of the representation can solve this issue and lead to OOD generalizing predictors
- In some toy experiments, they show that IB-IRM sometimes performs better
main_review: Strengths:
- They argue that the information bottleneck in some situations can help to obtain the invariant predictor when invariance itself cannot (when there’s not enough support overlap)
- In their (few) experiments on modified colored MNIST datasets, including one where IRM does not improve much compared to ERM (CS-MNIST) and demonstrate that adding the IB regularizer leads to better OOD generalization

Weaknesses:

Theory
- The insufficiency results for IRM are not surprising, e.g. FIIF problem was already noted in Nagarajan et al
- Comparison with other works that show limits of IRM such as Srebro - their examples themselves seem to make a similar point as FIIF?

Since the theoretical contributions are insufficient, we now examine the methodological contributions 
Methodology:
- major criticism: is this supposed to be a game-changer for practice? then it’s absolutely necessary to do OOD generalization experiments on real world datasets (such as WILDS). the current datasets are completely toy (versions of colored MNIST)
- since variances are huge compared to MSE for examples 1/1s, 3/3s with 6 environments, one can really only compare the performances of the methods using CS-MNIST and AC-MNIST and perhaps example 2/2s which is rather unsatisfying as empirical evidence for a method
- table 3 suggests that more environments worsens the benefits of adding IB even in an FIIF setting? more discussion/experiments on that would be necessary
- again regarding the point that the variances are huge for Example 1/1s with 6 vs. 3 environments: a comment on that in the main text would be useful - is that expected and why?

Update: Apologies, I actually was not able to understand the problem that I previously had when I had a brief new look at the paper (before even reading your response). I'm guessing I was thinking about some problems that confused my mindset when reading. Now the sufficiency result actually sounded trivial since in the case of spurious correlations AND support overlap all possible environments in E_all would also be spuriously correlated...

Thanks for discussion on relation to Kamath et al. 

I agree Nagarajan did not provide formal results, but hinted at the problem so this is why I said it is not surprising. 

Thanks for comment on six-environments to discuss the high variance. That comment should be added to paper.

Adding experiments on Coco addresses my main concern (I still think the methodology is the main contribution). However I would like to see more experimental details before giving the nod + experiments on one more dataset. The lack of real-world experimental evidence was the primal reason for the score and hence I still tend to reject the paper. The number of scenarios where IB-IRM or IB-ERM do better is still rather limited and currently only includes COCO in terms of non-toy dataset (without having been able to see the revision and experimental details) which is in my opinion still quite rather meager for publication at Neurips. How about WILDS? I believe if the authors run a more extensive experimental study this paper can be accepted at the next venue.

I didn't see this point addressed: "Table 3 suggests that more environments worsens the benefits of adding IB even in an FIIF setting? more discussion/experiments on that would be necessary"
limitations_and_societal_impact: Authors do have a section on limitations and motivate future work through that.
There's no potential negative societal impact for OOD detection per se ... (for certain applications it could, but this holds for almost all problems that one can think of solving).
review_title: null

Meta-review: After substantial discussion, including additions of new experimental results from the authors, reviewers have come to a consensus that this paper provides interesting and relevant theoretical results, as well as sufficient empirical evidence supporting the theory, to merit acceptance. We expect that this work will appeal to the ERM, IRM, and Information Bottleneck communities. We particularly think that the exponential speedup of convergence of the IB-based methods will be of theoretical and practical interest. We look forward to reading the updated version of the paper with the additions and revisions the authors have promised.
Decision: Accept (Spotlight)