On the Limitations of General Purpose Domain Generalisation Methods

• The authors show that all learning algorithm converge slowly with respect to the number of training domains, implying lack of algorithmic progress. Specifically, they assert universal ERM optimality under asymptotic conditions with finite domains and samples, potentially overlooking domain-specific invariance properties and structural assumptions. Such a claim is too assertive (A typical example is the CMNIST, where ERM consistently performs worse than well-motivated DG algorithms). Without any specific characterizations on distribution shift [1]，it is unlikely to capture the key factors governing generalization performance across domains.

  [1] An Information-theoretic Approach to Distribution Shifts, NeurIPS 2021.

• The theoretical results do not involve the algorithm architecture. For modern DNNs, the Rademacher complexity bounds are basically vacuous, we cannot gain meaningful insights from the current claims.

• In practical, the i.i.d. assumption of domain is too restrictive to apply. Besides, as shown in previous study [2,3], proper assumptions about the problem statement and data-generating process plays a key role in characterize DG.

  [2] On learning invariant representations for domain adaptation, ICML 2019.

  [3] The risks of invariant risk minimization, ICLR 2021.

• The main results are basically rooted in the pioneering theoretical investigation on ERM [4, 5]. The technical contributions on theoretical prove are quite limited.

  [4] Rademacher and Gaussian complexities: Risk bounds and structural results. JMLR, 2002

  [5] Foundations of Machine Learning, MIT Press, 2018.

Given the current results presented by the authors, I have to disagree with the main claims of the paper that no model substantially outperforms ERM. Here are the reasons:

• The problem formulation of DG deviates from the mainstream settings. This paper focuses on minimizing the expected population risk of the model on randomly sampled target domains (eq. 5). This objective is equivalent to ERM on i.i.d sampled domains, but is already shown to be vulnerable to OOD data. Instead, DG is usually formalized as a minimax optimization problem [1] e.g. $\min_f \max_P L_P(f)$, which is not covered in this paper. This results in a different optimal model $f^*$.

• It is consensus that Rademacher complexity is not sufficient to explain generalization of deep learning. To let $\mathcal{R}_m(\mathcal{F})$ scale with $1/\sqrt{m}$, one require $m$ to be significantly larger than the capacity of the models, which is hardly met for modern deep networks. Instead, they can easily fit the given random labeled datasets and we will get $\mathcal{R}_m(\mathcal{F}) \approx 1$ in most cases which invalidates the bounds.

• In the definition of minimax excess risk, $\mathcal{P}$ is considered to be the set of all possible sample distributions over $X \times Y$. This is rarely the case in practice since $X$ and $Y$ always share some common causal relationships among different domains. The authors claim that $\mathcal{P}$ can be easily extended to a certain set of distributions, but to my understanding the proof of Theorem 4 relies on this condition. At (eq. 42 $\to$ eq.43), the labels $y_1$ to $y_{2m}$ can no longer be arbitrarily selected when $\mathcal{P}$ has changed. Thus, the lower bounds may not apply to practical learning settings.

• There is strong evidence that ERM results in poor generalization under certain conditions, e.g. [2]. I do not see conflicts between the settings of [2] and this paper. Explanations on why the results in this paper do not apply to Colored MNIST in [2] should be included.

[1] Sagawa S, Koh PW, Hashimoto TB, Liang P. Distributionally Robust Neural Networks. InInternational Conference on Learning Representations 2019 Sep 25. [2] Arjovsky M, Bottou L, Gulrajani I, Lopez-Paz D. Invariant risk minimization. arXiv preprint arXiv:1907.02893. 2019 Jul 5.

The setup of this paper is quite broad, with very general theorems, making it challenging to assess the precise difficulty of the domain generalization problem. One popular approach in domain generalization is invariant risk minimization (IRM), introduced by Arjovsky et al., and subsequently explored in other studies. This line of research aims to identify patterns that are consistent across multiple domains, thereby disregarding spurious correlations that vary across domains. This approach aligns with (and is motivated by) causal inference, which assumes that only the causal components of correlations remain stable across domains.

