Research map / Learning theory and algorithms / Sample complexity

Computational Explorations of Total Variation Distance

ICLR 2025 · Learning theory and algorithms › Sample complexity · approach: Learning under log-concave distributions · 0 citations (OpenAlex)

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.

Gives a deterministic polynomial-time algorithm for checking equivalence of mixtures of product distributions via a linear-algebra basis construction, and shows that approximating TV distance between Ising models admits no FPRAS unless NP ⊆ RP.

Problem

Efficiently deciding whether two mixtures of product distributions are equal (TV distance zero), and the computational hardness of approximating TV distance between Ising models.

Approach

Equivalence of mixtures of products is reduced inductively over coordinates to maintaining a linear basis of coefficient vectors, checked via Gaussian elimination; for Ising models, an approximation-preserving reduction maps partition-function estimation to atomic marginals and then to TV distance between Ising models.

Key results

• Deterministic algorithm decides equality of two mixtures of k product distributions over n variables with alphabet Sigma in O(n k^4 |Sigma|^4) time, outputting a distinguishing marginal point if unequal.
• Under NP not subset of RP, no FPRAS exists for estimating TV distance between any two Ising models, via reduction from partition function estimation to atomic marginals to TV distance.

Surprising findings

• Mixtures of product distributions can equal each other while having different parameter sets, so equivalence is not reducible to parameter matching.

Limitations

• Hardness result only rules out FPRAS under NP not subset of RP; no algorithm for approximating Ising TV distance is given.
• Equivalence algorithm's applicability to Bayes nets is ruled out by NP-hardness, so extension is open.

Experimental setup

Builds on: Gaussian elimination Ising model partition function hardness (NP not in RP)

Closest papers by meaning

• Total Variation Distance Meets Probabilistic Inference (ICML 2024 · similarity 0.89)
• Total Variation Distance Estimation in Autoregressive Models (NeurIPS 2026 · similarity 0.84)
• A New Robust Partial p-Wasserstein-Based Metric for Comparing Distributions (ICML 2024 · similarity 0.83)
• Efficient Mixture Learning in Black-Box Variational Inference (ICML 2024 · similarity 0.82)
• Product Distribution Learning with Imperfect Advice (NeurIPS 2025 · similarity 0.82)
• Subtractive Mixture Models via Squaring: Representation and Learning (ICLR 2024 · similarity 0.82)