Understanding Domain Generalization: A Noise Robustness Perspective

4. ... In page 4, how comes "the classifier become either $w_{spu}$ or $w_{inv}$"? ...

   We would like to clarify that $w^{(inv)}$ stands for the classifier that uses the invariant and nuisance features. Similarly, $w^{(spu)}$ is for spurious and nuisance features. It is not necessary for the classifier to choose between $w^{(spu)}$ or $w^{(inv)}$. In practice, it is more likely to be a mix of both. The main goal of theorem 4.2 is to show that under that gap condition, there exists another classifier $w^{(spu)}$ that has less norm than $w^{(inv)}$ with high probability. This suffices to show the model will not converge to the invariant classifier and thus have more reliance on spurious features.

5. The description of the Lemma C.1 is unclear ... it should be a conclusion that holds with high probability, but the lemma presents it deterministically.

   Thank you for pointing this out. Yes, our main result is based on the probabilistic bound. We apologize for the incorrect wording and have added the term "with high probability" for both Lemma C.1 and Theorem 4.2.

6. ... Some of the symbols are not described (just mentioned) in this paper ...

   We have added the mathematical definition of the symbols representing the classifier $w^{(spu)}$ and $w^{(inv)}$ in Appendix C.1. We will continue to improve the description of the symbols.

7. ... In the experiment section, I recommend that the authors discuss the values of the weights' norms ...

   Thank you for the suggestion. In Appendix D.3, we update the experiments on synthetic data and plot the norms of $w^{(spu)}$, $w^{(inv)}$, $w^{(spu)}\_{spu}$, $w^{(inv)}\_{inv}$ with respect to increasing noise levels. The results show that as the noise level goes up, $w^{(spu)}$ indeed tends to have a smaller norm than $w^{(inv)}$. At the same time, the change in norm gap between $w^{(spu)}\_{spu}$ and $w^{(inv)}\_{inv}$ is relatively small. Moreover, the classifier $w$ that uses all features also gets closer to $w^{(spu)}$. The empirical evidence is consistent with the implications of Theorem 4.2. However, for real-world image datasets, we are unable to show the norm comparison since we cannot be sure about which features are invariant or spurious.

Questions:

1. In all tables in experiments, the authors should add references to Mixup, GroupDRO, IRM, VREx.

   As adding references for these tables in ICLR format will break the current typeset, we have opted for writing the baselines in the main paper and reference them there.

2. The author should provide another theorem to illustrate that the classifier with a smaller norm becomes more favored by the model.

   In Appendix C.2, we have added two formal theorems shown by [5,6] related to the implicit regularization effect of (stochastic) gradient descent. In particular, [5] proved that logistic regression converges in the direction of the max-margin classifier, which is equivalent to the minimum-norm classifier given the right constraints. Thus, we can conclude that the model has the inductive bias of learning models with smaller norms.

3. The authors should provide further explanations on the regularization term in the practical surrogate.

   The goal of IRM [1] is to obtain classifiers that are simultaneously optimal across all training environments, but this induces a challenging bilevel optimization problem. As zero gradient is necessary for reaching the local minimum, IRM has the practical surrogate that minimizes the norm of the gradient to encourage reaching the local minimum for all training environments. Since our goal is to understand how the DG algorithms work in practice, we only analyze the practical surrogate of IRM, which is the de facto implementation across standard benchmarks. This has been updated at the beginning of Appendix B.1.

We hope that our justifications and discussions have addressed your concerns and will improve your opinion of our work.

[1] Arjovsky, M., Bottou, L., Gulrajani, I., & Lopez-Paz, D. (2019). Invariant risk minimization. arXiv preprint arXiv:1907.02893.

[2] Lyu, K., & Li, J. (2019). Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint arXiv:1906.05890.

[3] Nagarajan, V., Andreassen, A., & Neyshabur, B. (2020). Understanding the failure modes of out-of-distribution generalization. arXiv preprint arXiv:2010.15775.

