  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: (1) how to statistically
test for permutation invariance of coordinates in a random vector where the
dimension is allowed to grow with the sample size; (2) how to leverage
permutation invariance in estimation problems and how does it help reduce
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 permutation invariant function
classes and compare them with their counterparts without imposing permutation
invariance; (iv) deriving an embedding of permutation invariant reproducing
kernel Hilbert spaces for efficient computation. 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.
