Computational Explorations of Total Variation Distance

This paper studies two fundamental questions about high-dimensional probability distributions.

1. Is there a polynomial-time algorithm which can decide whether two mixtures of product distributions on the hypercube are equal to each other?
2. Is there a polynomial-time algorithm which can accurately approximate the total variation distance between two Ising model distributions?

The paper answers (1) affirmatively, giving a very nice linear algebraic algorithm which can test equivalence between mixtures of product distributions on the cube, given access to the parameters of the distributions. The paper answers (2) negatively, showing that unless NP is contained in RP (that is, unless NP-complete problems have randomized polynomial time algorithms), the total variation distance between Ising models is inapproximable.

Strengths: The paper studies truly fundamental problems which will be of broad appeal to the ICLR audience. The results are convincing, and the equivalence-checking algorithm is very nice.

Weaknesses: These problems are so fundamental that it is a little hard to believe they are not already well studied. It would be nice if the related work section were expanded. It would be nice if the algorithm also meant you can test equivalence given samples.

Overall, I recommend accepting the paper to ICLR, on the basis that the results are about a very fundamental set of problems, and the equivalence testing algorithm is very clean.

Questions:

• Does result (1) mean you can also do equivalence testing from samples?
• Is the linear algebraic method you describe similar to any existing equivalence tester in the literature?

The paper studies some properties about the complexity of computing the Total Variation Distance between distributions. The authors consider the case of the mixure of product distributions and the case of Ising models. In the first case they show a polytime algo that has access to the marginals and checks the equivalnece of two mixtures. For the second case they show hardness of approximating TVD by an FPRAS under the hypothesis NP not included in RP. The two results are sound and well written. However, the contribution is limited. I think neither of the two results are very significant alone and together the overall contribution is not very much more.

The paper has two main contributions: (1) An algorithm for checking equivalence for mixtures of product distributions (2) A hardness reduction for approximating the total variation distance between two Ising models.

The problem of checking equivalence of product distributions is takes the following as input: we are given $w_1,\cdots, w_k, P_1,\cdots,P_k$ and $v_1,\cdots, v_k, Q_1,\cdots,Q_k$ where:

1. Each of $P_1,\cdots,P_k$ and $Q_1,\cdots,Q_k$ is a product distribution over $\Sigma^n$.
2. $w_1,\cdots, w_k$ are the weights for $P_1,\cdots,P_k$ and $v_1,\cdots, v_k$ are the weights for $Q_1,\cdots,Q_k$. So, the first distribution $P$ is the mixture of $P_1,\cdots,P_k$ each weighted by $w_1,\cdots, w_k$ and the second distribution $Q$ is the mixture of $Q_1,\cdots,Q_k$ each weighted by $v_1,\cdots, v_k$. The task is to determine wether the two mixture distributions are the same.

Here is an example (from page 2) an equal mixture of $Bern(1/3)$ and $Bern(2/3)$ equals to the distribution $Bern(1/2)$. This illustrates how a mixture of two product distributions can equal a different product distribution.

The paper gives a deterministic algorithm whose run-time is $O(nk^4 |\Sigma|^4)$ which is polynomial in the input size which equals $kn|\Sigma|$. One idea the algorithm uses is that if the two mixtures $w_1P_1+,\cdots, +P_kw_k$ and $v_1Q_1+,\cdots, +v_k Q_k$ are equal, then (after a normalization) the mixtures $w_1P_1+,\cdots, +P_jw_j$ and $v_1Q_1+,\cdots, +v_j Q_j$ are also equal for every $j$. The algorithm utilizes the idea by iteratively establishing equivalence for $j=1,2..., k$ at every step $j$ establishing equivalence for $j+1$ assuming equivalence for $j$ (or to find some $x$ for which the probabilities of two distributions differ). As the paper shows, such steps can be achieved by keeping track of bases for solutions of certain types of equations.

Ising models are a fundamental family of probability distributions over $\{\pm 1\}^n$. Probability of each $x$ in $\{\pm 1\}^n$ is proportional to $\exp(P(x))$ where $P$ is a degree-2 multilinear polynomial. Ising models are a very well-studied family of distributions modeling systems for which random features have only pairwise interactions (this is because each term in $P$ has at most two variables).

A Fully Polynomial-time Randomized Approximation scheme FPRAS is a randomized algorithm that gives a multiplicative $(1+\epsilon)$-approximation to a desired quantity. Here, this means that one is given a pair of degree-2 polynomials $P_1$ and $P_2$ describing a pair of Ising models, and the goal of the algorithm is to output a multiplicative $(1+\epsilon)$-approximation to the TV distance between the pair of Ising models. The paper shows that no poly-time algorithm can achieve this task (under a basic complexity-theoretic assumption).

The hardness proof proceeds by developing an approximation-preserving reduction to the problem of approximating the partition function of an Ising model, which is known from previous work to be hard to approximate. As an intermediate step, the reduction goes through the problem of approximating the marginal of an Ising-model distribution on one of the coordinates $x_i$ (this is referred to as the problem of approximating the atomic marginal).

The paper discusses computational aspects of the total variation (TV) distance between probability distributions and has two contributions:

It provides a deterministic polynomial-time algorithm for testing whether two mixtures of product distributions are equivalent, which means the algorithm can decide whether the TV distance between them is zero.

It demonstrates that, unless NP is contained in RP, there cannot exist an efficient algorithm to estimate the TV distance between arbitrary Ising models. This result points out the computational hardness of this problem.

This paper addresses the problem of computing the total variation distance (TV-distance) between high-dimensional distributions from a computational standpoint. For distributions with compact descriptions, calculating TV-distance poses significant challenges, as the direct approach incurs exponential time complexity relative to input size. The authors present two main contributions:

(1) They provide a polynomial-time algorithm for determining whether two mixtures of product distributions are identical.

(2) They establish the computational hardness of approximating the TV-distance between two arbitrary Ising models.

The first result is based on a simple and clever algorithm, the second result comes from the standard hardness result of approximating partition functions of Ising models.

Due to the limited time for reviewing, I went through all the proofs and understood the main ideas; however, I did not verify every detailed calculation.

Dear Reviewers,

The authors have provided their rebuttal to your questions/comments. It will be very helpful if you can take a look at their responses and provide any further comments/updated review, if you have not already done so.

Thanks!

The total variation distance between multivariate distributions is a basic function that appear often in statistics and information theory. Computing TV distance between even simple product distributions can be difficult to understand. This paper first gives an algorithm for testing, and then provides a conditional lower bound for Ising models.

Weakness: appeal to ICLR audience may be less

Reviewers are positive about the paper and gave high scores. I recommend acceptance.

Accept (Spotlight)