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

Behrooz Tahmasebi; Melanie Weber

cs.LGOct 13, 2026

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

Authors: Behrooz Tahmasebi, Melanie Weber

Organizations: Harvard John A. Paulson School of Engineering and Applied Sciences (SEAS), Harvard University, Cambridge, MA 02138, USA

Abstract

Modern machine learning models increasingly operate on variable-size structured data, such as sets and graphs. A central requirement is 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.

Figures & tables

Source decay	In-domain error	Size-generalization error
Polynomial	$n^{-\Theta(1)}$	$(\log n)^{-\Theta(1)}$
Exponential	$n^{-\Theta(1)}$	$n^{-\Theta(1)}$

Table 1: The statistical cost of size generalization.

Source decay	In-domain	Sets	Graphs
Polynomial, $k^{-\tau}$	Sets: $n^{-\tau/(\tau+rd)}$ Graphs: $n^{-\tau/(\tau+rd^{2})}$	$(\log n)^{-\tau(r+1)/r}$	$(\log n/\log\log n)^{-\tau}$
Exponential, $e^{-ak^{\nu}}$	Both: $n^{-1+o(1)}$	$n^{-1+o(1)}$ if $\nu>\frac{r}{r+1}$	$n^{-1+o(1)}$ if $\nu>1$

Table 2: Minimax-optimal in-domain and dimension-free size-generalization rates.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 1 — Figure 1: Two mechanisms governing transfer across graph sizes. (a) Transfer from 10-node Erdős–Rényi graphs: normalized invariant moments transfer directly, whereas labeled triangle features require explicit subgraph averaging. (b) Exact equivariant transfer from 10-node weighted graphs using size-normalized features: curves show mean relative MSE over ten repetitions, with 95% confidence intervals. Fast coefficient decay yields uniformly smaller truncation error.

Sample Complexity

Sample complexity studies how many data points, queries, or observations are needed to learn, estimate, test, or sample to a target accuracy.

See all 102 papers

Jul 8, 2026

Any-Dimensional Learning by Sampling

Many machine learning models are defined for inputs of different sizes, such as point clouds containing different numbers of points, sequences of tokens of different lengths, and graphs on different numbers of nodes. Such models are trained on finitely many examples of necessarily limited sizes. How well do these models generalize from inputs of small size to larger inputs of size not seen during training? Furthermore, evaluating such models on large inputs is often expensive. How can we sketch large inputs to obtain smaller ones on which the model takes similar values? At the heart of both questions is the need to compare inputs of different sizes and to approximate large inputs by small ones. We present a unified approach to address these questions by using random sampling maps to compare inputs of different sizes. The sampling maps we consider are generalizations of sampling with replacement, random binning, and species sampling. We characterize the application domains in which each type of sampling is appropriate in terms of the symmetries and relations between problem instances of different sizes in the domain. Our framework yields explicit generalization and sketching rates for function classes continuous with respect to a chosen notion of sampling, encompassing large families of functions defined on sequences, graphs, and tensors of different sizes. Specific examples include moment polynomials on measures, homomorphism densities and numbers of graphs, permutation-invariant transformers, and graph neural networks.

Eitan Levin, Venkat Chandrasekaran

Department of Statistics University of Chicago Chicago, IL 60637 · Department of Computing and Mathematical Sciences Department of Electrical Engineering California Institute of Technology Pasadena, CA 91125

Randomized Sketching Generalization Bounds

Ask PDF

May 19, 2026

Sample Complexity of Transfer Learning: An Optimal Transport Approach

Transfer learning is an essential technique for many machine learning/AI models of complex structures such as large language models and generative AI. The essence of transfer learning is to leverage knowledge from resolved source tasks for a new target task, especially when the sample size

m

of the training data for the latter is low. In this work, we rigorously analyze the potential benefit of transfer learning in terms of sample efficiency. Specifically, taking an optimal transport viewpoint of transfer learning, we find that when the data dimension

d

is higher than

3

, the sample complexity for transfer learning is

O(m^{-(α+1)/d})

, with

α

indicating the smoothness of the data distribution, as opposed to the

O(m^{-p/d})

sample complexity for direct learning with

p

indicating the smoothness of the optimal target model. Our finding theoretically supports a better sample efficiency for transfer learning, when the target task is optimizing over a family of not-so-smooth models (i.e., highly complex networks with the possible use of non-smooth activation functions). Using image classification as an example, we numerically demonstrate the sample efficiency for transfer learning, that is, in the data hungry regime, the model performance can be significantly improved by transfer learning.

Haoyang Cao, Xin Guo, Wenpin Tang +1

Department of Applied Mathematics and Statistics, John Hopkins University, Baltimore, MD, USA · Department of Industrial Engineering and Operations Research, University of California, Berkeley, CA, USA · Department of Industrial Engineering and Operations Research, Columbia University, New York, NY, USA +1

Sample Complexity Transfer Learning Statistical Learning Theory Data-Efficient Learning

Ask PDF

May 13, 2026

Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale

We study the optimal scale at which real-valued function classes exhibit uniform convergence and learnability. Our main result establishes a scale-sensitive generalization of the fundamental theorem of PAC learning: for every bounded real-valued class and every

γ>0

, uniform convergence at scale

γ

, agnostic learnability at scale

γ/2

, and finiteness of the fat-shattering dimension at every scale

γ'>γ

are equivalent. This resolves a question by Anthony and Bartlett (Cambridge Univ. Press 1999) on the precise scales governing learnability, refuting a conjecture attributed there to Phil Long that a multiplicative 2-factor gap is unavoidable, and improves the upper bounds of Bartlett and Long (JCSS 1998), which incur such a loss. The key technical ingredient is a direct bound on empirical

\ell_\infty

covering numbers, avoiding the standard detour through packing numbers. As a consequence, we obtain sharp asymptotic metric-entropy bounds in terms of the fat-shattering scale

γ

: an

O(\log^2 n)

bound holds already at scale

γ/2

, while an

O(\log n)

bound holds at scale

2γ

. We further show that the

O(\log^2 n)

bound is sometimes tight. These results resolve open questions by Alon et al. (JACM 1997) and Rudelson and Vershynin (Ann. of Math. 2006). As an application, we establish a sharp dichotomy for bounded integral probability metrics: every such IPM is either estimable or cannot be weakly evaluated within any multiplicative factor

c<3

, while

3

-weak evaluability always holds, resolving an open question from Aiyer et al. (ICML 2026). We also highlight several open questions on quantitative sample complexity and evaluability.

Shashaank Aiyer, Yishay Mansour, Shay Moran +2

University of Maryland · Tel Aviv University and Google Research · Technion and Google Research +1

Agnostic Learning Statistical Learning Theory Integral Probability Metrics Generalization Bounds

Ask PDF

Abstract

Sample Complexity

Explore similar work

Any-Dimensional Learning by Sampling

Sample Complexity of Transfer Learning: An Optimal Transport Approach

Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale