Permutation Invariant Functions: Statistical Testing, Density Estimation, and Metric Entropy

Wee Chaimanowong, Ying Zhu
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:2908-2916, 2025.

Abstract

Permutation invariance is among the most common symmetries that can be exploited to simplify complex problems in machine learning. There has been a tremendous surge of research activities in building permutation invariant machine learning architectures. However, less attention is given to: (1) how to statistically test for the assumption of permutation invariance of coordinates in a random vector where the dimension is allowed to grow with the sample size; (2) how to estimate permutation invariant density functions; (3) how much “smaller” is the class of smooth functions with permutation invariance compared to that without permutation invariance. In this paper, we take a step back and examine these fundamental questions. In particular, our testing method is based on a sorting trick, and our estimation method is based on an averaging trick. These tricks substantially simplify the exploitation of permutation invariance. We also analyze the metric entropy of permutation invariant function classes and compare them with their counterparts without imposing permutation invariance.

Cite this Paper

BibTeX
@InProceedings{pmlr-v258-chaimanowong25a, title = {Permutation Invariant Functions: Statistical Testing, Density Estimation, and Metric Entropy}, author = {Chaimanowong, Wee and Zhu, Ying}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {2908--2916}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/chaimanowong25a/chaimanowong25a.pdf}, url = {https://proceedings.mlr.press/v258/chaimanowong25a.html}, abstract = {Permutation invariance is among the most common symmetries that can be exploited to simplify complex problems in machine learning. There has been a tremendous surge of research activities in building permutation invariant machine learning architectures. However, less attention is given to: (1) how to statistically test for the assumption of permutation invariance of coordinates in a random vector where the dimension is allowed to grow with the sample size; (2) how to estimate permutation invariant density functions; (3) how much “smaller” is the class of smooth functions with permutation invariance compared to that without permutation invariance. In this paper, we take a step back and examine these fundamental questions. In particular, our testing method is based on a sorting trick, and our estimation method is based on an averaging trick. These tricks substantially simplify the exploitation of permutation invariance. We also analyze the metric entropy of permutation invariant function classes and compare them with their counterparts without imposing permutation invariance.} }
Endnote
%0 Conference Paper %T Permutation Invariant Functions: Statistical Testing, Density Estimation, and Metric Entropy %A Wee Chaimanowong %A Ying Zhu %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-chaimanowong25a %I PMLR %P 2908--2916 %U https://proceedings.mlr.press/v258/chaimanowong25a.html %V 258 %X Permutation invariance is among the most common symmetries that can be exploited to simplify complex problems in machine learning. There has been a tremendous surge of research activities in building permutation invariant machine learning architectures. However, less attention is given to: (1) how to statistically test for the assumption of permutation invariance of coordinates in a random vector where the dimension is allowed to grow with the sample size; (2) how to estimate permutation invariant density functions; (3) how much “smaller” is the class of smooth functions with permutation invariance compared to that without permutation invariance. In this paper, we take a step back and examine these fundamental questions. In particular, our testing method is based on a sorting trick, and our estimation method is based on an averaging trick. These tricks substantially simplify the exploitation of permutation invariance. We also analyze the metric entropy of permutation invariant function classes and compare them with their counterparts without imposing permutation invariance.
APA
Chaimanowong, W. & Zhu, Y.. (2025). Permutation Invariant Functions: Statistical Testing, Density Estimation, and Metric Entropy. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:2908-2916 Available from https://proceedings.mlr.press/v258/chaimanowong25a.html.

Related Material