PaperlayerView exact revision on arXiv

Source-linked AI summary

How Many Samples Are Enough for Learning Across Domains?

Hong Zheng

arXiv:2609.39336v1cs.LG

TL;DR

Existing theory lacks a principled account of how many samples each training domain needs for learning across domains. This paper derives per-domain sufficiency criteria from learning bounds. The criteria show that required samples decrease linearly as the number of training domains increases, while retaining a minimum requirement.

  • Problem

    Existing theory lacks a principled characterization of per-domain sample requirements and of what makes samples sufficient.

    Source: §1 · p. 2

  • Method

    The paper derives criteria for per-domain sample requirements from upper learning bounds under mild assumptions.

    Source: §1 · p. 2

  • Results

    Required samples per domain decrease linearly as the number of training domains increases, but cannot become arbitrarily small.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The criteria provide theoretical guidance for assessing dataset adequacy.

    Source: §1 · p. 2

    The bounds require bounded loss and additional assumptions; without them, they cannot effectively guide domain-generalization learning or determine sample sufficiency.

    Source: §2.4 · p. 14

Abstract

from arXiv · show

Understanding the fundamental mechanisms of learning is essential for designing systems with strong generalization. Recent studies have shown that increasing the number of training domains, or enlarging the distribution shift among them, improves generalization when each domain contains sufficiently many data samples. However, the conditions under which the data samples can be considered sufficient remain unexplored. In this work, we fill this gap by establishing criteria for per-domain sample requirements based on the presented learning bounds. These criteria not only reveal an inverse linear scaling law between the number of training domains and the number of samples required per domain, but also explain the fundamental rationale behind the assumption of data sufficiency, thereby providing theoretical guidance for assessing the adequacy of existing datasets and constructing datasets. This differs from classical learning theory, as the number of samples required is highly dependent on the number of training domains. Additionally, we prove the close relationship between in-domain learning and out-of-domain generalization through the presented generalization bounds, and lastly discuss some key arguments.

1 Introduction

Domain-generalization theory has linked generalization to the number and diversity of training domains, but has not established how many samples each domain needs. This work derives per-domain sample criteria from learning bounds, revealing their dependence on domain count and connecting in-domain learning bounds to out-of-domain generalization.

1 Introduction

  • Classical learning theory developed non-asymptotic bounds under an i.i.d. assumption, which becomes limiting when domain generalization involves distribution shift.Source: §1 · p. 1
  • Prior domain-generalization theory associates better unseen-domain generalization with more training domains or greater distribution shift, assuming sufficient samples within each domain.The number of samples that makes this assumption valid had not been thoroughly investigated.Source: §1 · pp. 1–2
  • The per-domain sample requirement decreases linearly as training domains increase, but retains a minimum even as the number of domains tends to infinity.The criteria are derived from learning bounds and provide theoretical guidance for assessing and constructing domain-generalization datasets.Source: §1 · p. 2
  • The paper establishes per-domain sample-requirement criteria from upper learning bounds under mild assumptions, also recovering prior results on the role of training-domain count..Source: §1 · p. 2
  • Generalization bounds characterize error under distribution shift for finite training domains whose samples meet the proposed criteria, linking in-domain learning performance with out-of-domain generalization.Source: §1 · p. 2

2 Theoretical Results

This section develops bounds relating the number of source domains and per-domain sample size to learning and target generalization, including sample-sufficiency criteria and their refinement using variance information. It then discusses how these criteria guide dataset evaluation and construction, alongside assumptions and practical limits.

2.1 Preliminares

  • Each domain may have its own Bayes-optimal classifier, avoiding the stronger requirement of a shared minimizer and allowing substantial distribution shifts.The setup treats source and target domains as distinct distributions and assumes no target-domain information is available during training.Source: §2.1 · p. 3

2.2 Bounds

  • For a fixed error tolerance, the standard bound yields an inverse-linear relationship between domain count and per-domain sample size, with a nonzero sample floor even as domains increase.The bound’s main order is O(M/EN), with a complexity term governed by dvc and N.Source: §2.2 · pp. 5–6
  • With λ*, target-domain relative expected loss is bounded by learning, complexity, and source–target discrepancy terms; as E and N grow, in-domain learning governs out-of-domain generalization.The discrepancy term reflects differences between source and target joint distributions and is unknown during training.Source: §2.2 · pp. 6, 8

2.3 Tighter Bounds

  • With variance information σ², the per-domain sample lower bound remains inversely related to E but becomes tighter, yielding a more precise sufficiency criterion when σ² is small.When σ² is large, the tighter bound’s advantage may deteriorate relative to the bounded-loss bound.Source: §2.3 · pp. 9–10
  • The tighter target-generalization bound improves on Theorem 3 when both σ² and σhat² are sufficiently small, and σhat² is the variance of the source-domain error ϵ.The bound retains bias and complexity terms alongside its main order term.Source: §2.3 · p. 11

