Sample Complexity of Probability Divergences under Group Symmetry

Ziyu Chen; Markos Katsoulakis; Luc Rey-Bellet; Wei Zhu

ICML 2023poster14 citations

Sample Complexity of Probability Divergences under Group Symmetry

Ziyu Chen, Markos Katsoulakis, Luc Rey-Bellet, Wei Zhu

Abstract

We rigorously quantify the improvement in the sample complexity of variational divergence estimations for group-invariant distributions. In the cases of the Wasserstein-1 metric and the Lipschitz-regularized $\alpha$-divergences, the reduction of sample complexity is proportional to an ambient-dimension-dependent power of the group size. For the maximum mean discrepancy (MMD), the improvement of sample complexity is more nuanced, as it depends on not only the group size but also the choice of kernel. Numerical simulations verify our theories.

BibTeX

@inproceedings{icml2023_samplecomplexity,
  title = {Sample Complexity of Probability Divergences under Group Symmetry},
  author = {Ziyu Chen and Markos Katsoulakis and Luc Rey-Bellet and Wei Zhu},
  booktitle = {ICML 2023},
  year = {2023}
}