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

Abstract

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.