Total Variation Distance Estimation through Domain Reduction
Arnab Bhattacharyya, Graham Cormode, Yucheng Fu, Kuldeep S. Meel
Source abstract
Computing the total variation (TV) distance between succinctly represented high-dimensional distributions is generally intractable. We give an FPRAS for TV distance between mixtures of product distributions and, more generally, for a natural class of structured probabilistic circuits. Our main technique is a novel application of domain reduction: Given a family of feature vectors indexed by assignments, we use Lewis-weight sampling to replace the assignment domain by a polynomial-size weighted subset that simultaneously approximates the sum of absolute values of every linear projection. For mixtures of product distributions, we construct such reduced domains incrementally over the coordinates, obtaining the first FPRAS with running time polynomial in both the dimension and the number of mixture components. We then extend the approach to smooth, deterministic, structured-decomposable probabilistic circuits with a common structured architecture.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.