Understanding Domain Generalization: A View of Necessity and Sufficiency

Authors: Long Tung Vuong, Vy Vo, Van-Anh Nguyen, Trung Le, Thanh-Toan Do, Mehrtash Harandi, Dinh Phung
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords: Domain Generalization

Abstract:
Despite the rapid advancements in domain generalization (DG), the majority of DG studies center on establishing theoretical guarantee  for generalization under the assumption of sufficient, diverse or even infinite domains. This assumption however is unrealistic, thus there remains no conclusive evidence as to whether the existing DG algorithms can truly generalize in practical settings where domains are limited. This paper aims to elucidate this matter. We first study the conditions for the existence and learnability of an optimal hypothesis. As the sufficient conditions are non-verifiable, our identified two necessary conditions become critical to guaranteeing the chance of finding the global optimal hypothesis in finite domain settings. In light of the theoretical insights, we provide a comprehensive review of DG algorithms explaining to what extent they can generalize effectively. We finally introduce a practical approach that leverages the joint effect of the two sets of conditions to boost generalization. Our proposed method demonstrates superior performance on well-established DG benchmarks.

Decision: reject
Reviewer scores: 5, 3, 3, 3, 5

Reviews and discussion:
<thread>
creation date:
1730508098060

thread_type:
official_review

<thread_object>
creator: reviewer_rzuw

<content>
summary:
This paper first studies the conditions for the existence and learning of an optimal hypothesis. The authors analyze the existing methods on whether they meet the necessary conditions 3.3 and 3.7. They further incorporate the sufficient representation constraint via ensemble learning and present a novel representation alignment strategy that can enforce the necessary conditions. They verify the effectness of the proposed method on five datasets against four baseline methods.

strengths:
The paper is well-written and mathematical sound.  The proposed necessary conditions can be used to verify whether a method is good or not.

weaknesses:
The experimental results lack too much baseline to compare with, e.g., IRM, VREx, IIB, IB-IRM mentioned in section 4.2.

questions:
There is a line of works that also use mutual information for invariant representation. The authors have not mentioned and compared with them. 

Cha, J., Lee, K., Park, S., & Chun, S. (2022). Domain Generalization by Mutual-Information Regularization with Pre-trained Models. ArXiv, abs/2203.10789.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730644169133

thread_type:
official_review

<thread_object>
creator: reviewer_thnp

<content>
summary:
This paper studies the sufficient and necessary conditions for the success of domain generalization (DG) problems. The authors demonstrate that under the assumption of a covariate shift setting, where causal support is covered by the training domains, having a sufficient number of diverse training domains or learning an invariant representation function will enable a DG algorithm to generalize effectively. However, as meeting these sufficient conditions is often impractical, the authors introduce necessary conditions: specifically, that the optimal hypothesis for the training domains must also be optimal for the global domain, and that the representation function must serve as a sufficient representation. Furthermore, the authors apply these conditions to analyze existing DG approaches. They also propose an algorithm designed to learn sufficient invariant representations by partitioning each training domain into subdomains based on their labels.

strengths:
1. The use of sufficient and necessary conditions to identify potential failures in previous DG works is both interesting and significant.

2. Partitioning each training domain according to its labels and aligning the corresponding partitions across different training domains seems to be an effective strategy.

weaknesses:
1. I have concerns regarding the causal relationships between variables in this paper, particularly with verifying that the label $Y$ is conditionally independent of $E$ given $Z\_c$. This seems essential to justify the covariate shift assumption made in Assumption 3.1. Another potentially related concern is whether your analysis is constrained solely to covariate shift. Under covariate shift, $P^{e}(X)\neq P^{e'}(X)$ for different domains, while $P^{e}(Y|X=x)= P^{e'}(Y|X=x)$ holds for any $e,e'\in\mathcal{E}$. However, what if conditional shift occurs, namely $P^{e}(Y|X=x)\neq P^{e'}(Y|X=x)$? Conditional shift is also common in DG and could imply that $Y$ may still depend on $E$ even when conditioned on $Z\_c$?