2.4 Discussion

  • The discussion extends the average-size criterion to assess sample sufficiency in any individual training domain by substituting the other domains’ sample sizes into the inequality.The authors present the lower bounds as criteria for the sufficient-sample assumption in each domain.Source: §2.4 · p. 12
  • show E tightens a minmax-risk lower bound, while (Dwork et al., 2026) similarly find E improves an upper bound; both assume large or infinite N.Source: §2.4 · p. 13
  • (Zheng and Teng, 2026) rely on KL's absolute-continuity assumption; require small feature dimension and do not discuss generalization effects.Source: §2.4 · p. 13
  • The authors state that their bounds converge at O(1/EN), while noting that surpassing existing bounds is not the work's aim.Source: §2.4 · p. 13
  • Although the standard consistency bound makes empirical learning increasingly consistent with expected risk as EN→∞, it implies N→1 as E→∞ and offers little guidance on per-domain sufficiency.Source: §2.4 · p. 13
  • For fixed E, ε approaches similar asymptotes as N grows, whereas fixed N yields different asymptotes as E grows.Under the selected parameters, targeting ε→1.0 (ϵ→0.58) requires N≥25; in Group B, only N=50 and N=100 meet this condition.Source: Figure 2 · p. 14, §2.4 · p. 14
  • The results require bounded loss and σ² and σ̂² for bounds (6) and related generalization bounds; Y={0,1} also limits direct regression use unless transformed to [0,1].Source: §2.4 · p. 14
  • In practice, λ* is often modeled by assuming target and source data differ but are related, while evaluating it directly is generally impractical because it requires the underlying distributions.Source: §2.4 · p. 14
  • The criteria can assess whether available samples suffice for ERM; when Nmax < χϵE−1 + µϵ, Structural Risk Minimization may be preferred over ERM or ERM-based learning objectives, and guide data collection.Source: §2.4 · p. 15

3 Related Works

The related work traces domain generalization from foundational theories and early domain-adaptation work to studies of training-domain number and distribution shift. It also reviews invariant, causal, and regularization-based learning approaches and their stated assumptions or limitations.

Theoretical Bounds

  • Recent theory examines how the number of training domains and the degree of source-domain distribution shift affect generalization.Wang et al. (2024) and Dwork et al. (2026) study domain number; Zheng and Teng (2026) study distribution shift.Source: §3 · p. 15

Learning Methods

  • Invariant risk minimization and its variants assume that invariant features learned from source domains generalize out of distribution, but their effectiveness and failure conditions have been questioned.Causality-based methods require stronger assumptions, while regularization-based methods have shown promise for improving domain generalization and facilitating practical application.Source: §3 · p. 15

Theoretical Bounds

  • The review places domain-generalization methods within a longer theoretical lineage, from VC and Massart-type bounds to early work on learning across domains.It also notes bounds for specific learning methods.Source: §3 · p. 15

4 Conclusion

The paper characterizes how many samples an individual domain needs for learning across domains, with a requirement that varies with the number of training domains. It presents this as theoretical guidance while noting that it does not experimentally validate its predictions.

Conclusion

  • The per-domain sample requirement varies with the number of training domains, unlike classical results such as VC bounds.The paper argues that its criteria also provide a guarantee for single-domain generalization.Source: §4 · p. 15
  • The paper does not provide experiments to validate its theoretical predictions and leaves such validation to interested readers.The authors identify this as a limitation of the work.Source: §4 · p. 15
  • The conclusion frames the work as answering how many samples are sufficient for learning across domains.It focuses on the sample requirement for an individual sub-domain in the domain-generalization setting.Source: §4 · p. 15

Appendix A.

Appendix A supplies lemmas and their proofs used to prove the paper’s main theorems.

Appendix A

  • Appendix A provides lemmas used to prove the main theorems.The appendix states that it provides the lemmas along with their proofs.Source: Appendix A · p. 16
  • The appendix’s stated role is supporting the proofs of the main theorems.It does not describe additional results in this passage.Source: Appendix A · p. 16
  • The lemmas are accompanied by proofs in Appendix A.This restates the appendix’s stated contents.Source: Appendix A · p. 16

A.1 Lemmas

Appendix A.1 collects inequalities and lemmas used in the paper’s arguments, including VC-class risk bounds and tools for handling distributional comparisons. It also states that the cited i.i.d. lemmas apply within a single domain in domain generalization.

A.1 Lemmas

  • The appendix illustrates applying a classical inequality with Zi defined as γ(h, ξi), assuming Zi lies in [0, Mi].It also notes that a corresponding result holds with different coefficients when Zi = ℓN,i(h, s) lies in [−Mi, Mi].Source: §A.1 · p. 16
  • For an empirical risk minimizer over a VC-class, the cited lemma gives an inequality under a margin condition, and its bound is described as consistent with the well-known VC bound.The passage notes that the displayed version is simplified to a bound related to VC dimension.Source: §A.1 · p. 18
  • The appendix describes using random combinatorial entropy to measure the size of a VC-class and relates it to VC dimension through Sauer’s lemma.For N ≥ dvc, it states HA ≤ dvc(1 + log(N/dvc)).Source: §A.1 · p. 18
  • The appendix states that the i.i.d. assumptions of Lemmas 11 and 12 mean those lemmas hold within a single domain in domain generalization.This qualifies the setting in which the lemmas apply.Source: §A.1 · p. 19

Related papers

Loading 2609.39336v1…