Entropy Equivalence Testing
Abstract
We introduce the problem of entropy equivalence testing for probability distributions, a relaxation of the well-studied closeness testing problem, where the distribution testing algorithm is now only required to distinguish, given samples from two unknown distributions and a parameter , between and (where denotes the Shannon entropy). We provide a time- and sample-efficient algorithm for this task, showing that the optimal sample complexity for this task can be significantly lower than that of closeness testing. As an application, we leverage this result to provide the first non-trivial testing algorithm for (standard) closeness of low-degree Bayesian networks, which significantly improves on either the sample or time complexity of a baseline based on full learning.
Keywords and phrases:
Entropy, distribution testing, sublinear algorithm, Bayesian networkCategory:
RANDOMFunding:
Jonathan Scarlett: Supported by the National University of Singapore under the Presidential Young Professorship scheme.Copyright and License:
2012 ACM Subject Classification:
Theory of computation Lower bounds and information complexity ; Mathematics of computing Probabilistic algorithmsAcknowledgements:
We would like to thank Sayantan Sen, Jan Seyfried and Marco Tomamichel for the discussion on their work of testing Conditional Mutual Information. JY would also like to thank Davin Choo for the early discussions predating this project. This work is conducted while JY was interning at National Institute of Informatics, hosted by Yuichi Yoshida.Editors:
Mohit Singh and Tom GurSeries and Publisher:
Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik
1 Introduction
Distribution testing, a subfield of property testing [35, 30] concerned with efficient algorithms for deciding statistical properties of data, has witnessed a significant interest since its systematic introduction by Batu, Fortnow, Rubinfeld, Smith, and White [5], with a flurry of works over the past two decades addressing a range of hypothesis testing tasks, under various models of distribution testing (see, e.g., [34, 10, 11] and [29, Chapter 11] for surveys and expositions).
Two of the flagship and most fundamental tasks in distribution testing are identity testing (and its special case, uniformity testing), and closeness testing (also known as equivalence testing): in the first, an algorithm is given independent samples from an (unknown) discrete probability distribution, and must decide whether the distribution is equal to some known reference distribution, or significantly deviates from it in a meaningful notion of distance (typically total variation distance). In the second, the algorithm has access to samples from two unknown distributions, and similarly must decide whether they are equal, or significantly far from each other. Here, “significantly far” is quantified by an input parameter , and the algorithm is required to be correct with high probability ,111One typically sets to be a small constant, e.g., : this is without much loss of generality, as one can amplify this by repetition to any target , at the cost of an factor in sample and time complexity. while minimizing the sample complexity, that is, the total number of samples taken from the distribution(s) in the worst case as a function of the domain size , distance parameter , and error probability .
The sample complexity of these two flagship tasks is by now well understood, with several time-efficient algorithms known to achieve the optimal sample complexity, as a function of all parameters: namely,
for identity testing [32, 1, 28, 27], and
for closeness testing [5, 17, 28, 26]. However, in spite of these impressive advances, these sample complexities can remain prohibitively large for many combinations of , notably for small corresponding to distributions that may be very close to one another. Given that their sample complexities are constant-factor optimal, there would seem to be little room for improvement, yet two possible avenues remain. The first is to relax the guarantees: total variation is known to be a very stringent measure of distance, and testing with respect to a more permissive distance measure may enable significant sample complexity savings, while still being “good enough” for the application at hand. This direction was partially explored in, for instance, [24]. The second avenue, particularly well suited to high-dimensional data, is to make additional structural assumptions on the distribution: high-dimensional data is seldom fully unstructured, and one can usually leverage domain knowledge to make modelling assumptions, for instance that the probability distributions exhibit a low-degree Bayesian network structure, or are consistent with an Ising model. This line of work, in the context of distribution testing, was initiated in [12, 23].
Our work makes progress on both of these fronts. We first define a relaxation of closeness testing, which we term entropy equivalence testing, where one is asked to detect if the two unknown distributions have significantly different (Shannon) entropy:222Recall that the (Shannon) entropy of a probability distribution over a discrete domain is defined as .
Entropy Equivalence Testing (): Given sample access to distributions over a known domain of size and parameters and , distinguish, with probability at least , between the following two cases: (1) , and (2) .
We note that the “single-distribution” version of this task, when is fully known to the algorithm, was recently introduced [15], under the name Entropy Identity Testing (). [15] then leveraged their algorithm for to obtain an improved identity testing algorithm for “standard” identity testing (i.e., in total variation distance) of bounded-in-degree Bayes nets, establishing a connection between the two aforementioned avenues of research. We build upon and deepen this connection to obtain, from our algorithm for , the first non-trivial closeness testing algorithm for Bayes nets.
1.1 Our results
We now describe our results in more detail. Our first contribution is an efficient algorithm for the task defined above (where we implicitly set the probability of failure to be a small constant):
Theorem 1.
There exists an algorithm for the Entropy Equivalence Testing problem with sample complexity
and running time near-linear in the number of samples.
Combining Theorem 1 and the “baseline tester” discussed below (see Section 1.2) which follows from a reduction from entropy difference to total variation distance and has sample complexity , one gets, after simplifying the resulting sample complexity, our main result:
Corollary 2 (Main testing result).
There exists an algorithm for the Entropy Equivalence Testing problem with sample complexity
and running time near-linear in the number of samples.
We complement this positive result with an information-theoretic lower bound, showing that our algorithm has nearly optimal sample complexity:
Theorem 3 (Lower bound).
Any algorithm for the Entropy Equivalence Testing problem must draw
total samples from and .
Finally, we show how to leverage our algorithm for to obtain a closeness testing algorithm for bounded in-degree Bayes nets: we emphasize that, to the best of our knowledge, this is the first testing algorithm for this problem, besides the “naïve” (and computationally inefficient) testing-by-learning approach that fully learns the two unknown distributions with samples, in time :
Theorem 4.
There exists an algorithm for closeness testing (in total variation distance) of in-degree Bayesian networks with sample complexity
and running time .
Interestingly, the techniques underlying Theorem 4 can also be easily adapted to obtain an algorithm for identity testing of Bayes nets, improving upon the work of [15]: see Corollary 18.
1.2 Technical overview
We now provide an overview of the techniques and main ideas underlying our results.
1.2.1 Upper bound for EET
A bound of readily follows from a standard inequality, allowing one to reduce the entropy difference problem to closeness testing in TV: namely, when , then [21, Lemma 2.7]. Another straightforward upper bound is obtained by estimating the entropy, a harder task, which takes samples [42]. This hints at the possibility of getting a better bound of for some absolute constant . Surprisingly, the final upper bound of is related to the squared Hellinger distance (and not the total variation). This is a result of considering two testers that can solve independently, and choosing the one with lower sample complexity. The main contribution of our work is providing an alternative tester to the TV reduction tester above.
An tester.
Our analysis starts with a reduction to testing both farness (vs. equality) in Hellinger distance and a cross-entropy difference term (with respect to the uniform mixture) via some algebraic manipulations (see Lemma 9). The problem thus becomes testing whether Hellinger distance is large (which we know costs ) and testing whether the cross-entropy term is large (since one of them will be large if the entropy difference is large). A natural idea is of course to employ a plug-in estimator for the cross entropy difference (see (1)). Unfortunately, this empirical estimator has an inherent333In the works of [42], their plug-in estimator also exhibits similar bias in the analysis, and they resort to machinery from polynomial approximation to reduce the bias (which will increase the variance the higher the degree of the polynomial). bias of the form , where is the (equal) number of samples we take from and to compute the estimate. Our argument to deal with the bias is as follows: If the expectation of the plug-in estimator has low bias (at most ), then we can rely on its estimate alone. On the other hand, if it has high bias (at least ), we hope to catch it and reject (i.e., declare that ) early.
Low mass regime: Reduction to TV.
One main challenge to designing this test is that the bias is impossible to test without a lower bound on (the variance of estimating the bias could be huge). The key to passing this hurdle is an idea inspired by a different algorithm from [28], whose analysis implies that for the elements where (or ) is small, we can perform tests more efficiently (in TV) via access to its conditional distribution (as efficiently as ), with the intuition being: The TV distance between the conditional distributions is actually larger (inverse of its mass size , where is the set of small-mass elements). Via a reduction to TV from cross-entropy difference, we can also test farness on these elements with samples.
Detecting bias in the high mass regime.
Capitalizing on this, we will consider exclusively elements with large mass: . With a bound on (since we take ), this reduces to testing farness in TV distance, which can be performed with samples (to bound the bias term by ), rather than the for some that we set out for. Luckily our problem can be easier (depending on relation between ) than testing in TV (see Lemma 13). Intuitively, this is related to testing in the instance-optimal setting [40, 28] – one can test with sample complexity as a function of (for our case has exclusively large probability masses), rather than as a function of the domain size (the worst case over all possible ). Interestingly, to detect the bias, we are using the same test statistic (with different threshold) first used in [17] to test in TV distance and subsequently in [24] to test in Hellinger distance.
Had we not made a “reject” decision after the bias check in the high mass regime (nor rejected due to its low mass cross-entropy difference), it would suggest that the bias on the high mass regime is at most and therefore, the estimator for is reliable: A standard analysis of expectation and variance followed by an application of Chebyshev’s inequality then yields Theorem 1.
1.2.2 Lower bound for EET
The lower bound is a combination of and . The former is derived via a reduction from testing mutual information to entropy difference. The task of testing mutual information () is as follows: if , then accept with probability ; If , then reject with probability . Given the close relation between mutual information and entropy: , one can reduce the problem of testing to by treating as the joint distribution of and as the product of and (we can simulate sample access to the product of and with two samples from the joint distribution). Therefore, the existing lower bound from [37, Corollary 6.2] holds for our problem. The latter lower bound of comes from [15, Lemma 2.7], given the reduction from identity testing to equivalence testing.
1.2.3 Application to equivalence testing of Bayes nets
As laid out by [15], one can utilize testing entropy difference as a subroutine to testing Bayes nets. The key of the analysis is derived via the celebrated Chow-Liu decomposition [20]: If two Bayes nets and have similar local entropies, then they must share approximately similar structures (their corresponding DAGs are close in some sense; see [15, Lemma 3.4]). Once we confirm that they share a similar structure, the problem boils down to checking local (every subset of random variables of size at most ) KL-divergences. While KL-divergences are known to be untestable [24, Theorem 7] in the extreme cases when , there is hope if one can obtain a lower bound on . In fact, we can reduce testing in KL to testing in Hellinger distance with an factor overhead using [37, Lemma 3.1]. To get a lower bound on , we use a standard technique of testing the mixture of and the uniform distribution.
1.3 Related works
Estimating entropy.
Entropy estimation is a well-studied problem in both the information theory [41, 42, 31] and property testing [39, 3] communities, with the near-optimal sample complexity being eventually established by [42, 31] (for discrete distributions). As we are considering the testing problem, our upper bound is less costly compared to its learning (estimation) variant. Moreover, other variants of entropy have been studied, such as Rényi entropy [2]. The more general problem of estimating functionals of distributions was also considered by [31].
Identity testing and closeness testing.
The standard formulation of identity testing asks the following problem: Given a full description of a hypothesis , how many i.i.d. samples are needed from to distinguish between and , where and are both distributions over support of size ? This problem is well-known to have a sample complexity of , a much lower cost compared to fully learning every parameter of , which takes samples. A similar problem can be asked if one is instead only provided sample access to and , both unknown. This is the closeness testing problem (in TV) and it is known that a sample complexity is necessary and sufficient, making this a slightly harder problem than identity testing while still saving on samples compared to fully learning and . Our problem differs from the standard formulation by testing in the entropy difference rather than in TV distance. Most relevant to our work is the work of [15], which solves the problem of entropy identity testing (up to polylogarithmic factors) with a sample complexity of . Another relevant work is that of [24], which asks the question of testing in different distances, e.g., distinguishing between and for identity testing (sample access to and the full description of ). Interestingly, as shown in the same work, equivalence testing in squared Hellinger distance, i.e., distinguishing between and has a similar cost of (though perhaps not so surprising, as we are reducing to testing in squared Hellinger square in one of the cases we handle). Our work adds to their results for equivalence testing in entropy difference.
Testing mutual information.
Testing mutual information () asks the following question: Given sample access to a (discrete) distribution over two random variables with a domain of size and respectively, how many samples do we need from to distinguish between and ? The study of this problem was initiated by [9] to solve the problem of learning a special variant of Bayes net (trees). While their tester is sufficient for learning trees-structured distributions near-optimally, their upper bound is loose in terms of dependence on and : . More recently, [37] gave a near-optimal bound of (assuming ). We note that this bound bears similarity (e.g., setting ) to ours due to the close relation between and entropy: . Indeed, testing can be reduced to naturally (as outlined above). Before these works, [4, 13] studied the problem of (conditional) independence testing in the TV distance.
Testing Bayesian networks.
A Bayesian network (Bayes net) is a high-dimensional distribution over random variables that factorizes into conditional probabilities: , where is called the parent set of . This factorization is associated with a directed acyclic graph (DAG) (), and if , then the edge (with being one of ’s parents). A distribution is called a Bayes net if its joint probability density function factorizes according to and is called Markov with respect to . Learning Bayesian networks from samples is a fundamental problem in learning theory, and there is a plethora of evidence that this problem is hard computationally [18, 22, 7]. On the other hand, time-efficient algorithms (polynomial in , the number of random variables) do exist in some special cases [19, 8, 9].
Identity testing and closeness testing of Bayes nets were systematically studied by [12], though their stronger upper bounds only consider relaxed version of Bayes nets where both and are required be balanced and non-degenerate. While they also provide a more general upper bound (without assuming balancedness and non-degeneracy for Bayes nets), they still require that the node ordering be the same between and , a non-trivial assumption. Our upper bound does not make any assumption other than the bounded in-degree , which is a natural and necessary parameter to consider, since testing unbounded degree Bayes nets is exponentially hard: (e.g., see [6, Theorem B.1]). The strongest upper bound that we are aware of is by [25], which can solve the identity testing444Note that their setting of identity testing actually corresponds to equivalence testing in our setting. problem in samples,555Implicitly, using the Hellinger testing result of [24, Theorem 1]. under the assumption that and have the same structure (Markov with respect to the same DAG). For equivalence testing, under the same assumption, they give a bound of .666Implicitly, using the optimal Hellinger equivalence test [24]. Our results match their bounds if , and our algorithm will work without the extra assumption that and share the same structure. A lower bound of when [6, Theorem 4.1] holds for identity testing of Bayes nets and thus also for its closeness testing variant (our setting).
1.4 Preliminaries
Define the factorial moment by , which gives an unbiased estimator for the monomials of the Poisson mean: namely, if , then for all . More generally, we have the following fact, whose proof we provide in Appendix A for completeness:
Fact 5.
Let be a Poisson random variable with parameter , and be any function, then, we have that . In particular, choosing , we have that for all .
Fact 6 (Folklore).
For any and , testing whether the bias of a coin is at most or at least , with probability at least , can be done with samples.
Distances and norms.
We will use a number of standard distance measures for two distributions over , and various known inequalities between them, e.g., see [36]. The squared Hellinger distance is
The total variation distance is . The distance is , and the -divergence of from is . These satisfy the chain of inequalities
and the equivalence . The Kullback–Leibler (KL) divergence is , which satisfies and Pinsker’s inequality .
Notation.
In what follows, for a given integer , we denote by the set , and by the uniform distribution on . When clear from context, we will omit the subscript, and write instead of . Given a probability distribution over and a set such that we write for the conditional distribution of on . For the high dimensional (Bayes net) section, we use to denote the marginalization of over , where is a subset of , e.g., denotes the marginal distribution of . We also use to denote the parent set of the random variable in a Bayes net.
Throughout the paper, we use for the natural logarithm, and adopt the standard asymptotic notation , as well as the closely related , which hide polylogarithmic factors in their argument.
2 An Upper Bound for EET
In this section, we establish our main theorem, Theorem 1. We begin with a simple algorithmic “trick” that allows us to reduce the task to one where both put at least some minimum probability on every element of the domain:
Lemma 7.
Let be distributions over , and set . Let and likewise for . Then for every , and
Moreover, one sample from (resp. ) can be simulated from one sample from (resp. ).
Proof.
Since , by invoking the bound on entropy difference with respect to TV distance in [21, Lemma 2.7], we get
Similarly, we have . By the triangle inequality, we then have
and
establishing the lemma. Of course, if , then ; Lemma 7 guarantees that if , then . That is, satisfy the promise with the same (up to constants) whenever do, so we can henceforth assume that . With this in hand, we are ready to establish our main theorem, restated, as follows:
Theorem 8 (Theorem 1, restated).
There exists an algorithm (Algorithm 1) which, given sample access to two unknown probability distributions over a known domain , as well as parameter , takes
samples from both and , and has the following guarantees:
-
If , then the algorithm outputs accept with probability at least ;
-
If , then the algorithm outputs reject with probability at least .
Further, the algorithm runs in time , where is the total number of samples.
The remainder of this section is dedicated to proving this theorem, which we do via a series of lemmas.
The first lemma relates a difference in entropy to a difference in (squared) Hellinger distance and a cross entropy term with respect to a mixture:
Lemma 9.
For any two distributions over , we have
Proof.
Letting , we can write
We then observe that
where the last equality comes from the equivalence of between Hellinger distance and Triangle distance (e.g., see [24, Proposition 3]).777Note that the induced KL terms have been studied in information theory (called Jensen-Shannon divergence; see e.g., [33, Chapter 7] and more systematically in [38], where they actually show that the Jensen-Shannon divergence and the Triangle distance are equivalent up to constant factors). Similarly, we have that , and we conclude that
as claimed. Lemma 9 allows us to split the entropy difference into a Hellinger part and a term , so that an entropy difference implies at least one of these two terms must be : thus, it suffices to test both, and reject if, and only if, at least one of them is detected to be . (Clearly, if , both the Hellinger and KL-like terms are zero.)
The Hellinger term can be tested with samples using a Hellinger closeness tester (e.g., [28, Proposition 2.15]): if , this tester will allow us to reject with high probability. For the rest of the subsection we therefore can assume , and the task reduces to testing the second, “KL-like” term,
| (1) |
and specifically to distinguish from .
To do so, the idea is to handle separately the set of “heavy” elements, on which either or puts relatively high probability (specifically, at least some threshold ), and the remaining set of “light” elements (which have low probability under both and ). Of course, we do not know this set , as both are unknown; however, by taking samples (which is inconsequential, as we will pay this sample complexity for the Hellinger test anyway), we can obtain a set which is a good proxy for . To make this formal, define the following two sets:
where are two absolute constants. Our focus is to identify a set such that .
Lemma 10.
Using samples from and , one can efficiently return a set satisfying with probability at least .
Proof.
By Fact 6, choosing , as we have sample access to the uniform mixture , we can distinguish and with probability costing samples from and . Therefore, running the test over the support (using the same set of samples to run this test for all ’s) and adding each to the set if we detect , by a union bound, the algorithm will be simultaneously correct on all with probability at least . To summarize, once we have identified such a set , given that
it suffices to separately test (1) vs. , and (2) vs. ; we do so below, assuming that our set satisfies .888For simplicity of exposition, we henceforth ignore the factor , and consider instead of ; a simple rescaling argument gives the original guarantees.
Test 1: vs.
Inspired by the ideas of [28], we can then check if the distributions are far in TV distance in the low-probability regime (i.e., elements in ), which will suffice by a simple reduction from entropy difference to TV (using the lower bound ). In more detail, we have
While this is a task that would in general require a large number of samples, here we can leverage the additional fact that does not contain any heavy elements.
Lemma 11.
Let be a set such that . Then, testing versus (with probability of success ) can be done with samples from .
Proof.
By [28], we know that samples suffice to distinguish from with high constant probability. For the sake of completeness, we briefly explain how to adapt their argument to our setting. First, it takes samples to check whether the mass of on is larger than , and similarly for : if both have mass smaller that this, we accept, as . If only one of the two puts large enough mass on , we reject, as this shows that . Otherwise, both put enough mass on , and we continue.
With samples, we then confirm that their probability masses on approximately match, i.e., that . If they do not, we can output reject. Otherwise, we have
Thus, if and (for suitable choice of constants in the , ), then we have that
Recalling that and , we can sample from via rejection sampling at the cost of an expected , factor in the sample complexity. Thus, we can use an off-the-shelf TV equivalence tester (e.g., from [17, Theorem 1]) to test vs. at the cost of
samples from ; which, by the above discussion, requires an expected
samples from (which can be made high-probability via Markov’s inequality, paying a constant factor in the sample complexity and a small additional probability of failure). Since , we finally conclude that taking samples suffices.
Test 2: vs.
We now look at the second – and more involved – case, namely, detecting when the entropy difference is far in the high mass regime. That is, we are testing vs. .
We will define a suitable test statistic, , and analyze its expectation (with the goal of bounding its bias and relate it to ), before bounding its variance to conclude with an application of Chebyshev’s inequality. At a high level, our strategy is as follows: either the empirical entropy difference has low bias, which means we can simply rely on its output for the test, or it has high bias, in which case this can be detected by performing additional checks to detect this bias.
Let be the number of samples taken from , and assume the Poissonized setting: that is, instead of exactly samples, we take a random number of samples.999This standard technique is valid as it only affects the sample complexity by constant terms and an arbitrarily small error probability adjustment, since a Poisson random variable tightly concentrates around its mean. Its advantage is to provide additional independence between the empirical counts of each element, which is useful in the analysis. Recall that by construction of the set , we can assume for all . Focusing on , we run two further checks, each at cost :
-
1.
, which implies .
-
2.
, which is checked via testing at distance using an -closeness tester (e.g., via learning in distance, see for instance [16]).
If either check rejects, we reject; otherwise we proceed assuming both guarantees hold.
Letting (resp. ) be the number of occurrences of element among the samples from (resp. from ), we define our entropy difference estimator to be
and we write for the -th summand and let when . By the above Poissonization procedure, we have and for all , and the (resp. ) are independent. We first bound the bias of this estimator :
Lemma 12.
For any set ,
Proof.
Let with
. Conditional on , the count is
-distributed, so
.
By the law of total expectation, pulling the factor outside
the inner expectation,
We then apply the Poisson identity (Fact 5) , taking :
Subtracting the target ,
We proceed to bound from above and below. By Jensen’s inequality applied to the concave function ,
For the lower bound, the inequality applied to , together with for , gives
Combining these findings gives (using for all ), so
Summing over yields the claim.
The bias of our estimator is determined by the RHS of Lemma 12; note that if , the RHS simplifies to . As a result, a natural idea would be to use this RHS as a proxy, and to check if the RHS is noticeably large using another test: if it is larger than , we can immediately reject, as this is clear evidence that . We do so in the following lemma:
Lemma 13.
Suppose that . Then, with samples from , one can distinguish between the following two cases with high constant probability:
-
1.
(which implies ).
-
2.
.
Proof.
We use the test statistic
where and . We show:
-
In the first case, , while in the second case .
-
in both cases.
Chebyshev’s inequality then will enable us to separate the two cases by thresholding at a value scaling as .
Analyzing .
The first part is similar to the analysis from [17, Lemma 4], which relies on the same statistic (for a different purpose): write and . Conditional on , we have so , and . Hence,
and the binomial variance gives
Combining, . The -th summand of is , which we set to when (the case). For ,
Taking the outer expectation, with the indicator enforcing the convention,
where .
In particular, in the first case (when ), for every , and so . We therefore now focus on the second case, for which we depart from [17]. By the construction of (Lemma 10), for every , so choosing with a sufficiently large constant gives for all . The bound for then yields
By Cauchy–Schwarz,
Since (in view of and ), we have . Applying this termwise and using the definition of the second case,
Combining,
which is given the settings of and .
Upper bound on .
The variance bound from [17, Lemma 5] gives
Under the lemma’s assumption on the Hellinger distance, , so the second term is , and , where . This scaling of leads to the simplified bound .
Concluding via Chebyshev.
In the first case, and , so with probability . In the second case, and , so with probability . Thresholding at thus distinguishes the two cases.
Having used the RHS of Lemma 12 as a proxy for the bias, and checked that it is small (and rejected otherwise), we are not yet done: we could still have both small bias for (so that ) and large . However, now, since we know that , to conclude it suffices to run one last check: namely, that is small enough.
Indeed, we know now that has small bias: if we can also show, via a variance argument, that concentrates around its expectation, then we will have , and checking that is small will ensure (with high probability) that we can guarantee that is small. Thus, our last missing piece is an upper bound on , which will let us show that concentrates around its expectation.
Lemma 14.
The variance of the entropy difference estimator satisfies
Proof.
Under Poissonization, the counts and are mutually independent across coordinates. As a result, the ’s are also independent, and
Fix any , letting , and defining the event . Since , the Chernoff bound for Poisson random variables gives . Then:
-
On : for , and noting from before that when , we have . Squaring and taking expectations,
using and (moments of Poisson r.v.’s).
-
On : from and (valid since ), we get . Combining Cauchy–Schwarz with the moment bound (since Poisson moments are polynomials in the mean, by Fact 5) and the tail bound ,
To conclude this subcase.
We choose a threshold for at a suitable constant multiple of that distinguishes the two cases. If , then with probability at least the test on from Lemma 13 will not reject and , and so this overall test accepts. If and , then with probability at least either the test on from Lemma 13 rejects, or it does not and then , and this overall test rejects.
Wrapping up
Putting the above ingredients together:
-
If , then with high constant probability, (1) the Hellinger test on accepts, and (2) (a) the set is correctly identified, (b) the test on accepts, (c) (i) the test on (checking for low bias for ) accepts, and (ii) the test on (test on assuming low bias for ) accepts. Overall, the algorithm accepts with probability at least by a union bound.
-
If , then with high constant probability (1) either the Hellinger test on rejects; or it accepts because is small, in which case must be large; then, with high constant probability (2) (a) the set is correctly identified, (b) the test on rejects, or it accepts because is small, which means must be large: in which case (c) (i) the test on (checking for low bias for assuming is small) rejects, or it accepts because the bias is small, in which case (ii) the test on (test on assuming low bias for ) rejects. Overall, the algorithm rejects with probability at least by a union bound.
Overall, each subtest in Algorithm 1 uses no more than or samples, and hence the total sample complexity of our algorithm is
All our test statistics can be computed in time once all are collected.101010The statistics for testing Hellinger square is the same as (albeit with different threshold; see [24, Theorem 5]). can be computed in time once all , are known. Computing can be done in time and calculating the empirical of can be implemented in time. As for the conditional TV tester, the rejection sampling will cost as many samples as we take in total, and for TV closeness testing we use the same statistic (see, e.g., [24, Theorem 4]). For tester, the statistic is also computable in time [17, Section 3]. Assuming that we can compute in constant time, one can compute the statistic in time. To compute , one can first sort over all samples which takes time, where is the number of samples in one of the subtests, and then sum them up. Thus, the time complexity of our algorithm is , where is the total number of samples. This concludes the proof of Theorem 8.
3 Bayesian Network Equivalence Testing
In this section, we show how to leverage our Entropy Equivalence Testing () algorithm (Algorithm 2) to obtain an equivalence testing (closeness testing) algorithm for bounded-degree Bayesian networks (Bayes nets). Specifically, the problem we consider is the following:
Bayes-Net Equivalence Testing: Given sample access to distributions over , each Markov with respect to a DAG of in-degree at most (the DAG is unknown, and possibly distinct between and ), and parameters and , distinguish, with probability at least , between the following two cases: (1) , and (2) .
Definition 15.
A projection of a Bayes net on onto a DAG is denoted by , and is defined by its probability mass function (PMF) as follows:
where is the set of parents of in . Moreover, with a slight abuse of notation, we write or for the marginal distribution of on the subset
The baseline here is the testing-by-learning approach, whereby one learns the two unknown in-degree Bayes nets to TV distance and checks the distance between the two learned hypotheses. It is known that learning an in-degree Bayes net in total variation distance can be done in samples (see [12, Appendix A]): to the best of our knowledge, the time complexity of any learning algorithm achieving this bound is exponential, namely, . In contrast, we obtain a testing algorithm with drastically better running time (for all ), and significantly better sample complexity whenever .
Theorem 16 (Theorem 4, restated).
There exists an algorithm (Algorithm 2) that, given sample access to two Bayesian networks and over with in-degree at most , as well as a parameter , takes
samples from , and distinguishes with probability at least between (1) and (2) . Moreover, the algorithm runs in time .
Proof.
The pseudocode is provided in Algorithm 2. Due to space constraints, we defer the proof of correctness to the full version [14].
Remark 17.
We have an interesting dichotomy: our algorithm is efficient (polynomial in ) only if is constant. However, it is worse than its learning counterpart when is constant: (our test) vs. (learning). On the other hand, if , then our tester will be more efficient than learning sample-wise, but its runtime becomes , and is thus quasi-polynomial.
As identity testing is a special case of closeness testing, our above analysis can straightforwardly be ported to yield an identity testing algorithm (using an algorithm for identity testing in Hellinger instead of a closeness one as the first building block). An immediate consequence of this is to yield an improved identity tester for Bayes net with sample complexity , thus improving on the prior bound [15, Theorem 1.2].
Corollary 18.
Given sample access to a Bayesian networks and a full description of Bayesian network over with in-degree at most , as well as a parameter , there is an algorithm that takes
samples from , and distinguishes with probability at least between (1) and (2) . Moreover, the algorithm runs in time .
4 Lower Bound
In this section, we establish our sample complexity lower bound for (Theorem 3). The term follows from a reduction to mutual information () testing combined with [37, Corollary 6.2], and the term follows directly from [15, Lemma 2.7], whose two-point construction is also a hard instance for .
For a joint distribution over with marginals , the mutual information between coordinates is
and equals zero if and only if . The testing problem asks, given sample access to , to distinguish from with probability at least . [37, Corollary 6.2] established the lower bound
for this task.
Reduction from MI testing to EET
Lemma 19.
Let and . Any algorithm over with sample complexity yields an testing algorithm over with sample complexity and the same success probability.
Proof.
Map with via some fixed bijection. Using , we construct a tester for over as follows:
-
1.
Draw i.i.d. samples from .
-
2.
Form samples of , denoted by for .
-
3.
Form samples of , denoted by for . Since the samples are i.i.d., the - and -coordinates of each pair are independent draws from and respectively.
-
4.
Run on the samples of and the samples of .
Observe that . Then:
-
If , then , so and returns accept.
-
If , then and returns reject.
Theorem 20 ( lower bound: Theorem 3, restated).
Any algorithm that, given sample access to two unknown distributions over and parameter , distinguishes from with probability at least requires
samples from each of and .
Proof.
Apply Lemma 19 with and . Combining with [37, Corollary 6.2] gives the first term:
For the second term, [15, Lemma 2.7] exhibits distributions over with that no algorithm can distinguish from using fewer than samples from when is given. Any algorithm using samples from each of yields such a tester by simulating samples from the known , so also requires samples.
References
- [1] Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath. Optimal testing for properties of distributions. In NeurIPS, pages 3591–3599, 2015. URL: https://proceedings.neurips.cc/paper/2015/hash/1f36c15d6a3d18d52e8d493bc8187cb9-Abstract.html.
- [2] Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, and Himanshu Tyagi. The complexity of estimating rényi entropy. In SODA, pages 1855–1869. SIAM, 2015. doi:10.1137/1.9781611973730.124.
- [3] Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, and Ronitt Rubinfeld. The complexity of approximating the entropy. SIAM J. Comput., 35(1):132–150, 2005. doi:10.1137/S0097539702403645.
- [4] Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, and Patrick White. Testing random variables for independence and identity. In FOCS, pages 442–451. IEEE Computer Society, 2001. doi:10.1109/SFCS.2001.959920.
- [5] Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White. Testing that distributions are close. In FOCS, pages 259–269. IEEE Computer Society, 2000. doi:10.1109/SFCS.2000.892113.
- [6] Arnab Bhattacharyya, Clément L. Canonne, and Joy Qiping Yang. Independence testing for bounded degree bayesian networks. In NeurIPS, 2022.
- [7] Arnab Bhattacharyya, Davin Choo, Sutanu Gayen, and Dimitrios Myrisiotis. Learnability of parameter-bounded bayes nets. In AAAI, pages 15559–15566. AAAI Press, 2025. doi:10.1609/AAAI.V39I15.33708.
- [8] Arnab Bhattacharyya, Sutanu Gayen, Philips George John, Sayantan Sen, and N. V. Vinodchandran. Distribution learning meets graph structure sampling. In Advances in Neural Information Processing Systems, volume 38, pages 21411–21432, 2025.
- [9] Arnab Bhattacharyya, Sutanu Gayen, Eric Price, Vincent Y. F. Tan, and N. V. Vinodchandran. Near-optimal learning of tree-structured distributions by chow and liu. SIAM J. Comput., 52(3):761–793, 2023. doi:10.1137/22M1489678.
- [10] Clément L. Canonne. A Survey on Distribution Testing: Your Data is Big. But is it Blue? Number 9 in Graduate Surveys. Theory of Computing Library, 2020. doi:10.4086/toc.gs.2020.009.
- [11] Clément L. Canonne. Topics and techniques in distribution testing: A biased but representative sample. Found. Trends Commun. Inf. Theory, 19(6):1032–1198, 2022. doi:10.1561/0100000114.
- [12] Clément L Canonne, Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Testing Bayesian networks. In Conference on Learning Theory, pages 370–448. PMLR, 2017. URL: http://proceedings.mlr.press/v65/canonne17a.html.
- [13] Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Testing conditional independence of discrete distributions. In STOC, pages 735–748. ACM, 2018. doi:10.1145/3188745.3188756.
- [14] Clément L. Canonne, Yash Pote, Jonathan Scarlett, and Joy Qiping Yang. Entropy equivalence testing. CoRR, abs/2605.23225, 2026. doi:10.48550/arXiv.2605.23225.
- [15] Clément L Canonne and Joy Q Yang. Entropy testing and its application to testing Bayesian networks. Advances in Neural Information Processing Systems, 2024.
- [16] Clément L. Canonne. A short note on learning discrete distributions, 2020. arXiv:2002.11457.
- [17] Siu On Chan, Ilias Diakonikolas, Paul Valiant, and Gregory Valiant. Optimal algorithms for testing closeness of discrete distributions. In SODA, pages 1193–1203. SIAM, 2014. doi:10.1137/1.9781611973402.88.
- [18] David Maxwell Chickering, David Heckerman, and Christopher Meek. Large-sample learning of bayesian networks is np-hard. J. Mach. Learn. Res., 5:1287–1330, 2004. URL: https://jmlr.org/papers/volume5/chickering04a/chickering04a.pdf.
- [19] Davin Choo, Joy Qiping Yang, Arnab Bhattacharyya, and Clément L. Canonne. Learning bounded-degree polytrees with known skeleton. In ALT, Proceedings of Machine Learning Research, pages 402–443. PMLR, 2024. URL: https://proceedings.mlr.press/v237/choo24a.html.
- [20] C. K. Chow and C. N. Liu. Approximating discrete probability distributions with dependence trees. IEEE Trans. Inf. Theory, 14(3):462–467, 1968. doi:10.1109/TIT.1968.1054142.
- [21] Imre Csiszár and János Körner. Information Theory: Coding Theorems for Discrete Memoryless Systems. Cambridge University Press, 2011.
- [22] Sanjoy Dasgupta. Learning polytrees. In UAI, pages 134–141. Morgan Kaufmann, 1999. URL: https://dslpitt.org/uai/displayArticleDetails.jsp?mmnu=1&smnu=2&article_id=162&proceeding_id=15.
- [23] Constantinos Daskalakis, Nishanth Dikkala, and Gautam Kamath. Testing ising models. In SODA, pages 1989–2007. SIAM, 2018. doi:10.1137/1.9781611975031.130.
- [24] Constantinos Daskalakis, Gautam Kamath, and John Wright. Which distribution distances are sublinearly testable? In SODA, pages 2747–2764. SIAM, 2018. doi:10.1137/1.9781611975031.175.
- [25] Constantinos Daskalakis and Qinxuan Pan. Square hellinger subadditivity for bayesian networks and its applications to identity testing. In COLT, volume 65 of Proceedings of Machine Learning Research, pages 697–703. PMLR, 2017. URL: http://proceedings.mlr.press/v65/daskalakis17a.html.
- [26] Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, John Peebles, and Eric Price. Optimal testing of discrete distributions with high probability. In STOC, pages 542–555. ACM, 2021. doi:10.1145/3406325.3450997.
- [27] Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price. Sample-optimal identity testing with high probability. In ICALP, LIPIcs, pages 41:1–41:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.ICALP.2018.41.
- [28] Ilias Diakonikolas and Daniel M. Kane. A new approach for testing properties of discrete distributions. In FOCS, pages 685–694. IEEE Computer Society, 2016. doi:10.1109/FOCS.2016.78.
- [29] Oded Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. doi:10.1017/9781108135252.
- [30] Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653–750, 1998. doi:10.1145/285055.285060.
- [31] Jiantao Jiao, Kartik Venkat, Yanjun Han, and Tsachy Weissman. Minimax estimation of functionals of discrete distributions. IEEE Trans. Inf. Theory, 61(5):2835–2885, 2015. doi:10.1109/TIT.2015.2412945.
- [32] Liam Paninski. A coincidence-based test for uniformity given very sparsely sampled discrete data. IEEE Trans. Inf. Theory, 54(10):4750–4755, 2008. doi:10.1109/TIT.2008.928987.
- [33] Yury Polyanskiy and Yihong Wu. Information Theory: From Coding to Learning. Cambridge University Press, 2025.
- [34] Ronitt Rubinfeld. Taming big probability distributions. XRDS, 19(1):24–28, 2012. doi:10.1145/2331042.2331052.
- [35] Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252–271, 1996. doi:10.1137/S0097539793255151.
- [36] Igal Sason and Sergio Verdú. f-divergence inequalities. IEEE Trans. Inf. Theory, 62(11):5973–6006, 2016. doi:10.1109/TIT.2016.2603151.
- [37] Jan Seyfried, Sayantan Sen, and Marco Tomamichel. Testing (conditional) mutual information. Electron. Colloquium Comput. Complex., TR25, 2025. URL: https://eccc.weizmann.ac.il/report/2025/076.
- [38] Flemming Topsøe. Some inequalities for information divergence and related measures of discrimination. IEEE Trans. Inf. Theory, 46(4):1602–1609, 2000. doi:10.1109/18.850703.
- [39] Gregory Valiant and Paul Valiant. Estimating the unseen: An n/log(n)-sample estimator for entropy and support size, shown optimal via new clts. In STOC, pages 685–694. ACM, 2011. doi:10.1145/1993636.1993727.
- [40] Gregory Valiant and Paul Valiant. An automatic inequality prover and instance optimal identity testing. In FOCS, pages 51–60. IEEE Computer Society, 2014. doi:10.1109/FOCS.2014.14.
- [41] Yihong Wu and Pengkun Yang. Optimal entropy estimation on large alphabets via best polynomial approximation. In ISIT, pages 824–828. IEEE, 2015. doi:10.1109/ISIT.2015.7282570.
- [42] Yihong Wu and Pengkun Yang. Minimax rates of entropy estimation on large alphabets via best polynomial approximation. IEEE Trans. Inf. Theory, 2016. doi:10.1109/TIT.2016.2548468.
Appendix A Deferred Proofs
Fact 5. [Restated, see original statement.]
Let be a Poisson random variable with parameter , and be any function, then, we have that . In particular, choosing , we have that for all .
Proof.
We first show that by standard Poisson calculations:
The proof is then completed by induction, by noting that
