Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper proposes an iterative feature matching algorithm to solve domain generalization problem with logarithmic environment complexity, compared to linear complexity of ERM and IRM. The authors also provide theoretical justification and empirical evaluation.
strengths_and_weaknesses: Strength: 
(a)	The investigated problem is of great importance in invariance-based domain generalization and out-of-distribution generalization.
(b)	The proposed method has sound theoretical justification.
Weakness:
(a)	The experimental part is relatively weak, several more baselines (refer to Domainbed) and benchmarks (Colored-MNIST or other real-world datasets) should be included for better insight and significance.
(b)	The organization of the manuscript could be improved by moving proofs into appendix rather than piling them up in main body.
(c)	The authors should elaborate more on the gap between linear setting in theoretical analysis and real world applications with more complex models.

questions: Refer to Weakness
limitations: Refer to Weakness
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper analyzes the environmental complexity in domain generalization: how many environments are needed in order to recover an invariant predictor? While most existing papers give pessimistic results on domain generalization algorithms, this work shows positive theoretical results on the sublinear environment complexity. However, the data model may not be practical for real usage.

--post rebuttal--
Thank you for the detailed response and the effort for improving the draft and adding discussions. From the new experiments, it seems that the IFM + CORAL does not improve the performance of CORAL (or very slightly). Therefore, it remains questionable whether the proposed method can be applied in practice, or it could be that the data model studied is too simple to represent more realistic tasks such as PACS/VLCS/OfficeHome. Although the theoretical analysis seems interesting, my main concerns are not addressed. Finally, understanding the non-linear feature embedding is more interesting (though challenging) and I would expect some theoretical results on this case in the revised draft.

--post post rebuttal--
After checking the response of Reviewer D1nV I decide to update my score due to the proof of the IRM lower bound which uses tools from differential topology. I haven't checked the proof in too much detail though.
strengths_and_weaknesses: Strengths:
1. This work is novel and interesting to the domain generalization field, and analyzes the theoretical model proposed in Rosenfeld et al. The data generation is anti-casual, we first generate the (binary) uniform label distribution and then generate the invariant and spurious features. Finally, the input variable is generated. The novelty part in this work is the addition of a Gram matrix from Gaussian.
2. Based on the data model, the authors propose Iterative Feature Matching, or IFM, for finding invariant featurizer and classifier in $O(\log d_s)$ rounds with $\tilde{O}(1)$ training environments per round. Therefore the environmental complexity is smaller than the $O(d_s)$ complexity of ERM/IRM.
3. The presentation is clear with solid theoretical results, it involves interesting techniques from probability theory, statistics and differential topology, which might be useful for later theoretical results in this field.

Weaknesses:
1. The setting borrows from Rosenfeld et al, which shows the reason why IRM may fail in some simple cases. However, the goal of the current paper is to show an DG algorithm that works in practice. As much as I appreciate the theoretical contributions about the positive results of IFM, in practice (e.g. on MNIST), the algorithm does not work. Moreover, as mentioned in Appendix C, there is even a $O(1)$ environmental complexity algorithm based on Assumption 3.2, which further adds doubts to the applicability of this assumption. If IFM does provide intuitions into algorithmic design, the authors need to at least show some more practical examples.
2. The lower bounds of ERM/IRM do not seem novel compared to Rosenfeld et al. The only difference is the assumption 3.2 vs. assumption 3.1. In Line 149-150, the authors claim that the analysis applies to all but a measure-zero set of covariances, but I'm not quite convinced since the Gram matrix is built from standard normal and the $\bar{\Sigma}$ is bounded.
3. A practical algorithm for finding the maximum dimension $r_t$ in Alg 1 is needed. This is very important for practitioners to apply this algorithm.
4. In the experimental section, the main contribution part is 1) addition of orthonomality of the featurizer in the Gaussian model; 2) matching the sufficient statistics of each layer vs. only matching the last layer. This experiment may be too far away from the linear featurizer and the data model presented in the theoretical analysis. If matching the representation of each layer works for CORAL/DANN/MMD in practice, could the authors try some experiments or prove some theoretical results? 
5. In line 203-205, the goal is to provide a theoretical justification of the feature matching algorithm, rather than to solve a specific data model, but the main theoretical results are based on this model.
6. The IFM algorithm resembles Independent Component Analysis (ICA). Discussions and comparisons of the similarities and differences are needed.



