The Intractability of Total Variation Distance in High Dimensions

28 concepts16 papers1 proposal

Statistical distance measures are the bedrock of machine learning, information theory, and verification. They allow us to quantify how much two representations of reality differ. Among these, the Total Variation (TV) distance is arguably the most intuitive: it represents the maximum possible difference in probability that two distributions can assign to the exact same event.

For simple, independent distributions—such as product distributions—one might expect that calculating the TV distance would be computationally trivial. After all, other foundational metrics like Kullback-Leibler (KL) divergence or Hellinger distance can be computed in linear time relative to the number of dimensions.

However, as proven by Arnab Bhattacharyya et al. in Total Variation Distance for Product Distributions is #P-Complete, TV distance is a stark computational outlier. Even when every variable across two distributions is completely independent, computing the exact TV distance is $\mathsf{\#P}$-complete—placing it in the same complexity class as the hardest counting problems in computer science. Understanding why this metric resists efficient computation requires looking at how it behaves across high-dimensional spaces.

Why TV Distance Fails to Tensorize

To build intuition for why TV distance is so uniquely difficult, we must look at the property of tensorization. In On the tensorization of the variational distance, Aryeh Kontorovich notes that the exponential growth of a distribution's support size creates an inherent barrier to direct computation.

When we compute the KL divergence between two product distributions, the log-likelihood ratio splits cleanly into a sum of independent terms:

$$\log \prod \frac{p_i(x_i)}{q_i(x_i)} = \sum \log \frac{p_i(x_i)}{q_i(x_i)}$$

This clean decomposition allows us to evaluate each dimension in isolation and sum the results, scaling linearly with the number of dimensions.

TV distance, by contrast, does not tensorize. Mathematically, it is defined as:

$$D_{\text{TV}}(P, Q) = \frac{1}{2} \sum_{x} |P(x) - Q(x)|$$

As Arnab Bhattacharyya et al. explain in On Approximating Total Variation Distance, finding this sum requires identifying the specific subset of the global sample space where $P(x) > Q(x)$. Because the boundary of this optimal subset can cut across dimensions in a highly complex, combinatorial fashion, you cannot solve the problem by looking at each dimension independently. To find the exact boundary, an algorithm is forced to confront the geometry of the entire exponentially large state space.

Hardness Escalation: Marginals and Graphical Models

If independent product distributions are already $\mathsf{\#P}$-complete, introducing even minimal structured dependencies makes the problem entirely intractable. For instance, the authors of On Approximating Total Variation Distance demonstrate that adding sparse dependencies—such as those found in simple Bayesian networks—renders even the basic task of deciding whether the TV distance is non-zero $\mathsf{NP}$-hard.

A particularly striking manifestation of this hardness occurs when we look at marginal distributions. In many physical and statistical systems, like spin systems (e.g., the Ising or hardcore models), we have efficient algorithms to sample from or count configurations for the full global distribution. One might naturally assume that this tractability extends to comparing their marginals.

However, Weiming Feng 0001 et al. prove in Approximating the total variation distance between spin systems that approximating the TV distance between the marginal distributions of spin systems remains $\mathsf{\#P}$-hard. This reveals a fundamental complexity gap: even when a global distribution is perfectly well-behaved and easy to sample from, projecting it down to a subset of variables completely obscures the geometric boundaries needed to compute or approximate the TV distance. Similarly, Bahar Taskesen et al. demonstrate in Discrete Optimal Transport with Independent Marginals is #P-Hard that computing optimal transport distances remains $\mathsf{\#P}$-hard even when one of the discrete distributions has independent marginals.

The Bottleneck in Machine Learning and Verification

This computational barrier severely limits practical applications in machine learning and system verification, where comparing high-dimensional distributions is a core requirement.

Consider the problem of distribution shift. To guarantee that a model trained on a source distribution will perform reliably on a shifted test distribution, classical learning theory relies on bounding the distance or "discrepancy" between the two. But as Adam Klivans et al. point out in Testable Learning with Distribution Shift and Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds, calculating these global discrepancy distances is $\mathsf{NP}$-hard for complex classifier classes, rendering traditional domain adaptation bounds uncomputable in practice.

A similar bottleneck appears in formal verification. In Converging from Branching to Linear Metrics on Markov Chains, Giorgio Bacci et al. show that determining whether linear-time trace distances between Markov chains exceed a given threshold is $\mathsf{NP}$-hard. When verifying machine learning models like probabilistic circuits, Yash Pote et al. note in Testing Probabilistic Circuits that the exponential size of the state space makes direct enumeration impossible, creating an urgent need for efficient approximation alternatives.

Bypassing Hardness via Structural Constraints

Because exact computation is fundamentally blocked, recent research focuses on routing around this intractability. By shifting the goal from exact computation to designing Fully Polynomial-Time Randomized Approximation Schemes (FPRAS) or Deterministic Approximation Schemes (FPTAS), researchers exploit specific structural constraints to make the problem tractable.

1. Equivalence to Probabilistic Inference

In Total Variation Distance Estimation Is as Easy as Probabilistic Inference and Total Variation Distance Meets Probabilistic Inference, Arnab Bhattacharyya et al. establish a deep theoretical bridge between distance estimation and inference. By introducing a structural framework known as partial couplings, they prove that if you can perform efficient probabilistic inference on a graphical model (such as a Bayesian network with a manageable treewidth), you can also efficiently approximate its TV distance via an FPRAS.

2. Restricting Marginal Parameters

Another avenue is restricting the parameter space of the distributions themselves. In On Approximating Total Variation Distance, the authors demonstrate that an FPTAS becomes possible if one distribution is completely uniform, or if the total number of unique marginal probabilities across all dimensions is bounded by a constant. Limiting the variety of parameters prevents the decision boundary from becoming too combinatorially complex.

3. Localized and Relaxed Metrics

When global distance metrics fail, we can change the question. To handle distribution shift without calculating intractable global discrepancies, Gautam Chandrasekaran et al. in Efficient Discrepancy Testing for Learning with Distribution Shift propose testing localized discrepancy distance relative to a specific classifier. This bypasses the need to search the entire hypothesis space.

From an optimization perspective, Jean B. Lasserre demonstrates in A hierarchy of convex relaxations for the total variation distance that the infinite-dimensional dual space of TV distance can be bypassed entirely. By leveraging the Moment-SOS hierarchy, the author constructs a sequence of solvable semidefinite programs (SDPs) that use known moments to converge deterministically to the true distance.

Through these diverse lenses, the computer science community has mapped a clear boundary: while the global geometry of Total Variation distance makes it fundamentally hard, exploiting inference tractability, parameter uniformity, or localized relaxations allows us to safely navigate its complexity.

Key Foundational Work

Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing (2018) — contributed 1 concept elements to this direction.
Converging from Branching to Linear Metrics on Markov Chains (2015) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_hardness_of_marginal_tv_distance_approxi_996eddcd,
  title = {hardness of marginal TV distance approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hardness-of-marginal-tv-distance-approximation/rdr_996eddcd502d4a89aa11ae68af0b52a2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_hardness_of_marginal_tv_distance_approxi_996eddcd_v1,
  title = {hardness of marginal TV distance approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hardness-of-marginal-tv-distance-approximation/rdr_996eddcd502d4a89aa11ae68af0b52a2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake