Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 26 min ago
PreprintCC BY 4.0arXiv

Total Variation Distance Estimation through Domain Reduction

  • Arnab Bhattacharyya
  • Graham Cormode
  • Yucheng Fu
  • Kuldeep S. Meel
Open at sourcePDFDOICite

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, structured-decomposable probabilistic circuits with a common structured architecture.

Related

  1. Interpretable intrinsic dimension estimation through componentwise calibration of distance and angle
    Chih-Hsuan Huang, Chih-Wei Chen, Szu-Chi Chung
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  2. Total Variation Distance between Product Distributions: an Analytic Proxy
    Ariel Avital, Aryeh Kontorovich, Roman Vershynin +1
    arXivPreprintarXiv licenceFull textProbabilityStatisticsarXiv
  3. On Deterministically Computing Total Variation Distance via Zonotope Compression
    Yucheng Fu
    arXivPreprintCC BY 4.0Full textProbabilityarXiv
  4. Stability of optimal transport maps and second variation of the 2-Monge-Kantorovich distance
    F. -U. Caja-Lopez, Matias G. Delgadino, Jun Kitagawa
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsarXiv
  5. Testing Implies Distance Estimation with Polynomial Loss
    Gaia Carenini, Cameron Seth
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{bhattacharyya2026total,
  title = {{Total Variation Distance Estimation through Domain Reduction}},
  author = {Arnab Bhattacharyya and Graham Cormode and Yucheng Fu and Kuldeep S. Meel},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.18707},
  eprint = {2609.18707},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.18707},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Total Variation Distance Estimation through Domain Reduction
AU  - Arnab Bhattacharyya
AU  - Graham Cormode
AU  - Yucheng Fu
AU  - Kuldeep S. Meel
PY  - 2026
DA  - 2026/10/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.18707
UR  - https://arxiv.org/abs/2609.18707
AB  - 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, structured-decomposable probabilistic circuits with a common structured architecture.
ER  -