这篇论文提出了一个统一的采样框架，帮你理解模型在不同大小输入上的泛化能力，还能把大输入压缩成小输入来节省计算，例子涵盖Transformer和图神经网络。
该论文提出使用随机采样映射（如替换采样、随机分箱、物种采样）来比较不同大小的输入（如点云点数量不同、序列token长度不同、图节点数不同）。通过分析领域内问题实例的对称性，确定了每种采样类型的适用场景。框架给出了函数类连续性的显式泛化率和草图化率，涵盖序列、图和张量上的函数族。具体例子包括矩多项式、同态密度、置换不变Transformer和图神经网络。
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.