Any-Dimensional Learning by Sampling Eitan Levin† and Venkat Chandrasekaran‡ ∗ †
arXiv:2607.07680v1 [math.ST] 8 Jul 2026
‡
Department of Statistics University of Chicago Chicago, IL 60637
Department of Computing and Mathematical Sciences Department of Electrical Engineering California Institute of Technology Pasadena, CA 91125 July 9, 2026
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. Keywords. de Finetti, distribution shift, exchangeability, generalization, partition models, random binning, sketching, species sampling
1
Introduction
Out-of-sample generalization is a core challenge in machine learning, particularly when there are qualitative differences between the training and test data. An important source for such differences is the dimensionality of the data, which can vary from training to test time in applications involving point clouds containing different numbers of points, graphs on different numbers of vertices, and sequences of tokens of different lengths. In these and other domains, we are given training data consisting of inputs of bounded size, and we aim to learn a function that can be applied at test time to inputs of arbitrary size. In particular, such a learned function must exhibit any-dimensional generalization so that it performs well on inputs of sizes that are not seen during training. ∗ Emails: [email protected], [email protected]
1
A related problem is one in which we are given a function that is well-defined on inputs of any size, and we wish to evaluate the function on a high-dimensional input. When such a high-dimensional function evaluation is expensive, we seek to suitably subsample, or sketch, the input to obtain a low-dimensional object on which the function can be evaluated efficiently and whose value is close to that of the original input. We call the problem of producing such low-dimensional sketches any-dimensional sketching, as our goal is to produce small approximations of arbitrarily-sized inputs. Our objective in this paper is to show that the above two problems of any-dimensional generalization and sketching are closely related to each other, and to develop a systematic approach to tackle them. The fundamental challenge in addressing both of these questions is that of comparing inputs of different sizes. In other words, in what sense can a small object be an approximation to a large one? Broadly, we develop a sampling-based approach to represent and compare objects of different sizes. We associate to an object of arbitrary size a sequence of random variables representing increasingly-fine subsamples of the object. By defining an appropriate metric over such sequences, we then obtain a convenient method for comparing objects of different sizes. Building on this sampling-based approach, we identify classes of any-dimensional functions that can be learned from, or approximated on, low-dimensional inputs, and we quantify how small this dimensionality needs to be for a given accuracy. We also discuss applications to a number of domains of contemporary interest. We next outline these contributions in more detail.
1.1
Our Contributions
Formalizing Any-Dimensional Learning (Section 2.1) To frame our discussion concretely, let (Vn ) be a sequence of vector spaces, with the index n specifying object size, e.g., vectors of length n, adjacency matrices of graphs on n vertices, and so on. We consider the following two running examples, although our framework also encompasses many others: • Sequences of features or tokens, represented as n vectors in Rd . Here we set Vn = Rd×n for a fixed d ∈ N and growing n. • Weighted and directed graphs on n vertices, represented by their adjacency matrices. Here we set Vn = Rn×n and let n grow. In many applications, it is often the case that the objects of interest belong to some proper subset Ωn ⊆ Vn ; for instance, an unweighted graph is precisely one whose adjacency matrix belongs to Ωn = {0, 1}n×n . In the F sequel, F we will see that various structural properties of this subset, and indeed of the disjoint union Ω ⊆ n n n Vn of subsets containing objects of all possible sizes, play a central role in our framework. F In order to formulate the any-dimensional generalization F problem precisely, let Ω≤n = i≤n Ωi be the set of objects of size at most n. For two functions f, g : n Ωn → R defined on objects of all sizes, i.e., any-dimensional functions, define en (f, g) = supx∈Ω≤n |f (x) − g(x)| to be the maximum discrepancy between f and g on objects of size n, and e∞ (f, g) = supn en (f, g) to be the maximum discrepancy on objects of any size. We then investigate the following question: F Any-dimensional generalization: Under what conditions on n Ωn and on any-dimensional functions f, g : F n Ωn → R do we have that: lim en (f, g) = e∞ (f, g)? n→∞
At what rate does this limit converge? Are there hypothesis classes of any-dimensional functions over which the convergence rate is uniform? If en (f, g) converges to e∞ (f, g) as n → ∞, then we can control the error e∞ (f, g) between a function f and its estimate g on objects of arbitrarily-large size by the error en (f, g) on objects of size at most n. If we further have explicit and uniform rates of convergence over some hypothesis class, then we can obtain a priori bounds on the input size n needed to accurately approximate the target function, and precise bounds on e∞ (f, g) as a function of en (f, g). We would thereby reduce the problem of approximating a target function on arbitrary-size inputs to approximating it on inputs of a fixed (sufficiently-large) size, which belongs to the realm of traditional generalization theory on which there is a substantial literature.
2
We have stated any-dimensional generalization in terms of uniform error over inputs of each size. If instead we wish to quantify generalization in terms of the average error with respect to some data distribution, it is essential F that we formalize the idea of an any-dimensional data distribution. Merely considering distributions µ on n P Ωn is not sufficient, since any such distribution will be concentrated on bounded-dimensional inputs because n µ(Ωn ) = 1. Instead, a more appropriate notion for any-dimensional data distributions is that of a weakly-convergent sequence of distributions (µn ∈ P(Ω≤n )) supported on increasingly larger objects, as we show in Proposition 2.2. The second question we consider involves approximating the value of an any-dimensional function on a large input by its value on a small sketch of this input. F Any-dimensional sketching: Under what conditions on F n Ωn and on an any-dimensional function f : F n Ωn → R can we find a (potentially random) map Sk : n Ωn → Ωk satisfying lim e∞ (f, f ◦ Sk ) = 0 almost surely?
k→∞
At what rate does this limit converge? Are there hypothesis classes of any-dimensional functions over which the convergence rate is uniform? As with any-dimensional generalization, if we have explicit and uniform rates of convergence for the above limit over some hypothesis class, then we can provide a priori bounds on the sketch size required for a desired accuracy in evaluating a function on inputs of any size. In particular, such uniform rates would yield sketch sizes that do not depend on the ambient dimension of the object being sketched. Already at this stage, it is clear that any attempt to addressFthe above two questions would require some way to evaluate similarity between objects of different sizes in n Ωn , and for the any-dimensional functions under consideration to be well-behaved with respect to this similarity notion. Indeed, if a model performs well on large inputs of unseen size, then these inputs must in some sense be similar to smaller inputs from the training set. Similarly, if a function takes on similar values on a low-dimensional sketch of a high-dimensional object, then the object F and its sketch must be similar to each other. More precisely, we need a distance d between elements of n Ωn that allows us to quantitatively compare objects of different sizes and to consider any-dimensional F functions that are continuous in d. We show in Theorem 2.1 that precompactness of the metric space ( n Ωn , d) plays a central role in addressing the above questions. A Sampling-Based Approach for Comparing Objects of Different Sizes (Section 2.2) To address the preceding questions on any-dimensional learning and sketching, we describe a sampling-based approach to represent F and compare objects of different sizes. Specifically, we fix a collection of random sampling maps (Sk : n Vn → Vk )k∈N , and we associate to each x ∈ Vn the sequence of random variables x 7→ (Sk (x))k∈N . In words, we form random samples of the object x of increasing sizes, which we view as increasingly-fine sketches of x. Observe that this map is well-defined for inputs of any size (i.e., x ∈ Vn for any n), and its output is a sequence of random variables taking values in the vector spaces (Vk ). We then compare any two F objects x, y ∈ n Vn by comparing the distributions of their samples SF k (x) and Sk (y) of each size k. To quantify this comparison, we define the sampling metric between x, y ∈ n Vn by X dsamp (x, y) = 2−k W1 (Sk (x), Sk (y)), (1) k≥1
where W1 denotes the Wasserstein-1 distance between two distributions of random variables1 with respect to some norm on Vk , assumed to satisfy supk E∥Sk (x)∥ < ∞ for each x so that dsamp (x, y) < ∞. The coefficients 2−k were chosen for convenience, and any other summable sequence would suit. An appropriately bounded sequence (xn ) converges with respect to the sampling metric (1) if and only if the sequence of fixeddimensional samples (Sk (xn ))n converges weakly for each size k, see Proposition 2.3. We next present several illustrations of sampling maps. 1 Wasserstein distances are defined between distributions, but to avoid notational clutter, we define these distances between
random variables with the understanding that they apply to the laws of these variables.
3
Example 1.1 (Sampling columns). Suppose Vn = Rd×n for a fixed d ∈ N. Consider the map Sk which samples k columns from x = [x1 , . . . , xn ] ∈ Vn uniformly at random with replacement, i.e., sample indices iid
J1 , . . . , Jk ∼ Unif([n]) and set Sk (x) = [xJ1 , . . . , xJk ] ∈ Vk . We obtain a sampling metric (1) by using the ℓ∞ norm to define the W1 distances. Given a compact set Θ ⊆ Rd , convergence of a sequence (xn ∈ Θn ) in dsamp is equivalent to weak convergence of the uniformly random columns (S1 (xn )) because the distribution of the size-k sample is Law(Sk (x)) = Law(S1 (x))⊗k . Example 1.2 (Sampling vertices). Consider Vn = Rn×n , viewed as the space of weighted and directed graphs on n vertices. Let Sk be the map that samples k vertices with replacement and extracts the corresponding iid induced subgraph, i.e., for x ∈ Vn , we have (Sk (x))i,j = xJi ,Jj for J1 , . . . , Jk ∼ Unif([n]). Once again, we obtain a sampling metric (1) with the entrywise ℓ∞ norm defining the W1 distances. Convergence in sampling metric corresponds precisely to the dense graph limits studied in [1–4]. Example 1.3 (Random binning, hashing). Suppose Vn = Rd×n and consider the sampling map Sk that randomly assigns the n columns of x ∈ Vn into k bins and sums the columns in each bin, i.e., we sample P iid J1 , . . . , Jn ∼ Unif([k]) and set the ith column of Sk (x) ∈ Vk to (Sk (x))i = ℓ:Jℓ =i xℓ for i ∈ [k]. This random binning map, also called hashing, has found uses in machine learning as a dimensionality reduction method [5, 6] and in information theory as part of source and channel coding protocols [7]. We will consider the associated sampling metric (1) defined with the ℓ2 norm. Example 1.4 (Species sampling, random partitions). Suppose Vn = Rn . A vector x ∈ ∆n defines a random partition of [k] for each k ∈ N as follows. We view x as a distribution on indices in [n] and sample k indices I1 , . . . , Ik ∈ [n] iid from this distribution. This sample defines a partition of [k] in which i, j ∈ [k] belong to the same block if Ii = Ij , and we set the entries of Sk (x) ∈ ∆k to be the fraction of indices in [k] belonging to each block of the partition. Explicitly, we randomly order the ℓ ≤ k distinct indices {I1 , . . . , Ik } sampled in this way as t1 , . . . , tℓ , and set Sk (x)j = |{i : Ii = tj }|/k; the tj ’s are sometimes called ‘species’ [8, Chap. 7]. This sampling map extends to a general x ∈ Rn by homogeneity, so Sk (x)j = ∥x∥1 sign(xtj )Sk (|x|/∥x∥1 )j for x ̸= 0 and Sk (0) = 0. This notion of sampling and the associated random partition models have been studied extensively, see [8–11] for example. The sampling metric and associated notion of convergence have been previously widely used in the graph limits literature [12] to compare graphs of different sizes and to take their limits, as highlighted in Example 1.2. We demonstrate in this paper that the underlying idea is much more broadly relevant to comparing objects of different sizes in many other applications. In particular, we go well beyond the preceding specific illustrations by describing next a combinatorial perspective on sampling based on random maps between finite sets. This viewpoint yields three broad classes of sampling maps that represent a significant generalization of Examples 1.1-1.4. As we shall see, the sampling perspective is useful both analytically and methodologically, as it provides sketching maps with which to approximate large inputs by small ones and yields explicit rates for any-dimensional generalization and sketching. General Sampling Maps (Section 2.3) We generalize the sampling maps used in Examples 1.1-1.4 and unify their analysis by using maps between finite sets. To motivate our generalization, we note that any map f : [k] → [n] between finite sets defines a (linear) map ρ(f ) : Rd×n → Rd×k extracting the columns f (1), . . . , f (k) specified by f , or more formally [ρ(f )x]i = xf (i) for i ∈ [k] where subscripts index columns. Moreover, if we replace a fixed such map f by a uniformly random map Fn,k : [k] 7→ [n], with each Fn,k (i) drawn independently and uniformly from [n], then ρ(Fn,k ) is precisely the random map sampling k columns as in Example 1.1. Likewise, a map f : [k] → [n] acts on pairs by (i, j) 7→ (f (i), f (j)), and therefore defines a (linear) map ρ(f ) : Rn×n → Rk×k between matrices indexed by these pairs via [ρ(f )x]i,j = xf (i),f (j) for i, j ∈ [k]. Once again, applying a uniformly random map ρ(Fn,k )x recovers the vertex sampling map of Example 1.2. More generally, we consider a sequence of index sets (In ) along with actions θ(f ) : Ik → In associated to each map f : [k] → [n] between finite sets, and we assume that these actions satisfy certain compatibility conditions (see Definition 2.10). We then consider the sequence of vector spaces (Vn = RIn ) consisting of
4
vectors indexed by (In ), and associate a (linear) map ρ(f ) : Vn → Vk to each map f : [k] → [n] between finite sets given by [ρ(f )x]i = xθ(f )(i) for x ∈ Vn and i ∈ Ik . (2) Finally, we define sampling with replacement maps (Rk ) on these spaces by Rk (x) = ρ(Fn,k )x
where Fn,k : [k] → [n] is uniformly random,
(3)
and x ∈ Vn . In this manner, we generalize sampling with replacement to more complicated objects such as graph signals (by setting In = [n]2 ⊔ [n]), hypergraphs and tensors (by setting In = [n]d ), and polynomials (by setting In = [n]d /Sd to be the collection of multisets of [n] containing d elements, where Sd is the group of permutations on d letters permuting indices in a tuple). Our perspective enables a single unified analysis for general actions θ, and thereby yields rates in a broad array of applications. Our generalization of random binning also proceeds via an action of maps on index sets. Indeed, any function f : [n] → [k] can be viewed as binning n indices into k bins, and defines a P map β(f ) : Rd×n → Rd×k by binning columns in this way and summing the columns in each bin [β(f )x]i = j∈f −1 (i) xj . Applying a uniformly random map β(Fk,n ) in this way yields the random binning map of Example 1.3. More generally, we consider a sequence of index sets (In ) with action θ and associated sequence of vector spaces (Vn = RIn ) as above. We associate a (linear) map β(f ) : Vn → Vk to each map f : [n] → [k] between finite sets via X [β(f )x]i = xj for x ∈ Vn and i ∈ Ik . (4) j∈θ(f )−1 (i)
We remark that the above two maps ρ and β from (2) and (4) are adjoints of each other, in the sense that β(f ) = ρ(f )⋆ with respect to the usual inner products on RIn . Finally, we define random binning maps (Bk ) on these vector spaces by Bk (x) = β(Fk,n )x
where Fk,n : [n] → [k] is uniformly random,
(5)
and x ∈ Vn . By varying the index sets (In ), we generalize random binning to more general objects, and once again they can all be analyzed in a unified manner. For example, setting In = [n]2 recovers the random quotients of graphs studied in [13]. Lastly, we generalize the species sampling map from Example 1.4. We consider a particular class of index sets (In ) that can be derived from tuples [n]d (see Definition 2.11), and view vectors x ∈ ∆In as distributions over the index sets In . We can then repeat the construction in Example 1.4 to form more general species sampling maps (Ek ), see Section 2.3.2. Given a sequence of index sets (In ), we have defined three sampling maps on the same underlying vector spaces RIn . When is it appropriate to use a particular sampling map to compare objects of different sizes? Each of the above sampling maps induce an equivalence between different inputs, meaning there exist x ̸= y possibly of different sizes with dsamp (x, y) = 0. Therefore, a choice of sampling maps is appropriate only if pairs x, y at sampling distance zero can indeed be viewed as equivalent in the context of the given application domain. We characterize these equivalences in Section 2.3. Informally, for sampling with replacement (Rk ) as defined above, the distribution of Rk (x) is unchanged if and only if we duplicate or permute the entries of x, appropriately defined (see Propositions 2.13 and 2.14). For example, if x ∈ Rd×n and we permute the columns of x or duplicate them m times (so x 7→ x ⊗ 1⊤ m ), then the distribution of Rk (x) is unchanged for all k ∈ N. Such permutation and duplication is natural when x represents a point cloud, strategies in a symmetric game converging to a mean-field limit, or dense graphs, see Example 2.16. For random binning (Bk ) and species sampling (Ek ), the distributions of (Bk (x)) and (Ek (x)) are unchanged if and only if we zero-pad or permute the entries of x, again appropriately defined. For example, if x ∈ Rn and we append k zeros to x, then the distributions of Bk (x) and Ek (x) are unchanged for all k. Such permutation and zero-padding is natural when x represents a distribution on unlabelled items or a sparse graph, see Example 2.17.
5
Rates for Sampling with Replacement (Section 3) We derive rates for any-dimensional sketching and generalization using the sampling metric (1) defined with F respect to general sampling with replacement maps (R : V → Vk ). To state our results, we fix a k n n F sequence of compact subsets (Ωn ⊆ Vn ) such that Rk ( n Ωn ) ⊆ Ωk almost surely for all k, i.e., the subsets Ωn are closed under sampling with replacement. For example, the hypercubes Ωn = [−1, 1]n ⊆ Rn and the collection of unweighted graphs Ωn = {0, 1}n×n ⊆ Rn×n are closed under sampling with replacement. Theorem 1.5 (informal, see Theorem 3.1). We have the following rates for sampling with replacement F (Rk : n Ωn → Ωk ) acting on compact sets (Ωn ) closed under sampling. F (Any-dimensional sketching) For any function f : n Ωn → R that is L-Lipschitz in dsamp and any x ∈ F 2 −2ϵ we have n Ωn , with probability at least 1 − e r i h 1 c3 −1 1+D + Lϵ . |f (x) − f (Rn (x))| ≤ Lc1 exp − (c2 log n) n (Any-dimensional generalization) For any other L-Lipschitz function fb, we have that: h i 1 1+D e∞ (f, fb) ≤ en (f, fb) + 2Lc1 exp −(c−1 log n) . 2 The constants c1 , c2 , c3 > 0 are explicit and depend on the collection (Ωn ), and the parameter D is a ‘degree’ that quantifies the complexity of the action θ underlying the sampling maps (Rk ). The proof of these bounds relies on a concentration result in which we show that the distance dsamp (x, Rn (x)) is c/n-subgaussian, for a constant c > 0. For any-dimensional sketching, we are able to approximate the value of a Lipschitz function on an arbitrarily-large input by evaluating the function on a random sample of the input, with the size of the sketch depending only on the desired accuracy. For any-dimensional generalization, our results show that if fb ≈ f on inputs of size n, then fb ≈ f on inputs of all sizes up to a slack that decays to zero as n increases. In other words, approximating a target function on sufficiently-large input sizes guarantees a good approximation on inputs of all sizes. Moreover, Theorem 1.5 reduces the analysis of any-dimensional generalization error to generalization error on a finite-dimensional compact set, a classical problem (see [14] for example). The rates in Theorem 1.5 are clearly quite slow. On the other hand, these rates are uniform in the sense that they hold for objects of any size. Moreover, these slow uniform rates are to be expected in general. For example, when Ωn is the collection of n × n adjacency matrices of simple graphs, a rate of exp[− 12 log log n] was shown in [2, Thm 2.9] for the closely related cut metric as a consequence of Szemerédi’s regularity lemma (see [12, Exer. 10.33] for the connection between the cut and sampling metrics). Nevertheless, we can substantially improve the above uniform rates using additional structure in the function f . For example, we will see in Section 3 that many any-dimensional functions f depend on their arbitrarily-large inputs only via a fixed-dimensional random sample, i.e., f (x) depends on its input only via Law(Rk (x)) for some fixed k. We give two illustrations here of some of these improved rates in specific applications. The first pertains to polynomialsFthat are unchanged by suitably-defined duplication of the entries of their inputs. Specifically, a function p : n Vn → R is a polynomial if all the restrictions p|Vn are polynomials of some fixed degree, denoted deg(p). Corollary 1.6 (informal, F see Corollary 3.8). Suppose that (Ωn ) is a sequence of compact sets closed under sampling, and let p : n Ωn → R be a polynomial that is symmetric and unchanged by duplication. Then 2 there exist constants F c1 , c2 , c3 > 0 only depending on (Ωn ) and p such that with probability at least 1 − e−2ϵ , we have for any x ∈ n Ωn that |p(x) − p(Rn (x))| ≤
c1 deg(p)2 c2 deg(p)ϵ √ + , n n
and if pb is another such polynomial of the same degree, e∞ (p, pb) ≤ en (p, pb) + 6
c3 deg(p)2 . n
Examples of polynomials satisfying the above conditions are polynomials in moments of measures, graph homomorphism densities, and polynomial graph neural networks; see Corollary 3.8 and the discussion following it. The proof uses a result of [15] stating that such polynomials compute moments of fixed-sized samples of their inputs. We remark that the above O(n−1 ) any-dimensional generalization rates are a substantial improvement over previous rates in the literature, as the latter were proved for larger function classes and exploit less structure. For example, the framework of [16] yields the rates O(n−1/d ) for moment polynomials on Rd , and O((log n)−1/4 ) for graph homomorphism densities; see [16, Cors. F.6, G.4]. The second consequence we highlight is to sketching and generalization for transformers. Corollary 1.7 F(informal, see Corollary 3.10). Suppose Vn = Rd×n with d > 2, and Ωn = Θn for compact Θ ⊆ Rd . If T : n Vn → Rd is a permutation-invariant transformer,2 there exists an L-Lipschitz continuous 2 map T̄ : P(Θ) → Rd satisfying T (x) = T̄ (Law(R1 (x))). Consequently, with probability at least 1 − e−2ϵ we have c2 ϵ (6) |T (x) − T (Rn (x))| ≤ Lc1 √ + 1/d . n n For any other such map Ḡ : P(Θ) → Rd , we define G(x) = Ḡ(Law(R1 (x))) and obtain e∞ (T, G) ≤ en (T, G) +
2c3 L , n1/d
where en (T, G) = supx∈Θn ∥T (x)−G(x)∥∞ and e∞ (T, G) = supn en (T, G). Above, the constants c1 , c2 , c3 > 0 are explicit and depend only on (Ωn ). The proof is based on the measure-theoretic in-context mapping of [17]; see Section 3.2. We remark that evaluating T (x) exactly on an input x ∈ VN consisting of N tokens requires O(N 2 ) operations (see (22)), but evaluating it to a desired accuracy δ > 0 can be done with high probability in O(δ −2d ) time (independent of the number of tokens N ) after sampling n = O(δ −d ) columns from x uniformly at random and using (6). Rates for Random Binning and Species Sampling (Section 4) Next we present our results on any-dimensional sketching andFgeneralization using the sampling metric dsamp defined with respect to general random binning maps (Bk : n Vn → Vk ). Once again, we fix a sequence of compact subsetsF(Ωn ⊆ Vn ) closed under sampling, this time under both random binning and under species sampling so Bk ( n Ωn ) ⊆ Ωk almost surely for all k and similarly for (Ek ). Examples include the simplex Ωn = ∆n and entrywise ℓ1 balls. As in Theorem 1.5, we would like to use the maps (Bk ) for sketching high-dimensional inputs. The challenge with this approach is that the distance dsamp (x, Bn (x)) does not concentrate as well as in the case of sampling with replacement (see Example 4.1). Fortunately, our generalization of the species sampling map (Ek ) exhibits the requisite concentration, as dsamp (x, En (x)) is c/n-subgaussian for a constant c > 0 depending only on (Ωn ). Thus, species sampling furnishes the necessary sketching map. Theorem 1.8 (informal, see Theorem 4.2). We have the following results for random binning (Bk ) and species sampling (Ek ) acting on compact sets (Ωk ) closed under both sampling maps. Below, we let dsamp be the sampling metric defined by (Bk ). F (Any-dimensional sketching) For any function f : n Ωn → R that is L-Lipschitz in dsamp and any x ∈ F −2ϵ2 that n Ωn , we have with probability at least 1 − e |f (x) − f (En (x))| ≤
L(c1 + c2 ϵ) √ . n
F (Any-dimensional generalization) If fb: n Ωn → R is also L-Lipschitz in dsamp , then 2Lc1 e∞ (f, fb) ≤ en (f, fb) + √ . n 2 We assume infinite-precision self-attention and mean pooling for the last layer, see Corollary 3.10.
7
The constants c1 , c2 > 0 are explicit and depend only on the collection (Ωn ). In words, we always get n−1/2 rates for random binning, regardless of the complexity of the action β in (5). We obtain the same rates also for functions f exhibiting latent low-complexity structure. The following are some of the function classes satisfying the sketching and generalization rates of Theorem 1.8. (Polynomials) In analogy to Corollary 1.6, there is a large class of polynomial functions thatFare continuous with respect to random binning. Specifically, Theorem 4.2 applies to any polynomial p : n Vn → R that is symmetric and unchanged by zero-padding, appropriately defined (Corollary 4.6). Such polynomials include multi-symmetric functions on sequences of vectors and homomorphism numbers for graphs of arbitrary size. (Symmetric neural networks) Many permutation-invariant neural network architectures are continuous with respect to random binning, including DeepSets [18] (Corollary 4.7), PointNet [19] (Corollary 4.8), and graph neural networks [20] (Corollary 4.9), with appropriate choices of parameters and nonlinearities. Finally, we show that the topologies defined by random binning and by species sampling via the corresponding sampling metrics are closely related to each other (Proposition 4.10). See Section 4 for more details.
1.2
Related Work
There are several machine learning models that are defined for inputs of different sizes. Examples include neural networks processing sets and point clouds of different sizes [18, 19, 21], graphs of different sizes [20, 22, 23], and transformers processing sequences of tokens of any length [17, 24, 25]. Importantly, the anydimensional generalization and sketching rates of each of the above models are comparatively less studied, with the following notable exceptions. The ability of a graph neural network to generalize to graphs of different sizes has been called transferability in the literature, and has been extensively studied by considering appropriate topologies and limits on the space of graphs of all sizes, see [23, 26–28] for example. In particular, many results in this line of work exploit the continuity of appropriately-normalized graph neural networks with respect to dense graph limits, which correspond to convergence in the sampling metric (1) defined using sampling vertices with replacement as in Example 1.2, see [12, §1]. We generalize and unify many of the techniques in this literature by considering more general notions of sampling maps, which are in turn useful in a broader array of applications. There is also a literature studying the ability of transformers to generalize to inputs of different lengths, see [29–32] for example. Some of the results in this literature are negative, showing that transformers often do not generalize well to longer inputs, while others prove length generalization under specific assumptions on the transformer architecture. Our theory contributes to the latter line of work by giving explicit generalization guarantees for permutation-invariant transformers. The measure-theoretic description of attention we use for this purpose has been previously used to prove universality results for transformers [17, 33, 34], but to our knowledge our result is the first application of these ideas to length generalization. The authors of [35] study the particular case of generalization of symmetric any-dimensional polynomials fitted via least-squares to training inputs of bounded dimensions. They measure generalization using meansquared error with respect to fixed training and test sets in possibly different dimensions, and their bounds depend explicitly on these sets. In contrast, we simultaneously control the error on inputs of all possible sizes by the error in a fixed training dimension; the latter in turn can be controlled by classic results in generalization theory in a fixed dimension [14]. More broadly, our framework applies seamlessly to general classes of functions continuous with respect to sampling, which go well beyond polynomials. Transferability of graph neural networks has been extended in [16] to more general any-dimensional models, where it was defined to be continuity of the model in a certain space containing inputs of all sizes and their limits. The any-dimensional generalization and sketching problems that are the subject of our paper are neither formalized nor explicitly tackled there, and sampling maps do not play a role in the construction of their space. Nevertheless, several results in [16] do pertain to these problems and involve sampling. These include rates for any-dimensional generalization for average error with respect to specific data distributions [16, Prop. 4.2], and expected convergence rates for function values on low-dimensional samples of high-dimensional inputs [16, Prop. D.5]. Both assume access to sampling maps satisfying certain desiderata, verified case-by-case. In contrast, sampling maps are fundamental to our framework—we systematically 8
generalize several notions of sampling maps, and we prove the requisite properties pertaining to them in a unified fashion and in broader application domains. In particular, we formalize the notion of any-dimensional data distributions, and we obtain improved generalization rates with respect to them compared to [16] by exploiting sampling-specific structure in the functions; we also prove any-dimensional generalization with respect to worst-case error. Furthermore, we obtain convergence rates for function values on low-dimensional samples that hold not only in expectation but also with high probability, which is essential for deriving a practically-relevant methodology for sketching. Finally, the sketching rates we obtain for sampling with replacement generalize previous rates obtained for measures [36] (viewed as limits of point clouds) and graphons [2] (viewed as limits of dense simple undirected graphs). These sketching rates were used to test properties of large graphs in the latter literature [12]. In particular, rates of approximation for graphons by finite graphs were shown to follow from compactness of the space of graphons in [37], a connection we generalize in Theorem 2.1. Our random binning and species sampling maps generalize those studied in [13] for graphs with nonnegative edge weights summing to one. In particular, the authors of [13] show a similar n−1/2 rate as in Theorem 1.8 with respect to a different but related metric.
1.3
Notation
We denote by N the collection of strictly positive integers and by N0 = N ∪ {0}. For n ∈ N, we denote [n] = {1, . . . , n}. We denote by Sn = {π : [n] → [n] bijective} the group of permutations on n letters. If I is a finite set, we denote by RI the vector space consisting of vectors indexed by I, by ∆I the unit simplex in RI consisting of nonnegative vectors whose entries sum to 1, and by [−r, r]I for r > 0 the hypercube consisting of vectors with entries of magnitude at most r. If (Ω, d) is a pseudometric space and S ⊆ Ω, we denote by dist(x, S) = inf y∈S d(x, y) the distance of x ∈ Ω to S. The space (Ω, d) is totally bounded if all its covering numbers are finite. We denote the distribution of a random variable X by Law(X). If X and d
Y are two random variables on the same space, we write X = Y to denote equality of their distributions Law(X) = Law(Y ). We denote the collection of (Borel) probability distributions on Ω by P(Ω). If µ ∈ P(Θ), we write X ∼ µ for a random variable X to denote Law(X) = µ. If f : Ω → Ω′ is a continuous map between two topological spaces Ω and Ω′ and µ ∈ P(Ω), we denote by f µ the pushforward of µ by f . If µ ∈ P(Ω) and f : Ω → R is a measurable function, we denote by Eµ f = EX∼µ f (X) the expectation of f with respect to µ. The Wasserstein-1 distance between two measures µ, ν ∈ P(Ω) on a metric space (Ω, d) is defined by W1 (µ, ν) =
inf random (X,Y ) X∼µ,Y ∼ν
Ed(X, Y ) =
sup
|Eµ f − Eν f |,
f : Ω→R 1-Lipschitz
where the infimum is taken over couplings of µ and ν. To simplify our notation, if X and Y are random variables (not necessarily coupled) on the same space Ω, we denote W1 (X, Y ) = W1 (Law(X), Law(Y )). A sequence of measures (µn ) ⊆ P(Ω) converges weakly to µ ∈ P(Ω) if Eµn f → Eµ f for all continuous functions f : Ω → R. If Ω is a compact metric space, this is further equivalent to convergence in W1 distance. A sequence of random variables (Xn ) converges weakly if their distributions (Law(Xn )) converge weakly. If F (Ωn ) are sets, we denote their disjoint union by n Ωn = {(n, x) : x ∈ Ωn , n ∈ N}. If ∼ is an equivalence relation on a set Ω, we denote by Ω/ ∼ the quotient space consisting of equivalence classes. Any pseudometric F d on Ω induces an equivalence relation by setting x ∼ y if d(x, y) = 0. If d is a pseudometric on n Ωn , F we denote by Ω∞ = n Ωn / ∼ the quotient space under the equivalence relation induced by d, on which d defines a metric, and by Ω∞ the completion of this metric space.
2
Comparing Objects of Different Sizes
In this section, we begin our study of any-dimensional learning by formally investigating how inputs of different sizes are compared to each other. We start in Section 2.1 by stating a general equivalence between various notions of generalization and sketching across dimensions, and compactness of the metric space (for a general metric) consisting of inputs of all sizes and their limits. We then focus in Section 2.2 on the sampling metric. We describe a large and natural family of compact metric spaces that can be derived with respect to the sampling metric, and we provide a link between (random) limit objects in these metric spaces and 9
an appropriate notion of an any-dimensional data distribution. Finally, we discuss compatibility conditions between index sets that lead to general sampling maps in Section 2.3. Missing proofs in this section are given in Section 2.4.
2.1
The Role of Compactness
Given a pseudometric defined on inputs of all sizes, we prove that compactness of this metric space is equivalent to the any-dimensional generalization and sketching properties from Section 1.F While the argument is elementary, we include it here for completeness. Suppose d is a pseudometric on n Ωn , and define the equivalence relation x ∼ y if d(x, y) = 0. We allow for pseudometrics, as opposed to only metrics, because inputs of different sizes can correspond to the same object F in the context of a given application domain, see Sections 1 and 2.3. Note that d is a metric on Ω∞ = n Ωn / ∼, and we define F Ω∞ to be the completion of this metric space. Denote by F1 the collection of 1-Lipschitz functions on n Ωn , or equivalently, on Ω∞ . Theorem 2.1. Assume (Ωn , d) is totally bounded for each n. Then the following are equivalent. 1. (Ω∞ , d) is compact. 2. We have limn→∞ supx∈Ω∞ dist(x, Ω≤n ) = 0. F 3. There exist random maps Sk : n Ωn → Ω≤k for each k such that lim sup e∞ (f, f ◦ Sk ) = 0,
k→∞ f ∈F1
almost surely.
4. There exists a rate (Rn ≥ 0)n∈N with Rn → 0 such that for any f, g ∈ F1 , we have e∞ (f, g) ≤ en (f, g) + Rn . The proof of this theorem proceeds via a straightforward direct argument, which we defer to Section 2.4. The above theorem shows that a number of desirable properties are equivalent to compactness of the limit space Ω∞ with the pseudometric d. Part 2 is an any-dimensional approximation property that says that any object of any size can be approximated by objects of size n with uniform rates, which pertains to the any-dimensional sketching question. The derivation of these rates is the key step in our analyses below. Parts 3 and 4 give a positive answer to the any-dimensional sketching and generalization questions we posed in Section 1, respectively, with uniform rates over the class of 1-Lipschitz functions. We remark that part 3 can be equivalently stated in terms of deterministic maps Sk , but the above formulation more closely aligns with our any-dimensional sketching question and subsequent developments using sampling maps. As discussed in Section 1, we would also like to quantify generalization error with respect to anydimensional data distributions. Specifically, we consider average error with respect to sequences of distributions supported on inputs of growing size that converge weakly to a distribution on limit objects, as formalized by the following proposition. Below, if µ ∈ P(Ω∞ ) and f, g : Ω∞ → R we define eµ (f, g) = Eµ |f − g|. Proposition 2.2. Suppose (Ω∞ , d) is compact. For any sequence of distributions (µn ∈ P(Ω≤n )) and µ∞ ∈ P(Ω∞ ), we have µn → µ∞ weakly if and only if there exists a rate (Rn ≥ 0) with Rn ↓ 0 such that for any f, g ∈ F1 , we have eµ∞ (f, g) ≤ eµn (f, g) + Rn . Once again, the proof is direct and is given in Section 2.4. The above results are completely general, and show that any compact pseudometric between objects of different sizes enables generalization across dimensions for functions that are continuous with respect to that metric. We turn next to analyzing the sampling metric (1) in more detail, and show that it admits rich families of compact sets and a natural correspondence between limit objects and any-dimensional data distributions.
2.2
The Sampling Metric
F Fix vector spaces (Vn ) and sampling maps (Sk : n Vn → Vk ), where each Sk is viewed as a random map.3 We begin by showing that any sequence of compact sets (Ωn ⊆ Vn ) closed under these sampling maps yields a compact limiting space. 3 We can also view S as a kernel, i.e., a map k
F
n Vn → P(Vk ). The two views are equivalent by [38, Lemma 3.2(vii)].
10
Proposition 2.3. Suppose (Ωn ⊆ Vn ) is a sequence of compact sets in the usual topology such that F Sk ( n Ωn ) ⊆ Ωk almost surely. Endow each Vn with a norm such that supn supx∈Ωn ∥x∥ < ∞, and consider F the sampling metric (1) on n Ωn with W1 distances defined using the above norms. Then (Ω∞ , dsamp ) is F compact and each (Ωn , dsamp ) is totally bounded. Moreover, a sequence (xi ) ⊆ n Ωn converges in dsamp if and only if (Sk (xi ))i converges weakly for each k ∈ N. We emphasize that we are assuming above that each Ωn is compact in the usual norm topology on Vn , and conclude that each Ωn is precompact (or equivalently, totally bounded) in the topology induced Q by the sampling metric dsamp . This proposition follows from Tychonoff’s theorem applied to the product n P(Ωn ), and we give the full proof in Section 2.4. Note that this result assumes nothing about the sampling maps or how they are related to each other. We proceed to give several examples of sampling maps and sets satisfying the above hypotheses. In some of these examples the limit space Ω∞ has been characterized before and shown to be compact, while in others an explicit description may be involved and challenging to obtain, but compactness still follows from the above result. Example 2.4 (Sampling columns). Suppose Vn = Rd×n , and consider the maps Sk sampling k columns from x uniformly at random with replacement as in Example 1.1. Note that for any compact Θ ⊆ Rd , n the sequence F nof product sets Ωn = Θ is closed under sampling. As noted in Example 1.1, a sequence (xi ) ⊆ n Θ converges in dsamp if and only if (Law(S1 (xi )))i ⊆ P(Θ) converge weakly. In this case, sending x 7→ Law(S1 (x)) identifies Ω∞ with the collection of all measures in P(Θ) that have a finite support and rational weights, as these are precisely the measures of the form Law(S1 (x)) for some x ∈ Θn and some n ∈ N. We can then identify Ω∞ with all of P(Θ) endowed with the weak topology, which is indeed compact. Example 2.5 (Sampling vertices). Suppose Vn = Rn×n , viewed as the space of weighted and directed graphs, and consider the sampling map Sk drawing k vertices with replacement and extracting the corresponding induced subgraph as in Example 1.2. Then the sequence (Ωn ) of simple undirected graphs on n vertices is closed under sampling, and limits in dsamp correspond to dense graph limits [1, 2]. Such limits can be represented by a graphon, which is a symmetric measurable function W : [0, 1]2 → [0, 1] modulo an equivalence relation [1]. In this case, we can identify Ω∞ with the space of so-called step-graphons, which are (equivalence classes of ) step functions associated to finite graphs [2, §3.1]. We can then identify Ω∞ with the space of all graphons, which was shown to be compact in [37]. For more general sequences of sets (Ωn ) closed under sampling, including weighted and directed graphs, the characterization of Ω∞ becomes more involved [4], but its compactness still follows from Proposition 2.3. Example 2.6 (Random binning and species sampling). If Vn = Rn , then the sequence of simplices (Ωn = ∆n ) is closed under both random binning as in Example 1.3 and species sampling as in Example 1.4. In this case, we can view Ω∞ as the space of random exchangeable Pn probability measures on [0, 1] with finite support by associating to each x ∈ Rn the random measure i=1 xi δTi where T1 , . . . , Tn are iid uniform in [0, 1]. Then the closure Ω∞ with respect to both random binning and species sampling corresponds to the space of all random exchangeable measures4 on [0, 1] by [13, Props. 3.3, 4.1], and is compact by Proposition 2.3. (n) The sequence of ℓ1 balls (Ωn = Bℓ1 (r)) of radius r is also closed under both binning and species sampling, and its limit space can similarly be identified with a compact space of (signed) random measures. Combining Proposition 2.3 and Theorem 2.1, we conclude that if (Ωn ) is closed under sampling then there are uniform rates at which we can approximate arbitrary-sized objects by fixed-sized ones (as in Theorem 2.1(2)), and uniform any-dimensional sketching and generalization rates for Lipschitz functions measured by worst-case error (as in Theorem 2.1(3-4)). We derive explicit such rates for several notions of sampling in Sections 3 and 4 below after introducing the relevant sampling maps. We further seek uniform rates for generalization measured by average error with respect to any-dimensional data distributions. According to Proposition 2.2, such uniform rates are available for sequences of measures (µn ∈ P(Ωn )) with a weak limit µ∞ ∈ P(Ω∞ ). However, there are many sequences of measures converging to the same limit µ∞ , and we seek a ‘canonical’ choice of such a sequence to model data distributions of 4 Here we endow the space of random probability measures P(P([0, 1])) with the weak topology with respect to the weak topology on P([0, 1]). See [13] for more details.
11
growing dimensionality. Under the sampling metric, there is a natural family of such sequences of distributions. Specifically, each µ∞ ∈ P(Ω∞ ) defines a sequence of distributions of its samples (Sk (X)) where X ∼ µ∞ is independent of the sampling maps Sk . This sequence of distributions converges weakly back to µ∞ whenever the sampling maps (Sk ) yield increasingly-good approximations of their inputs, in the sense that Sk (x) → x weakly as k → ∞ for any x ∈ Ω∞ . This is the case for all the sampling maps considered in the paper. We now state theQabove result formally. For the following result, we endow P(Ω∞ ) with the weak topology, and F F endow n P(Ωn ) with the product of weak topologies. We also observe that the sampling maps (Sk : n Ωn → Ωk ) extend to Ω∞ . Indeed, if x ∈ Ω∞ then we can write x = limi xi for (xi ) ⊆ n Ωn and define Sk (x) to be the weak limit of (Sk (xi ))i for each k ∈ N. It is easy to check that this is well-defined by definition of convergence in dsamp . Proposition 2.7. In the setting of Proposition 2.3, assume that lim Edsamp (x, Sn (x)) = 0,
n→∞
for each x ∈ Ω∞ .
(7)
Then for any µ ∈ P(Ω∞ ) the sequence of measures µn = Q Law(Sn (X)) where X ∼ µ is independent of Sn converges weakly to µ. Furthermore, the map P(Ω∞ ) → n P(Ωn ) sending µ 7→ (µn = Law(Sn (X)))n∈N ,
(8)
is a linear isomorphism from P(Ω∞ ) onto its image. We give the proof of this result in Section 2.4. We characterize the image of the map (8) for our generalizations of sampling with replacement and random binning in Theorems 3.4 and 4.3 below. The above sequences (µn ) are precisely the ones we use in the sequel to quantify average generalization error in the sense of Proposition 2.2. Note that (7) is the only assumption we have made on the sampling maps (Sk ). Example 2.8. In the setting of Example 2.4 with Ωn = Θn for compact Θ ⊆ Rd , we have Ω∞ = P(Θ) so limit objects are probability distributions on Θ; hence P(Ω∞ ) corresponds to random probability measures on Θ. The map R (8) sends a distribution over measures M ∈ P(P(Θ)) to the mixture of iid distributions Law(Sn (x)) = µ⊗n dM(µ). We show in Theorem 3.1 below that (7) holds for sampling with replacement, and hence Proposition 2.7 yields a linear isomorphism between random measures and mixtures of iid distributions, recovering a part of de Finetti’s theorem. De Finetti’s theorem further states that the space of such mixtures is isomorphic to the space of infinite exchangeable arrays, a result we generalize in Theorem 3.4 to our broader notion of sampling with replacement. Remark 2.9 (Extremality). We remark that the map (8) identifies limit objects in Ω∞ with extremal sequences of measures obtained from sampling. Indeed, elements of Ω∞ are precisely the extreme points of P(Ω∞ ), which are mapped isomorphically to extreme points of the image of the map (8). As an illustration, in the setting of Example 2.8 we recover the fact that sequences of iid distributions obtained from deterministic measures on Θ are precisely the extreme points of all sequences of mixtures of iid distributions. We recover further results from the literature pertaining to such extremality in Sections 3 and 4. Having studied sampling maps in general, we now describe three specific families of sampling maps generalizing the examples in Section 1.
2.3
General Sampling Maps
In this section, we formalize our generalizations of sampling with replacement, random binning, and species sampling from Examples 1.1-1.4 in Section 1, and we explain when each sampling map is appropriate by characterizing their symmetries and relations between dimensions. We begin in Section 2.3.1 by generalizing sampling with replacement and random binning, which are dual to each other in a precise sense and can be analyzed together. Then in Section 2.3.2 we generalize species sampling.
12
2.3.1
Sampling with Replacement and Random Binning
As explained in Section 1, the key to our general perspective on sampling with replacement and random binning is an action of maps between finite sets on index sets of vectors, which we now make precise. Definition 2.10 (Compatible index sets). A (FinSet-)compatible sequence of index sets is a sequence of finite sets (In ) together with maps θ(fn,k ) : Ik → In associated to each fn,k : [k] → [n] which satisfies (i) θ(id[n] ) = idIn ; and (ii) θ(f1 ◦ f2 ) = θ(f1 ) ◦ θ(f2 ) whenever the composition is well-defined. The collection of maps θ = {θ(fn,k ) : fn,k : [k] → [n]} is called an action.5 As a consequence of Definition 2.10, if n ≤ N and ϕ : [n] → [N ] is an injection, then θ(ϕ) : In → IN is an injection as well. Indeed, there is a surjection ψ : [N ] → [n] satisfying ψ ◦ ϕ = id[n] , in which case θ(ψ)◦θ(ϕ) = idIn so θ(ϕ) is injective. Likewise, if ψ : [N ] → [n] is surjective then θ(ψ) : IN → In is surjective. Examples of such compatible sequences include In = [d] × [n] with action θ(f )(i, j) = (i, f (j)), tuples In = [n]d with action θ(f )(i1 , . . . , id ) = (f (i1 ), . . . , f (id )), and multisets In = [n]d /Sd , viewed as the set of orbits under permutations of the d indices in each tuple of [n]d , with the same action. More generally, standard operations on sets can be applied to create new compatible sequences from previous ones. For example, if {(In ), θI } and {(Jn ), θJ } are two compatible sequences, then so are {(In ⊔ Jn ), θI ⊔ θJ } and {(In × Jn ), θI × θJ }. All of the compatible sequences of index sets in this paper can be derived by applying such standard operations to the basic sequence (In = [n]). For compatible sequences obtained in this manner, we quantify the complexity of the sequence using the following notion of a ‘degree’. This degree appears explicitly in the sequel in our rates for any-dimensional sketching and generalization. Definition 2.11 (Degree of compatible index sets). Consider a compatible sequence (In ) of the form In = FM dm /Hm , where Hm ⊆ Sdm is a subgroup of permutations acting by permuting the multi-indices in m=1 [n] dm [n] . The degree of such a compatible sequence is given by D = maxm dm .6 Fd As illustrations, the degree of In = [d]×[n] = i=1 [n] is one, while the degrees of In = [n]2 , In = [n]2 ⊔[n], and In = [n]2 /S2 are all two. As discussed in Section 1, we associate to each compatible sequence (In ) a sequence of vector spaces (Vn = RIn ), and let maps between finite sets act on these vector spaces via the maps ρ and β given by (2) and (4), respectively. The maps ρ and β in turn yield generalizations of sampling with replacement (Rk ) and random binning (Bk ) in (3) and (5), respectively. Example 2.12 (Vector spaces from index sets). The following are examples of vector spaces obtained from compatible sequences. (Sequences) When In = [d] × [n], we have Vn = Rd×n whose elements we view as sequences of n vectors in Rd . In this case, if f : [m] → [n] then ρ(f ) : Vn → Vm extracts the m columns f (1), . . . , f (m), while β(f ) : Vm → Vn bins m columns into n bins f −1 (1), . . . , f −1 (n). The map Rk samples k columns with replacement as in Example 1.1, while Bk randomly bins the columns into k bins and sums all columns in each bin as in Example 1.3. (Graphs) When In = [n]2 , we have Vn = Rn×n whose elements we view as adjacency matrices of (weighted, directed) graphs on n vertices, and when In = [n]2 /S2 , we have Vn = {X ∈ Rn×n : X ⊤ = X} whose elements we view as undirected graphs on n vertices. In either case, if f : [m] → [n] then ρ(f ) extracts the induced subgraph on the m vertices f (1), . . . , f (m) while β(f ) forms the quotient graph defined by binning m vertices into n bins f −1 (1), . . . , f −1 (n), given by X (β(f )X)i,j = Xk,ℓ . k∈f −1 (i) ℓ∈f −1 (j)
The map Rk extracts the induced subgraph on k vertices sampled with replacement as in Example 1.2, while Bk forms the quotient graph defined by randomly binning vertices into k bins as in [13]. 5 In the language of category theory, this is a functor from the category FinSet of finite sets to itself. 6 Our notion of degree is closely related to the degree of a polynomial functor [39].
13
(Graph signals) When In = [n]2 ⊔ ([n] × [d]), we have Vn = Rn×n ⊕ Rn×d whose elements we view as pairs (G, X) of a graph G on n vertices and a graph signal X assigning d-dimensional features to each vertex [40]. In this case, if f : [m] → [n] then ρ(f )(G, X) = (ρ(f )G, ρ(f )X) extracts the induced subgraph on the m vertices f (1), . . . , f (m) along with their corresponding features, while β(f )(G, X) = (β(f )G, β(f )X) forms the quotient graph defined by binning m vertices into n bins f −1 (1), . . . , f −1 (n) and sums the features of vertices in the same bin. The map Rk samples k vertices with replacement along with their corresponding features, while Bk randomly bins the vertices into k bins, forms the quotient graph, and sums all features of vertices in the same bin. When In = [n]d and [n]d /Sd , the above examples generalize to directed and undirected hypergraphs. Note that we have two sampling maps (Rk ) and (Bk ) defined on the same sequences of vector spaces. We explain in Examples 2.16 and 2.17 when each of these sampling maps is appropriate. We remark that the actions ρ and β from (2) and (4), respectively, respect compositions of maps between finite sets. Specifically, we have ρ(f1 ◦ f2 ) = ρ(f2 ) ◦ ρ(f1 ) while β(f1 ◦ f2 ) = β(f1 ) ◦ β(f2 ) whenever the composition f1 ◦ f2 is well-defined, so ρ reverses the order of compositions while β preserves it.7 We will exploit this compositionality in what follows. When is each sampling map appropriate? As discussed in Section 1, the sampling maps (Rk ) and (Bk ) induce equivalence relations between distinct objects, meaning that dsamp (x, y) = 0 for x ̸= y when dsamp is defined using either choice of sampling maps. Importantly, we will see that distinct objects of the same size and also of different sizes can be equivalent under dsamp . We characterize the equivalences induced by sampling with replacement and random binning, and discuss some of the application domains in which these equivalences are natural. For objects of the same size, equivalences arise from permutation symmetry. To see this symmetry, observe that if π : [n] → [n] is a permutation (i.e., a bijection), then π defines a bijection from In to itself via θ, and two isomorphisms of Vn to itself via ρ and β. These two actions of permutations on Vn define representations of the group Sn on Vn ; moreover, the actions are dual to each other and the associated representations are isomorphic. When the context is clear, we denote the action of a permutation π ∈ Sn on a vector x ∈ Vn by πx, which equals either ρ(π)x or β(π)x depending on whether (Vn ) is endowed with sampling with replacement or with random binning maps, respectively. Proposition 2.13 (Permutation symmetry). Suppose (In ) is a compatible sequence, let (Vn = RIn ) be the associated vector spaces endowed with either sampling with replacement or random binning, denoted by (Sk ). Fix x ∈ Vn . d
(Exchangeability) The distribution Law(Sk (x)) is exchangeable, meaning πk Sk (x) = Sk (x) for each πk ∈ Sk . d
(Permutation invariance) For any πn ∈ Sn , we have Sk (πn x) = Sk (x) for all k, hence dsamp (x, πn x) = 0. d
d
Proof. For any k, ℓ ∈ N, let Fℓ,k : [k] → [ℓ] be a uniformly random map, and note that Fℓ,k ◦ πk = πℓ ◦ Fℓ,k = Fℓ,k since all three maps send each i ∈ [k] independently to a uniformly random element of [ℓ]. Applying ρ d
d
and β, we conclude that πk ◦ Sk = Sk ◦ πn = Sk for any πk ∈ Sk and πn ∈ Sn , as claimed. In addition to permutation symmetry in each fixed dimension, there are also equivalences between objects of different sizes. We characterize these equivalences using two distinguished maps between finite sets. The first set are the inclusions ιN,n : [n] ,→ [N ] defined as ιN,n (i) = i for i ∈ [n],
whenever n ≤ N.
These inclusions in turn define inclusions of In into IN via the action θ. Then the map ρ(ιN,n ) : VN → Vn acts as the orthogonal projection with respect to the usual inner product, while β(ιN,n ) : Vn → VN is an embedding by zero-padding. For example, when Vn = Rn the projection ρ(ιN,n ) extracts the first n entries 7 Such composition-reversing and composition-preserving linear actions of maps between finite sets were called FinSetop - and FinSet-representations, respectively, in [15].
14
from a length-N vector, while β(ιN,n ) zero-pads a vector of length n by N − n zeros. Similarly, when Vn = Rn×n the projection ρ(ιN,n ) extracts the induced subgraph on the first n vertices from a graph on N vertices, while the embedding β(ιN,n ) corresponds to appending N − n isolated vertices to a graph on n vertices. See Example 2.12 for these and other examples. The second distinguished set of maps are the consecutive partitions κn,N : [N ] → [n] defined by κn,N (j + (i − 1)(N/n)) = i
for i ∈ [n], j ∈ [N/n],
whenever n|N.
(9)
The corresponding linear maps ρ(κn,N ) : Vn → VN are embeddings that duplicate the entries of their inputs in a suitable sense based on the action θ. For example, we have ρ(κn,N )x = x ⊗ 1N/n when Vn = Rn , which acts by duplicating each entry of a vector x of length n the same number N/n of times. Similarly, we have n×n ρ(κn,N )X = X ⊗ 1N/n 1⊤ , which acts by duplicating each entry of a matrix X of size N/n when Vn = R n × n into a block of (N/n) × (N/n) entries. Meanwhile, the maps β(κn,N ) : VN → Vn are projections that sum consecutive blocks of coordinates. For example, the vector β(κn,N )x ∈ Rn is obtained from x ∈ RN by summing each group of consecutive N/n coordinates. Similarly, the matrix β(κn,N )X ∈ Rn×n is obtained from X ∈ RN ×N by summing the entries of each consecutive N/n × N/n block in X. See Example 2.12. We are now ready to state the relationships across dimensions satisfied by our sampling maps. Proposition 2.14 (Relations between Dimensions). Suppose (In ) is a compatible sequence, and let (Vn = RIn ) endowed with sampling with replacement (Rk ) and random binning (Bk ). d
d
(Inclusions) For any n ≤ N , we have ρ(ιN,n ) ◦ RN = Rn and Bk ◦ β(ιN,n ) = Bk for all k ∈ N. d
d
(Consecutive partitions) For any n|N , we have Rk ◦ ρ(κn,N ) = Rk for all k ∈ N and β(κn,N ) ◦ BN = Bn . d
Proof. For the first claim, fix n ≤ N , let k ∈ N be arbitrary and note that Fk,N ◦ιN,n = Fk,n since both maps send each i ∈ [n] independently to a uniformly random element of [k]. Applying ρ and β to this identity d
yields the first claim. For the second claim, note that κn,N ◦ FN,k = Fn,k since each i ∈ [k] is sent by FN,k independently to a uniformly random element of [N ], so its image is equally likely to lie in each fiber of κn,N . Applying ρ and β to this identity yields the second claim. In particular, note that for any x ∈ Vn , we have dsamp (x, ρ(κn,N )x) = 0 if dsamp is defined using (Rk ), while dsamp (x, β(ιN,n )x) = 0 for any x ∈ Vn if dsamp is defined using (Bk ). Note here that ρ(κn,N )x and β(ιN,n )x belong to VN , so the sampling distance between objects of different sizes can equal zero. Observe that the maps ιN,n are particular types of injections, while the maps κn,N are particular types of equipartitions.8 By combining Propositions 2.13 and 2.14, we are able to obtain the following consequences for all injections and equipartitions: d
ρ(ϕN,n ) ◦ RN = Rn and
d
Rk ◦ ρ(ψn,N ) = Rk
and
and
d
Bk ◦ β(ϕN,n ) = Bk d
β(ψn,N ) ◦ BN = Bn
for any injection ϕN,n : [n] → [N ],
(10)
for any equipartition ψn,N : [N ] → [n],
(11)
since we can write ϕN,n = πN ◦ ιN,n and ψn,N = κn,N ◦ πN for some permutation πN ∈ SN . As a converse to the preceding equivalences, we now prove that if dsamp (x, y) = 0 then x, y must differ by permutations and duplication for sampling with replacement, or permutations and zero-padding for random binning. Proposition 2.15. Suppose (In ) is a compatible sequence, and let (Vn = RIn ) endowed with sampling with replacement (Rk ) and random binning (Bk ). Let x ∈ Vn and y ∈ VN for n ≤ N . d
1. If Rk (x) = Rk (y) for all k ∈ N, then ρ(κN,L )y = ρ(ψn,L )x for L = lcm{n, N } and some equipartition ψn,L : [L] → [n]. d
2. If Bk (x) = Bk (y) for all k ∈ N, then y = β(ϕN,n )x for some injection ϕN,n : [n] → [N ]. 8 An equipartition is a map with equal-sized fibers.
15
The proof uses concentration results for uniformly random maps between finite sets. In particular, the proof of part 1 entails showing that a bipartite graph constructed from fibers of these random maps contains a perfect matching. We defer the full proof to Section 2.4. We now give some examples of application domains where each of the above equivalences naturally arises. Example 2.16 (Duplication). If Vn = Rd×n and x = (x1 , . . . , xn ) ∈ Vn is viewed as a point cloud in Rd , then reordering the columns or duplicating them same number of times yields an equivalent point cloud Pthe n (e.g., the corresponding discrete distribution n1 i=1 δxi is unchanged). In the context of mean-field games, we can view the columns of x as strategies played by n symmetric players, and in the mean-field limit one can show that duplicating the columns of x yields a strategy with the same payoff [41, §2]. Sampling columns with replacement would therefore be appropriate for either of these types of data. If Vn = Rn×n and we view x ∈ Vn as adjacency matrices of graphs, then simultaneously permuting the rows and columns of x corresponds to relabelling the vertices, which does not change the topology of the graph. Furthermore, duplicating each vertex of x corresponds to the so-called blowup of the graph, and these blowups have the same graph homomorphism densities [2]. Sampling vertices with replacement would therefore be appropriate when studying such structural properties of graphs. Example 2.17 (Zero-padding). If Vn = Rn and we view x ∈ Vn as a (signed) distribution on n items, then reordering the entries of x corresponds to relabelling the items, while zero-padding x amounts to viewing it as a distribution on a larger collection of items assigning zero weight to all but the original n ones. Such relabelling and zero-padding preserves many structural properties of x, such as various diversity indices measuring its dispersion [42], and hence random binning is appropriate when studying such properties. If Vn = Rn×n and we view x ∈ Vn as an adjacency matrix of a graph, then permuting and zero-padding x amounts to relabelling and adding isolated vertices to the graph, respectively. These operations again preserve many properties of the graph in question, including homomorphism numbers and various measures of centrality and clustering [13], so random binning of vertices is appropriate when studying such properties. F If f : n Vn → R is continuous with respect to the sampling metric defined by (Rk ), then f (ρ(ψn,N )x) = f (x)
for all x ∈ Vn and equipartitions ψn,N : [N ] → [n],
(12)
or equivalently, each restriction f |Vn is permutation-invariant and f is unchanged by duplication of entries defined by ρ(κn,N ). Likewise, if f is continuous with respect to the sampling metric defined by (Bk ), then f (β(ϕN,n )x) = f (x)
for all x ∈ Vn and injections ϕN,n : [n] → [N ],
(13)
or equivalently, each restriction f |Vn is permutation-invariant and f is unchanged by zero-padding defined by β(ιN,n ). Thus, functions continuous in the sampling metric defined using either choice of sampling maps respect the same equivalence relations. The converses of (12) and (13) are false in general, that is, there are functions invariant under equipartitions or injections that are not continuous in the corresponding sampling metric. For example, the norm f (x) = ∥x∥1 satisfies (13) but we show in Corollary 4.7 that it is not continuous with respect to random binning. However, the converses are true if f |Vn is a polynomial of some degree d for all n. In this case, if f is unchanged by equipartitions in the sense of (12) then there exists k ∈ N and a fixed-dimensional polynomial gk ∈ R[Vk ] such that f (x) = Egk (Rk (x)) for all x by [15, Thm. 5.2]. Similarly, if f is unchanged by zero-padding in the sense of (13) then there exists k ∈ N and gk ∈ R[Vk ] such that f (x) = Egk (Bk (x)) for all x by the same theorem. In other words, these polynomials are computing a moment of a fixed-dimensional sample of their input under either sampling with replacement or random binning. We exploit this sampling representation for polynomials in Sections 3 and 4. 2.3.2
Species Sampling
We now generalize the species sampling map from Example 1.4. Fix a compatible sequence (In ) and consider the corresponding sequence (Vn = RIn ) of vector spaces. For simplicity, suppose first that x ∈ ∆IN is a simplex element. We view such x as a probability distribution over IN , and consider forming an empirical approximation to it from n iid samples. Specifically, sampling α1 , . . . , αn ∈ IN iid according to x, we set n
1X eα . En (x) = n i=1 i 16
(14)
In general, we have En (x) ∈ VN and hence En does not reduce the dimensionality of its input. However, it does produce a sparse vector, as En (x) has at most n nonzero entries regardless of the dimensionality of x. We can exploit this sparsity by relabeling the elements of the index set to produce a low-dimensional element defining our generalization En (x) of species sampling. We next describe this construction formally. Suppose first that In = [n]D for all n and x ∈ ∆IN as above. (i)
(i)
1. Sample α1 , . . . , αn from the distribution x on IN = [N ]D . Denote αi = (j1 , . . . , jD ) for each i. Sn (i) (i) 2. Consider the subset i=1 {j1 , . . . , jD } of [N ], and denote its cardinality by k ≤ nD. Uniformly randomly enumerate the elements of this subset to obtain t1 , . . . , tk . 3. Set
En (x)ℓ1 ,...,ℓD = En (x)tℓ1 ,...,tℓD ,
(15)
if ℓ1 , . . . , ℓd ∈ [k], and En (x)ℓ1 ,...,ℓD = 0 otherwise. In words, we view the elements of [N ] as labeling distinct species, and elements of IN = [N ]D as relations between these species. The empirical sampling map En samples these relations while ‘remembering’ the species labels, while the species sampling map En ‘forgets’ the labels of the species in steps 2 and 3 of the above construction. For example, if IN = [N ] then En recovers the species sampling map of Example 1.4. Furthermore, if IN = [N ]2 and we view elements of VN = RN ×N as adjacency matrices of (weighted, directed) graphs on N vertices, then En can be viewed as sampling n edges proportionally to their edge weights, and has been studied in connection with limits of large graphs in [13]. The above construction of En (x) generalizes to any compatible sequence (In ) of finite degree and any x ∈ VN , not necessarily a simplex element, as follows. • If In = [n]D /H for some subgroup H ⊆ SD , then each αi sampled in step 1 above is the coset of a (i) (i) tuple, denoted αi = H(j1 , . . . , jD ). Because H acts by permuting indices in a tuple, step 2 is welldefined. Moreover, if (i1 , . . . , iD ) = h(j1 , . . . , jD ) for some h ∈ H then (ti1 , . . . , tiD ) = h(tj1 , . . . , tjD ). Thus, setting En (x)H(i1 ,...,iD ) = En (x)H(ti1 ,...,tiD ) is well-defined and generalizes (15) to this case. FM • If In = m=1 [n]dm /Hm is a general compatible sequence of degree D = maxm dm , then each αi sampled in step 1 above belongs to [n]dmi /Hmi for some mi . Then in step 2 we randomly enumerate the set of all indices contained in all of the αi , and in step 3 we generalize (15) as above. More (i) (i) precisely, denoting αi = Hmi (j1 , . . . , jdm ), in step 2 we randomly enumerate the elements of the i Sn (i) (i) subset i=1 {j1 , . . . , jdm } of [N ], which again contains k ≤ nD distinct elements t1 , . . . , tk . In step 3, i we then set En (x)Hm (i1 ,...,idm ) = En (x)Hm (ti1 ,...,tid ) , generalizing (15) to a general compatible sequence m of index sets. • We extend both En and En beyond simplex vectors by homogeneity. Specifically, if (In ) is a compatible sequence of finite degree and x ∈ VN , define En (x) = ∥x∥1 sign(x) ⊙ En (|x|/∥x∥1 ) where ⊙ denotes entrywise product (and En (0) = 0 by convention), and define En (x) as above. We have thus generalized species sampling toF general vectors indexed by elements of a compatible sequence of finite degree to obtain random maps (Ek : n Vn → VkD )k . When is species sampling appropriate? Species sampling induces the same equivalences between objects of different sizes as random binning, namely, equivalence under permutations and zero-padding. Proposition 2.18. Suppose (In ) is a compatible sequence of finite degree and let (Vn = RIn ) endowed with d
the species sampling maps (Ek ). We have Ek ◦ β(ϕN,n ) = Ek for any injection ϕN,n : [n] → [N ]. d
Proof. Observe that β(ϕN,n )Ek (x) = Ek (β(ϕN,n )x) as can be seen directly from (14) using the fact that ϕN,n d
is injective. The construction of Ek then shows that Ek (β(ϕN,n )x) = Ek (x), as claimed.
17
In particular, if dsamp is defined using species F sampling, then dsamp (x, β(ϕN,n )x) = 0 for all x ∈ Vn and all injections ϕN,n : [n] → [N ]. Likewise, if f : n Vn → R is continuous with respect to the sampling metric defined by (Ek ), we have f (β(ϕN,n )x) = f (x). Conversely, it follows from Proposition 4.10 below that if dsamp (x, y) = 0 for x ∈ Vn and y ∈ VN for n ≤ N then y = β(ϕN,n )x for some injection ϕN,n . Thus, species sampling may be appropriate in the same domains as random binning, such as those in Example 2.17. In fact, we show in Proposition 4.10 of Section 4 that random binning and species sampling define closely related topologies via the corresponding sampling metrics.
2.4
Missing Proofs from Section 2
We begin by proving Theorem 2.1 via a direct argument. Proof (Theorem 2.1). We start by arguing that properties 1 and 2 are equivalent. Since Ω∞ is a complete metric space by construction, it is compact if and only if it is totally bounded. If property 2 holds, then for any ϵ > 0 there is N (ϵ) ∈ N such that supx∈Ω∞ dist(x, Ω≤N (ϵ) ) ≤ ϵ/2. Since Ω≤N (ϵ) is totally bounded, it has a finite ϵ/2-net that is an ϵ-net for Ω∞ , proving that the latter is indeed F totally-bounded. Conversely, if Ω∞ is totally bounded and {y1 , . . . , yk } ⊆ Ω∞ is a finite ϵ/2-net, let xi ∈ n Ωn satisfy d(xi , yi ) ≤ ϵ/2 and note that {x1 , . . . , xk } ⊆ Ω≤N (ϵ) for some N (ϵ) ∈ N, hence supx∈Ω∞ dist(x, Ω≤N (ϵ) ) ≤ ϵ. Letting ϵ → 0 proves statement 2. Thus, statements 1 and 2 are equivalent. We proceed to argue that statements 2 and F 3 are equivalent. If statement 2 holds, for any (ϵk ≥ 0) with ϵk → 0, define the (deterministic) map Sk : n Ωn → Ω≤k by finding Sk (x) ∈ Ω≤k satisfying d(x, Sk (x)) ≤ dist(x, Ω≤k ) + ϵk . Then for any f ∈ F1 we have e∞ (f, f ◦ Sk ) ≤ sup F x∈Ω∞ dist(x, Ω≤k ) + ϵk → 0, so statement 3 holds. Conversely, suppose statement 3 holds and fix any x ∈ n Ωn . Then fx = d(x, ·) is 1-Lipschitz and dist(x, Ω≤k ) ≤ d(x, Sk (x)) = |fx (Sk (x)) − fx (x)| ≤ e∞ (fx , fx ◦ Sk ) ≤ sup e∞ (f, f ◦ Sk ). f ∈F1
F Since this holds for any x ∈ n Ωn , we conclude that statement 2 holds. Finally, we argue that statement 4 is equivalent to the previous equivalent three statements. If statement 3 holds, denote Rn = E supf ∈F1 e∞ (f, f ◦ Sn ), and note that Rn → 0 because (supf ∈F1 e∞ (f, f ◦ Sk ))k is a sequence of bounded (by statement 1) random variables converging to zero almost surely, so they also converge to zero in expectation. Then for any f, g ∈ F1 and any x ∈ Ω∞ we have |f (x) − g(x)| ≤ |f (x) − Ef (Sn (x))| + |Ef (Sn (x)) − Eg(Sn (x))| + |Eg(Sn (x)) − g(x)| ≤ en (f, g) + 2Rn , hence statement 4 holds. Conversely, suppose statement 4 holds. For any n ∈ N, let f = dist(·, Ω≤n ) and g = 0, and note that sup dist(x, Ω≤n ) = e∞ (f, g) ≤ en (f, g) + Rn = Rn , x∈Ω∞
which converges to zero as n → ∞, hence statement 2 holds. Next, we prove Proposition 2.2, likewise via a direct argument. Proof (Proposition 2.2). Since Ω∞ is compact, we have µn → µ∞ weakly if and only if limn W1 (µn , µ∞ ) = 0, or equivalently, if and only if limn supf ∈F1 |Eµ∞ f − Eµn f | = 0. Thus, if µn → µ∞ weakly then eµ∞ (f, g) ≤ eµn (f, g) + 2W1 (µn , µ∞ ) since if f, g ∈ F1 then 21 |f − g| ∈ F1 . Conversely, if such rate Rn exists, note that n o W1 (µn , µ∞ ) = sup |Eµ∞ f − Eµn f | = max sup (Eµ∞ f − Eµn f ), sup (Eµ∞ (−f ) − Eµn (−f )) f ∈F1
f ∈F1
f ∈F1
= sup (Eµ∞ f − Eµn f ) = sup (Eµ∞ (f − inf f (x)) − Eµn (f − inf f (x))) f ∈F1
x∈Ω∞
f ∈F1
x∈Ω∞
= sup (Eµ∞ f − Eµn f ) = sup (eµ∞ (f, 0) − eµn (f, 0)) ≤ Rn → 0, f ∈F1 f ≥0
f ∈F1 f ≥0
and hence µn → µ∞ weakly. Above, in going from the first to the second line we used the fact that −f ∈ F1 if and only if f ∈ F1 , and the last inequality follows since eµ (f, 0) = Eµ f when f ≥ 0. 18
We now prove Proposition 2.3 using Tychonoff’s theorem. Proof (Proposition 2.3). Endow each P(Ω Qn ) with the weak topology, metrized by the W1 -metric with respect to the given norms on V , and endow n n P(Ωn ) with the product topology, metrized by d((µk ), (νk )) = P Q −k 2 W (µ , ν ). Note that P(Ω ) is compact by Tychonoff’s theorem, and that the map sending 1 k k n k≥1 n Q x 7→ (Law(Sk (x)))k is an isometric embedding of Ω∞ into n P(Ω ). It therefore extends to an isometric n Q embedding of Ω∞ as a closed, and therefore compact, subset of n P(Ωn ). In particular, each Ωn is totally bounded in dsamp since Ω∞ is totally bounded. The above argument further shows that convergence of (xi ) in Q dsamp is equivalent to convergence of the sequence of sequences ((Sk (xi ))k )i in the product topology on n P(Ωn ), which precisely means that (Sk (xi ))i converges weakly for each k. We turn to proving Proposition 2.7, relating limits in sampling metric to sequences of distributions. Proof (Proposition 2.7). For the first claim, let X ∼ µ and let Sn be independent of X for each n. Then lim sup W1 (X, Sn (X)) ≤ lim sup EX ESn dsamp (X, Sn (X)) ≤ E lim sup ESn dsamp (X, Sn (X)) = 0, n→∞
n→∞
n→∞
where we used the fact that dsamp (X, Sn (X)) ≤ diam(Ω∞ ) < ∞ almost surely. This proves that Sn (X) → X weakly in Ω∞ , which is the first claim. R For the second claim, it is clear that (8) is linear, i.e., maps mixtures to mixtures, as Law(Sn (X)) = Law(Sn (x)) dν(x) if X ∼ ν is independent of Sn . To see that it is continuous, note that if µi → µ∞ weakly in P(Ω∞ ), then there is a coupling of Xi ∼ µi such that Xi → X∞ in dsamp almost surely by Skorokhod’s representation. We then get Law(Sn (Xi )) → Law(Sn (X∞ )) for each n where Sn is independent of the Xi . d
To see that (8) is injective, suppose Sn (X) = Sn (Y ) for random X, Y ∈ Ω∞ and for all n and take the weak d
limits of both sides as n → ∞ to obtain X = Y by the first claim. Thus, the map (8) is indeed a linear isomorphism onto its image. Finally, we prove Proposition 2.15. d
Proof (Proposition 2.15). For the first claim, it suffices to prove that if n = N and Rk (x) = Rk (y) for all k then there exists π ∈ Sn such that y = ρ(π)x. Applying this claim to ρ(κN,L )y, ρ(κn,L )x ∈ VL yields the claim for general x and y. d Suppose Rk (x) = Rk (y) for all k and n = N . Then for each k ∈ N there is a coupling (Fn,k , Gn,k ) of two uniformly random maps from [k] to [n] satisfying ρ(Fn,k )x = ρ(Gn,k )y. We argue that for sufficiently-large k ≥ n, with positive probability we can find an injection ϕk,n : [n] → [k] such that Gn,k ◦ ϕk,n = id[n] and Fn,k ◦ϕk,n ∈ Sn is a permutation, in which case applying ρ(ϕk,n ) to both sides above yields ρ(Fn,k ◦ϕk,n )x = y as desired. To this end, we define a bipartite graph with bipartition [n] ⊔ [n] where i, j ∈ [n] are connected −1 if Fn,k (i) ∩ G−1 n,k (j) ̸= ∅. We prove that this graph has a perfect matching π ∈ Sn with positive probability, −1 in which case picking ϕk,n (i) ∈ G−1 n,k (i) ∩ Fn,k (π(i)) yields the desired injection. We prove the existence of this perfect matching by showing that Hall’s condition holds with positive probability. 1 Pick ϵ < 2n . For any subset S ⊆ [n], we have with probability at least 1 − 2 exp(−2ϵ2 k) that |G−1 n,k (S)| −
|S|k ≤ ϵk, n
Pk Therefore, with probability at least 1 − since |G−1 i=1 1[Gn,k (i) ∈ S] ∼ Binom(k, |S|/n). n,k (S)| = n+2 2 2 exp(−2ϵ k) the above holds both for Fn,k and for Gn,k , and simultaneously for all subsets S ⊆ [n]. Choosing k sufficiently large ensures that this probability is positive. For each S ⊆ [n] define −1 N (S) = {i ∈ [n] : G−1 n,k (i) ∩ Fn,k (S) ̸= ∅}, −1 and suppose that |N (S)| < |S| for some such S. Observe that Fn,k (S) ⊆ G−1 n,k (N (S)) by definition of N (S) and hence (|N (S)| + 1)k |S|k |N (S)|k −1 − ϵk ≤ − ϵk ≤ |Fn,k (S)| ≤ |G−1 + ϵk. n,k (N (S))| ≤ n n n
19
1 We conclude that ϵ ≥ 2n , a contradiction. Thus, we have |S| ≤ |N (S)| for all S ⊆ [n], so Hall’s condition is satisfied and the above bipartite graph has a perfect matching, as desired. This proves the first claim. d For the second claim, suppose Bk (x) = Bk (y) for all k, so there is a coupling (Fk,n , Gk,N ) of uniformly random maps [n] → [k] and [N ] → [k], respectively, satisfying β(Fk,n )x = β(Gk,N )y. Note that for k ≥ n, the random map Fk,n is injective with probability at least 1 − n(n−1) and similarly for Gk,N . Therefore, for 2k k ≥ N sufficiently large both Fk,n and Gk,N are injective with positive probability, in which case there are permutations π, τ ∈ Sk satisfying Fk,n = π ◦ ιk,n and Gk,N = τ ◦ ιk,N . In this case we get
β(ϕk,n )x = β(ιk,N )y,
for some injection ϕk,n : [n] → [k].
(16)
Define the map f : [k] → [N ] sending f (i) = i for i ∈ [N ], sending ϕk,n ([n]) \ [N ] injectively to [N ] \ ϕk,n ([n]), and sending f (i) = 1 for i ∈ / [N ] ∪ ϕk,n ([n]). Note that f ◦ ιk,N = id[N ] and f ◦ ϕk,n is injective, so applying β(f ) to both sides in (16) yields the second claim.
3
Rates for Sampling with Replacement
In this section, we prove rates for any-dimensional sketching and generalization using the sampling metric defined with respect to sampling with replacement (3). The general outline for this section is as follows. We first derive rates at which arbitrary objects can be approximated by fixed-dimensional ones in Theorem 3.1, quantifying part 2 of Theorem 2.1. Based on Proposition 2.7, we then characterize in Theorem 3.4 the structure of any-dimensional data distributions obtained by sampling with replacement from limit objects. Next we leverage the equivalences in Theorem 2.1 to derive explicit sketching and generalization rates in Theorem 3.7 for functions continuous with respect to sampling with replacement. We conclude by deriving corollaries of our general results for functions arising in several applications, including graph densities and signals as well as many permutation-invariant neural network architectures such as transformers.
3.1
Main Results
We fix a compatible sequence of index F sets (In ), and consider the associated vector spaces (Vn = RIn ) and sampling with replacement maps (Rk : n Vn → Vk ) defined by (3). We also fix a sequence of compact sets (Ωn ) closed under sampling, such as the sequence of hypercubes Ωn = [−r, r]In . Throughout this section, we consider the sampling metric (1) defined using (Rk ), with W1 -distances taken with respect to the ℓ∞ -norms. Our first result shows that Edsamp (x, Rn (x)) → 0 as n → ∞ and gives the associated rate at which this expectation goes to zero. To bound Edsamp (x, Rn (x)), we must bound for each k the expected distance ERn W1 (Rk (x), Rk ◦ Rn (x)), where we (a) fix a realization of Rn ; (b) compute the W1 distance between the distributions of Rk (x) and Rk ◦ Rn (x), yielding a random number depending on Rn ; and (c) take the expectation with respect to Rn . In Theorem 3.1. Suppose a compatible F sequence (In ) has degree D, and suppose (Ωn ⊆ [−r, r] ) is closed under sampling. Then for any x ∈ n Ωn and k ≤ n such that |Ik | > 2, we have
k(k − 1) ERn W1 (Rk (x), Rk ◦ Rn (x)) ≤ r + 208r n
2 2 1/|Ik | k r n
2 2
and W1 (Rk (x), Rk ◦ Rn (x)) is 4knr -subgaussian with respect to the randomness in Rn . We also have h i 1 Edsamp (x, Rn (x)) ≤ Cr exp − (M −1 log2 n) 1+D , where C > 0 is a constant depending on (In ) and M is as in Definition 2.11. Furthermore, the distance 2 dsamp (x, Rn (x)) is 16r n -subgaussian. The proof is based on the observation that a uniformly random map FN,k : [k] → [N ] can be identified with k iid uniformly distributed random indices (FN,k (1), . . . , FN,k (k)) in [N ], so Law(FN,k ) = µ⊗k where µ is the uniform distribution on [N ]. Meanwhile, if we fix a realization FbN,n of FN,n , we have Law(FbN,n ◦Fn,k ) = µ⊗k n 20
Pn where µn = n1 i=1 δFbN,n (i) is an empirical measure obtained by sampling n iid points from µ. Comparing µn to µ yields the proof, see Section 3.2. We give a few examples of the rates implied by Theorem 3.1. Example 3.2 (Sampling columns with replacement). Suppose Vn = Rd×n and Ωn = [−r, r]d×n . As discussed in Example 2.4, we have an isomorphism Ω∞ ∼ = P([−r, r]d ) induced by x 7→ Law(R1 (x)). In particular, in this special case we have Law(Rk (x)) = Law(R1 (x))⊗k , so dsamp (x, y) and W1 (R1 (x), R1 (y)) metrize the same topology. The rate ERn W1 (R1 (x), R1 ◦ Rn (x)) = O(n−1/d ) for d > 2 from Theorem 3.1 is optimal [36]. Example 3.3 (Sampling vertices with replacement). Suppose Vn = Rn×n and let Ωn ⊆ [−r, r]n×n be closed under sampling. Convergence in dsamp recovers the limits of weighted graphs studied in [4]. We obtain a rate of convergence of O(exp[−(log2 n)1/3 ]) in dsamp , compared with a rate of O(exp[− 21 log log n]) implied by the results of [4] (who focus on convergence in a different metric, but the two can be related as in [12, Exer. 10.33]). We get the similar rate O(exp[−( 12 log2 n)1/3 ]) for pairs h of graphs and graph i signals on them, 1
for which Vn = Rn×n ⊕ Rn×d . Likewise, we obtain a rate of O exp −(M −1 log n) 1+D of general rank-D hypergraphs (with M = 1) and hypergraph signals (M = 2).
for approximation
Theorem 3.1 has two important consequences. First, it implies that Edsamp (x, Rn (x)) → 0 for any x ∈ Ω∞ , so Proposition 2.7 applies and gives us a characterization of any-dimensional data distributions obtained by sampling from random limit objects. Theorem 3.4 (Projection-consistent distributions). Suppose (In ) has finite degree and let (Ωn ⊆ [−r, r]In ) be closed under sampling. Then the following are equivalent for a sequence of probability distributions (µn ∈ P(Ωn )): (Projection consistency) We have ρ(ϕN,n )µN = µn whenever ϕN,n : [n] → [N ] is injective. (Sampling representation) There exists a distribution µ∞ ∈ P(Ω∞ ) such that µn = Law(Rn (X)) for all n, where X ∼ µ∞ is independent of Rn . Moreover, the measure µ∞ above is unique, and sequences of the form (µn = Law(Rn (x))) for deterministic x ∈ Ω∞ are extremal in the set of all projection-consistent sequences. The proof combines Proposition 2.7 and Theorem 3.1, along with a “finite” de Finetti theorem comparing sampling with and without replacement from [15] generalizing [43], see Section 3.2. Theorem 3.4 may be viewed as generalizing one formulation of de Finetti’s theorem and several related results concerning infinite exchangeable arrays, as we proceed to illustrate. Example 3.5 (Infinite exchangeable arrays). Suppose Vn = Rd×n and Ωn = Θn for compact Θ ⊆ Rd . In this case, projection-consistent distributions are precisely infinite exchangeable arrays. Indeed, if (X1 , X2 , . . .) is an infinite exchangeable array with Xi ∈ Θ almost surely then µn = Law(X1 , . . . , Xn ) is projectionconsistent, and conversely if a sequence of measures (µn ∈ P(Ωn )) is projection-consistent then the sequence (X1 , . . . , Xn ) ∼ µn extends to an infinite exchangeable array by Kolmogorov’s extension theorem. Since Ω∞ ∼ = P(Θ) in this case, Theorem 3.4 recovers the correspondence between infinite exchangeable arrays and mixtures of iid arrays, along with the extremality of iid arrays, that follows from de Finetti’s theorem and its extensions by Hewitt–Savage [44] and Dynkin [45]. Example 3.6 (Infinite exchangeable random graph models). Suppose Vn = Rn×n and Ωn ⊆ {0, 1}n×n . Reasoning as in Example 3.5, we note that projection-consistent sequences (µn ∈ P(Ωn )) correspond to infinite two-dimensional arrays of binary random variables (Xi,j )i,j∈N whose distribution is unchanged by simultaneous permutations of rows and columns. Such arrays can be viewed, in turn, as unweighted random graph models on countably-many exchangeable vertices, see [3]. In this setting, Theorem 3.4 implies that the countable random graph models obtained by sampling vertices with replacement from deterministic graphs and their limits are extremal, recovering [3, Cor. 5.4]. Our Theorem 3.4 similarly applies to general weighted countable graph models, as well as hypergraph models.
21
The second consequence of Theorem 3.1 is sketching and generalization bounds for functions continuous in sampling metric. While the rates we obtain for general Lipschitz-continuous functions are quite slow, we obtain substantially faster rates by exploiting particular representations of the functions at hand in terms of low-dimensional samples of their inputs. Theorem 3.7 (Sketching and generalization rates). In the setting of Theorem 3.1, consider functions F f, fb: n Ωn → R. F 2 (General) If f is L-Lipschitz in dsamp , then for any x ∈ n Ωn with probability at least 1 − e−2ϵ we have i 4rLϵ h 1 |f (x) − f (Rn (x))| ≤ LCr exp − (M −1 log2 n) 1+D + √ . n If fb is also L-Lipschitz in dsamp , then 1 e∞ (f, fb) ≤ en (f, fb) + 2LCr exp −(M −1 log2 n) 1+D .
(17)
(Fixed-dimensional laws) Suppose f (x) = g(Law(Rk (x))) where g : P(Ωk ) → R is L-Lipschitz in Wasserstein F 2 distance and |Ik | > 2. Then for any x ∈ n Ωn with probability at least 1 − e−2ϵ we have " 2 2 1/|Ik | # k r k(k − 1) 2kϵ + √ + 208 . |f (x) − f (Rn (x))| ≤ Lr n n n If fb has the same form as f above, then "
k(k − 1) e∞ (f, fb) ≤ en (f, fb) + 2Lr + 208 n
2 2 1/|Ik | # k r . n
(18)
(Fixed-dimensional moments) Suppose f = σ(Egk ◦ Rk ) where each coordinate function of gk : Ωk →FRℓ is B-bounded and σ : Rℓ → R is Lσ -Lipschitz with respect to the ℓ1 norm on Rℓ . Then for any x ∈ n Ωn 2 with probability at least 1 − e−2ϵ we have k−1 2ϵ +√ . |f (x) − f (Rn (x))| ≤ Lσ Bkℓ n n If fb has the same form (possibly with a different Lσ -Lipschitz σ b and B-bounded gbk ), then 2 k−1 b b +√ . e∞ (f, f ) ≤ en (f, f ) + 2Lσ Bkℓ n n √ When ℓ = 1 and σ = id, the 2/ n term above can be omitted.
(19)
The generalization bounds (17), (18), and (19) also hold for average error with respect to projection-consistent distributions. The proof uses Theorem 3.1, and we again defer it to Section 3.2. We now illustrate these improved rates on several classes of functions, beginning with polynomials. F Corollary 3.8 (Polynomials). In the setting of Theorem 3.1, let p : n Ωn → R be a polynomial of F degree d unchanged by equipartitions in the sense of (12). Then there exists B > 0 such that for any x ∈ n Ωn 2 with probability at least 1 − e−2ϵ , we have Dd − 1 2ϵ |p(x) − p(Rn (x))| ≤ BDd +√ . (20) n n b > 0 such that If pb is another such polynomial, then there exists B e∞ (p, pb) ≤ en (p, pb) +
b (B + B)Dd(Dd − 1) . n
22
Proof. It was shown in [15, Sec. 5] that there is a polynomial gDd ∈ R[VDd ] satisfying p(x) = EgDd (RDd x) for b we obtain both conclusions from Theorem 3.7. all x. Setting B = supx∈ΩDd |gDd (x)| and similarly for B, Notably, Corollary 3.8 applies to any polynomial function and any finite-degree compatible sequence of index sets. Here are a few examples encompassed by the above result. (Moment polynomials) When Vn = Rd×n , polynomials unchanged by duplication are precisely moment polynomials p(x) = q E(R1 (x))α1 , . . . , E(R1 (x))αℓ , where αi ∈ Nd0 and q is a fixed polynomial [15, §6.1]. Here E(R1 (x))α = n1
Pn
j=1
Qd
αℓ d ℓ=1 (xj )ℓ for α ∈ N0 .
(Graph densities) When Vn = Rn×n , polynomials unchanged by duplication are precisely linear combinations of graph homomorphism densities [15, §6.3]. Specifically, if H ∈ Nk×k is a multigraph, we define the 0 homomorphism density of H in G ∈ Vn by t(H; G) =
1 nk
X
k Y
H
i,j Gf (i),f (j) .
f : [k]→[n] i,j=1
It is called a homomorphism density because when H and G are undirected simple graphs, the value t(H; G) is the fraction of maps between vertex sets V (H) → V (G) that are graph homomorphisms. Similarly, when Vn = (Rn )⊗d is viewed as the space of adjacency tensors of hypergraphs, polynomials unchanged by duplication correspond to linear combinations of hypergraph densities. (Graph signals) When Vn = Rn×n ⊕ Rn×d consists of pairs of graphs and graph signals on them, then polynomials unchanged by duplication include polynomial graphon neural networks [23], which are compositions of polynomials of the form ! L X 1 ℓ (G, X) 7→ σ G XΘℓ , for polynomial σ and Θ0 , . . . , ΘL ∈ Rd×d . nℓ ℓ=0
For all of the above families of polynomials, we obtain any-dimensional sketching rates of O(n−1/2 ) and any-dimensional generalization rates of O(n−1 ). We remark that the rates for these polynomials are a substantial improvement over those previously available. For √ example, the result [16, Prop. 4.2] implies O(n−1/d ) generalization rates for moment polynomials and O(1/ log n) rates for graph densities and signals with respect to projection-consistent any-dimensional distributions. The improvement comes precisely from exploiting the fact that polynomials compute moments of low-dimensional samples, instead of merely their Lipschitz continuity. Next, we turn to nonpolynomial function classes. Corollary 3.9 (Normalized DeepSets). Suppose In = [d] × [n] so Vn = Rd×n , and let (Ωn ⊆ [−r, r]d×n ) d ℓ be a sequence of compact sets closed under sampling. Suppose each coordinate F function of h : R → R is ℓ B-bounded on Ω1 and σ : R → R is Lσ -Lipschitz in ℓ1 -norm. Consider f : n Ωn → R defined by ! n 1X f (x) = σ h(xi ) = σ(Eh ◦ R1 (x)), for x = (x1 , . . . , xn ) ∈ Vn . (21) n i=1 Then for any x ∈
F
−2ϵ2 we have n Ωn with probability at least 1 − e
|f (x) − f (Rn (x))| ≤
2Lσ Bℓϵ √ , n
and for any other fb of the above form, we have e∞ (f, fb) ≤ en (f, fb) + 23
4Lσ Bℓ √ . n
Proof. This directly follows from Theorem 3.7. When σ and h are neural networks, the architecture defined by (21) is called normalized DeepSets [16, 21]. In particular, when Ωn = Θn for compact Θ ⊆ Rd , we can extend f in (21) to measures µ ∈ P(Θ) by f (µ) = σ(Eµ h). This extension was shown in [21] to be Lipschitz-continuous in Wasserstein metric on P(Θ). In turn, the result [16, Prop. 4.2] implies O(n−1/d ) generalization rates for such Lipschitz functions on measures for average error with respect to infinite exchangeable arrays (Example 3.5). This rate can similarly be derived from Theorem 3.7, and Corollary 3.9 yields improved O(n−1/2 ) rates for functions of the form (21). Finally, we give sketching and generalization rates for transformers, making Corollary 1.7 precise. Corollary 3.10 (Permutation-invariant transformers). Suppose In = [d] × [n] with d > 2, so Vn = Rd×n , and Ωn = Θn for compact Θ ⊆ [−r, r]d . For matrices Q, K ∈ Rh×d and V ∈ Rd×d , define the self-attention mapping A : Vn → Vn by n
A(x1 , . . . , xn )i = xi +
1 X exp(⟨Qxi , Kxj ⟩)V xj , Zi j=1
where Zi =
n X
exp(⟨Qxi , Kxj ⟩).
(22)
j=1
Let ϕ : Rd → Rd be Lϕ -Lipschitz, Pnand let it act column-wise on Vn . Finally, let P : Vn → V1 be the mean pooling map P (x1 , . . . , xn ) = n1 i=1 xi . Define a depth-ℓ transformer to be the mapping T : Vn → V1 defined by the composition T = P ◦ (ϕ ◦ A)◦ℓ , Then there exists an L-Lipschitz continuous map T̄ : P(Θ) → Rd satisfying T (x) = T̄ (Law(R1 (x))). ConseF 2 quently, for any x ∈ n Ωn with probability at least 1 − e−2ϵ we have 2ϵ 208r2/d . (23) |T (x) − T (Rn (x))| ≤ Lr √ + n n1/d For any other L-Lipschitz map Ḡ : P(Θ) → Rd , we define G(x) = Ḡ(Law(R1 (x))) and obtain e∞ (T, G) ≤ en (T, G) +
416Lr1+2/d , n1/d
where en (T, G) = supx∈Θn ∥T (x) − G(x)∥∞ and similarly for e∞ . The proof is based on the measure-theoretic in-context mapping of [17], and is deferred to Section 3.2. We remark that evaluating T (x) exactly for x ∈ VN takes O(N 2 ) operations due to (22), but evaluating it to a desired accuracy δ > 0 can be done with high probability in O(δ −2d ) time (independent of the length N of the input) after sampling n = O(δ −d ) columns from x uniformly at random and using (23).
3.2
Missing Proofs from Section 3
We begin by proving Theorem 3.1. The following is the key proposition we shall need. F Proposition 3.11. Fix a bounded f : Ωk → R and x ∈ n Ωn , and define the random variable Zf = ERk f (Rk ◦ Rn (x)) − Ef (Rk (x)) where expectations are only with respect to Rk , which is independent of Rn . (Bias) We have |ERn Zf | ≤ k(k−1) ∥f ∥∞ whenever k ≤ n. n 2
(Concentration) Zf − ERn Zf is 4kn ∥f ∥2∞ -subgaussian. Proof. By [46], there is a coupling of a uniformly random map Fn,k and of a uniformly random injection Φn,k d
such that P[Fn,k ̸= Φn,k ] ≤ k(k−1) 2n . Furthermore, since FN,n ◦ ϕn,k = FN,k for any injection ϕn,k : [k] → [n], d
we have ρ(Φn,k ) ◦ Rn = Rk if Rn is independent of Φn,k . In this case, we have h i k(k − 1) , |EZf | = |Ef (ρ(Fn,k ) ◦ Rn (x)) − Ef (ρ(Φn,k ) ◦ Rn (x))| ≤ 2∥f ∥∞ P Fn,k ̸= Φn,k ≤ ∥f ∥∞ n 24
as claimed. To see the subgaussianity of Zf , represent a map [n] → [N ] as a sequence in [N ]n , and observe that Pn Law(FN,n ) = Unif[N ]⊗n . Writing Rn = ρ(FbN,n ), let µn = n1 i=1 δFbN,n (i) be the empirical measure obtained b by sampling n iid points from µ = Unif([N ]). Now observe that Law(FbN,n Fn,k ) = µ⊗k n conditioned on FN,n ⊗k k e e while Law(FN,k ) = µ . Furthermore, if we define f : [N ] → R by f (F ) = f (ρ(F )x), then n h i X e= 1 e FbN,n (i1 ), . . . , FbN,n (ik ) , ERk f (Rk ◦ Rn (x)) = Eµ⊗k f f n nk i ,...,i =1 1
(24)
k
where ∥fe∥∞ ≤ ∥f ∥∞ . Changing the value FbN,n (iℓ ) for any fixed ℓ ∈ [n] changes the value of Eµ⊗k fe by at n 2
4k 2 most 2k n ∥f ∥∞ , hence Zf − EZf is n ∥f ∥∞ -subgaussian by the bounded-difference inequality [47].
We turn to proving Theorem 3.1 by combining Proposition 3.11 with the following standard covering number bound. Lemma 3.12 (Covering number bound). In the setting of Proposition 3.11, suppose Fk is a family of functions on Ωk with supf ∈Fk supx∈Ωk |f (x)| ≤ r. Then ) ( √ Z 16 2kr r p k(k − 1) log N (Fk , ∥ · ∥∞ , ϵ) dϵ , + inf 4δ + √ E sup Zf ≤ r δ>0 n n f ∈Fk δ where N (Fk , ∥ · ∥∞ , ϵ) is the ϵ-covering number of the function class Fk in ∥ · ∥∞ . Moreover, the random 2 2 variable supf ∈Fk Zf is 4knr -subgaussian. 2 2
Proof. Since Zf − Zg = Zf −g , we conclude that {Zf − EZf }f ∈Fk is a centered 4knr -subgaussian process with respect to the uniform metric. Since the diameter of Fk under the uniform metric is at most 2r by assumption, Dudley’s entropy integral bound [48] gives ) ( √ Z 16 2kr r p log N (Fk , ∥ · ∥∞ , ϵ) dϵ . E sup (Zf − EZf ) ≤ inf 4δ + √ δ>0 n f ∈Fk δ Combining the above bound with our bias bound from Proposition 3.11 yields the third claim. Finally, observe that Zf is a function of n iid random indices FbN,n (1), . . . , FbN,n (n), and that changing the value of one of these indices affects at most nk −(n−1)k ≤ knk−1 terms in (24) by at most 2∥f ∥∞ /nk ≤ 2r/nk . n Therefore, each Zf is a 2kr n -Lipschitz function with respect to the Hamming distance on [N ] , and hence the same is true of supf ∈Fk Zf . The bounded difference inequality [47, Cor. 2.21] yields the final claim. Combining Lemma 3.12 with covering number bounds for Lipschitz functions yields Theorem 3.1. Proof (Theorem 3.1). Let Fk be the collection of all functions f : [−r, r]Ik → R with f (0) = 0 that are 1-Lipschitz with respect to the ℓ∞ -norm, and note that supf ∈Fk ∥f ∥∞ ≤ r. Combining the definition of the W1 distance with Lemma 3.12 gives ( ) √ Z k(k − 1) 16 2kr r p ERn W1 (Rk (x), Rk ◦ Rn (x)) ≤ E sup Zf ≤ r + inf 4δ + √ log N (Fk , ∥ · ∥∞ , ϵ) dϵ . δ>0 n n f ∈Fk δ By [49, §9] (or by [50, Thm. 17]), we have 2r log N (Fk , ∥ · ∥∞ , ϵ) ≤ (log 2)N ([−r, r]Ik , ∥ · ∥∞ , ϵ/2) + log 2 +1 . ϵ |I |
We further have N ([−r, r]Ik , ∥ · ∥∞ , ϵ/2) ≤ ⌈4r/ϵ⌉ k and hence log N (Fk , ∥ · ∥∞ , ϵ) ≤ (1 + log 2) 5r ϵ all ϵ ∈ (0, 2r). Since |Ik | > 2, we have √ Z p 16 2kr r p kr δ −|Ik |/2+1 4δ + √ log N (Fk , ∥ · ∥∞ , ϵ) dϵ ≤ 4δ + 16 2(1 + log 2) √ (5r)|Ik |/2 . |Ik |/2 − 1 n n δ 25
|Ik |
for
2/|Ik | 2 2 1/|Ik | p Choosing δ = 5r 4 √krn 2(1 + log 2) , we obtain the claimed estimate 208r k nr . Proposi2 2
tion 3.11 also shows that supf ∈Fk Zf is 4knr -subgaussian. Turning to the claim bound on dsamp , for any K ≤ n we have Edsamp (x, Rn (x)) ≤
K X
2−k ERn W1 (Rk (x), Rk ◦ Rn (x)) + 2−K+1 r ≤ Cr
k=1
2 1D r MK + 2−K r n
obtained by estimating ERn W1 (Rk (x), Rk ◦ Rn (x)) ≤ 2r for k ≥ K and applying the upper bounds from the first part of this corollary (if |Ik | ≤ 2 for some small k, the covering number argument yields bounds −1/2 of O(n O(n−1/2 log n), both of which are dominated by the slower |Ik | > 2 terms). Choosing ) or 1 1 D+1 D+1 2 log2 n log2 (n/r ) K= if r ≤ 1 and K = gives the desired bound. Finally, the same proof M M as 3.11 shows that dsamp (x, Rn (x)) is a function of n independent random variables and is P in Proposition 4r −k 2kr = 2 k≥1 n n -Lipschitz in Hamming distance in each of them, hence the bounded-difference inequality 2
yields its claimed 16r n -subgaussianity. We turn to proving Theorem 3.4 by combining Proposition 2.7 and a “finite” de Finetti theorem from [15]. Proof (Theorem 3.4). Propositions 2.13 and 2.14 show that if µn = Law(Rn (X)) for random X independent of Rn , then (µn ) is projection-consistent. Conversely, if (µn ) is projection-consistent then by [15, Thm. 4.15] i→∞ there is a sequence νi ∈ P(Ω∞ ) such that Law(Rn (Xi )) −−−→ µn weakly for each n where Xi ∼ νi is independent of Rn . This implies that the sequence (νi ) converges weakly with respect to dsamp , and µ∞ = limi νi ∈ P(Ω∞ ) then satisfies the desired sampling representation. The last claim follows by Proposition 2.7, which applies by Theorem 3.1. Specifically, Theorem 3.1 shows that Edsamp (x, Rn (x)) → 0 as n → ∞ at a universal rate for all x ∈ Ω∞ . If x ∈ Ω∞ then we can write x = limi xi for xi ∈ Ω∞ , so Rn (x) is the weak limit of Rn (xi ). A simple application of the triangle inequality shows that Edsamp (x, Rn (x)) → 0 at the same universal rate, so the condition (7) in Proposition 2.7 is satisfied. Next, we prove the sketching and generalization bounds in Theorem 3.7. F Proof (Theorem 3.7). If f and fb are L-Lipschitz in dsamp and x ∈ n Ωn , then |f (x) − f (Rn (x))| ≤ Ldsamp (x, Rn x) and |f (x) − fb(x)| ≤ |f (x) − Ef (Rn (x))| + |E[f (Rn (x)) − fb(Rn (x))]| + |Efb(Rn (x)) − fb(x)|.
(25)
Now observe that |f (x) − Ef (Rn (x))| ≤ LEdsamp (x, Rn (x)) and similarly for fb, and that |E[f (Rn (x)) − fb(Rn (x))]| ≤ en (f, fb). The bounds for general Lipschitz functions now follow from Theorem 3.1. If f (x) = F (Law(Rk (x))) for L-Lipschitz F , we have |f (x) − f (Rn (x))| ≤ LW1 (Rk (x), Rk ◦ Rn (x)) where we fix a realization of Rn , and |f (x) − Ef (Rn (x))| ≤ LEW1 (Rk (x), Rk ◦ Rn (x)). Since fb satisfies the same bounds, we obtain the claimed rates from Theorem 3.1 using (25) again. Finally, suppose f (x) = σ(Egk (Rk (x))) and note that |f (x) − f (Rn (x))| ≤ Lσ ∥ERk gk (Rk (x)) − ERk gk (Rk ◦ Rn (x))∥1 =
ℓ X
E[gk ]j (Rk (x)) − ERk [gk ]j (Rk ◦ Rn (x)) ,
j=1
where we fix a realization of Rn and denote by [gk ]j the jth coordinate function of gk . Similarly, we have Pℓ |f (x) − Ef (Rn (x))| ≤ Lσ ERn j=1 |ERk [gk ]j (Rk (x)) − ERk [gk ]j (Rk ◦ Rn (x))|. Since fb satisfies the same bounds, we obtain the claimed rates from Proposition 3.11 using (25) again. If σ = id, we can improve the generalization bound because |f (x)−Ef (Rn (x))| ≤ ∥Egk (Rk (x))−Egk (Rk ◦Rn (x))∥1 where both expectations are inside the norm, and hence we only incur an error due to the bias in Proposition 3.11. All the above bounds hold for average error with respect to projection-consistent distributions (µn ). This can be seen by writing µn = Law(Rn (X)) for a random X ∈ Ω∞ using Theorem 3.4 and applying the above bounds conditionally on X. 26
Finally, we prove Corollary 3.10 using the measure-theoretic expression for attention in [17]. Proof (Corollary 3.10). Let Pc (Rd ) be the space of compactly-supported probability measures on Rd , and consider the in-context attention mapping Ā : Rd × Pc (Rd ) → Rd introduced in [17], given by Ā(x, µ) = x + which satisfies
EY ∼µ exp(⟨Qx, KY ⟩)V Y , EY ∼µ exp(⟨Qx, KY ⟩)
d
R1 ◦ A(x) = Ā(R1 (x), Law(R1 (x))). Defining A : Pc (Rd ) → Pc (Rd ) by A(µ) = Law(Ā(X, µ)) where X ∼ µ, letting ϕ act on measures via pushforward, and defining T̄ (µ) = EX∼(ϕ◦A)◦ℓ (µ) X, wePget T (x) = T̄ (Law(R1 (x))) as desired. Indeed, for ℓ = 1 we have T̄ (Law(R1 (x))) = Eϕ(R1 ◦ A(x)) = n 1 i=1 ϕ(A(x)i ) = T (x), and inducting on ℓ shows the claimed identity in general. n Let t = supj≤ℓ supx∈Θ ∥(ϕ◦A)◦j (x)∥∞ < ∞ and denote Bt = {x ∈ Rd : ∥x∥∞ ≤ t}. We can find Lipschitz constants L1 , L2 > 0 such that Ā(x, ·) : P(Bt ) → Rd is L1 -Lipschitz while Ā(·, µ) : Bt → Rd is L2 -Lipschitz for any x ∈ Bt and µ ∈ P(Bt ), see [51, Lemma 2] for example. For any x, y ∈ Btn , we then have W1 (R1 ◦ A(x), R1 ◦ A(y)) ≤ (L1 + L2 )W1 (R1 (x), R1 (y)). Likewise, we have W1 (R1 ◦ ϕ(x), R1 ◦ ϕ(y)) ≤ Lϕ W1 (R1 (x), R1 (y)) because ϕ acts column-wise. Thus, we get W1 (R1 ◦ (ϕ ◦ A)◦ℓ (x), R1 ◦ (ϕ ◦ A)◦ℓ (y)) ≤ Lℓϕ (L1 + L2 )ℓ W1 (R1 (x), R1 (y)), so T̄ is Lℓϕ (L1 + L2 )ℓ -Lipschitz. The result now follows from Theorem 3.7.
4
Rates for Random Binning and Species Sampling
In this section, we prove rates for sketching and generalization using the sampling metric defined with respect to random binning from Section 2.3.1, and relate the topologies defined by random binning and species sampling via their corresponding sampling metrics.
4.1
Main Results
We fix a compatible sequence of F index sets (In ), and consider the associated vector spaces (Vn = RIn ) and random binning maps (Bk : n Vn → Vk ) defined by (5). We also fix a sequence of compact sets (n) (Ωn ) closed under random binning, such as the sequence of ℓ1 balls Bℓ1 (r) = {x ∈ Vn : ∥x∥1 ≤ r}. Proceeding as in Section 3, it may be tempting to try to prove a result akin to Theorem 3.1 in which we might show that dsamp (x, Bn (x)) → 0 with high probability, and quantify the rate at which it converges to zero. Unfortunately, while we will show below that Edsamp (x, Bn (x)) → 0, the following example illustrates that individual realizations dsamp (x, Bn (x)) do not concentrate as well around their means as in the case of sampling with replacement. Example 4.1 (Anti-concentration for random binning). Suppose Vn = Rn and consider x = (1/2, 1/2) ∈ V2 . Observe that Bn (x) equals one of the standard basis vectors with probability 1/n, since this is the probability that the two entries of xPto map to the same bin. Therefore, with probability 1/n, we have that 2 −k . Borel–Cantelli implies that for any rate dsamp (x, Bn (x)) = dsamp (x, e1P ) = (1 − k1 ) 12 = 1−log k≥2 2 2 (ϵn ≥ 0) with ϵn ↓ 0 we have n≥1 P[dsamp (x, Bn (x)) ≥ ϵn ] = ∞. In contrast, for sampling with replacement Theorem 3.1 gives a rate ϵn such that P[dsamp (x, Rn (x)) ≥ ϵn ] ≤ e−Cn for a constant C > 0. To remedy this situation, we show in Theorem 4.2 that dsamp (x, En (x)) exhibits the requisite concentration, where En is the species sampling map from Section 2.3.2. In other words, species sampling furnishes the requisite sketching map for the sampling metric defined via random binning. Subsequently, we follow a 27
similar agenda as in Section 3. We characterize the any-dimensional data distributions that are obtained via random binning in Theorem 4.3. We then give explicit any-dimensional sketching and generalization rates in Theorem 4.5, followed by corollaries that provide concrete illustrations of our results in the context of applications in graph signal processing and neural networks. We conclude with Proposition 4.10 in which we relate convergence with respect to random binning and species sampling. We begin by quantifying the convergence dsamp (x, En (x)) → 0 in expectation and with high probability. Theorem 4.2. Suppose (In ) is a compatible sequence of index sets of degree D, and consider the sampling metric defined using random binning (Bk ) and the W1 -metric with respect to the ℓ2 norm. Fix (Ωn ⊆ RIn ) closed under both binning and species sampling such that supn∈N supx∈Ωn ∥x∥1 ≤ r. F 1. For any x ∈ n Ωn , we have r 2 EEn W1 (Bk (x), Bk ◦ En (x)) ≤ r n p and similarly Edsamp (x, En (x)) ≤ r 2/n. Moreover, both W1 (Bk (x), Bk ◦ En (x)) and dsamp (x, En (x)) 2 are 4rn -subgaussian with respect to the randomness in En . F 2. For any x ∈ n Ωn and any k ∈ N, we have r 2D(3D − 1) , (26) EBn W1 (Bk (x), Bk ◦ Bn (x)) ≤ r n q and similarly Edsamp (x, Bn (x)) ≤ r 2D(3D−1) . n We emphasize again that although Theorem 4.2(2) shows that Edsamp (x, Bn (x)) → 0, these distances do not concentrate well around their means as shown in Example 4.1. The proof of Theorem 4.2(1) is based on the following standard bound for the empirical sampling map (14), s 2 X ∥x∥1 E∥x − En (x)∥2 ≤ ∥x∥1 E pα − n1 Binom(n, pα ) ≤ √ , for any x ∈ RIN , N ∈ N, (27) n α∈IN
where pα = |xα |/∥x∥1 are the probabilities proportional to the magnitudes of entries of x, together with the fact that dsamp (En (x), En (x)) = 0 almost surely. The proof of Theorem 4.2(2) uses an explicit coupling between Bk (x) and Bk ◦ Bn (x). We give the full details in Section 4.2. Examples of sets satisfying the hypotheses of Theorem 4.2 include the sequence of simplices Ωn = ∆In and ℓ1 -balls. We proceed to describe some of the implications of Theorem 4.2. First, the fact that Edsamp (x, Bn (x)) → 0 at a universal rate as n → ∞ allows us to apply Proposition 2.7 and leads to a characterization of sequences of any-dimensional distributions that are compatible with random binning. Theorem 4.3 (Equipartition-consistent distributions). Suppose (In ) has finite degree, let Vn = RIn , and suppose (Ωn ) is a sequence of compact sets closed under binning with supn supx∈Ωn ∥x∥1 < ∞. Then the following are equivalent for a sequence of probability distributions (µn ∈ P(Ωn )): (Equipartition consistency) We have β(ψn,N )µN = µn whenever ψn,N : [N ] → [n] is an equipartition. (Sampling representation) There exists a distribution µ∞ ∈ P(Ω∞ ) such that µn = Law(Bn (X)) for all n, where X ∼ µ∞ is independent of Bn . Moreover, the measure µ∞ above is unique, and sequences of the form (µn = Law(Bn (x))) for deterministic x ∈ Ω∞ are extremal in the set of all such sequences. Similarly to Theorem 3.4, the proof combines Proposition 2.7 with a “dual” finite de Finetti theorem comparing uniformly random binning and random binning into equally-sized bins from [15], see Section 4.2. We give some examples of the any-dimensional data distributions obtained by randomly binning limit objects. Using Theorem 4.2, we then give generalization rates for average error with respect to these distributions. 28
Example 4.4. If In = [n] and Ωn = ∆n , then a sequence (µn ∈ P(∆n )) is equipartition-consistent if and only if (i) each µn is exchangeable; (ii) whenever n|N we have n N/n X d (XN )j+(i−1)(N/n) = Xn . j=1
i=1
For example, the sequence of Dirichlet distributions µn = Dir(α1n /n) satisfies these conditions for any α ∈ [0, ∞), where α = 0 corresponds to a uniformly random coordinate vector. If In = [n]2 , then equipartition-consistent sequences (µn ∈ P(∆n×n )) were called “equipartition-consistent random graph models” in [13], where they were shown to correspond to certain limits of growing-sized graphs. In particular, the specialization of Theorem 4.3 to this case was proved in [13, Thm. 1.9]. The next consequences of Theorem 4.2 are the following sketching and generalization rates, proved in Section 4.2. In contrast to the analogous Theorem 3.7 for sampling with replacement, here we get a rate of n−1/2 regardless of the latent low-dimensional structure of our functions. F Theorem 4.5 (Sketching and generalization rates). In the setting of Theorem 4.2, suppose f : n Ωn → R satisfies one of the following conditions. (General) f is L-Lipschitz in dsamp ; (Fixed-dimensional laws) f is L-Lipschitz in (x, y) 7→ W1 (Bk (x), Bk (y)) for some k ∈ N; (2-norm continuity) f is unchanged by zero-padding so f ◦ β(ϕN,n ) = f for any injection ϕN,n : [n] → [N ], and f |Vn is L-Lipschitz in ℓ2 norm for all n. F 2 Then for any x ∈ n Ωn with probability at least 1 − e−2ϵ we have √ Lr( 2 + 2ϵ) √ . (28) |f (x) − f (En (x))| ≤ n If fb is another such function and n ≥ D, then s e∞ (f, fb) ≤ en (f, fb) + 2Lr
2 . ⌊n/D⌋
(29)
If (µn ) is equipartition-consistent and µ∞ is their representing measure from Theorem 4.3, we also have r 2D(3D − 1) b b eµ∞ (f, f ) ≤ eµn (f, f ) + 2Lr . n The proof is a direct application of the above two theorems, and we defer it to Section 4.2. The three conditions on the function f in Theorem 4.5 are different sufficient conditions for continuity of f with respect to random binning. Some of these conditions are more conveniently applicable to different function classes, as we proceed to illustrate. As in Section 3, a prominent example of functions satisfying the above hypotheses are polynomials. F Corollary 4.6. In the setting of Theorem 4.2, let p : n Ωn → R be a polynomial unchanged by zero-padding, so p ◦ β(ϕN,n ) = p for all injections ϕN,n : [n] → [N ] and all n ≤ N . Then p satisfies the second condition in Theorem 4.5. Proof. It was shown in [15, Sec. 5] that there exists gk ∈ R[Vk ] satisfying p(x) = Egk (Bk (x)) for all x. If L is the Lipschitz constant of gk over Ωk , then p is L-Lipschitz in (x, y) 7→ W1 (Bk (x), Bk (y)), as claimed. Note that we obtain sketching and generalization rates that do not directly depend on the degree of p or of (In ). The following are a few examples of the polynomials to which Corollary 4.6 applies, which constitute “unnormalized” analogs of the polynomials unchanged by duplication considered in Corollary 3.8. 29
(Multisymmetric Functions) When Vn = Rd×n , polynomials unchanged by zero-padding are precisely multisymmetric functions [52], consisting of polynomials of the form p(x) = q pα1 (x), . . . , pαk (x) , Pn Qd α where q ∈ R[y1 , . . . , yk ] is a fixed polynomial, and for α ∈ Nd0 we have pα (x) = i=1 j=1 xj,ij . When d = 1 Pn and α ∈ N0 , the polynomials pα (x) = i=1 xα i are known as power-sum polynomials, and polynomials unchanged by zero-padding are called symmetric functions. These are classic objects of study in combinatorics and representation theory, see [53, Chap. 7] and [54]. ((Hyper)Graph Numbers) When Vn = Rn×n , polynomials unchanged by zero-padding are precisely linear combinations of graph homomorphism numbers [15, §6.4]. Specifically, if H ∈ Nk×k is a multigraph, we define 0 the homomorphism number of H in G ∈ Vn by hom(H; G) =
X
k Y
H
i,j Gf (i),f (j) .
f : [k]→[n] i,j=1
When H, G are simple graphs, the value hom(H; G) is the number of graph homomorphisms from H to G. Similarly, when Vn = (Rn )⊗d polynomials unchanged by zero-padding are linear combinations of hypergraph homomorphism numbers, analogously defined. (Graph Signals) When Vn = Rn×n ⊕ Rn , polynomials unchanged by zero-padding include polynomial (unnormalized) graph neural networks, which are compositions of polynomials of the form ! L X ℓ (G, X) 7→ σ G XΘℓ , for polynomial σ and Θ0 , . . . , ΘL ∈ Rd×d . ℓ=0
For all of the above families of polynomials, we obtain sketching and generalization rates of O(n−1/2 ). We now turn to proving sketching and generalization rates for some non-polynomial function classes. P Corollary 4.7 (DeepSets). Let Vn = Rd×n and consider maps of the form f (x1 , . . . , xn ) = σ( i ρ(xi )) for ρ : Rd → Rℓ with ρ(0) = 0 and σ : Rℓ → R. Then f is unchanged by zero-padding. √ 1. Suppose σ is Lσ -Lipschitz, and that ρ is Lρ r-Lipschitz with respect to the ℓ2 norm on√{x ∈ Rd : ∥x∥1 ≤ r} for each r. Then f satisfies the third condition in Theorem 4.5 with L = Lρ Lσ 2r. P 2. The 1-norm f (x) = i |xi | is discontinuous in sampling metric. The proof is a direct computation, see Section 4.2. Although the 1-norm is of the form f (x1 , . . . , xn ) = P σ( i ρ(xi )) for d = 1, σ = idR and ρ = | · |, both of which are 1-Lipschitz, the stronger condition on ρ in part 1, requiring its Lipschitz constant to decay to zero around the origin, fails to hold for the absolute value function. Therefore, mere Lipschitz continuity of ρ (as well as σ) is not by itself sufficient to obtain continuity with respect to random binning. The hypothesis on ρ in part 1 is satisfied if, for example, ρ is differentiable with a 1/2-Hölder continuous derivative satisfying ρ′ (0) = 0. When σ and ρ in Corollary 4.7 are neural networks, the resulting architecture is called DeepSets [18]. When d = 1 and Ωn = ∆n , different choices of σ and ρ yield various diversity indices used to quantify the 1−t gives concentration of a discrete probability distribution [42]. For example, setting ρ(x) = xq and σ(t) = q−1 Tsallis’ entropy, which for q ≥ 3/2 satisfies the hypotheses of Corollary 4.7(1). We note however that some diversity indices are not continuous in sampling metric. This is the case for Shannon and Rényi entropies 1 log(t), ρ(t) = tq for the latter) for example, (given by σ = id, ρ(t) = t log 1t for the former and σ(t) = 1−q both of which diverge along the (convergent) sequence x(n) = 1n /n. Corollary 4.8 (PointNet). Let Vn = Rd×n and consider maps of the form f (x1 , . . . , xn ) = σ(supi ρ(xi )) for ρ : Rd → Rℓ and σ : Rℓ → R, where the supremum is taken coordinate-wise. If ρ(x) ≥ 0 for all x, ρ(0) = 0, and if σ and ρ are Lσ and Lρ -Lipschitz continuous in ℓ2 -norm, then the function f satisfies the third condition in Theorem 4.5 with L = Lρ Lσ . 30
Proof. Direct computation. Finally, we consider non-polynomial graph neural networks. Corollary 4.9 (Graph Neural Networks). Let Vn = Rn×n ⊕ Rn×d and consider a composition of maps of the form !! D X d F (A, X) = A, σ A XΘd , where Θ0 , . . . , ΘD ∈ Rd×d , d=0 d
d
and σ : R → R satisfies σ(0) = 0, is Lσ -Lipschitz in ℓ2 , and is applied row-wise. Also define P : Vn → Rd by P (A, X) = ρ(X)⊤ 1n for ρ : Rd → Rd that is applied row-wise and satisfies the hypotheses of Corollary 4.7(1). Consider the depth-ℓ graph neural network given by the composition G (n) f = P ◦ F ◦ℓ : Bℓ1 (r) → Rd , n (n)
where Bℓ1 (r) = {(A, X) ∈ Vn : ∥A∥1 + ∥X∥1 ≤ r}. Then each coordinate function of f satisfies the third condition in Theorem 4.5. The proof is an elementary but long computation, and we defer it to Section 4.2. For all of the function classes in the above corollaries, Theorem 4.5 yields n−1/2 sketching and generalization rates. So far in this section, we have worked with the sampling metric defined by random binning, and showed that species sampling is an appropriate sketching map with respect to this metric. We end this section by further considering the sampling metric defined by species sampling, and show that its induced topology is closely related to the one induced by random binning. F Proposition 4.10. Let (In ) be a compatible sequence of finite degree, and let (xi ) ⊆ n RIn . Then (Ek (xi )) − converges for all k if and only if the sequence of random tuples ((Bk (x+ i ), Bk (xi )))i converges for all k, where + − xi = max{xi , 0} and xi = max{−xi , 0} are the entrywise positive and negative parts of xi , and we apply − the same random map Bk to both x+ i and xi . In words, convergence of the species samples is equivalent to joint convergence of random binning of the positive and negative parts. In particular, the two notions of convergence are equivalent for nonnegative vectors. The special case of this equivalence for In = [n]2 and Ωn = ∆n×n was shown in [13, Prop. 4.1]. We remark that species sampling gives another sequence of any-dimensional data distributions, and our results yield generalization rates with respect to these distributions. For example, if (Ωn = ∆In ) then we get the same completion Ω∞ with respect to both (Bk ) and (Ek ) by Proposition 4.10. Combining Theorem 4.2 and Proposition 2.7 shows that each probability distribution µ ∈ P(Ω∞ ) on limit objects yields two sequences of distributions on finite objects converging weakly to µ, namely (Law(Bk (x))) and (Law(Ek (X))) for X ∼ µ independent of Bk and Ek . Both sequences of measures can be used as any-dimensional distributions for which n−1/2 generalization rates are available. It would be interesting to characterize sequences of the form (Law(Ek (X))) analogously to Theorem 4.3. For example, when In = [n]2 such sequences of distributions are precisely edge-exchangeable multigraph models normalized to have unit edge weights, as shown in [13, Rmk. 4.2]. We leave such a characterization more generally for future work.
4.2
Missing Proofs from Section 4
We begin by proving Theorem 4.2. We shall need the following several lemmas to do so. The first lemma shows that the species sampling En and empirical sampling En maps in (15) and (14), respectively, are equivalent in the sampling metric defined by random binning. Lemma 4.11 (Equivalence of species and empirical sampling). Suppose (In ) has finite degree and let Vn = RIn . Then dsamp (En (x), En (x)) = 0 for any x ∈ VN and any n, N ∈ N. Proof. After zero-padding x if necessary, which does not change the distributions of En (x) and En (x) by Proposition 2.18, we may assume N ≥ nD. We construct a random injection ΦN,nD : [nD] → [N ] satisfying En (x) = β(ΦN,nD )En (x), 31
(30)
which proves that dsamp (En (x), En (x)) = 0 by (10). To construct this injection, recall the randomlyenumerated indices {t1 , . . . , tk } from the construction of En and En in Section 2.3.2, where k ≤ nD. Set ΦN,nD (i) = ti for i ≤ k and set ΦN,nD |[nD]\[k] to be a uniformly random injection into [N ] \ {t1 , . . . , tk }. Note that (30) is satisfied by construction of En (x) in (15). As we shall see, empirical sampling satisfies several useful properties that we exploit to prove Theorem 4.2. The second lemma shows a compatibility between the empirical sampling En from (14) and the action (4) of maps between finite sets. Lemma 4.12. Let (In ) be a compatible sequence and x ∈ ∆In . Then for any map f : [n] → [m], we have d
Ek (β(f )x) = β(f )Ek (x). Proof. Observe that the probability of sampling α ∈ Im from β(f )x is probability that if γ ∈ In is drawn from x then ρ(f )(γ) = α. Thus, β(f )Ek (x) =
xγ . γ∈In ρ(f )(γ)=α
P
This is also the
k k X 1X d 1 eρ(f )(γi ) = eα = Ek (β(f )x), k i=1 k i=1 i
where γ1 , . . . , γk ∈ In are sampled iid from x while α1 , . . . , αk are sampled iid from β(f )x. Combining Lemma 4.12 with the bound (27) for the empirical sampling map, we are ready to prove the first bound from Theorem 4.2(1). Lemma 4.13. Suppose (In ) has finite degree. For any x ∈ RIN and any N ∈ N, we have r 2 EEn W1 (Bk (x), Bk ◦ En (x)) ≤ ∥x∥1 . n Proof. By homogeneity of En and linearity of Bk , it suffices to prove the claim when ∥x∥1 = 1, which we assume for the remainder of the proof. Suppose first that x ≥ 0, so that x ∈ ∆IN . Then EW1 (Bk (x), Bk ◦ En (x)) = EW1 (Bk (x), Bk ◦ En (x)) ≤ EEn EBk ∥Bk (x) − Bk ◦ En (x)∥2 1 = EBk EEn ∥Bk (x) − En (Bk (x))∥2 ≤ √ , n where the first equality follows from Lemma 4.11, the second √ equality follows from Lemma 4.12, and the last inequality follows from the fact that E∥p − En (p)∥2 ≤ 1/ n for any discrete distribution p by (27). If x ≤ 0 then the fact that En (−x) = −En (x) and the linearity of Bk again yields the claimed bound. Therefore, suppose max{0, x} ̸= 0 and max{0, −x} ̸= 0 and write x = αx+ − βx− with x± ∈ ∆IN and α, β ≥ 0 with α + β = ∥x∥1 = 1 (explicitly, αx+ = max{0, x} and α = ∥ max{0, x}∥1 , and similarly for βx− ). By construction of En , if (N+ , N− ) ∼ Multinom(2, n, (α, β)) then we have N+ N− d En (x) = EN+ (x+ ) − EN− (x− ) , (31) n n where EN+ (x+ ) and EN− (x− ) are independent. Conditioning on (N+ , N− ) and applying the above argument to x+ and x− separately, we get " # r p N− 1 1 √ 2 N+ 1 p p + ≤√ α+ β ≤ , EEn W1 (Bk (x), Bk ◦ En (x)) ≤ E(N+ ,N− ) n n n n N+ N− as claimed. Next, we prove the bound (26) from Theorem 4.2(2) using an explicit coupling between Bk (x) and Bk ◦ Bn (x). Along the way, we prove a bound between x and an appropriate zero-padding of the binned Bn (x), to be used in the proof of Theorem 4.5. 32
Lemma 4.14. Suppose (In ) has degree D. For any x ∈ RIN and any N ∈ N, we have r 2D(3D − 1) EBn W1 (Bk (x), Bk ◦ Bn (x)) ≤ ∥x∥1 . n Also, there is a random injection Φ : [n] → [N ] coupled to Bn satisfying E∥x−β(Φ)Bn (x)∥2 ≤ ∥x∥1
q
2D(3D−1) . n
FM P Proof. Since (In ) has degree D, write In = m=1 [n]dm /Hm with D = maxm dm , and write x = α∈IN xα eα where (eα ) is the standard basis for RIN . After zero-padding x, we may assume that N ≥ n. Let Fk : [N ] → [k] and Fn : [N ] → [n] be uniformly random maps, so that X X xα eθ(Fk )(α) . xα eθ(Fn )(α) , Bk (x) = Bn (x) = α∈IN
α∈IN
We proceed to construct a coupling of Bk ◦ Bn (x) and of Bk (x) for a fixed realization of Fn . We do so by constructing a map Gk,n : [n] → [k] depending on Fk and Fn such that the distribution of Gk,n given Fn is uniform on the set of all maps from [n] to [k], and such that Gk,n ◦ Fn is equal to Fk on the most “important” d
d
indices, which we proceed to formalize. Once we do so, we get β(Fk )x = Bk (x) and β(Gk,n ◦Fn )x = Bk ◦Bn (x) for any realization of Fn , yielding the desired coupling. If α = H(i1 , . . . , id ) for H ⊆ Sd we write supp(α) = {i1 , . . . , id } ⊆ [N ] for the set of distinct indices appearing in α. Note that this is well-defined as H acts by permuting coordinates in a tuple, and that each α ∈ IN has this form for some d and H. We now define the weight associated to i ∈ [N ] by X wi = |xα |, (32) α∈IN i∈supp(α)
PN so that i=1 wi ≤ D∥x∥1 as each α ∈ IN contains at most D indices in its support. Using these weights, for each ℓ ∈ [n] we choose a representative ρ(ℓ) ∈ Fn−1 (ℓ) with the largest weight, breaking ties by choosing the smallest such index. Formally, we set ) ( ρ(ℓ) = min i ∈ Fn−1 (ℓ) : wi =
max
i′ ∈Fn−1 (ℓ)
wi′
,
if Fn−1 (ℓ) ̸= ∅ and set ρ|[n]\Fn ([N ]) to be an arbitrary injective map [n] \ Fn ([N ]) → [N ] \ ρ(Fn ([N ])). We thus get a random (depending only on Fn ) injective map ρ : [n] → [N ]. We then define Gk,n : [n] → [k] by setting Gk,n (ℓ) = Fk (ρ(ℓ)), (33) so we map ℓ ∈ [n] to the image under Fk of a largest-weight element in the fiber Fn−1 (ℓ). Note that Gk,n is indeed a uniformly random map from [n] to [k] conditioned on Fn , since ρ is always injective and since Fk maps distinct inputs to independent and uniform elements in [k]. Thus, we have q EBn W1 (Bk (x), Bk ◦ Bn (x)) ≤ E∥β(Fk )x − β(Gk,n ◦ Fn )x∥2 ≤ E∥β(Fk )x − β(Gk,n ◦ Fn )x∥22 . (34) We turn to analyzing the squared 2-norm of the difference X β(Fk )x − β(Gk,n ◦ Fn )x = xα δα , where δα = eθ(Fk )(α) − eθ(Gk,n ◦Fn )(α) . α∈IN
Explicitly, if α = H(i1 , . . . , id ) then δα = eH(Fk (i1 ),...,Fk (id )) − eH(Fk ◦ρ◦Fn (i1 ),...,Fk ◦ρ◦Fn (id )) . Consider ⟨δα , δβ ⟩ for α, β ∈ IN . Cauchy–Schwarz gives |⟨δα , δβ ⟩| ≤ 2. We further claim that E[⟨δα , δβ ⟩|Fn ] = 0
under the following two conditions on α, β, 33
namely, and
ρ ◦ Fn (i) = i for all i ∈ supp(α) ∩ supp(β),
(A)
Fn (i) ̸= Fn (i′ ) for all distinct i, i′ ∈ supp(α) ∪ supp(β).
(B)
Indeed, if (A) and (B) hold and we further condition on the variables V = {Fk (i) : i ∈ supp(β) or ρ(Fn (i)) = i}, we have
i h E ⟨δα , δβ ⟩ Fn , V = E δα |Fn , V , δβ ,
because V includes all random indices Fk (i) appearing in δβ . Furthermore, if α = H(i1 , . . . , id ) then d
conditioned on V.
(Fk (i1 ), . . . , Fk (id )) = (Fk ◦ ρ ◦ Fn (i1 ), . . . , Fk ◦ ρ ◦ Fn (id ))
That is because either ρ ◦ Fn (ij ) = ij , or ρ ◦ Fn (ij ) ̸= ij in which case both Fk (ij ) and Fk ◦ ρ ◦ Fn (ij ) are not in V (since ij ∈ / supp(β) by (A)), so both are uniformly distributed over [k] and independent for different ij (because Fn (ij ) are all distinct by (B)). Thus, we conclude that E[δα |Fn , V ] = 0 and hence E[⟨δα , δβ ⟩|Fn ] = 0 if the events (A) and (B) hold. The above argument shows that E|⟨δα , δβ ⟩| ≤ 2P[not (A) or not (B)] ≤ 2 P[ρ ◦ Fn (i) ̸= i for some i ∈ supp(α) ∩ supp(β)] (35) + P[Fn (i) = Fn (i′ ) for some i ̸= i′ ∈ supp(α) ∪ supp(β)] . We proceed to bound each probability separately. First, we have X
P[ρ ◦ Fn (i) ̸= i for some i ∈ supp(α) ∩ supp(β)] ≤
P[ρ ◦ Fn (i) ̸= i]
i∈supp(α)∩supp(β)
≤
X
P[there is j ∈ [N ] \ {i} s.t. wj ≥ wi and Fn (j) = Fn (i)].
i∈supp(α)∩supp(β) 1 Let Si = {j ∈ [N ] \ {i} : wj ≥ wi } and note that |Si | ≤ D∥x∥ wi . Indeed, note that X X wi |Si | ≤ wj ≤ wj ≤ D∥x∥1 .
j∈Si
j∈[N ]
Therefore, P[there is j ∈ [N ] \ {i} s.t. wj ≥ wi and Fn (j) = Fn (i)] ≤
X
P[Fn (j) = Fn (i)] ≤
j∈Si
D∥x∥1 |Si | ≤ , n wi n
since Fn is uniformly random. Thus, we have the following bound on the first probability in (35) P[ρ ◦ Fn (i) ̸= i for some i ∈ supp(α) ∩ supp(β)] ≤
D∥x∥1 n
X i∈supp(α)∩supp(β)
1 . wi
For the second probability in (35), note that |supp(α) ∪ supp(β)| ≤ 2D, so P[Fn (i) = Fn (i ) for some i ̸= i ∈ supp(α) ∪ supp(β)] ≤ ′
′
2D 2
n
=
D(2D − 1) . n
Using the above bounds, we have E∥β(Fk )x − β(Gk,n ◦ Fn )x∥22 ≤
X
|xα xβ | · E|⟨δα , δβ ⟩|
α,β∈IN
2D∥x∥1 X ≤ |xα xβ | n α,β∈IN
X i∈supp(α)∩supp(β)
34
1 2D(2D − 1) + wi n
(36) X α,β∈IN
|xα xβ |.
The second term in (36) is simply 2D(2D−1) ∥x∥21 . For the first term, we interchange the sums to obtain n 2
X α,β∈IN
=
X
|xα xβ |
N X
i∈supp(α)∩supp(β)
N X 1 1 = wi w i i=1
X α,β∈IN i∈supp(α)∩supp(β)
|xα xβ | =
N X 1 wi i=1
X α∈IN i∈supp(α)
|xα |
wi ≤ D∥x∥1 ,
i=1
by definition of wi in (32). Putting everything together, we get E∥β(Fk )x − β(Gk,n ◦ Fn )x∥22 ≤
2D2 ∥x∥21 2D(2D − 1)∥x∥21 2D(3D − 1)∥x∥21 + = , n n n
giving the first claimed bound by (34). For the second claimed bound, we consider a large k in the above coupling. Specifically, for k ≥ N the −1) map Fk : [N ] → [k] is injective with probability at least 1 − N (N , in which case 2k ∥β(Fk )x − β(Gk,n ◦ Fn )x∥2 = ∥β(Fk )(x − β(ρ ◦ Fn )x)∥2 = ∥x − β(ρ ◦ Fn )x∥2 . Thus, we have h i N (N − 1) 1− E∥x − β(ρ ◦ Fn )x∥2 ≤ E ∥β(Fk )x − β(Gk,n ◦ Fn )x∥2 Fk injective P[Fk injective] 2k r 2D(3D − 1) ≤ E∥β(Fk )x − β(Gk,n ◦ Fn )x∥2 ≤ ∥x∥1 . n Taking k → ∞ and recalling that ρ is injective, we obtain the second claimed bound. We are ready to prove Theorem 4.2. Proof (Theorem 4.2). For the first part, the expectation bounds follow from Lemma 4.13 and the fact that supn supx∈Ωn ∥x∥1 ≤ r. The claim subgaussianity follows from the bounded-difference inequality. Indeed, by Lemma 4.11 we can replace En (x) by En (x) without changing the distributions in question, and observe that En (x) is a function of n iid indices sampled from x by construction in Section 2.3.2, and changing any one of them affects two entries in En (x) by at most r/n. For the second part, the bound (26) follows from Lemma 4.14, and the bound on Edsamp (x, Bn (x)) then follows by the definition (1) of the sampling metric. We turn to proving Theorem 4.3 by combining Proposition 2.7 and a dual de Finetti theorem from [15]. Proof (Theorem 4.3). Propositions 2.13 and 2.14 show that if µn = Law(Bn (X)) for random X ∈ Ω∞ independent of Bn , then (µn ) is equipartition-consistent. Conversely, if (µn ) is equipartition-consistent then i→∞ by [15, Thm. 4.20] there is a sequence (νi ∈ P(Ω∞ )) such that Law(Bn (Xi )) −−−→ µn weakly for each n, where Xi ∼ νi is independent of Bn . This implies that (νi ) converges weakly with respect to dsamp to some µ∞ ∈ P(Ω∞ ) satisfying the claimed sampling representation. The uniqueness of such µ∞ and the extremality of sequences of the form (Law(Bn (x))) for x ∈ Ω∞ both follow from Proposition 2.7, which applies by Theorem 4.2. Specifically, Theorem 4.2 shows that Edsamp (x, Bn (x)) → 0 as n → ∞ at a universal rate for all x ∈ Ω∞ . If x ∈ Ω∞ then we can write x = limi xi for xi ∈ Ω∞ , so Bn (x) is the weak limit of Bn (xi ). The triangle inequality shows that Edsamp (x, Bn (x)) → 0 at the same universal rate, so the condition (7) in Proposition 2.7 is satisfied. Next, we use Theorem 4.2 to prove the sketching and generalization rates in Theorem 4.5. The following proof is similar to the proof of Theorem 3.7.
35
Proof (Theorem 4.5). First suppose f is L-Lipschitz with respect to dsamp . Then √ Lr( 2 + 2ϵ) √ , |f (x) − f (En (x))| ≤ Ldsamp (x, En (x)) ≤ n
(37)
2
with probability at least 1 − e−2ϵ by Theorem 4.2(1). The same theorem gives r 2 |f (x) − Ef (En (x))| ≤ LEdsamp (x, En (x)) ≤ Lr . n
(38)
Second, if f is L-Lipschitz with respect to (x, y) 7→ W1 (Bk (x), Bk (y)), then Theorem 4.2(1) gives the bounds (37) and (38) using the same arguments. Now suppose f is unchanged by zero-padding and that each restriction f |Vn is L-Lipschitz in 2-norm. Then by Lemma 4.11 we have |f (x) − f (En (x))| = |f (x) − f (En (x))| ≤ L∥x − En (x)∥2 ≤
Lr(1 + 2ϵ) √ , n
2
with probability at least 1 − e−2ϵ , where the last inequality follows from (27) and the fact that ∥x − En (x)∥2 2 Lr . and the latter is 4rn -subgaussian. Likewise, it follows from (27) that |f (x) − Ef (En (x))| ≤ √ n We have thus proved the claimed sketching rates under all the three conditions in Theorem 4.5. To obtain b the generalization F rates, let f, f satisfy either of the three conditions in the theorem (possibly different ones) and fix any x ∈ n Ωn . If m = ⌊n/D⌋, then Em (x) ∈ ΩmD ⊆ Ω≤n , and hence s 2 b b b b . |f (x) − f (x)| ≤ |f (x) − Ef (Em (x))| + |Ef (Em (x)) − Ef (Em (x))| + |Ef (Em (x)) − f (x)| ≤ en + 2Lr ⌊n/D⌋ Finally, suppose (µn ) is equipartition-consistent. By Theorem 4.3, there is a measure µ ∈ P(Ω∞ ) such that µn = Law(Bn (X)) for X ∼ µ independent of Bn . Arguing as above, we have eµ∞ = E|f (X) − fb(X)| ≤ EX |f (X) − EBn f (Bn (X))| + E|f (Bn (X)) − fb(Bn (X))| r 2D(3D − 1) b b + EX |EBn f (Bn (X)) − f (X)| ≤ eµn + 2Lr , n using Lemma 4.14 (together with a limiting argument to handle limit objects, like in the proof of Theorem 4.3 above). This is the last claimed bound. We now apply Theorem 4.5 to analyze the DeepSets-like functions from Corollary 4.7. Proof (Corollary 4.7). The first claim follows from the observation that if x, y ∈ Vn then X X p √ |f (x) − f (y)| ≤ Lσ ∥ρ(xi ) − ρ(yi )∥ ≤ Lσ Lρ ∥xi − yi ∥2 ∥xi ∥1 + ∥yi ∥1 ≤ Lσ Lρ 2r∥x − y∥2 . i
i
1 1 1 1 For the second claim, consider the sequence x(n) = ( 2n e1 , . . . , 2n e1 , − 2n e1 , . . . , − 2n e1 ) ∈ V2n , where both d
entries are repeated n times. Note that x(n) → 0 in sampling metric. Indeed, we have Bk (x(n) ) = Nk N1 1 ′ 1 1 ′ ⊤ ⊤ ⊤ 2n Bk (1n e1 ) − 2n Bk (1n e1 ) where Bk , Bk are independent. Since Bk ( n 1n e1 ) = ( n e1 , . . . , n e1 ) where P k (N1 , . . . , Nk ) ∼ Multinom(n, k, 1k /k), we get E∥Bk (x(n) )∥22 = 12 i=1 Var(Ni /n) = 1−1/k 2n , proving that (n) (n) Bk (x ) → 0 weakly for each k. However, we have f (x ) ≡ 1 for all n, proving that f is discontinuous in sampling metric. We turn to proving Corollary 4.9 analyzing certain graph neural networks.
36
Proof (Corollary 4.9). It is easy to verify that f is unchanged by zero-padding. If ∥A∥1 + ∥X∥1 ≤ r, we have ∥F (A, X) − F (B, Y )∥2 ≤ ∥A − B∥2 + Lσ
D X
Ad XΘd −
d=0
≤ ∥A − B∥2 + Lσ
D X
D X
B d Y Θd
d=0
2
∥Ad XΘd − Ad Y Θd ∥2 + ∥Ad Y Θd − B d Y Θd ∥2
d=0
≤ ∥A − B∥2 + Lσ
D X
∥A∥d2 ∥Θd ∥op ∥X − Y ∥2 +
d=0
≤
Lσ
D X
r ∥Θd ∥op
∥X − Y ∥2 +
1 + Lσ
d=0
≤
1 + Lσ
∥Ad − B d ∥op ∥Y ∥2 ∥Θd ∥op
d=0
! d
D X
D X
! d
dr ∥Θd ∥op
∥A − B∥2 ,
d=0 D X
d
r ∥Θd ∥op + Lσ
d=0
D X
! d
{z
|
∥(A, X) − (B, Y )∥2 .
dr ∥Θd ∥op
d=0
}
=L(r)
Finally, note that if ∥A∥1 + ∥X∥1 ≤ r, then D D √ X √ X ∥Θd ∥1 ∥Ad ∥1 ∥X∥1 ≤ r + Lσ d rd+1 ∥Θd ∥1 . ∥F (A, X)∥1 ≤ ∥A∥1 + Lσ d d=0
d=0
Denoting the last bound above by R(r), after j applications of F (A, X) we have ∥F ◦jp (A, X)∥1 ≤ R◦j (r), Qℓ ◦(j−1) ◦ℓ and hence is Lipschitz with constant j=1 L(R (r)). Since f = P ◦ F and P is Lρ 2R◦ℓ (r)-Lipschitz ◦ℓ in 2-norm on the 1-norm ball of radius R (r) by Corollary 4.7(1), we obtain the claim. Finally, we prove Proposition 4.10 showing that convergence of species samples is equivalent to joint convergence of the random binnings of positive and negative parts. To this end, we shall need the following two lemmas. The first lemma is an analog of the first bound in Theorem 4.2(1) with the roles of random binning and species sampling reversed. Lemma 4.15. Let (In ) be a compatible sequence of degree D and let x ∈ RIN with x ≥ 0. Then EBn W1 (Ek (x), Ek ◦ Bn (x)) ≤ ∥x∥1
kD(kD − 1) . n
Proof. By homogeneity of Ek and Ek ◦ Bn , it suffices to prove the claim for x ∈ ∆IN . After zero-padding x if needed, we may assume that N ≥ kD. Fix a realization Fn,N : [N ] → [n] of a uniformly random map, so d
Bn (x) = β(Fn,N )x. Pk Following the construction in Section 2.3.2, sample α1 , . . . , αk ∈ IN from x, define Ek (x) = k1 i=1 eαi , Sk and let t1 , . . . , tℓ be a random enumeration of S = i=1 supp(αi ) ⊆ [N ], where ℓ ≤ kD and if α = H(j1 , . . . , jd ) for some H ⊆ Sd we denote supp(α) = {j1 , . . . , jd }. Recall from the proof of Lemma 4.12 that d
θ(Fn,N )(α1 ), . . . , θ(Fn,N )(αk ) are iid samples from β(Fn,N )x, so β(Fn,N )Ek (x) = Ek (β(Fn,N )x). If Fn,N is injective on the random and independent set S, then a uniformly random enumeration of Sk Ik to be i=1 supp(θ(Fn,N )(αi )) = Fn,N (S) is given by Fn,N (t1 ), . . . , Fn,N (tℓ ). Setting Xk , Yk ∈ ∆ k
(Xk )H(i1 ,...,id ) = Ek (x)H(ti1 ,...,tid ) =
1X 1[αi = H(ti1 , . . . , tid )], k i=1 k
(Yk )H(i1 ,...,id ) = [β(Fn,N )Ek (x)]H(Fn,N (ti1 ),...,Fn,N (tid )) =
37
1X 1[θ(Fn,N )(αi ) = H(Fn,N (ti1 ), . . . , Fn,N (tid ))], k i=1
d
d
for each H(i1 , . . . , id ) ∈ Ik . If Fn,N is injective on S, then Xk = Ek (x), Yk = Ek (β(Fn,N )x), and Xk = Yk because αi = H(ti1 , . . . , tid ) if and only if θ(Fn,N )(αi ) = θ(Fn,N )H(ti1 , . . . , tid ) = H(Fn,N (ti1 ), . . . , Fn,N (tid )). If Fn,N is not injective on S, let Xk and Yk be arbitrary couplings of Ek (x) and Ek (β(Fn,N )x), which always satisfy ∥Xk − Yk ∥2 ≤ ∥Xk ∥1 + ∥Yk ∥1 = 2. We conclude that kD kD(kD − 1) 2 EBn W1 (Ek (x), Ek ◦ Bn (x)) ≤ 2P[Fn,N not injective on S] ≤ 2 = , n n as claimed. We proceed to relate convergence with respect to species sampling and random binning. Lemma 4.16. Let (In ) be a compatible sequence of finite degree, set Vn = RIn , and let (xi ) ⊆
F
n Vn .
1. If (Ek (xi )) converges weakly for each k, then (Bk (xi )) converges weakly for each k. 2. If (Bk (xi )) converges weakly for each k and xi ≥ 0 for all i, then (Ek (xi )) converges weakly for each k. Proof. For the first claim, suppose (En (xi ))i converges weakly for each n. In particular, the sequence of norms ∥xi ∥1 = |E1 (xi )| converges, so we can find r > 0 such that supi ∥xi ∥1 ≤ r. Choose ϵ > 0 and n ≥ 2(r/ϵ)2 . By Skorokhod’s representation theorem, we can find a coupling (Xi,n )i of (En (xi ))i converging almost surely. For any k, i, j ∈ N, we then have W1 (Bk (xi ), Bk (xj )) ≤ EEn W1 (Bk (xi ), Bk ◦ En (xi )) + EXi,n ,Xj,n W1 (Bk (Xi,n ), Bk (Xj,n )) + EEn W1 (Bk ◦ En (xj ), Bk (xj )) ≤ 2ϵ + E∥Bk (Xi,n − Xj,n )∥2 , by Theorem 4.2(1) and our choice of n, where in the last line Bk is independent of Xi,n , Xj,n . Noting that ∥Bk (Xi,n − Xj,n )∥2 ≤ ∥Xi,n − Xj,n ∥1 → 0 almost surely, we have lim supi,j→∞ W1 (Bk (xi ), Bk (xj )) ≤ 2ϵ for any ϵ > 0, and hence that (Bk (xi )) converges for each k. This proves the first claim. Now interchange the roles of species sampling and random binning, using Lemma 4.15 instead of Theorem 4.2(1). We conclude that if (Bn (xi ))i converges for each n, then W1 (Ek (xi ), Ek (xj )) ≤ 2ϵ + EXi,n ,Xj,n W1 (Ek (Xi,n ), Ek (Xj,n )), where (Xi,n )i is an almost-surely convergent coupling of (Bn (xi )). Since Xi,n ≥ 0, either Xi,n → 0 in which case W1 (Ek (Xi,n ), Ek (Xj,n )) → 0, or limi ∥Xi,n ∥1 > 0, in which case W1 (Ek (Xi,n ), Ek (Xj,n )) ≤∥Xi,n ∥1 W1 (Ek (Xi,n /∥Xi,n ∥1 ), Ek (Xj,n /∥Xj,n ∥1 )) + ∥Xi,n ∥1 − ∥Xj,n ∥1 . Both terms converge to zero almost surely, the second because (∥Xi,n ∥1 = ∥B1 (xi )∥1 )i converges, and the first because W1 (Ek (x), Ek (y)) ≤ k∥x − y∥1 for x, y ∈ ∆In . This can be seen by noting that 12 ∥x − y∥1 is the total variation distance between the distributions defined by x and y on In , so there is a coupling between k iid samples from these distributions that are equal with probability at least 1 − k2 ∥x − y∥1 . Applying this fact to the construction of Ek (x) and Ek (y) from Section 2.3.2 yields the claimed bound. We are ready to prove Proposition 4.10. Proof (Proposition 4.10). Define a new compatible sequence (Jn = In ⊔ In ), consisting of two disjoint copies n of the original one. Note that its degree is also D. We have maps S : RIn → RJ + into nonnegative vectors d
In n sending x 7→ (x+ , x− ), and Q : RJ sending (y, z) 7→ y − z. Observe that Ek (x) = Q ◦ Ek ◦ S(x) + → R IN for any x ∈ R and any N by construction in Section 2.3.2. Indeed, the empirical sample Ek (x) = ∥x∥1 sign(x) ⊙ Ek (|x|/∥x∥1 ) can equivalently be formed by sampling k iid elements (α1 , s1 ), . . . , (αk , sk ) from the distribution (x+ , x− )/∥x∥1 on Jn , where si = 1 if αi is sampled from x+ and si = −1 if it is sampled Pk d d from x− . We then have Q ◦ Ek ◦ S(x) = k1 i=1 si eαi = Ek (x). Relabelling the sampled αi randomly as in (15) shows that the same identity holds for Ek instead of Ek .
38
We conclude that (Ek (xi ))i converge weakly if and only if (Q ◦ Ek ◦ S(xi ))i converges weakly. Since Ek ◦ S(xi ) = (Yi , Zi ) and the supports of Yi and Zi are disjoint almost surely, we have Ek ◦ S(xi ) = S ◦ Q ◦ Ek ◦ S(xi ) for all i, so (Q ◦ Ek ◦ S(xi ))i converges weakly if and only if (Ek ◦ S(xi ))i converges weakly. In turn, since S(xi ) ≥ 0, we conclude by Lemma 4.16 that (Ek ◦ S(xi ))i converges weakly for all k if and d
− + − only if (Bk ◦ S(xi ))i converges weakly for all k. Finally, observe that Bk (x+ i , xi ) = (Bk (xi ), Bk (xi )) by construction of random binning in (5) (see also Section 2.3.1).
5
Conclusions
We have considered the closely-related problems of generalization and sketching of any-dimensional functions. To tackle these problems, we compare objects of different sizes by comparing distributions of their random samples. By using the right sampling maps, depending on the application domain and the relations between inputs of different sizes there, we obtain rich families of compact sets on which we get uniform rates for generalization and sketching, and a correspondence between limit objects and any-dimensional data distributions. Focusing on specific generalizations of sampling with replacement, random binning, and species sampling, we then obtain precise quantitative rates for approximation, sketching, and generalization. Some of the function classes for which our framework applies include polynomials, permutation-invariant transformers, and several neural network architectures defined for sets, point clouds, and graphs of all sizes. We end with a few directions for future work. (Distributions of species samples) Can we characterize the collection of sequences (Law(Ek (X)))k for random X in terms of the relations of these distributions across dimensions, analogously to Theorems 3.4 and 4.3? These sequences of distributions include random partitions of integers [8–11] and edge-exchangeable random graph models [13, 55]. (Other sampling maps) While we focused on three particular notions of sampling in this paper, there are other notions that might be appropriate for different applications. For example, in the context of natural language sentences, which are not permutation-invariant, is there a different notion of sampling that can summarize long sentences by short ones? (Set-based summaries) In this paper, we consider summarizing objects using random sampling, and comparing these random summaries in Wasserstein distance. Another type of summary studied in the context of certain graph limits involves summarizing an object by forming sets consisting of all possible projections of it, suitably defined, and comparing these sets in Hausdorff distance, see [12, Chap. 12] and [28] for example. Can we develop a general framework and rates for such summaries?
Acknowledgements The authors were supported in part by AFOSR grant FA9550-23-1-0070 and by NSF grant DMS-2502377. Some ideas in the proofs of Proposition 2.15(1), Theorem 4.2(2), and Proposition 4.10 were suggested by the ChatGPT 5.5 Thinking model. This work was conducted while EL was at the department of Computing and Mathematical Sciences at Caltech.
References [1] László Lovász and Balázs Szegedy. Limits of dense graph sequences. Journal of Combinatorial Theory, Series B, 96(6):933–957, 2006. [2] C. Borgs, J.T. Chayes, L. Lovász, V.T. Sós, and K. Vesztergombi. Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing. Advances in Mathematics, 219(6):1801– 1851, 2008. [3] Persi Diaconis and Svante Janson. Graph limits and exchangeable random graphs. arXiv preprint arXiv:0712.2749, 2007. 39
[4] Romain Abraham, Jean-François Delmas, and Julien Weibel. Probability-graphons: Limits of large dense weighted graphs. Innovations in Graph Theory, 2:25–117, March 2025. [5] Graham Cormode and S. Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1):58–75, 2005. [6] Qinfeng Shi, James Petterson, Gideon Dror, John Langford, Alex Smola, and SVN Vishwanathan. Hash kernels for structured data. Journal of Machine Learning Research, 10(11), 2009. [7] Mohammad Hossein Yassaee, Mohammad Reza Aref, and Amin Gohari. Achievability proof via output statistics of random binning. IEEE Transactions on Information Theory, 60(11):6760–6786, 2014. [8] Abel Rodriguez and Peter Müller. Nonparametric bayesian inference. In NSF-CBMS Regional Conference Series in Probability and Statistics, volume 9, pages i–110. JSTOR, 2013. [9] Jim Pitman. Exchangeable and partially exchangeable random partitions. Probability theory and related fields, 102(2):145–158, 1995. [10] J. F. C. Kingman. The representation of partition structures. Journal of the London Mathematical Society, s2-18(2):374–380, 10 1978. [11] John Frank Charles Kingman. Random partitions in population genetics. Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 361(1704):1–20, 05 1978. [12] László Lovász. Large networks and graph limits, volume 60. American Mathematical Soc., 2012. [13] Eitan Levin and Venkat Chandrasekaran. Limits of weighted graphs via random quotients. arXiv preprint arXiv:2512.23149, 2025. [14] Vladimir Vapnik. The Nature of Statistical Learning Theory. Springer, 1999. [15] Eitan Levin and Venkat Chandrasekaran. Any-dimensional polynomial optimization via de Finetti theorems. arXiv preprint arXiv:2507.15632, 2025. [16] Eitan Levin, Yuxin Ma, Mateo Díaz, and Soledad Villar. On transferring transferability: Towards a theory for size generalization. arXiv preprint arXiv:2505.23599, 2025. [17] Takashi Furuya, Maarten V. de Hoop, and Gabriel Peyré. Transformers are universal in-context learners. In The Thirteenth International Conference on Learning Representations, 2025. [18] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. Deep sets. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. [19] Charles R. Qi, Hao Su, Kaichun Mo, and Leonidas J. Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), July 2017. [20] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61–80, 2009. [21] Christian Bueno and Alan Hylton. On the representation power of set pooling networks. Advances in Neural Information Processing Systems, 34:17170–17182, 2021. [22] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2019. [23] Luana Ruiz, Luiz Chamon, and Alejandro Ribeiro. Graphon neural networks and the transferability of graph neural networks. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1702–1712. Curran Associates, Inc., 2020. 40
[24] Tianyang Lin, Yuxin Wang, Xiangyang Liu, and Xipeng Qiu. A survey of transformers. AI Open, 3:111–132, 2022. [25] Qingsong Wen, Tian Zhou, Chaoli Zhang, Weiqi Chen, Ziqing Ma, Junchi Yan, and Liang Sun. Transformers in time series: a survey. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI ’23, 2023. [26] Sohir Maskey, Ron Levie, and Gitta Kutyniok. Transferability of graph neural networks: an extended graphon approach. Applied and Computational Harmonic Analysis, 63:48–83, 2023. [27] Sohir Maskey, Ron Levie, Yunseok Lee, and Gitta Kutyniok. Generalization analysis of message passing neural networks on large random graphs. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 4805–4817. Curran Associates, Inc., 2022. [28] Thien Le and Stefanie Jegelka. Limits, approximation and size transferability for gnns on sparse graphs via graphops. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 41305–41342. Curran Associates, Inc., 2023. [29] Yongchao Zhou, Uri Alon, Xinyun Chen, Xuezhi Wang, Rishabh Agarwal, and Denny Zhou. Transformers can achieve length generalization but not robustly. In ICLR 2024 Workshop on Mathematical and Empirical Understanding of Foundation Models, 2024. [30] Xinting Huang, Andy Yang, Satwik Bhattamishra, Yash Sarrof, Andreas Krebs, Hattie Zhou, Preetum Nakkiran, and Michael Hahn. A formal framework for understanding length generalization in transformers. In Y. Yue, A. Garg, N. Peng, F. Sha, and R. Yu, editors, International Conference on Learning Representations, volume 2025, pages 58095–58179, 2025. [31] Amirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, and Siva Reddy. The impact of positional encoding on length generalization in transformers. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 24892–24928. Curran Associates, Inc., 2023. [32] Andy Yang, Pascal Bergsträßer, Georg Zetzsche, David Chiang, and Anthony W Lin. Length generalization bounds for transformers. arXiv preprint arXiv:2603.02238, 2026. [33] Takashi Furuya, David Mis, Ivan Dokmanić, Maarten V de Hoop, and Matti Lassas. Function graph transformers universally approximate operators between function spaces. arXiv preprint arXiv:2605.17968, 2026. [34] Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-sequence functions? In International Conference on Learning Representations, 2020. [35] Mateo Díaz, Dmitriy Drusvyatskiy, Jack Kendrick, and Rekha R Thomas. Invariant kernels: Rank stabilization and generalization across dimensions. arXiv preprint arXiv:2502.01886, 2025. [36] Nicolas Fournier. Convergence of the empirical measure in expected wasserstein distance: nonasymptotic explicit bounds in Rd . ESAIM: Probability and Statistics, 27:749–775, 2023. [37] László Lovász and Balázs Szegedy. Szemerédi’s lemma for the analyst. GAFA Geometric And Functional Analysis, 17(1):252–270, 2007. [38] Olav Kallenberg. Foundations of modern probability. Springer, 1997. [39] Nelson Niu and David I. Spivak. Polynomial Functors: A Mathematical Theory of Interaction. London Mathematical Society Lecture Note Series. Cambridge University Press, 2025.
41
[40] Antonio Ortega, Pascal Frossard, Jelena Kovačević, José M. F. Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106(5):808– 828, 2018. [41] Pierre Cardaliaguet. Notes on mean field games. Technical report, Technical report, 2010. [42] Zhiyi Zhang and Michael Grabchak. Entropic representation and estimation of diversity indices. Journal of Nonparametric Statistics, 28(3):563–575, 2016. [43] P. Diaconis and D. Freedman. Finite Exchangeable Sequences. The Annals of Probability, 8(4):745 – 764, 1980. [44] Edwin Hewitt and Leonard J. Savage. Symmetric measures on cartesian products. Transactions of the American Mathematical Society, 80(2):470–501, 1955. [45] Evgenii Borisovich Dynkin. Classes of equivalent random quantities. Uspekhi Matematicheskikh Nauk, 8(2):125–130, 1953. [46] A. J. Stam. Distance between sampling with and without replacement. Statistica Neerlandica, 32(2):81– 91, 1978. [47] Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge university press, 2019. [48] Peter Bartlett. Theoretical statistics, lecture 14. https://www.stat.berkeley.edu/~bartlett/ courses/2013spring-stat210b/notes/14notes.pdf, 2013. [49] Andrei Nikolaevich Kolmogorov and Vladimir Mikhailovich Tikhomirov. ε-entropy and ε-capacity of sets in function spaces. Uspekhi Matematicheskikh Nauk, 14(2):3–86, 1959. [50] Ulrike von Luxburg and Olivier Bousquet. Distance-based classification with Lipschitz functions. Journal of Machine Learning Research, 5(Jun):669–695, 2004. [51] Takashi Furuya, Davide Murari, and Carola-Bibiane Schönlieb. Approximation theory for lipschitz continuous transformers. arXiv preprint arXiv:2602.15503, 2026. [52] Francesco Vaccarino. The ring of multisymmetric functions. Annales de l’Institut Fourier, 55(3):717– 731, 2005. [53] Richard P. Stanley and Sergey Fomin. Enumerative Combinatorics. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 1999. [54] Ian Grant Macdonald. Symmetric functions and Hall polynomials. Oxford university press, 1998. [55] Svante Janson. On edge exchangeable random graphs. Journal of statistical physics, 173(3):448–484, 2018.
42