Any-Dimensional Learning by Sampling: A Unified Generalization Theory for Varying-Size Inputs

Many machine learning models handle inputs of varying sizes, such as point clouds with different numbers of points, sequences of different lengths, and graphs with different numbers of nodes. These models are typically trained on finite-size samples but may encounter larger inputs during deployment. How can we guarantee generalization? Moreover, inference on large inputs is often computationally expensive—can we sketch (downsample) the input while preserving the model output? This paper unifies these two questions as a problem of comparing inputs of different sizes and proposes using random sampling maps as a comparison mechanism. The authors consider three types of sampling: sampling with replacement (preserving order), random binning (aggregation within bins), and species sampling (for rare categories). For each type, they characterize the class of functions that are 'sampling-continuous' based on symmetries and relations between problem instances. They prove that for such function classes, random sampling yields controlled generalization and sketching errors. Specific examples include moment polynomials, graph homomorphism densities (closely related to graph neural networks), permutation-invariant transformers, and various graph neural networks. The framework offers theoretical guidance for practical applications, such as selecting optimal sampling strategies to balance accuracy and computational cost.