math.STJul 8, 2026

Any-Dimensional Learning by Sampling

Authors: Eitan Levin, Venkat Chandrasekaran

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.

Explore similar work

CardsList
May 22, 2026cs.LG

Any-Dimensional Invariant Universality

Several machine learning models are defined for inputs of any size, such as graphs with different numbers of nodes and point clouds containing varying numbers of points. The universality properties of such any-dimensional models remain poorly understood, as universality is traditionally studied for models accepting inputs of a fixed size, defined on a compact subset of their domain. In sharp contrast, any-dimensional models can be viewed as sequences of functions defined on growing-sized inputs, and it is not clear in which sense they can be universal. We develop a systematic approach to establish any-dimensional universality, by identifying any-dimensional functions with a unique function taking inputs in a suitable infinite-dimensional limit space containing inputs of all finite sizes as well as their limits. Using the symmetries of these inputs and relations between inputs of different sizes, we show that this limit space admits a natural topology with rich families of compact sets on which any-dimensional universality can be established. We illustrate our approach by showing that several existing architectures fail to be universal, and we propose simple modifications that restore universality.
Shengtai Yao, Eitan Levin, Mateo Díaz
UniversalMetric SpacesMachine LearningLarge Output SpacesFiniteLatent Space+1
AskPDF
May 19, 2026cs.LG

Less Data, Faster Training: repeating smaller datasets speeds up learning via sampling biases

This work investigates the ``small-vs-large gap'', where repeating on fewer samples can lead to compute saving during training compared to using a larger dataset. This is observed across algorithmic tasks, architectures and optimizers and cannot be explained using prior theory. We argue that the speedup comes from appropriate layer-wise growth enabled by sampling biases, which is more pronounced when the dataset size is smaller. We provide both theoretical analysis and empirical evidence from various interventions. Our results suggest that using a smaller dataset with more repetitions is not just a fallback strategy under data scarcity, but can be proactively leveraged as a favorable inductive biases for optimization, particularly in reasoning tasks.
Jingwen Liu, Ezra Edelman, Surbhi Goel +1
Table Reasoning DatasetsInductive BiasBenchmark DatasetsData ScarcityBias Detection and MitigationC-Gap
AskPDF
May 22, 2026cs.LG

Optimal Dimension-Free Sampling for Regularized Classification

We prove optimal sampling bounds achieving (1±ε)(1\pm\varepsilon)-relative error for a broad class of Lipschitz continuous classification loss functions under various regularization terms. This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples. In particular, we prove k2/ε2k^2/\varepsilon^2 upper and lower bounds for ∥⋅∥2/k\|\cdot\|_2/k regularization, and k/ε2k/\varepsilon^2 upper and lower bounds for ∥⋅∥1/k\|\cdot\|_1/k regularization. For ∥⋅∥22/k\|\cdot\|_2^2/k regularization, the sampling complexity depends mainly on a bounded derivative property: if ∣g′(x)∣≤g(x)|g'(x)|\leq g(x), and g(0)>0g(0)>0, and gg is monotonic or convex, then it admits linear in kk sampling complexity; otherwise the general bound is k2/ε2k^2/\varepsilon^2. However, if g(0)=0g(0)=0, our results indicate that no dimension-free bounds are possible, and even sublinear bounds are ruled out. All upper bounds are complemented by matching lower bounds up to polylogarithmic terms. Moreover, our work relies conceptually and algorithmically on simple uniform or (squared) norm sampling and hereby improves over recent cubic k3/ε2k^3/\varepsilon^2 sensitivity sampling bounds of (Alishahi and Phillips, ICML'24). This is achieved by refined arguments involving higher moment bounds and empirical process analyses to avoid overcounting that appears in the de-facto standard VC-dimension and sensitivity framework.
Meysam Alishahi, Alexander Munteanu, Simon Omlor +1
Optimal Sample ComplexityLipschitz ConstantRegularization MethodsLoss FunctionIntrinsic Dimensionality
AskPDF