How Many Domains Suffice for Domain Generalization? A Tight Characterization via the Domain Shattering Dimension
Authors: Cynthia Dwork
Lunjia Hu
Han Shao
Venue: NeurIPS 2025 poster ()
Keywords: Domain generalization
PAC learning
sample complexity
shattering dimension
partial concepts
Primary area: theory

Abstract: We study a fundamental question of domain generalization: given a family of domains (i.e., data distributions), how many randomly sampled domains do we need to collect data from in order to learn a model that performs reasonably well on every seen and unseen domain in the family? We model this problem in the PAC framework and introduce a new combinatorial measure, which we call the domain shattering dimension. We show that this dimension characterizes the domain sample complexity. Furthermore, we establish a tight quantitative relationship between the domain shattering dimension and the classic VC dimension, demonstrating that every hypothesis class that is learnable in the standard PAC setting is also learnable in our setting.

How Many Domains Suffice for Domain Generalization? A Tight Characterization via the Domain Shattering Dimension
Cynthia Dwork
Lunjia Hu
Harvard University
Northeastern University
dwork@seas haw.ard. edu
Junjia@alumni wtwp:/uunnnnnnnnnfooooooooeooa stanford edu
Han Shao
University of Maryland, College Park hanshao@umd, edu
Abstract
We study fundamental question of domain generalization: given family of domains (i.e., data distributions), how many randomly sampled domains do we need to collect data from in order to learn model that performs reasonably well on every seen and unseen domain in the family? We model this problem the PAC framework and introduce shattering dimension. We show that this dimension characterizes the domain sam- establish tight quantitative relationship between
combinatorial measure, which call the domain
ple complexity. Furthermore, the domain shattering dimension and the classic VC dimension, demonstrating that every hypothesis class that is learnable in the standard PAC setting also learnable in our setting.
Introduction
The ability to generalize across domains is an important component of human intelligence and crucial milestone in the development of increasingly powerful artificial intelligence. It is not surprising that an experienced driver in one country can reasonably, albeit imperfectly, drive in another country even without further training. It is also not surprising that skilled chess player can outperform an average person on a totally different board game. An expert doctor who has studied a disease using data from few large hospitals can potentially provide reasonable treatment for patients in geographically remote and biologically different population that does not have access to those large hospitals and has not been the subject of prior study. Such domain generalization abilities empowered by the capability of the learner (i.e., the driver, chess player, or doctor) to distill and master universal laws (about driving, game playing, or medical treatment) that hold on unseen domains, while separating them from idiosyncratic patterns that are domain -amain-specific.
In this work, we study the theoretical foundations of domain generalization with focus capturing this ability of learning "universal laws" while not overfitting to the "idiosyncratic patterns". Consider family G of domains, where every domain D is distribution examples (xr, y) each consisting of an instance I E X and a binary label y E {0, 1). On a specific domain D, there may be a hypothesis
Work done while at Harvard. Supported by the Simons Foundation Collaboration on the Theory of Algorithmic Fairness and the Harvard Center for Research on Computation and Society (CRCS).
1 Work done while at Harvard. Supported by the Harvard Center of Mathematical Sciences and Applications (CMSA).
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

