提出高效算法估算两个高斯分布的总变差距离
Approximating the Total Variation Distance between Gaussians
- 将连续高斯分布的变差距离计算转化为离散变量方法
- 可在多项式时间内实现任意精度逼近，复杂度依赖1/ε和log(距离)
- 对统计学与机器学习中的分布比较有实用价值
总变差距离是统计学与概率论中的核心度量。然而，关于其算法计算的研究直到近年才开始系统展开。本文聚焦多维高斯分布这一重要情形，研究如何以ε相对误差逼近两多维高斯分布D₁、D₂之间的总变差距离D := d_TV(D₁,D₂)。此前工作仅能获得固定常数相对误差的闭式解。本文给出新算法：对任意n维高斯分布及任意ε > 0，可在poly(n, 1/ε, log(1/D))次操作内实现ε相对精度逼近。核心技术是将近期离散随机变量变差距离的进展推广至连续情形的归约方法。
原文摘要 · Abstract (English)
The total variation distance is a metric of central importance in statistics and probability theory. However, somewhat surprisingly, questions about computing it algorithmically appear not to have been systematically studied until very recently. In this paper, we contribute to this line of work by studying this question in the important special case of multivariate Gaussians. More formally, we consider the problem of approximating the total variation distance between two multivariate Gaussians to within an $ε$-relative error. Previous works achieved a fixed constant relative error approximation via closed-form formulas. In this work, we give algorithms that given any two $n$-dimensional Gaussians $D_1,D_2$, and any error bound $ε> 0$, approximate the total variation distance $D := d_{TV}(D_1,D_2)$ to $ε$-relative accuracy in $\text{poly}(n,\frac{1}ε,\log \frac{1}{D})$ operations. The main technical tool in our work is a reduction that helps us extend the recent progress on computing the TV-distance between discrete random variables to our continuous setting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。