CS Paper Radar

How Many Samples Are Enough for Learning Across Domains?

Hong Zheng

cs.LG ·submitted 2026-09-30 09:05 UTC · v1
theory

Abstract

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Can Domain Generalization be Guaranteed in Small-Sample Learning?

cs.LG ·2026-09-30 ·Hong Zheng
similarity 0.75
Abstract

The small-sample learning problem remains a fundamental challenge in machine learning because limited training data lead to unstable model estimation and generalization. Structural Risk Minimization (SRM) has long been regarded as a principled solution under the classical i.i.d. assumption. However, domain generalization (DG) violates this assumption, leaving the theoretical role of SRM in DG largely unexplored. To bridge this gap, we establish the first theoretical guarantees for SRM in DG under mild assumptions. Specifically, based on the concept of stability, we derive learning consistency and generalization error bounds and prove that these bounds become tight when the hypotheses satisfy the stability condition. Building upon this, under a specific hypothesis space assumption, we establish stability, learning, and generalization bounds for SRM. We further discuss the applicability of these bounds to deep learning. This work establishes theoretical foundations for SRM under distribution shifts and sheds light on the design of robust DG algorithms in small-sample scenarios.

0.20

Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation

cs.LG cs.AI ·2026-10-13 ·Behrooz Tahmasebi, Melanie Weber
published similarity 0.75
Abstract · 32 pages, 1 figure. An extended abstract of this paper appeared at the ICML 2026 HiLD Workshop (July 10, 2026)

Modern machine learning models increasingly operate on variable-size structured data, such as sets and graphs. A central requirement is \emph{size generalization}: the ability of a model trained on inputs of one size to generalize to inputs of a different, potentially much larger, size. Classical statistical learning theory, however, primarily considers fixed input domains, and its guarantees often deteriorate with input dimension. Although extensive work has established when models on sets and graphs can be transferred across input sizes, such results do not characterize the statistical cost of doing so: the sample complexity of size generalization, and its relationship to classical in-domain learning, remain largely unknown. We develop a statistical learning theory of size generalization and establish a sharp exponential separation in sample complexity. Letting $n$ denote the number of training samples, we show that polynomial source decay is insufficient for efficient size generalization: while it yields error $n^{-Θ(1)}$ and hence polynomial sample complexity for in-domain learning, size-generalization error decays only as $(\log n)^{-Θ(1)}$, yielding an exponential separation. Thus, polynomial in-domain sample complexity can become exponential across sizes. We then identify an exponential source condition under which size generalization achieves error $n^{-Θ(1)}$, recovering polynomial sample complexity. These guarantees are independent of input dimension and depend only on the number of training samples, yielding dimension-free scaling laws. We also provide matching minimax lower bounds, establishing optimality. To our knowledge, this work provides the first dimension-free minimax theory of size generalization and a rigorous characterization of when, and at what statistical cost, learning can transfer across input sizes.

0.31

Extending Rademacher Complexity-Based Generalization Theory to Domain Generalization

cs.LG cs.CV ·2026-11-19 ·Xi Wang, Liang Bai, Xian Yang, Richard Yi Da Xu
similarity 0.69
Abstract

Domain generalization (DG) aims to train models on multiple source domains with distinct distributions to ensure robust performance on unseen target domains. In doing so, it elevates the concept of generalization from the traditional sample level to the distribution level. Existing theoretical frameworks introduce a domain space endowed with a meta-distribution to extend classical generalization analysis to this new setting. However, these approaches typically treat the domain space as devoid of geometry. In reality, the domain space is an inherently infinite-dimensional, nonlinear abstract space composed of probability distributions, and its complex geometric properties fundamentally determine generalization behavior. Consequently, existing geometry-free theories of domain generalization have a fundamental limitation. They lack a formal characterization of what distinguishes distribution-level generalization from sample-level generalization, leaving the inherent difficulty of generalizing across domains largely unexplained. To bridge this gap, we formalize the domain space as the Wasserstein space over the representation space. Building on the geometric properties of this space (specifically the $\mathrm{CD}(K,\infty)$ curvature theory) we derive a novel, geometry-dependent DG error bound. By introducing an additional curvature-dependent confidence term, this bound formally disentangles the two levels of generalization effects and reveals the essential nature that domain generalization is affected by both the invariance and the curvature of the representation space. Finally, we experimentally validate the effect of curvature on domain generalization.

