Deterministic method approximates distance between complex distributions efficiently
On Deterministically Computing Total Variation Distance via Zonotope Compression
Data Structures and Algorithms
Summary
Measuring how different two complex probability models are can be very hard and slow. The authors developed a step-by-step method that represents this difference using special geometric shapes called zonotopes. This new approach lets them quickly and accurately estimate the difference for several types of models, including mixtures of simpler distributions, Markov chains, and certain network models called latent-tree Ising models. Their method works with guaranteed precision and reasonable running times, making analysis of high-dimensional data more practical.
What this means in practice
- •For data scientists: Estimate difference between complex probabilistic models with guaranteed accuracy and feasible computation time for model comparison or selection.
- •For machine learning engineers: Improve evaluation of mixture models and Markov chain differences to enable reliable training and tuning of probabilistic models.
Authors
Yucheng Fu
Abstract
We study deterministic relative approximation of the total variation distance between high-dimensional distributions given by succinct descriptions. We develop an abstract deterministic approximation framework based on representing the total variation distance as a support function of a low-dimensional zonotope. As applications, we obtain FPTASs for several models. Given two mixtures of product distributions over $[q]^n$ with a total of $K$ component distributions, our algorithm approximates their TV-distance within a factor of $1+\varepsilon$ in time $\widetilde O_K(nq(n/\varepsilon)^{2K})$. We also give an FPTAS for mixtures of $n$-step Markov chains over $[q]^n$ with a total of $K$ component distributions, with running time $\widetilde O_K(nq^2(n/\varepsilon)^{2K})$. Finally, for two latent-tree Ising models with the same underlying tree topology, we give an FPTAS for the TV-distance between their leaf marginals in time $O(|V|^{13}\varepsilon^{-12})$.