---
title: "Any-Dimensional Learning by Sampling: A Unified Generalization Theory for Varying-Size Inputs"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2607.07680v1"
permalink: "https://feed.astralor.com/items/itm_0d94e5621a5b09c9a9af8372"
published: "2026-07-08T17:38:29.000Z"
score: 74
channel: "tech"
tags: ["Transformer","Any-Dimensional Learning","Graph Neural Network","Generalization Theory","Sketching","Random Sampling"]
---

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

## AI commentary

> This paper offers a powerful theoretical toolkit for researchers studying generalization across input sizes, especially those working on graph neural networks, point clouds, and sequence modeling. It unifies disparate techniques like random downsampling and binning under a mathematical framework with error bounds, which is valuable for understanding model behavior and designing more efficient inference strategies.

## At a glance

This paper presents a unified framework using random sampling maps to compare inputs of different sizes (e.g., point clouds, sequences, graphs), addressing two key questions: how models trained on small inputs generalize to larger unseen inputs, and how to sketch large inputs to obtain approximations. The authors systematically analyze three sampling types (sampling with replacement, random binning, species sampling) and characterize the applicable function classes based on symmetries and relations between problem instances. The framework yields explicit generalization and sketching rates for function classes continuous with respect to the chosen sampling notion, covering moment polynomials, homomorphism densities, permutation-invariant transformers, and graph neural networks.

## Key points

- Proposes a unified method using random sampling maps to compare inputs of varying sizes
- Classifies three sampling types with applicability conditions
- Derives explicit generalization and sketching rates
- Theory covers diverse ML models on sequences, graphs, and tensors

## Full text

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.

---

Verify against the original before citing; curated by Astral Feed: https://feed.astralor.com/items/itm_0d94e5621a5b09c9a9af8372