2. The theoretical development and writing in this paper lack rigor, largely due to many undefined or inconsistent notations. Below are some examples, though there are additional instances throughout the paper: 1) In Eq.(1) $\mathcal{F}^*$ is defined using the undefined term $\mathcal{L}$. I suggest defining the loss before introducing $\mathcal{F}^*$. 2) The notation $\mathcal{F}_{\mathbb{P}^{e_i}}$ first appears in Line 204 without definition; it is only defined later in Line 285.  3) In Line 227, it is unclear what is meant by $\mathbb{P}(g(x))=\mathbb{P}(Y|z_c)$. Since $g:\mathcal{X}\to\mathcal{Z}$, how can the probability of the representation output be equal to the conditional probability of the label? 4) In Lines 227, 232, 240, and 243, notations such as $g\in\mathcal{G}\_c$, $g\_c$ within the set $\mathcal{G}\_c$, $g_c\in\mathbf{G}\_c$ and $g\in\mathcal{G}\_c$ are used interchangeably. Are they intended to mean the same thing? 5) In Definition 3.7, the function set $\Phi$ is not defined. I assume $\mathcal{G}\_c$ refers to a function set mapping $\mathcal{X}$ to $\mathcal{Z}$, so $\phi\circ g:\mathcal{X}\to\mathcal{Z}$. In that case, what are the domain and range of $g\in\mathcal{G}\_s$? 6) In Line 252, $\mathcal{L}(h\circ g(x),y)$ is used, where, where the input space of $\mathcal{L}$ is $\Delta\_{|\mathcal{Y}|}\times\mathcal{Y}$. This notation contradicts other uses in the paper, such as $\mathcal{L}(f,\mathbb{P}^e)$. 7) In Line 452, $\Gamma:\mathcal{X}\to\mathcal{M}$ is defined, and then $\Gamma=f$ is set in Line 485. Given that $f:\mathcal{X}\to\Delta\_{|\mathcal{Y}|}$, does this imply $\mathcal{M}=\Delta\_{|\mathcal{Y}|}$? This seems inconsistent, as $\mathcal{M}$ was previously described as a set of indices. 8) In Line 486, what is the intended meaning of $m(i)$? 9) In Line 828, the expression $h(Y|g\_c(x))$ is unclear. Since $h:\mathcal{Z}\to\Delta\_{|\mathcal{Y}|}$, the equation $h(Y|g\_c(x))=\mathbb{P}(Y|z\_c)$ is confusing. 10) In Eqs. (9–12) in the Appendix, there seems to be an inconsistency. In Eq. (9), a conditional expectation is taken with respect to  $X=x$. How, then, does $\mathbb{P}^{e'}(X=x|z_c,z_e)$ appear in Eq. (10)? Did you mean to write $\mathbb{P}^{e'}(Z_c=z_c,Z_e=z_e|X=x)$ here? 11) In Line 899, the sentence "we construct a new function $h\_\phi=h\circ\phi$, where $h\circ g\_c$ belongs to $\mathcal{F}\_{\mathbb{P}^e,g\_c}$." is unclear. Could you clarify this?

There are additional such issues throughout the paper; I recommend a thorough proofread to fix these inconsistencies.

