How Many Domains Suffice for Domain Generalization? A Tight Characterization via the Domain Shattering Dimension

Thank you for your careful review and thoughtful feedback! We will make sure to revise our paper based on your comments. Below are our responses to your specific points.

Regarding experiments and practical benefits. We believe there is a non-trivial audience at NeurIPS interested in foundational advances in theoretical machine learning. While our work is purely theoretical, we’d like to emphasize two key takeaways:

1. Conceptual insight: We introduce a new framework for analyzing domain generalization, which avoids the need to explicitly model domain similarity—something that is often difficult in practice.

2. Algorithmic contribution: We also provide a practical algorithmic principle—min-max ERM—which can be implemented efficiently using standard optimization techniques such as gradient descent or multiplicative weights for concrete hypothesis classes such as neural networks or linear models. Our analysis suggests that min-max ERM is provably more robust than standard ERM in multi-domain settings.

We hope these insights can inform the design and analysis of future algorithms, and potentially guide empirical work moving forward. We will highlight this in our revision.

Regarding the assumption that H contains a suitable hypothesis. Unlike the realizability assumption in classical PAC learning, we do not assume the existence of a perfect hypothesis in $\mathcal{H}$. We only assume that there exists a reasonably good hypothesis $h^\*$ that performs well (i.e. has reasonably small error) across domains—analogous to how one might expect a CNN to generalize reasonably well across diverse image domains (e.g., natural images, medical images, etc.). We evaluate the performance of the learned model $\hat h$ by comparing it with this reasonably good hypothesis $h^\*$ (similarly to the agnostic setting of PAC learning).

Of course, if $\mathcal{H}$ does not contain such a hypothesis $h^\*$—just as a CNN might fail on certain image types—then the issue is not with the theory, but with the choice of hypothesis class. In such cases, one would need to explore a richer or more appropriate class (e.g., a new architecture). How to select or learn an appropriate hypothesis class for domain generalization is an important and open direction for future work.

Regarding dimension of deep neural networks. We’d like to clarify that our proposed dimension can, in fact, be small even for deep neural networks when the domains are similar. Consider $\mathcal{H}$ as the class of all networks defined by varying parameters within a fixed architecture. In the extreme case where all domains are identical, the domain shattering dimension $\text{Gdim}(\mathcal{H}, \mathcal{G}, \tau, \alpha)$ becomes 0, regardless of the VC dimension of the network.

We agree that in the classical PAC setting, VC dimension leads to vacuous bounds for deep nets because it accounts for the worst-case over all distributions. However, in our framework, the domain space is taken as an input, allowing the dimension to reflect structure in the distribution over domains. As a result, the domain sample complexity can remain meaningful even for expressive hypothesis classes like neural networks. That said, estimating this dimension in practice—especially for deep models—is still an open and challenging question, which we view as an interesting direction for future work.

Regarding local minima versus global minima. Our analysis does not require solving ERM exactly. For any threshold $\tau$, if the algorithm returns a hypothesis that achieves error at most $\tau$ on each observed domain, then our generalization bound still applies. In practice, this means that approximate solutions—such as those obtained via standard deep learning optimization methods—can still yield meaningful guarantees, as long as the per-domain training errors remain controlled. Running exact ERM would simply allow for a smaller achievable $\tau$, but it is not necessary for our theoretical results to hold. We will include this discussion in our revision.

Thank you for your careful reading and thoughtful review! We will make sure to revise our paper based on your comments and correct the typos you pointed out. Below are our responses to your specific points.

Regarding Lines 71-74. We will revise our paper to include the definition of the classical fat-shattering dimension and refine these lines to make them clearer. The main message is that the classical fat-shattering dimension is not an appropriate complexity measure in our setting because it is maximized over all choices of thresholds $\tau\in [0,1]$. For instance, let us fix $\tau = 0.3$. Consider a hypothesis class $\mathcal{H}$ where every $h \in \mathcal{H}$ satisfies $\text{err}_D(h) \leq 0.3$ for all domains $D$. Moreover, for any subset of domains $E$, there exists an $h \in \mathcal{H}$ such that $\text{err}_D(h) \leq 0.2$ if and only if $D \in E$. In this case, domain generalization with respect to $\tau = 0.3$ is trivial, yet the fat-shattering dimension is large (because it is large at another threshold $\tau’ = 0.2$). We hope this clarifies Lines 71-74. Please let us know if you have further questions.

Our domain shattering dimension can be viewed as a variant of the fat-shattering dimension with a fixed threshold $\tau$. This modification makes the characterization tight, which we prove using many new ideas beyond the classic theories about the fat-shattering dimension (e.g. Lemma 4.2).

Regarding experiments. While our work is purely theoretical, we’d like to emphasize two key takeaways:

1. Conceptual insight: Our results show that it is possible to analyze domain generalization without explicitly modeling domain similarity. This is insightful because domain similarity is often difficult to model in practice. The proposed domain shattering dimension captures inter-domain structure implicitly, offering a flexible and general framework.

2. Algorithmic contribution: We also provide a practical algorithmic principle—min-max ERM—which can be implemented efficiently using standard optimization techniques such as gradient descent or multiplicative weights for concrete hypothesis classes.

We believe these contributions are valuable in their own right and will highlight them in the revised paper. While experimental validation is important, toy experiments are unlikely to offer insights beyond what our theory already captures. Designing meaningful empirical studies that reflect real-world scenarios while providing additional insight beyond our theoretical results remains an open and important question.

Regarding the section on connection to domain adaptation. Thank you for the comment! We will refine the presentation of this section to make it clearer.

Our Theorem 6.1 shows that the covering size $|\mathcal G'|$ under the $(\mathcal{H},\tau)$-divergence gives an upper bound on the domain shattering dimension. Combining this with our main upper bound (Theorem 4.1), we get an upper bound on the target error in terms of the covering size $|\mathcal G'|$ under the $(\mathcal{H},\tau)$-divergence.

While Theorem 6.1 is stated (and proved in Appendix B.5) for the $(\mathcal{H},\tau)$-divergence, it applies to the $\mathcal{H}$-divergence as well because the latter only makes the covering size become larger (or remain the same). This follows from the basic fact that the $(\mathcal{H},\tau)$-divergence never exceeds the $\mathcal{H}$-divergence. We will make this clearer in the revision.

We don't know if the $\mathcal H \Delta \mathcal H$-divergence has a relaxed form (as you suggest) that would meaningfully bound the target error. However, our result extends to the original $\mathcal H\Delta \mathcal H$-divergence as defined in Ben-David et. al [2010]. Lemma 4 of Ben-David et. al [2010] proves an upper bound on the $\mathcal H$-divergence (defined in our paper at Line 318 as the maximum error difference over $h\in \mathcal H$) using the $\mathcal H\Delta \mathcal H$-divergence. Combining that with our Theorem 6.1 gives an upper bound on the domain shattering dimension using the $\mathcal H\Delta \mathcal H$-divergence, and by Thm 4.1 we get an upper bound on the target error using the $\mathcal H\Delta \mathcal H$-divergence. Thank you for bringing the $\mathcal H\Delta \mathcal H$-divergence to our attention. We will include this result in our revision.

Typographical Errors. Thank you for finding these! We will correct them in the revision.

Thank you for appreciating our work and providing insightful comments. Below are our answers to your specific questions:

Is the VC dimension of the partial concept class equivalent to the domain shattering dimension? Yes. This is mentioned at Line 213 of the paper. We can make it more visible by upgrading it to a Lemma or a Claim in the revision. We appreciate your suggestions.

Regarding the lower bound construction and the idea of an altered notion of the domain shattering dimension. Your idea makes perfect sense to us, and we appreciate your thoughtful comment. The gap between our upper and lower bounds arises because the min-max ERM algorithm we use for the upper bound does not require any knowledge of the domain space $\mathcal{G}$ beyond the observed domains—whereas, in principle, there exist domain families $\mathcal{G}$ that are trivially easy to learn if such knowledge were available. Proving a tight upper bound for every choice of $(\mathcal H, \mathcal G)$ without the $\mathcal G'$ augmentation requires a more advanced algorithm that leverages the inherent structure of $\mathcal G$. This is an intriguing follow-up question of our work and we will mention it explicitly in the revision.

However, in many practical settings we have little knowledge about the inherent structure of $\mathcal{G}$, and this is a scenario where the min-max ERM algorithm is well suited for. (This lack of knowledge is certainly the case for the real-life medical research problem that originally piqued our interest in the problem, where at training time we have little knowledge about the space of patient distributions of unseen hospitals in the future.) An alternative way to interpret our lower bound is as a universal hardness result: there always exists a slightly extended domain space $\mathcal{G}'$ for which the lower bound applies and the min-max ERM algorithm is (near) optimal. Our current lower bound construction explicitly provides such a $\mathcal{G}'$.

In the learnability definition, is there a size requirement on m? In the learnability definition, we only require m to be finite. In the algorithm and upper bound, we just adopt $m = O(\frac{\text{VCdim}}{\epsilon^2})$ from classical VC theory (see Lines 186-188).

Thank you for appreciating our work! Also thank you for pointing us to those papers—it's definitely interesting to explore how our framework might connect to data-generating processes modeled through causal assumptions.

Thank you for your careful review and thoughtful feedback! We will make sure to revise the paper based on your comments. Below are our responses to your specific points.