[4] Sagawa, S., Raghunathan, A., Koh, P. W., & Liang, P. (2020). An investigation of why overparameterization exacerbates spurious correlations. In International Conference on Machine Learning (pp. 8346-8356). PMLR.

[5] Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S., & Srebro, N. (2018). The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1), 2822-2878.

[6] Zhang, C., Bengio, S., Hardt, M., Recht, B., & Vinyals, O. (2021). Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3), 107-115.

We would like to thank you for appreciating our analyses of the harmful effect of label noise with spurious correlations and the noise robustness of DG algorithms. We address your comments below.

Summary:

• We provide an extensive discussion to your concern about our assumptions and the applicability of the theorems.
• We provide theoretical justifications for the implicit bias towards minimum-norm solution and an additional empirical study to the norms of the classifiers.
• We thank your valuable suggestions for improving our paper, which has been revised accordingly in blue color.

Weaknesses:

1. My primary concern relates to the assumption of linear separability ...

   We think that the assumption is in fact more inclusive than it is restrictive, as discussed right after Assumption 4.1. This is because the linear separability is only assumed for the noise-free data distribution. In cases when the dataset is not linearly separable, we can view that as a result of adding some form of label noise to the clean data. For example, when some critical features are not observed, there may exist the same data points with different labels, and some can be viewed as label noise. A higher noise level corresponds to worse non-separability. However, we acknowledge that this analogy is by no means comprehensive of all cases.

   Moreover, it is also hard to have orthogonal invariant and spurious features...

   We believe that the orthogonality is actually a reasonable setup. Recall that by definition the invariant features are optimal across all environments. An alternative interpretation is that these features do not change even though the environment changes. For example, when classifying the cow/camel, the features of the foreground animal should not change as the background gets changed to grassland or desert. Now consider the case where invariant and spurious features are not orthogonal, then the spurious features will have a non-zero projection onto the invariant features. As the spurious features change across environments, its projection onto the invariant features also changes. This causes the invariant features to change, which violates the definition of invariance. Thus, it is common to assume a feature vector can be decomposed into spurious and invariant components that are orthogonal to each other. A similar assumption has also been adopted in prior works [3,4].

2. In practical scenarios, the minimum-norm classifier may not be the most suitable choice, which implies that Thm4.2 may not be applicable.

   For linear cases, we add two formal theorems shown by [5,6] related to the implicit regularization effect of gradient descent (GD) in Appendix C.2. In particular, [5] proved that logistic regression converges in the direction of the max-margin classifier, which is equivalent to the min-norm classifier given the right constraints. Thus, we can conclude that the model has the inductive bias of learning models with smaller norms. In practice, when the model becomes a neural network, and early stopping is often used, it is true that the min-norm may not always be favored. On the bright side, homogeneous neural networks have been shown to converge in direction to max-margin solution [2] as well. There is a potential to extend the current analysis and we leave that for future work.

3. The theorem does not sufficiently prove the ideas presented in this paper. ... No formal theorem is there to demonstrate the superior performance of the DG algorithm.

   Our norm-related analysis in Section 4.2 is independent of the algorithms, but the theorem is only applicable to ERM because it has been shown to have the implicit regularization effect with GD. For IRM and other DG algorithms, there is no guarantee that gradient descent still favors the small norm solutions. Thus, we explore an alternative path to explain the why DG algorithm succeeds in certain situations.

   Most of the existing works that analyze noise robustness or the generalization properties of the DG algorithms are done in expectation, which effectively have infinite samples. In contrast, we choose to explain the phenomenon observed with finite samples. We think it is more valuable to perform finite-sample analysis because in practice the model can overfit and memorize noisy samples. Consequently, certain desirable properties may not always hold if only analyzed in expectation. However, finite-sample analysis for DG algorithms is challenging, and we do not have a formal theorem yet. Thus, we have taken a more intuitive approach by analyzing the gradients of IRM and V-REx algorithms. To the best of our knowledge, despite its simplicity, the gradient analysis and its insights for these DG algorithms has been overlooked in the past. We hope this would shed light on future studies of the internal working of DG algorithms under a more practical finite-sample setting.

