Research map / Label-efficient and robust learning / Domain adaptation and generalization

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

NeurIPS 2025 · Label-efficient and robust learning › Domain adaptation and generalization · approach: Optimization-based domain generalization · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Characterizes how many randomly sampled domains are needed for domain generalization in the PAC framework via a new domain shattering dimension, with matching upper and lower bounds up to polylog factors and a tight O(d log(1/α)) relation to VC dimension.

Problem

How many i.i.d.-sampled training domains are needed so that a learned predictor achieves low error on nearly all seen and unseen domains from a meta-distribution over a domain family (domain sample complexity).

Approach

Introduces the domain shattering dimension, a fat-shattering-style combinatorial measure with a single fixed threshold across shattered domains, and shows it tightly characterizes domain sample complexity via a min-max ERM upper bound and a matching lower bound; relates it to VC dimension via O(d log(1/α)) upper and Ω(d log(1/α)) lower bounds.

Key results

• Upper bound: min-max ERM achieves Er_{P,tau}(h) <= O((d log^2 n + log(1/delta))/n) where d is the domain shattering dimension.
• Lower bound: Omega((d + log(1/delta))/n) domain sample complexity for threshold tau' slightly above tau - alpha, matching the upper bound up to O(log^2 n).
• Domain shattering dimension is at most O(d log(1/alpha)) for VC dimension d and is Omega(d log(1/alpha)) for some classes.

Surprising findings

• Standard ERM can fail in the domain generalization setting; a toy example shows it may pick a hypothesis with worst-case error 0.5 over one with uniform 0.3 error.
• The domain shattering dimension can exceed the VC dimension by a factor growing as log(1/alpha), so PAC learnability does not imply domain sample complexity equal to sample complexity.

Limitations

• The domain shattering dimension is generally hard to compute, so choosing tau is difficult.
• A gap remains between upper bound (O(Gdim) domains at threshold tau) and lower bound (Omega(Gdim) at a slightly lower threshold tau'), and the lower bound requires augmenting G with extra domains.
• Assumes no unlabeled data from unseen domains is used.

Experimental setup

Metrics: domain error probability Er_{P,tau}(h) domain sample complexity

Baselines: standard ERM fat-shattering dimension bound

Builds on: fat-shattering dimension VC dimension Sauer-Shelah-Perles lemma H-divergence

Closest papers by meaning

• Lost Domain Generalization Is a Natural Consequence of Lack of Training Domains (AAAI 2024 · similarity 0.89)
• Unknown Domain Inconsistency Minimization for Domain Generalization (ICLR 2024 · similarity 0.86)
• Seeking Consistent Flat Minima for Better Domain Generalization via Refining Loss Landscapes (CVPR 2025 · similarity 0.86)
• Set Valued Predictions For Robust Domain Generalization (ICML 2025 · similarity 0.85)
• Mixup-Induced Domain Extrapolation for Domain Generalization (AAAI 2024 · similarity 0.85)
• Robust Domain Generalization under Divergent Marginal and Conditional Distributions (NeurIPS 2026 · similarity 0.85)