arXiv Machine Learning
Oct 15

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

The paper introduces a statistical learning theory for size generalization in models that handle variable-size structured data such as sets and graphs. It proves an exponential separation in sample complexity: polynomial in-domain learning yields only logarithmic decay in size-generalization error, while an exponential source condition restores polynomial decay. These results provide dimension‑free scaling laws and optimal minimax bounds for transferring learning across input sizes.

By Behrooz Tahmasebi, Melanie Weber