Dear reviewer qd9a, we would like to extend our thanks for your thoughtful review. If you have any remaining questions or concerns that were not covered in our previous response, we are glad to discuss them further.

References:

[1] Arjovsky, M., Bottou, L., Gulrajani, I., & Lopez-Paz, D. (2019). Invariant risk minimization. arXiv preprint arXiv:1907.02893.

[2] Creager, E., Jacobsen, J. H., & Zemel, R. (2021, July). Environment inference for invariant learning. In International Conference on Machine Learning (pp. 2189-2200). PMLR.

[3] Dwork, C., Hardt, M., Pitassi, T., Reingold, O., & Zemel, R. (2012, January). Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference (pp. 214-226).

[4] Hardt, M., Price, E., & Srebro, N. (2016). Equality of opportunity in supervised learning. Advances in neural information processing systems, 29.

[5] Nagarajan, V., Andreassen, A., & Neyshabur, B. (2020). Understanding the failure modes of out-of-distribution generalization. arXiv preprint arXiv:2010.15775.

[6] Ng, A. Y. (2004, July). Feature selection, L 1 vs. L 2 regularization, and rotational invariance. In Proceedings of the twenty-first international conference on Machine learning (p. 78).

[7] Rosenfeld, E., Ravikumar, P., & Risteski, A. (2020). The risks of invariant risk minimization. arXiv preprint arXiv:2010.05761.

[8] Sagawa, S., Raghunathan, A., Koh, P. W., & Liang, P. (2020). An investigation of why overparameterization exacerbates spurious correlations. In International Conference on Machine Learning (pp. 8346-8356). PMLR.

[9] Wang, J., Liu, Y., & Levy, C. (2021, March). Fair classification with group-dependent label noise. In Proceedings of the 2021 ACM conference on fairness, accountability, and transparency (pp. 526-536).

• W4: ... the conclusion from the experimental study is not fully convincing, and seems to need further exploration.

  The key message from our extensive empirical study is that DG algorithms work well for synthetic datasets with label noise due to their implicit noise robustness, but this is still not good enough to convincingly outperform ERM in real-world scenarios. We also provide our hypotheses and discussions in Section 7. As the aim of the paper is to demonstrate understanding and provide insights for DG problems, we hope our results can shed light on future works that take the implicit noise robustness into account.

Questions:

• Q1, Q2: .... The authors might need an ideal feature extractor that provides the disjoint sets of invariant, spurious, and nuisance predictors ...

  Please refer to our response to weaknesses 1,2 and 3.

• Q3: It seems like the overall problem setting is also relevant to the fairness problem. Is there any relevant study from algorithmic fairness literature that the authors know of?

  Algorithmic fairness aims to obtain predictors that satisfy certain criteria of fairness, such as demographic parity [3] or equalizing odds [4]. As discussed in [2], some fairness criteria can be related to the objectives used by DG. While DG focuses more on learning invariant representation that generalizes across environments, fairness emphasizes removing the bias, though fundamentally there are many similarities. Based on our literature review so far, from the perspective of label noise, the most similar work that we found is "Fair classification with group-dependent label noise"[9]. This work and its follow-ups show that when naively using fair constraints, having label noise for certain groups can degrade the accuracy for groups without label noise, such that the result becomes worse than ERM. However, it differs significantly from our work in two ways:

  • Their noise setting is group-dependent, while ours is uniform without discrimination.
  • They show that label noise is more harmful to fairness algorithms than ERM in expectation, while our finite-sample analysis and experiments show the opposite of that: label noise is harmful to ERM, but some DG algorithms can be more robust to that.

  We believe that such discrepancy is caused by their group-dependent label noise setting and our uniform noise setting is comparably more general to all groups. We have also added the discussion in Section 2 for related works.

