Entropy testing and its application to testing Bayesian networks

Authors: clément l canonne
joy qiping yang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-09 07:33:51

Abstract: This paper studies the problem of \emph{entropy identity testing}: given sample access to a distribution $p$ and a fully described distribution $q$ (both are discrete distributions over the support of size $k$), and the promise that either $p = q$ or $ | H(p) - H(q) | \geqslant \varepsilon$, where $H(\cdot)$ denotes the Shannon entropy, a tester needs to distinguish between the two cases with high probability. We establish a near-optimal sample complexity bound of $\tilde{\Theta}(\sqrt{k}/\varepsilon + {1}/{\varepsilon^2}$) for this problem, and show how to apply it to the problem of identity testing for in-degree-$d$ $n$-dimensional Bayesian networks, obtaining an upper bound of $\tilde{O}\left( {2^{d / 2} n}/{\varepsilon^2} + {n^2}/{\varepsilon^4} \right)$. This improves on the sample complexity bound of $\tilde{O}(2^{d/2}n^2/\varepsilon^4)$ from Canonne, Diakonikolas, Kane, and Stewart (2020), which required an additional assumption on the structure of the (unknown) Bayesian network.

Main paper: 
 introduction: 
 Entropy is a fundamental information theory notion, which quantifies the amount of "uncertainty" a given random variable carries. Since its introduction by Shannon, this notion has found myriads of applications, and is central -among others -to compression and coding, probability, electrical engineering, and learning theory.As a result, the task of estimating the Shannon entropy of a discrete random variable (or, equivalently, its probability distribution) from samples has naturally emerged, starting (in Computer Science) with the work of [BDKR02] which considered multiplicative approximations. Additive approximation of the entropy (within ±ε) was then considered in a series of papers [VV11a, VV11b, VV13, HJW15a, ADOS17], culminating with the work of [WY16] , which establishes the optimal sample complexity,Θ k ε log k + log 2 k ε 2, 1 where k ≫ 1 is the domain size.While the resulting sample complexity is sublinear in the domain size k, it is only so by a mere logarithmic factor. In some settings, paying this near-linear dependence in the amount of data necessary is impractical, typically in the large-domain regime (e.g., for high-dimensional data, where k is exponential in the dimension); moreover, it may even be unnecessary. Specifically, one may not be concerned so much about the (approximate) value of the entropy of a distribution, but rather about whether it is above a threshold, or differs from that of a given purported model.It is this latter task we introduce and consider in our work, which can be seen as a variant of the standard identity testing question from distribution testing: given a reference known hypothesis distribution q over a domain of size k, and i.i.d. samples from an unknown distribution p, what is the sample complexity of testing whether p is equal to q, or their entropies differ significantly? And, crucially, is this testing task more sample-efficient than that of estimating H(p)?Entropy Identity testing: Given a reference distribution q, parameter ε > 0, and samples from an unknown p, what is the cost of deciding (with high probability) whether p = q vs. |H(p) -H(q)| > ε, with correct probability at least 2/3?Note that in the case where q is the uniform distribution over the domain, this task is equivalent to distinguishing between H(p) = log k and H(p) < log k -ε.Our main contribution is to show that the testing question can indeed be performed much more efficiently than the estimation one, at least for most parameter regimes. Specifically, we establish the following theorem: Theorem 1.1. The sample complexity of entropy identity testing is O k log(k/ε)/ε + log2 (k)/ε 2 . Moreover, this is nearly tight: Ω √ k/ε + log 2 k/ε 2 samples are necessary in the worst case.Interestingly, this differs both from the estimation task (which, as discussed before, has a near-linear dependence on the domain size k) but also from identity testing in total variation distance, which has sample complexity Θ( √ k/ε 2 ) (see Section 1.1).Application: Identity testing for Bayesian networks. As an application of Theorem 1.1, we derive an efficient algorithm for identity testing (in total variation distance) for maximum in-degree d Bayesian networks (shorten as degree-d Bayes net in the remaining of the paper): 2 Theorem 1.2 (Informal; see Theorem 3.1). There is an algorithm which, given sample access to a degree-d Bayes net p and the full description of a reference degree-d Bayes net q (both over {0, 1} n ),takes Õ 2 d/2 n ε 2 + n 2 ε 4samples from p, and distinguishes between p = q and d TV (p, q) ≥ ε.Prior to this, the best known sample complexity upper bound for this task [CDKS20] was quadratically worse in both n and ε, and further required an assumption on the underlying graph structure of both p and q. We emphasize that (1) our result improves on the sample complexity of the learning baseline for d ≫ log(n/ε), and on its computational efficiency; and (2) compared to the previous testing results, removes strong structural assumptions which considerably limited their applicability. We elaborate on this in the next section.As previously discussed, entropy estimation has received a considerable amount of interest from computer scientists, information theorists and statisticians [BDKR02, Pan04, HJW15a, WY16] . Entropy is also a key example of symmetric property (invariant to relabeling of the domain) [VV11a, VV11b, VV13, ADOS17], and has been considered in other settings as well, e.g., the quantum case [GHS21, AISW20] and the memory-limited setting [ABIS19, AMNW22] . Estimation of some generalizations of Shannon entropy, such as the family of Rényi entropies, also have been studied [AOST17] .Over the years, sample complexity of identity testing for discrete distribution has been intensively studied and essentially settled [Pan08, BFF + 01, VV17]. In high dimensions, however, the square root dependence of the sample complexity on the domain size means that most identity testing tasks of interest require sample complexity exponential in the dimension. Moreover, this curse of dimensionality extends to a large range of distribution testing problems [BCY22, Theorem B.1]. As such, many turn to the study of testing distributions under additional natural structural assumptions, such as graphical models: [BGKV21] look at identity testing for product distributions (degree-0 Bayes nets) and give the optimal bound of Θ( n|Σ|/ε 2 ), where |Σ| is the alphabet size of each variable (rather than binary alphabet studied in our paper). [DDK19, KDDC23] study testing Ising models, obtaining sample complexity bounds that are poly(n/ε); [DP16], [CDKS20] give tight results to identity testing and closeness testing for a variety of constant in-degree Bayes nets, which also gives polynomial sample complexity bounds.However, the testing algorithms provided in [CDKS20] and [DP16] are not fully satisfactory, as they require some strong assumptions on Bayes nets. Specifically, [CDKS20, Theorem 21] assumes that the topological ordering of the two Bayes nets are the same, and shows that under this assumption O(2 d/2 n 2 /ε4 ) samples are sufficient.3 [CDKS20, Theorem 17] makes the further stringent restriction that the reference Bayes net has to be balanced, i.e., that the conditional probabilities are all bounded away from 0 and 1; moreover, it also requires every parental configuration to be bounded from 0, and that the structure of the unknown Bayes net be a subset of that of the reference one. The result of [DP16, Theorem 4.2] combined with the Hellinger tester from [DKW18, Theorem 1] implies that, under the assumption that p and q share the same factorization structure (i.e., their associated DAGs are the same or one is a subgraph of the other), then this problem is solvable in Õ 2 d/2 n/ε 2 samples. While this latter sample complexity is near-optimal (in some regime 4 ), in view of the Ω 2 d/2 n/ε 2 lower bound obtained in [BCY22, Theorem 4.1], the factorization structure requirement considerably limits the applicability of the algorithm.One can also compare our result to the learning results on Bayesian networks, as any learning algorithms enables testing as well (the "testing-by-learning" baseline). It is known [CDKS20] ) that learning degree-d Bayes nets can be done with Õ(2 d n/ε 2 ) samples, without any structural assumptions. Our testing result improves on this sample complexity as long as n 2 /ε 4 ≪ 2 d n/ε 2 , i.e., for d ≫ log(n/ε); moreover, it is worth noting that the known learning algorithms are computationally inefficient (running in time n O(dn) via an enumeration of all possible underlying graph structures [CDKS20, BGMV20]), and this is believed to be inherent [CHM04] . In contrast, our algorithm runs in time poly(n d , 1/ε).Testing in entropy. A first idea is to use the conversion between total variation (TV) distance and entropy difference to reduce this problem to identity testing in TV:When d TV (p, q) ⩽ 1/2, then |H(p) -H(q)| ⩽ d TV (p, q) log k dTV(p,q) [CK11, Lemma 2.7]. This gives an up- per bound of O( √ k log 2 (k/ε) ε 2), which is already better than the sample complexity of estimation:O k ε log k + log 2 k ε 2for the parameter k. However, it is not clear whether the quadratic dependence on ε is necessary: indeed, the "hard instances" for TV testing (the Paninski construction [Pan08] ), small perturbations around the uniform distribution which have TV distance ε from uniform, actually only have entropy log k -Θ(ε 2 ). The Ω( √ k/ε 2 ) uniformity testing lower bound from these hard instances thus only implies an Ω( √ k/ε) entropy identity testing lower bound!A next natural idea is to strengthen the lower bound. However, it then becomes clear that the Paninski [Pan08] construction cannot be improved: as just mentioned, when its TV distance to the uniform distribution is around Θ( √ ε) its entropy difference to it is only Θ(ε) (giving an Ω( √ k/ε) lower bound). Moreover, this is not a coincidence: when the reference distribution q is uniform, we are able to get a matching upper bound using [DKW18, Algorithm 1], upon noticing thatEQUATIONwhich implies d KL (p∥u k ) = log k -H(p) ⩾ ε, where u k is the uniform distribution on [k] and d KL denotes the Kullback-Leibler divergence. Interestingly, a completely different hard instance, against a very much non-uniform reference distribution, does yield the second term of our lower bound, Ω(log 2 k/ε 2 ).Inspired by these two different lower bounds, we can generalize (1) by defining A as the set of "not too small probability elements under q", and then observing (looking ahead, using the inequality (12)) that|H(p A ) -H(q A )| ⩽ |d KL (p A ∥q A )| + i∈A (p i -q i ) log 1 q i (2)where H(p A ) is the "entropy" of the sub-distribution restricted to the set A. In particular, this hints that one could solve the general problem by testing if either of the two terms on the right-hand-side is large. The name of the game now is to (i) choose the threshold for A (i.e., what does it mean for an element to have "not too small probability under q"), and (ii) have algorithms to test whether these two quantities are noticeably large.Let us focus on how to test the first term of (2). If min i q i ⩾ Ω ε k , we can adapt and use an algorithm of [DKW18] to efficiently test d KL (p∥q) ⩾ ε vs. p = q. In addition, if log(1/q i ) is bounded, then in fact, estimating the second term to O(ε) is possible as well. Thus it is natural to wonder if we can afford to neglect the region where q i ⩽ ε k . Indeed, the impact on entropy is at most O(τ log(k/τ )) if we are to remove regions with at most O(τ ) as mass. Thus, by adjusting the appropriate threshold, we can still detect difference in entropy even if we only test on elements with greater than τ /k masses, where τ = ε log(k/ε) . The problem then becomes to check if p puts more than 100 • τ mass in Ā = {i ∈ [k] : q i < τ /k}, which costs O(1/τ ) = O(log(k/ε)/ε) samples. If it does, then it cannot be the case that p = q; we can reject. After this stage, both p( Ā), q( Ā) ⩽ O(τ ). To move forward, we need to check the influence on entropy: H(p) and H(q). By Jensen's inequality and monotonicity of f (x) = x log 1 x when x < 1 e , we havei∈ Ā p i log 1 p i ⩽ p( Ā) log k p( Ā) ⩽ τ log k τ .Therefore, the impact on entropy will be at mostO τ log k τ . Setting τ = ε log(k/ε) , this becomes O(ε), which gives us the room to check if |H(p A ) -H(p A )| ⩾ 100ε or p A = q A .Testing Bayesian networks. Similar to [DP16, Theorem 4.2],5 the identity testing algorithm is straight-forward: check every possible subset of size d + 1 if p L = q L or one of them is far apart, where p L denotes the marginalization of p over subset L. 6 If p = q, then obviously, all such tests will accept with high probability; and by subadditivity of squared Hellinger distance, this will guarantee that for any DAG, and a projection p G (resp. q G ) of p (resp. q) unto G (see, [DP16, Corollary 2.4]):d H (p G , q G ) ⩽ ε.While it seems unintuitive that this method does not work without the common-structure assumption, directly extending this argument does not work. Indeed, if they (p and q) do not share a common structure, then it is clear that p ̸ = q; but the tricky part is the farness case, when d H (p, q) ⩾ ε and p, q does not share a common structure; the tester could still accept if every d H (p L , q L ) ⩽ ε/ √ n, which only guarantees that d H (p G , q G ) ⩽ ε for every G. Our fix to the problem is to additionally check if there exists a common graph G where d H (p, p G) and d H (q, q G) are close. If it does, via triangular inequality, we can in fact show thatd H (p, q) ⩽ d H (q, q G) + d H (q G, p G) + d H (p, p G) ⩽ O(ε).This handles the last possible issue. To this end, we will conduct local entropy identity test between p and q for subset of size d + 1 and d. The idea is that if all tests pass, then we can conclude that p and q are close in local entropy and thereafter, we can utilize entropy of q to learn the graphical structure [KCG + 23] of p (which uses no additional samples).Preliminaries and notation. The (Shannon) entropy H of a discrete distribution p supported on [k] is given by:H(p) = - i∈[k] p i log p i .The conditional entropy H(p X | p Y ) for X supported on X , and Y on Y, defined by the joint distribution p X,Y , can be written asEQUATIONWe adopt the entropy notation for a sub-probability vector H(q A ) = i∈A q i log 1 qi . Throughout this paper, we will use e as base of the log and of the entropy. We will use ← for variable assignment.We adopt the standard O(•), Ω(•) and Θ(•) asymptotic notation and use • to hide any polylogarithmic factors in the argument. We will use various metrics or divergences on probability distributions: Kullback-Leibler (d KL ), Hellinger (d H ), chi-squared (d χ 2 ), and total variation (d TV ). We denote p A as restricting p onto the elements in A, and we denote distributional distances restricting on A as follows:d KL (p A , q A ) = i∈A p i log pi qi . d H (p A , q A ) = 1 √ 2 i∈A √ p i - √ q i 2 .For a set A, we write p(A) = i∈A p i . We also have the following inequality [DKW18, Proposition 1]:EQUATIONA distribution p supported over the hypercube {0, 1} n is a Bayesian network if its probability mass function satisfies the factorization associated with G, a directed acyclic graph (DAG): 2 Near-optimal entropy testingEQUATIONWe prove Theorem 1.1, establishing the sample complexity upper and lower bounds separately. 
an: 
 O √ k log(k/ε) ε + log 2 (k) ε 2upper boundWe will prove the following theorem: Theorem 2.1. There is an algorithm (Algorithm 1) which, given n samples from a discrete distribution p, the full description of a reference distribution q, both over [k], and parameter ε > 0, distinguishes between p = q and |H(p) -H(q)| ⩾ ε with probability at least 2/3, as long asn ≥ c 1 k log(k/ε) ε + log 2 (k) ε 2and c 2 ε ⩽ k, for some absolute constants c 1 , c 2 > 0. Moreover, the algorithm runs in time linear in the number of samples n and the domain size k.The proof will rely on the two following claims and Lemma 2.4, which is a straightforward extension of [DKW18, Lemma 2]. Their proofs are deferred to Appendix B. Throughout, we let τ := ε 16 log(k/ε) , andA := i ∈ [k] | q i ⩾ τ k , as in Algorithm 1. Claim 2.2. Let A be any set such that p( Ā) < ε/2. Then, if |H(p A ) -H(q A )| ⩾ ε, we must have (i) d KL (p A ∥q A ) ⩾ ε 2 or (ii) | i∈A (p i -q i ) log( 1 qi )| ⩾ ε 2 .Claim 2.3. Let p be the empirical estimator for an unknown discrete distribution p supported on [k], based on Poi(m) samples, where m = Θ log 2 (k)ε 2 ; assume that d χ 2 (p A , q A ) ⩽ ε/8 and p( Ā) + q( Ā) ⩽ 4τ = 1 4 ε log(k/ε) , 7 then Pr i∈A (p i -pi ) log 1 q i ⩾ 1 8 ε ⩽ 1 100 .Algorithm 1 Entropy identity testing Require: Sample access to p and full description of q, both over [k]; accuracy parameter ε.1: Set τ := ε 16 log(k/ε) , and A := i ∈ [k] | q i ⩾ τ k . 2:Take m 1 = 48/τ samples from p and compute the empirical p′ .3: Compute Z 1 = p′ ( Ā). 4: if Z 1 ⩾ 2τ then return reject ▷ Early rejection. ▷ N i : the empirical count among samples of the i-th element. 5: Let m 2 = 65536 √ k•log(k/ε) ε. Draw Poi(m 2 ) samples from p and computeZ 2 = i∈A (N i -N q i ) 2 -N i N q i . 6: if Z 2 ⩾ 1 16 m 2 ε then return reject 7: Let m 3 = 140800 log 2 (k) ε 2 8: Draw Poi(m 3 ) samples from p, compute the empirical p; let Z 3 ← i (p i -q i ) log 1 qi . 9: if Z 3 ⩾ 1 8 ε then return reject 10: return accept Lemma 2.4. Let A := {i ∈ [k] | q i ⩾ α}. Let m 2 ⩾ 16384 max 1 αε , √ k ε be the number of samples used to compute Z 2 . Then E[Z 2 ] = m 2 d χ 2 (p A , q A ). Moreover, if d χ 2 (p A , q A ) ⩽ ε 2 , then Var[Z 2 ] ⩽ ( 1 32 m 2 ε) 2 . If d χ 2 (p A , q A ) ⩾ ε, then Var[Z 2 ] ⩽ O(E[Z 2 ] 2 ).Proof of Theorem 2.1. We prove the statement by analyzing Algorithm 1. First, note that excluding the set of Ā (elements with small mass), can change the value of H(q) by at most ε/8: indeed, by Jensen's inequality (f (x) = log x is concave) and x log 1 x being monotonically increasing in (0, 1/e),H(q Ā) = i∈ Ā q i log 1 q i ⩽ q( Ā) log | Ā| q( Ā) ⩽ τ log k τ = ε 16 log(k/ε) log 16k ε/ log(k/ε) ⩽ 1 8 ε, when τ ⩽ 1/e. Similarly, if p( Ā) ⩽ 3τ , we have that H(p Ā) ⩽ 3 8 ε. Therefore, ε ⩽ |H(p) -H(q)| ⩽ |H(p A ) -H(q A )| + |H(p Ā) -H(q Ā)| ⩽ |H(p A ) -H(q A )| + |H(p Ā)| + |H(q Ā)| ⩽ |H(p A ) -H(q A )| + 1 2 ε.For Line 4, we prove the following: with probability at least 99/100, ifZ 1 ⩾ 2τ , then p( Ā) ⩾ τ ; and if Z 1 < 2τ , then p( Ā) < 3τ (this is a standard technique; see e.g., [Can22, Fact 2.2].) For the sake of completeness we include the full derivation in the Appendix A.After Line 4 of Algorithm 1. We conclude from the above that i. A still has sufficient entropy gap to test on:|H(p A ) -H(q A )| ⩾ 1 2 ε.ii. With probability at least 99/100, when p = q, it will not be rejected in Algorithm 4 of Line 4; and once it is pass through this stage, we have p( Ā) ⩽ 3τ .Completeness: when p = q.• We have that d χ 2 (p A , q A ) = 0, and via Lemma 2.4, we know thatE[Z 2 ] = 0 and Var[Z 2 ] ⩽ 1 32 2 m 2 2 ε 2 . By Chebyshev's inequality, Pr |Z 2 -E[Z 2 ]| ⩾ 2 Var[Z 2 ] ⩽ 1 4 , and so Pr[Z 2 ⩾ 2 • 1 32 m 2 ε + E[Z 2 ]] ⩽ 1 4 ; and we have Pr[Z 2 ⩾ 1 16 m 2 ε] ⩽ 1 4 .• On the other hand, by Claim 2.3, setting m 3 = 140800 log 2 (k)ε 2, we have that with probability at least 99/100,Z 3 = i∈A (p i -q i ) log 1 q i = i∈A (p i -p i ) log 1 q i ⩽ 1 8 ε.Therefore, with probability at least 1 -1 4 -2 100 = 73 100 > 2 3 , the tester will accept. Soundness: when |H(p) -H(q)| ⩾ ε. If p( Ā) ⩾ 3τ then p( Ā) ⩾ 2τ with probability 99/100, and the algorithm will output Reject. We proceed assuming p( Ā) ⩽ 3τ and recall Item ii. from before, we have|H(p A ) -H(q A )| ⩾ 1 2 ε. By Claim 2.2, we have that either d KL (p A , q A ) ⩾ 1 4 ε or i∈A (p i -q i ) log (1/q i ) ⩾ 1 4 ε. We apply Lemma 2.4, setting α = τ /k and m 2 ⩾ 65536 k log(k/ε)/ε. • If d KL (p A ∥q A ) ⩾ 1 4 ε, with (4) and exp(3/2) ⩽ k/ε, we have 1 8 ε ≤ -3τ + d KL (p A , q A ) ⩽ i∈A (q i -p i ) + d KL (p A , q A ) ⩽ d χ 2 (p A , q A ),which by Lemma 2.4, and our setting of m 2 and α, impliesVar[Z 2 ] ⩽ ( 1 4 E[Z 2 ]) 2 and E[Z 2 ] = m 2 • d χ 2 (p A , q A ) ⩾ 1 8 m 2 ε. By Chebyshev, Pr |Z 2 -E[Z 2 ]| ⩾ 2 Var[Z 2 ] ⩽ 1 4 and so Pr[Z 2 ⩽ 1 16 m 2 ε] ⩽ 1 4 . • On the other hand, if it is the case that i∈A (p i -q i ) log (1/q i ) ⩾ 1 4 ε, by Claim 2.3, setting m 3 = 140800 log 2 (k)/ε 2 , with probability at least 99/100, 1 4 ε ⩽ i p i log 1 q i -q i log 1 q i ⩽ i (p i -pi ) log 1 q i + i (p i -q i ) log 1 q i ⩽ 1 8 ε + i (p i -q i ) log 1 q i .We have that Z 3 = i (p i -q i ) log 1 qi ⩾ 1 8 ε and thus with probability at least 1 -1 4 -2 100 = 73 100 , the following will happen, the tester will reject: either p( Ā) ⩾ 3τ , and it is rejected at Line 4 of Algorithm 4, or it passes and p( Ā) ⩽ 3τ andZ 2 ⩾ 1 8 m 2 ε or Z 3 ⩾ 1 8ε, and will be rejected. This concludes the proof.Remark 2.5. We note that we can slightly improve the sample complexity of Theorem 1.1 (specifically, improving on the k log(k/ε) term), at the price of a more complicated algorithm, by adding thresholdsτ ′ = ε log log(k/ε) , τ ′′ = ε log log log(k/ε) ,A ′ = {i : q i ∈ (τ /k, τ ′ /k]}, A ′′ = {i : q i ∈ (τ ′ /k, τ ′′ /k]}; specifically, by grouping them in groups, and "merging" each group to get a "new" element with larger probability. For the sake of clarity, we defer this improvement to Appendix E.Ω( √ k/ε + log 2 k/ε 2 ) lower boundThe Ω( √ k/ε + log 2 k/ε 2 ) lower bound comes from the combination of Lemma 2.6 and Lemma 2.7. We obtain Lemma 2.6 through the classical hard instance used for uniformity testing [Pan08] and a simple conversion between TV distance and entropy difference gives the result. We note that distributions close to uniform distribution actually have smaller entropy difference (uniform distribution is quite special: having the highest entropy of log k). Indeed, replacing the uniform distribution with a slightly biased distribution, we obtain another hard instance for Lemma 2.7, using the classical Le Cam's two-point method.Algorithm 2 Identity testing for bounded degree Bayes nets Require: Sample access to Bayes net p, full description of Bayes net q, accuracy parameter ε, in-degree d and dimension n.1: S 1 ← O 2 d/2 n √ d log(n/ε) ε 2 + d 2 n 2 ε 4 d log n samples from p; 2: S 2 ← O 2 d/2 n ε 2 log(1/ε) • log n samples from p; 3: for all L ∈ N d+1 ∪ N d do ▷ N ℓ is all subsets of {0, 1} n with size ℓ 4:Call Algorithm 1 with p L , q L and S 1 ; ▷ Entropy test on p L and q L with accuracy ε 2 /n.if Entropy test rejects then return reject6: S 3 ← O d log(n)•log(1/ε) ε 2samples from p and compute its empirical distribution p;7: for all i ∈ [n] do 8: if pXi,Π G i ( Ā′ i ) ⩾ Ω(ε 2 / log(1/ε)) then return reject 9: Check d KL (p Xi,Π G i ;A ′ i ∥q Xi,Π G i ;A ′ i ) ⩾ ε 2 n or d KL (p Xi,Π G i ;A ′ i ∥q Xi,Π G i ;A ′ i ) = 0.10:if i-th KL test says far then return reject 11: return accept ▷ Accept if all tests pass.Lemma 2.6. With fewer than c 3 • √ k/ε samples from p, no tester can distinguish between p = q and |H(p) -H(q)| ⩾ ε with probability higher than 2/3, where c 3 > 0 is an absolute constant.Lemma 2.7. With fewer than c 4 • log 2 k/ε 2 samples from p, no tester can distinguish between p = q and |H(p) -H(q)| ⩾ ε with probability higher than 2/3, where c 4 > 0 is an absolute constant. 
application to identity testing for bayes nets: 
 We now provide an application of our main entropy identity testing theorem, to obtain an improved "standard" identity testing algorithm for Bayesian networks: Theorem 3.1. Given sample access to an in-degree d Bayes net p and full description of in-degree d Bayes net q, Algorithm 2 takes C •2 d/2 nd 3/2 log n• √ log(n/ε) ε 2 + d 3 n 2 •log n ε 4samples to test between p = q or d H (p, q) ⩾ Ω(ε), where C > 0 is an absolute constant. Moreover, the algorithm runs in time polynomial in n d and 1/ε.Before proceeding to the analysis of our algorithm, we require the following definitions. Definition 3.2. A projection of a Bayes net p on {0, 1} n unto a DAG G is denoted p G , and is defined by its probability mass function (PMF) as follows:p G (X 1 , . . . , X n ) = n i=1 p(X i | Π G i ),whereΠ G i is the set of parents of X i in G. Denote U := n i=1 A i , where A i := x ∈ {0, 1} n : q Xi,Π G i (x i (x), π G i (x)) ⩾ Ω ε 2 / log(1/ε) 2 d+1 n .This gives us the property that marginalization over X i = x i , Π G i = π G i works nicely as we include elements only based on its local property (as long as q Xi,Πi is large enough). And q is Markov w.r.t.G. We use (x i , π i ) ∈ A ′ i , where A ′ i = x ′ ∈ {0, 1} |Π G i |+1 : q Xi,Π G i (x ′ ) ⩾ Ω ε 2 / log(1/ε) 2 d+1 n. Let (a, B) ∈ A ′ i , we have that as long as (x i (x), π i (x)) = (a, B), then x ∈ A i and vice versa, which means thatU = n i=1 A i = n i=1 {x ∈ {0, 1} n : (x i (x), π G i (x)) ∈ A ′ i }.We will check if p Xi,Π G i ( Ā′ i ) ⩾ Ω(ε 2 / log(1/ε)) and reject early if true; this takesO d log(n)•log(1/ε) ε 2samples for all tests to be correct via a union bound. After passing this test, we can conclude thatp( Ū) = x∈ n i=1 Āi p(x) ⩽ x∈ Ā1 p(x) ⩽ x ′ ∈ Ā′ 1 p X1,Π G 1 (x ′ ) = p X1,Π G 1 ( Ā′ 1 ) ⩽ O(ε 2 / log(1/ε)).Similarly, we can upper bound q( Ū) ⩽ q Xi,Π G i ( Ā′ i ) ⩽ O(ε 2 / log(1/ε)). Denote p G;U as projecting p onto G, which gives p G and then restricting the distribution p G to take elements in U. Claim 3.3. Suppose that p( Ū) ⩽ O(ε 2 / log(1/ε)), then we haved KL (p Ū ∥p G; Ū ) ⩾ -p( Ū) • log 1 p( Ū) ⩾ -O(ε 2 ).We will also need the following lemma whose proof is deferred to Appendix C.Lemma 3.4. Suppose d 2 H (p, q) ⩾ Ω(ε 2 ) and d KL (p∥p G ) ⩽ O(ε 2 ), then we have n i=1 d KL (p Xi,Π G i ;A ′ i ∥q Xi,Π G i ;A ′ i ) ⩾ Ω(ε 2 ). Therefore testing d KL (p Xi,Π G i ;A ′ i ∥q Xi,Π G i ;A ′ i ) ⩾ ε 2n over all i suffices to detect this case.Proof of Theorem 3.1. We show the result by analyzing Algorithm 2. By Theorem 1.1, the sample complexity for entropy testing on any subset L of size (dimension)d or d + 1, is O 2 d/2 n d log(n/ε)/ε 2 + d 2 n 2 /ε 4 .To guarantee the success of every tests employed in the algorithm, we increase the sample complexity of each test by an extra O(log(n d+1 )) = O(d log n) factor to boost their success probability to 1 -1 100n d+1 (via a standard majority vote technique), which will allow us to use a union bound over all tests as there are at most n d+1 subsets with size d + 1. For this step, the sample complexity will beO 2 d/2 n d log(n/ε) ε 2 + d 2 n 2 ε 4 d log n .With this in hand, we will proceed with the analysis under the event that every entropy test performed is correct (which by the above happens with high probability). If distribution p manages to pass all the entropy tests, it must satisfy the following:EQUATIONfor every subset L of size d + 1 for the latter, and every subset L of size d or d + 1 for the former. From here, in principle, we can perform structural learning of p through H(q L ), which then gives us an approximated DAG Ĝ of p and we can check d H (p Ĝ, q Ĝ). Unfortunately, structural learning of Bayes nets is known to be computationally hard in many settings [Höf93, CHM04] , and so this would lead to a computationally inefficient algorithm.Instead, we argue that this (learning) step can be bypassed entirely: the intuition of the argument is to view structure learning for Bayes net as an optimization problem; and any assignment x to the two optimization problems (structure learning of p and q) satisfy f 1 (x) = f 2 (x)±O(ε 2 ) due to their local entropy being close8 -this means that an optimax 1 for f 1 satisfies min x f 1 (x) = f 1 (x 1 ) ⩾ f 2 (x 1 ) -ε 2 ⩾ min x f 2 (x) -ε 2 and vice versa (optima x 2 for f 2 ).More formally, by the celebrated works of Chow and Liu [CL68] and its generalization to Bayes net, one can write the KL divergence between Bayes net and its projection to any graph G as difference between sum of n local conditional entropies (we provide a derivation for the sake of completeness in F):EQUATIONEQUATIONwhere X Πi denotes the parents of X i in Bayes net p and X Π G i denotes the parents of X i in DAG G. Here we assume that q is Markov with respect to G. Since the local entropies between p and q are close by O(ε 2 /n) (see ( 6)) and its relation to conditional entropy via (3), we can conclude the following:EQUATION)By our assumption, since q is Markov to G, we can combine (7), ( 9) and (10), which then give:0 ⩽ d KL (p∥p G ) ⩽ - n i=1 H(q Xi,XΠ i |q XΠ i )+ n i=1 H(q Xi,X Π G i |q X Π G i )+O(ε 2 ) = -d KL (q∥q G ′ )+O(ε 2 ),where p is Markov to G ′ , as Π i is the set of parents of X i for p. Rearranging terms and we haveEQUATIONWith this at hand, we continue onto the KL testing part. The algorithm will check ifp Xi,Π G i ( Ā′ i ) ⩾ Ω(ε 2 / log(1/ε)) and reject early if it is true (this costs O d log(n)•log(1/ε) ε 2) and then check forevery i ∈ [n], d KL (p Xi,Π G i ;A ′ i ∥q Xi,Π G i ;A ′ i ) ⩾ ε 2 n or d KL (p Xi,Π G i ;A ′ i ∥q Xi,Π G i ;A ′ i ) = 0.Using Lemma 2.4 (after converting from KL to χ 2 noting the mass of A ′ on both distributions) and a union bound over n tests, the sample complexity isO 2 d/2 n ε 2 log(1/ε) • log n .Following this, we look at the two cases:• If p = q, then with high probability, p will pass all entropy tests, all KL local tests and the tester will accept. • If d H (p, q) ⩾ ε, either it fails one of the entropy test. If it does pass the entropy test, then we must have that d KL (p∥p G ) ⩽ O(ε 2 ) by (11). Then following Lemma 3.4 and Lemma 2.4, the tester will reject.In total, the sample complexity is (dominated by entropy testing):O 2 d/2 n d log(n/ε) ε 2 + d 2 n 2 ε 4 d log n .This concludes the proof of the theorem. 
conclusion and open problems: 
 In this paper, we study a variant of distribution testing problem in terms of entropy difference; we give nearly tight upper and lower sample complexity bounds for the problem. We subsequently apply our entropy testing algorithm to identity testing of Bayes nets, which unlike prior works, makes merely the necessary assumptions (the bound on the in-degree of the Bayes nets).Future direction. We believe the closeness (two-sample) testing variant of the problem (testing if two unknown distribution p and q are the same or far in terms of entropy difference) could also be interesting; and, notably, has connections to other distribution testing problems: first, it should lead to a natural solution to closeness testing of Bayes nets via ideas in this paper. Second, solving the closeness entropy testing problem give another path to testing independence in terms of mutual information (studied in [BGP + 23] and also covered in [CDKS18] ), a notion closely related to entropy.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [NA] Justification: The paper does not contain experiments. 
open access to data and code: 
 Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [NA] Justification:Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [NA]Justification:Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [NA]Justification:Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. Justification:Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: this work is theoretical in nature; it is hard to predict its societal impact.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: We need to show the following: with probability at least 99/100, if Z 1 ⩾ 2τ , then p( Ā) ⩾ τ ; and if Z 1 < 2τ , then p( Ā) < 3τ . For the first one, we prove by contrapositive: with high probability 1 -1 200 , p( Ā) < τ ⇒ Z 1 < 2τ . Suppose T = Binomial(m 1 , τ ) and setting m 1 = 48 τ ⩾ 3 log 200 τ , and using a Chernoff bound, we have the followingPr[T ⩾ 2τ ] ⩽ exp(-τ • m 1 /3) ⩽ 1 200 .Since any Binomial(m 1 , p( Ā)) will be first-order stochastic dominated by Binomial(m 1 , τ ) if p( Ā) < τ , we can conclude the following: if p( Ā) < τ , thenPr[Z 1 ⩾ 2τ ] ⩽ Pr[T ⩾ 2τ ] ⩽ 1 200 .For the latter, we prove via its contrapositive: with probability 1-1 200 , p( Ā) ⩾ 3τ ⇒ Z 1 ⩾ 2τ . As p( Ā) ⩾ 3τ , take m 1 = 48 τ ⩾ 9 log 200 τ, by a Chernoff bound, we havePr[p ′ ( Ā) ⩽ 2τ ] ⩽ Pr[p ′ ( Ā) ⩽ (1-1/3)•p( Ā)] ⩽ exp - m 1 • p( Ā) 18 ⩽ exp - m 1 • τ 9 ⩽ 1 200.Combining the two with a union bound concludes the proof.B Deferred proofs from Section 2.1Claim 2.2. Let A be any set such that p( Ā) < ε/2. Then, ifEQUATIONwhich implies that at least one of the two terms is at least ε/2. If it is the second, we are done; otherwise, we know that eitherd KL (p A ∥q A ) ⩾ 1 2 ε or d KL (p A ∥q A ) ⩽ - 1 2 ε.We will rule out the second case, using that log1 x ⩾ 1 -x for x > 0, 9 d KL (p A ∥q A ) = i∈A p i log p i q i ⩾ i∈A p i 1 - q i p i = q( Ā) -p( Ā) > - 1 2 ε.Thus, we cannot have d KL (p A ∥q A ) ⩽ -1 2 ε and so d KL (p A ∥q A ) ⩾ 1 2 ε. Claim 2.3. Let p be the empirical estimator for an unknown discrete distribution p supported on [k], based on Poi(m) samples, where m = Θ log 2 (k)ε 2 ; assume that d χ 2 (p A , q A ) ⩽ ε/8 and p( Ā) + q( Ā) ⩽ 4τ = 1 4 ε log(k/ε) , 10 then Pr i∈A (p i -pi ) log 1 q i ⩾ 1 8 ε ⩽ 1 100 .Proof of Claim 2.3. We follow the same analysis as in [WY16] .Letting Y i := (p i -pi ) log 1 qi for i ∈ A, we have E[Y i ] = 0 and Var[Y i ] = E[(Y i -E[Y i ]) 2 ] = E[Y 2 i ] = E[(p i -pi ) 2 ] log 2 1 q i = 1 m 2 (mp i ) log 2 1 q i = p i m log 2 1 q i .Let Y := i∈A (p i -pi ) log 1 qi . We will use our assumption that d χ 2 (p A , q A ) ⩽ ε/8 and p( Ā) + q( Ā) ⩽ 1 4 ε log(k/ε) below. Note that, our analysis is in the Poissonized setting: i∈A p i log 2 1 pi ⩽ 2 log 2 k + 3 in (14). We use the premise and (4) in (15) and we have thatEQUATIONd TV (p, q) = d TV (p A , q A ) + d TV (p Ā, q Ā) ⩽ d χ 2 (p A , q A ) + p( Ā) + q( Ā) ⩽ ε 8 + 4τ ;and the last step is obtained by noticing that log(k) ⩾ 2 3 for k ⩾ 2. By Chebyshev's inequality, we then have thatPr   |Y | ⩾ 10 38 log 2 k m   ⩽ Pr |Y -E[Y ]| ⩾ 10 Var[Y ] ⩽ 1 100 ,and this last inequality yields the statement as long as m ⩾ 22×100×8 2 log 2 (k)ε 2 = 140800 log 2 (k) ε 2 . Lemma 2.4. Let A := {i ∈ [k] | q i ⩾ α}. Let m 2 ⩾ 16384 max 1 αε , √ k ε be the number of samples used to compute Z 2 . Then E[Z 2 ] = m 2 d χ 2 (p A , q A ). Moreover, if d χ 2 (p A , q A ) ⩽ ε 2 , then Var[Z 2 ] ⩽ ( 1 32 m 2 ε) 2 . If d χ 2 (p A , q A ) ⩾ ε, then Var[Z 2 ] ⩽ O(E[Z 2 ] 2 ).Proof of Lemma 2.4. The proof is a relatively straightforward modification of the argument of [DKW18, Lemma 2]. We have the expectation and variance of Z 2 ,E[Z 2 ] = m 2 d χ 2 (p A , q A ) and Var[Z 2 ] = i∈A 2 p 2 i q 2 i + 4m 2 p i (p i -q i ) 2 q 2 i .It boils down to bounding the following,2 i∈A p 2 i q 2 i ⩽ 4k + 4 i∈A (p i -q i ) 2 q 2 i ⩽ 4k + 4 α i∈A (p i -q i ) 2 q i ⩽ 4k + 4 αm 2 E[Z 2 ].Derivation of the inequalities follow from [DKW18, proof of Lemma 2].4m 2 i∈A p i (p i -q i ) 2 q 2 i ⩽ 4m 2 i∈A p 2 i q 2 i 1/2 i∈A (p i -q i ) 4 q 2 i 1/2 ⩽ 4m 2 4k + 4 αm 2 E[Z 2 ] 1/2 i∈A (p i -q i ) 2 q i = 4 2 √ k + 2 1 αm 2 E[Z 2 ] E[Z 2 ] = 8 √ kE[Z 2 ] + 8(αm 2 ) -1/2 (E[Z 2 ]) 3/2 .Combing both, we have thatEQUATION)When d χ 2 (p A , q A ) ⩽ ε/2, then E[Z 2 ] ⩽ m2ε 2 ; and we solve Var[Z 2 ] ⩽ ( 1 32 m 2 ε) 2 , which gives4k + 4 αm 2 + 8 √ k m 2 ε 2 + 8(αm 2 ) -1/2 ( m 2 ε 2 ) 3/2 ⩽ ( 1 32 m 2 ε) 2 .We solve for the relaxation:LHS ⩽ 4 • max 4k, 2ε α 4 √ km 2 ε, 8 m 2 √ α2 3/2 ε 3/2 ⩽ ( 1 32 m 2 ε) 2In the end, we obtain:max 128 • √ k ε , 64 2 αε , 32 2 • 16 √ k, 32 2 • 16 1 √ αε √ 2 ⩽ 32 2 • 16 • max √ k ε , 1 αε ⩽ m 2 When d χ 2 (p A , q A ) ⩾ ε, then E[Z 2 ] ⩾ m 2 ε; and we solve Var[Z 2 ] ⩽ ( 1 4 E[Z 2 ]) 2 , 4k + 4 αm 2 + 8 √ k E[Z 2 ] + 8(αm 2 ) -1/2 (E[Z 2 ]) 3/2 ⩽ ( 1 4 E[Z 2 ]) 2 ,which is equivalent to the following4k (E[Z 2 ]) 3/2 + 4 αm 2 + 8 √ k 1 (E[Z 2 ]) 1/2 + 8(αm 2 ) -1/2 ⩽ 1 16 (E[Z 2 ]) 1/2Further relaxing the solution, it is enough to have4k (E[Z 2 ]) 3/2 + 4 αm 2 + 8 √ k 1 (E[Z 2 ]) 1/2 + 8(αm 2 ) -1/2 ⩽ 4k (m 2 ε) 3/2 + 4 αm 2 + 8 √ k 1 (m 2 ε) 1/2 + 8 1 √ αm 2 ⩽ 1 16 (m 2 ε) 1/2 ⩽ 1 16 (E[Z 2 ]) 1/2 ,as long as the following holds,EQUATIONEQUATION)Letting m 2 ⩾ 512 max1 αε , √ k ε, we have that both statements.Proof of Claim 3.3.d KL (p Ū ∥p G; Ū ) = x∈ Ū p(x) log p(x) p G (x) = - x∈ Ū p(x) log p G (x) p(x) ⩾ -   x∈ Ū p(x)   • log   x∈ Ū p(x) • p G (x) p(x) x∈ Ū p(x)   = -p( Ū) • log p G ( Ū) p( Ū) ⩾ -O(ε 2 / log(1/ε)) • log 1 ε 2 / log(1/ε) ⩾ -O(ε 2 ),where we use monotonicity of -x log 1x and the fact that p G ( Ū) ⩽ 1 in the second last inequality.Proof of Lemma 3.4. By Claim 3.3 and the assumption that d KL (p∥p G ) ⩽ O(ε 2 ), we have thatEQUATION)By (18), we writeΩ(ε 2 ) -d KL (p U ∥p G;U ) ⩽ d KL (p U ∥q U ) -d KL (p U ∥p G;U ) = x∈U p(x) n i=1 log p(x i |π G i ) q(x i |π G i ) = x∈U p(x) n i=1 log p(x i , π G i ) q(x i , π G i ) q(π G i ) p(π G i ) ⩽ x∈U p(x) n i=1 log p(x i , π G i ) q(x i , π G i ) - n i=1 log q(π G i ) p(π G i ) = x∈ n i=1 Ai p(x) n i=1 log p(x i , π G i ) q(x i , π G i ) - n i=1 log q(π G i ) p(π G i ) = n i=1 x:xi(x),π G i (x)∈A ′ i p(x) log p(x i , π G i ) q(x i , π G i ) -log q(π G i ) p(π G i ) = n i=1 (xi,π G i )∈A ′ i p(x i , π G i ) log p(x i , π G i ) q(x i , π G i ) -log q(π G i ) p(π G i ) = n i=1 d KL (p Xi,Π G i ;A ′ i ∥q Xi,Π G i ;A ′ i ) -d KL (p Π G i ;A ′ i ∥q Π G i ;A ′ i ) n i=1 d KL (p Xi,Π G i ;A ′ i ∥q Xi,Π G i ;A ′ i ) ⩾ Ω(ε 2 ) + n i=1 d KL (p Π G i ;A ′ i ∥q Π G i ;A ′ i ). d KL (p Π G i ; Ā′ i ∥q Π G i ; Ā′ i ) ⩾ -p Π G i ( Ā′ i ) • log q Π G i ( Ā′ i ) p Π G i ( Ā′ i ) ⩾ O(ε 2 /n).And we can conclude by rearranging:n i=1 d KL (p Xi,Π G i ;A ′ i ∥q Xi,Π G i ;A ′ i ) ⩾ Ω(ε 2 )Lemma 2.6. With fewer than c 3 • √ k/ε samples from p, no tester can distinguish between p = q and |H(p) -H(q)| ⩾ ε with probability higher than 2/3, where c 3 > 0 is an absolute constant.Proof of Lemma 2.6. This follows from the standard uniformity testing lower bound [Pan08] , which provides a lower bound of Ω( √ k/η 2 ): there exists a family of distributions that are hard to distinguish from uniform u k , using fewer than c 1 • √ k/η samples. Let k be an even number; the construction is by taking θ = {-1, 1} k/2 uniformly at random, and letting, for every i ∈ [k/2],p no θ (2i) = 1 + θ i • η k , p no θ (2i + 1) = 1 -θ i • η k .We can verify that for any θ:|H(p no θ ) -H(u k )| = log k - k 2 1 + η k log 1 + η k + 1 -η k log 1 -η k = Θ(η 2 ) Setting η = ε 2 yields the lower bound of Ω √ k ε .Lemma 2.7. With fewer than c 4 • log 2 k/ε 2 samples from p, no tester can distinguish between p = q and |H(p) -H(q)| ⩾ ε with probability higher than 2/3, where c 4 > 0 is an absolute constant.Proof of Lemma 2.7. Following [WY16, B.2 Proof of Proposition 2], we look at the same construction but with different parameters ε ′ = ε log(2(k-1)) :p = 1 3(k -1) , . . . , 1 3(k -1) , 2 3 , q = 1 + ε ′ 3(k -1) , . . . , 1 + ε ′ 3(k -1) , 2 -ε ′ 3 . One can check that H(q) -H(p) ⩾ 1 3 log(2(k -1))ε ′ -ε ′ 2 = Ω(ε).Moreover, direct calculation of the (squared) Hellinger distance shows thatd H (p, q) 2 = Θ(ε ′2 ) = Θ ε 2 log 2 kwhich implies that p and q cannot be distinguished with fewer than c 4log 2 k ε 2 samples [BY02, Theo- rem 4.7]. E Sketch proof of O √ k log log log(k/ε) ε + log 2 (k) ε 2upper bound.We will rely the following inequality for compression, both via Jensen's inequality,EQUATIONas log(x) is concave and log 1 x is convex.i∈∆ p i log 1 p i ⩾ i∈∆ p i log i∈∆ p i i∈∆ p 2 i ⩾ i∈∆ p i log 1 i∈∆ p i ,suggesting that if we merge elements of ∆ into one, then we will lose a log(|∆|) factor of the entropy. By merging enough elements, we can then reduce this problem into the first case, where elements have large enough mass in each location.Claim E.1. Let S ⊆ [k], if p(S) -q(S) > -η, then |d KL (p S ∥q S )| ⩾ η ⇒ d KL (p S ∥q S ) ⩾ η. Proof. If |d KL (p S ∥q S )| ⩾ η, then d KL (p S ∥q S ) ⩾ η or d KL (p S ∥q S ) ⩽ -η.We will rule out the second case, using that logEQUATIONThus, we cannot have d KL (p S ∥q S ) ⩽ -η and so d KL (p S ∥q S ) ⩾ η.We use the same idea as our first upper bound but choose a series of thresholds. LetS 3 := i ∈ [k]|q i ⩾ Ω ε k log log log(k/ε) ; S 2 = i ∈ [k]|Ω ε k log log(k/ε) ⩽ q i ⩽ O ε k log log log(k/ε) ; S 1 = i ∈ [k]|Ω ε k log(k/ε) ⩽ q i ⩽ O ε k log log(k/ε) .The following calculation ensuesΩ(ε) ⩽ |H(p A ) -H(q A )| ⩽ 3 i=1 d KL (p Si , q Si ) + i∈A (p i -q i ) log 1 q i ⩽ 3 i=1 |d KL (p Si , q Si )| + i∈A (p i -q i ) log 1 q i .We have that one of the four terms will be at leastΩ(ε/4). If it is i∈A (p i -q i ) log 1 q i ⩾ Ω(ε), which is testable with O log 2 (k) ε 2samples using arguments from proof of Theorem 2.1. If it is |d KL (p Si , q Si )| ⩾ Ω(ε), for i = 1, 2, 3. We have the following: Case S 3 . Suppose |d KL (p S3 , q S3 )| ⩾ Ω(ε). We will check whether p(S 3 ) ⩾ Ω ε log log log(k/ε) , if not, we can reject. We proceed assuming the inequality holds. Note that|p(S 3 ) -q(S 3 )| = |p(S 3 ) -q(S 3 )| ⩽ O ε log log log(k/ε) .Thus, p(S 3 ) -q(S 3 ) > -O ε log log log(k/ε) , and by Claim E.1, we have that d KL (p S3 , q S3 ) ⩾ Ω(ε). Using (4), we then have that d χ 2 (p S3 , q S3 ) ⩾ Ω(ε). Using Lemma 2.4 (setting suffices to check between the case that d χ 2 (p S3 , q S3 ) ⩾ Ω(ε) and p S3 = q S3 . Case S 2 . Suppose |d KL (p S2 , q S2 )| ⩾ Ω(ε). We will check whetherα = OΩ ε log log(k/ε) ⩽ p(S 2 ) ⩽ O ε log log log(k/ε) ,if not, we will reject. We proceed assuming the inequality holds. Now, recall that the main bottleneck of the χ 2 tester analyzed in Lemma 2.4 is due to the minimum probability α = min i∈S2 q i (increasing this would decrease the sample complexity). Our main idea here is to increase α by merging a suitable number (log log(k/ε) in this case) of elements into one single bin to form a new distribution to test. Denote ∆ j where j ∈ |S2| log log(k/ε) and j ∆ j = S 2 . We will subsequently treat every elements in ∆ j as 1 bin in the new distribution, calling it p ∆ , q ∆ and denote p(∆ j ), q(∆ j ) as mass on ∆ j , where p(∆ j ) = i∈∆j p i . This gives us the following:i. q(∆ j ) ⩾ Ω ε k log log(k/ε) • |∆ j | ⩾ Ω ε k ; the domain size is |S2| minj |∆j | ⩽ O k log log(k/ε) . ii. j p(∆ j ) = p(S 2 ) ⩽ O ε log log log(k/ε) and j q(∆ j ) = q(S 2 ) ⩽ O ε log log log(k/ε) .iii. Their entropy difference is preserved, which we will prove next:j p(∆ j ) log 1 p(∆ j ) - j q(∆ j ) log 1 q(∆ j )⩾ Ω(ε).F Derivation for KL decompositiond KL (p, p G ) = x∈{0,1} n p(x) log p(x) p G (x) = x∈{0,1} n p(x) log n i=1 p(x i |π i ) n i=1 p G (x i |π G i ) = x∈{0,1} n p(x) log n i=1 p(x i |π i ) -p(x) log n i=1 p G (x i |π G i ) = x∈{0,1} n n i=1 p(x) log(p(x i |π i )) -p(x) log(p G (x i |π G i )) = n i=1 x∈{0,1} n p(x) log(p(x i |π i )) -p(x) log(p G (x i |π G i )) = n i=1   xi,πi∈Xi,Πi p(x i , π i ) log(p(x i |π i ))   -   xi,πi∈Xi,Π G i p(x i , π G i ) log(p G (x i |π G i ))   = n i=1 H(p Xi,Π G i |p Π G i ) -H(p Xi,Πi |p Πi ),where π i , Π i denote the parents of x i , X i in Bayes net p (a set of random variables or their domain); and π G i , Π G i as the parents defined by G. p G is the projection of p unto G as defined by Definition 3.2. It is not hard to see that the derivation extends beyond the case of hypercube, {0, 1} n .• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.All logarithms in the paper are natural (e as base).Our algorithm actually provides a stronger guarantee, with respect to Hellinger distance, which implies the TV result.While the sample complexity of the algorithm is not explicitly stated in their proof, inspection of their argument yields this bound.The lower bound [BCY22, Theorem 4.1] only holds under the sparse regime: d ≪ log n.We note that what they refer to as "identity testing" is different from ours (and the standard) use of the term: in their setting, the reference distribution is replaced with sample access to the distribution (this is commonly referred to as "closeness testing").L = {Xσ 1 , . . . , Xσ d+1 } ⊂ {X1, . . . , Xn}; pL = pX σ 1 ,...,Xσ d+1 is the marginalization of X on L.One can remove the assumption that p( Ā) + q( Ā) ⩽ 4τ , at the cost of a slightly worse constant.Here, x is the DAG's assignment of parents and child; and f1(x) (resp. f2(x)) is the associated KLdivergence (also called score of the DAG in the literature, which measures the how well DAG models the true Bayes net) between p (resp. q) and x. Since we are in the realizable setting, the optimal is in fact 0.In the case of pi = 0, we still have pi log p i q i ⩾ pi -qi.One can remove the assumption that p( Ā) + q( Ā) ⩽ 4τ , at the cost of a slightly worse constant.In the case of pi = 0, we still have pi log p i q i ⩾ pi -qi. 


Decision: This manuscript proposes a new property testing problem called the entropy testing and obtains the tight sample complexity for this task. Surprisingly, the entropy testing can be used as a subroutine in testing Bayesian networks and lead to an improved sample complexity over [Canonne, Diakonikolas, Kane, and Stewart, 2020] and the removal of an unnecessary condition. The reviewers agree that the new problem is fundamental, the analysis is sound (originally one reviewer spotted an error, but the rebuttal clears the correctness concern), and the application to testing Bayesian networks is clever. The reviewer also raise some concerns, e.g. the overall algorithm is not very neat (needs to distinguish into cases) and hardly practical, which are not so important given the theoretical nature of this work. Overall I recommend acceptance.

Reviews: review: paper_summary: paper_summary: This paper studies the problem of testing a null hypothesis against alternatives that are far in Shannon entropy. They provide information-theoretic minimax lower bounds that they also achieve up to polylogarithmic factors. They then apply these results to Bayes net testing.
strength_weakness: strength_weakness: * The lemmas in section 2.2 are written somewhat informally, but they read as if they are making an instance-dependent claim (e.g., for any $q$, it is impossible to test with fewer than $c_3 \sqrt{k}/\varepsilon$). However, the lemmas seem to actually be minimax claims, as the two lower bounds are obtained by different single hard distributions.
* There is no discussion of proof strategy or intuition in section 2.2 so the results feel like they come from no where (the results of lemma 2.6 were discussed in section 1.2, but not lemma 2.7 as far as I can tell).
* The fact that the two lower bounds arise from such different distributions indicates the possibility of a tighter instance-dependent quantity. This sort of bound could help illuminate the structure of this testing problem.
questions: questions: * In the display after line 195, I don’t quite follow how the last inequality holds. In particular, where does the $\log \log (k/\varepsilon)$ factor go?
* Between equations (13) and (14) in the display following line 416, $d_{TV}(p, q)$ is bounded above by $\sqrt{\frac{\varepsilon}{8}} + 4\tau$, which is then bounded above by a constant. Isn’t it easier to just directly (and trivially) bound $d_{TV}(p, q)$ by 1? This would also remove the requirement (as far as I can tell) of assuming $p(\bar{A}) + q(\bar{A}) \leq 4\tau$.

Minor comments
* In line 108, in the phrase “as just mentioned, when its TV distance…” what is “it” referring to?
* In line 163, is the partial Hellinger distance missing a power of 2 in the summand?
* In lines 414-416, the sentence “We continue based on the premise…” is redundant, as the premises given are already assumed as conditions in the claim.
* In the display following line 416, maybe good to mention that the Poissonization trick is used there
* In line 434, “When $d_{\chi^2}(p_{\mathcal{A}}, q_{\mathcal{A}}) \geq \varepsilon$” is written twice.
* In the display following line 446, should $\theta \cdot \eta$ instead be $\theta_i \cdot \eta$?Otherwise I don’t see how the equation can make sense ($\theta$ is a vector, $\eta$ is a scalar, and the output of the operation needs to be a scalar).
limitations: limitations: They have addressed their limitations.
paper_summary: paper_summary: * This work focuses on the problem of Entropy identity testing, i.e., whether for two distributions $p, q$ if $p = q$ or $|H(p) - H(q)| > \epsilon $ given samples from unknown  $p$ and complete description of $q$ over a domain of size $k$.

* The authors show that the sample complexity of entropy identity testing is $ \sqrt{k \log(k/\epsilon )} /\epsilon + \log^2(k)/\epsilon^2 $. This is an interesting observation since for identity testing problems, the sample complexity is usually $O(\sqrt{k}/\epsilon^2)$, but now it gets split into two terms with $\epsilon^2$ appearing below the shorter term when $k$ is exponentially large. 

* Using this testing procedure as a subroutine, this results leads to better testing procedure for the problem of Identity testing for Bayesian networks over {0,1}$^n$ and the authors (as mentioned in abstract) obtain a better bound for this problem improving it from $O(2^{d/2} n^2 /\epsilon^4 )$ in [CDKS20] to $O(2^{d/2} n \epsilon^2 + n^2/\epsilon^4)$.  

Roughly speaking, the algorithm for entropy identity testing divides the space into two regions:
1) Where $q$ has low probability: just test whether $\hat{p}$ attains large values in this region. if so, then reject.
2) Where $q$ has high probability: use the algorithm of [DKW18] to efficiently test whether $d_{KL}(p||q) \geq \epsilon$.
strength_weakness: strength_weakness: * The algorithm/testing-procedure, although interesting from a theoretical viewpoint, is hardly practical as it involves so many individual tests and just too many weird (but tunable) constants. A "neat algorithm" would have been even more useful from a practical viewpoint, but overall the work is interesting and may serve as a nice starting point for designing a ``neat" algorithm. 

Other minor points: 
* The (possible) applications of either of the two testing problems, especially the identity testing of degree-d Bayes can be mentioned.

* Lines 142-143 can be slightly rephrased ``directly extending this argument does not work" causes some confusion.

* In line 145, please provide a reference/explanation for where the factor $\epsilon / \sqrt{n}$ comes from. If I am not wrong, it probably comes from [DP16 Theorem 4.2]
questions: questions: As far as the goal of getting a better bound for identity testing for Bayes net is concerned, won't Reyni Entropy identity testing might be a better choice (especially of order $2$), which has $\sqrt{k}$ sample complexity and is also much simpler to estimate and might have even better sample complexity for identity testing.
limitations: limitations: Work has essentially no negative societal impact. A justification for the limitations question in the checklist can be added as it could help the readers directly without searching at different places.
paper_summary: paper_summary: The authors consider the entropy identity testing problem for two discrete distributions $p$ and $q$, which is a hypothesis test between $p=q$ and $|H(p) - H(q)| \geq \epsilon$. They propose an algorithm for this problem that is near-optimal in terms of the sample complexity. The main ideas of the algorithm are 1) ignoring a set with small probability with respect to $q$ and 2) bounding the entropy difference by KL-divergence. The result is applied to identity testing problem for Bayes nets.
strength_weakness: strength_weakness: The importance of the problem is not discussed much.
The writing is not clear with several errors.
questions: questions: 1) It is hard to see the significance of the entropy identity testing. 
Heuristically, the alternative hypothesis $|H(p) - H(q)| > \epsilon$ is too much different from the null, since it is possible that $p \neq q$ but $H(p) =H(q)$,
and thus the entropy identity testing might be essentially easier than the other testing problems based on "distances" such as KL-divergence or Hellinger distance.