(i.e., classifier) h: X - {0, 1} with low classification error errp (h), say, below 0.01:
( := Pr(c,))~Dly # h(x)) - 0.01.
However, the strong performance of this hypothesis may rely on patterms specific to the current domain and may fail transfer to other domains D' G. For the purpose of domain generalization, we would instead prefer a different hypothesis h* that achieves reasonably thothh not necessarily minimal- across all domains D G. Specifically, for mild but meaningful error threshold, say 0.3, we assume
max maxcrr - 0.3.
DEC
Motivated by this, we model the underlying "universal laws" by assuming the existence of such universally good hypothesis A" E H that satisfies Equation ( We make no further assumptions on the structure of the domains in or on the relationships among them.
In our domain generalization task, a learner has data access to a limited number of domains Di...., Dr sampled ii.d. from meta-distribution P over domain space G. Using this limited data access, the learner's goal is to output a model h X + (0, 1) that achieves reasonably good performance on new, unseen domains drawn from P without any additional training. Concretely, for performance threshold and error parameter T, E [0, 1]. the learner's 's goal is to output h : X - {0, 1} such that
Pro- (rD-p(eerD(() (h) S <> 2 1-7.
In this work, we aim to answer the following quantitative question:
How many domains does the learner need to see to achieve domain generalization?
The answer to this question, which call the domain sample complexity, is analogous the notion of sample complexity in classic learning theory. Sample complexity is defined as the number of data points needed to learn good model on single domain, whereas notion of domain sample complexity measures the number of domains the learner needs to collect data from in order to generalize to unseen domains. Thus, domain sample complexity can be viewed as a higher-level meta-variant of the notion of sample complexity.
Characterizing the sample complexity of various learning tasks is a central question in learning theory. For example, the celebrated VC theory characterizes the sample complexity of classic PAC learning [Valiant 1984] using the VC dimension /Vapnik and Chervonenkis 1971.. combinatorial complexity measure of the hypothesis class H. The goal of our work is to characterize the domain sample complexity, which depends not only the complexity of the hypothesis class H. but also on the interaction between H. and the domain family G. For example, even if H is itself very complex, the domain sample complexity can still be very small if the domains in G are very similar. Even when both H. and G are complex, the domain sample complexity can still be small if their complexities are concentrated disjoint subsets of the input space X. For instance, suppose all hypotheses h H are identical on a subset X, C X, and G only contains domains D satisfying Pro(æ E X1] = 1. In this case H can be complex outside of X1 and G can be complex inside X1, but the domain sample complexity is always zero: on every fixed domain D E G, all hypotheses h E H achieve the same error. Finding a combinatorial quantity that tightly characterizes the domain sample complexity requires accurately capturing this interaction between H. and g
1.1 Our Contributions
We model the domain generalization problem in the PAC framework and introduce a new combinato- rial measure, the domain shattering dimension (Definition 4.1). for hypothesis class H with respect to family G of domains.
For each hypothesis h, we define the function err. (h) G + E that maps each domain to the error of h on that domain, thereby inducing a new function class. natural idea is to analyze the fat-shattering dimension [Kearns and Schapire 1994] of this class. This turns out to overestimate the domain sample complexity. For target error threshold (e.g. T 0.3). the domain sample complexity can
A similar situation that requires capturing the interaction between pair of hypothesis classes occurs in the study of comparative learning (hybrid of realizable and agnostic learning) (Hu and Peale 2023 Hu et al. 2022
2

---

be very small (e.g. when (I) S 7 is achieved by every h E H.. on every domain D E G), but the size of shattered set can be large at a different threshold 7', causing the fat-shattring dimension to be large as well.
To address this, we propose new dimension by modifying the fat-shattering dimension: instead of allowing different thresholds across shattered domains, we require a uniform and fixed threshold across all of them. We show that the resulting domain shattering dimension gives both upper (Theorem 4.I and lower (Theorem 4.3 bounds on the domain sample complexity, and these bounds match up to a poly-logarithmic factor. We obtain the upper bound by a min-max variant of the empirical risk minimization (ERM) algorithm. To analyze the domain sample complexity achieved by the min-max ERM algorithm, we establish a uniform convergence bound (Lemma (42)) for partial concept classes based on generalized Sauer-Shelate Sae--h-heeerrreee Perles lemma by Alon et al. [2022]. which may be of independent interest. Our algorithm and upper bound can be directly applied to other learning tasks beyond binary classification, such as multi-class classification and regression (Remark 4.2)
The next question we address in this paper is the relationship between domain generalization learnability and standard PAC learnability. It is well known that PAC learnability is characterized by the VC dimension. We compare our domain shattering dimension with the VC dimension and show that, for hypothesis class H with VC dimension d and a margin a, the domain shattering (Theorem 5.2). Moreover, we construct a
dimension is always upper bounded by O(dlog(1/a) hypothesis class with VC dimension d and a domain family G for which the domain shattering dimension is (2 1/a)) (Theorem 5.1). This establishes a tight relationship between the two measures and demonstrates that standard PAC learnability implies domain generalization learnability, but the domain sample complexity can be much smaller than the sample complexity for PAC learning.
Finally, we relate our work to the literature on domain adaptation. In domain adaptation, the goal is to generalize from a source distribution are sufficiently similar. This similarity is often quantified using measures such as the H-divergence introduced in Benn-Daiid al. [2010]. We show that if all domains in 9 are similar to each other under a metric based on a modified version of the H--divergence, then the domain shattering dimension is 1. Moreover, when the hypothesis class admits finite cover under this metric, the domain shattering dimension can be upper bounded by the covering number (Theorem 6.11. These results illustrate the potential of our domain shattering dimension as a general notion for characterizing domain generalization without explicitly modeling how domains are related.
related target distribution, under the assumption that the two
1.2
Related Work
There is a vast literature on domain generalization and related learning paradigms such as meta- learning, zero-shot learning, domain adaptation, out of distribution generalization, transfer learning. invariant risk minimization, and multi-task learning. The excellent survey of domain generalization of
Wang et al. 2022) provides a helpful taxonomy of many of these paradigms and explores thcoretical underpinnings of domain adaptation and domain generalization. Zhou et al. [2022) organizes a plethora of works by (1) application area; (2) method; and (3) learning paradigm, and provides pointers to many datasets commonly used for domain generalization.
Our work is distinguished from prior theoretical work in that simultaneously (1) we make only the minimalist assumption of the existence of a universally good hypothesis 4t" E H. (e.g., one satisfying Equation (T)), with no further requirements regarding how different domains in G are related, making our model very general; and (2) we obtain provable results for the strong learning objective of requiring the output model h to achieve a reasonably low error simultancously on essentially all domains (including the unobserved ones), rather than achieving low error in expectation over choice of domain. Achieving low error simultaneously on all domains can be substantially different from achieving low average eтror when T is not very close to zero. For example, an average error of 0.25 could arise if the hypothesis incurs zero eтror on 3/4 of the domains but makes completely incorrect predictions (error 1) on the remaining 1/4 of the domains. Finally, we explicitly focus on the question of domain sample complexity - the total number of domains that need to be sampled in order to generalize well to a random new domain. This is different from the common notions of sample complexity and query complexity, and this lens yielded the key concept of the domain shattering dimension.
3

---

2 Preliminaries
We include the definition of partial concepts that will be very useful in our analysis. A partial concept
is a function f Z - {0, ] that assigns each individual in an input space Z a binary label (0 or 1), or the "unknown" label, denoted by I. A total concept f: Z + {0, 1] assigns a binary label (0 or 1) to each individual 2 E Z without using the "unknown" label 1. Throughout the paper, for positive integer n, we use [n] to denote the set [l....,n).
Definition 2.1 (VC dimension of partial concept classes Vapnik and Chervonenkis, 1971 Alon et al.
2022]). Let FF be a class of partial concepts f Z 10.1,17 1) on an arbitrary input space Z. We say subset S S Z is shattered by F for every subser E C S, there exists fE E F such that
fE(() = 0 for every E E,
fE( = for every s E S E.
The VC dimension of F (denoted VCdim(F)) is the size of the largest shattered set S C Z.
Clearly, the classical VC dimension, defined for total concept classes, is special case of the VC dimension for partial concept classes.
3 Problem Setup for Domain Generalization
Given input space X and label space Y = {0, 1}, domain (or data distribution) D is a distribution over X x Y. We consider a family G of domains D. For any hypothesis/predictor h : X Y. we define the error rate of & under domain D as
crr == P ((a))D (y # h(x))
We consider an underlying meta distribution P over the domains D G. Given threshold for any hypothesis h and a threshold r, we define the domain error of with respect to T as
Erp,, (h) == PD~P (h)r > T)
which quantifies the probability mass of the domains where / incurs error greater than T. It follows immediately that Erp, (h) is monotonically decreasing in
As in the standard PAC learning setting, we are given a hypothesis class H. and aim to output a hypothesis that performs well compared to the best hypothesis in H.
Definition 3.1 (Optimal domain error bound and optimal hypothesis). Given a hypothesis class H. domain class G. and distribution P over G, the optimal domain error bound is defined as
T m E H. (h),
and the optimal hypothesis h* is defined one hypothesis achieving Erp,, (h) = 0.
This definition ensures that there exists a hypothesis h* in H that achieves an error rate below threshold Tp.. every domain sampled from P, and T represents the smallest such achievable threshold. Thus, Tİ.N serves as benchmark for our learning problem and any threshold 2 TP.H is achievable. We assume that TP, is reasonably small-if T perform well across the domains-though we do not assume is zero.
0.5, then no hypothesis in H can
Then given a hypothesis class H. and a threshold т, a learner AA access to a set of i.i.d. sampled domains G (D1, D2, ... .. Dn). and i.i.d. data S, collected from each domain D;, with the goal of outputting a hypothesis / A((S), ..... S, ) that achieves error rate of at most 7 under almost every domain. This can be formalized into the following learnability problem for domain generalization, where we focus on the domain sample complexity: the number of observed domains needed to achieve domain generalization.
Definition 3.2 ((T, a. 77,))-dmain learnability). For any T,a,7, 5 E (0, we say (HL is (T, ar 7/ 8) learnable if there exists finite integers n and m for which there exists an algorithm A such that for any distribution P over G with optimal error bound Tp.x ST- with probability at least - 8 over G ~ p and S; "D for all D, E G.
(A S.))) 57
The domain sample complexity is the smallest integer satisfying the above constraint.

---

Characterizing Domain Sample Complexity Using Domain Shattering Dimension
To characterize the domain sample complexity. we introduce the following combinatorial measure inspired by the fat-shattering dimension (Kearns and Schapire [994].
Definition 4.1 (Domain shattering dimension). Let G be set of domains. We say subset S S G is a-shattered by at r for all C S, there exists hypothesis hy H satisfying
eIIp(hg) <T- crrp(hg) >T
for every D E E, for every E S
The domain shattering dimension of H. denoted by Gdim(H, 9, O.,, is defined to be the maximum size of set S that can be a-shattered by H.
Monotonicity of domain shattering dimension. It follows directly from the definition that for any T, T', of if 7' 2 and 7' a' S O, have GH,m(H, "," S 9,
4.1 Upper Bound
show an upper bound on the domain sample complexity using the domain shattering dimension in Theorem 4. below. We prove this upper bound using the following natural min-max variant of the empirical risk minimization (ERM) algorithm. In the next subsection (Section 4.2). we will prove a lower bound that matches upper bound up to polylogarithmic factor.
Min-Max ERM Algorithm. Given set of i.i.d. sampled domains G (D D2...... Da). we assume access to approximate error rates for any hypothesis & E H. on each domain. Specifically, for some e > 0, for every domain G and hypothesis h E H. we can access an estimate ert (h) of the true error err such that
(h) errp (h)) < for all E G and H.
By standard uniform convergence guarantees, with success probability at least - 6, these estimates can be obtained the empirical error on O(VCdimm( (H) + log(n/))) (o/m/)))//²" i.i.d. data points from each domain's 's distribution. Given access to eIT (h), we return the min-max predictor
arg min max eri MEN DEG
The following theorem upper bounds Erp,, (h) in terms of the domain shattering dimension and the number of training domains. This implies domain sample complexity upper bound.
Theorem 4.1. Let H. be class of hypotheses h X + {0, 1} and let G be family of domains D each being a distribution over X {0, 1). Define every e, 8 E (0, 1/2), for every domain distribution P over G satisfying TPH S T- a - 2s, with probability at least 1 5 over a sample G of i..dd. domains drawn frow P. when given access to (h) for all D E G and h E H satisfying
Gdim G, ai) for T, a [0, 1]. For
2 the min-max predictor h in 3 satisfies
Erp. (T) S (d dog" n 1og(1/0)
Theorem 4.1 guarantees good accuracy of h on new, unseen domains drawn from P. To prove this result, we start by analyzing the performance of h on the training domains in G. By the assumption of Theorem 4.1 there exists ht E H such that (ht" TT- - 2s for every D E G. Now by and 3 we have
errp(h) (h) (h) + eiip(h") + err 2s <
for every G.
(4)
This ensures that N achieves low error on every training domain D E To prove Theorem 4.1 we need to show that achieves low error on new domains drawn from P. Specifically, for some
= o dllog n log(1/8)
5

---

our goal is to show that with probability at least - 8, the i returned by min-max ERM satisfies
Pr [err h S
(5)
D-P
To prove the guarantee (5) for D ~ P from the guarantee convergence bound over all H.
(4) for D E G, we establish a uniform
One natural idea for establishing a desired uniform convergence bound is by applying existing results about the fat-shattering dimension Kearns and Schapire [1994], which is similar to our domain shattering dimension. However, this idea falls short for our purpose because 1) the fat-shatt dimension defined as maximum over all thresholds and 2) prior results from the fat- tat-shattering dimension incur a constant- factor blow-up in the margin a. We instead use results about partial concept classes from Alon et al. 2002 Specifically, for each h E H. we construct a partial concept fu : 9 - 1, by letting
1
if err (h) > T, if errp <T
(D)
O.W.
This allows to construct new partial concept class F = ffulh E H}. Our assumption in Theorem 4.1 that the domain shattering dimension H is d ensures that the VC dimension of F (see Definitions 2.1 and 4.1 Now (4) can be equivalently written as
(D) =
for every D E G,
and similarly, our goal ( is equivalent to
Pr (x 1 1
Thus, to prove Theorem 4.1 it suffices to establish the following uniform convergence bound: 7 and vD GD s
Pr G~pn
Dr Pro-p(S(D)
We formally state this uniform convergence bound the following general lemma
Lemma 4.2 (Uniform convergence for partial concepts). Let F be class of partial concepts f + {0, 1, on an arbitrary input space Z. Assune that F has VC dimension For every Z>n and 5 E 1/2), there exists
d dloog log(1/0)
T
(6)
n
such that for every distribution P over Z. n i..dd. data points 21,..., from P. Pr E Pre-p (f(2) 1] and Vi E [n], f(z)) 0] S
We establish this uniform convergence bound using standard symmetrization trick combined with a generalized Senue-Shelah-Peee [022]. We defer the full proof of Lemma 4.2 to Appendix B.1
lemma for partial concept classes (Theorem B.I] by Alon al.)
Remark 4.1 (Choice the threshold r). It is important to note that while our upper bound depends on the choice of t and the algorithm itself does not. Let fix the relationship T As we increase т and a at the same rate-i.e.. relax the target error threshold T-the value of Gdim G. G,T,CO a. decreases monotonically. This means that larger proportion of domains can meet the relaxed threshold т. Therefore, the choice of T captures a trade-off between the strictness of the generalization goal and the fraction of domains that able to satisfy it.
2z.
Remark 4.2 (Beyond binary classification). We emphasize that neither the algorithm nor the analysis relies on binary labels, and both can be directly applied to other learning tasks such as multi-class classification and regression.
2022 is that uniform convergence and the ERM algorithm both fail for learning partial concepts. This, however. not contradict our Lemma 4.2 Roughly speaking. the uniform convergence needed in the setting of Alon et al. (2022) requires replacing
*We remark that key message from the work of Alon
(f))) in 7 with (fz= = 1 or LJ. This stronger form of uniform convergence does not hold.

---

Remark 4.3 (Standard ERM fails). Note that standard ERM, which selects hypothesis minimizing the empirical error over the entire pool of training data, may fail in our setting. Consider toy example with two hypotheses: one incurs an error of 0.3 on every domain, while the other achieves O error on half of the domains and 0.5 on the other kalf. Standard ERM would choose the latter, despite its poor worst-case performance across domains.
4.2 Lower Bound
We prove a lower bound (Theorem 4.3 showing that the error upper bound in Theorem 4. is
essentially cetrmatioonthhoreticee that the error bound is instance-wise optimal: for every fixed choice of H. 9 and parameters т, a, E, 8, the error bound in Theorem 4.1 cannot be improved even if one uses learning algorithm specifically designed for those fixed choices. However, this perfect instance-wis wiie optimality does not hold for the following trivial reason. For every domain D E G, let Dx denote the marginal distribution of t E X where (I, y) ~ D. Consider a fixed choice of G and suppose that the marginal distributions Dx for D are supported on disjoint subsets of X. In this case, the learner can simply always output the hypothesis h- that simultaneously minimizes the error on every domain D E G. This solves domain generalization task without observing any training domains drawn from P. The domain sample complexity is zero, but the domain shattering dimension can be very large, implying that our upper bound Theorem 4.1 is far from optimal in this setting.
optimal up an (log" n) factor. It would be ideal to show
We thus make a slight compromise in the level of instance-wist optimality. We still consider arbitrary fixed choices of H and G. However, in our learning task, the domains do not solely come from g. but instead come from a mildly extended family g' Importantly, for some domains D in the extended family G', their marginal distributions Dx will be supported on overlapping subsets of X. In this case, we are able to prove a domain sample complexity lower bound (Theorem 4.3) that nearly matches our upper bound (Theorem 4.1).
Concretly, we assume that there exists a distribution Do of data points (z, E X x 10.1] such that erTD, (h) = 0 for every h E H
7 Let d be the domain shattering dimension of H on G. and let Di...., Da E G be d domains shattered by H. For every = I,...,dd, d, we define a new domain Dj as follows:
D' (1 A)Do + X(-D,).
(8)
Here, A E (0, 1] is a fixed parameter, and -D; is obtained by flipping the labels in D. That is, -D; is the distribution of (Ir, -y) for (xr,)) ~ DD. Equation (8) defines Dj as a mixture of Do and -D;
We define G" to be G U (Do D/, , D'J.. We view G' as a mild extension of G. In particular, as we show in Theorem 4.3 below, H has the same domain shattering dimension on G' on & for an appropriate choice of Å. Moreover, in Theorem 4.3 we show a domain sample complexity lower bound on G' that nearly matches our upper bound in Theorem [41
Theorem 4.3 (Lower bound). Consider an arbitrary class Ht of hypotheses h: X + {0, 1 and an arbitrary family G of domains D (i.e. distributions over X x {0, 13). Assume that Gdim G.T.a) d for some (I. v) E X x f0. 1} satisfying eITD, (h) = 0 for every shattered by H. and define G' = G U (Do, D Di...., D')) as in (8) for
E R and d E Zz where 0 I a < T < 1/2. Let Do be a distribution of
H. Let DI....,Da Du E 9 be domains
x == T E (0,
Then Gdim(H, a. d. Moreover, for some n > 0,8 10.1/4), n E Zso, and an error threshold r' <T- I-a a E (5- a, suppose there is an algorithm A with the following property on every distribution P over satisfying Tİ. <T- oz it takes n domains drawn i..dd. from P as input, and with probability at least 1 8, outputs a hypothesis such that
Erp. (T) S
Then
7 Ω min { d + dogo (1/)
1,
(10)
'We view this as a mild assumption. Note that Da does not need to be a member of G. This assumption is satisfied as long as there is an input point zo E X receiving the same label (((2)) b E {0, 1) for all h E H. in which case choose Do the degenerate distribution supported the single point (za. b).
7

---

We remark that the lower bound in Theorem 4.3 is for a lower (i.e., more challenging) error threshold r' instead of the original enror threshold the definition of the domain shattering dimension. Nonetheless, the lower threshold r' is always allowed to be above the optimal error TDHH (i.e. T' a T.
We defer the proof of Theorem 4.3 Appendix
B.2
5 Relationship between Domain Shattering Dimension and VC Dimension
In this section, we study the relationship between the VC dimension and the domain shattering dimension of hypothesis class H. It is easy much smaller than the VC dimension when the domains in & are similar-in in the extreme case where contains only single domain, the domain shattering dimension cannot be more than one. We thus focus on the other direction: can the domain shattering dimension of a hypothesis class exceed its VC dimension? How much larger can it be?
that the domain shattering dimension can be
We give an accurate answer to this question in Theorems 5.1 and 5.2 below: for an error margin (see Definition 4.1.. the domain shattering dimension be as large as 12(d log(1/a)), which also the largest possible (up to a constant factor). Therefore, the domain shattering dimension approaches zero, but for any fixed > 0, the domain shattering dimension upper bounded linearly by the VC dimension. This implies that a PAC learnable hypothesis class is also learnable for our domain generalization task in Definition (3.2
can be arbitrarily larger than the VC dimension
Theorem 5.1. For every positive integer d, there exists a hypothesis class H. with VCdim(H) satisfying the following property. For any (0, 1/12), there exist k = 52 log(//a)) domains Di...., Dr such that
Gdim ... ( D,)
Theorem 5.2. Let H. be an arbitrary hypothesis class with VC dimension For any set of domains, any threshold T E R. and any margin 1/2),
Cdim(H, 9, T, ax) = Old O(dlog()/))).
(11)
We defer the proofs of these two theorems to Appendices B.3 and B.4 Our proof of Theorem 5.2 uses dimension reduction argument combined with the standard Suuer-Shelah-eebee lemma, which inspired by the proof of a classic covering number upper bound in terms of the VC dimension [see e.g. Vershynin 2018 Theorem 8.3.
6 Connection to Domain Adaptation
In the domain adaptation literature, common setting assumes that the training data are drawn from source distribution, while the test data come from a different but related target distribution. When the souree and target distributions are sufficiently similar, a model trained on the source data can generalize well to the target distribution. To quantify this similarity, various notions have been proposed, such as the H-divergence [Ben-David et al. 2010 and the propensity scoring function class (Kim et al. 2022).
Our work makes assumptions about the inter-domain structure, except that the optimal domain error bound T is reasonably small. We then upper bound the domain generalization error using the domain shattering dimension. In this section,
show that when the covering number of the domain space G w.r.t. the H-divergence is small, the domain shattering dimension is also small. In fact, we show a stronger result (Theorem 6. for refined variant of the H-divergence. This illustrates that our domain shattering dimension can capture the similarity between domains without requiring an explicit model of their relationships.
Inspired by the H-divergence introduced by Ben- et al. 2010 where
(D D') = sup |errp - errp (h)).
heh
we define refined notion of divergence, Given H, the (H, didveereeeeee between two domains D, D' is
du (D, D') =
sup
errp(h) err err
he Hamin (frp (t))) (k)))ST
8

---

Note that dx,-(D.D)) I dx(D.D") D') as we only take supremum over subset of hypotheses {h H. minferrp (h), err (h))} S J). Given domain space G. we say G' is an a-cover of w.n.t du.r if for every 'D E g. there exists D' E G' such that (D, D') S Any a-cover G' w.r.t. du is also an a-cover w.r.t. dz.r.
Theorem 6.1. For every hypothesis class H. domain space 9 and T, E (0, 1), let g' be an o -over of 9 w.E.t d We have Gdim(H, 9, a:) 19'
Proof of Theorem 6.1
For every D' E g', define G(D)) = E 9: (D, s 2). Since G is an 2 -cover, the union of (DD)) over D' G' g.
Fix an arbitrary D' E G and let D1, D2 be two domains in (DD). We show that D1, D2 cannot be a-shattered at r. In particular, show that for every h H. the two conditions errp, (h) and errp, (h) > T cannot hold simultancously. Indeed. if errp, (h) < T a, then we have
ert (h) I errD, + < r
a 2
a
2
and consequently,
eRTD, (h) S errD (h) + 2 <.
Therefore, (h) > cannot hold.
We have now shown that every subset of domains that is a-shattered at contains at most one domain from each ((D)) for D' E g". Thus the domain shattering dimension Gdim(H, 9, a:) does not exceed (
When all the domains similar, the cover size is 1, then sampling one domain is sufficient. Below are two examples of domain spaces with cover size 1.
Example 6.1 (Small H--ivergences). For any domain space 9, for every pair of distributions DD D' E G. dx (D, D') S a. Then the a-cover size of G is 1.
Example 6.2 (Smooth Distributions). Given marginal data distribution μ and a labeling function p", we define Du..= as the distribution over labeled data where features are drawn from and labels are assigned according to p²_ For a parameter Y (0,1), 1), labeling function p', and a base marginal distribution po, define the smooth domain space as
9p Ppr-po.77 = DDp
plx)) Mo(x) E 17, Hb Vo E supp(uo) }
For domain space 9p- poo.7 we can find (+z -1) r-cover of size 1.
For any two distributions D DuLr'' D Dug.p" 9p porrs it holds that supp(Hg). Consequently, for any hypothesis h, we have
Mi (ar) (2(w)
E
162 (p) for all
eIrD (h) S errp (h)
72 eIrD (h).
Therefore, by the definition of the r) T diverrgeee it follows that
1 {/2 -1)
dn (P. (Dur.' D )pZpr) -
Hence, for domain space ppr, we can find a (+ -1)
1+-11)-cover r-cover of size 1.
7 Discussion and Limitations
This work was inspired by the very real and widely acknowledged problem of transferring research from well-funded flagship medical research institutions to essentially communities, even those with direct access to these facilities, "from preeminent bench to geographically remote bedside"

---

(Deng et al. (2020)). Our succinct characterization and algorithm close some facets of this central question, while opening others.
How to compute the shattering dimension. As discussed in Remark 4.1 the choice of r reflects a trade-off between the strictness of the generalization goal and the fraction of domains that can satisfy it, as captured by Gdim (H. G,T,)) However, choosing an appropriate 7 depends on understanding the value of Gdim(H, G, a)), which-like the VC dimension-is generally difficult compute. Developing tools or approximation techniques to estimate Gdim is an important direction for future work.
Choice of hypothesis class H. We focus on the setting where a hypothesis class H. is given and assumed to contain a reasonably good hypothesis that generalizes across all domains. However, in practice, one may have access to a collection of candidate classes. How should we select the best class-one that contains reasonably good hypothesis but is not overly complex-for generalization? This question relates to structured ERM in the learning theory literature and presents an interesting open direction.
Gap between upper and lower bounds. Although we show that the domain shattering dimension provides both upper and lower bounds the domain sample complexity, small gap remains. Our upper bound guarantees that (Gdimm(HL g. T. a)) sampled domains are sufficient to learn a predictor most domains, while the lower bound shows that 22 (Gdim(H, G, r, a))
with error at most domains are necessary to achieve an error threshold T' E (T - a, T). Additionally, the lower bound does not apply to all domain families G; in some cases, the construction requires augmenting 9 with a few extra domains. It would be of moderate interest to close this gap.
Unlabeled data from some unseen groups. In this work, we assume no information is available from unobserved domains. However, in real-world applications such as healthcare, labeled data can be anpensive-particulaae
in rural regions where diagnostic tools may be limited-while unlabeled data are often cheaper and more accessible. This brings us full circle to the motivating scenario in the original paper domain generalization Blanchard et al. 2011 J, what is there termed automatic gating of flow cytometry data. In this problem, each patient yields a patient-specifie distribution (i.e. domain) of d-vectors of attributes of cells. The label might capture whether or not the given cell is lymphocyte. Our work strengthens the results of Blanchard et al.) [201 by obtaining generalization to all unseen patients, and not just in expectation over unseen patients. This inspiring scenario, in which unlabled data are plentiful, raises the following question: If we permit the (fixed) learned hypothesis to be modified based unlabeled samples from the test domain, can we beat our lower bound and get away with training on fewer than Gdim (H, G, a) domains, while maintaining the learning objective of performing well on every unseen domain?
References
Maryam Aliakbarpour, Konstantina Bairaktari, Gavin Brown, Adam Smith, Nathan Srebro, and Jonathan Ullman. Metalearning with very few samples per task. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 46-93. PMLR, 30 Jun-03 Jul 2024. URL httpps//pproceednns.. mlr. Titesss/2277/aaaaabrra
html
Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. A theory of PAC learnability of partial concept classes. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 658-671. IEEE, 2022.
Yannay Alon, Steve Hanneke, Shay Moran, and Uri Shalit. On the ERM principle in meta-learning. arXiv preprint arXiv:2411. 2024.
Martin Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint 1xXhv:1907002893, 2019.
Pranjal Awasthi, Nika Haghtalab, and Eric Zhao. Open problem: The sample complexity of multi- distribution learning for VC classes. Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 5943-5949. PMLR, 12-15 Jul 2023. URL, URI httphhttp:///ttt ttttps:///prccedinng mlr, .prss// v195/ wwwsthi2aaaaa.mm.a.aaa.aaa html
10

---

Shai Den-D.vid. John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 79:151-175, 2010.
Gilles Blanchard. Gyemin Lee, and Clayton Scott. Generalizing from several related classification tasks to a new unlabeled sample. Advances in neural information processing systems, 24, 2011.
Avrim Blum, Nika Haghtalab, Ariel D Procaccia, and Mingda Qiao. Collaborative PAC learn- ing. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran As- sociates, Inc., 2017. URL htpps/tttt///prreeeeddngg www.:s/.eerrippccoomm http://wwwcccooooooooooooo.cpppp 2tt.29992277722dd3336/68/89999 fil1://8e11122223e/aaccce/cceee1
httpp/ppper.iileeepppee/////// p
Jiecao Chen, Qin Zhang, and Yuan Zhou. Tight bounds for collaborative PAC learning via multi- plicative weights. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran As- sociates, Inc., 2018 URL /
pdf
Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared rep- resentations for personalized federated learning. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Pro- ceedings of Machine Learning Research, pages 2089-2099, PMLR, 18-24 Jul 2021. URL
//rpce///rocceding.. mlr. wttppps//1////ollnss////// html
Zhun Deng, Frances Ding, Cynthia Dwork, Rachel Hong, Giovanni Parmigiani, Prasad Patil, and Pragya Sur. Representation via representations: Domain generalization via adversarially learned invariant representations. arXiv preprint arXiv:2006. 1478, 2020.
Simon Shaolei Du, Wei Hu, Sham M. Kakade, Jason D. Lee, and Qi Lei. Few-shot learning via learning the representation, provably. In International Conference on Learning Representations, 2021. URL /tt//tttts://oeeeeriiee
John C Duchi, Vitaly Feldman, Lunjia Hu, and Kunal Talwar. Subspace recovery from heterogeneous data with non-isotropic noise. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and
A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 5854-5866 neurips cttccc//ppaao wccpppape__ac files/ Curran Associates, Inc., 2022. URL https::/ppoceeediiiiii Paper- Conference, .dff
Vikas Garg, Adam Tauman Kalai, Katrina Ligett, and Steven Wu. Learn to expect the unexpected: Probably approximately correct domain generalization. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 3574-3582, PMLR, 13-15 Apr 2021. http:ptts/////rroot
mlr. ppwss//130/gargrrreeee garp//gaagaaa... html
Mingming Gong, Kun Zhang, Tongliang Liu, Dacheng Tao, Clark Glymour, and Bernhard Schölkopf. Domain adaptation with conditional transferable components. In International conference on machine learning, pages 2839-2848. PMLR, 2016
Nika Haghtalab, Michael Jordan, and Eric Zhao. On-demand sampling: Learning optimally from multiple distributions. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 406-419. Cur- ran Associates, Inc., 2022. https::t:t:/ htt.htttts:/prroceeiieee neurips cc/ ccpppppp____ fil.files/see /aaper///p////aa//// Patp:/oeeeePaaeererrooeeeeeeeee. Conf-roooeeee.eeeeeeem pdf
Lunjia Hu and Charlotte Peale. Comparative Learning: Sample Complexity Theory for Two Hypothesis Classes. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics (LIPlcs), pages 72:1-72:30 Dagstuhl, Germany, 2023. Schloss Dagstuhl Leibniz-Zenttrum für Informatik. ISBN 978-3-95977-266-1 doi: 10.4230 URL https
202.37.
// /ttps/aa/o//eoooooooeeeeeee/////

---

Lunjia Hu, Charlotte Peale, and Omer Reingold. Metric entropy duality and the sample complexity of outcome indistinguishabiiiyy. In Sanjoy Dasgupta and Nika Haghtalab, editors, Proceedings of The 33rd International Conference on Algorithmic Learning Theory, volume 167 of P Proceedings of Machine Learning Research, pages 515-552. PMLR, 29 Mar-01 Apr 2022. URL https
//prccediiggs mlr www.spress/vie wttps///vv///huuu2 html
Michael J Kearns and Robert E Schapire. Efficient distribution free learning of probabiliistic concepts. Journal of Computer and System Sciences, 48(():464-44) 4416644444744 1994.
Michael P Kim, Christoph Kern, Shafi Goldwasser, Frauke Kreuter, and Omer Reingold. Universal adaptability: Varget-indeppendent inference that competes with propensity scoring. Proceedings of the National Academy of Sciences, 119(4)=221800)) 1100)221000991111 19, 2022.
Weihao Kong, Raghav Somani, Zhao Song, Sham Kakade, and Sewoong Oh. Meta-learning for mixed linear regression. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5394-5404. PMLR, 13-18 Jul 2020. URL htttp::/pproceeeeeeee kong20a. html
mlr wpwpserreiig.
Kasper Green Larsen, Omar Montasser, and Nikita Zhivotovskiy. Derandomizing multi-distribution learning. In A. Globerson, L., Mackey, D. Belgrave, A. Fan, U. Paquet, Tomezak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages wtl_ffflllsspeeeee ran Associates, Inc., 2024. URL httpttttt///rceeeiiingg neurips cc/paper_tteee Cowfeeenoe.oeeeccc.... pdf
Cur-
David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 3384-3393. PMLR, 10-15 Jul 2018. URL httpss://proceeddii
wwdraaa8a..aaaaaaaamaaaaa html mlr. aal..prss//e p/rpes/s//0/mmmrra18a.aa.
Andreas Maurer, Massimiliano Pontil, and Bernardino Comera-Paredes The benefit of multitask representation learning. Journal of Machine Learning Research, 17(81):1-32, 2016. URL
242.5-22222222 html
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 4615 4625. PMLR, 09-15 Jun 2019. URL htttts://ppooeeeeee
htt//moorrrii/ 19a. html
Omar Montasser, Han Shao, and Emmanuel Abbe. Transformation-invaiiann learning and theoretical guarantees for OOD generalization. The Thirty-eighth Anmual Conference on Neural Information Processing Systems, 2024. URL https: // http///ppereveieeeeeeeeee wwtp://eett/ttd//////e/to XRLaN)
Krikamol Muandet, David Balduzzi, and Bernhard Schölkopf. Domain generalization via invariant feature representation. In International conference on machine learning. pages 10-18. PMLR, 2013.
Huy Nguyen and Lydia Zakynthinou. Improved algorithms for collaborative PAC learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, ed- itors, Advances in Neurul Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL 3569df 3f69df 155561195ee277445554444428882063 pdf
Binghui Peng. The sample complexity of multi-distribution learning. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 4185-4204. PMLR. 30 Jun-03 03 Jul 2024. URL mlr http://innnnir..pppr//////////// prress//2AA7peeg244 .hmml
N Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1): 145-147, 1972. ISSN 0097-3165. doi: wtt.../....0.0000000013113909990 URL
12

