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.

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 \((\mathbb{V}_n)\) 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 \(\mathbb{R}^d\). Here we set \(\mathbb{V}_n=\mathbb{R}^{d\times n}\) for a fixed \(d \in \mathbb{N}\) and growing \(n\).

• Weighted and directed graphs on \(n\) vertices, represented by their adjacency matrices. Here we set \(\mathbb{V}_n = \mathbb{R}^{n\times n}\) and let \(n\) grow.

In many applications, it is often the case that the objects of interest belong to some proper subset \(\Omega_n \subseteq \mathbb{V}_n\); for instance, an unweighted graph is precisely one whose adjacency matrix belongs to \(\Omega_n = \{0,1\}^{n \times n}\). In the sequel, we will see that various structural properties of this subset, and indeed of the disjoint union \(\bigsqcup_n \Omega_n \subseteq \bigsqcup_n \mathbb{V}_n\) of subsets containing objects of all possible sizes, play a central role in our framework.

In order to formulate the any-dimensional generalization problem precisely, let \(\Omega_{\leq n} = \bigsqcup_{i\leq n}\Omega_i\) be the set of objects of size at most \(n\). For two functions \(f,g \colon \bigsqcup_n \Omega_n \to \mathbb{R}\) defined on objects of all sizes, i.e., any-dimensional functions, define \(\mathrm{e}_n(f,g)=\sup_{x\in\Omega_{\leq n}}|f(x)-g(x)|\) to be the maximum discrepancy between \(f\) and \(g\) on objects of size \(n\), and \(\mathrm{e}_{\infty}(f,g)=\sup_n\mathrm{e}_n(f,g)\) to be the maximum discrepancy on objects of any size. We then investigate the following question:

Any-dimensional generalization: Under what conditions on \(\bigsqcup_n \Omega_n\) and on any-dimensional functions \(f,g : \bigsqcup_n \Omega_n \to \mathbb{R}\) do we have that: \[\lim_{n\to\infty} \mathrm{e}_n(f,g) = \mathrm{e}_{\infty}(f,g)?\] At what rate does this limit converge? Are there hypothesis classes of any-dimensional functions over which the convergence rate is uniform?

