On Approximating Total Variation Distance
On Approximating Total Variation Distance
复制标题
DOI：
10.24963/ijcai.2023/387
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Arnab Bhattacharyya;Sutanu Gayen;Kuldeep S. Meel;Dimitrios Myrisiotis;A. Pavan;N. V. Vinodchandran
中科院分区：
文献类型：
--
作者：
Arnab Bhattacharyya;Sutanu Gayen;Kuldeep S. Meel;Dimitrios Myrisiotis;A. Pavan;N. V. Vinodchandran
总变差距离（TV距离）是概率分布之间距离的基本概念。在这项工作中，我们介绍和研究的问题，计算两个产品分布的TV距离的区域{0，1}^n。特别是，我们建立了以下结果。1.精确计算两个乘积分布的TV距离的问题是P-完全的。这与其他距离度量（如KL，卡方和Hellinger）形成鲜明对比，这些距离度量在边缘上进行张量化，从而产生有效的算法。2.有一个完全多项式时间确定性近似方案（FPTAS）用于计算两个产品分布P和Q的TV距离，其中Q是均匀分布。这一结果被扩展到的情况下，Q有一个常数的不同的边缘。相反，我们表明，当P和Q是贝叶斯网络分布的相对近似的电视距离是NP-困难的。
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.