3. The lack of rigor in the writing raises concerns about the theoretical development in this paper. For example, in the proof of Theorem 3.6: 1) A minor note, Theorem A.5 restates Theorem 3.8, not Theorem 3.6 as indicated; 2) You let $x=\psi(z_c,z_e)$,  in the proof, which contradicts the setup in Line 116 and Proposition A.3, where $x=\psi(z_c,z_e,u_x)$. Why is $u_x$ omitted here? 3) More importantly, Eqs. (9–12) are confusing. While $f_c$ is defined as the risk minimizer under $\mathbb{P}^e$, it is unclear why it would also minimize the risk of every data from $\mathbb{P}^{e'}$; 4) By the way, the loss notation $\ell(f(X),\mathbb{P}(Y|z_c))$ used in Eqs. (9–12) differs from the notation $\ell(f(X),Y)$ used in the main paper, and as noted previously, the conditional expectation in this proof is unclear, as it seems to be taken with $X=x$ fixed. Could you clarify the exact conditional distribution over which this expectation is calculated? Please provide further clarification on the proof of Theorem 3.6.

4. Related to the previous concern, in Theorem 5.1, point (i), it seems that the intention is to provide an upper bound for the target generalization loss, but what is actually bounded is the average risk over the training domains. Additionally, in the proof of Theorem 5.1, could you clarify the steps between Eq.(19) and (20)? Specifically, it is unclear to me why the LHS in Eq. (20) includes a factor of $\frac{1}{|\mathcal{E}_{tr}|}$ while the RHS does not.

Overall, the paper is very unclear in its current state, and some theoretical results seem quite trivial (e.g., Theorem 3.4, Corollary 4.1). A significant revision is needed to improve clarity and rigor.


Minor comments:

1. Note that the $\mathcal{H}$-divergence was originally proposed in Ben-David et al (2006), not by Zhao et al.(2019).

Shai Ben-David, et al. "Analysis of representations for domain adaptation." Advances in neural information processing systems 19 (2006).

2. In Line 051, the sentence seems incomplete, as there is an extra "which."

3. In Corollary 4.1, $0\geq \delta\geq 1\Longrightarrow 0\leq \delta\leq 1$.

4. In Lines 453–455, the sentence "Let $\mathbb{P}^e_m$ be ..." defines $\mathbb{P}^e_m$ twice. Please rewrite this for clarity.

questions:
What is the exact difference between an invariant representation function and a sufficient representation function? This question may stem from the undefined function $\phi$; could you clarify its exact role?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730726326293

thread_type:
official_review

<thread_object>
creator: reviewer_zugg

<content>
summary:
Authors analyze the sufficient conditions and necessary conditions of achieving domain generalization. They further propose an algorithm to learn sufficient invariant representation. Experiments show their effectiveness.

strengths:
The systematic analyses of sufficient and necessary conditions are novel.

weaknesses:
1. Although the sufficient representation condition is a necessary condition, it is easy to satisfy using an identical function. The incorporation of this constraint is meaningful and beneficial only if there is empirical evidence that most of current algorithms are far from satisfying this. 
2. As a core part of the paper, sufficient representation constraint is only implemented by ensemble learning. The connection between them, although explained in the last paragraph of Section 5.1, seems farfetched. 
3. Only several basic methods are compared with the proposed method. You may refer to the github repo of DomainBed for more baselines. 

Minor issues:

- In Line 139, "the the". 
- In Line 145, "while vary"
- In Figure 2, the part of $\mathcal{F}\_{P^{e_2}}\cap\mathcal{F}\_{P^{e_3}}-\mathcal{F}\_{P^{e_1}}$ seems absent in the Venn diagram. 

##

questions:
Please refer to weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730780833730

thread_type:
official_review

<thread_object>
creator: reviewer_vflm

<content>
summary:
This submission considers domain generalization, where the learner observes data from source environments/domains and needs to learn a hypothesis that generalizes well to unseen environments. A particular structural causal model is assumed, where there are core and spurious latent factors, such that only the core latent factor causally influences the label and does it with an invariant $P(Y | Z)$ distribution. To make the problem well-defined, the authors make two assumptions: (i) a label identifiability condition similar to $P(Y|X)$ being invariant and (ii) that every possible value of the core variable is supported in at least one of the training domains. Furthermore, the authors assume infinite data from each domain, but finite training domains.

Under the stated assumptions, the authors present two necessary and two sufficient conditions for obtaining a hypothesis that is optimal for all domains, including the unseen ones.
* Necessary condition #1 (See definition 3.3) is simple and states that a globally optimal (i.e., optimal for all possible domains) hypothesis should be optimal for training domains too.
* Sufficient condition #1 (Theorem 3.4) states that if there are sufficiently many diverse training domains, then any hypothesis that is optimal for all training domains is also globally optimal.
* Sufficient condition #2 (Theorem 3.6) states that hypotheses that consist of an optimal (w.r.t. training domains) classification head on top of an invariant representation ($P(Y|Z)$ being invariant for *all* domains) are globally optimal.
* Necessary condition #2 (Theorem 3.8) states that globally optimal hypotheses that consist of a classification head on top of a representation $z = g(x)$ should be such that the representation function $g$ can be reduced to an invariant representation, i.e. there exists a function $\psi$ such that $P(Y | \psi(g(X)))$ is invariant.

The authors also show that the two necessary conditions together are not enough to guarantee global optimality. Based on the above results, the authors recommend designing domain generalization algorithms that strive for the sufficient conditions but making sure that the necessary conditions are satisfied. They propose a new domain generalization algorithm that partitions the input space and enforces similar marginal distributions of representations across environments conditioned in each part.

strengths:
* Understanding necessary and/or sufficient conditions for domain generalization is an important problem and can lead to effective domain generalization algorithms. The authors formulate a reasonable structural causal model and assumptions that enable formal analysis.
* Stressing the importance of having sufficient representations (Definition 3.7 and necessary condition #2) and pointing out that many domain generalizations fail to find a globally optimal hypothesis partly for not having sufficient representations.

weaknesses:
**Clarity and quality of writing.** The paper is hard to read and is unclear in many parts. Below are a few places where the writing can be improved.
* Lines 49-50: “In other approaches grounded in causality, there is typically an assumption of arbitrary targets” – this is unclear.
* Lines 050-053: At this point of the text it is hard to understand these two sentences. Writing can also be improved.
* Lines 076-083: It is unclear what sufficient conditions are referred to here.
* Equation (2) should be before equation (1) for better readability.
* Theorem 3.4 should state clearly where x comes from (the support of $P^{e_k}$ as I understand).
* Lines 195-196: Optimality for training domains is not really verifiable, given that we have only finite data from the training environment in practice.
( Lines 438-442: Unclear what is multi-view representation here. The notation does not make sense here.

**Not enough rigor in mathematical expositions.** I found some of the proofs hard to follow and possibly flawed.
* I am not convinced of the proof of Theorem 3.4. In fact, the Theorem 3.4 might not hold, because while with each added “diverse” environment at least one function is eliminated, this does not mean that in the limit only globally optimal functions would be left. Since a general function space is typically uncountable, the process might not converge as one adds countably infinite training domains.
* The paper is very loose about $\ell(y’, y)$ and $y’=f(x)$. Sometimes $y’$ is a distribution over classes, but sometimes it is a predicted hard label.
* The proof of Corollary 4.1 is unclear, although I believe the result is correct.

**Weak evidence that the proposed algorithm outperforms the baselines.**
* Looking at the result tables, the improvements over baselines seems marginal and can possible be attributed to the proposed method having more hyperparameters (number of subspaces per class, $\lambda_P$, and $\lambda_D$).
* As shown in Table 3, varying the number of subspaces does not have a large effect. To better motivate and understand the proposed method, it would be good to design a synthetic 2D domain generalization task and visualize what subspaces are found.
* It would be interesting to add a baseline consisting of only SRA to separate its effect from that of SWAD.

questions:
**A few minor comments**
* Proposition 3.5 needs a fix, it should be $P(y|g(x))$.
* Theorem A.5 is wrongly stated in the appendix, it repeats Theorem A.6.
* Results tables presented in Appendix have many cases where the bolded value is actually smaller than another value in the same column.
* Theorem 3.6 requires one domain to cover the whole $\mathcal{Z}_c$, which is not exactly what Assumption 3.2 is.
In my opinion this work needs a focal point. Currently it is unclear what the main takeaways and results are.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730919025595

thread_type:
official_review

<thread_object>
creator: reviewer_uuz4

<content>
summary:
This paper addresses the domain generalization (DG) problem by exploring it through the lens of sufficient and necessary conditions for generalization. The authors demonstrate that sufficient conditions are often unverifiable in practice. They then introduce two necessary conditions to ensure the performance of DG methods. Using this framework, they analyze and explain existing DG approaches. Finally, they propose a new method called Subspace Representation Alignment (SRA) and demonstrate its effectiveness across various datasets.

strengths:
1. The paper studies the domain generalization problem from the perspective of necessary and sufficient conditions, which is interesting and provides a fresh viewpoint.
2. The theoretical contributions are generally sound and contribute to a deeper understanding of DG.
3. The Subspace Representation Alignment (SRA) method proposed by the authors achieves good performance on various datasets.

weaknesses:
1. There are several concerns regarding Theorem 5.1:
   - It appears that the authors have omitted a $1/|\mathcal{E}_{tr}|$ term in the first term on the right-hand side (RHS) of equation (i) in Theorem 1.
   - The first term on the RHS is actually the same as the left-hand side (LHS), as verified by Equation (17) in the appendix. As a result, the inequality in Theorem 5.1 seems useless.
   - Theorem A.11, which seems to be a restatement of Theorem 5.1, differs significantly from Theorem 5.1. It is unclear which version is correct and should be included in the main text.
2. The connection between Theorem 5.1 and the proposed method requires further elaboration. It appears that the authors aim to use Equation (4) to optimize the upper bound of the LHS of condition (i) in Theorem 5.1. However, it seems feasible to optimize the LHS directly, raising questions about the necessity of introducing the subspace representation alignment term in Equation (4).
3. The two necessary conditions proposed in the paper seem to align with the objectives of Invariant Risk Minimization (IRM). A more detailed comparison with IRM would strengthen the paper and clarify the contributions.
4. There are issues with notation and definitions:
   - The use of $h \in \arg\min \sup$ in Equation (4) is unusual. In the definition of $\mathcal{F}^*$, a predictor $f \in \mathcal{F}^*$ if and only if for all $e$, $f \in \arg\min L(f, P^e)$. However, Equation (4) presents a minimax problem, which differs from the definition of $\mathcal{F}^*$. Should it be $\forall e, h \in \arg\min L(h \circ g, P^e)$ in Equation (3)?
5. There are unclear parts and typos:
   - The sentence is incomplete in Line 51 and needs revision
   - The notation $\Phi$ in Definition 3.7 is introduced without explanation, causing confusion.
   - $G_c$ should be $\mathcal{G}_c$ in Line 240.

questions:
See the weakness part.
</content>
</thread_object>

</thread>


Metareview:
metareview:
Summary: This paper studies the sufficient and necessary conditions for the domain generalization problem. The paper shows that sufficient conditions are oftentimes unverifiable in practice. Therefore, the authors turn to necessary conditions to analyze existing DG approaches. They also propose an algorithm, Subspace Representation Alignment, to learn sufficient invariant representations.

Strengths:
1. Necessary and sufficient conditions of domain generalization problems are important research topic. The paper provides a fresh perspective on this topic.

Weaknesses:
1. As raised by Reviewer uuZ4, there are errors in Theorem 5.1 (the lack of $|\epsilon_r|$ term), and the authors admit it in the rebuttal. Errors are not acceptable in the top conferences such as ICLR.
2. Presentation errors exist in Proposition 3.5, Theorem A.5, the results tables presented in the Appendix, and other unclear sections highlighted by the reviewers.
3. One reviewers have concerns on the readability of the proof. The proof may have errors and be non-rigorous.
4. The paper shows weak evidence that the proposed algorithm outperforms the baselines.

All reviewers vote for rejection consistently. AC would follow reviewers' suggestions and recommend for rejection as well. AC would encourage the authors to take the above weaknesses into consideration in the future revision of this paper.