In this paper, the authors begin with a general setup (Section 3), assuming that distributions are generated i.i.d. from a distribution over the space of distributions. This aligns well with the Bayesian framework, where such a setup is known as a hierarchical prior. However, in the context of domain generalization, if all domains are generated independently and identically, it becomes unclear what form of similarity the model is expected to learn across domains. If there is no notion of similarity we expect to learn from domains, what is the motivation behind borrowing information from various domains? The theorems in Section 3 are fairly basic, applying standard symmetrization techniques, which leads to general but uninformative convergence rates. For instance, the derived rate, $1/\sqrt{mn} + 1/\sqrt{n}$, essentially simplifies to $1/\sqrt{n}$ (as $m > 1$), meaning that the rate depends primarily on the number of domains. This result is unsurprising, given the independence assumed across all domains.

In Section 4, the authors introduce conditions that allow for potentially faster rates, with these conditions depending on the distance between domains. However, it remains unclear whether the upper and lower bounds align precisely or if the dependence on $\sigma$ in the upper bound is optimal.

Additionally, the current presentation of the results may be challenging for readers less familiar with empirical process theory. I suggest assuming a specific complexity measure for the underlying function class (such as covering number) and then expressing the results in terms of $(m, n, \sigma)$ for both the upper and lower bounds.

My main concern is that some of this papers' claim is not rigorous. For example, in the discussion of Theorem 4 (equation (11)), the authors claim that the minimax excess risk scales as $\Omega(\frac{1}{\sqrt{mn}} + \frac{1}{\sqrt{n}})$, since the two terms in lower bound are both $\Omega(\frac{1}{\sqrt{mn}} + \frac{1}{\sqrt{n}})$, and $\Omega(\frac{1}{\sqrt{mn}} + \frac{1}{\sqrt{n}}) - \Omega(\frac{1}{\sqrt{mn}} + \frac{1}{\sqrt{n}})$ scales as $\Omega(\frac{1}{\sqrt{mn}} + \frac{1}{\sqrt{n}})$. This claim is not true in general.

Also, the authors claim that the risk "scales as" something, where many related quantities are hiding in the "$\Omega$". Then they claim that this best-case behaviour matches the worst-case scaling behaviour of ERM, so that ERM already has the optimal scaling behaviour for general DG problems. However, since many things are hiding in the "$\Omega$", I do not think this claim is valuable enough.

On a technical front, the paper is fairly straightforward: since suprema in the Rademacher complexity nicely "split" by triangle inequality, the upper bounds boil down to two application of the standard Rademacher bound machinery. The min-max lower bounds also follow from fairly standard machinery and are fairly expected.

This of course would be not a problem if the results were surprising or suggested interesting training interventions --- which unfortunately I don't think it's the case here: (1) The main reason for a lot of the developments mentioned in the related works and introduction (e.g. the causal modeling view in IRM) was introduced as a richer way to model distribution shift. In fact, in the a lot of the causality-inspired works (e.g. IRM), the goal is not to only do well in expectation over environments, but in the worst case over some set of environments (e.g. all possible sets of interventions). Because the paper commits to a metric of performance "in expectation" over the choice of environment, and takes a worst-case view over the set of predictors in some class --- the fact that the Rademacher complexity characterizes both the performance of ERM, and the information-theoretic optimum is not surprising. (2) The "actionable insights" suggested in the paper (amount of regularization to pick) are also predicated upon the "in-expectation" view of generalizing over a domain distribution. The more typical viewpoint in recent DG work is to focus on a "worst-case" notion of generalization in some set of domains (e.g. all interventions on a subset of variables in a causal graph) --- in which case choosing the regularization strength is much trickier. In fact, as Gulrajani-Lopez Paz show --- a "cheating way" to choose regularization strength in IRM, if allowed to "peek" in the test set, is why a lot of papers over-reported the performance of IRM.

Overall, I think neither the technical ingredients in the proofs, nor the results themselves stand well on their own.