Search papers, labs, and topics across Lattice.
This paper introduces a unified framework leveraging random sampling maps to address the challenges of generalizing machine learning models across inputs of varying sizes, such as point clouds, sequences, and graphs. By characterizing the appropriate sampling methods based on the underlying symmetries of the problem domains, the authors derive explicit rates for generalization and sketching, applicable to a wide range of function classes. The key result demonstrates that this approach not only facilitates effective comparisons between inputs of different sizes but also enables efficient approximations of large inputs through smaller sketches, significantly impacting model evaluation and training efficiency.
Random sampling can bridge the gap between small and large input sizes, revealing how models generalize across dimensions with surprising efficiency.
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.