---

Bernhard Schölkopf, Dominik Janzing, Jonas Peters, Eleni Sgouritsa, Kun Zhang, and Joris Mooij. On causal and anticausal learning. arXiv preprint arXiv:/206.666 6471, 2012.
Han Shao, Omar Montasser, and Avrim Blum. theory of PAC learnability under transformation invariances. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho. and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 13989-14001, Curran As-
sociates, Inc., 2022. URL /ttpstttss/////oceiiingg newrips cc/ pappraapppppppp Saapperrfilie filee//l//eeee...l wttpr//eeeeeeeeaeaa///ee paper/2022/ fil1:/58882200002000800000666666 htwpp//peeeettttoeeaa-e-oo-errre Conference, pdf
Saharon Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics, 41(1):247-261, 1972.
Kiran Koshy Thekumparampil, Prateck Jain, Pranceth Netrapalli, and Sewoong Oh. Sample efficient linear meta-learning by alternating minimization. arXiv preprint arXiv: 2021.
Nilesh Tripuraneni, Michael Jordan, and Chi Jin. On the theory of transfer learning: The importance of task diversity. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 7852-7862. Curran As- sociates, Inc., 2020. JtRpstttss//p/roeeeeiiii neurips. wwwrips.cccpappr.... www.fffleefapeeeee /202 http://98870fffee117776666333332
Paper .df
Nilesh Tripuraneni, Chi Jin, and Michael Jordan. Provable meta-learning of linear representations. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning. volume 139 of Proceedings Machine Learning Research, pages 10434-10443, PMLR, 18-24 Jul 2021. URL https: htttps://proceeddiiiiieo mlr press/ v139 wtwp//1ttttteeeeee http///rrrrraann11eea
html
L. G. Valiant. theory of the learnable. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, STOC '84, page 436 445, New York, NY, USA, 1984. Association for Computing Machinery. ISBN 0897911334, doi: 10. 10.1145/800057.8088 8008000 URL https
7/doi. aeroi.org/ii
org/ 10. 1145/ 0000057.808710
V.N. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264-280, 1971. doi: 10.1137/1 1 16025. URL httpp::://oi..rg/g///e 1137/1116113
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
Jindong Wang, Cuiling Lan, Chang Liu, Yidong Ouyang, Tao Qin, Wang Lu, Yiqiang Chen, Wenjun Zeng, and Philip S Yu. Generalizing unseen domains: survey on domain generalization. IEEE transactions on knowledge and data engineering, 8055-882,,, 2022.
Kun Zhang, Mingming Gong, and Bernhard Schölkopf. Multi-source domain adaptation: A causal view. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Zihan Zhang, Wenhao Zhan, Yuxin Chen, Simon Du, and Jason D Lee. Optimal multi-distribution learning. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference Learning Theory. volume 247 of Proceedings of Machine Learning Research, pages 5220-522 5223. PMLR, 30 Jun 03 Jul 2024. URL http: mlr. press/ press/v247. v247 zhang24b. html
Kaiyang Zhou, Ziwei Liu, Yu Qiao, Tao Xiang, and Chen Change Loy. Domain generalization: A survey. IEEE transactions on paltern analysis and machine intelligence, 45(4):439-44115, 2022.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We have included references to all main theorems and lemmas in Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See discussion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