Regarding practical and theoretical implications / insights. Before we make a clarification about your comment on the problem formulation, we’d like to highlight that our proposed min-max ERM is a practical algorithmic principle that can be implemented using standard optimization techniques—for example, gradient descent, multiplicative weights, or other iterative methods—for concrete hypothesis classes like neural networks or linear models. Please keep in mind that our goal is to characterize how many observed source domains are sufficient for learning a good model (hypothesis) that generalizes well to the unseen target domains.

Regarding the problem formulation you suggest. The formulation you suggest is, in fact, what we study in our paper. While we formulate the question as “how many observed domains are sufficient” to generalize to $(1-\epsilon)$ fraction of the unseen target domains, this question can be equivalently formulated as “how many unseen domains” one can generalize to given data from a fixed, small number $n$ of observed domains. For example, a result saying that “$n = 1/\epsilon$ observed domains are sufficient to achieve generalization on $(1-\epsilon)$ fraction of the unseen domains” is equivalent to the result that “one can generalize to $(1 - 1/n)$ fraction of the unseen domains given data from $n$ observed domains”. While the two formulations are equivalent, the latter formulation is indeed more natural and relevant in practical scenarios, where the number of observed domains is limited and not controlled by the learner (as you pointed out). In fact, our main theorems (Theorems 4.1 and 4.3) are stated using this more relevant formulation, where we express $\epsilon$ (the fraction of unseen domains that we don’t generalize to, denoted by $\text{Er}_{\mathcal P,\tau}(\hat h)$ in the paper) as a function of the number $n$ of observed domains. We hope this clarifies the implications of our results to DG practice and will include this clarification in the revised paper.

Regarding the treatment of domains as individual samples. We believe that treating domains as individual samples is a key conceptual contribution of our work. Prior theoretical work typically assumes strong structural relationships across domains, such as similarity under a predefined divergence measure. However, in real-world applications, it is often unclear how to define or justify such similarity measures. This motivated us to ask whether domain generalization is possible without making explicit structural assumptions. Our framework addresses this by borrowing tools from statistical learning theory and analyzing generalization across domains in a similar way PAC theory analyzes generalization across examples. A major advantage of our approach is that it allows us to characterize domain generalization using our domain shattering dimension, which does not require any predefined similarity measure. As we show in Section 6, when the domains are similar under classical measures (e.g., the H-divergence of Ben-David et al.), our domain shattering dimension becomes small—implying that it naturally captures domain similarity without requiring it to be modeled explicitly.

While our proof technique involves a reduction to binary labels, it is not trivial to use such a reduction to prove a tight characterization with matching upper and lower bounds. We prove our tight characterization using many novel components in addition to the reduction. For example, if one defines a binary loss at the domain level (e.g., via a fixed threshold $\tau$), the setting may resemble standard PAC learning, but this does not lead to a tight upper bound. To ensure tightness, we need two thresholds $\tau - \alpha$ and $\tau$ and map values between them to a special label $\bot$ beyond the binary labels 0 and 1. To analyze the partial hypotheses obtained from this reduction, we leverage deep results (Theorem B.1) from Alon et al. [2022] to prove a novel uniform convergence bound (Lemma 4.2) beyond the scope of Alon et al. [2022] (see Footnote 1 on Page 6).

Regarding domain similarity. We appreciate the reviewer’s concern. To clarify: the sentence "domain sample complexity can still be very small if the domains in $\mathcal{G}$ are very similar" aims to discuss the property of domain sample complexity instead of describing an observation. It refers to a hypothetical extreme scenario where all domains in $\mathcal{G}$ are highly similar (or even identical). In such cases, the domain sample complexity can indeed be small—we mention this in the introduction to emphasize that domain sample complexity depends not only on the hypothesis class $\mathcal{H}$, but also on the domain family $\mathcal G$. We did not intend to suggest that such similarity can be inferred from a small number of training domains. We will make this clearer in the revision.

Regarding the section on domain adaptation and divergence measure. The goal of this section is to connect our framework to prior work, specifically to show that we can recover insights from Ben-David et al. [2010] within our setting and thereby demonstrate the expressiveness of our approach.

Ben-David et al. define the $\mathcal{H}$-divergence to measure similarity between domains, and show that generalization is possible when the source and target domains are close under this measure. This leads to a clustering interpretation: if the domain space admits a small cover under $\mathcal{H}$-divergence, then observing one domain per cluster suffices.

We show that our domain shattering dimension implicitly captures this structure. Specifically, a small domain shattering dimension is guaranteed by a small covering number under our new divergence, which is in turn guaranteed by a small cover under the $\mathcal{H}$-divergence. The takeaway is that our framework captures domain similarity without requiring it to be explicitly modeled, yet can still recover and generalize known results from domain adaptation—highlighting its power and flexibility. We will emphasize this point as the motivation of the section in the revised paper.

The new divergence measure is introduced solely as an intermediate step to bridge our shattering-based analysis with the divergence-based analysis. We will make this clearer in the revision.