2) I think the manuscript should be revised for clarity, since it contains too many typos and small errors. Below are a few examples.
- In Abstract, $k$ is not defined.
- In line 131, what is $\leftarrow$? Also, if $\bar{A}$ is the complement of $A$, then the equality should be removed from $q_i \leq \tau/k$.
- In the equation below line 134, $p(\bar{A}) = O(\tau)$ does not imply the second inequality.
- In line 182, the semicolon seems to be a typo.
- In Algorithm 1, what is $N_i$?
- In line 200 and line 202, "Algorithm 4" should be "Algorithm 1".
- In Algorithm 2, what is S_1?
limitations: limitations: The work does not seem to have potential negative societal impact.
paper_summary: paper_summary: In this paper, the authors first find the complexity upper and lower bound for the entropy identity testing problem: given sample access to a distribution $p$ and a fully described distribution $q$, the tester needs do distinguish between two hypotheses $p=q$ and $|H(p)-H)(q)|\geq \epsilon$. Based on this, the authors find the sample complexity upper bound for the problem of identity testing for in-degree-$d$ $n$-dimensional Bayesian networks. This bound improves an existing bound by Canonne et al. (2020) without using an additional assumption that the structure of unknown Bayes net is a subset of that of the reference one.
strength_weakness: strength_weakness: Some key proofs look not correct, and some notations are not defined. Please see the questions below.
questions: questions: + What is the definition of $\mbox{Poi}(m)$ in Claim 2.3?
+ Proof of Theorem 2.1: The first inequality between lines 195 and 196 looks not correct since the function $\log \frac{1}{x}$ is convex. An application of the Jensen's inequality should give $H(q_{\bar{A}}) \geq q(\bar{A}) \log \frac{|\bar{A}|}{q(\bar{A})}$ (not $\leq$ as in your paper). 
+ For the case $p=q$, from the line 206, we only infer that $Z_2<2m_2 \epsilon$ with probability $>3/4$. What happens in Algorithm 1 if $2m_2 \epsilon> Z_2\geq \frac{1}{16}m_2 \epsilon$?
+  In the last equations in Appendix A (Derivation of Line 4 in Algorithm 1), you mentioned that you use Chernoff bound $\mathbf{P}(\hat{p}'(\bar{A})\leq (1-1/3)p(\bar{A}))\leq \exp\big(-\frac{m_1 p(\bar{A})}{18}\big)$. Would you please explain this more? It seems to me that you need use the union bound before using the Chernoff bound, hence we need to multiply $|\bar{A}|$ in the RHS of the above inequality.
+ In the statement of Lemma 2.4, $\mbox{Var}[Z_2]\leq O(m_2^2 \epsilon^2)$ and $\mbox{Var}[Z_2] \leq O(\mathbf{E}[Z_2]^2)$. However, in the proof (from line 204 to line 223), you use the exact constants. 
+ In line 218, you mention that you use Claim 2.3 to derive some results. How do you justify that $d_{\chi^2}(p_A,q_A)\leq \epsilon/8$ to apply this claim?
limitations: limitations: This is a theoretical research paper, hence the negative society impact of this work is not direct.

Comments: comment: Getting back to this, we would like to know if the reviewer is satisfied with our answers addressing the correctness doubts they raised; if so, whether they would reflect this in their score, which currently indicates "a paper with technical flaws".
Thanks for clarifying! Indeed, our null hypothesis is more stringent (smaller set) than the one you mention -- first, in order to have a non-degenerate null hypothesis, but more importantly as this is the "cleanest" formulation for our application. However, relaxing the null to $H(p)=H(q)$ would make the sample complexity of the problem much higher, basically as hard as entropy estimation: 
$$
\Theta\left(\frac{k}{\varepsilon\log k} + \frac{\log^2 k}{\varepsilon^2}\right)
$$
(This is because the lower bounds from Wu and Yang (2016) still apply via a reduction, while their upper bound does allow to solve the problem.)
Thank you for your response. My questions have been clarified and I’ll maintain my current score.
Thanks for the response. As my questions have been adequately addressed, and I did not identify any major flaws or concerns with the approach, I maintain my current rating, and I believe the paper meets the necessary standards for acceptance.
Thank you for your answer. I might rephrase my first question as follows. If you use a 'true' distance then the null $p=q$ is equivalent to $d(p, q)=0$, hence the testing is about whether $d(p, q)=0$ vs. $d(p, q)>\varepsilon$, which is a usual hypothesis test that concerns a single parameter $d(p, q)$. However, in this work, the entropy identity testing is not about whether $|H(p) - H(q)| = 0$ vs. $|H(p) - H(q)| >\varepsilon$, since $p=q$ is essentially different from $|H(p) - H(q)| = 0$. Anyhow, I can see your point that the main motivation of the work was to consider Bayesian networks.