Computational Explorations of Total Variation Distance

Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, N. V. Vinodchandran · 2024

Read Computational Explorations of Total Variation Distance by Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, N. V. Vinodchandran (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-10370.txt.

Introduction

Arnab Bhattacharyya and co-authors probe what can be computed about total variation distance, in this 2024 paper. The distance measures how far apart two probability distributions sit. Many of its computational corners had never been mapped.

First, they give a fast exact test for when mixtures of product distributions are identical, the zero-distance case, over any alphabet. Second, they prove a hardness result: estimating the distance between general Ising models cannot be done efficiently unless a major complexity collapse occurs. Even randomized methods with bounded error fail. The pair of results sketches where easy problems end and hard ones begin.

Catalog record

CREATORArnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, N. V. Vinodchandran
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-10370

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Computational Explorations of Total Variation Distance Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, N. V. Vinodchandran Abstract We investigate some previously unexplored (or underexplored) computational aspects of total variation (TV) distance. First, we give a simple deterministic polynomial-time algorithm for checking equivalence between mixtures of product distributions, over arbitrary alphabets. This corresponds to a special case, whereby the TV distance between the two distributions is zero. Second, we prove that unless 𝖭𝖯 ⊆ 𝖱𝖯 \mathsf{NP}\subseteq\mathsf{RP} , it is impossible to efficiently estimate the TV distance between arbitrary Ising models, even in a bounded-error randomized setting. 1 Introduction The total variation (TV) distance between distributions P and Q over a common sample space D , denoted by d_{\mathrm{TV}}(P,Q) , is defined as d_{\mathrm{TV}}(P,Q):=\max_{S\subseteq D}\!\left(P(S)-Q(S)\right)=\frac{1}{2}\sum_{x\in D}|P(x)-Q(x)|=\sum_{x\in D}\max\!\left(0,P(x)-Q(x)\right). The TV distance satisfies many basic properties, making it a versatile and fundamental measure for quantifying the dissimilarity between probability distributions. First, it has an explicit probabilistic interpretation: The TV distance between two distributions is the maximum gap between the probabilities assigned to a single event by the two distributions. Second, it satisfies many mathematically desirable properties: It is bounded and lies in [0,1] , it is a metric, and it is invariant with respect to bijections. Third, it satisfies some interesting composability property. Given f(g_{1},g_{2},\dots,g_{n}) , suppose that we replace g_{2} with g^{\prime}_{2} such that d_{\mathrm{TV}}(g_{2},g^{\prime}_{2})\leq\varepsilon . Then the TV distance between f(g_{1},g_{2},\dots,g_{n}) and f(g_{1},g^{\prime}_{2},\dots,g_{n}) is at most \varepsilon . Because of these reasons, the total variation distance is a central distance measure employed in a wide range of areas including probability and statistics [ MU05 ] , machine learning [ SB14 ] , and information theory [ CT06 ] , cryptography [ Sti95 ] , data privacy [ Dwo06 ] , and pseudorandomness [ Vad12 ] . Lately, the computational aspects of TV distance have attracted a lot of attention. [ SV03 ] established, in a seminal work, that additively approximating the TV distance between two distributions that are samplable by Boolean circuits is hard for \mathsf{SZK} (Statistical Zero Knowledge). The complexity class \mathsf{SZK} is fundamental to cryptography and is believed to be computationally hard. Subsequent works captured variations of this theme [ GSV99 , Mal15 , DGPV20 ] : For example, [ GSV99 ] showed that the problem of deciding whether a distribution samplable by a Boolean circuit is close or far from the uniform distribution is complete for \mathsf{NISZK} (Non-Interactive Statistical Zero Knowledge). Moreover, [ CMR07 , LP02 , Kie18 ] showed that it is undecidable to check whether the TV distance between two hidden Markov models is greater than a threshold or not, and that it is \#\mathsf{P} -hard to additively approximate it. Finally, [ BGM+23 ] showed that (a) exactly computing the TV distance between product distributions is \#\mathsf{P} -complete, and (b) multiplicatively approximating the TV distance between Bayes nets is \mathsf{NP} -hard. On an algorithmic note, [ BGMV20 ] designed efficient algorithms to additively approximate the TV distance between distributions efficiently samplable and efficiently computable (including the case of ferromagnetic Ising models). In particular, they designed efficient algorithms for additively approximating the TV distance of structured high dimensional distributions such as Bayesian networks, Ising models, and multivariate Gaussians. In a similar vein, [ PM21 ] studied a related property testing variant of TV distance for distributions encoded by circuits. Multiplicative approximation of TV distance has received less attention compared to additive approximation. Recently, [ BGM+23 ] gave an FPTAS for estimating the TV distance between an arbitrary product distribution and a product distribution with a bounded number of distinct marginals. [ FGJW23 ] designed an FPRAS for multiplicatively approximating the TV distance between two arbitrary product distributions and [ FLL24 ] gave an FPTAS for the same task. Finally, [ BGM+24 ] gave an FPRAS for estimating the TV distance between Bayes nets of small treewidth. In this paper we address some previously unexplored (or underexplored) computational aspects of total variation distance relating to mixtures of product distributions and Ising models. 1.1 Equivalence Checking for Mixtures of Product Distributions Mixtures of product distributions constitute a natural and important class of distributions that have been studied in the mathematics and computer science literature. For instance, it is a standard observation that any distribution can be described by some (possibly large) mixture of product distributions (see 4 ). [ FM99 ] gave an efficient algorithm for learning a mixture of two product distributions over the Boolean domain. As part of their analysis, they showed that given two mixtures of two product distributions, their KL divergence can be upper bounded by that of the components and a certain distance between the mixture coefficients. However, this upper bound does not lead to an equivalence checking algorithm. A related problem in machine learning is source identification, whereby one is asked to identify the source parameters of a distribution. [ GMRS21 , GS22 , GJM+23 ] give algorithms for source identification of a mixture of k product distributions on n bits, when given as input approximate values of multilinear moments. We focus on the equivalence checking problem regarding mixtures of product distributions. Note that while it is easy to check whether two product distributions are equivalent, that is, by checking whether their respective Bernoulli parameters are equal, it is not clear how to do so for the case of mixtures of product distributions. This is so, because there are mixtures of product distributions that are equal (as distributions) but different sets of Bernoulli parameters describe them. For example, consider the case where we have two mixtures over one bit, namely P=1\cdot P_{1}+0\cdot P_{2} and Q=\frac{1}{2}\cdot Q_{1}+\frac{1}{2}\cdot Q_{2} , where P_{1}=P_{2}=\mathrm{Bern}(\frac{1}{2}) while Q_{1}=\mathrm{Bern}(\frac{1}{3}) and Q_{2}=\mathrm{Bern}(\frac{2}{3}) . In this case, P=Q=\mathrm{Bern}(\frac{1}{2}) , but the parameters of P and Q are different. We present a simple deterministic polynomial-time algorithm for checking equivalence between mixtures of product distributions. Let us first formally define mixtures of product distributions. Let w_{1},\dots,w_{k} be real numbers (weights) such that 0\leq w_{i}\leq 1 for all 1\leq i\leq k , \sum_{i=1}^{k}w_{i}=1 , and P_{1},\dots,P_{k} are n -dimensional product distributions over an alphabet \Sigma . The distribution P specified by the tuple (w_{1},\dots,w_{k},P_{1},\dots,P_{k}) is a mixture of products if for all x\in\Sigma^{n} it is the case that P\!\left(x\right)=\sum_{i=1}^{k}w_{i}P_{i}\!\left(x\right) . For a distribution P , we denote by P^{\leq i} its marginal on the first i variables. We may now state our first main result. Theorem 1 . There is a deterministic algorithm E such that, given two mixtures of product distributions P and Q , specified by (w_{1},\dots,w_{k},P_{1},\dots,P_{k}) and (v_{1},\dots,v_{k},Q_{1},\dots,Q_{k}) , respectively, decides whether P=Q or not. Moreover, if P\neq Q , then E outputs some x\in\Sigma^{i} (with i\leq n ) such that P^{\leq i}\!\left(x\right)\neq Q^{\leq i}\!\left(x\right) . The running time of E is O(nk^{4}|\Sigma|^{4}) . (Note that the algorithm outlined in Theorem 1 has input size \Omega\!\left(kn\left|\Sigma\right|\right) .) The primary conceptual contribution of our work is a connection between equivalence checking for mixtures of distributions and basis construction over appropriately chosen vector space. The connection lends itself to a construction that makes both the algorithm and the proof accessible to undergraduates. 1.2 Hardness of Approximating Total Variation Distance Between Ising Models The Ising model [ Isi25 , Len20 ] ,

Read the complete text