Permutation invariant functions: statistical tests, dimension reduction
  in metric entropy and estimation
Wee Chaimanowong Ying Zhu
Permutation invariance is among the most common symmetry that can be
exploited to simplify complex problems in machine learning (ML). There has been
a tremendous surge of research activities in building permutation invariant ML
architectures. However, less attention is given to how to statistically test
for permutation invariance of variables in a multivariate probability
distribution where the dimension is allowed to grow with the sample size. Also,
in terms of a statistical theory, little is known about how permutation
invariance helps with estimation in reducing dimensions. In this paper, we take
a step back and examine these questions in several fundamental problems: (i)
testing the assumption of permutation invariance of multivariate distributions;
(ii) estimating permutation invariant densities; (iii) analyzing the metric
entropy of smooth permutation invariant function classes and compare them with
their counterparts without imposing permutation invariance; (iv) kernel ridge
regression of permutation invariant functions in reproducing kernel Hilbert
space. In particular, our methods for (i) and (iv) are based on a sorting trick
and (ii) is based on an averaging trick. These tricks substantially simplify
the exploitation of permutation invariance.