We provided all the assumptions and complete proofs (some are in the ap- pendix).
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: The paper does not include experiments. All results are carefully proven and do not require experiments to establish correctness.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
15

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: This is theoretical paper. All results carefully proven and do require experiments to establish correctness.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nnis.cc
aoblic//uiide//Coeettuiiiss www.ssicinooooyyyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ wttps/cccppplccguua.eeaeaecccuea
Saaeee/CCoSSuubissS..S.. www.sssoiicgyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This is theoretical paper. All results are carefully proven and do not require experiments to establish correctness.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This is theoretical paper. All results are carefully proven and do not require experiments to establish correctness.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
16

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This is theoretical paper. All results are carefully proven and do not require experiments establish correctness.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:://wwrpppppccpppppp/tttccac
Answer: [Yes]
Justification: We have carefully read and comply with the NeurlPS code of ethics. This work is theoretical and we do not foresee harmful consequences.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., s if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification:
We note that our work is theoretical. We do not foresee any societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
17

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The work is entirely theoretical; we do not release new data or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We do not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
18

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
19

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
We only used LLMs for editing.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: /ttp:::///eurps... hatps////coooefeeeeee////////// for what should or should be described.
20

---

A Deferred Related Work
Many previous theoretical works domain generalization make explicit assumptions on how domains are related. |Blanchard et al. [2011] formulated the problem and approached it using kernel methods. They and MMandet al. 2013 differ from our work in assuming similarity among the various domains (possibly after a learned transformation); moreover, they achieve low error only in expectation over the choice of test domain. More recently, Moori aecently,MMhrri al. (2019) assumes that the learner has access to a family of training domains, and the test domains are a family of mixtures (i.e., convex combinations) of the training domains. The coefficients of the convex combinations
are assumed to be in restricted range. The works of [hao et al. [2022] Montasser et al. [024]
assume that the domains are related by transformations. These works MMohri et al., 20199 Shao
itt al.
2022, Montasser ct al. 2024] all use a min-max objective similar to our work. Ben David al.
2010 studies learning with a source (training) domain and a target (test) domain with the
assumption that the each hypothesis h E H has similar overall average on the two domains (they
define H-divergence as the largest gap between the two averages). Kim al. [2022] assume that the
ratios of the probability density between domains (i.e. propensity scores) are bounded and come from
a restricted family. SSchökkoff et al.] [2012). Zhang et al. (2015), Gong et al. (2016) formulate the
problem from a causal perspective and make corresponding causal assumptions.
Inspired by causal reasoning, and seeking eliminate spurious correlations, Arjovsky et al. [009 introduced Invariant Risk Minimization, in which the different domains correspond to training data collected in different environments which "could represent different measuring circumstances loca- tions, times, experimental conditions" and so on. Invariant Risk Minimization seeks a representation mapping for instances, under which the optimal classifier is identical for all environments. Deng et al. (2020). whose setting and assumptions exactly match ours, also seeks representation approach, specifically, via adversarial learning using techniques developed in Madras et al. [2018); their algo- rithmic results have provable guarantees for unseen domains only when the observed domains form cover with respect to H-divergeence for the set of possible domains.
The work of Garg et al. [202T] studies domain generalization with the goal of minimizing the average error across domains, which is equivalent to the error on the single large domain defined as the mixture of all the domains in the problem. This makes their learning task similar to the standard PAC learning with the additional advantage that the training data is grouped by domain. This advantage allows them to show computationally efficient learning algorithms for specific learning problems that do not have known efficient algorithms in the standard PAC learning setting.
Alon et al. [2024] study a related meta-learning problem, where instead of outputting a single hypothesis h. their learner outputs a hypothesis class which can be used later to learn a good hypothesis on a new task (analogous to a new domain) given additional data from that task. They focus on the realizable setting with performance measured using the average accuracy over random new tasks. A large body of work studies meta-lcarning for linear regression and related problems under the assumption that the underlying parameters of different tasks can be represented in shared low-dimensional subspace [Maurer et al. 2016 Kong et al., 2020 Tripuraneni et al. (220 [02 Du
ct al. 2021 Collins et al. 2021 Thekumparmppl al. 202 Duchi et al. 2022 Aliakbarpour et al. 2024
There is large body of recent and earlier work on multi diniribdditibbtiionn learning [Larsen et al. 2024
Zhang et al. 2024 Peng 2024 Awasthi et al.) [2023] Haghtalab et al. 2022 Chen et al. [0118] Nguyen and Zakynthinou 2018 Blum al. [017]. This problem is closely related ours in that they also do not impose structural assumptions on the domains, and they also consider the min-max objective. However, their goal is to learn hypothesis that performs well on the observed domains, so their focus
lies in the total number of data points required for learning (i.c., the sample or query complexity). In contrast, we aim to generalize unobserved domains and focus on the number of domains the leamer needs to observe- the domain sample complexity.
B Deferred Proofs
B.1 Proof of Lemma
Lemma 4.2 (Uniform convergence for partial concepts). Let F be a class of partial concepts
f: Z + {0, 1} on arbitrary input space Z. Assume that F has VC dimension d. For every
21

---

E Zyu and ô E (0,1/2), there exists
y y= ( <dlog* n log(1/6)
(6)
n
such that for every distribution P over for n i.i.d. data points , , drawn from P.
Pr 21ymnn
Bf F s.t. Przup (f(2) 1] y and Vi E [n], = 6.
We will use the following result.
Theorem B.1 (Quasipolnnomial Sauer- Seeeer-Shehh-eeie Perles Lemma for Disambiguations of Partial Concepts
[Alon et al. 2022]). Let F be class of partial concepts f f - {0, 1, ] defined on an arbitrary
domain Z with VC dimension d. Let S be subset of Z with size [S] = n 1. Then there exists
class F of total concepts f S {0,1} with size
F old
that satisfies the following. For every f F, there exists J E F such that for every S with f(s) {0, 1}, it holds that f(s) f(s).
Proof of Lemma 4.2 We apply the symmetrization trick. Specifically, we independently draw another data points = ....... z/ i.i.d. from P. By the multiplicative Chernoff bound, assuming n C/7 for a sufficiently large absolute constant C >> 0 (which can be guaranteed by the choice of 7 in (6)). for fixed satisfying (fz)
> 7, with probability at least 1/2 we have
Hi E [n]] f(z)) (} 7m/2.
Therefore, to show
7) suffices to show that
Pr 21 ye
[ F s.t. Hi [m] f(=)) = 1}} 7n/2 and Vi [m), = 0] < 8/2. (12)
The 2n data points ~ 21,.... An. #1 .1..... 2 can be sampled equivalently as follows. We first draw 2n i.i.d. data points Ti...., T2n from P, choose n data points from them uniformly at random without replacement as 21...., 2n. and define the remaining n data points as 2i..... 2/. We define r r: (F.,..., 72n), = (Z1...., ,n), = (zf....,,/) 2/)).
For fixed by Theorem B.1 there exists a class F of total concepts J fri...., r2a3 - {0, with
F (2n) Old
(13)
satisfying the following property: for every f E F, there exists F such that for every E [2n]
with f(r:) E {0, 1}, it holds that f(r;)= = f(r)). Therefore, to show (12). it suffices to show that for
every fixed choice of r, can bound the following conditional probability given
Pr. E3 s.t. Hi E [n] 7(4) 1 mm/2 and Vi E [(), 0 r] 6/2,
where the probability is over the random partitioning of r into z and z'. By the union bound, suffices to show that for every f F.F
Prz.zr (i [m] T(=)) = 1}1 7n/2 and Vi E [m).7(z) = 0 < 6/(2
Note that Hi E [n] F(+)) = 1}| > 7n/2 implies that among the 2n data points Ti,... P2n- more than 7/4 fraction of the data points r; satisfy f(r:) = 1. Conditioned on satisfying this property, since 21,...,
......,,,, 2,, are chosen randomly without replacement from Ti; ........ .2n. the probability that all the data points 21, .1...., 2n satisfy F(2)) 0 at most (1 -/4)". Therefore, it suffices to prove that
(1 7/4)" (/(2
This holds when
C
7 > log (1
n
for sufficiently large absolute constant choice of y satisfying (6).
C 0. By the above inequality can achieved by
22

---

B.2 Proof of Theorem 4.3
Theorem 4.3 (Lower bound). Consider an arbitrary class H. of hypotheses X + {0. 1) and an arbitrary family G of domains 'D (i.e. distributions over X x {0, 1.). Assume that Gdim G.T. for some O E R and E Z,,, where S a T < 1/2. Let Do be a distribution of (x. v) E X x {0. 1} satisfying erro, (h) = foror every h E H. Let Di...., Da E 9 be d domains shattered by H. and define G¹ = = (Do. , D'd as in (8) for
E (0, 1].
1
Then Gdim "H,'',,.0 Gdim(H,,', d. Moreover, for some > 0,8 E (0. 10.1/4). n E Z and an error 1-a (5- a, T), suppose there is an algorithm with the following property on every distribution P over G' satisfying TH. < oz takes n domains drawn i..d from P as imput, and with probability at least outputs hypothesis h such that
threshold 7' < 1-T
Erp.r (n) S
Then
7 Ω min {
1, d + log(1 (18)))
}).
(10)
Claim B.2. In the setting of Theorem 4.3 for every i 1...., and every hypothesis h {0, 13, we have
+
err (h) 2 X X1 - errp,
(14)
A
1-T
max (h), errp (h)) 1+X 1-
a>>
(15)
Moreover, the inequality
14) becomes an equality when h H.
Proof. By (8, for any hypothesis h, we have
errp; (h) (1 (1- A)erTD, (h) + X(1 errp, (h)).
Inequality 14 follows immediately from the trivial fact that errp, (h) 2 0. When h E H. we have errD, (h) so (I4) becomes an equality.
It remains to prove (15). Suppose errp, (h) <
I4X By (4).
A
e (h) 2 A
1+X
This proves the first inequality in (15). The equality in (15) follows from the definition of À in (9) The last inequality in (15) our assumption about r' in Theorem 4.3
Proof of Theorem
4.3
first prove that Gdim g', T, ax) d. By Claim B.2 for any Dj and the
corresponding D in 8
the emors of any hypothesis h E H on DD and D' are related as follows:
errp, (h) =1 errp: (h)/A.
Therefore,
crTDy (h) <T- = erT,, > 1 (f) eTT (h) >
(h) < (1-
(16)
where we used the definition of À in (9) Consider any set SCC g' shattered by H. Clearly Do cannot appear in S because erTy,, (h) = 0 for every h E H. By (16). D; and D cannot both belong to S, and replacing D/ with D; in S still leads to shattered set. We can thus change into a shattered subset of G without changing its size. This implies that the domain shattering dimension of H on G' does not exceed its domain shattering dimension on g. The reverse direction trivial so the two domain shattering dimensions are both equal to d.
23

---

Now we prove the lower bound (TO) on y. We can assume without loss of generality that Y < 1 1/8,
because otherwise we already have y (1) as needed establish the theorem. For every bit string
b E {0, 10, we define domains Do.... Da as follows:
Do Do.
D. Dis if
(D' if by =, for I....,d. d.
(17)
We define Pb to be the distribution that puts 47 probability mass on Do, and distributes the remaining 47 probability mass uniformly on D ....... Dd.
......,,u, Du are shattered by H. there exists a hypothsis We first show that PMP < r - a. Since D ha H such that for every = ,,...,d d,
emT,, (ho) < T - a,
if = 0, if 1.
errD, (hb) > T
When errD, (hb) T, by Claim B.2
errp; (h6) < A(1 T)
7
1 - (1-7)=r-a.
Therefore, p, (hs) < r
for every = 0, ,.. This completes the proof of our claim that
TP. <
Now let us consider the following process. We first draw b uniformly at random from {0. 1)d. and then draw n i.i.d. domains from Po to form a training set G. Let & be the output of algorithm given G' as input. With probability at least - 8, the output ì satisfies
Pr DrPP
eerrD (c) > S') ST
(18)
Let m be the number of domains among Di.... Da that do not appear in the training set S. By Claim B.2 conditioned on m, with probability at least 1/2, at least m/2 2 of these domains Dj satisfy
eIT (h) > r'.
That is, with probability least 1/2.
Pr [err (h) 7'| 2 (m/2) (4y/d) (2m/d) 7 D.P.
Therefore, conditioned on m > d/2, with probability at least 1/2, 18 does not hold. Since (18)
holds with probability at least 1 - 6, we have
Pr(m > d/2] < 28,
or equivalently,
Pr[d - m < d/2] < 25.
(19)
The nonnegative random variable d m the number of domains among Di...., Du that do appear in the training set S. Since the training set S is formed by n i.i.d. examples drawn from Pa which puts 4y total probability mass on DI.... Da, we have E[d m] I 4yn. By Markov's 's inequality,
Pr(d - m S 8ym] 2 1/2.
(20)
Combining
19 and 20 with our assumption that å < 1/4, we have
8yn 2 d/2,
which implies that 7 > d/61n). Moreover, with probability (1 1-4y)", the training set S contains no domains among D, Da. giving d = 0. Therefore, by (19).
25 Pr(d m d/2] Pr[d 0 (1 4y)"
This implies that 7 2 ((log((/o))))) 18))m)/ In summary,
Ω log(1/8)
}
d log(1/0) (d+log(1/0)
2 max
16n
24

---

B.3 Proof of Theorem 5.1
Theorem 5.1. For every positive integer there exists hypothesis class with VCdim(HL satisfying the following property. For any E (0.1/12), there exist l = (og(/a)) domains Di...., Dt such that
Gdim (H, (.), D2).03,
We need the following helper lemma.
m....,,,,,..... m) consider the hypothesis Lemma B.3. For odd positive integer m, domain X {0, 1, ,,..,
class H = {h1,-... .......... hm where (a;())) = M2 2 a) for every = 1,..., and x E X. There exists
distribution D of (Ir, y) X {0,1} such that
0.3 1m
if is odd;
errp(N) 0.3 + 4m ifi is even.
Proof. We construct the distribution D of (I., y) as follows. With probability 1/2, we choose x 0. With the remaining probability 1/2, choose I uniformly random from ....., m. That is, Pr(x = i = 1/(2m) for every = 1....: m. Conditioned on x = 0, we draw y E {0. 1) such that 0.1. Conditioned * O, we choose y (deterministically) if is odd, and y = 0f x is even.
Pr(y = 1/
For odd i E (1,...,m] we have
errp(h;)
0.1
+
[h,(2)) + I[ is odd]
2
2m
1
0.05
[1[ < and is odd] + 1[ 2 and is even))
2m
1
0.05
2m
2
2
0.3
4m
Similarly, for even i E {l...., .m). we have
ehr 0.05
[1[ < and odd] + 1[x 2 and is even))
2m
m
i +
0.05
2m
2
1
0.3
4m
Proof of Theorem 5./
We first prove the theorem in the special case where d 1. On domain
X : Zzo (0. .....). ), consider the hypothesis class H (h1, h2,...., where (x(x)) = M[ 2 i for every = 1, and x E X. Clearly, VCdim(H) 1.
Let be the largest integer satisfying 2*+ + < 1/a. By our assumption that a E (0. 1/12), we have k ((log(1/a))) Our goal is to construct & distributions D D.....; D3 that shattered by hi, ......, hx for K = 2*_ Let Ei.... Ex be all the K subsets of (1....,k) kk.. For every 1,.... k. we will construct D, such that for every I.....K. K.
crTD, (h+) 0.3 a,
if j E E;;
errp, (h:) 0.3,
if & E,
(21)
This ensures that DI...., Dí are shattered by hy...., "h....,hy, lxx as needed to prove the lemma.
It remains to show the construction of DD for every j = 1, 1,...,k k. It will become convenient to choose E, to be the whole set F, = [1,...,k} k.). This ensures that j E E2 for every j 1.... For fixed partition {L...., K} into consecutive non-empty blocks Si....,
S.....,,,,. Sm for some < K. Each
25

---

block St has the form S { 21- + 2.....,22 where 0 = 21 < ... < Im = K.
We define these blocks Si...., S, so that
j e E, for every odd & {l....,mL m] and every i i Sy;
j E, for every even l {1..... m) and every St-
(22)
If m is odd, define X' {Io, LI...I...... Zm If is even, we define X' {ro, 21, ..... 2m K
1}. By Lemma B.3 there exists a distribution Dj over X' x {0, 1} such that
errD, (hee) - 0.3
4(m + 1) < 0.3 -
for odd & m..
erTD, (hxr) 0.3
> 0.3
for even & fl....,m. m,).
(23)
4(m + -)
where used 4(m 1) < 4(K 1) 2 1/a. Recall that for each é = 1, I.... the
largest element in block S is Ie, so for every E St.
(x(x)= (x) for every I E X'.
Therefore, 23 implies
errD, (h/) 0.3
for every odd é m.]...,m]. and every i E St; for every even & {1....,m) m) and every i St.
crrp, (h4) 0.3
(24)
Combining 22 and (4 proves
Finally, we prove the theorem for a general positive integer d. On input space X' = [d] x X, we construct hypothesis class 76' using our hypothesis class H above as follows:
H {h: X' {0, 1 ......... ha H s.t. h (i, h,(x)) for every (i,x) E X'}.
This construction ensures that VCdim = VCdim = d. By our analysis above, there exist A 2 (log(1/a)) domains D..... D2 X that are shattered by H. Now for every E [d] and j E [k),, we define Di, to be the distribution of (i,z) E X' with x ~ Dj. These kd = ((dlogg(/// domains (D.,) (e,j)<[()) [E] are shattered by H', completing the proof.
B.4 Proof of Theorem 5.2
Theorem 5.2. Let be an arbitrary hypothesis class with VC dimension For any set of domains, any threshold R. and any margin (0, 1/2),
Gdim(H, T, O(dlog(1/a))
(11)
We will use the following classic result:
Theorem B.4 Sameer-Sheah--Perkeee Lemma (Sauer 1972 Shelah 1972)) Let F be a class of
concepts f 7 > {0, 1) defined arbitrary domain Z with VC dimension d. Let S be subset
of Z with size |S| = n 2 d. Then
FFsl S (en/dy" where Fs is the restriction of to the subset C Z.
Proof of Theorem 5.2 Let Di,..., Dr E E be domains shattered by H. By the definition of shattering, there exist K 2 hypotheses hi...., ...,...,gg hg E H. with the following property: for every pair of hypotheses h h22 with 1 S j1 < j2 I K. there exists i E {l...., k} such that lerrp (h,,) emrp (h222)
(25)
Let consider fixed domain DD for arbitrary
1, 1,...,k. k. We show that for some -kk,, there exists dataset S; consisting of m points (I1, B1)...... (Imr Vm) such that
lerrd, (h₂) errs, (h₂) a/2 for every j = I,...,K. K,
(26)
where erTs, (hy) is the empirical error S;:
crts, (h,) 1 m
m Σ
Isye + h,(xe)).
26

---

That is, S; is a representative dataset for distribution D; in terms of measuring the enror of the K shattering hypotheses. We prove the existence of S by the probabilistic method. For i.i.d. points (11, "........... (mm; 9/ drawn from Dr, by the Chernoff bound, for fixed j. (26) holds with probability at least 1/(2K) as long as m 2 Ca for a sufficiently large absolute constant C 0. By the union bound over j = ,.... K, with probability at least 1/2, the data points satisfy (26). proving the existence of S..
We have now proved that for every
1...., k. there exists a size-mn dataset S; satisfying (26).
where O(a =k).. Combining this with (25). we know that for any pair of hypotheses h h
with < j1 < j2 S K, there exists E {1...., k such that
errs, (h),) * errs, (hz2).
This implies that h3, (x) + h (x) for some (2. E S S (S1 U... U.). By Theorem B.4 for
n = 11 U ....UU U.E I mk O(a 21:2),
(27)
holds that
2 < (2 en/d)²
(28)
Plugging
(7 into (8) and taking the logarithm of both sides, we get
k/d - (llo((1/a) + log(2 + k/d)).
This implies k/d ((log(//a)) proving
27


Reviews:
[{"review_id": "THKltvE8J3", "reviewer": "Reviewer_VFhB", "summary": "This paper analyses the domain sample complexity—that is, how many domains must be randomly sampled to learn a model that performs reliably on both seen and unseen domains from a given family—within the PAC learning framework. Specifically, the authors derive both upper and lower bounds on the domain sample complexity using a novel combinatorial measure they introduce, called the domain shattering dimension. Furthermore, the authors establish a tight quantitative relationship between the domain shattering dimension and the classical VC dimension. This connection implies that any hypothesis class that is learnable under the standard PAC framework is also learnable under their proposed setting.", "questions": "Please see the strengths and weaknesses.", "limitations": "Yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 1, "originality": 2, "strengths_and_weaknesses": "## Strengths:\n\nThe authors derive both upper and lower bounds on domain sample complexity using a combinatorial measure they introduce, termed the domain shattering dimension, which appears to offer some degree of novelty, although its practical or theoretical implications are not immediately clear.\n\n## Weaknesses:\n\n- The paper does not provide any clear practical or theoretical implications for the domain generalization (DG) problem. In DG, we typically assume access to a limited number of source domains, and the key challenge is how to leverage these to generalize to unseen target domains. A more relevant formulation would focus on to what extent a model trained on a small number of domains can generalize well. In contrast, the question this paper raises—how many domains are needed to guarantee generalization to any unseen domain—feels somewhat unrealistic and disconnected from the practical challenges in DG. This formulation does not appear to offer useful insights for designing algorithms for DG.\n- Moreover, the authors seem to treat domains as individual samples and then define a new loss function at the domain level, comparing it to 0/1 loss on samples via a threshold $\\tau$. They then apply sample complexity bounds analogously at the domain level. However, this domain complexity upper bound does not seem to provide any additional insight beyond standard sample complexity bounds in the context of DG.\n- The paper states: \"domain sample complexity can still be very small if the domains in \\mathcal{G} are very similar.\" However, domain similarity is difficult to quantify, and even if we had a metric, it would only apply to the observed training domains. This observation is only meaningful if the number of training domains is large and diverse enough to represent a meaningful meta-distribution. If the training domains are limited and highly similar, it's unclear what conclusion we can draw—do we need more diverse training domains, or have we already captured enough information?\n- Regarding the connection to domain adaptation, the authors suggest defining a new divergence measure. However, it is unclear what the benefit of this new divergence is, or how it contributes to our understanding or improvement of domain adaptation techniques. This section lacks a clear motivation and purpose.", "was_revised": true, "final_justification": "**Note to Authors:**\nThe proof shows that the min-max ERM algorithm, which takes the maximum over sampled domains, is a consequence of the min-max objective in Definition 3.1. If the objective were defined using the standard ERM approach, the resulting algorithm would be an ERM algorithm. Therefore, the conclusion that the theory suggests the min-max ERM algorithm is superior to ERM is not true.\n\n**Overall:**\nThe paper treats domains as individual samples and defines a new loss function at the domain level. This loss function is then compared to the 0/1 loss on samples using a threshold $\\tau$. The paper applies sample complexity bounds similarly at the domain level. The current results suggest that with a sufficiently large number of training domains (assuming the domains are iid sampled), generalization is guaranteed. However, this formulation does not appear to offer substantial insights for designing algorithms for domain generalization.", "rebuttal": "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.\n\n**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.**\n\n**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.\n\n**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*.\n\nWhile 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).\n\n**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.  \n\n**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.\n\nBen-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.\n\nWe 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.\n\nThe 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."}, {"review_id": "IL3gOvXpsp", "reviewer": "Reviewer_KZw4", "summary": "The paper studies domain adaptation, focusing on quantifying how many domains are sufficient to learn a model that performs well across both seen and unseen domains within a family. Under the assumption that there exists an estimator that achieves low error across all domains, the authors derive upper and lower bounds on the domain sample complexity, introducing a new combinatorial quantity, the \"domain shattering dimension.\" The upper bound is established on Min-Max ERM. \nInterestingly, the authors also construct counterexamples demonstrating that this bound is not instance-optimal, indicating that further improvements may be possible in specific settings. Additionally, the paper draws connections between the proposed framework and existing measures in domain adaptation, such as the H-divergence.", "questions": "Personally, I would have also been interested in connections to the underlying data generating process, e.g., whether causal assumptions could help (sparse mechanism shift; independent causal mechanisms) - cf. https://arxiv.org/abs/1206.6471, https://proceedings.mlr.press/v48/gong16.html, https://ojs.aaai.org/index.php/AAAI/article/view/9542. But don't take this as a criticism of the paper.", "limitations": "Limitations are discussed in the last section.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "This is a serious theoretical contribution. The authors formalize the domain adaptation problem in a rather general setting—without assumptions on domain similarity—and provide tight upper and lower bounds applicable to arbitrary hypothesis classes and classes of domains. \nThe results connect the new notion of domain shattering dimension with established concepts from the literature, offering a unified perspective on domain generalization and adaptation.\nOne potential drawback is that, in practice, it can be challenging to clearly specify or identify the class of domains relevant to a given problem. Computing the domain shattering dimension would then be difficult.", "was_revised": false, "final_justification": "", "rebuttal": "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."}, {"review_id": "XZ5Wcxg4ql", "reviewer": "Reviewer_3Zud", "summary": "This paper tackles a \"meta-learning\" problem of understanding domain generalization in the same vein as how sample complexities are derived in PAC learning to give statistical guarantees. In this setting, there exists a family of domains $\\mathcal{G}$, where every domain is a distribution on instance-label pairs, and a concept class $\\mathcal{H}$ and the goal is to characterize the number of domains needed to be observed in the training data such that it is possible to select an $h \\in H$ that yields low error on unseen domains. The idea is that there is a distribution $\\mathcal{P}$ over $\\mathcal{G}$ and using PAC-like statistical guarantees, to produce a classifier $h$, with high probability, that has low expected error on all domains in $\\mathcal{G}$ with respect to $\\mathcal{P}$.\n\nThe authors construct a new combinatorial quantity called the domain shattering dimension that is defined in somewhat similar fashion to the fat shattering dimension. It essentially measures the \"capacity\" of $\\mathcal{G}$ in the sense that it captures the largest set $S \\subseteq \\mathcal{G}$ such that for any subset $S' \\subseteq S$, there exists a classifier $h$ with error below a certain threshold on domains in $S'$ and error above a threshold for all domains in $S \\setminus S'$. The authors use the domain shattering dimension to construct both upper and lower bounds on the number of domains needed to achieve successful domain generalization and also explore connections with the VC-dimension.", "questions": "- If my understanding is correct, is it true that the VC dimension of the partial concept class generated from $\\mathcal{G}$ is equivalent to the domain shattering dimension?\n- This is a follow-up to my point in the weakness section. Is there a somewhat altered notion of the domain shattering dimension that additionally takes into account the structure of domains in $\\mathcal{G}$ with respect to the instance space? To me (I could be wrong), it seems to make sense that the domain sample complexity can also be tied to the inherent structure of the domains itself because one could leverage this information in learning regardless of the different domains seen by the learner.\n- In $(\\tau, \\alpha, \\gamma, \\delta)$-domain learnability, is there a size on what $m$ is required to be? Is the size of $m$ inferred from VC theory on the number of samples needed to obtain uniform convergence guarantees on $\\mathcal{H}$?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper tackles a new problem of domain generalization that hasn't been explored before. \n- The paper is quite well-written and the technical details of their constructions are accessible.\n- For the upper bound, the technique of casting the domain learnability problem as a partial concept class and then using machinery established by Alon et al. to produce a uniform convergence guarantee is quite clever. \n\nWeaknesses:\n- My primary concern is the way the lower bound is constructed to show that the sample complexity using the domain shattering dimension is indeed tight up to logarithmic factors. As explained in the first paragraph of Section 4.2, the domain shattering dimension doesn't necessarily provide a lower bound for the domain sample complexity in all cases. For the specific mentioned by authors in Section 4.2, it seems that even the domain sample complexity generated from the domain shattering dimension provides a pretty loose upper bound (i.e. much larger than the true domain sample complexity). Generally, one tries to show the validity of a combinatorial quantity by showing that it measures the hardness of a learning instance through lower and upper bounds that work in the same exact learning setting. Here, the family $\\mathcal{G}$ is augmented to the family of $\\mathcal{G}'$ to prevent certain degenerate cases and the lower bound is on this $\\mathcal{G}'$. Altering the learning setting for the lower bound seems a bit concerning because the lower bound no longer certifies the hardness of the original problem instance.", "was_revised": true, "final_justification": "Overall, I lean positively toward this paper getting accepted at NeurIPS. My primary concern with this paper was their lower bound construction in showing that the domain shattering dimension is critical when observing the sample complexity. The authors successfully addressed my concerns and I recommend the authors to add a more detailed explanation of the lower bound construction in that section of the paper.", "rebuttal": "Thank you for appreciating our work and providing insightful comments. Below are our answers to your specific questions:\n\n**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.\n\n**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.\n\nHowever, 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}'$.\n\n**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)."}, {"review_id": "JZGFSjl6vl", "reviewer": "Reviewer_BJVM", "summary": "The paper studies an important problem in domain generalization(DG): how many randomly sampled domains are needed to perform well on unseen domains? To this end, the papers develops a new measure, domain shattering dimension and also establish a relationship between this dimension and the classic VC dimension.", "questions": "The following are the questions/suggestions:\n\n1. The motivation lines in 71-74 need detailed justification.\n\n2. It is not sure how will the developed theory be used in practical scenarios? Atleast a toy experiment is needed to establish the significance of the developed theory.\n\n3. The connection to domain adaptation section is not well explained. How will the relaxed H-divergence upper bound the target error? Can the same idea be extended to H \\delta H divergence? This divergence is actually used in the final upper bound developed in Ben-David et. al [2010]", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The paper addresses an important problem that is highly relevant in practical scenarios.\n\n2. It is always valuable to see theory in DG: the paper develops a new combinatorial measure characterizing domain sample complexity and establishes its relationship with VC dimension.\n\nWeaknesses:\n\n1. Weak motivation: In Lines 71–74, the paper claims that for a different threshold \\tau' the fat shattering dimension grows large, but provides no detailed justification for this assertion.\n\n2. Missing practical experiment: Seminal theoretical papers in domain adaptation and domain generalization (Ben-David et al., 2010; Blanchard et al., 2011) always accompany their theory with a practical experiment demonstrating its usefulness. This paper provides no such experiment.\n\n3. The section 6, where the paper connects the developed domain shattering dimension to domain adaptation is not explained clearly. In lines 312-314, it is mentioned that the domain shattering dimension upper bounds the error. But in the paper it only establishes the relationship between relaxed H-divergence and H-divergence in Line 321. It is not clear if this relaxed H-divergence can upper bound the target error? Also in Ben-David et al. [2010] the upper bound that is finally developed uses H \\delta H divergence. Will a similar relaxed version of H \\delta H divergence exist?\n\n4. There are several typographical errors: Lines 143, 213, 313 (it should be domain adaptation and not domain generalization), 81 (before this line there is no reference or explanation about what is partial concept class) and 165 (\\gamma is not defined)", "was_revised": true, "final_justification": "The rebuttal has addressed most of my concerns.", "rebuttal": "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.\n\n**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.\n\nOur 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).\n\n**Regarding experiments.** While our work is purely theoretical, we’d like to emphasize two key takeaways:\n\n1. **Conceptual insight**: \nOur 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.\n\n2. **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.\n\nWe 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.\n\n\n**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.\n\nOur 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.\n\nWhile 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.\n\nWe 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.\n\n**Typographical Errors.**  Thank you for finding these! We will correct them in the revision."}, {"review_id": "0UZGOfgupa", "reviewer": "Reviewer_M2uG", "summary": "This paper investigates how many domains are needed to train a model that generalizes well to unseen domains from a theoretical perspective? This problem is formulated as a PAC learning setting and using a new combinatorial complexity measure called the domain shattering dimension, extensions analogous to classic PAC learning are offered. The domain shattering dimension captures how complex a hypothesis class is in relation to a family of domains, and it determines the number of domains required to ensure generalization. The central insight is that while VC dimension explains learning on a single domain, domain sample complexity quantifies how many domains a learner must see to perform well on unseen domains. The domain shattering dimension measures how well a hypothesis class can separate domains with respect to error thresholds. The authors provide tight upper and lower bounds on domain sample complexity using this new dimension. They design a min-max ERM algorithm and prove that the number of required domains depends logarithmically on the domain shattering dimension. Moreover, they show this measure is tightly related to the VC dimension. The paper also explores connections to domain adaptation, showing that when domains are similar (as measured by a variant of H-divergence), the domain shattering dimension is small.", "questions": "1. While this work might be an interesting work for a venue like COLT, it will not be very interesting in the absence of any empirical validation for the general audience of NeurIPS. Why there is not empirical experiments to validate the theoretical results or at least show their applicability in some cases?\n\n2. What are the benefits of this work and the results for modern ML models?\n\n3. The theory assumes the hypothesis class H is given and contains a suitable hypothesis, but how can this be verified in practice?", "limitations": "I would like to highlight that while I am familiar with the broad concepts of PAC-learnability and understand the paper, theoretical ML is not my research area and it is not something that I work about on a day to day basis. For this reason, my confidence in rating  is low because it is challenging for me to judge the novelty level of this work from theoretical perspective. I hope the rest of reviewers can compensate for it. Despite this shortcoming, I am quite familiar with empirical aspects domain generalization and domain adaptation.\n\n1. Similar to PAC-learning, this work provides guarantees when the hypothesis class has finite domain sample complexity. Deep neural networks, however, typically have extremely large or even infinite VC dimension, making the standard PAC bounds uninformative in this context. As a result, the sample complexity guarantees become unhelpful.\n\n2.  The theory is built around ERM. In deep learning, however, practical optimization cannot search the entire hypothesis space and often only finds local minima, not the global one required by ERM. This means the theoretical guarantees do not directly translate to the way deep learning models are actually trained.\n\n3. While deep learning models can be trained efficiently in practice, the theoretical guarantees about computational tractability provided by PAC-learning are not tight or meaningful for modern neural architectures.\n\n4. The classic PAC model assumes the data can be generated by some function within the hypothesis class which is rarely true for deep learning.", "rating": 3, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n- The paper is well written and can be followed without the need to check the details of proofs.\n\n- Introduction of domain shattering dimension for characterizing domain generalization sample complexity is novel and new.\n\n- The results and algorithms apply to binary classification, multi-class classification, and regression.\n\nWeaknesses:\n\n- The practical value of this work to the current trend in AI is unclear.\n\n- There is no empirical verification. \n\n- The domain shattering dimension is hard or even impossible to compute or estimate for practical deep networks, similar to how VC dimension is often intractable.\n\n- A core assumption is that the hypothesis class contains a single model that performs well across all domains. But in diverse domain distributions. this assumption is probably wrong.\n\n-", "was_revised": true, "final_justification": "I acknowledge the theoretical merits of this work but remain unconvinced about practical benefits of this work and its applicability for deep learning. Given that the reviewers are divided, I leave the decision to AC and would be OK if my opinion is discarded in favor of positive opinions. I would also like to add that theoretical ML is not my research focus and I might have not fully grapsed the theoretical novelty of this work.", "rebuttal": "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.\n\n**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:\n\n1. **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.\n\n2. **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.\n  \nWe 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.\n\n**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).\n\nOf 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.\n\n \n\n**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.\n\nWe 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.\n\n**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."}]

Author rebuttal:

Meta-review: [nice summary lifted from one of the reviews] The paper studies domain adaptation, focusing on quantifying how many domains are sufficient to learn a model that performs well across both seen and unseen domains within a family. Under the assumption that there exists an estimator that achieves low error across all domains, the authors derive upper and lower bounds on the domain sample complexity, introducing a new combinatorial quantity, the "domain shattering dimension." 

The theoretically-inclined reviewers seem to praise the results of the paper (5-4-4). They also engaged in discussion with the authors, who clarified most issues that were raised. On the other hand the more skeptical reviewers insist more on limited applicability issues in practice (3-3). Given the strongly theoretical/fundamental inclination of the contribution and the novel theoretical contributions pointed out by the reviewers, I am in favor of accepting.
Decision: Accept (poster)