Learning Wasserstein-Stable Permutation-Invariant Functions: $N$-Independent Latent Dimension and Sample Complexity

Learning permutation-invariant functions over sets is fundamental to many applications, including point-cloud analysis, multi-instance learning, and data-driven stochastic optimization. DeepSets provide a standard architecture for this task by applying a shared encoder to individual elements and aggregating their representations. However, whether increasing the set size $N$ necessarily increases the complexity of either representation or learning remains open. Existing latent-dimension bounds scale from $\mathcal{O}(N)$ for exact multiset representation to $\mathcal{O}(\log N)$ for Wasserstein-stable approximation, while the dependence of the required number of training samples on $N$ remains open. In this paper, we show that both the latent dimension and the sample complexity can be made independent of $N$ for Wasserstein-stable permutation-invariant functions. We first develop a Soft-Histogram Encoder and prove an $N$-independent latent-dimension bound for continuous DeepSets approximation. We then establish an $N$-independent sample-complexity bound for learning such functions from i.i.d. training sets. To improve data efficiency under limited labeling budgets arising from expensive target evaluations, we further develop permutation-aware maximin sampling (PAMS), which selects training sets to maximize their separation under optimal permutation matching. Numerical experiments on resource-allocation problems validate the predicted $N$-independent scaling of both the critical latent dimension and the number of training sets required to reach a fixed prediction accuracy, and show that PAMS achieves lower prediction error than random sampling under the same labeling budget. Together, these results establish that Wasserstein stability enables cardinality-independent representation and learning, while providing a practical route toward data-efficient permutation-invariant learning.