Permutation invariant functions: statistical tests, density estimation, and computationally efficient embedding
<|reference_start|>Permutation invariant functions: statistical tests, density estimation, and computationally efficient embedding: 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.<|reference_end|>
@article{chaimanowong2024permutation,
    title={Permutation invariant functions: statistical tests, density estimation,
  and computationally efficient embedding},
    author={Wee Chaimanowong, Ying Zhu},
    journal={arXiv preprint arXiv:2403.01671},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.01671},
    primaryClass={cs.LG}
}