Entropy testing and its application to testing Bayesian networks
Authors: Clement Louis Canonne
Qiping Yang
Venue: NeurIPS 2024 poster (2024)
Keywords: bayesian networks
distribution testing
shannon entropy
graphical models
hypothesis testing
Primary area: learning_theory

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}( {2^{d / 2} n^{3/2}}/{\varepsilon^2} + {n^2}/{\varepsilon^4} )$. 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.

Entropy testing and its application to testing Bayesian networks
Clément Canonne University of Sydney
Joy Qiping Yang University of Sydney 1yan62380uni.aydle .sydney. edu. au
clement, wwwonne@sydney....ooooooome.aa. edu. au
Abstract
This paper studies the problem of entropy identity testing: given sample access to a distribution p and fully described distribution (both discrete distributions over a domain of size k), and the promise that either p = q or (H H()) where H.)) denotes the Shannon entropy, a tester needs to distinguish between the two cases with high probability. We establish near-optimal sample com- plexity bound of Ō(Vk/e 1/2²) for this problem, and show how to apply the problem of identity testing for in-degree-d n-dimensional Bayesian networks, obtaining an upper bound of ((24/2 /2² + n²/ /s)) This improves on the sample complexity bound of n224/2n2 /Et) from [CDKS20], which required additional assumption on the structure of the (unknown) Bayesian network.
Introduction
Entropy is fundamental information theory notion, which quantifies the amount of "uncertainty" 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 discrete random variable (or, equiva- lently, its probability distribution) from samples has naturally emerged, starting (in Computer Sei- ence) with the work of [BDKR02] which considered multiplicatiiv approximations. Additive ap- proximation of the entropy (within +G) was then considered in series of papers [VV1la, VV11b, VV13, 15,, ADOS17J, culminating with the work of [WY16], which establishes the optimal sample complexity, 6 o
log² k) where k > the domain size.
While the resulting sample complexity is sublinear in the domain size k, it is only by mere logarithmic factor. In some settings, paying this near-linear dependence the amount data nec- essary impractical, typically in the large-domain regime (e.g., for high-dimensiooal data, where is exponential the dimension); moreover, may even be unnecessary. Specifically, one may not be concerned much about the (approximate) value of the entropy of distribution, but rather about whether is above a threshold, or differs from that of a given purported model.
It is this latter task we introduce and consider in work, which be seen as variant of the standard identity testing question from distribution testing: given reference known hypothesis distribution q domain of size k. and i.i.d. samples from unknown distribution what is the sample complexity testing whether p is equal to q, or their entropies differ significantly? And, erucially, is this testing task more sample-efficiett than that of estimating Hp))?
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Entropy Identity testing: Given a reference distribution g. parameter & > 0, and samples from an unknown p. what is the cost of deciding (with high probability) whether p = vs. Hp)) H()) > E, with correct probability at least 2/3?
Note that in the case where is the uniform distribution over the domain, this task is equivalent to distinguishing between H (p) log k and (p) < log k c.
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 /
Moreover, this is nearly tight: SI( S1(Vk// + log* k//²²) samples 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 @(vk/=²) (see Section 1.1).
Identity testing for Bayesian networks. As an application of Theorem 1.1, we derive 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):'
Application:
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)"),
takes Ô 24/2 +
n2
samples from p, and distinguishes between p = q and drv (rvv(p.)) q) 2 E.
Prior to this, the best known sample complexity upper bound for this task [CDKS20] was quadrati- cally worse in both and E, 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 > log(n/e), 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.
1.1 Related work
As previously discussed, entropy estimation has received considerable amount of interest from computer scientists, information theorists and statisticians [BDKRO2, PanO4, HJW15a, WY16]. En- tropy is also a key example of symmetric property (invariant to relabeling of the domain) [VVIla, VV 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 stud- ied [AOST17].
Over the years, sample complexity of identity testing for discrete distribution has been intensively studied and essentially settled [Pan08, OFF+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 O( //////>>) 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/s); [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
Our algorithm actually provides a stronger guarantce, with respect to Hellinger distance, which implics the TV result drv q) S dudn(p, q) for any two distributions p. q.
2

---

the topological ordering of the two Bayes nets the same, and shows that under this assumption O(24/2n2 /E*) samples are sufficient. [CDKS20, Theorem 17] makes the further stringent restric- tion 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 O, 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 II implies that, under the assumption that and share the same factorization structure (i.e.. their associated DAGS are the same one is subgraph of the other), then this problem is solvable in Ô (24/2 n//e) samples. While this latter sample complexity is near-optimal (in some regime"), ), in view of the Q (24/2n/E²) lower bound obtained in [BCY22, Theorem I, the factorization struc- ture 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
baseline). It is known [CDKS20]) that learning degree-d Bayes nets can be done with Ó(2'n/EE) samples, without any structural assumptions. Our testing result improves on this sample complexity as long as n²/e"" < n2n/ and 23/2 < n i.e., for d > log(n/s); moreover, it is worth noting that the known learning algorithms are computationally inefficient (running in time n ((dn) via an enumeration of all possible underlying graph structures [CDKS20, BGMV20J), and this is believed to be inherent [CHM04]. In contrast, our algorithm runs in time poly(n 1/e).
1.2 Techniques overview
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 drv (p, 4) < 1/2, then (H) - Hgg) & drv(p.q) log (rv [CK11, Lemma 2.7J.* This gives an up- per bound of O VK (k/e))))))) which is already better than the sample complexity of estimation: 0 clogk + log? k for the parameter k. However, it 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, actu- ally only have entropy log - O(s²). The D D(VK/s") uniformity testing lower bound from these hard instances thus only implies an 22 ((Vk/s) 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 around (vv)) its entropy difference to it is only (es) (giving an Q ((VR/e) lower bound). Moreover, this is not coincidence: when the reference distribution g is uniform, we are able to get a matching upper bound using [DKW18, Algorithm 1], upon noticing that
(1) which implies dkr. (pllu)) u log k H(p) > E, where uy is the uniform distribution on [k] and dx1, denotes the Kullback-Leibler divergence. Interestingly, a completely different hard instance, against very much non-uniform reference distribution, does yield the second term of our lower bound, 2(log* k/e²).
((p) = log h: (pl(pllux).
Inspired by these two different lower bounds, we can generalize (1) by defining A as the set of "not too small probability elements under g", and then observing (looking ahead, using the inequality (7)) that
1
H(PA) H(ga)) < (Pallla)))))
Ep. q:) log PEA
(2)
qi
where H (P.) 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 rinht-hand-side
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.
All logarithms in the paper natural (c as base).
3

---

is large. The name of the game now is (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; qi e 2 (f.), we can adapt and use an algorithm of [DKW18] to efficiently test (pl(g) 2 E vs. p= q. In addition, if log(1/g.) 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 di & f. Indeed, the impact on entropy is at most O(T log( (K/T) if we are to remove regions with at most ((T) 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 7/k masses, where
log(k/e}
The problem then becomes to check if p puts more than 100r mass in A = {i E [R]] : 9: < </K), which costs ((1/r) = O(log(k/e)/s; samples. If it does, then it cannot be the case that p q we can reject. After this stage, both p(A)) ((A) & O(r). To move forward, we need to check the influence on entropy: H (p) and (g). By Jensen's 's inequality and monotonicity of f(x) x log 1
when r < 2 we have
Ep: pi log 1
k p(A)
& log k
< p(A) log
AEA
Therefore, the impact on entropy will be at most 0 (T log 4). Setting T kog() this becomes Oe)), which gives us the room to check if (P(A)) (pA)) 100g or P.A QA-
Testing Bayesian networks. Similar to [DP16, Theorem 4.2], the identity testing algorithm is straight-forward: check all every E [m]] if Px. ny or is one of them is far apart, where q is Markov with respect to G' (q factorizes according the DAG G). The main technical part is to show that the distance is "subaddititve" when and q share no common structure, but are close to sharing common factorization structure (this can be thought of as a relaxtion of [DP16, Theorem 4.2]; refer to Lemma 3.3 for details). As a consequence of "subadditivity". if p and q are far in distributional distance (differed from [DP16], our work opted to test in KL divergence restricted on subsets with large enough density), then it would imply that one of the local distance between p and q is sufficiently large. This allows to reduce from global testing to local testing.
Another key aspect checking whether p and q are close to sharing common structure. More specifically, whether dk1. (plPpG) is small, where pG is the projection of p unto q's DAG G. Here, we establish a connection between entropy closeness and structure closeness. particular, we show that if every local entropy (involving subsets of size d + 1, where d is the bound maximum in-degree) between p and q is close, then this means that they must approximately share the same structure (see Lemma 3.4). The intuition behind the connection is that if all tests pass, then we can conclude that and are close in local entropy and thereafter, we can utilize entropy of q to learn the graphical structure IKCG+23) of (which uses additional samples).
At high level, our algorithm first check p and q roughly share the same structure via a proxy check of local entropy tests. If all local entropy tests pass, then we can show that there exists i E [r]] such that local KL restricted on subset with large enough mass is greater than S A subsequent identity test with x" "-estt [DKW18] suffice.
Preliminaries and notation. The (Shannon) entropy H of discrete distribution p supported on [k] is given by:
H(p)
Σ
pe log ps.
SE|R
The conditional entropy Hpx pv) for X supported on X, and Y on V, defined by the joint distribution px,,, can be written as
p(z,v) v) plu)
[px ppr) -- Σ p(z, 8) log
=
(3)
xEX,
'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 "closeness testing")..