questions: See the questions above.
limitations: As the authors acknowledge in Appendix D, the main limitation is the applicability of IFM in realistic datasets.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the domain generalization (DG) setting.  The authors construct a simple yet fundamental data generating procedure for DG, which shares similarities with that of _The Risks of Invariant Risk Minimization_ (henceforth RoIRM).  The authors propose an iterative algorithm which requires only logarithmically many training domains in the spurious feature dimension $d_2$ to generalize to particular test environments given infinitely many samples per domain.  This result stands in contrast to results from other works (including RoIRM)l, which show that IRM needs $O(d_s)$ environments to generalize in the linear setting.  The authors also provide several toy experiments to illustrate their results.
strengths_and_weaknesses: ### Strengths

---

**Problem setting.**  I liked quite a bit about this paper.  I felt that first and foremost, it attempts to theoretically study what makes domain generalization hard, and in what settings we expect to generalize OOD.  This is essential, as it is not well understood in the literature when domain generalization is even possible.  The data generating procedure discussed in Section 3 seems quite natural, and it certainly extends the framework of RoIRM to the setting of (more) general covariance matrices.  The other innovation over RoIRM here seems to be the generation of the test environments.  

**Definition of environmental complexity.**  This seems like quite a natural definition of complexity in DG; certainly removing the caveat that in practice we get a finite sample from each environment helps to illuminate the structure of the problem.  It would be interesting to see future works study this definition for other algorithms/data generating models.

**Theoretical work.** Thm. 1 seems to be a strong result here, because it proves the existence of an algorithm which generalizes with $\log(d_s)$ in a particular linear DG setting.  To my knowledge, such a result was not known in the literature before this work.  I believe that the proof techniques may be of independent interest here, which adds to the contribution of this paper.

### Weaknesses

---

**Over-simplification of the field of DG in the intro.**  One minor point: The introduction reads as if the *standard* assumption to make in DG is that the distributions of labels given features should be environment dependent (lines 21-22).  Furthermore, there is a claim that algorithms that rely on these assumptions "dominate" DG benchmarks (lines 23-24).  I think that both of these claims are in doubt.  There are many other works that make different assumptions on the set of stable or invariant features (see e.g. [Zhang et al., 2021] and [Robey et al., 2021], which assume domain/measurement shift).  I think this points to the fact that this paper could benefit from a related work section, which is notably absent in this submission.  WRT the point about feature-matching algorithms "dominating" the leaderboards, this seems untrue based on recent surveys: [Gulrajani & Lopez-Paz, 2020] and [Koh & Sagawa et al., 2021].  Both of these works show that ERM is a rather strong baseline relative to all other algorithms, especially relative to feature-matching algorithms.

**The term "feature matching."**  One point of confusion throughout the work was referring to "matching."  I think it would help if the authors could formally define what it means to "match" features.  The reason I bring this up is that it gets rather confusing in the non-linear case how features are being "matched."  The paper seems to assume that the reader is a priori going to know what this means, but I imagine that many readers may become confused at this point.

**Algorithm description.**  The description of the algorithm that is actually run in practice is confusing, and crucial details are missing.  One question is: How are the subsets selected?  Is $T$ a hyperparameter?  If so, how is it tuned?  Furthermore, which Alg. 1 shows us the basic steps of the algorithms, it's not clear how one would actually go about implementing this method.  In particular, the step in line 5 seems challenging.  In the end, the authors appear to tweak the implementation of CORAL by removing the ERM term.  I think it would be reasonable to expect a more robust discussion of the implementation of these methods -- which also seems to be missing from the appendices.  I am listing this as a weakness because if a contribution of this paper is to propose this algorithm as a new method, which seems to be the case based on this:

> "This work presents the first domain generalization algorithm which provably recovers an invariant predictor with a number of environments that scales sub-linearly with the spurious feature dimension."

then the paper should be responsible for connecting the pseudocode in Alg. 1 to an implementable optimization problem.

**Why doesn't CORAL work?** Related to the previous point, after reading the paper I am still unsure of why CORAL fails in the experiments whereas IFM succeeds.  Is it the fact that IFM optimizes for each $U_t$ separately in rounds, or is it the dropping of the ERM term that helps?  Perhaps this is already answered somewhere, but it was not obvious to me after reading.

**Experiments.** The experiments feel like a weak point of this paper, with the caveat that this paper seems to be more of a theoretical paper than an experimental one.  Even still, I think it wouldn't be unreasonable to expect a stronger set of experiments here.  Some comments:

* The Noisy MNIST dataset doesn't seem to satisfy the assumption concerning $Z_2$ below line 136.
* The authors claim that

> "Our results in Section 7 suggest that practitioners may benefit from feature matching algorithms when the distinguishing property of the signal feature is indeed conditional distributional invariance"

