$\mathcal{O}(\log N)$ Latent Dimension Suffices for Universal Approximation of Permutation-invariant Function

Learning permutation-invariant functions over sets of $N$ elements, where the output is independent of the input ordering, is fundamental to many deep learning applications. While sum-decomposable architectures like DeepSets offer universal approximation for such functions, existing constructive bounds require a latent dimension of $\mathcal{O}(N)$, posing a significant scalability bottleneck. We break this barrier for *Wasserstein-stable* functions, i.e., those that are Lipschitz continuous with respect to the Wasserstein-1 metric on input distributions. We constructively prove that a latent dimension of $\mathcal{O}\left(C_D\varepsilon^{-(3D+4)}\log(N+\varepsilon^{-D})\right)$ suffices for uniform approximation as $ \varepsilon\to 0 $, where $D$ is the element dimension and $C_D$ is a constant depending only on $D$. We first discretize the input space into a finite net of measures with covering number polynomial in $N$. We then embed it via a multiscale Random Fourier Feature encoder that guarantees both Lipschitz stability and Hölder separation. Finally, we recover the target function via a McShane-extended Hölder decoder. This result advances the theoretical understanding of the expressivity and scalability of set-based neural architectures.

Many machine learning tasks involve set-valued inputs, such as point clouds, sensor readings, or sampled scenarios, where the output should not depend on the order of the elements. Although DeepSets-style architectures are designed for such permutation-invariant tasks, existing theory suggests that their latent dimension may need to grow linearly with the set size $N$. This paper shows that, for Wasserstein-stable set functions whose outputs change smoothly under small distributional shifts, this linear scaling is unnecessary. We prove that a latent dimension growing only logarithmically with $N$ is sufficient for uniform approximation, using a multiscale random feature embedding and a continuous decoder. This helps explain why compact set-based neural networks can work well for large sets and provides new theoretical insight into their scalability.