Article Source

• Approximating the TV Distance Between Two Product Distributions

Approximating the TV Distance Between Two Product Distributions

• Weiming Feng (University of Edinburgh)
• https://simons.berkeley.edu/talks/weiming-feng-university-edinburgh-2023-10-20
• Probabilistic Circuits and Logic

Abstract

The total variation (TV) distance is a fundamental metric to measure the difference between two distributions. Recently, Bhattacharyya et al. initiated the problem of computing the TV distance between two high-dimensional distributions. They proved that the exact computing of TV distance, even for product distributions over the Boolean domain, is #P-hard.

In this talk, I will discuss some recent progress in approximating the TV distance between two product distributions. I will introduce a randomized approximation algorithm based on the coupling technique and a deterministic algorithm based on the sparsification of distributions.