# Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning

arXiv: https://arxiv.org/abs/2002.05378 · HTML: https://mlsanity.com/paper/2002.05378/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2020.

## Built on by (most cited first, 14 of 14)

- [Independence Testing for Bounded Degree Bayesian Network](https://mlsanity.com/paper/2204.08690/) (2022)
- [Total Variation Distance Meets Probabilistic Inference](https://mlsanity.com/paper/2309.09134/) (2023)
- [Learning bounded-degree polytrees with known skeleton](https://mlsanity.com/paper/2310.06333/) (2023)
- [Learning Polynomial Transformations](https://mlsanity.com/paper/2204.04209/) (2022)
- [Learning Sparse Fixed-Structure Gaussian Bayesian Networks](https://mlsanity.com/paper/2107.10450/) (2021)
- [Approximating the total variation distance between spin systems](https://mlsanity.com/paper/2502.05437/) (2025)
- [Total Variation Distance Estimation in Autoregressive Models](https://mlsanity.com/paper/2607.19510/) (2026)
- [Efficient inference of interventional distributions](https://mlsanity.com/paper/2107.11712/) (2021)
- [Distribution Learning Meets Graph Structure Sampling](https://mlsanity.com/paper/2405.07914/) (2024)
- [Approximating the Total Variation Distance between Gaussians](https://mlsanity.com/paper/2503.11099/) (2025)
- [Zero-Shot Attribution for Large Language Models: A Distribution Testing Approach](https://mlsanity.com/paper/2506.20197/) (2025)
- [Dimension Agnostic Testing of Survey Data Credibility through the Lens of Regression](https://mlsanity.com/paper/2508.20616/) (2025)
- [On approximating the f-divergence between two Ising models](https://mlsanity.com/paper/2509.05016/) (2025)
- [On Computing Total Variation Distance Between Mixtures of Product Distributions](https://mlsanity.com/paper/2605.03839/) (2026)

## Abstract (arXiv)

We design efficient distance approximation algorithms for several classes of structured high-dimensional distributions. Specifically, we show algorithms for the following problems: - Given sample access to two Bayesian networks P1 and P2 over known directed acyclic graphs G1 and G2 having n nodes and bounded in-degree, approximate dtv(P1,P2) to within additive error ε using poly(n,ε) samples and time - Given sample access to two ferromagnetic Ising models P1 and P2 on n variables with bounded width, approximate dtv(P1, P2) to within additive error ε using poly(n,ε) samples and time - Given sample access to two n-dimensional Gaussians P1 and P2, approximate dtv(P1, P2) to within additive error ε using poly(n,ε) samples and time - Given access to observations from two causal models P and Q on n variables that are defined over known causal graphs, approximate dtv(Pa, Qa) to within additive error ε using poly(n,ε) samples, where Pa and Qa are the interventional distributions obtained by the intervention do(A=a) on P and Q respectively for a particular variable A. Our results are the first efficient distance approximation algorithms for these well-studied problems. They are derived using a simple and general connection to distribution learning algorithms. The distance approximation algorithms imply new efficient algorithms for em tolerant testing of closeness of the above-mentioned structured high-dimensional distributions.