arXiv preprint ·
On Deterministically Computing Total Variation Distance via Zonotope Compression
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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})$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
High-Dimensional Ultra-Log-Concave Distributions
Weighted universal Value-at-Risk Superadditivity for discrete distributions
Quantum-Enhanced Sampling of Schrödinger Bridges
Affine Volterra covariance processes and application to commodity markets
Local Weak Limits for Equilibrium and Risk in Economic Networks
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.