---

We adopt the entropy notation for sub-probability vector H(gA) Died 9 log q. Throughout this paper, we will e as base of the log and of the entropy. We will use for variable assignment. We adopt the standard O()). S2() and (-) asymptotic notation and u hide any polyl polylogarithmic factors the argument. We will use various metries or divergences Kullback- -Liblee (dKL), Hellinger (dμ), chi-squared (dya), and total variation (drv). We denote PA as restricting p onto the elements A, and we denote distributional distances restricting on A
probability distributions:
as follows: (PA, QA) ) = EiEA Pi log P; dH(PA, = -े V EiEA (VPi - væ:)² For a set
"." A, write p(A) EiEAPi Pt- We also have the following inequality [DKW18, Proposition 1]:
dTv(PA V2dH(PAMAA) &
Σ(a (q: p.) (PA. (ee(pA,ga)
(4)
A distribution p supported over the hypercube (0. 1)th is Bayesian network if its probability mass function satisfies the factorization associated with G, a directed acyelic graph (DAG):
p(11," .M , = II p(x,
(5)
and II; is the set of parents of X; in G; and say that is Markov with respect to DAG G. In section 3, slightly abusing notation, we use pG to denote a projection of a Bayes net p to a DAG G (which it may or may not be Markov with respect see Definition 3.2). We work in the Poissonized setting (see, e.g., [Can22, Appendix CJ) - instead of drawing N samples directly from p, we draw Y ~ Poi(N) samples from p. where Poi(N) denotes the random variable distributed the Poisson distribution with parameter N. The Poissonized and usual sampling settings are equivalent for constant probability of failure, up (small) multiplicative factor in the sample complexity.
2
Near-optimal entropy testing
We prove Theorem 1.1, establishing the sample complexity upper and lower bounds separately,
2.1 An O logg(///)
log (k)
upper bound
We will prove the following theorem:
Theorem 2.1. There is algorithm (Algorithm 1) which, given samples from discrete distri- bution p. the full description of a reference distribution both over [k], and parameter e > O, distinguishes between p q and Hp))) H(4) > with probahility least 2/3, as long as
Vk /llg((//))
log? (k)
n 2
c2
and 02 for some absolute constants C1, C2 O. Moreover, the algorithm runs in time linear in the number of samples n and the domain size k.
The proof will rely the two following claims and Lemma 2.4, which is straightforward ex- tension of [DKW18, Lemma 2]. Their proofs are deferred to Appendix B. Throughout, we let
16log(k/e)* and A = { E [k]] q: 2 } in Algorithm 1.
Claim 2.2. Let A be any set such that p(A) < e/2. Then, H((A) H(gA) 2 6, must have
(i) dKI((P (194) > or (ii) Eie ④)) log +
Claim 2.3. Let be the empirical estimator for an unknown discrete distribution supported on
[k], based on Poi(m) samples, where m = θ 1og²
assume that d (pA, < s/8 and
p(AA + ((A) < 45 = "ogi5/z5" then
1
1
Pr
Σ (pr P.) log ieA
c
qi
8
100"
'One remove the assumption that p(AA) g(A))
4r, at the cost of slightly constant.
5

---

Algorithm Entropy identity testing
Require: Sample access to p and full description of q. both over [k]; accuracy parameter e.
1: Set Tog(kk/e and A := {i E [A] 9: }
2: Take m = 48/T samples from p and compute the empirical p².
3: Compute Z1 p' (AA).
4: if Z1 > 2r then return reject
> Early rejection.
> Ny: the empirical count among samples of the i-th element.
5: Let m2 65536
Draw Poi(ma) samples from p and compute
(N:
Nq.)² - N;
Z2
Nq.
SEA
6: if Z2 > 16 m22 then return reject
(l)
7: Let mg 140800
8: Draw Poi(ms) samples from compute the empirical ý; let Z3 + E, 4:) log
9: if L3 & then return reject
10: return accept
vK Lemma 2.4. Let A= E [k] qi > a}. Let m2 > 16384 max V as = be the number of
samples used to compute Zz. Then T Z2] mzdy3 (PA: 9A). Moreover, dx (PA: QA) < 3. then
Var[Zz] & m25) df QA) > E, then Var Zz] < O(E[Z2)²)
Proof of Theorem 2.1. We prove the statement by analyzing Algorithm 1. First, note that excluding the of A (elements with small mass), can change the value of (q) by at most e/8: indeed, by Jensen's inequality (f(x) = log x is concave) and r loo being monotonically increasing in (0, 1/c).
A ((A)
& log k 16log(k/e)
16k
1
H(gı) = Σ q: log
< ((A log
log
<
4s
T
E//lo(///s)
8
SEA
when + 1/e.. Similarly, if p(AA) < 3r, we have that H(Pa) < c.. Therefore,
E << Hp) - H()) < [Н(μ)) H(qA)l + (PA) - H(qa)l
< [H(PA) H(dA)) + [H(x)) + (H(x))
[H(AA) - H((AA) f...
For Line 4, we prove the following: with probability at least 99/100, 2, > 2T, then p(AA) > T; and if Zi < 2T, then p(AA) 3r (this is 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 of Algorithm 1. We conclude from the above that
i. A still has sufficient entropy gap to on: [IA) ((gA)) f.c.
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(.A) < 3r.
Completeness: when
We have that (pA, qA) O, and via Lemma 2.4, we know that E[Zg] and Var [Zz] I mžee. By Chebyshev's inequality,
<
1
1 4
Pr Zz
E[Z2]| > 2 Varl [z
Var
< 4'
and so Pr|Zz >
m2c + E[Z2]]
<
32
and have Pr|Zz > 16 m & 1

---

140800 (k)
On the other hand, by Claim 2.3, setting mg least 99/100,
have that with probability
Z3 = Σ (pi - q:) log
Σ (f: - p.) log 1
1 < g
=
SEA
ieA
2 Therefore, with probability at least 1 1 100
73
z.b the tester will accept.
100
Soundness: when (p) (g)] > E. If p(A) > 3r then ((A) >> 2T with probability 99/100,
and the algorithm will output Reject. We proceed assuming p(A) & 3r and recall Item ii. from before, we have (PA) (qA))
> ze. By Claim 2.2, we have that either dRI (PA, QA) >
de IEiEA(i - 9.) log (1/4:)
> J. We apply Lemma 2.4, setting a = T/k and m2 2
If (dKL(PAllal > te, with (4) and exp(3/2) < k/e, we have
E x 3r + (pA, &
E( p.) + (PA: & dy=(pA: gA),
iEA
which by Lemma 2.4, and our setting of m2 and a, implies Var[Z2] < () and B[Z2] = m2- dx=(pA, 9A) > mm2e. By Chebyshev,
1
Pr Z2 E[Zz]] > 2V Z2r
< 4 and so Pr|Zz <
m2el < 4.
16
On the other hand, if it is the case that EEEA (P: 4.) log (1/4)]
> 1.. by Claim 2.3, setting
m3 140800 log2 /c2 with probability at least 99/100,
1
Σ Ps log
q: log
9i
qi
Σ (ps (x)
log
+
Σ
(pi - 4))
log
qi
1
1
Σ (pi 4:) log
+
8
qi
We have that Zz E.:
q:) log
fee and thus with probability at least 1 1- 1
73
100
100
the following will happen, the tester will reject: either p(A) > 3r, and rejected at Line 4 of Algorithm 4, or it passes and p(A) & 37 and
Ze > ms or Ze > ge,
and will be rejected. This concludes the proof.
We note that we can slightly improve the sample complexity of Theorem 1.1 (specif- ically, improving on the / (oo(((/)) term), at the price of a more complicated algorithm,, by adding thresholds 7' = log (e) 7"
Remark 2.5.
log (kg(k//)) and considering separately the elements in A' = {i qi E (r/k,-'/k) A" = fi groups, and "merging" each group to get "new" element with larger probability. For the sake of clarity, we defer this improvement to Appendix D.
/k]}; specifically, by grouping them in
2.2 An R(VK/E + log² k/E²) lower bound
The ((Vk/e + log² k/E²) 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.
7

---

Algorithm 2 Identity testing for bounded degree Bayes nets
Require: Sample access Bayes p. full description of Bayes net g, accuracy parameter e, in-degree d and dimension n.
24/2 ny 2 allg(n/c) dnn dllog
S1 +0
samples from p;
2: S2 00
24/2
(og(1/e) log n samples from p:
8
3:
for all I. E Na+1 U.2 do
No is all subsets of {0, 1]" with size & D. Entropy test on Pr and qr with accuracy e² //n.
4: Call Algorithm with PL. 91 and S
5: if Entropy test rejects then return reject
6: S3 +0
samples from and compute its empirical distribution p
5²
7:
for all E [n] do
8:
if ix (A,) 3 Q(=2/((22 (oonnnnnnoo/n)))) log(n/z))) then return reject
Check dPL AA Inxx), ش n 9:
or dKI, (KI.(xx,,nf;At 1xx, 0.
10: if i-th KL test says far then return reject
11:
return accept
b Accept if all tests pass.
Lemma 2.6. With fewer than cs - Vk/E samples from p. no tester can distinguish between p and (p) - H()l > E with probability higher than 2/3, where 03 > 0 is an absolute constant.
Lemma 2.7. With fewer than log k/e² samples from no tester can distinguish between and (p) - (4) 2 e with probability higher than 2/3, where C4 > 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 Bayes net q, Algorithm 2 takes
24/2 nd 3/2 logn- n. log(n/E) d logn
2/22
-log n
C
62
62
samples test between p q or du 9) > ME)), where C 0 is absolute constant. Moreover, the algorithm runs in time polynomial in nd and 1/E.
Before proceeding the analysis of our algorithm, we require the following definitions.
Definition 3.2. A projection of Bayes net p on {0, 1)" unto a DAG G is denoted pc. and is defined by its probability mass function (PMF) as follows:
PG(X X p(X, 119),
where II is the set parents of X; in G. Abusing the notation in the context of Bayesian networks, we refer to PX,.11, or PX, (Ii TT.) as the marginal distribution of p on the subset {X,, II.).
Denote == U._. A., where A, == ==f= (0, R (z, (x))
22- (n/e)
This gives us the property that marginalization over X, = I,, 11 = प. works nicely as we include elements only based on its local property (as long as qx, is large enough). And q is Markov w.r.t
G. We use (x,, m.) E A', where A {a' E (0, 1319 11 4x (x') > Ω p Let () E AC, we have that as long as (e(()),(())) = (a, B), then a E A, and vice versa, which means that
u - 10. (cr()), E AT}.
8

---

We will check if nf (At) 3 01=2/(12 O
log(n/e))) and reject early if true; this takes (og(la/))/)) log(n) samples for all tests to be correct via union bound. After passing this gx test, we can conclude that
p(u) E
p(x) & Ep(x) p(z)=
Σ Px Px (A4) & 0 n² log(n/8)
æEAA
z'EA'
where we marginalize over everything other than (X1, 11() in the third step.
Similarly, we can upper bound q(U) & no & O(=² ((=2/(n2 log(n/s))) Abusing the notation
slightly, we denote РG:4 as the distribution obtained by projecting onto G (which gives pc) and then restricting the distribution PG to take elements in U.
We will need the following Lemma 3.3 whose proof deferred to Appendix E.
Lemma 3.3. Suppose (p.9) > S){²)); (pllp))) & O(e²); p(l))
nlog(n//) Vi
[n)] ((A)) < i log(n/jj where Ai defined above, and q is Markov with respect G. then we have
S((E))
Therefore testing dKL (P... waaalllx..nm 19x over all suffices detect this case.
In addition, to connect entropy testing to Bayes net testing, will need the following Lemma 3.4, whose proof will deferred to Appendix E. And so we can show that all local entropies between Bayes nets p and q sufficiently close, then this implies that p must be close to q's DAG G and must also be close to p's DAG G'.
Lemma 3.4. Let p and q be two max in-degree-d Bayes nets supported on {0, 10" such that for every subset L S {X,,'.. Xn} 3noor of size d + 1, the following holds:
Hpr.) - H( &
Suppose is Markov wrr. G and 9 Markov w.r.t. G. Then we have that
(vlpp) & O(e²) and dxr, (xll(g))) < O
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 of size (dimension) d or d 1,
(2 2 n log((n)))/ dnn /n2
To guarantee the success of every tests employed in the algorithm, we increase the sample complex- ity of each test by an extra (llog(=+2)) = Odl n) factor to boost their success probability to 1 100n4eT (via standard majority vote technique), which will allow us use union bound over all tests there most n++ subsets with size d 1. For this step, the sample complexity will be
(2412 "ollln//lognn// dlog(n/s) o ((
dnn et
d llog
22
With this in hand, we will proceed with the analysis under the event that every entropy test performed is correct (which by the above argument happens with high probability). If distribution manages to pass all the entropy tests, must satisfy the following:
H(pr) H(gn)) < n
for every subset L of size d + 1 for the latter, and every subset L of size d or + 1 for the former. From here, in principle, we can perform structural learning of p through H H(L)), which then gives us approximated DAG Ô of p and check (H 96). Unfortunately, structural learning

---

of Bayes nets is known to be computationally hard in many settings (H8f93, CHM04), and this would lead to computationally inefficient algorithm.
Instead, 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 æ to the two optimization problems (structure learning of p and q) satisfy fi fz(x) due to their local entropy being close? - this means that an optima x1 for fi satisfies ming fi (x) = fi (11) >
fa(21) ? 2 ming f2(x) =² and vice versa (optima 22 for f2).
Applying Lemma 3.4, we have that dRL. (plpe) & Os(s²) where G is the DAG q is Markov with respect to. With this at hand, we continue onto the KL testing part. The algorithm will check if Px..n((AA)) 2 (2c2 max(n, log(1/e))) and reject early it is true (this costs llgg(n) (o)g(()amxxxnaa.m (max(nnlo(11/1))
samples) and then check for every i [nl].
E²
det, (Pt/Px na: ((x.))))a)) > or dKL uf lell = O.
Recalling (4), if the former case holds, we have
dxs m x11 > p (A,) Ix (A)) + (f = Ω n2
<0(=2/m)
the bound on the first term following from the algorithm's is check on Line 10. Using Lemma 2.4, we can perform the corresponding check for i E [nl], and after union bound over n tests, noting that 2²
((xa,={)) 2 2at"n n² (o/en/E) when restricted on A'. the sample complexity is
((V" 2d log(n/E) n
2²
2d+ n
(2 n2//2n3/2 E2
llog = =0
loo
E²
Following this, we look at the two cases:
If p-p=on = q, then with high probability, p will pass all entropy tests, all KI. local tests and the
tester will accept.
If du (p. q) B E, either fails one of the entropy tests. It does pass the entropy test, then we must have that dKI (pllpa) < O(=²) by (26). Then following Lemma 3.3 and Lemma 2.4, the tester will reject.
In total, the sample complexity is:
o
2d/ ny dlo(gn/e)
dn² +
24/2n3/2 d n +
loog
g²
e
g²
This concludes the proof of the theorem.
4 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 directions. We believe the closeness (two-sample) testing variant of the problem (testing if two unknown distribution and y 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 testing independence in terms of mu- tual information (studied in [BGP+23] and also covered in [CDKS18)). notion closely related to entropy.
"Here, x is the DAG's assignment of parents and child; and fi (x) (resp. fe(x)) is the associated KL- divergence (also called score of the DAG in the literature, which measures the how well DAG models the true Bayes net) between p (resp. 4) and Since are in the realizable setting, the optimal is in fact 0.
10

---

Acknowledgments and Disclosure of Funding
We would like to thank the reviewers for their suggestions and efforts which help improve this paper.
References
[ABIS19] Jayadev Acharya, Sourbh Bhadane, Piotr Indyk, and Ziteng Sun. Estimating entropy of distributions constant space. In NeurIPS, pages 5163-5174, 2019.
[ADOS17] Jayadev Acharya, Hirakendu Das, Alon Orlitsky, and Ananda Theertha Suresh. A unified maximum likelihood approach for estimating symmetrie properties of discrete distributions. In ICML, volume 70 of Proceedings of Machine Learning Research, pages 11-21. PMLR, 2017.
[AISW20] Jayadev Acharya, Ibrahim Issa, Nirmal V. Shende, and Aaron B. Wagner. Estimating quantum entropy. IEEE J. Sel. Areas Inf. Theory, 1(2):454 468, 2020.
[AMNW22] Maryam Aliakbarpour, Andrew McGregor, Jelani Nelson, and Erik Waingarten. Es- timation of entropy in constant space with improved sample complexity. In NeurIPS, 2022.
[AOST17] Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, and Himanshu Tyagi. Esti- mating renyi entropy discrete distributions. IEEE Trans. Inf. Theory, 63(1):38-56, 2017.
[BCY22] Amab Bhattacharyya, Clément L. Canonne, and Joy Qiping Yang. Independence test- ing for bounded degree bayesian network. CoRR, abs/2204.086900 2022.
[BDKRO2] Tügkan Batu, Sanjoy Dasgupta, Ravi Kumar, and Ronitt Rubinfeld. The complexity approximating entropy. In STOC, pages 678-687. ACM, 2002.
[BFF+01] Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, and Patrick White. Testing random variables for independence and identity. In FOCS, pages 4514 IEEE Computer Society, 2001.
[BGKV21] Arnab Bhattacharyya. Sutanu Gayen, Saravanan Kandasamy, and NV Vinodehandran. Testing product distributions: A closer look. In Algorithmic Learning Theory, pages 367-396. PMLR, 2021.
[BGMV20] Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, and N. V. Vinodchandran. Ef- ficient distance approximation for structured high-dimensional distributions via learn- ing. In NewrIPS, 2020.
[BGP+23] Arab Bhattacharyya, Sutanu Gayen, Eric Price, Vincent Y. F. Tan, and N. V. Vin- odchandran. Near-optimal learning of tree-structured distributions by chow and liu. SIAM J. Comput., 52(3):661-733 2023.
[BY02] Ziv Bar- Yossef. The Complexity of Massive Data Set Computations. PhD thesis, UC Berkeley, 2002. Adviser: Christos Papadimitriou. Available at http://webee. technion.co ac httpa////wewe////eeeeeeeee/////e
html.
[Can22] Clément L.. Canonne. Topics and techniques in distribution testing: A biased but representative sample. Found. Trends Commun. Inf. Theory, 196)::032-1198. 2022.
[CDKS18] Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Test- ing conditional independence of discrete distributions. In STOC, pages 735-748. ACM, 2018.
[CDKS20] Clément I.. Canonne, Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Test- ing bayesian networks. IEEE Trans. Inf. Theory, 66(5))3132-3170, 2020. Preprint available arXiv:1612.0313.

---

[CHM04] 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.
[CK11] Imre Csiszár and János Körner. Information Theory Coding Theorems for Discrete Memoryless Systems, Second Edition. Cambridge University Press, 2011.
[CL68] C. K. Chow and C. N. Liu. Approximating discrete probability distributions with dependence trees. IEEE Trans. Inf. Theory, 14(3)462-467, 1968.
[DDK19] Constantinos Daskalakis, Nishanth Dikkala, and Gautam Kamath. Testing ising mod- els. IEEE Trans. Inf. Theory, 65(1 1):6829 6852, 2019.
[DKW18] Constantinos Daskalakis, Gautam Kamath, and John Wright. Which distribution dis- tances are sublinearly testable? In Proceedings the Twenty-Ninth Annual ACM- SIAM Symposium on Discrete Algorithms, pages 2747-2764. SIAM, 2018.
[DP16] Constantinos Daskalakis and Qinxuan Pan. Square hellinger subadditivity for bayesian networks and its applications to identity testing. arXiv preprint arXiv.1612.03164, 2016. Full version of [DP17].
[DP17] 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.
[GHS21] Tom Gur, Min-Hsiu Hsieh, and Sathyawageeswar Subramanian. Sublinear quantum algorithms for estimating von neumann entropy. CoRR, abs/2111.11132 2021.
[HJW15a] Yanjun Han, Jiantao Jiao, and Tsachy Weissman. Adaptive estimation of shannon entropy. In ISIT, pages 1372-1376. IEEE, 2015.
[HW15b]] Yanjun Han, Jiantao Jiao, and Tsachy Weissman. Adaptive estimation of shannon entropy. CoRR, abs/1502.00326, 2015.
[Hof93] Klaus-U Höffgen. Learning and robust learning of product distributions. Proceed- ings of the sixth annual conference Computational learning theory, pages 77-83, 1993.
[3CG+23] Neville Kenneth Kitson, Anthony C. Constantinou, Zhigao Guo, Yang Liu, and Kiat- tikun Chobtham. survey of bayesian network structure learning. Artif. Intell. Rev. 56(8):8721-88) 18144 2023.
[KDDC23] Anthimos Vardis Kandiros, Constantinos Daskalakis, Yuval Dagan, and Davin Choo. Learning and testing latent-tree ising models efficiently. In COLT, volume 195 of Proceedings of Machine Learning Research, pages 1666-1729. PMLR, 2023.
[Pan04] Liam Paninski. Estimating entropy on m bins given fewer than m samples. IEEE Trans. Inform. Theory, 50(9):2000- 2203, 2004.
[Pan08] Liam Paninski. A coincidence-basee test for uniformity given very sparsely sampled discrete data. IEEE Transactions on Information Theory, 54(10):4750-4755 2008.
[VVIla] 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.
[VV11b] Gregory Valiant and Paul Valiant. The power of linear estimators. In FOCS, pages 403-412. IEEE Computer Society, 2011.
[VV13] Paul Valiant and Gregory Valiant. Estimating the unseen: Improved estimators for entropy and other properties. In NIPS, pages 2157-2165, 2013.
[VV17] Gregory Valiant and Paul Valiant. automatic inequality prover and instance optimal identity testing. SIAM J. Comput., 46(1):429-455) 2017.
12

---

[WY16] Yihong Wu and Pengkun Yang. Minimax rates of entropy estimation large alpha- bets via best polynomial approximation. IEEE Trans. Inform. Theory, 62(6):3702-
3720, 2016.
13

---

A Derivation for Line 4 in Algorithm 1
We need to show the following: with probability at least 99/100, if 21 3 2r, then p(A) > r: and if 1 2T, then p(A) < 3T. For the first one, prove by contrapositive: with high probability 1 200 p(A) < < Z1 2r. Suppose T Binomiaa(m1, 5) and setting my 3 log 200
and using Chernoff bound, we have the following
Pr[T 2r] & exp( m1/3) < 200
Since any Binomial (m1, p(A) will be first-order stochastic dominated by Binomial (m1.7)
p(A) < T, we can conclude the following: if p(A) < T, then Pr[Z1 > 2r]
< Pr(T
> 2r
< 200
For the latter, we prove via its contrapositive: with probability 1
p(A) 3r
+ Z1 2T. As
200
p(A) > 3r, take mi
48
log 200 by Chernoff bound, we have
Pr[j' & 2r < Pr (A) < (1-1/3) (1-1/3) & exp (- m. m))((A)
m1
& exp
<
18
9
200
Combining the two with union bound concludes the proof.
B Deferred proofs from Section 2.1
Claim 2.2. Let A be any set such that p(AA < 2/2. Then, if (PA)) H(aa)) 2 E, we must have (i) (KL(PA llqa) or (ii) EiEd(P (pi 9:) logl 1
9
Proof of Claim 2.2. We can bound (μ(a)) H H(aa)) as
1 9i
8 < {H((A))- H(qa)l
Σ
Ps log
qi log
pi
1
1
ps log
+ pe log
9: 1: qe
log
pt
Σ iEA
Ps log
Ui
+
Σ
ps log
1
gi log
1)
ps
qi
qi
iEA
1
|dKı. (PAllAA)) +
Σ
(pi (i) log
qi
BEA
which implies that at least of the two terms is least e/2. If it is the second, are done; otherwise, we know that either
(kL(PAllęл) > ze or (xalla)) < <-
We will rule out the second case, using that log 1 > 1 for 0,
(KI.(PAllAA) = Σ log
pr
Pi
Σ Pt
1
qi
g ((A) - p(A) -
Pi
SEA
iEA
Thus, we cannot have dRL. (PAllAA) < - and so (KI((AAlgA) > tec.
Claim 2.3. Let P be the empirical estimator for an unknown discrete distribution supported on
[k], based on Poi(m) samples, where m θ Iog)
assume that dx (p qA) E/8 and
p(A) + ((A) & i logik/23" 'hhn
E(n - p.) log
1
Pr
qi
8
100
*In the case of p. 0, we still have ps log p1
3 Pr g.
One can remove the assumption that p( ((A)
4r, at the cost of slightly constant.
14

---

Proof of Claim 2.3. We follow the same analysis in [WY16]. Letting Y, (pi (i)) log for
q:
i E A, we have Y = 0 and
EY = Bi(p: - log" Var[Y.] = EY, - =
q: = m² (mp;) log²
Pt
log
m
Let :- EiEA(Di - po) log प. We will use our assumption that dx² (PA qA)
& e/8 and p(A) +
q(A) < à Tomthyes below. Note that, our analysis is in the Poissonized setting:
Var[Y]
Var
E(n - D.) log
qi
Pi
log²
2
m
9i
iEA
Ps
1
Pi
2
log
+
log
m
Pi
qi
iEA
Pi
1
2
Pi
2
log
+
+
log
m
qi
EEA
2
Pi
log?
1
+
2
Ps
log?
2
Pi
pi
qi
EEA
IEA
2
Pt log
[
1
+
2
Pi
Pi
1
+
Σ
2
Pi
y:
(8)
m
pi
m
qi
m
Pi
EL <1iEA
2 Pi log?
1
+
2
(p:
4:)3
Σ
2
(p:
9i)
+
Σ
2 (g: pi)
m
Pi
m
4s
m
EEA
24 P1IEA
21 92
<LiEA
9
4 log
2 k
6
2
+
(dxa
(PA. qu) + +drv(p. (p.)))
(9)
m0
m
m
4 log²
2
2
E
c +
4log 2 k
8
22 log? k
+
m
8
V
+
m
m
<
(10)
For (8), we analyze by two cases:
if
Pi
>
1, we have that p: log?
2
Pt
<
pi
P:
1
4
4:
otherwise, log" [z)) = =p: log"
(
1 pi
<
-1) And we use [HJW]]] 15b, Lemma3],
EieAph log² 1
< 2 2log h: + in (9). We use the premise and (4) in (10) and we have that
Pi
= dIv(pA, tarea & (dx(pannw +
V +
and the last step is obtained by noticing that log(k) > 2 for l > 2. By Chebyshev's 's inequality, we then have that
38 log? 2 k
1
Pr
Y
10
Pr
E|
> 10 Vrr
<
m
100
and this last inequality yields the statement as long as m > 22x x0x (kk)
140800 log (k) 2²
2²
Lemma 2.4. Let A = ii E [ di > a). Let m2 > 16384 max { V az L1 be the number of samples used to compute Zz. Then E[Zz] = m2dy3 (PA. 9A). Moreover, if dx qu) < á, then Ze] < ( m If (p qa) 2 then Var[Za & ((
15

---

Proof of Lemma 2.4. The proof is relatively straightforward modification of the argument of [DKW18, Lemma 2]. We have the expectation and variance of Zz,
pr
P: (p: q:)²²
E 7-2 madda (A), and Var [Z2)
Σ SEA
2 2
4m2
9:
boils down to bounding the following,
(P: 9:)²
2
Σ EEAA
4k + 4
q
4
iEAA
(pi - 9:)
4k +
iEAA
4k
+
IE [2)]
0m2
Derivation of the inequalities follow from [DKW18, proof of Lemma 2].
1/2
1/2
Pi
-2)2
Σ
(pi
q;)
4mz
4mz
Of
EEA
VEA
VEA
4m2
4k +
E[Zz]
1/2
Σ
(pi
9:
am2
qi
VEA
2 2
B[Z,]
B[Za]
am722
8V 8V Z2] + 8(am2) - 1/2 (E[22))8//2
Combing both, have that
(
(1++8 + +88
Var[Za] < 4k
B[Zz] + -/
(11)
am2
When (p=(PA))A) & e/2, then E[Zz]
mae and solve Var [Zz]
(32 m25) which gives
4k +
+ 88k
m2c
+ 8(amm)) 1/2 m22 m2e 33/2 <
m2²)?
am2
2
2
32
We solve for the relaxation:
LHS & 4 max
4k:
2: AVKmme, 8
m2
3/2
<
m25)
Va23/2
32
In the end, we obtain:
Vi
2
1
Vk
max
128
64l
32
32
16
322 16 max
m2
ae"
VaEV2
When dx=(PA. > c, then B[[Z]] m2c; and we solve Var < (Z
4k
4
8VK
EiZzi + -/2 < B(Zz))²
am2
which is equivalent to the following
4k
+
+
8v
+ 8(am2) 1/2 <
11/2
E 2/2
3//2
amz
(E|
16
16

---

Further relaxing the solution, it is enough to have
4k
+ 88
8((mm2) 1/2 11/2
22
[
22
am2
(B
4k
+ 88k
+
(225
am12
(m22)
Vam2
1
(m2e)
1/2
(B(Z2))
16
as long as the following holds,
2
1
Vk
a
vk 512
m2 > 64 max
2
max
128
(12)
us
as
Letting m2 > 512 max (Vae
vk
we have that both statements.
C Proofs of entropy testing lower bounds
Lemma 2.6. With fewer than vk/s samples from no tester can distinguish between p and [p) (q)) > with probability higher than 2/3, where c3 is an absolute constant.
This follows from the standard uniformity testing lower bound [Pan08], which provides lower bound of O (VVkrn²): there exists family of distributions that are hard to dis- tinguish from uniform Ug. using fewer than C₁ vk/n samples. Let be even number; the construction is by taking 0 {-1, k/2 uniformly at random, and letting, for every i E [k/2].
Proof of Lemma 2.6.
+ 0:-1 k
1 1 0,
P6 (2i)
P6 (2i 1)
k
We can verify that for any 0:
1 11+1
1)
1+
7
1 1-11
)) - O(7?)
(p H (ux) = log /
log
+
log
2 k
h
k
Setting 1 ²² yields the lower bound of 52
(((V))
Lemma 2.7. With fewer than C4 llgg k/e² samples from no tester can distinguish between
and (p) - H (4) 2 e with probability higher than 2/3, where 04 > is an absolute constant.
Proof of Lemma 2.7. Following [WY16, B.2 Proof of Proposition 2], we look the same construc- tion but with different parameters Tog(2(A-
2) 1 9= 3(k 1)""""" 3(k - 1)' 3
1+ 1 2- 5
33k--11 1) 3(k: 1lkk-)'3/
One can check that
H(g) H(p) > log(2(k: - 2(E))
1
3
Moreover, direct calculation of the (squared) Hellinger distance shows that
( log
d=(p.g)² 0(5 -
which implies that p and q cannot distinguished with fewer than 04 log² samples [BY02, Theo-
rem 4.7].
17

---

Vkllog g log log(k//)
(k)
D Sketch proof of o
upper bound.
We will rely the following inequality for compression, both via Jensen's inequality,
A
Σ
log
ErEa Pi
log
<
Σ
Ps
log
EiEa
(13)
Ps
YEA
EEA
VE
log(z)) is concave and log (+) is convex.
Eiea Pi EiEa P
Pi log Σ
Σn Pi VEA
log
Σ Pt VEA
log
Eves Pi
Pi
iEA
suggesting that if merge elements of A into one, then will lose log(|A]) 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 D.1. Let S S [k]. p(S) - (()) -7, then
(ps |1 = dxL (psllas) > n.
Proof. If (dKl(Ps|las) > y,, then
(pslls)) 2 n dkI. (psllaa) < -1)
We will rule out the second case, using that log 1 x > 1 - x for x > 0, 10
(psllss14s) = Σ
Pi pi log
Σ (1
qi
= p(S) - ((S) > -
(14)
Ti
P:
iES
SES
Thus, we cannot have dkL. (ps)lls) < 17 and so dkL. (ps (|gs) >
We use the same idea first upper bound but choose series of thresholds. Let
S3 = { i [k|la > Ω
k log log log (o/g))/)))))
S2 i [1:112
E 1: log (og()//))
E 5
E
k log log log(k/E)
S - iE [k|]
< 9 <
klog(k//)
k log log(k/e)
The following calculation ensues
l(E)
<
(H(A)) -((A))
dKL dkI
+
Σ iEA
(p: 4i) log
Σ IdKL as.)1+
Σ
(pt q:) log
iEAA
We have that one of the four terms will be least ((E/4). 4). it
(p. 9:) 9:) log
>
A(s),
qi
PEA
which is testable with O (kk)
samples using arguments from proof of Theorem 2.1. If it is
(ps, as:)) > ((s). for i = 3. We have the following:
In the case of p. 0, we still have p: log Pi
ge.
9:
18

---

Case S3. Suppose (ps, 98,)) > (E)). We will check whether p(Sa) > 0 not, we can reject. We proceed assuming the inequality holds. Note that
log log log(k/e)
e 1p(Ss) 9(Ss) = (p(5a) g(Ss) <0 log log log(k/e)
F Thus, p(Sa) ((Ss) -0 log log Tog(k/s) and by Claim D.I, have that diL (psa qs.)
>
(s).
Using (4), we then have that dxa (PS (S2) > ((e). Using Lemma 2.4 (setting
0 (oglgloggog(ke)) ) and similar argument from the proof of Theorem 2.1, we have that
0
lil log log(k/e) suffices check between the case that dx-(ps, 98,) > ((=) and ps,
98..
Case Sz. Suppose ddt (ps;; 9s,) 2 [ss). We will check whether
loglog(k/E) ) p(82) &0
Ω
log log log(k/E)
if not, we will reject. We proceed assuming the inequality holds. Now, recall that the main bottle- neck of the x² tester analyzed Lemma 2.4 is due to the minimum probability a = minges; qi (increasing this would decrease the sample complexity). Our main idea here is to increase a by merging suitable number (log log(k/e) in this case) of elements into one single bin to form new [S2] and U, U, S2. We will subsequently treat every elements in A, as 1 bin in the new distribution, calling it pa. aa and denote p(Aj), 9 (4)) as mass on Aj. where p( AA)) Liea, Pt. This gives us the following:
distribution to test. Denote A, where j E log (og((k/)//)
9(A,)
Ω
k log log(k/e)
|ر,1 >
2 2()): the domain size is
S miny ر
k log (og()/e)
ii -, = PS2)) =((z)) <0
log (og((//)) and -((()))((()) < <
= (S22)
log log kt/))
iii. Their entropy difference is preserved, which we will prove next:
1 ((( EE(Aj) log g(A,)
Σ p(d,) log p(A,)
> M(s).
Note that these better conditions compared i. and ii in the proof of Theorem 2.1 (in this analysis, using ii., it is sufficient to prove that dKL (PA 92) > Q(s) in view of Claim D.I). The gain comes from the fact that we can apply Lemma 2.4 with better min, ((A,) > (i) and thus
+
R O
k
o a8
= 0
However, the gain only affect Claim 2.3 by constant factors. The soundness and completeness then follows similarly to the proof of Theorem 2.1. We prove (ii..) next:
19

---

Suppose H(ps,) H(s,)) > then,
(())
Pt log
Σ
qi log
1
pl
qi
SES
IES2
Σ
Pig log
1
Σ
Σ
R.j log
Pi.j
qi.j
EEA;
1
iEAj
Σ p(A,) log
Σ ((A))
log
(15)
p(A,)
Σ log + Σ p p(4)) log
1
E {(1))) log g(m,)
p(A,)
o ( log log(k/))) log | + Σ p(A p(A,)
1
Σ 2(4 log ((,,) .16)
1
where the (15) is due to (13) and for (16), recall that E, p(A,) = p(S2) <0
log log log(k/e)
Suppose H(gs)) H (ps.) > (2x), the same goes below:
((E)
Σ qi log
Σ pi log
1 Pl
qi
= Σ Σ
Ui.j log
Σ ΣΣ
Pt.j log
4s.5
ps.j
EEA;
1 iEA,
|4,1
-Ep( Ep(A,) log 1
Σ ((A))log g(A,))
p(A,)
< 0(s) + Σ ((ا,) log q(A,)
E((ds) log p(Ai)
3
Therefore, we have proved (iii.).
Case Sj. The proof follow similar to Case S2, but by merging log(k//s) elements.
E Proofs of testing Bayesian networks
Claim E.1. Suppose that p(ù) < x0(=2/ (((e)))o(1)/E), then we have for any distribution
9(U)
dkL dkI(Pullg)) > -p(()) log
> -
p(ú)
This implies that dRL (pall > -O(E?) for any DAG G. Moreover if dkl(pllpG) & O then deL (pulllll (l..) O
20

---

Proof of Claim E.I.
Σ p(x) log p(r)
dgL (atrpllPaal
(ci(
xetl
pa(xx) p(ar)
Σ p(x) log
seil
Eneil p(a))p())...))))>)))) ΣzEa P(x)
po(()) p(a)
Σ p(z)
llog
NEll
pG(lI)
-p(U) log
p(l))
-O log(l1/)) log E² log(1/E)
-O(=2)
where we use monotonicity of -x =olog and the fact that pu( & the second last inequality. Since (plip) = dxL. (Pu (pullppa) + dKL (Pa (lp))) & (( and dRL (Pa (lPaa) > -c() we can rearrange and see that dKr (PrllPGH)) & O(
We will need the following claim for the proof of Lemma 3.3.
Claim E.2. The following inequalities hold, for any i E [ri]
px log ( qT (x'))
E²
Σ Z'EA
(17)
Σ p(z) log ((. (x))
E2
-0
(18)
((.(())).{()))
#EA.
Proof. We will show (17) first.
Σ ne (x') log (x=(((x))
Ex,e ((77(((() p()(((a)))
Σ Px.))(())) F'EA
log
((
T'EAG
EvER Px (2¹)
Σ px Z'E.
-log
E(r,T)e PxçIng (x/(T)) ((T))
Σ (x))
log
Σ Px..n((a')
F'E
r'EAi
22
)) log
n log((/e))) (1-
122 log(m/e))
e2
W
n² log(n/E)
where the first step follows from Jensen's inequality applied to the function f(x) log(1/x)), and the second-to-last step due to x log æ is monotonically increasing when æ 2 and log(1 x) > -2x when (0, 0.5). This concludes the proof of (17).
21

---

We next to proving (18).
ExEANUP(S)
pla) log (<2;(z) m (x))
Σ
Σ p())
log
(z, m. (x))
EmEANUP(S) ((o
*EA,Y
sEAiiu
EPEAN P(z)
E p(x)
log
EREANH p(a) (())))
DEALNH I
Σ p(x) DEAN
log
Σ p(a)
BEA.
where the second-to-last step follows from Equation (19) below, and last step by monotonic- ity (decreasing) of f(x) = log when x
< 1 and ((E))up(z) & Eits ExEA, p(z) <
Eips 0 (n=log(mne))
0 nogg(n/)))
Σ
p(x)
ZEANH
p(x)
Σ
p(.((T) Tf
zEAiV
(
E
p(a.(z), p(a)
ZEAiV
Σ
(()
p()lo,()), m (x))
ZEAM
Σ
p( 2 )
Σ p(a'12z, 12 x(
(19)
(x
((0,)))
<'E(0.1j"-1n.1 1111
Σ
p(T:))
Σ
( =1
(.E(
This concludes the proof of (18).
Lemma 3.3. Suppose (p.g) q) > S(E2); dra (pllp)) & O(E2); p(l))
n log(n/E) Vi
p(A)) & nt log(nfjj where Ai, is defined above, and q is Markov with respect to G, then we have
dxL. (px. (1xx > 2(62).
Therefore testing deL (Px,, a waaealll9ee (9x.. > 2² over all suffices to detect this case.
Proof of Lemma 3.3. By Claim E. and the assumption that (pl(pp)))) < O(E²), we have that
dRI(pu (Paa)) der.(pllp)) dxi. (PallPaaz)) & (EE2).
(20)
1 O(E?) < (p.(p.)) q) = (p +d, (pa. q2) < di (pu, an) u (x(()) & di (pu (pu.
22

---

(1(2) < (pu, qu) & drı((ullle)) + ((2) p(()) = dRI(pullux)) > 2(62). (21)
Combining and (20) and (21), write
((=²)
<
dxi. (pullqu))
- dRL (PrdlPPa)
(()
Σ
p())
log (x)(T)));
DEl
E p(r) ((((()))((()))
Σ
p(x) log
((t;(t))m{(x))
DEA,
sEAiV
p(z) log ((a(())((())
p(r) log (X)
Σ
Σ
DEA.i
p(ri(c')
p(z) log ([)((t))T{(
(x)) log
Σ
Σ
((,;((²) (=)
T'EA
ZEA:V
Σ Σ (x. log ((m)((x))
dKL (Px ((
g(T((x²)))
i=1 r'EE
p(x) log ((<(())(+{(0))
[ (x))
i=1 DEA. V
With Claim E.2 and Claim E.I, we can lower bound the sum of local KL divergences,
M(=?).
Lemma 3.4. Let p and q be max in-degree-d Bayes nets supported {0, 13" such that for every subset L S {",,'" ;nn of size + 1, the following holds:
E²
H(PL) H(()) &
Suppose p is Markov w.r.t G and 9 Markov w.r.t. G. Then have that (kL(P) & O(E²) and dxL (gllgc)) < O(E?).
Proof of Lemma 3.4. More formally, by the celebrated works of Chow and Liu [CL68] and its gen- eralization to Bayes net, 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 derivation for the sake of completeness in Appendix F):
0 & (KI((p))G))
Σ H (px..xn,
+
Σ
H H (xx,g))
(22)
0 & dKL(gl19G:)
Σ H (xng)) +
H (qx, 19xa,),
(23)
where XI1, denotes the parents of X; in Bayes net p and Xn1 denotes the parents of X, in DAG G. Here assume that & is Markov with respect G. Since the local entropies between and are close by O ((52/n) (see (6)) and its relation to conditional entropy via (3), we can conclude the following:
(gx.. 1axu,) -((2/m)) & H(px,.x, (xx.,) ) < H(gx..X 12xm, O(E
(24)
23

---

H(xx,. 9x (9xmg) 0()2/n) H(xx, ng (xxØ)) & (yx,, 9x + (s)2/n). (25)
Since assume that q is Markov with respect G, can combine (22), (23), (24) and (25), which then give:
a
dKL(plIpe
Σ Hlgx..xn, 1axn, )+
Σ H(gx.. 4x +0())) ==dku(gllg)))+((e
where p Markov with respect to G", as II; is the set of parents of X; for p. Rearranging terms and we have
(xI((p))G)) dkl, (allar)) < O(s²).
(26)
Since KL-divergence is nonnegative, we conclude that both terms must be at most (s²²).
F
Derivation for KL decomposition
Below, we provide full proof on decomposing the KL divergence between Bayes net p and its projection Pa. for any DAG G, into local conditional entropies.
dKI.Pp,P3 PG)
(()) log p(x)
Σ
pa
=E(0,1)"
Σ xE(0,1)"
p(z) log
I po (x)
Σ p(x) log
II p(Za)(m)))
p(x) log II pa(
"
Σ xEf0,11"
Σ ((x) log(p(a;(m.)) p(x) (og(p)
Σ
Σ
log(p((())))))) - p(=) log(pa
1= (0,1))
Σ EX:.I
p(as, n,) log(p(s((())
Σ EX,
plus, ( (og(po(s:(m=)))
((Pxx.mplnne HPx. lmn.),
where ni II, denote the parents of 24, X, in Bayes net p (a set of random variables or their domain); and n. II as the parents defined by G. PG the projection unto G as defined by Definition 3.2. It is not hard see that the derivation extends beyond the case of hypercube, (0, 1
24

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers penalize honesty concerning limitations.
will be specifically instructed
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer:
[Yes]
Justification: The proofs are provided either in the main paper or the appendix, both part of the submission. Assumptions are fully stated in the theorem and lemma statements.
25

---

Guidelines:
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 cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper 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 comple-
mented by formal proofs provided in appendix supplemental material. Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
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 conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not contain experiments.
Guidelines:
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 not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending on the contribution, reproducibility can accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way accomplish this, but reproducibility 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.
also be provided via
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. model (e.g., large language model), then there should
(c) If the contribution is either be a way to access this model for reproducing the results or a way to re- produce the model (e.g., 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 au- thors 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
26

---

Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurlPS code and data submission guidelines (https://nips)
public/guides Sotees/CodSuummsssiiiii
for more details.
While we encourage the release of code and data, understand that this might not be possible, so "No" am acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurIPS code and data submission guidelines (https: //iips.cc/puleee cccpublic////ccccccccccccccmllbb cubbiic/uuieen seiddes//e /CoeeSubmdiiiii commisssion onPolicy) for details. The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, 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 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, as supplemental material.
7. Experiment Statistical Significance
Question:
Does the paper report error bars suitably and correctly defined or other appropri- ate 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, confi- dence 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.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errrrs is not verified.
27

---

For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't t make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /ttt::::///erip.....
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code Ethics. If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. s. if there is special consid- eration due to laws or regulations their jurisdiction).
10. 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 theoretical in nature; hard to predict its societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal
impact 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 spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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.
28

---

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 being used 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 mitiga- tion 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).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere usage guidelines or restrictions 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
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 dataset.
The authors should state which version of the asset used and, possible, include URL.
The name the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors are encouraged to reach out to the asset's 'ss creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
29

---

The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/cooe/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.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere 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.
30


Reviews:
[{"review_id": "jh63Mk8TJq", "reviewer": "Reviewer_BQBQ", "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.", "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?\n* 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$.\n\nMinor comments\n* In line 108, in the phrase “as just mentioned, when its TV distance…” what is “it” referring to?\n* In line 163, is the partial Hellinger distance missing a power of 2 in the summand?\n* 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.\n* In the display following line 416, maybe good to mention that the Poissonization trick is used there\n* In line 434, “When $d_{\\chi^2}(p_{\\mathcal{A}}, q_{\\mathcal{A}}) \\geq \\varepsilon$” is written twice.\n* 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": "They have addressed their limitations.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* Clear and well-written\n* This seems like a fundamental problem and it’s good to get tight bounds for it", "weaknesses": "* 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.\n* 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).\n* 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their encouraging comments.\n\nWe understand the confusion, and will rewrite the statement of the two lemmas in the revision to make it clear that these are minimax lower bounds. For Lemma 2.7, we will add a paragraph to provide some\nintuition, pointing out that it is based on the classical Le Cam's two-point method commonly used in the\ndistribution testing literature, and briefly explaining ``why'' one would expect these to be hard instances. Indeed, instance-optimal bounds could be an\ninteresting research direction to pursue.\n\nWe will address the questions raised below:\n\n1. $\\log \\left( \\frac{16 k}{\\varepsilon / \\log (k / \\varepsilon)} \\right) =\n\\log (16) + \\log \\left( \\frac{k}{\\varepsilon} \\right) + \\log \\log (k /\n\\varepsilon) \\leqslant 2 \\log (k / \\varepsilon)$ for large enough $k$, as\n$\\log \\log x \\ll \\log x$.\n\n2. You are correct. We could indeed obtain the same result by losing a little\nbit on the constant and dropping the assumption on $p (\\bar{\\mathcal{A}}) + q\n(\\bar{\\mathcal{A}})$.\n\nMinor comments:\n\n1. It is referring to the paragraph from Line 103-106.\n\n2. 3. 4. 5. 6. Yes, you are correct. We will make the corresponding changes in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VGjgwXw0ak", "reviewer": "Reviewer_cFXh", "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$.\n\n* 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. \n\n* 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)$.  \n\nRoughly speaking, the algorithm for entropy identity testing divides the space into two regions:\n1) Where $q$ has low probability: just test whether $\\hat{p}$ attains large values in this region. if so, then reject.\n2) Where $q$ has high probability: use the algorithm of [DKW18] to efficiently test whether $d_{KL}(p||q) \\geq \\epsilon$.", "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": "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.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The nice thing is the observation that the identity entropy testing problem is much easier than the entropy estimation problem itself, which is known to be $\\theta( \\frac{k}{\\epsilon \\log k}  + \\frac{\\log^2 k}{\\epsilon^2} )$.\n\n* The paper is well explained. I appreciate the intuitive explanation and thought process of bounds that are obtained using simple ideas, followed by the need to make appropriate modifications to overcome those issues.\n\n* It is indeed surprising that entropy, which is not an easy quantity to estimate (optimally), is much easier to test.", "weaknesses": "* 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. \n\nOther minor points: \n* The (possible) applications of either of the two testing problems, especially the identity testing of degree-d Bayes can be mentioned.\n\n* Lines 142-143 can be slightly rephrased ``directly extending this argument does not work\" causes some confusion.\n\n* 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]", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their encouraging comments and feedback.\n\nWe did not try to optimize the constants. This is primarily a theoretical\ncontribution which can serve as a proof of concept: any practical\nimplementation would be significantly optimized, and there is nothing a priori\ninherent to our approach that would make this impossible.\n\nRegarding the comment about Renyi entropy: this is an interesting question.\nRenyi entropy of order 2 is equivalent to $\\ell_2$ norm of the distribution,\nand so, in some sense, in testing in $\\ell_2$ (which has been considered in\nprevious work, but did not appear to yield any obvious sample complexity\nimprovement for the task of Bayes net testing). It is not clear to us whether\nthis would translate to an algorithm, but this is something to consider in\nfuture work (especially for general $\\alpha$-Renyi entropy).\n\n*On the minor points*:\n1. 2. Thank you for the suggestions.\n3.. Yes, you are correct.\n\nWe will make the corresponding changes in the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "olkXCdidOc", "reviewer": "Reviewer_S8s6", "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.", "questions": "1) It is hard to see the significance of the entropy identity testing. \nHeuristically, 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)$,\nand thus the entropy identity testing might be essentially easier than the other testing problems based on \"distances\" such as KL-divergence or Hellinger distance.\n\n2) I think the manuscript should be revised for clarity, since it contains too many typos and small errors. Below are a few examples.\n- In Abstract, $k$ is not defined.\n- 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$.\n- In the equation below line 134, $p(\\bar{A}) = O(\\tau)$ does not imply the second inequality.\n- In line 182, the semicolon seems to be a typo.\n- In Algorithm 1, what is $N_i$?\n- In line 200 and line 202, \"Algorithm 4\" should be \"Algorithm 1\".\n- In Algorithm 2, what is S_1?", "limitations": "The work does not seem to have potential negative societal impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The performance of the algorithms, including the runtime and the error bound, is guaranteed by theoretical analysis.\nDetailed mathematical proof is given.", "weaknesses": "The importance of the problem is not discussed much.\nThe writing is not clear with several errors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and review.\n\n1. Indeed, the formulation introduced is a bit atypical, but we emphasize that\neven more standard formulations where the alternative is in terms of distances\n(such as total variation distance or KL divergence, say) might still have a\nsimilar objection, namely that  $p \\neq q$ but $d(p,q) < \\varepsilon$. The motivation for\nthe formulation chosen is made apparent by one of the applications, namely\nthat of Bayesian network testing, where we show that as a building block, it\nleads to savings compared to existing algorithms (this application was\nactually the starting point for formulating this hypothesis testing question\nin the first place). We strongly believe that this new hypothesis testing\nquestion will find other applications.\n\n2. Thank you for the comments. We will fix the typos the reviewer pointed out\nand improve the presentation; in particular, defining the notation\n$\\leftarrow$ for variable assignment and $N_i$ for the empirical count among\nsamples of the $i$-th element; $\\mathcal{S}_1$ was the set of samples from\nLine 1 of Algorithm 2, and should have been written there. $p (\\bar{A}) = O\n(\\tau)$ for sufficiently small constant inside the big $O$, implies the second\ninequality through the monotonicity of $f (x) = x \\log \\frac{1}{x}$ when $x <\n\\frac{1}{e}$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7JMcWouc5l", "reviewer": "Reviewer_wSfS", "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.", "questions": "+ What is the definition of $\\mbox{Poi}(m)$ in Claim 2.3?\n+ 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). \n+ 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$?\n+  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.\n+ 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. \n+ 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": "This is a theoretical research paper, hence the negative society impact of this work is not direct.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The claimed results sound interesting.", "weaknesses": "Some key proofs look not correct, and some notations are not defined. Please see the questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and review (and for taking a close look at the\nproofs).\n\nWe would like to address the questions raised in the review below:\n\n1. As is standard in distribution testing, we work in the Poissonized sampling\nmodel. $\\operatorname{Poi} (m)$ denotes a random variable distributed as the Poisson\ndistribution with parameter $m$. In the revision, we will formally define this\nin the Preliminaries.\n\n2. We apologize for skipping some proof details when applying Jensen's\ninequality here. Our proof means to use the function $f (x) = \\log (x)$ as\nconcave. So, in this case, we are taking $x_i = \\frac{1}{q_i}$ and $a_i = q_i$\nwhich yields the following inequality:\n$$ \\frac{\\sum a_i \\log (x_i)}{\\sum a_i} \\leqslant \\log \\left( \\frac{\\sum a_i\n   x_i}{\\sum a_i} \\right) \\Rightarrow \\frac{\\sum q_i \\log \\left( \\frac{1}{q_i}\n   \\right)}{\\sum q_i} \\leqslant \\log \\left( \\frac{\\sum q_i \n   \\frac{1}{q_i}}{\\sum q_i} \\right) . $$\n3. Thank you for catching this! We neglected to change out the constants while\ncalculating this part of the proof. Note that, this does not affect the end\nstatement of the theorem, but just the constant factors in the analysis.\nIndeed, $\\operatorname{Var} [Z_2]$ needs to be smaller in terms of its constant in the\ncase of Completeness for the analysis to work; and one can do that by\ntightening the constant in the analysis. In particular, we can adjust from the\ninequality from line 431-433 from the proof of Lemma 2.4. See calculation\ndetails below:\n\nSolve $2 \\sqrt{\\operatorname{Var} [Z_2]} \\leqslant \\frac{1}{16} m_2 \\varepsilon$:\n$$ 4 k + \\left( \\frac{4}{\\alpha m_2} + 8 \\sqrt{k} \\right)  \\frac{m_2\n   \\varepsilon}{2} + 8 (\\alpha m_2)^{- 1 / 2}  \\left( \\frac{m_2\n   \\varepsilon}{2} \\right)^{3 / 2} \\leqslant \\frac{1}{32^2} m_2^2\n   \\varepsilon^2 ; $$\n$$ m_2 \\geqslant 128 \\max \\left ( \\frac{2 \\sqrt{k}}{\\varepsilon},\n   \\sqrt{\\frac{2}{\\alpha \\varepsilon}}, 4 \\frac{\\sqrt{k}}{\\varepsilon}, 2\n   \\sqrt{\\frac{2}{\\alpha \\varepsilon}} \\right ) = 512 \\max \\left(\n   \\sqrt{\\frac{1}{\\alpha \\varepsilon}}, \\frac{\\sqrt{k}}{\\varepsilon} \\right)\n   . $$\n\nNote that, this is the same requirement as the other case (no change to the\nsample complexity upper bound in terms of constant).\n\n4. Note that $m_1  \\hat{p}' (\\bar{A})$ is distributed as Binomial with\nparameter $m_1$, $p (\\bar{A})$ and so we can apply Chernoff bound on this\nrandom variable.\n\n5. Sorry for the slight abuse of notation. We will add the constants in the\nstatement of Lemma 2.4. Specifically, relating this to reponse 3 above: we\nwill change the statement to\n\n*Let $\\mathcal{A} \\leftarrow \\{i \\in [k] \\mid q_i \\geqslant \\alpha\\}$. Let $m_2 \\geqslant 512 \\max \\left(\\sqrt{\\frac{1}{\\alpha \\varepsilon}}, \\frac{\\sqrt{k}}{\\varepsilon}\\right)$ be the number of samples used to\ncompute $Z_2$. Then $\\mathbb{E} [Z_2] = m_2 d_{\\chi^2} (p_{\\mathcal{A}}, q_{\\mathcal{A}})$. Moreover, if $d_{\\chi^2} (p_{\\mathcal{A}}, q_{\\mathcal{A}}) \\leqslant \\frac{\\varepsilon}{2}$, then $\\operatorname{Var} [Z_2] \\leqslant \\left( \\frac{1}{32} m_2 \\varepsilon \\right)^2$. If $d_{\\chi^2} (p_{\\mathcal{A}},q_{\\mathcal{A}}) \\geqslant \\varepsilon$, then $\\operatorname{Var} [Z_2] \\leqslant \\left( \\frac{1}{4} \\mathbb{E}[Z_2] \\right)^2$.*\n\n6. Sorry for not being clear enough: indeed, it relies on the testing outcome\nfrom line 215-217, which is saying, if $d_{\\chi^2} (p_{\\mathcal{A}},\nq_{\\mathcal{A}}) \\geqslant \\frac{1}{8} \\varepsilon$, then we can detect it and\nreject it early (with high probability). So to continue towards line 218, and\nstill not being rejected, it has to be the case that $d_{\\chi^2}\n(p_{\\mathcal{A}}, q_{\\mathcal{A}}) \\leqslant \\frac{1}{8} \\varepsilon$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all the reviewers for their detailed and thoughtful
comments (especially for taking a close look at the
proofs). We respond to each reviewer's comments individually below; and here focus on a common point raised across the reviews, that of the motivation or practical relevance of the question.

It is always delicate to argue about the importance of a newly formulated question, such as the one we are introducing and addressing in this paper. However, ``testing in entropy difference'' can be seen as a variant of the well-studied goodness-of-fit question, where the alternative hypothesis focuses on some particular premise (namely, that what one aims to detect as evidence is a discrepancy in entropy). This question actually originated from the main application we consider in the paper, that of testing Bayes networks, for which we provide an algorithm where testing in entropy difference is an important building block. Given the existing literature on estimating (Shannon) entropy and on testing graphical models, we are confident that this new problem will find more applications.

We also want to emphasize that the correctness issues raised by the reviewers stemmed from some lack of detailing on our end, but did not reflect a flaw in our arguments (see detailed individual comments). However, we feel compelled to mention that, in the process of improving the writing and presentation, we have since identified a potential issue in the informal description (ll. 142--148; we elaborate on this in the next paragraph). Fortunately, there is an easy fix which does not affect the end results: namely, instead of Hellinger distance, we can instead rely on an (similar-length) KL-divergence-based argument.

*Details*. The issue is that having all subsets $L \subset \\{ 0, 1 \\}^n$ with size of $d +
1$ close by $O (\varepsilon^2 / n)$ in Hellinger distance does not
guarantee that $d_H^2 (p_G, q_G) \leqslant O (\varepsilon^2)$ for every graph
$G$, as claimed in Line 142-148. 
Instead, we can do local Kullback-Leibler tests on these subsets $L$, excluding small-probability elements: as it turns out out, this is enough, and does not require any change to the algorithm itself (only to its analysis).

If the reviewers feel this is useful, we would of course be happy to provide the full revised argument. We did so in the attached PDF; however, based on the guidelines, we understand that this PDF may only be read by the reviewers at their discretion.

Meta-review: 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.
Decision: Accept (poster)