• Q4: Is it possible to extend the discussion in Section 4, which is focused on subpopulation shift, to analyze the domain shift? Particularly, for the cases where the ERM or DG might fail.

  Overall, if we treat the domain-specific features as spurious features $x_{spu}$, our norm-based theoretical results about ERM relying on spurious features are actually applicable to domain shift. However, the concepts of majority group (w/ spurious correlation) and minority group (w/o spurious correlation), which we want to highlight for better clarity, are mostly discussed for subpopulation shift but uncommon for domain shift. Moreover, extending to domain shifts requires assuming the domain-specific features to have strong correlations with the labels, which may complicate the discussion.

  Regarding the failure mode of DG algorithms in domain shifts, we currently do not have a good theoretical answer. Prior works have shown invariance learning algorithms require a sufficiently large number of environments [1,7], so having too few environments constitutes a failure mode for DG. Other than this, we have also briefly discussed in Section 7 the possibility of learning spurious features also being a non-trivial task.

We hope that our clarifications have addressed your concerns and will improve your evaluation of our work by bringing out more insights.

We thank you for the insightful comments and recognizing our contribution to studying the advantages of domain generalization methods.

Summary: we have addressed:

• The practicality, generality, and limitations of us assuming the availability of disjoint features.
• How representation learning can be responsible for the experimental observations in real-world datasets.
• Related work to fairness.
• Potential extension to domain shifts.

Detailed responses to your comments are as follows:

Weaknesses:

• W1, W2, Q1, Q2: ... assuming that we have disjoint sets of invariant, spurious, and nuisance predictors. This seems to be a reasonable assumption for theoretical analysis. However, in real-world cases, we might not be able to have such disjoint sets of predictors ... Even for tabular data, we might need a proper transformation to have such ideal sets of predictors.

  We believe your major concern for Weakness 1,2 and Question 1,2 is the practicality of our assumption on having disjoint sets of invariant, spurious, and nuisance features, which require ideal feature extractors. We would like to argue that our analyses in Section 4 have broader implications:

  1. For linear cases, though not explicitly stated, our theoretical analysis in Theorem 4.2 generalizes to rotational feature transformation. To see this: logistic regression and SVMs have the rotational invariance property [6], which means that training on data with original features or rotated features effectively yield the same decision boundaries. This natural extension implies that the invariant, spurious, and nuisance features do not have to be in distinct dimensions, as long as they are orthogonal to each other. To further strengthen the idea, we extend our synthetic experiments by transforming the input features with random projection matrices onto the same dimension. We observe almost exactly the same trends in comparison to the case without random projection. We have included the discussions and experimental results in Appendix D.2, which is consistent with Figure 1 in the main paper. We believe this also addresses the concern for tabular data if the transformation is linear.

  2. Similar setting with linear models learning from orthogonal invariant, spurious, and nuisance features has been also made in prior theoretical works [5,8].

  3. For real-world tasks with non-linear feature transformations, Due to the complexity of deep learning models, we agree that it is hard to identify which and whether features have been extracted. However, we would like to highlight that the main objective of Section 4 is to show how label noise prevents ERM from utilizing invariant features. What we have demonstrated is the failure mode when invariant and spurious features can be extracted. Now, let's briefly consider two other scenarios where the ideal feature extractor does not exist:

     • Spurious features are not fully extracted: This can be viewed as having a weaker spurious correlation and our results still apply.
     • Invariant features are not fully extracted: The model has to exploit more spurious correlations and nuisance features, so it already fails to generalize.

     We believe that showing the failure mode of ERM under such an ideal situation encompasses some other failure modes without the ideal feature extractors. From this perspective, the assumption may not be overly restrictive. However, we agree such an assumption may affect the analysis of the benefit of noise robustness of DG algorithms, which we discuss below for W3.