However, the authors do not run their proposed algorithm on any standard benchmarks, making it difficult to discern whether or not IFM would be useful for practitioners.  Indeed, it looks like IFM isn't even run on the Noised MNIST dataset, which raises concerns about whether IFM on its own works (without the ERM loss term).
* The authors refer to $U_t$ as a "layer" (line 325), which is confusing to me.  Is this supposed to be related to the layers of a DNN?
* It's unclear how the algorithm works in the nonlinear case, i.e. when you need to do feature matching for different layers.  As I mentioned above, a better understanding of how the algorithms are implemented would lead to stronger insights from the experiments.

### Overall evaluation

---

Overall, I liked this paper.  I think that it makes a strong theoretical contribution, and that it studies an important and understudied aspect of DG.  I believe that the paper is generally well written, and I appreciate that although this is more of a theoretical paper, the authors ran some experiments.  This being said, there are a number of drawbacks that I would like to see addressed.  Firstly, the algorithmic description and experimental evaluation are weak compared to the theory, but I think both of these points could be addressed (see above).  Another weakness is the lack of a related work section, which ideally would more broadly discuss recent developments and algorithms proposed for the DG setting.  All of this being said, I'm leaning toward accepting this paper.

### Citations

---

[Zhang et al., 2021] Zhang, Marvin, et al. "Adaptive risk minimization: Learning to adapt to domain shift." Advances in Neural Information Processing Systems 34 (2021): 23664-23678.

[Robey et al., 2021] Robey, Alexander, George J. Pappas, and Hamed Hassani. "Model-based domain generalization." Advances in Neural Information Processing Systems 34 (2021): 20210-20229.

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

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


questions: **Test environment generation.** I won't list this as a weakness per se, but I do have questions regarding how the test environments are generated.  One natural question is whether (or to what extent) this model of test environment generation is necessary for achieving OOD generalization in log(d_s) training environments.  Let's say that I was to select completely new means $\mu^e_2$ and covariances $\Sigma_2^e$; then let 

$$Z_2 \sim\mathcal{N}(Y \cdot \mu_2^e , \Sigma^e_2).$$

Would there be any hope of generalizing in this setting?  I think that this question is important because in practice, we would expect to receive data from *new domains* with new underlying parameters.  This is not to say that the setting analyzed here is less relevant; on the contrary, it seems evident that there needs to be some sort of connection between training and test domains to achieve OOD generalization.

**Dimension of style.** The authors say that

> "stylistic variations between domains are likely high-dimensional."

Is there any way to justify this?  In the case of the standard ColoredMNIST benchmark, this seems to be somewhat untrue given that the background color correlation could be controlled by a very low-dimensional parameter.  Furthermore, given the rise of large generative models which can capture semantic changes in low-dimensional feature spaces, I would tend to push back on this statement ever so slightly.

**Tranversality.**  It would be helpful if the authors could explain a bit more what they mean by this _tranversality_ condition.  I anticipate that the definition is technical, but even some intuition for this condition would be helpful.

**I.I.D.-ness.** I assume that the labels are being drawn i.i.d. from a Bernoulli, as are the latents.  This should perhaps be stated more explicitly for completeness.

**Why does $r_t$ shrink to $r$?**  It would be great if the authors could help me to understand why $r_t$ will eventually shrink to $r$.  What is stopping it from failing to shrink?

**Uniqueness.** One small question I have WRT Thm. 1 is whether $w^\star$ is necessarily unique.

**"Simple" algorithm.**  What is the basis for including this so-called "simple" alternative algorithm in the main text?  If it is mentioned, I would expect the authors to compare with it in the experiments section.  But the inclusion of this algorithm seems to be a bit orthogonal to the contribution of the paper.

**Class imbalance.**  If $\eta\neq 1/2$, how would Thm. 4.2 change?  Would the condition that the test risk under the 0-1 loss be larger than $1/2$ become $\eta$ (or perhaps $(1-\eta)$?

**ERM results.** In Thm. 4.2, I thought that we were operating under the assumption that $\bar{\Sigma^e_2}$ could be _adversarially_ chosen, and that it would not be diagonal.  It seems that one would want the assumptions of the three theorems to align; so unless I am misunderstanding something, this discrepancy calls into question whether all three results can hold under a common assumption.

limitations: The discussion in Appendix D is sufficient in my eyes.
review_title: null

Meta-review: metareview: This paper gives theoretical guarantees for the problem of domain generalization from a few training environments. This paper gives an algorithm that achieves strong theoretical improvements over prior work (logarithmically many training environments vs linear number for existing methods).  The reviewers also felt that there are novel insights that may be of independent interest in this space.  There was some concern by some reviewers about the extent of the empirical evaluations. However, since this is primarily a theoretical paper with strong improvements, the contributions seemed above the bar for NeurIPS. 
confidence: Less certain
Decision: Accept