Research map / Probabilistic and scientific modeling / Variational and generative sampling
Total Variation Distance Meets Probabilistic Inference
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Reduces relative approximation of total variation distance between same-structure Bayes nets to probabilistic inference queries on a related Bayes net (via partial couplings), yielding an FPRAS for bounded/log treewidth Bayes nets and for TV distance to uniform.
Problem
Estimating total variation (TV) distance between high-dimensional distributions, such as Bayes nets over a common DAG, has only had efficient relative-approximation algorithms for product distributions; an FPRAS for Bayes nets (even trees) was open.
Approach
A structure-preserving reduction from relative TV-distance approximation to probabilistic inference, using a new notion of partial coupling realized as a Bayes net over the same DAG; importance sampling with an estimator f(w)=g*(w)/g(w) and a normalizer Z computed by inference queries.
Key results
- Gives a (1+eps)-relative approximation of TV distance between two Bayes nets over the same DAG of n nodes with running time T(G,l^2)*O(n^3 eps^-2 l log(1/delta)) using inference queries.
- FPRAS for TV distance between two Bayes nets of treewidth O(log n) and constant alphabet, running in poly(n) time, resolving the open question for tree-structured Bayes nets.
- Exact TV distance between a bounded in-degree Bayes net and the uniform distribution is #P-complete, while an FPRAS exists for any Bayes net vs. uniform with time O(n^3 l^(2d+2) eps^-2 log(1/delta)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Reduce TV-distance estimation to probabilistic inference over a Bayes net with the same DAG | TV estimation between same-DAG Bayes nets · Same-DAG Bayes nets, alphabet size ℓ | relative approximation guarantee: (1+ε)-relative approximation with probability at least 1−δ | Helped |
| Use the reduction with variable elimination for logarithmic-treewidth Bayes nets | TV-distance estimation between same-DAG Bayes nets · Same-DAG Bayes nets, treewidth O(log n), alphabet size O(1) | running time: poly(n)·O(ε^{-2}logδ^{-1}) | Helped |
| Estimate TV distance to the uniform distribution using uniform samples and Bayes-net probability evaluations | TV distance between a Bayes net and the uniform distribution · Bayes net and uniform distribution | running time: O(n^3ℓ^{2d+2}ε^{-2}logδ^{-1}) | Helped |
Surprising findings
- Exact TV distance computation is #P-complete even for product distributions, where inference is easy.
Limitations
- The general reduction requires alphabet and treewidth conditions for efficient inference; for TV to uniform the running time is exponential in in-degree d.
- Partial coupling is a relaxation; the approach is stated for directed graphical models only.
- The paper leaves undirected graphical models and other distances such as Wasserstein as open problems.
Experimental setup
Baselines: FPRAS for product distribution TV distance FPTAS for product distribution TV distance additive TV estimation via sampling
Builds on: optimal coupling variable elimination Hoeffding's inequality product distribution TV estimation (Bhattacharyya et al.)
Closest papers by meaning
- Computational Explorations of Total Variation Distance (ICLR 2025 · similarity 0.89)
- Probabilistic Circuits for Variational Inference in Discrete Graphical Models (NeurIPS 2020 · similarity 0.87)
- Total Variation Distance Estimation in Autoregressive Models (NeurIPS 2026 · similarity 0.85)
- Fast Wasserstein rates for estimating probability distributions of probabilistic graphical models (NeurIPS 2026 · similarity 0.85)
- TreeVI: Reparameterizable Tree-structured Variational Inference for Instance-level Correlation Capturing (NeurIPS 2024 · similarity 0.85)
- Efficient Mixture Learning in Black-Box Variational Inference (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.