• W3: So, such difficulty in having an appropriate representation might be responsible for the failure of the noise robustness to translate to better generalizability in the experimental study.

  We thank you for pointing out the insight and agree that representation learning is an important aspect of domain generalization. If such representations cannot be extracted in practice and only spurious features are picked up by the model, then no algorithms would work perfectly here. The phenomenon of DG algorithms succeeding for synthetic data but being on par with ERM for real-world data could potentially be caused by the representations learned. In particular, it might be the case that CMNIST has easier invariant features, but the real-world dataset does not, causing all models to fail to generalize. Currently, the standard evaluation of DG algorithms is still based on ResNet-50 pretrained on ImageNet. With more powerful feature extractors, it may be possible to see the expected trend as in the synthetic case, which is left for future work. We acknowledge that assuming those features are accessible by the model in the theoretical setup is one of the limitations that cause the gap from theory to practice, but we believe our analyses provide valuable insights from a new perspective to the DG community.

Dear reviewer TZVP, we thank you once again for your thorough review. We would like to ask if you have any other questions beyond our rebuttal above and we hope to clarify them in time during the discussion period.

Questions

1. Q1 - Can your theoretical framework comprehensively explain all domain generalization methods that address subpopulation shift and spurious correlations, or are there any inherent limitations?

   Our first theoretical analysis in Section 4 on the failure condition of ERM due to label noise and spurious correlations is applicable to both subpopulation shift and domain shift in linear settings. However, in practice, when the feature extractors are non-linear and both the invariant and spurious features may not be perfectly extracted by the model, our result from linear settings may not be directly applicable. Therefore, we perform extensive empirical study to verify our hypothesis in synthetic and real-world non-linear settings in Sections 6.2 and 6.3, respectively. We can observe that the performance of ERM degrades severely when label noise is introduced for synthetic and real-world subpopulation shifts. However, the issue is less severe for domain shifts.

   Our second analysis in Section 5 addresses the noise robustness of two invariance learning algorithms: IRM and V-REx, but not all domain generalization methods can be theoretically proven to possess such a desirable property. Various existing DG algorithms have different working mechanisms and it is challenging to generalize to all. For example, Fish [4] and Fishr [2] align the sample gradient from different environments, so that more assumptions are needed to examine the effect of gradient alignments on noise robustness or other properties. Moreover, similarities among DG algorithms may be drawn in expectation with infinite samples, but we focus on a more practical finite-sample perspective which adds more difficulty. We have added the relevant discussion in the revised paper.

2. Q2 - What motivated the selection of the methods used in the experimental section? Why were these particular methods chosen?

   For ERM-based algorithms, Mixup is a simple yet effective approach that has been widely studied from both empirical and theoretical perspectives.

   For DG algorithms, we choose a few most influential and well-cited algorithms with theoretical guarantees for comparisons. These algorithms also constitute the baselines for many other DG algorithms. In particular:

   • IRM is the first algorithm proposed to learn invariant/causal predictors from multiple environments with deep learning.
   • V-REx extends IRM with a simplified objective function that addresses covariate shift in the input distribution. It is also theoretically analyzed for homoskedastic environments (consistent noise level).
   • GroupDRO is one of the first algorithms proposed to specifically address subpopulation shifts by minimizing the worst-group risk directly. By utilizing the group information effectively, it has been considered the gold standard amongst many subsequent works that try to deal with subpopulation shifts without group labels.

   We have added detailed descriptions of these algorithms in Appendix E.2.

We hope that the additional insights provided in our responses and the revised paper can further improve your opinion of our paper.

References:

[1] Ahuja, K., Caballero, E., Zhang, D., Gagnon-Audet, J. C., Bengio, Y., Mitliagkas, I., & Rish, I. (2021). Invariance principle meets information bottleneck for out-of-distribution generalization. Advances in Neural Information Processing Systems, 34, 3438-3450.

[2] Rame, A., Dancette, C., & Cord, M. (2022, June). Fishr: Invariant gradient variances for out-of-distribution generalization. In International Conference on Machine Learning (pp. 18347-18377). PMLR.

[3] Sun, B., & Saenko, K. (2016). Deep coral: Correlation alignment for deep domain adaptation. In Computer Vision–ECCV 2016 Workshops: Amsterdam, The Netherlands, October 8-10 and 15-16, 2016, Proceedings, Part III 14 (pp. 443-450). Springer International Publishing.