0.13

Epiplexity Guided Data Selection and Generation for Out-of-Distribution Generalization

cs.LG cs.CL ·2026-08-12 ·Ellen Su, Andres Potapczynski, Shikai Qiu, Edward Hughes, Andrew Gordon Wilson
code/data similarity 0.68
Abstract · Code available for EpiSelect (https://github.com/eysu35/EpiSelect) and EpiGen (https://github.com/eysu35/EpiGen)

Modern systems are increasingly expected to transfer across tasks not specified during training. What data facilitates generalization to unanticipated settings? One hypothesis is that data with more structural information could contain shared circuits and subprograms that may be recycled in a wider array of downstream settings. Epiplexity, a recently proposed measure of the structural information a compute-bounded learner can extract from data, offers a mechanism to reason about this relationship. As existing estimators for epiplexity only operate on data already seen during training, we show how to operationalize epiplexity as an online training signal by greedily maximizing its stepwise gain in two settings. For data selection, we fit scaling laws to the training loss curves of natural data domains to predict the expected epiplexity gain as a function of training tokens, and use this signal to adaptively determine the sampling weights over domains during training. For synthetic data generation, where no domain structure exists, we reward a generator with the change in epiplexity of a learner's synthetic training data and use REINFORCE policy gradients to guide the generator toward an epiplexity-maximizing distribution. In both cases, we find higher epiplexity predicts improved downstream performance on zero-shot and fine-tuning tasks, supporting the hypothesis that data rich in structural information yield representations that better transfer across domains.

0.24

Rural Readiness: Domain Generalization with Adversarially Chosen Domains

cs.LG stat.ML ·2026-10-29 ·Cynthia Dwork, Andisheh Ghasemi, Lunjia Hu
similarity 0.68
Abstract

Predictive models trained at well-resourced data-rich institutions often fail when deployed in new populations. Motivated by the goal of building clinical diagnosis and decision-making algorithms for data-scarce rural populations using the general knowledge learned from data-rich hospitals, we formulate the fundamental question of \emph{domain generalization with adversarially chosen domains}, which asks a learner to perform on any unseen target domain nearly as well as the worst hypothesis consistent with the evidence from the observed source domains. Assuming only that the hypothesis class contains a "universal" predictor with small error on all $k$ source domains, we characterize the sample complexity of this objective up to logarithmic factors. Letting $d$ denote the VC dimension of the hypothesis class, we find, somewhat surprisingly, that the sample complexity reduces significantly from $Ω(dk)$ to $O(d)$ under a small relaxation of the learning goal in which, roughly speaking, we allow the learned model to compete with hypotheses that perform well on 99% instead of 100% of the source domains. By applying this insight to the meta-distributional setting, in which source domains are selected according to a distribution on distributions, we obtain a corresponding improvement over known sample complexity upper bounds. We also study the effect of data access to the target domain and show that a small labeled sample from the target domain does not improve the worst-case sample complexity on the source domains.

0.20

Formalizing the Intrinsic Dimension of Objective Landscapes by a Generalized Notion of Co-dimension

cs.LG stat.MLmath.MG ·2026-10-29 ·Ernesto Araya, Gitta Kutyniok, Weilin Li, Johannes Maly, Manjot Singh
similarity 0.66
Abstract

In this work, we formalize the concept of intrinsic dimension of objective landscapes introduced in Li et al. (2018), which measures the structural complexity of learning problems by training along randomly generated subspaces. We define the intrinsic dimension of a set $Θ\subset\mathbb{R}^p$ as the minimal dimension $d_{\mathrm{int}}(Θ)$ such that a random plane of dimension $d_{\mathrm{int}}(Θ)$ in $\mathbb{R}^p$ intersects $Θ$ with probability one. We show that it is a generalized notion of co-dimension that depends on the global geometry of $Θ$. We study mathematical properties of the intrinsic dimension and develop techniques to estimate the intrinsic dimension of sets $Θ$ that arise in learning problems. More specifically, we derive upper and/or lower bounds where $Θ$ is the set of optimal parameters in student-teacher settings with shallow and deep ReLU networks, including finite and infinite sample cases, and with and without regularization. We discuss how our theory leads to novel types of generalization bounds, thereby showing that the intrinsic dimension is a measure of learning complexity. Our results connect techniques from seemingly different areas of machine learning research such as classification of symmetries of ReLU networks and stochastic geometry.

0.15

Quantitative Generalization Bounds for Multi-Layer Transformers: A Few Long Strings can Beat Many Short Ones

cs.LG cs.AIcs.CL ·2026-10-26 ·Marius Henry, Michael Rizvi-Martel, Michael Hahn
similarity 0.64
Abstract · Fix of a formatting issue of the abstract

Transformer-based language models exhibit an astonishing capacity to generalize to longer and more difficult problem instances than those seen in training. However, theoretical understanding of this phenomenon still lags behind. Unlike most machine learning models, the generalisation abilities of transformers inherently require considering two axes. On one hand, one must examine in-distribution statistical generalisation, which concerns the ability of a model to broaden a function from training samples to novel samples of the same distribution. On the other hand, given the sequential nature of language data, one must also consider length generalisation, which reflects whether a model trained on inputs of a given length can extrapolate to longer ones. These two notions have mostly been studied separately, leaving open how they interact. In this work, we give a joint treatment of both axes for fixed-precision transformers. We give generalisation guarantees in terms of the parameter sizes of the involved models, as well as the quantization space and the alphabet size that supply the sequences. Finally, we illustrate how the requirements in the sample count and training length trade off. In particular, we find that increasing training length can be exponentially more efficient than increasing the sample size. Experiments support predictions of the theory.

0.15

Language Models Can Benefit from Domain-Specific Inductive Biases

cs.LG ·2026-11-02 ·Damien Teney, Liangze Jiang, Zachary Shinnick, Hemanth Saratchandran, Simon Lucey
published similarity 0.63
Abstract · 40th Conference on Neural Information Processing Systems (NeurIPS 2026). Position Paper Track

Language models are typically trained with a single choice of architecture on diverse domains and data sources. Modern transformers have been extensively refined for such general-purpose learning, but are they equally effective across different subsets of the pretraining data? We investigate this question by training small language models from scratch on representative subsets of pretraining data such as web text, code, and mathematics. We introduce variants of transformers in which standard activation functions are replaced with learned splines tuned on specific datasets, providing a simple way to modify their inductive biases. Using a mix-and-match of architectures and datasets, we evaluate cross-domain transfer, i.e. how well does an architecture tuned for one domain perform on data from another? We find that the tuned transformer variants improve training efficiency or generalization on all seven of our tested datasets, but the gains are often domain-specific. For example, architectures tuned on a natural language dataset such as FineWeb perform well on TinyStories, whereas those tuned on mathematics perform poorly on natural language. We identify several mechanisms underlying these improvements, including wider loss basins and more abundant "lottery tickets". Our results show that different subsets of pretraining data can benefit from different learning mechanisms, highlighting a limitation of the prevailing trend towards a small set of general-purpose architectures and optimizers. This points to an opportunity to improve data efficiency by developing domain-specific learning strategies that retain the ability to train general-purpose models.

0.22