If \(\mathrm{e}_n(f,g)\) converges to \(\mathrm{e}_{\infty}(f,g)\) as \(n \rightarrow \infty\), then we can control the error \(\mathrm{e}_\infty(f, g)\) between a function \(f\) and its estimate \(g\) on objects of arbitrarily-large size by the error \(\mathrm{e}_n(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 \(\mathrm{e}_{\infty}(f,g)\) as a function of \(\mathrm{e}_n(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.

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 that we formalize the idea of an any-dimensional data distribution. Merely considering distributions \(\mu\) on \(\bigsqcup_n\Omega_n\) is not sufficient, since any such distribution will be concentrated on bounded-dimensional inputs because \(\sum_n\mu(\Omega_n)=1\). Instead, a more appropriate notion for any-dimensional data distributions is that of a weakly-convergent sequence of distributions \((\mu_n\in\mathcal{P}(\Omega_{\leq n}))\) supported on increasingly larger objects, as we show in Proposition 4.

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.

Any-dimensional sketching: Under what conditions on \(\bigsqcup_n \Omega_n\) and on an any-dimensional function \(f : \bigsqcup_n \Omega_n \to \mathbb{R}\) can we find a (potentially random) map \(\mathsf{S}_k\colon\bigsqcup_n\Omega_n\to\Omega_k\) satisfying \[\lim_{k\to\infty}\mathrm{e}_{\infty}(f, f\circ\mathsf{S}_k)=0\quad \textrm{almost surely?}\] 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 address the above two questions would require some way to evaluate similarity between objects of different sizes in \(\bigsqcup_n \Omega_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 and its sketch must be similar to each other. More precisely, we need a distance \(d\) between elements of \(\bigsqcup_n \Omega_n\) that allows us to quantitatively compare objects of different sizes and to consider any-dimensional functions that are continuous in \(d\). We show in Theorem 3 that precompactness of the metric space \((\bigsqcup_n \Omega_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 and compare objects of different sizes. Specifically, we fix a collection of random sampling maps \((\mathsf{S}_k\colon\bigsqcup_n \mathbb{V}_n \to \mathbb{V}_k)_{k\in\mathbb{N}}\), and we associate to each \(x \in \mathbb{V}_n\) the sequence of random variables \[x \mapsto \left(\mathsf{S}_k(x)\right)_{k\in\mathbb{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 \in \mathbb{V}_n\) for any \(n\)), and its output is a sequence of random variables taking values in the vector spaces \((\mathbb{V}_k)\). We then compare any two objects \(x,y\in\bigsqcup_n\mathbb{V}_n\) by comparing the distributions of their samples \(\mathsf{S}_k(x)\) and \(\mathsf{S}_k(y)\) of each size \(k\). To quantify this comparison, we define the sampling metric between \(x,y \in \bigsqcup_n \mathbb{V}_n\) by \[\label{eq:sampling95metric} d_{\mathrm{samp}}(x,y)=\sum_{k\geq 1}2^{-k}W_1(\mathsf{S}_k(x), \mathsf{S}_k(y)),\tag{1}\] where \(W_1\) denotes the Wasserstein-1 distance between two distributions of random variables² with respect to some norm on \(\mathbb{V}_k\), assumed to satisfy \(\sup_k\mathbb{E}\|\mathsf{S}_k(x)\|<\infty\) for each \(x\) so that \(d_{\mathrm{samp}}(x,y)<\infty\). The coefficients \(2^{-k}\) were chosen for convenience, and any other summable sequence would suit. An appropriately bounded sequence \((x_n)\) converges with respect to the sampling metric 1 if and only if the sequence of fixed-dimensional samples \((\mathsf{S}_k (x_n))_n\) converges weakly for each size \(k\), see Proposition 5. We next present several illustrations of sampling maps.

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 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-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-4 and unify their analysis by using maps between finite sets. To motivate our generalization, we note that any map \(f\colon[k]\to[n]\) between finite sets defines a (linear) map \(\rho(f)\colon\mathbb{R}^{d\times n}\to\mathbb{R}^{d\times k}\) extracting the columns \(f(1),\ldots,f(k)\) specified by \(f\), or more formally \([\rho(f) x]_i=x_{f(i)}\) for \(i\in[k]\) where subscripts index columns. Moreover, if we replace a fixed such map \(f\) by a uniformly random map \(F_{n,k} : [k] \mapsto [n]\), with each \(F_{n,k}(i)\) drawn independently and uniformly from \([n]\), then \(\rho(F_{n,k})\) is precisely the random map sampling \(k\) columns as in Example 1.

Likewise, a map \(f\colon[k]\to[n]\) acts on pairs by \((i,j)\mapsto(f(i),f(j))\), and therefore defines a (linear) map \(\rho(f)\colon\mathbb{R}^{n\times n}\to\mathbb{R}^{k\times k}\) between matrices indexed by these pairs via \([\rho(f)x]_{i,j}=x_{f(i),f(j)}\) for \(i,j\in[k]\). Once again, applying a uniformly random map \(\rho(F_{n,k})x\) recovers the vertex sampling map of Example 2.

More generally, we consider a sequence of index sets \((\mathcal{I}_n)\) along with actions \(\theta(f)\colon\mathcal{I}_k\to\mathcal{I}_n\) associated to each map \(f\colon[k]\to[n]\) between finite sets, and we assume that these actions satisfy certain compatibility conditions (see Definition 5). We then consider the sequence of vector spaces \((\mathbb{V}_n = \mathbb{R}^{\mathcal{I}_n})\) consisting of vectors indexed by \((\mathcal{I}_n)\), and associate a (linear) map \(\rho(f)\colon\mathbb{V}_n\to\mathbb{V}_k\) to each map \(f\colon[k]\to[n]\) between finite sets given by \[\label{eq:sampling95action} [\rho(f)x]_i=x_{\theta(f)(i)} \quad \textrm{for } x\in\mathbb{V}_n \textrm{ and } i\in\mathcal{I}_k.\tag{2}\] Finally, we define sampling with replacement maps \((\mathsf{R}_k)\) on these spaces by \[\label{eq:sampling95general} \mathsf{R}_k(x) = \rho(F_{n,k})x\quad \textrm{where } F_{n,k}\colon[k]\to[n] \textrm{ is uniformly random},\tag{3}\] and \(x \in \mathbb{V}_n\). In this manner, we generalize sampling with replacement to more complicated objects such as graph signals (by setting \(\mathcal{I}_n=[n]^2\sqcup[n]\)), hypergraphs and tensors (by setting \(\mathcal{I}_n=[n]^d\)), and polynomials (by setting \(\mathcal{I}_n=[n]^d/\mathfrak{S}_d\) to be the collection of multisets of \([n]\) containing \(d\) elements, where \(\mathfrak{S}_d\) is the group of permutations on \(d\) letters permuting indices in a tuple). Our perspective enables a single unified analysis for general actions \(\theta\), 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\colon[n]\to[k]\) can be viewed as binning \(n\) indices into \(k\) bins, and defines a map \(\beta(f)\colon\mathbb{R}^{d\times n}\to\mathbb{R}^{d\times k}\) by binning columns in this way and summing the columns in each bin \([\beta(f) x]_i=\sum_{j\in f^{-1}(i)}x_j\). Applying a uniformly random map \(\beta(F_{k,n})\) in this way yields the random binning map of Example 3. More generally, we consider a sequence of index sets \((\mathcal{I}_n)\) with action \(\theta\) and associated sequence of vector spaces \((\mathbb{V}_n=\mathbb{R}^{\mathcal{I}_n})\) as above. We associate a (linear) map \(\beta(f)\colon\mathbb{V}_n\to\mathbb{V}_k\) to each map \(f\colon[n]\to[k]\) between finite sets via \[\label{eq:binning95action} [\beta(f)x]_i = \sum_{j\in\theta(f)^{-1}(i)}x_j \quad \textrm{for } x\in\mathbb{V}_n \textrm{ and } i\in\mathcal{I}_k.\tag{4}\] We remark that the above two maps \(\rho\) and \(\beta\) from 2 and 4 are adjoints of each other, in the sense that \(\beta(f)=\rho(f)^\star\) with respect to the usual inner products on \(\mathbb{R}^{\mathcal{I}_n}\). Finally, we define random binning maps \((\mathsf{B}_k)\) on these vector spaces by \[\label{eq:binning95general} \mathsf{B}_k(x) = \beta(F_{k,n})x\quad \textrm{where } F_{k,n}\colon[n]\to[k] \textrm{ is uniformly random},\tag{5}\] and \(x \in \mathbb{V}_n\). By varying the index sets \((\mathcal{I}_n)\), we generalize random binning to more general objects, and once again they can all be analyzed in a unified manner. For example, setting \(\mathcal{I}_n=[n]^2\) recovers the random quotients of graphs studied in [13].

Lastly, we generalize the species sampling map from Example 4. We consider a particular class of index sets \((\mathcal{I}_n)\) that can be derived from tuples \([n]^d\) (see Definition 6), and view vectors \(x\in\Delta^{\mathcal{I}_n}\) as distributions over the index sets \(\mathcal{I}_n\). We can then repeat the construction in Example 4 to form more general species sampling maps \((\mathsf{E}_k)\), see Section 2.3.2.

Given a sequence of index sets \((\mathcal{I}_n)\), we have defined three sampling maps on the same underlying vector spaces \(\mathbb{R}^{\mathcal{I}_n}\). 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\neq y\) possibly of different sizes with \(d_{\mathrm{samp}}(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 \((\mathsf{R}_k)\) as defined above, the distribution of \(\mathsf{R}_k(x)\) is unchanged if and only if we duplicate or permute the entries of \(x\), appropriately defined (see Propositions 8 and 9). For example, if \(x\in\mathbb{R}^{d\times n}\) and we permute the columns of \(x\) or duplicate them \(m\) times (so \(x\mapsto x\otimes\mathbb{1}_m^\top\)), then the distribution of \(\mathsf{R}_k(x)\) is unchanged for all \(k\in\mathbb{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 13.

For random binning \((\mathsf{B}_k)\) and species sampling \((\mathsf{E}_k)\), the distributions of \((\mathsf{B}_k(x))\) and \((\mathsf{E}_k(x))\) are unchanged if and only if we zero-pad or permute the entries of \(x\), again appropriately defined. For example, if \(x\in\mathbb{R}^n\) and we append \(k\) zeros to \(x\), then the distributions of \(\mathsf{B}_k(x)\) and \(\mathsf{E}_k(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 14.

Rates for Sampling with Replacement (Section 3)↩︎

We derive rates for any-dimensional sketching and generalization using the sampling metric 1 defined with respect to general sampling with replacement maps \((\mathsf{R}_k\colon\bigsqcup_n\mathbb{V}_n\to\mathbb{V}_k)\). To state our results, we fix a sequence of compact subsets \((\Omega_n \subseteq \mathbb{V}_n)\) such that \(\mathsf{R}_k (\bigsqcup_n \Omega_n) \subseteq \Omega_k\) almost surely for all \(k\), i.e., the subsets \(\Omega_n\) are closed under sampling with replacement. For example, the hypercubes \(\Omega_n=[-1,1]^n\subseteq\mathbb{R}^n\) and the collection of unweighted graphs \(\Omega_n=\{0,1\}^{n\times n}\subseteq\mathbb{R}^{n\times n}\) are closed under sampling with replacement.

The proof of these bounds relies on a concentration result in which we show that the distance \(d_{\mathrm{samp}}(x,\mathsf{R}_n(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 \(\widehat f\approx f\) on inputs of size \(n\), then \(\widehat f\approx 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 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 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 \(\Omega_n\) is the collection of \(n\times n\) adjacency matrices of simple graphs, a rate of \(\exp[-\frac{1}{2}\log\log n]\) was shown in [2] for the closely related cut metric as a consequence of Szemerédi’s regularity lemma (see [12] 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 \(\mathrm{Law}(\mathsf{R}_k(x))\) for some fixed \(k\).

We give two illustrations here of some of these improved rates in specific applications. The first pertains to polynomials that are unchanged by suitably-defined duplication of the entries of their inputs. Specifically, a function \(p\colon\bigsqcup_n\mathbb{V}_n\to\mathbb{R}\) is a polynomial if all the restrictions \(p|_{\mathbb{V}_n}\) are polynomials of some fixed degree, denoted \(\deg(p)\).

Examples of polynomials satisfying the above conditions are polynomials in moments of measures, graph homomorphism densities, and polynomial graph neural networks; see Corollary 3 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 \(\mathbb{R}^d\), and \(O((\log n)^{-1/4})\) for graph homomorphism densities; see [16].

The second consequence we highlight is to sketching and generalization for transformers.

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\in\mathbb{V}_N\) consisting of \(N\) tokens requires \(O(N^2)\) operations (see ?? ), but evaluating it to a desired accuracy \(\delta>0\) can be done with high probability in \(O(\delta^{-2d})\) time (independent of the number of tokens \(N\)) after sampling \(n=O(\delta^{-d})\) columns from \(x\) uniformly at random and using ?? .

Rates for Random Binning and Species Sampling (Section 4)↩︎

Next we present our results on any-dimensional sketching and generalization using the sampling metric \(d_{\mathrm{samp}}\) defined with respect to general random binning maps \((\mathsf{B}_k\colon\bigsqcup_n\mathbb{V}_n\to\mathbb{V}_k)\). Once again, we fix a sequence of compact subsets \((\Omega_n \subseteq \mathbb{V}_n)\) closed under sampling, this time under both random binning and under species sampling so \(\mathsf{B}_k (\bigsqcup_n \Omega_n) \subseteq \Omega_k\) almost surely for all \(k\) and similarly for \((\mathsf{E}_k)\). Examples include the simplex \(\Omega_n=\Delta^n\) and entrywise \(\ell_1\) balls.

As in Theorem 1, we would like to use the maps \((\mathsf{B}_k)\) for sketching high-dimensional inputs. The challenge with this approach is that the distance \(d_{\mathrm{samp}}(x,\mathsf{B}_n(x))\) does not concentrate as well as in the case of sampling with replacement (see Example 19). Fortunately, our generalization of the species sampling map \((\mathsf{E}_k)\) exhibits the requisite concentration, as \(d_{\mathrm{samp}}(x,\mathsf{E}_n(x))\) is \(c/n\)-subgaussian for a constant \(c > 0\) depending only on \((\Omega_n)\). Thus, species sampling furnishes the necessary sketching map.

In words, we always get \(n^{-1/2}\) rates for random binning, regardless of the complexity of the action \(\beta\) 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 2.

1. In analogy to Corollary 1, there is a large class of polynomial functions that are continuous with respect to random binning. Specifically, Theorem 16 applies to any polynomial \(p\colon\bigsqcup_n\mathbb{V}_n\to\mathbb{R}\) that is symmetric and unchanged by zero-padding, appropriately defined (Corollary 6). Such polynomials include multi-symmetric functions on sequences of vectors and homomorphism numbers for graphs of arbitrary size.

2. Many permutation-invariant neural network architectures are continuous with respect to random binning, including DeepSets [18] (Corollary 7), PointNet [19] (Corollary 8), and graph neural networks [20] (Corollary 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 19). See Section 4 for more details.

*** OLDER STUFF ***

Venkat: “Some general points:

• In first paragraph, need to make the point that while \(\Omega\) is typically easy to specify in most applications, the key challenge is that of providing a useful pseudometric \(d\).

• Related to above, should we discuss the sampling metric first, before giving definitions of any-dimensional approximation and generalization? There are several reasons why this may be more convenient.

• Should we change notation for dimension \(n\) to something else, so as to not confuse with sample size?

”

To frame our discussion concretely, we consider a sequence of sets \((\Omega_n)\) consisting of our objects of interest, with the index \(n\) specifying object size, e.g., graphs on \(n\) vertices, tokens of length \(n\), and so on. Let \(d \colon \bigsqcup_n\Omega_n \times \bigsqcup_n\Omega_n \to [0,\infty)\) be a pseudometric and suppose each \(\Omega_n\) is compact in \(d\). We say that two objects \(x,y \in \bigsqcup_n\Omega_n\) are equivalent \(x \sim y\) if \(d(x,y) = 0\). The flexibility provided by the pseudometric formalism will be useful for identifying equivalent objects such as isomorphic graphs. We then denote by \(\Omega_\infty = \bigsqcup_n\Omega_n / \sim\) the collection of objects of all sizes upto equivalence. Observe that \(d\) is a metric on \(\Omega_\infty\). Finally, let \(\Omega_{\leq n} = \bigsqcup_{i\leq n}\Omega_i / \sim\) be the set of objects of bounded size.

Venkat: “Should we give an example or two here to make things concrete? Right now, it feels a bit abstract and reads like a notation section. We could return to these several times throughout the introduction.”

With this setup, we state our first definition pertaining to any-dimensional approximation. Given a point \(x \in \Omega_\infty\) and a subset \(S \subseteq \Omega_\infty\), let \(\mathrm{dist}(x,S) = \inf_{y \in \Omega_\infty} d(x,y)\) be the distance from \(x\) to \(S\).

The any-dimensional approximation property states that objects of any size can be approximated by bounded-size objects. In particular, the order of the limit and the supremum highlights the any-dimensional nature of the definition, as approximability is required to hold uniformly over all objects of arbitrary size. Next we give our definition of any-dimensional generalization. For two functions \(f,g \colon \bigsqcup_n \Omega_n \to \mathbb{R}\) defined on objects of all sizes, i.e., any-dimensional functions, define \(\mathrm{e}_n(f,g)=\sup_{x\in\Omega_{\leq n}}|f(x)-g(x)|\) and \(\mathrm{e}_{\infty}(f,g)=\sup_n\mathrm{e}_n(f,g)\). Venkat: “Should \(\mathrm{e}_{\infty}\) be defined more directly as \(\mathrm{e}_{\infty} = \sup_{x\in\Omega_{\infty}}|f(x)-g(x)|\)? Also, is ‘error’ the right terminology here? Should we state something agnostic at this stage, such as ‘distance’?”

The any-dimensional generalization property implies that if the error between a target function \(f\) and its estimate \(\widehat f\) is small on bounded-size objects, then the error can be controlled on objects of arbitrary size. Specifically, training on bounded-size objects would then yield generalization to objects of arbitrary size.

At this stage, both of the above definitions are asymptotic in nature and do not have any formal consideration of rates. An important objective of our paper is to provide explicit rates for the quantities \(\sup_{x\in\Omega_{\infty}}\mathrm{dist}(x,\Omega_{\leq n})\) and \(\mathrm{e}_{\infty}(f,g) - \mathrm{e}_n(f,g)\) to decay towards zero, as functions of the size \(n\) of the fixed-size objects. To make progress on this question, we need a pseudometric \(d\) to compare objects of different sizes.

Venkat: “Given the pivot in the above paragraph to explicitly considering rates, should we tweak both definitions to highlight rates? Alternatively, should we move the definitions to Section 2 and only highlight the quantities \(\sup_{x\in\Omega_{\infty}}\mathrm{dist}(x,\Omega_{\leq n})\) and \(\mathrm{e}_{\infty}(f,g) - \mathrm{e}_n(f,g)\) here?”

In broad overview, our primary contribution in this paper is that a fruitful approach to represent an object is via an infinite sequence of distributions of subsamples of varying sizes. By defining an appropriate metric over such sequences, we obtain a natural method for comparing objects of different sizes. Formally, let \((\mathbb{V}_n)\) be a sequence of vector spaces with each \(\Omega_n \subseteq \mathbb{V}_n\). Given a collection of random sampling maps \((\mathsf{S}_k\colon\bigsqcup_n \mathbb{V}_n \to \mathbb{V}_k)_{k\in\mathbb{N}}\), we define the associated sampling metric by: \[d_{\mathrm{samp}}(x,y)=\sum_{k\geq 1}2^{-k}W_1(\mathsf{S}_k(x),\mathsf{S}_k(y)),\] where \(W_1\) denotes the Wasserstein distance between two probability measures.⁴

Contributions:

• Define the any-dimensional approximation and any-dimensional learning in uniform loss, both wrt metric on objects of all sizes.

• Explain equivalence with uniform approximation of objects.

• We compare objects of different sizes by comparing distributions of samples. Define sampling metric.

• This recovers topologies such as weak convergence of measures and of random partition models, as well as dense graph limits.

• More broadly, choice of sampling maps is dictated by application domain and in particular, relations between problem instances of different sizes and their symmetries.

• Data distributions should be sequences of distributions on increasingly-large inputs converging weakly

• Limit objects in sampling metric are naturally associated with a notion of data distributions [state theorem].

• We define and study two general notions for sampling: Sampling with replacement and random partitions. Define for \(\mathbb{R}^n\) and for \((\mathbb{R}^n)^{\otimes k}\). Appropriate for problems related by duplication / zero-padding (functions continuous in sampling metric are unchanged under permutations and either one of these embeddings)

• For each, we prove uniform rates in sampling metric. State \(\mathrm{dist}(x,\mathbb{V}_n)\) rates for \(\mathbb{V}_n=(\mathbb{R}^n)^{\otimes k}\), uniformly for \(x\in\Omega_{\infty}\) where \((\Omega_n)\) are compact closed under sampling.

• Relate rates to Szemeredi and to compactness, remark that slow rates are real.

• Remark: rates for approximation and learning for Lipschitz functions in sampling metric.

• We get better rates for approximation and sketching of subclasses of functions by using more precise sampling-based representations for functions. For example, functions of the form \(f(x)=\sigma(\mathbb{E}g_k(\mathsf{S}_kx))\) or more generally \(f(x)=F_k(\mathrm{Law}(\mathsf{S}_kx))\) for some finite \(k\).

Applications:

• Symmetric polynomial regression: \(O(1/n)\) rates when related by duplication, \(O(1/\sqrt{n})\) when related by zero-padding.

• \(O(1/\sqrt{n})\) generalization rates for DeepSets and PointNet

• \(O(n^{-\frac{1}{(K+1)(K+2)}})\) generalization for graphon NNs of order \(K\); \(O(1/\sqrt{n})\) rates for graph NNs.

• \(O(1/\sqrt{n})\) generalization and sketching for permutation-invariant transformers.

1.2 Our Contributions – Take Two↩︎

Comparing Inputs of Different Sizes via Sampling↩︎

In broad overview, our primary contribution in this paper is that a fruitful approach to represent an object is via an infinite sequence of distributions of subsamples of varying sizes. By defining an appropriate metric over such sequences, we then obtain a natural method for comparing objects of different sizes. Formally, let \((\mathbb{V}_n)\) be a sequence of vector spaces, with the index \(n\) specifying object size, e.g., adjacency matrices of graphs on \(n\) vertices, tokens of length \(n\), and so on. Given a collection of random sampling maps \((\mathsf{S}_k\colon\bigsqcup_n \mathbb{V}_n \to \mathbb{V}_k)_{k\in\mathbb{N}}\), we represent \(x \in \mathbb{V}_n\) as: \[x \mapsto \left(\mathrm{Law}(\mathsf{S}_k(x))\right)\] Observe that this map is well-defined for inputs of any size (i.e., \(x \in \mathbb{V}_n\) for any \(n\)) and it yields as output a sequence of probability measures defined on the sequence of vector spaces \((\mathbb{V}_k)\). We present next several sampling maps from the literature that will appear in various contexts throughout the paper.

Venkat: “It is nice that all of the preceding examples cleanly describe sampling as an operation on vector spaces. To do this for ‘random partition models’ in general (rather than just simplex vectors) seems to be cumbersome. So I did not include it here.”

To compare inputs of different sizes, we then define the sampling metric between \(x,y \in \bigsqcup_n \mathbb{V}_n\) by: \[d_{\mathrm{samp}}(x,y)=\sum_{k\geq 1}2^{-k}W_1(\mathsf{S}_k(x),\mathsf{S}_k(y)),\]Venkat: “Given that the sampling representation is stated as \(\mathrm{Law}(\mathsf{S}_k(x))\), should we insert ‘Law’ above too?” where \(W_1\) denotes the Wasserstein distance between two probability measures. The coefficients \(2^{-k}\) were chosen to be summable to \(1\), but any nonnegative and summable sequence would be suitable. In Example[REF], the sampling metric between \(x, y\) amounts to \(\sum_{k\geq 1}2^{-k} W_1(\mu_x^{\otimes k}, \mu_y^{\otimes k})\), where \(\mu_x, \mu_y\) are the empirical measures of \(x,y\); Venkat: “Say something about the topology induced by this metric”. In Example[REF], if one restricts the objects to unweighted and undirected graphs (i.e., adjacency matrices that are symmetric and consist of entries in \(\{0,1\}\)), then limits in the sampling metric correspond to dense graph limits [12]. Venkat: “Should we say instead that the topology induced is the same as that of graphons?” As we shall see, the sampling perspective is useful both analytically and methodologically, as it yields explicit rates for any-dimensional learning and also provides an associated algorithmic framework.

Which Sampling Maps?↩︎

To go beyond the preceding specific illustrations, we leverage a combinatorial perspective on sampling based on maps between finite sets that facilitates a significant generalization of Examples[REF].

To motivate our generalization, we observe that any map \(f\colon[k]\to[n]\) defines a linear map \(\rho(f)\colon\mathbb{R}^n\to\mathbb{R}^k\) extracting entries specified by \(f\). Formally for any \(x\in\mathbb{R}^n\) the entries of \(\rho(f)x\in\mathbb{R}^k\) are given by \((\rho(f)x)_i=x_{f(i)}\). Moreover, if \(F_{n,k}\colon[k]\to[n]\) is a uniformly random such map, so that \(F_{n,k}(1),\ldots,F_{n,k}(k)\overset{iid}{\sim}\mathrm{Unif}([n])\), then \(\rho(F_{n,k})x\) is precisely the vector obtained by sampling \(k\) coordinates from \(x\) uniformly at random with replacement as in Example[REF]. Similarly, any map \(f\colon[k]\to[n]\) acts on tuples \(f^{\times 2}\colon [k]^2\to[n]^2\) by \(f^{\times 2}(i,j)=(f(i),f(j))\), and hence acts linearly on matrices indexed by these tuples via \((\rho(f)X)_{i,j}=X_{f(i),f(j)}\). Once again, applying a uniformly random map \(\rho(F_{n,k})X\) recovers the vertex sampling map as in Example 6. These two examples can be generalized by having maps \(f\) between finite sets act on index sets, and hence act linearly via a suitable action \(\rho(f)\) on elements of vector spaces that are indexed by those index sets. Venkat: “Give one or two other examples that can be accommodated by this general perspective?”

Next we interpret random binning as in Example 7 by again using maps between finite sets. Specifically, any map \(f \colon [n]\to[k]\) defines a binning of \(n\) items into \(k\) bins, and acts on a vector \(x\in\mathbb{R}^n\) by binning its coordinates and summing all coordinates in a given bin, i.e., \((\tau(f)x)_i=\sum_{j\in f^{-1}(i)}x_j\). Observe that this action of maps between finite sets is dual to the one above on sampling with replacement, in the sense that \(\rho(f)=\tau(f)^\top\) as matrices. In this case, if \(F_{k,n}\colon[n]\to[k]\) is a uniformly random map then \(\tau(F_{k,n})x\) is the uniformly random binning of the coordinates of \(x\) considered in Example 7. As before, we shall generalize this notion of random binning beyond vectors. Venkat: “Mention some more examples here?”

Venkat: “Make the point that this combinatorial perspective that facilitates a unified analysis framework for any-dimensional learning that yields explicit rates for all sampling-based approaches that fall in the above two classes.”

Venkat: “What dictates the choice of sampling map? Maybe make the point distinct elements \(x, y \bigsqcup_n \Omega_n\), even of different sizes, can have \(d(x,y) = 0\)? Also, compatibility across dimensions? These would suggest that relations between dimensions matter...”

Any-Dimensional Learning and Data Distributions↩︎

In many applications, it is often the case that the objects of interest belong to some proper subset \(\Omega_n \subseteq \mathbb{V}_n\); for instance, graphs can often have nonnegative weights in \([0,1]\) so that \(\Omega_n = [0,1]^{n \times n}\). In the sequel, we will see that the compactness properties of this subset, and indeed of the collection \(\bigsqcup_n \Omega_n\), play a central role in any-dimensional learning. To frame our discussion concretely, we consider a sequence of subsets \((\Omega_n \subseteq \mathbb{V}_n)\) consisting of our objects of interest. It turns out that the sampling metric [REF] defines a pseudometric on \(\bigsqcup_n \Omega_n\). Venkat: “Should we cite a result for the preceding assertion? To be pedantic, we need to show triangle inequality for \(d_{\mathrm{samp}}\) based on the properties of the Wasserstein metric, right?” In particular, distinct elements \(x, y \bigsqcup_n \Omega_n\) can have \(d_{\mathrm{samp}}(x,y) = 0\) as discussed above. We therefore say that two objects \(x,y \in \bigsqcup_n\Omega_n\) are equivalent \(x \sim y\) if \(d_{\mathrm{samp}}(x,y) = 0\), and we denote by \(\Omega_\infty = \bigsqcup_n\Omega_n / \sim\) the collection of objects of all sizes upto equivalence. Observe that \(d_{\mathrm{samp}}\) is a metric on \(\Omega_\infty\).

To formulate the any-dimensional generalization question precisely, let \(\Omega_{\leq n} = \bigsqcup_{i\leq n}\Omega_i / \sim\) be the set of objects of bounded size. For two functions \(f,g \colon \bigsqcup_n \Omega_n \to \mathbb{R}\) defined on objects of all sizes, i.e., any-dimensional functions, define \(\mathrm{e}_n(f,g)=\sup_{x\in\Omega_{\leq n}}|f(x)-g(x)|\) and \(\mathrm{e}_{\infty}(f,g)=\sup_n\mathrm{e}_n(f,g)\).

Venkat: “State any-dimensional generalization question as showing that \(\mathrm{e}_{\infty}(f,g) - \mathrm{e}_n(f,g)\) goes to \(0\)?”

Venkat: “Instead of definition, how about we pose the any-dimensional approximation property as a question – i.e., we want to show that \(\sup_{x\in\Omega_{\infty}} \mathrm{dist}(x,\Omega_{\leq n})\) goes to \(0\) as \(n \rightarrow \infty\) in the sampling metric.”

The any-dimensional approximation property states that objects of any size can be approximated by bounded-size objects. In particular, the question highlights the any-dimensional nature of the property we seek, as approximability is required to hold uniformly over all objects of arbitrary size.

Highlight that compactness matters.

Venkat: “Give rates, perhaps building on earlier examples. Maybe also give some new ones?”

Venkat: “Question – where to fit in data distribution?”

Paper Outline↩︎

1.3 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 any-dimensional 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 2, see [12]. 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 mean-squared 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], and expected convergence rates for function values on low-dimensional samples of high-dimensional inputs [16]. Both assume access to sampling maps satisfying certain desiderata, verified case-by-case. In contrast, sampling maps are fundamental to our framework—we systematically 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 3. 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 2 with respect to a different but related metric.

1.4 Notation↩︎

We denote by \(\mathbb{N}\) the collection of strictly positive integers and by \(\mathbb{N}_0=\mathbb{N}\cup\{0\}\). For \(n\in\mathbb{N}\), we denote \([n]=\{1,\ldots,n\}\). We denote by \(\mathfrak{S}_n=\{\pi\colon[n]\to[n] \textrm{ bijective}\}\) the group of permutations on \(n\) letters. If \(\mathcal{I}\) is a finite set, we denote by \(\mathbb{R}^{\mathcal{I}}\) the vector space consisting of vectors indexed by \(\mathcal{I}\), by \(\Delta^{\mathcal{I}}\) the unit simplex in \(\mathbb{R}^{\mathcal{I}}\) consisting of nonnegative vectors whose entries sum to 1, and by \([-r,r]^{\mathcal{I}}\) for \(r>0\) the hypercube consisting of vectors with entries of magnitude at most \(r\). If \((\Omega,d)\) is a pseudometric space and \(S\subseteq\Omega\), we denote by \(\mathrm{dist}(x,S)=\inf_{y\in S}d(x,y)\) the distance of \(x\in\Omega\) to \(S\). The space \((\Omega,d)\) is totally bounded if all its covering numbers are finite. We denote the distribution of a random variable \(X\) by \(\mathrm{Law}(X)\). If \(X\) and \(Y\) are two random variables on the same space, we write \(X\overset{d}{=}Y\) to denote equality of their distributions \(\mathrm{Law}(X)=\mathrm{Law}(Y)\). We denote the collection of (Borel) probability distributions on \(\Omega\) by \(\mathcal{P}(\Omega)\). If \(\mu\in\mathcal{P}(\Theta)\), we write \(X\sim\mu\) for a random variable \(X\) to denote \(\mathrm{Law}(X)=\mu\). If \(f\colon\Omega\to\Omega'\) is a continuous map between two topological spaces \(\Omega\) and \(\Omega'\) and \(\mu\in\mathcal{P}(\Omega)\), we denote by \(f\mu\) the pushforward of \(\mu\) by \(f\). If \(\mu\in\mathcal{P}(\Omega)\) and \(f\colon\Omega\to\mathbb{R}\) is a measurable function, we denote by \(\mathbb{E}_{\mu}f=\mathbb{E}_{X\sim\mu}f(X)\) the expectation of \(f\) with respect to \(\mu\). The Wasserstein-1 distance between two measures \(\mu,\nu\in\mathcal{P}(\Omega)\) on a metric space \((\Omega,d)\) is defined by \[W_1(\mu,\nu)=\inf_{\substack{\textrm{random } (X,Y)\\ X\sim\mu, Y\sim\nu}} \mathbb{E}d(X,Y) = \sup_{\substack{f\colon\Omega\to\mathbb{R}\\ \textrm{1-Lipschitz}}}|\mathbb{E}_{\mu}f-\mathbb{E}_{\nu}f|,\] where the infimum is taken over couplings of \(\mu\) and \(\nu\). To simplify our notation, if \(X\) and \(Y\) are random variables (not necessarily coupled) on the same space \(\Omega\), we denote \(W_1(X,Y)=W_1(\mathrm{Law}(X),\mathrm{Law}(Y))\). A sequence of measures \((\mu_n)\subseteq\mathcal{P}(\Omega)\) converges weakly to \(\mu\in\mathcal{P}(\Omega)\) if \(\mathbb{E}_{\mu_n}f\to\mathbb{E}_{\mu}f\) for all continuous functions \(f\colon\Omega\to\mathbb{R}\). If \(\Omega\) is a compact metric space, this is further equivalent to convergence in \(W_1\) distance. A sequence of random variables \((X_n)\) converges weakly if their distributions \((\mathrm{Law}(X_n))\) converge weakly. If \((\Omega_n)\) are sets, we denote their disjoint union by \(\bigsqcup_n\Omega_n=\{(n,x):x\in\Omega_n, n\in\mathbb{N}\}\). If \(\sim\) is an equivalence relation on a set \(\Omega\), we denote by \(\Omega/\sim\) the quotient space consisting of equivalence classes. Any pseudometric \(d\) on \(\Omega\) induces an equivalence relation by setting \(x\sim y\) if \(d(x,y)=0\). If \(d\) is a pseudometric on \(\bigsqcup_n\Omega_n\), we denote by \(\Omega_{\infty}=\bigsqcup_n\Omega_n/\sim\) the quotient space under the equivalence relation induced by \(d\), on which \(d\) defines a metric, and by \(\overline{\Omega}_{\infty}\) the completion of this metric space.

1.5 Stuff that needs to be in the intro somewhere↩︎

Given sets \((\Omega_n)\) and sampling maps \((\mathsf{S}_k\colon\bigsqcup_n\Omega_n\to\Omega_k)\), define the sampling metric \[\label{tauwyncj} d_{\mathrm{samp}}(x,y)=\sum_{k\geq 1}2^{-k}W_1(\mathsf{S}_kx,\mathsf{S}_ky).\tag{6}\]

For a collection of inputs \((\Omega_n)\) and any-dimensional functions \(f,g\colon\bigsqcup_n\Omega_n\to\mathbb{R}\), define \(\mathrm{e}_n(f,g)=\sup_{x\in\Omega_{\leq n}}|f(x)-g(x)|\) and \(\mathrm{e}_{\infty}(f,g)=\sup_n\mathrm{e}_n(f,g)\).

We will show that Definitions 3 and 2, as well as several other related properties including generalization with respect to average error, are all equivalent to the precompactness of \(\bigsqcup_n\Omega_n\).

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 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. While the argument is elementary, we include it here for completeness. Suppose \(d\) is a pseudometric on \(\bigsqcup_n\Omega_n\), and define the equivalence relation \(x\sim 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 in the context of a given application domain, see Sections 1 and 2.3. Note that \(d\) is a metric on \(\Omega_{\infty}=\bigsqcup_n\Omega_n/\sim\), and we define \(\overline{\Omega}_{\infty}\) to be the completion of this metric space. Denote by \(\mathcal{F}_1\) the collection of 1-Lipschitz functions on \(\bigsqcup_n\Omega_n\), or equivalently, on \(\overline{\Omega}_{\infty}\).

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 \(\overline{\Omega}_{\infty}\) 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 \(\mathsf{S}_k\), 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 any-dimensional 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 \(\mu\in\mathcal{P}(\overline{\Omega}_{\infty})\) and \(f,g\colon\overline{\Omega}_{\infty}\to\mathbb{R}\) we define \(\mathrm{e}_{\mu}(f,g)=\mathbb{E}_{\mu}|f-g|\).

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↩︎

Fix vector spaces \((\mathbb{V}_n)\) and sampling maps \((\mathsf{S}_k\colon\bigsqcup_n\mathbb{V}_n\to\mathbb{V}_k)\), where each \(\mathsf{S}_k\) is viewed as a random map.⁵ We begin by showing that any sequence of compact sets \((\Omega_n\subseteq\mathbb{V}_n)\) closed under these sampling maps yields a compact limiting space.

We emphasize that we are assuming above that each \(\Omega_n\) is compact in the usual norm topology on \(\mathbb{V}_n\), and conclude that each \(\Omega_n\) is precompact (or equivalently, totally bounded) in the topology induced by the sampling metric \(d_{\mathrm{samp}}\). This proposition follows from Tychonoff’s theorem applied to the product \(\prod_n\mathcal{P}(\Omega_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 \(\overline{\Omega}_{\infty}\) 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.

Combining Proposition 5 and Theorem 3, we conclude that if \((\Omega_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 3(2)), and uniform any-dimensional sketching and generalization rates for Lipschitz functions measured by worst-case error (as in Theorem 3(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 4, such uniform rates are available for sequences of measures \((\mu_n\in\mathcal{P}(\Omega_n))\) with a weak limit \(\mu_{\infty}\in\mathcal{P}(\overline{\Omega}_{\infty})\). However, there are many sequences of measures converging to the same limit \(\mu_{\infty}\), and we seek a ‘canonical’ choice of such a sequence to model data distributions of growing dimensionality. Under the sampling metric, there is a natural family of such sequences of distributions. Specifically, each \(\mu_{\infty}\in\mathcal{P}(\overline{\Omega}_{\infty})\) defines a sequence of distributions of its samples \((\mathsf{S}_k(X))\) where \(X\sim\mu_{\infty}\) is independent of the sampling maps \(\mathsf{S}_k\). This sequence of distributions converges weakly back to \(\mu_{\infty}\) whenever the sampling maps \((\mathsf{S}_k)\) yield increasingly-good approximations of their inputs, in the sense that \(\mathsf{S}_k(x)\to x\) weakly as \(k\to\infty\) for any \(x\in\overline{\Omega}_{\infty}\). This is the case for all the sampling maps considered in the paper.

We now state the above result formally. For the following result, we endow \(\mathcal{P}(\overline{\Omega}_{\infty})\) with the weak topology, and endow \(\prod_n\mathcal{P}(\Omega_n)\) with the product of weak topologies. We also observe that the sampling maps \((\mathsf{S}_k\colon\bigsqcup_n\Omega_n\to\Omega_k)\) extend to \(\overline{\Omega}_{\infty}\). Indeed, if \(x\in\overline{\Omega}_{\infty}\) then we can write \(x=\lim_ix_i\) for \((x_i)\subseteq\bigsqcup_n\Omega_n\) and define \(\mathsf{S}_k(x)\) to be the weak limit of \((\mathsf{S}_k(x_i))_i\) for each \(k\in\mathbb{N}\). It is easy to check that this is well-defined by definition of convergence in \(d_{\mathrm{samp}}\).

We give the proof of this result in Section 2.4. We characterize the image of the map ?? for our generalizations of sampling with replacement and random binning in Theorems 13 and 17 below. The above sequences \((\mu_n)\) are precisely the ones we use in the sequel to quantify average generalization error in the sense of Proposition 4. Note that ?? is the only assumption we have made on the sampling maps \((\mathsf{S}_k)\).

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-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.

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.

As a consequence of Definition 5, if \(n\leq N\) and \(\phi\colon[n]\to[N]\) is an injection, then \(\theta(\phi)\colon\mathcal{I}_n\to\mathcal{I}_N\) is an injection as well. Indeed, there is a surjection \(\psi\colon[N]\to[n]\) satisfying \(\psi\circ\phi=\mathrm{id}_{[n]}\), in which case \(\theta(\psi)\circ\theta(\phi)=\mathrm{id}_{\mathcal{I}_n}\) so \(\theta(\phi)\) is injective. Likewise, if \(\psi\colon[N]\to[n]\) is surjective then \(\theta(\psi)\colon\mathcal{I}_N\to\mathcal{I}_n\) is surjective.

Examples of such compatible sequences include \(\mathcal{I}_n=[d]\times [n]\) with action \(\theta(f)(i,j)=(i,f(j))\), tuples \(\mathcal{I}_n=[n]^d\) with action \(\theta(f)(i_1,\ldots,i_d)=(f(i_1),\ldots,f(i_d))\), and multisets \(\mathcal{I}_n=[n]^d/\mathfrak{S}_d\), 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 \(\{(\mathcal{I}_n),\theta_I\}\) and \(\{(\mathcal{J}_n),\theta_J\}\) are two compatible sequences, then so are \(\{(\mathcal{I}_n\sqcup\mathcal{J}_n),\theta_I\sqcup\theta_J\}\) and \(\{(\mathcal{I}_n\times\mathcal{J}_n),\theta_I\times\theta_J\}\).

All of the compatible sequences of index sets in this paper can be derived by applying such standard operations to the basic sequence \((\mathcal{I}_n=[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.

As illustrations, the degree of \(\mathcal{I}_n=[d]\times [n]=\bigsqcup_{i=1}^d[n]\) is one, while the degrees of \(\mathcal{I}_n=[n]^2\), \(\mathcal{I}_n=[n]^2\sqcup[n]\), and \(\mathcal{I}_n=[n]^2/\mathfrak{S}_2\) are all two.

As discussed in Section 1, we associate to each compatible sequence \((\mathcal{I}_n)\) a sequence of vector spaces \((\mathbb{V}_n=\mathbb{R}^{\mathcal{I}_n})\), and let maps between finite sets act on these vector spaces via the maps \(\rho\) and \(\beta\) given by 2 and 4 , respectively. The maps \(\rho\) and \(\beta\) in turn yield generalizations of sampling with replacement \((\mathsf{R}_k)\) and random binning \((\mathsf{B}_k)\) in 3 and 5 , respectively.

Note that we have two sampling maps \((\mathsf{R}_k)\) and \((\mathsf{B}_k)\) defined on the same sequences of vector spaces. We explain in Examples 13 and 14 when each of these sampling maps is appropriate.

We remark that the actions \(\rho\) and \(\beta\) from 2 and 4 , respectively, respect compositions of maps between finite sets. Specifically, we have \(\rho(f_1\circ f_2)=\rho(f_2)\circ \rho(f_1)\) while \(\beta(f_1\circ f_2)=\beta(f_1)\circ\beta(f_2)\) whenever the composition \(f_1\circ f_2\) is well-defined, so \(\rho\) reverses the order of compositions while \(\beta\) preserves it.⁹ We will exploit this compositionality in what follows.

When is each sampling map appropriate?↩︎

As discussed in Section 1, the sampling maps \((\mathsf{R}_k)\) and \((\mathsf{B}_k)\) induce equivalence relations between distinct objects, meaning that \(d_{\mathrm{samp}}(x,y)=0\) for \(x\neq y\) when \(d_{\mathrm{samp}}\) 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 \(d_{\mathrm{samp}}\). 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 \(\pi\colon[n]\to[n]\) is a permutation (i.e., a bijection), then \(\pi\) defines a bijection from \(\mathcal{I}_n\) to itself via \(\theta\), and two isomorphisms of \(\mathbb{V}_n\) to itself via \(\rho\) and \(\beta\). These two actions of permutations on \(\mathbb{V}_n\) define representations of the group \(\mathfrak{S}_n\) on \(\mathbb{V}_n\); 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 \(\pi\in\mathfrak{S}_n\) on a vector \(x\in\mathbb{V}_n\) by \(\pi x\), which equals either \(\rho(\pi)x\) or \(\beta(\pi)x\) depending on whether \((\mathbb{V}_n)\) is endowed with sampling with replacement or with random binning maps, respectively.

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 \(\iota_{N,n}\colon[n]\hookrightarrow [N]\) defined as \[\iota_{N,n}(i) = i \quad \textrm{for } i \in [n],\quad \textrm{whenever } n\leq N.\] These inclusions in turn define inclusions of \(\mathcal{I}_n\) into \(\mathcal{I}_N\) via the action \(\theta\). Then the map \(\rho(\iota_{N,n})\colon\mathbb{V}_N\to\mathbb{V}_n\) acts as the orthogonal projection with respect to the usual inner product, while \(\beta(\iota_{N,n})\colon\mathbb{V}_n\to\mathbb{V}_N\) is an embedding by zero-padding. For example, when \(\mathbb{V}_n = \mathbb{R}^n\) the projection \(\rho(\iota_{N,n})\) extracts the first \(n\) entries from a length-\(N\) vector, while \(\beta(\iota_{N,n})\) zero-pads a vector of length \(n\) by \(N-n\) zeros. Similarly, when \(\mathbb{V}_n = \mathbb{R}^{n \times n}\) the projection \(\rho(\iota_{N,n})\) extracts the induced subgraph on the first \(n\) vertices from a graph on \(N\) vertices, while the embedding \(\beta(\iota_{N,n})\) corresponds to appending \(N-n\) isolated vertices to a graph on \(n\) vertices. See Example 12 for these and other examples.

The second distinguished set of maps are the consecutive partitions \(\kappa_{n,N}\colon[N]\to[n]\) defined by \[\label{eq:standard95equipartition} \kappa_{n,N}(j + (i-1)(N/n)) = i \quad \textrm{for } i\in[n], j\in[N/n],\quad \textrm{whenever } n|N.\tag{7}\] The corresponding linear maps \(\rho(\kappa_{n,N})\colon\mathbb{V}_n\to\mathbb{V}_N\) are embeddings that duplicate the entries of their inputs in a suitable sense based on the action \(\theta\). For example, we have \(\rho(\kappa_{n,N})x=x\otimes\mathbb{1}_{N/n}\) when \(\mathbb{V}_n=\mathbb{R}^n\), which acts by duplicating each entry of a vector \(x\) of length \(n\) the same number \(N/n\) of times. Similarly, we have \(\rho(\kappa_{n,N})X=X\otimes\mathbb{1}_{N/n}\mathbb{1}_{N/n}^\top\) when \(\mathbb{V}_n=\mathbb{R}^{n\times n}\), which acts by duplicating each entry of a matrix \(X\) of size \(n\times n\) into a block of \((N/n)\times(N/n)\) entries. Meanwhile, the maps \(\beta(\kappa_{n,N})\colon\mathbb{V}_N\to\mathbb{V}_n\) are projections that sum consecutive blocks of coordinates. For example, the vector \(\beta(\kappa_{n,N})x\in\mathbb{R}^n\) is obtained from \(x\in\mathbb{R}^N\) by summing each group of consecutive \(N/n\) coordinates. Similarly, the matrix \(\beta(\kappa_{n,N})X\in\mathbb{R}^{n\times n}\) is obtained from \(X\in\mathbb{R}^{N\times N}\) by summing the entries of each consecutive \(N/n\times N/n\) block in \(X\). See Example 12.

We are now ready to state the relationships across dimensions satisfied by our sampling maps.

In particular, note that for any \(x\in\mathbb{V}_n\), we have \(d_{\mathrm{samp}}(x,\rho(\kappa_{n,N})x)=0\) if \(d_{\mathrm{samp}}\) is defined using \((\mathsf{R}_k)\), while \(d_{\mathrm{samp}}(x,\beta(\iota_{N,n})x)=0\) for any \(x\in\mathbb{V}_n\) if \(d_{\mathrm{samp}}\) is defined using \((\mathsf{B}_k)\). Note here that \(\rho(\kappa_{n,N})x\) and \(\beta(\iota_{N,n})x\) belong to \(\mathbb{V}_N\), so the sampling distance between objects of different sizes can equal zero.

Observe that the maps \(\iota_{N,n}\) are particular types of injections, while the maps \(\kappa_{n,N}\) are particular types of equipartitions.¹⁰ By combining Propositions 8 and 9, we are able to obtain the following consequences for all injections and equipartitions: \[\label{eq:injection95equivalence} \rho(\phi_{N,n})\circ\mathsf{R}_N\overset{d}{=}\mathsf{R}_n\quad \textrm{and} \quad \mathsf{B}_k\circ\beta(\phi_{N,n})\overset{d}{=}\mathsf{B}_k\quad \textrm{for any injection \phi_{N,n}\colon[n]\to[N]},\tag{8}\] and \[\label{eq:eqp95equivalence} \mathsf{R}_k\circ\rho(\psi_{n,N})\overset{d}{=}\mathsf{R}_k\quad \textrm{and}\quad \beta(\psi_{n,N})\circ\mathsf{B}_N\overset{d}{=}\mathsf{B}_n\quad \textrm{for any equipartition } \psi_{n,N}\colon[N]\to[n],\tag{9}\] since we can write \(\phi_{N,n}=\pi_N\circ \iota_{N,n}\) and \(\psi_{n,N}=\kappa_{n,N}\circ\pi_N\) for some permutation \(\pi_N\in\mathfrak{S}_N\).

As a converse to the preceding equivalences, we now prove that if \(d_{\mathrm{samp}}(x,y)=0\) then \(x,y\) must differ by permutations and duplication for sampling with replacement, or permutations and zero-padding for random binning.

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.

If \(f\colon\bigsqcup_n\mathbb{V}_n\to\mathbb{R}\) is continuous with respect to the sampling metric defined by \((\mathsf{R}_k)\), then \[\label{eq:eqp95invariant} f(\rho(\psi_{n,N})x)=f(x) \quad \textrm{for all } x\in\mathbb{V}_n \textrm{ and equipartitions } \psi_{n,N}\colon[N]\to[n],\tag{10}\] or equivalently, each restriction \(f|_{\mathbb{V}_n}\) is permutation-invariant and \(f\) is unchanged by duplication of entries defined by \(\rho(\kappa_{n,N})\). Likewise, if \(f\) is continuous with respect to the sampling metric defined by \((\mathsf{B}_k)\), then \[\label{eq:zero95pad95invariant} f(\beta(\phi_{N,n})x)=f(x) \quad \textrm{for all } x\in\mathbb{V}_n \textrm{ and injections } \phi_{N,n}\colon[n]\to[N],\tag{11}\] or equivalently, each restriction \(f|_{\mathbb{V}_n}\) is permutation-invariant and \(f\) is unchanged by zero-padding defined by \(\beta(\iota_{N,n})\). Thus, functions continuous in the sampling metric defined using either choice of sampling maps respect the same equivalence relations.

The converses of 10 and 11 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 11 but we show in Corollary 7 that it is not continuous with respect to random binning. However, the converses are true if \(f|_{\mathbb{V}_n}\) is a polynomial of some degree \(d\) for all \(n\). In this case, if \(f\) is unchanged by equipartitions in the sense of 10 then there exists \(k\in\mathbb{N}\) and a fixed-dimensional polynomial \(g_k\in\mathbb{R}[\mathbb{V}_k]\) such that \(f(x)=\mathbb{E}g_k(\mathsf{R}_k(x))\) for all \(x\) by [15]. Similarly, if \(f\) is unchanged by zero-padding in the sense of 11 then there exists \(k\in\mathbb{N}\) and \(g_k\in\mathbb{R}[\mathbb{V}_k]\) such that \(f(x)=\mathbb{E}g_k(\mathsf{B}_k(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 4. Fix a compatible sequence \((\mathcal{I}_n)\) and consider the corresponding sequence \((\mathbb{V}_n=\mathbb{R}^{\mathcal{I}_n})\) of vector spaces. For simplicity, suppose first that \(x\in\Delta^{\mathcal{I}_N}\) is a simplex element. We view such \(x\) as a probability distribution over \(\mathcal{I}_N\), and consider forming an empirical approximation to it from \(n\) iid samples. Specifically, sampling \(\alpha_1,\ldots,\alpha_n\in\mathcal{I}_N\) iid according to \(x\), we set \[\label{eq:empirical95sampling} \mathscr{E}_n(x)=\frac{1}{n}\sum_{i=1}^ne_{\alpha_i}.\tag{12}\] In general, we have \(\mathscr{E}_n(x)\in \mathbb{V}_N\) and hence \(\mathscr{E}_n\) does not reduce the dimensionality of its input. However, it does produce a sparse vector, as \(\mathscr{E}_n(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 \(\mathsf{E}_n(x)\) of species sampling. We next describe this construction formally.

Suppose first that \(\mathcal{I}_n=[n]^D\) for all \(n\) and \(x\in\Delta^{\mathcal{I}_N}\) as above.

1. Sample \(\alpha_1,\ldots,\alpha_n\) from the distribution \(x\) on \(\mathcal{I}_N=[N]^D\). Denote \(\alpha_i=(j_1^{(i)},\ldots,j_D^{(i)})\) for each \(i\).

2. Consider the subset \(\bigcup_{i=1}^n\{j_1^{(i)},\ldots, j_D^{(i)}\}\) of \([N]\), and denote its cardinality by \(k\leq nD\). Uniformly randomly enumerate the elements of this subset to obtain \(t_1,\ldots,t_k\).

3. Set \[\label{eq:species95sampling95general} \mathsf{E}_n(x)_{\ell_1,\ldots,\ell_D}= \mathscr{E}_n(x)_{t_{\ell_1},\ldots,t_{\ell_D}},\tag{13}\] if \(\ell_1,\ldots,\ell_d\in[k]\), and \(\mathsf{E}_n(x)_{\ell_1,\ldots,\ell_D}=0\) otherwise.

In words, we view the elements of \([N]\) as labeling distinct species, and elements of \(\mathcal{I}_N = [N]^D\) as relations between these species. The empirical sampling map \(\mathscr{E}_n\) samples these relations while ‘remembering’ the species labels, while the species sampling map \(\mathsf{E}_n\) ‘forgets’ the labels of the species in steps 2 and 3 of the above construction. For example, if \(\mathcal{I}_N=[N]\) then \(\mathsf{E}_n\) recovers the species sampling map of Example 4. Furthermore, if \(\mathcal{I}_N=[N]^2\) and we view elements of \(\mathbb{V}_N=\mathbb{R}^{N\times N}\) as adjacency matrices of (weighted, directed) graphs on \(N\) vertices, then \(\mathsf{E}_n\) 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 \(\mathsf{E}_n(x)\) generalizes to any compatible sequence \((\mathcal{I}_n)\) of finite degree and any \(x\in\mathbb{V}_N\), not necessarily a simplex element, as follows.

• If \(\mathcal{I}_n=[n]^D/H\) for some subgroup \(H\subseteq\mathfrak{S}_D\), then each \(\alpha_i\) sampled in step 1 above is the coset of a tuple, denoted \(\alpha_i=H(j_1^{(i)},\ldots,j_D^{(i)})\). Because \(H\) acts by permuting indices in a tuple, step 2 is well-defined. Moreover, if \((i_1,\ldots,i_D)=h(j_1,\ldots,j_D)\) for some \(h\in H\) then \((t_{i_1},\ldots,t_{i_D})=h(t_{j_1},\ldots,t_{j_D})\). Thus, setting \(\mathsf{E}_n(x)_{H(i_1,\ldots,i_D)}= \mathscr{E}_n(x)_{H(t_{i_1},\ldots,t_{i_D})}\) is well-defined and generalizes 13 to this case.

• If \(\mathcal{I}_n=\bigsqcup_{m=1}^M[n]^{d_m}/H_m\) is a general compatible sequence of degree \(D=\max_md_m\), then each \(\alpha_i\) sampled in step 1 above belongs to \([n]^{d_{m_i}}/H_{m_i}\) for some \(m_i\). Then in step 2 we randomly enumerate the set of all indices contained in all of the \(\alpha_i\), and in step 3 we generalize 13 as above. More precisely, denoting \(\alpha_i=H_{m_i} (j_1^{(i)},\ldots,j_{d_{m_i}}^{(i)})\), in step 2 we randomly enumerate the elements of the subset \(\bigcup_{i=1}^n\{j_1^{(i)},\ldots,j_{d_{m_i}}^{(i)}\}\) of \([N]\), which again contains \(k\leq nD\) distinct elements \(t_1,\ldots,t_k\). In step 3, we then set \(\mathsf{E}_n(x)_{H_m(i_1,\ldots,i_{d_m})}=\mathscr{E}_n(x)_{H_m(t_{i_1},\ldots,t_{i_{d_m}})}\), generalizing 13 to a general compatible sequence of index sets.

• We extend both \(\mathscr{E}_n\) and \(\mathsf{E}_n\) beyond simplex vectors by homogeneity. Specifically, if \((\mathcal{I}_n)\) is a compatible sequence of finite degree and \(x\in\mathbb{V}_N\), define \(\mathscr{E}_n(x)=\|x\|_1\mathrm{sign}(x)\odot \mathscr{E}_n(|x|/\|x\|_1)\) where \(\odot\) denotes entrywise product (and \(\mathscr{E}_n(0)=0\) by convention), and define \(\mathsf{E}_n(x)\) as above.

We have thus generalized species sampling to general vectors indexed by elements of a compatible sequence of finite degree to obtain random maps \((\mathsf{E}_k\colon \bigsqcup_n\mathbb{V}_n\to \mathbb{V}_{kD})_k\).

1ex -.5em 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.

In particular, if \(d_{\mathrm{samp}}\) is defined using species sampling, then \(d_{\mathrm{samp}}(x,\beta(\phi_{N,n})x)=0\) for all \(x\in\mathbb{V}_n\) and all injections \(\phi_{N,n}\colon[n]\to[N]\). Likewise, if \(f\colon\bigsqcup_n\mathbb{V}_n\to\mathbb{R}\) is continuous with respect to the sampling metric defined by \((\mathsf{E}_k)\), we have \(f(\beta(\phi_{N,n})x)=f(x)\). Conversely, it follows from Proposition 19 below that if \(d_{\mathrm{samp}}(x,y)=0\) for \(x\in\mathbb{V}_n\) and \(y\in\mathbb{V}_N\) for \(n\leq N\) then \(y=\beta(\phi_{N,n})x\) for some injection \(\phi_{N,n}\).

Thus, species sampling may be appropriate in the same domains as random binning, such as those in Example 14. In fact, we show in Proposition 19 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 3 via a direct argument.

Next, we prove Proposition 4, likewise via a direct argument.

We now prove Proposition 5 using Tychonoff’s theorem.

We turn to proving Proposition 6, relating limits in sampling metric to sequences of distributions.

Finally, we prove Proposition 10.

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 12, quantifying part 2 of Theorem 3. Based on Proposition 6, we then characterize in Theorem 13 the structure of any-dimensional data distributions obtained by sampling with replacement from limit objects. Next we leverage the equivalences in Theorem 3 to derive explicit sketching and generalization rates in Theorem 14 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 sets \((\mathcal{I}_n)\), and consider the associated vector spaces \((\mathbb{V}_n=\mathbb{R}^{\mathcal{I}_n})\) and sampling with replacement maps \((\mathsf{R}_k\colon\bigsqcup_n\mathbb{V}_n\to\mathbb{V}_k)\) defined by 3 . We also fix a sequence of compact sets \((\Omega_n)\) closed under sampling, such as the sequence of hypercubes \(\Omega_n=[-r,r]^{\mathcal{I}_n}\). Throughout this section, we consider the sampling metric 1 defined using \((\mathsf{R}_k)\), with \(W_1\)-distances taken with respect to the \(\ell_{\infty}\)-norms.

Our first result shows that \(\mathbb{E}d_{\mathrm{samp}}(x,\mathsf{R}_n(x))\to0\) as \(n\to\infty\) and gives the associated rate at which this expectation goes to zero. To bound \(\mathbb{E}d_{\mathrm{samp}}(x,\mathsf{R}_n(x))\), we must bound for each \(k\) the expected distance \(\mathbb{E}_{\mathsf{R}_n}W_1(\mathsf{R}_k(x),\mathsf{R}_k\circ\mathsf{R}_n(x))\), where we (a) fix a realization of \(\mathsf{R}_n\); (b) compute the \(W_1\) distance between the distributions of \(\mathsf{R}_k(x)\) and \(\mathsf{R}_k\circ\mathsf{R}_n(x)\), yielding a random number depending on \(\mathsf{R}_n\); and (c) take the expectation with respect to \(\mathsf{R}_n\).

The proof is based on the observation that a uniformly random map \(F_{N,k}\colon[k]\to[N]\) can be identified with \(k\) iid uniformly distributed random indices \((F_{N,k}(1),\ldots,F_{N,k}(k))\) in \([N]\), so \(\mathrm{Law}(F_{N,k})=\mu^{\otimes k}\) where \(\mu\) is the uniform distribution on \([N]\). Meanwhile, if we fix a realization \(\widehat F_{N,n}\) of \(F_{N,n}\), we have \(\mathrm{Law}(\widehat F_{N,n}\circ F_{n,k})=\mu_n^{\otimes k}\) where \(\mu_n=\frac{1}{n}\sum_{i=1}^n\delta_{\widehat F_{N,n}(i)}\) is an empirical measure obtained by sampling \(n\) iid points from \(\mu\). Comparing \(\mu_n\) to \(\mu\) yields the proof, see Section 3.2.

We give a few examples of the rates implied by Theorem 12.

Theorem 12 has two important consequences. First, it implies that \(\mathbb{E}d_{\mathrm{samp}}(x,\mathsf{R}_n(x))\to0\) for any \(x\in\overline{\Omega}_{\infty}\), so Proposition 6 applies and gives us a characterization of any-dimensional data distributions obtained by sampling from random limit objects.

The proof combines Proposition 6 and Theorem 12, along with a “finite” de Finetti theorem comparing sampling with and without replacement from [15] generalizing [43], see Section 3.2.

Theorem 13 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.

The second consequence of Theorem 12 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.

The proof uses Theorem 12, and we again defer it to Section 3.2. We now illustrate these improved rates on several classes of functions, beginning with polynomials.

Notably, Corollary 3 applies to any polynomial function and any finite-degree compatible sequence of index sets. Here are a few examples encompassed by the above result.

1. When \(\mathbb{V}_n=\mathbb{R}^{d\times n}\), polynomials unchanged by duplication are precisely moment polynomials \[p(x)=q\Big(\mathbb{E}(\mathsf{R}_1(x))^{\alpha_1},\ldots,\mathbb{E}(\mathsf{R}_1(x))^{\alpha_\ell}\Big),\] where \(\alpha_i\in \mathbb{N}_0^d\) and \(q\) is a fixed polynomial [15]. Here \(\mathbb{E}(\mathsf{R}_1(x))^{\alpha}=\frac{1}{n}\sum_{j=1}^n\prod_{\ell=1}^d(x_j)_\ell^{\alpha_{\ell}}\) for \(\alpha\in\mathbb{N}_0^d\).

2. When \(\mathbb{V}_n=\mathbb{R}^{n\times n}\), polynomials unchanged by duplication are precisely linear combinations of graph homomorphism densities [15]. Specifically, if \(H\in\mathbb{N}_0^{k\times k}\) is a multigraph, we define the homomorphism density of \(H\) in \(G\in\mathbb{V}_n\) by \[t(H;G) = \frac{1}{n^k}\sum_{f\colon[k]\to[n]}\prod_{i,j=1}^kG_{f(i),f(j)}^{H_{i,j}}.\] 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)\to V(G)\) that are graph homomorphisms. Similarly, when \(\mathbb{V}_n=(\mathbb{R}^n)^{\otimes d}\) is viewed as the space of adjacency tensors of hypergraphs, polynomials unchanged by duplication correspond to linear combinations of hypergraph densities.

3. When \(\mathbb{V}_n=\mathbb{R}^{n\times n}\oplus \mathbb{R}^{n\times 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 \[(G,X)\mapsto \sigma\left(\sum_{\ell=0}^L\frac{1}{n^{\ell}}G^{\ell}X\Theta_{\ell}\right),\quad \textrm{for polynomial } \sigma \textrm{ and } \Theta_0,\ldots,\Theta_L\in\mathbb{R}^{d\times d}.\]

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] implies \(O(n^{-1/d})\) generalization rates for moment polynomials and \(O(1/\sqrt{\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.

When \(\sigma\) and \(h\) are neural networks, the architecture defined by ?? is called normalized DeepSets [16], [21]. In particular, when \(\Omega_n=\Theta^n\) for compact \(\Theta\subseteq\mathbb{R}^d\), we can extend \(f\) in ?? to measures \(\mu\in\mathcal{P}(\Theta)\) by \(f(\mu)=\sigma(\mathbb{E}_{\mu}h)\). This extension was shown in [21] to be Lipschitz-continuous in Wasserstein metric on \(\mathcal{P}(\Theta)\). In turn, the result [16] implies \(O(n^{-1/d})\) generalization rates for such Lipschitz functions on measures for average error with respect to infinite exchangeable arrays (Example 17). This rate can similarly be derived from Theorem 14, and Corollary 4 yields improved \(O(n^{-1/2})\) rates for functions of the form ?? .

Finally, we give sketching and generalization rates for transformers, making Corollary 2 precise.

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\in\mathbb{V}_N\) takes \(O(N^2)\) operations due to ?? , but evaluating it to a desired accuracy \(\delta>0\) can be done with high probability in \(O(\delta^{-2d})\) time (independent of the length \(N\) of the input) after sampling \(n=O(\delta^{-d})\) columns from \(x\) uniformly at random and using ?? .

3.2 Missing Proofs from Section 3↩︎

We begin by proving Theorem 12. The following is the key proposition we shall need.

We turn to proving Theorem 12 by combining Proposition 15 with the following standard covering number bound.

Combining Lemma 1 with covering number bounds for Lipschitz functions yields Theorem 12.

We turn to proving Theorem 13 by combining Proposition 6 and a “finite” de Finetti theorem from [15].

Next, we prove the sketching and generalization bounds in Theorem 14.

Finally, we prove Corollary 5 using the measure-theoretic expression for attention in [17].

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 index sets \((\mathcal{I}_n)\), and consider the associated vector spaces \((\mathbb{V}_n=\mathbb{R}^{\mathcal{I}_n})\) and random binning maps \((\mathsf{B}_k\colon\bigsqcup_n\mathbb{V}_n\to\mathbb{V}_k)\) defined by 5 . We also fix a sequence of compact sets \((\Omega_n)\) closed under random binning, such as the sequence of \(\ell_1\) balls \(\mathcal{B}_{\ell_1}^{(n)}(r)=\{x\in\mathbb{V}_n:\|x\|_1\leq r\}\). Proceeding as in Section 3, it may be tempting to try to prove a result akin to Theorem 12 in which we might show that \(d_{\mathrm{samp}}(x,\mathsf{B}_n(x))\to0\) with high probability, and quantify the rate at which it converges to zero. Unfortunately, while we will show below that \(\mathbb{E}d_{\mathrm{samp}}(x,\mathsf{B}_n(x))\to0\), the following example illustrates that individual realizations \(d_{\mathrm{samp}}(x,\mathsf{B}_n(x))\) do not concentrate as well around their means as in the case of sampling with replacement.

In contrast, for sampling with replacement Theorem 12 gives a rate \(\epsilon_n\) such that \(\mathbb{P}[d_{\mathrm{samp}}(x,\mathsf{R}_n(x))\geq \epsilon_n]\leq e^{-Cn}\) for a constant \(C>0\).

To remedy this situation, we show in Theorem 16 that \(d_{\mathrm{samp}}(x,\mathsf{E}_n(x))\) exhibits the requisite concentration, where \(\mathsf{E}_n\) 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 similar agenda as in Section 3. We characterize the any-dimensional data distributions that are obtained via random binning in Theorem 17. We then give explicit any-dimensional sketching and generalization rates in Theorem 18, 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 19 in which we relate convergence with respect to random binning and species sampling.

We begin by quantifying the convergence \(d_{\mathrm{samp}}(x,\mathsf{E}_n(x))\to 0\) in expectation and with high probability.

We emphasize again that although Theorem 16(2) shows that \(\mathbb{E}d_{\mathrm{samp}}(x,\mathsf{B}_n(x))\to0\), these distances do not concentrate well around their means as shown in Example 19.

The proof of Theorem 16(1) is based on the following standard bound for the empirical sampling map 12 , \[\label{eq:Binom95bound} \mathbb{E}\|x-\mathscr{E}_n(x)\|_2 \leq \|x\|_1\sqrt{\sum_{\alpha\in\mathcal{I}_N}\mathbb{E}\Big(p_{\alpha} -\tfrac{1}{n}\mathrm{Binom}(n,p_{\alpha})\Big)^2} \leq \frac{\|x\|_1}{\sqrt{n}},\quad \textrm{for any } x\in\mathbb{R}^{\mathcal{I}_N},\;N\in\mathbb{N},\tag{17}\] where \(p_{\alpha}=|x_{\alpha}|/\|x\|_1\) are the probabilities proportional to the magnitudes of entries of \(x\), together with the fact that \(d_{\mathrm{samp}}(\mathscr{E}_n(x),\mathsf{E}_n(x))=0\) almost surely. The proof of Theorem 16(2) uses an explicit coupling between \(\mathsf{B}_k(x)\) and \(\mathsf{B}_k\circ\mathsf{B}_n(x)\). We give the full details in Section 4.2. Examples of sets satisfying the hypotheses of Theorem 16 include the sequence of simplices \(\Omega_n=\Delta^{\mathcal{I}_n}\) and \(\ell_1\)-balls.

We proceed to describe some of the implications of Theorem 16. First, the fact that \(\mathbb{E}d_{\mathrm{samp}}(x,\mathsf{B}_n(x))\to0\) at a universal rate as \(n\to\infty\) allows us to apply Proposition 6 and leads to a characterization of sequences of any-dimensional distributions that are compatible with random binning.

Similarly to Theorem 13, the proof combines Proposition 6 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 16, we then give generalization rates for average error with respect to these distributions.

The next consequences of Theorem 16 are the following sketching and generalization rates, proved in Section 4.2. In contrast to the analogous Theorem 14 for sampling with replacement, here we get a rate of \(n^{-1/2}\) regardless of the latent low-dimensional structure of our functions.

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 18 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.

Note that we obtain sketching and generalization rates that do not directly depend on the degree of \(p\) or of \((\mathcal{I}_n)\). The following are a few examples of the polynomials to which Corollary 6 applies, which constitute “unnormalized” analogs of the polynomials unchanged by duplication considered in Corollary 3.

1. When \(\mathbb{V}_n=\mathbb{R}^{d\times n}\), polynomials unchanged by zero-padding are precisely multisymmetric functions [52], consisting of polynomials of the form \[p(x)=q\Big(p_{\alpha_1}(x),\ldots,p_{\alpha_k}(x)\Big),\] where \(q\in\mathbb{R}[y_1,\ldots,y_k]\) is a fixed polynomial, and for \(\alpha\in\mathbb{N}_0^d\) we have \(p_{\alpha}(x)=\sum_{i=1}^n\prod_{j=1}^dx_{j,i}^{\alpha_j}\). When \(d=1\) and \(\alpha\in\mathbb{N}_0\), the polynomials \(p_{\alpha}(x)=\sum_{i=1}^nx_i^{\alpha}\) 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] and [54].

2. When \(\mathbb{V}_n=\mathbb{R}^{n\times n}\), polynomials unchanged by zero-padding are precisely linear combinations of graph homomorphism numbers [15]. Specifically, if \(H\in \mathbb{N}_0^{k\times k}\) is a multigraph, we define the homomorphism number of \(H\) in \(G\in\mathbb{V}_n\) by \[\mathrm{hom}(H;G)=\sum_{f\colon[k]\to[n]}\prod_{i,j=1}^kG_{f(i),f(j)}^{H_{i,j}}.\] When \(H,G\) are simple graphs, the value \(\mathrm{hom}(H;G)\) is the number of graph homomorphisms from \(H\) to \(G\). Similarly, when \(\mathbb{V}_n=(\mathbb{R}^n)^{\otimes d}\) polynomials unchanged by zero-padding are linear combinations of hypergraph homomorphism numbers, analogously defined.

3. When \(\mathbb{V}_n=\mathbb{R}^{n\times n}\oplus\mathbb{R}^n\), polynomials unchanged by zero-padding include polynomial (unnormalized) graph neural networks, which are compositions of polynomials of the form \[(G,X)\mapsto \sigma\left(\sum_{\ell=0}^LG^{\ell}X\Theta_{\ell}\right),\quad \textrm{for polynomial } \sigma \textrm{ and } \Theta_0,\ldots,\Theta_L\in\mathbb{R}^{d\times d}.\]

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.

The proof is a direct computation, see Section 4.2. Although the 1-norm is of the form \(f(x_1,\ldots,x_n)=\sigma(\sum_i\rho(x_i))\) for \(d=1\), \(\sigma = \mathrm{id}_{\mathbb{R}}\) and \(\rho = |\cdot|\), both of which are 1-Lipschitz, the stronger condition on \(\rho\) 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 \(\rho\) (as well as \(\sigma\)) is not by itself sufficient to obtain continuity with respect to random binning. The hypothesis on \(\rho\) in part 1 is satisfied if, for example, \(\rho\) is differentiable with a \(1/2\)-Hölder continuous derivative satisfying \(\rho'(0)=0\).

When \(\sigma\) and \(\rho\) in Corollary 7 are neural networks, the resulting architecture is called DeepSets [18]. When \(d=1\) and \(\Omega_n=\Delta^n\), different choices of \(\sigma\) and \(\rho\) yield various diversity indices used to quantify the concentration of a discrete probability distribution [42]. For example, setting \(\rho(x)=x^q\) and \(\sigma(t)=\frac{1-t}{q-1}\) gives Tsallis’ entropy, which for \(q\geq 3/2\) satisfies the hypotheses of Corollary 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 (given by \(\sigma=\mathrm{id}\), \(\rho(t)=t\log \frac{1}{t}\) for the former and \(\sigma(t)=\frac{1}{1-q}\log(t)\), \(\rho(t)=t^q\) for the latter) for example, both of which diverge along the (convergent) sequence \(x^{(n)}=\mathbb{1}_n/n\).

Finally, we consider non-polynomial graph neural networks.

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 18 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.

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 \(\mathcal{I}_n=[n]^2\) and \(\Omega_n=\Delta^{n\times n}\) was shown in [13].

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 \((\Omega_n=\Delta^{\mathcal{I}_n})\) then we get the same completion \(\overline{\Omega}_{\infty}\) with respect to both \((\mathsf{B}_k)\) and \((\mathsf{E}_k)\) by Proposition 19. Combining Theorem 16 and Proposition 6 shows that each probability distribution \(\mu\in\mathcal{P}(\overline{\Omega}_{\infty})\) on limit objects yields two sequences of distributions on finite objects converging weakly to \(\mu\), namely \((\mathrm{Law}(\mathsf{B}_k(x)))\) and \((\mathrm{Law}(\mathsf{E}_k(X)))\) for \(X\sim\mu\) independent of \(\mathsf{B}_k\) and \(\mathsf{E}_k\). 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 \((\mathrm{Law}(\mathsf{E}_k(X)))\) analogously to Theorem 17. For example, when \(\mathcal{I}_n=[n]^2\) such sequences of distributions are precisely edge-exchangeable multigraph models normalized to have unit edge weights, as shown in [13]. We leave such a characterization more generally for future work.

4.2 Missing Proofs from Section 4↩︎

We begin by proving Theorem 16. We shall need the following several lemmas to do so. The first lemma shows that the species sampling \(\mathsf{E}_n\) and empirical sampling \(\mathscr{E}_n\) maps in 13 and 12 , respectively, are equivalent in the sampling metric defined by random binning.

As we shall see, empirical sampling satisfies several useful properties that we exploit to prove Theorem 16. The second lemma shows a compatibility between the empirical sampling \(\mathscr{E}_n\) from 12 and the action 4 of maps between finite sets.

Combining Lemma 3 with the bound 17 for the empirical sampling map, we are ready to prove the first bound from Theorem 16(1).

Next, we prove the bound ?? from Theorem 16(2) using an explicit coupling between \(\mathsf{B}_k(x)\) and \(\mathsf{B}_k\circ\mathsf{B}_n(x)\). Along the way, we prove a bound between \(x\) and an appropriate zero-padding of the binned \(\mathsf{B}_n(x)\), to be used in the proof of Theorem 18.

We are ready to prove Theorem 16.

We turn to proving Theorem 17 by combining Proposition 6 and a dual de Finetti theorem from [15].

Next, we use Theorem 16 to prove the sketching and generalization rates in Theorem 18. The following proof is similar to the proof of Theorem 14.

We now apply Theorem 18 to analyze the DeepSets-like functions from Corollary 7.

We turn to proving Corollary 9 analyzing certain graph neural networks.

Finally, we prove Proposition 19 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 16(1) with the roles of random binning and species sampling reversed.

We proceed to relate convergence with respect to species sampling and random binning.

We are ready to prove Proposition 19.

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.

1. Can we characterize the collection of sequences \((\mathrm{Law}(\mathsf{E}_k(X)))_k\) for random \(X\) in terms of the relations of these distributions across dimensions, analogously to Theorems 13 and 17? These sequences of distributions include random partitions of integers [8]–[11] and edge-exchangeable random graph models [13], [55].

2. 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?

3. 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] 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 10(1), Theorem 16(2), and Proposition 19 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. Emails: eitanl@uchicago.edu, venkatc@caltech.edu↩︎

2. 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. We assume infinite-precision self-attention and mean pooling for the last layer, see Corollary 5.↩︎

4. The Wasserstein distance between two random variables is given by the distance between the associated laws, i.e., if \(X,Y\) are random variables, then \(W_1(X,Y)=W_1(\mathrm{Law}(X),\mathrm{Law}(Y))\).↩︎

5. We can also view \(\mathsf{S}_k\) as a kernel, i.e., a map \(\bigsqcup_n\mathbb{V}_n\to\mathcal{P}(\mathbb{V}_k)\). The two views are equivalent by [38].↩︎

6. Here we endow the space of random probability measures \(\mathcal{P}(\mathcal{P}([0,1]))\) with the weak topology with respect to the weak topology on \(\mathcal{P}([0,1])\). See [13] for more details.↩︎

7. In the language of category theory, this is a functor from the category \(\mathrm{FinSet}\) of finite sets to itself.↩︎

8. Our notion of degree is closely related to the degree of a polynomial functor [39].↩︎

9. Such composition-reversing and composition-preserving linear actions of maps between finite sets were called \(\mathrm{FinSet}^{\mathrm{op}}\)- and \(\mathrm{FinSet}\)-representations, respectively, in [15].↩︎

10. An equipartition is a map with equal-sized fibers.↩︎