[4] Shi, Y., Seely, J., Torr, P. H., Siddharth, N., Hannun, A., Usunier, N., & Synnaeve, G. (2021). Gradient matching for domain generalization. arXiv preprint arXiv:2104.09937.

We thank you for acknowledging our theoretical and empirical contributions to domain generalization and providing insightful suggestions. We address your comments as follows:

Summary:

• We have added empirical results for four more related algorithms and one NLP dataset to improve the generality of the results.
• We provide additional analysis of the limitations of our approach and more discussion about why the DG algorithms are selected.
• We have revised the paper accordingly with updates highlighted in blue.

Weaknesses:

1. W1: ... To enhance reader comprehension and provide a more thorough context, it would be beneficial for the authors to initiate with a comprehensive overview of domain generalization before delving into the specific scenario ...

   We thank you and agree with your suggestion. As we have already provided a comprehensive overview of the domain generalization problem in Section 3, we will move Section 3 ahead of Section 2 to improve the flow. We have also improved the writing of related work by adding more details.

2. W2: ... In order to strengthen the general statements proposed in the paper, it would be valuable to expand the range of DG algorithms under examination ...

   We agree that empirically examining more DG methods would improve our understanding and have added four more algorithms: CORAL [4] (domain adaption), IB_IRM [1] (DG), Fish [3] (DG), and Fishr [2] (DG). More details about the algorithms and results can be found in Appendix G.2. Due to the time limit, we evaluate these models on CMNIST, Waterbirds+, and PACS datasets, from which we can see the same empirical trend presented in the main paper still holds. For CMNIST, certain DG algorithms like Fishr and IB_IRM have the advantage over ERM. However, for real-world datasets, none of these algorithms clearly outperform ERM even under label noise setting. We believe that for these algorithms, the same pattern should also generalize to other datasets.

   As our experiments are extensive, to examine the algorithms further on all datasets, it would require training 1260 models for each noise level, which is quite expensive. Therefore, we only pick out a few representative datasets and influential algorithms for comparisons due to limited compute and space.

3. W3: The experiments of the paper are limited to tasks related to image classification, with no inclusion of other types of data, such as tabular data. This focus on image classification tasks allows the authors to delve deeply into this specific domain and gain insights relevant to this context. However, it's important to note that the findings and conclusions may not be directly applicable to other data types or domains, and this limitation should be kept in mind when interpreting the results.

   To incorporate more data types into our analysis, we perform empirical evaluation on CivilComments, a textual dataset for toxicity classification. The task description and results are added in Appendix G.1. In this NLP task, Mixup cannot be directly applied due to textual input. For other algorithms, GroupDRO has the lead in the noise-free setting, and V-REx exhibits slightly better noise-robustness. However, ERM still performs competitively compared to other algorithms even under label noise setting, which is consistent with the existing empirical observations.

4. W4: Section 5 only provides a description of IRM, but it would be valuable to have a more extensive discussion about other methods as well.

   Other than IRM, we have also included the analysis for the V-REx algorithm in Appendix B.2 and show that it has a similar property of oscillating between gradient descent and ascent for some data points, though with a slightly different mechanism. Furthermore, we have discussed in Section 6 about ERM, Mixup, and GroupDRO essentially sharing the same ERM objective and thus not having the noise robustness property. We choose IRM and V-REx as the two representative invariance learning algorithms because of their effectiveness and existing theoretical guarantee in expectation. We will discuss the challenges in extending our results to other DG approaches below in response to Q1.

References:

[1] Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S., & Srebro, N. (2018). The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1), 2822-2878.

[2] Zhang, C., Bengio, S., Hardt, M., Recht, B., & Vinyals, O. (2021). Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3), 107-115.

We thank your comments and acknowledging our positive contribution to domain generalization. We would like to address your comments as follows:

Summary:

• We discuss the importance of our work.
• We provide clearer explanations of the relationship between Theorem 4.2 and our main contributions. We revise the related paragraphs in Section 4.1.

Weaknesses:

1. W1. The failure of validation on real data is pessimistic, which seriously reduces the importance of the settings discussed in this paper, as real data does not fit well with simple noise settings.

   As our goal is to objectively study domain generalization, the result on real-world data with label noise (ERM-based methods performing competitively with DG algorithms) is not entirely pessimistic. We have demonstrated the consistency between theory and practice and the benefit of DG algorithms with experiments in coloredMNIST dataset. Moving on to real-world cases, the data is more complex and the features are more difficult to extract. We acknowledge that there is a gap between our theory and practice. However, our extensive empirical results on real-world data help researchers to develop an understanding and critically review the existing DG approaches. Moreover, we have elaborated in Section 7 about the potential reasons why the same patterns from synthetic datasets are not observed in real-world cases. We believe that our theoretical and empirical analyses provide insights from a new perspective and could drive new research advances in this area.

   Although real-world data are affected by more complicated noise, label noise is an important issue that is prevalent across domains. We believe that it is common to work with some form of simulated noise in the beginning, such as the uniform label noise used in this work.

2. W2. The main theoretical results of this paper have poor readability ... It is difficult to associate this principle with the main contributions described in the abstract of this paper.

   We have improved the writing in Section 4.1 of the revised paper with blue-colored text and hope that could help to clarify the connection between Theorem 4.2 and our contributions. We also provide more detailed explanations in response to your Q1 below.

Questions:

• Q1. I would like to know the relationship between Theorem 4.2 and ... How does this theorem reflect label noise?

  For "Specifically, our finite-sample analysis reveals that label noise exacerbates the effect of spurious correlations for ERM, undermining generalization", the overall rationale is that: label noise causes the spurious classifier to have less norm than the invariant classifier so that the model will rely more on spurious correlation. The rationale can be obtained with two steps:

  • Theorem 4.2 shows that having a more severe spurious correlation $\gamma$ and higher noise level $\eta$ both make the condition in Theorem 4.2 easier to satisfy. To interpret this, as the noise level of the label increases, the term $n(1 − \gamma)(1 − 2\eta)C$ on the right-hand side decreases, but the norm gap on the left-hand side of the inequality remains unchanged. Thus, the "if" condition is easier to satisfy, causing the spurious classifier to have less norm than the invariant one.
  • We have mentioned the minimum-norm bias of gradient descent (GD) in Section 4.1. This is also known as the implicit regularization effect [1,2]. As both types of classifiers are capable of reaching 0 training loss, the spurious classifier with less norm (less complex) is preferred by DG. Thus, the actual model we obtain is not purely invariant but utilizes spurious features, which hurts generalization.

  We restrict the consequence of having label noise to "exacerbating the effect of spurious correlations" because Theorem 4.2 also relies on the degree of spurious correlations. When the spurious correlation is high, having label noise will make it worse. In particular, for our synthetic linear and non-linear experiments, high spurious correlation may be less of an issue in a noise-free setting, but when combined with label noise, the generalization performance degrades severely.

  For "Conversely, we illustrate that DG algorithms exhibit implicit label-noise robustness during finite-sample training even when spurious correlation is present", in Section 5, we analyze the gradient of IRM (V-REx is also available in Appendix B.2), and show that it is more robust to memorizing label noise. In Section 6.2, on CMNIST dataset, we empirically show that IRM and V-REx algorithms perform well even after injecting label noise. However, ERM and Mixup perform worse than random guessing, indicating that spurious correlations are being exploited, despite searching over 60 sets of hyperparameters.

We sincerely hope our responses above have clarified your doubts about the connection between our contributions and Theorem 4.2 and will improve your opinion of our paper.

Dear reviewer jUs6, we appreciate you spending valuable time reviewing our work. We wish to confirm if our clarifications above have resolved your main concerns and we are glad to clarify any remaining doubts.