Metadata only
Date
2024Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
Total variation distance (TV distance) is an important measure for the difference between two distributions. Recently, there has been progress in approximating the TV distance between product distributions: a deterministic algorithm for a restricted class of product distributions (Bhattacharyya, Gayen, Meel, Myrisiotis, Pavan and Vinodchandran 2023) and a randomized algorithm for general product distributions (Feng, Guo, Jerrum and Wang 2023). We give a deterministic fully polynomial-time approximation algorithm (FPTAS) for the TV distance between product distributions. Given two product distributions P and Q over [q](n), our algorithm approximates their TV distance with relative error epsilon in time O (qn(2)/epsilon log q log n/epsilon Delta(TV)(P,Q)). Show more
Our algorithm is built around two key concepts: 1) The likelihood ratio as a distribution, which captures sufficient information to compute the TV distance. 2) We introduce a metric between likelihood ratio distributions, called the minimum total variation distance. Our algorithm computes a sparsified likelihood ratio distribution that is close to the original one w.r.t. the new metric. The approximated TV distance can be computed from the sparsified likelihood ratio. Show more
Our technique also implies deterministic FPTAS for the TV distance between Markov chains.
Publication status
publishedExternal links
Editor
Book title
Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Pages / Article No.
Publisher
SIAMEvent
Organisational unit
02889 - ETH Institut für Theoretische Studien / ETH Institute for Theoretical Studies
More
Show all metadata
ETH Bibliography
yes
Altmetrics