• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
On Approximating Total Variation Distance.
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S Meel, Dimitrios Myrisiotis, Pavan A. and N. V. Vinodchandran.
In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), July 2023.
Total variation distance (TV distance) is a fundamental notion of distance between probability distributions. In this work, we introduce and study the problem of computing the TV distance of two product distributions over the domain 0,1^n. In particular, we establish the following results.1. The problem of exactly computing the TV distance of two product distributions is #P-complete. This is in stark contrast with other distance measures such as KL, Chi-square, and Hellinger which tensorize over the marginals leading to efficient algorithms.2. There is a fully polynomial-time deterministic approximation scheme (FPTAS) for computing the TV distance of two product distributions P and Q where Q is the uniform distribution. This result is extended to the case where Q has a constant number of distinct marginals. In contrast, we show that when P and Q are Bayes net distributions the relative approximation of their TV distance is NP-hard.
@inproceedings{BGMMAV23, title={On Approximating Total Variation Distance}, author={ Bhattacharyya, Arnab and Gayen, Sutanu and Meel, Kuldeep S and Myrisiotis, Dimitrios and A., Pavan and Vinodchandran, N. V.} abstract={Total variation distance (TV distance) is a fundamental notion of distance between probability distributions. In this work, we introduce and study the problem of computing the TV distance of two product distributions over the domain {0,1}^n. In particular, we establish the following results. 1. The problem of exactly computing the TV distance of two product distributions is #P-complete. This is in stark contrast with other distance measures such as KL, Chi-square, and Hellinger which tensorize over the marginals leading to efficient algorithms. 2. There is a fully polynomial-time deterministic approximation scheme (FPTAS) for computing the TV distance of two product distributions P and Q where Q is the uniform distribution. This result is extended to the case where Q has a constant number of distinct marginals. In contrast, we show that when P and Q are Bayes net distributions the relative approximation of their TV distance is NP-hard.} publication_type={conference}, booktitle=IJCAI, year={2023}, month=jul, bib2html_rescat={Distribution Testing}, bib2html_pubtype={Refereed Conference}, bib2html_dl_pdf={../Papers/ijcai23-bggmpv.pdf}, }
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Thu Aug 22, 2024 18:37:34