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.