The article presents a unified approach to address generalization from small to large inputs and the sketching of large inputs using random sampling maps. These maps generalize sampling with replacement, random binning, and species sampling to compare inputs of varying sizes.
- The framework characterizes application domains for each sampling type based on symmetries and relations between problem instances.
- It yields explicit generalization and sketching rates for function classes continuous with respect to a chosen notion of sampling.
- Specific examples include moment polynomials on measures, homomorphism densities, permutation-invariant transformers, and graph neural networks.
The authors consider this important because it provides theoretical bounds for models defined on inputs of different sizes, such as point clouds and graphs.