aiqbench analysis
This research introduces a unified framework using random sampling maps to address generalization and computational efficiency for machine learning models handling variable-sized inputs like graphs and sequences. By characterizing how different sampling techniques relate to problem symmetries, the study provides explicit rates for approximating large datasets with smaller sketches without losing model fidelity. This advancement is particularly relevant for scaling graph neural networks and permutation-invariant transformers where evaluating full inputs is prohibitively expensive.
Any-Dimensional Learning by Sampling
arXiv:2607.07680v2 Announce Type: replace-cross Abstract: 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.
Abstract: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.
Statistics Theory (math.ST); Machine Learning (cs.LG); Probability (math.PR)
arXiv:2607.07680 [math.ST]
(or arXiv:2607.07680v2 [math.ST] for this version)
https://doi.org/10.48550/arXiv.2607.07680 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 330 words
Related coverage
Hybrid quantum-neural network beats classical machine learning
Quantum Zeitgeist · Aug 17, 2026
ADSEL: Adaptive Dual Self-Expression Learning for EEG Feature Selection via Incomplete Multi-Dimensional Emotion Labels
arXiv · Sep 22, 2026
Representation Learning for Sample-Efficient CATE Estimation by Leveraging Multiple Outcomes
arXiv · Sep 9, 2026
Handling Imbalanced Classification: What Works Better Than SMOTE
Analytics Vidhya · Jul 12, 2026