Estimating Statistical Similarity Between Product Distributions

This paper is about estimating statistical similarity between product distributions P and Q, which is defined by one minus total variation distance between P and Q, i.e. d_TV(P,Q). Estimating the exactly total variation distance between product distributions is #P hard, and hence estimating the statistical similarity is also #P hard. On the approximation side, there is an FPTAS for estimation the TV distance, however that would not give an approximation for the statistical similarity, as a multiplicative approximation for a function f does not give a multiplicative approximation for 1-f, and there are examples that such approx does not exist for 1-f.

This paper provides an FPTAS for estimating statistical similarity between product distributions. They use two reductions, the first reduce the problem to #MinPMFAtleast problem, which given C, asks for the number of inputs x such that min(P(x),Q(x)) >= C. Then they reduce this problem to a variant of the Knapsack problem that they introduce, called multidimensional #MaskedKnapsack. Finally they give an FPTAS for this variant of Knapsack.

The authors study the computation of the total variation similarity, s_TV (P,Q) = 1-d_TV(P,Q), between product distributions. The problem is #P-hard following the analogous result about the computation of the total variation distance d_TV(P,Q). For the latter an FPTAS is known to exists, which does not directly carry over to the computation of s_TV. The paper shows an FPTAS for s_TV. This is done by reducing the problem in two steps to the computation of a variant of multiple Knapsack problems.

This paper studies the hardness of computing the statistical similarity and shows that there exists an FPTAS for approximating the statistical similarity between product distributions. For two distributions $P$ and $Q$, the statistical similarity between $P$ and $Q$ is defined as $s_{TV}(P, Q) = 1-d_{TV}(P, Q)$, where $d_{TV}(.,.)$ is the total variation distance. In this work,

1- The authors first reduced approximating $s_{TV}$ to the #MinPMFAtLeast problem in which, given two product distributions $P$ and $Q$ over $\{0,1\}^n$ and $C\ge 0$, computes the number of $x\in\{0,1\}^n$ such that $\min\{P(x), Q(x)\}\ge C$. 2- Then, they reduced #MinPMFAtLeast to the 2-dimensional #MaskedKnapsack problem in which, given two instances $K_1$ and $K_2$ specified by weights $a_{i,1}, \ldots, a_{i,n}$, capacity $b_i$, and mask vectors $u_i=(u_{i,1}, \ldots, u_{i,n})$ for i\in{1,2\}, counts the number of solutions $x=(x_1, \ldots, x_n)$ such that $\sum_{j=1}^n a_{i,j}(x_j\oplus u_{i,j}) \le b_i for$i=1,2$. 3- Next, they show that there exists an FPTAS for$O(1)$-dimensional #MaskedKnapsack problem. 4- Finally, they approximately solved #MaskedKnapsack using techniques from [Gopalan et al (2010)].

The work addresses the computational problem of estimating the statistical similarity ($s_{TV}$) between two product distributions. Computing the exact $s_{TV}$ is #P-hard. The authors aim to develop an FPTAS for estimating $s_{TV}$ between arbitrary product distributions. To achieve this goal, they introduce a new variant of the knapsack problem called the multidimensional #MASKEDKNAPSACK and estimate the number of solutions to this problem. Their result is obtained by a chain of reductions: from the $s_{TV}$ estimation problem to the #MINPMFATLEAST problem, and then to the multidimensional #MASKEDKNAPSACK problem, which is supported by rigorous mathematical proofs.

This paper considers the problem of estimating the statistical similarity between distributions that are product of n Bernoulli trials. Statistical similarity is simply 1-(total variation distance). This paper proposes a fully polynomial time approximation algorithm for the problem. It is noteworthy that there are additive and relative approximations for the total variation distance that run in polynomial time. I believe that an additive approximation of TV distance translates to an additive approximation of statistical similarity. However, this is not the case for relative approximations of TV distance and statistical similarity and there is no straightforward relationship between them. Thus, although closely related, relative approximations of TV distance cannot be directly used for solving relative approximation of statistical similarty.

The main approach of the paper is to reduce the problem of estimating statistical similarity to a variant of the knapsack problem (masked version) and then designing a relative approximation for this variant.

While the reviewers all felt that this work had merit, the ultimate consensus is that the novelty and relevance to ICLR are limited in comparison to other submissions this year. The paper could be strengthened by better motivating the need for a multiplicative approximation to statistical similarity, especially given the existence of additive approximation methods, and multiplicative approximations to distance (a seemingly better motivated problem). An experimental evaluation (ideally demonstrating an application) would strengthen the paper as well. That said, we enjoyed reading this paper, and wish the authors the best of luck in resubmitting to another venue.

Reject