Uniform $\mathcal{C}^k$ Approximation of $G$-Invariant and Antisymmetric
  Functions, Embedding Dimensions, and Polynomial Representations
Soumya Ganguly Khoa Tran Rahul Sarkar
For any subgroup $G$ of the symmetric group $\mathcal{S}_n$ on $n$ symbols,
we present results for the uniform $\mathcal{C}^k$ approximation of
$G$-invariant functions by $G$-invariant polynomials. For the case of totally
symmetric functions ($G = \mathcal{S}_n$), we show that this gives rise to the
sum-decomposition Deep Sets ansatz of Zaheer et al. (2018), where both the
inner and outer functions can be chosen to be smooth, and moreover, the inner
function can be chosen to be independent of the target function being
approximated. In particular, we show that the embedding dimension required is
independent of the regularity of the target function, the accuracy of the
desired approximation, as well as $k$. Next, we show that a similar procedure
allows us to obtain a uniform $\mathcal{C}^k$ approximation of antisymmetric
functions as a sum of $K$ terms, where each term is a product of a smooth
totally symmetric function and a smooth antisymmetric homogeneous polynomial of
degree at most $\binom{n}{2}$. We also provide upper and lower bounds on $K$
and show that $K$ is independent of the regularity of the target function, the
desired approximation accuracy, and $k$.