Independence Testing for Bounded Degree Bayesian Networks
Authors: Arnab Bhattacharyya
Clement Louis Canonne
Qiping Yang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Distribution testing
Bayesian Network
Probabilistic Graphical Model

Abstract: We study the following independence testing problem: given access to samples from a distribution $P$ over $\{0,1\}^n$, decide whether $P$ is a product distribution or whether it is $\varepsilon$-far in total variation distance from any product distribution. For arbitrary distributions, this problem requires $\exp(n)$ samples. We show in this work that if $P$ has a sparse structure, then in fact only linearly many samples are required.
Specifically, if $P$  is Markov with respect to a Bayesian network whose underlying DAG has in-degree bounded by $d$, then $\tilde{\Theta}(2^{d/2}\cdot n/\varepsilon^2)$ samples are necessary and sufficient for independence testing.

Independence Testing for Bounded Degree Bayesian Networks
Arnab Bhattacharyya School of Computing National University of Singapore arnabbêre nus. edu. sg
Clément L. Canonne
School of Computer Science
University of Sydney
c clement. cawonneesyddny..ooooooo au
Joy Qiping Yang
School of Computing
National University of Singapore joy. yang@nus edu.sg
Abstract
We study the following independence testing problem: given access to samples from a distribution P over {0, decide whether P is a product distribution whether is e-far in total variation distance from any product distribution. For arbitrary distributions, this problem requires exp(n) samples. We show in this work that if P has a sparse structure, then in fact only linearly many samples are required. Specifically, if P is Markov with respect to Bayesian network whose underlying DAG has in-degree bounded by then 6(2//2 nn/²) samples are necessary and sufficient for independence testing.
1 Introduction
is often convenient to model high-dimensional datasets as probability distributions. An important reason is that the language of probability formalizes what intuitively mean by two features of the data being independent: the marginal distributions along the two corresponding coordinates are statistically independent. Independence is a basic probabilistic property that, when true, enables better interpretability of data as well as computationally fast inference algorithms.
In this work, study the problem of testing whether a collection of binary random variables are mutually independent. Independence testing is an old and foundational problem in hypothesis testing (Neyman and Pearson [933 Lehmann et al. 2005]. J. and consider it from the perspective of property lesting [Rubinfeld and Sudan 1996| Goldreich et al. 1998). Our goal is to design a tester that accepts product distributions
variables and rejects distributions that have statistical distance at least from every product distribution. The tester gets access to i.i.d. samples from the input distribution and can fail (in either case) with probability most 1/3. The objective is to minimize the number of samples as function of n and E.
Previous work [Diakonikolas and Kane 2016) shows that testing independence of a distribution {0, 1 requires 2 queries which is intractable. However, there is aspect of this proof that unsatisfying. The "hard distributions". which are shown to require many queries to distinguish from product distributions, cannot be described succinetly, as they require exponentially many bits to describe. Thus, a natural question arises: can we test independence efficiently for distributions on {0, 1)ad that have a sparse description?
'See Appendix D for more general result.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

One of the most canonical ways to describe high- high-dimensional distributions is as Bayesian networks (or Bayes nets in short). A Bayes net specifies how to generate an n-dimensional sample in an iterative way and is especially useful for modeling causal relationships. Formally, a Bayes net on {0. 13"h is given by a directed acyelic graph (DAG) G on n vertices and probability distributions Pi, on (0, 1} for all i E [n]] and all assignments to the parents of the i'th node in the graph G. An n--dimensional sample is obtained by sampling the nodes in a topological order of G, where the i'th node is sampled according to pi,x for the assignment π that is already fixed by the samples of the parent nodes of i. The generated distribution on {0, 1 is said to be Markov with respect to G.
In this work, we consider independence testing on distributions having a sparse Bayes net description, class of distributions naturally arising in, and with numerous applications to, machine learn- ing [Wainwright and Jordan 2008]. robotics. natural language processing. medicine, and biological settings such as gene expression data [Friedman et al,, 2000, Peng et al. 2009 Gardner et al., 2003) (where it is known that most genetic networks are actually sparse). In these cases, one hopes to leverage that additional knowledge to test whether those sparse, local dependencies are actually present without having to pay the prohibitive exponential cost in the dimension Specifically, we analyze independence testing on distributions that are promised to be Markov with respect to a DAG of maximum in-degree d. where d << n. While the learning sample complexity, known to be Ō(24 nn/s") [Bhattacharyya et al. 2020), provides a baseline for the texting question, it is not at all obvious that this is tight, and what the correct dependence on and even n are. Our main result essentially settles this question, and establishes the following:
Theorem 1.1 (Informal Main Theorem). Suppose an unknown distribution P on {0, 11th is Markov with respect to an unspecified degree-d DAG. The sample complexity of testing whether P is a product distribution or is at least from any product distribution is 6(24/2.n//s
In the course of proving this theorem, we additionally derive several technical results that are of independent interest, such bounds on the moment generating function of squared binomials and an independence testing algorithm for arbitrary distributions in Hellinger distance.
Our work explicitly initiates the study of testing graphical structure in the context of property testing, That is, instead of testing statistical property of a distribution (as is typical in distribution property testing), we can interpret our problem as that of testing graphical property of the underlying graph that describes the distribution. In particular, testing independence can be viewed as testing maximum degree-O of a distribution's s graph. This point of view opens the door to testing many other relevant graphical properties of graphical models, e.g., maximum degree k; being a forest, being connected, etc. Hence, by analyzing the "base case" of independence testing, we provide a necessary first step to solving other graphical testing problems. Information -theoorticccccccccc bounds for related problems were studied recently by Neykov et al. [2019]
1.1 Related Work
Distribution testing has been an active and rapidly progressing research program for the last 20+ years; see Rubinfeld [2012] and Canonne [2020] for surveys. One of the earliest works in this history was that of |atu et al. 2001) who studied testing independence of two random variables. There
followed series of papers Alon et al., 2007 Levi et al. 2013 Acharya et al. 2015). strengthening and generalizing bounds for this problem, culminating in the work of Diakonikolas and Kane (2016) who gave tight bounds for testing independence of distributions over [m]] x ... x [na]. Hao and Li 2020 recently considered the (harder) problem of estimating the distance to the closest product distribution (i.e., tolerant testing), showing this task could, too, be performed with sublinear sample complexity.
Though most of the focus has been on testing properties of arbitrary input distributions, it has long been recognized that distributional restrictions are needed to obtain sample complexity improvements. For example, Rubinfeld and Servedio (209), Adamaszek et al. (2010) studied testing uniformity of monotone distributions on the hypercube. Similarly, Daskalakis et al. (2012) considered the problem of testing monotonicity of komodal distributions. The question of independence testing of structured high-dimensional distributions was considered in DDsskllakis et al. (2019) in the context of Ising models. We note that while their work is in the same spirit as ours, Ising models and Bayes nets are incomparable modeling assumptions, and their results (and techniques) and ours are mostly disjoint. Further, while the results may overlap in some special cases, the conversion between

---

parameterizations makes them difficult to compare even in these cases (e.g., dependence on the maximum edge value parameter for Ising models, and max- max- undirected-degree vs. max-in-degreed More recently. Canonne et al. [2020), Daskalakis and Pan (2017), Bhhttacharyya et al. 22000) 2021)
have studied identity testing and closeness testing for distributions that are structured as degree-d Bayes nets. Our work here continues this research direction in the context of independence testing.
1.2 Our techniques
Upper bound. The starting point of our upper bound is the (standard) observation that a distribution P over {0, 1] is far from being a product if, and only if, it is far from the product of its marginals. By itself, this would not lead to any savings over the trivial exponential sample complexity. However, we can combine this with a localization result due to Daskalakis and Pan [017]. which then guarantees that the degree-d Bayes net is at Hellinger distance from the product of its marginals P', then there exists some vertex i [n|] such that P.n. (the marginalization of P onto the set of nodes consisting of i and its d parents) is at Hellinger distance at least م from P',,,. These two facts, vs combined, seem to provide exactly what is needed: indeed, given access to samples from P and any fixed set of d + vertices S, one can simulate easily samples from both Ps and P's (for the second, using d + 1 samples from P to generate one from P'g, as P'g is the product of marginals of Ps). A natural idea is then to iterate over all (4+1) possible subsets S of d d 1 variables and check whether Ps- = P'g for each of them using a closeness testing algorithm for arbitrary distributions over {0. 1) 1)d+1: the overhead due to union bound and the sampling process for Ps, P's adds a factor (d log (am1) = (dd lo to the closeness testing procedure. However, since testing closeness over {0, d+1 to total variation distance e' has sample complexity O(224/3 (e") and, by the quadratic relation between Hellinger and total variation distances, we need to take e' = =". we would then expect the overall test to result in ( /E*) sample complexity much more than what we set out for.
A first natural idea to improve upon this is to use the refined identity testing result of Daskalakis and Pan 2017 Theorem 4.2] for Bayes nets, which avoids the back and forth between Hellinger and total variation distance and thus saves on this quadratic blowup. Doing so, could in the last step keep el Vis (saving on this quadratic blowup), and pay only overall Ó(23d/4 (E Ö(2 ////d////// n/="). This is better, but still falls short of our original goal.
The second idea is to forego closeness testing in the last step entirely, and instead use directly an independence testing algorithm for arbitrary distributions over {0, 1] to test if Ps is indeed product distribution for every choice of 5 considered. Unfortunately, while promising, this idea suffers from a similar drawback as our very first attempt: namely, the known independence testing algorithms are all designed for testing in total variation distance (not Hellinger)! Thus, even using an optimal TV testing algorithm for independence [Acharya et al. 2013 DDiaonikkllss and Kane 2016 would still lead to this quadratic loss in the distance parameter e', and a resulting ((24/2 sample complexity.
To combine the best of our last two approaches and achieve the claimed O(24/2n/=²), we combine the two insights and perform, for each set S of d d+1 1 variables, independence testing on Ps in Hellinger distance, order to do so, however, we first need to design a testing algorithm for this task, as none was previously available in the literature. Fortunately for us, we are able to design such testing algorithm (Lemma 3.2) achieving the desired - and optimal - sample complexity. Combining this Hellinger independence testing algorithm over {0, 1 [ with the above outline finally leads to the 0(24/2 n/e²) upper bound of Theorem 1.1
Lower bound. To obtain our 2224/2n/e" lower bound on testing independence of a degree-d Bayes net, we start with the construction introduced by Canonne et al. 2020 to prove an ((n/s²) sample complexity lower bound on testing uniformity of degree- 1 Bayes nets. At a high level, this construction relies on picking uniformly at random a perfect matching M of the n vertices, which defines the structure of the Bayes net; and, for each of the n/2 resulting edges, picking either positive or negative correlation (with value te/Vn) between the two vertices, again uniformly at random. One can check relatively easily that every Bayes net PA obtained this way, where À encodes the matching M and the 2n/2 signs, is (1) a degree-1 Bayes net, (2) at total variation e from the uniform distribution U. The bulk of their analysis then lies showing that (3) Q(n/e2) samples are necessary to distinguish between U and such randomly chosen Px. Generalizing this lower bound
3

---

construction and analysis to independence testing (not just uniformity), and to degree-d (and not just degree-1) Bayes nets turns out be highly non-trivial, and is our main technical contribution.
Indeed, in view of the simpler and different Q224/2 /T/=²) sample complexity lower bound for uniformity testing degree-d Bayes nets obtained in Canonne et al. [2020] when the structure of the Bayes net is known one is tempted reserve - 1 out of the n vertices to "encode" a pointer towards one of 2d independently chosen Px's above (i.e., the hard instances are now uniform mixtures over 2d-1 independently generated degree-1 hard instances). The degree-1 hard instances lead in previous work to a tighter dependence on (linear instead of vn) because their Bayesian structure is unknown. Thus, by looking at the mixture of these degree-1 Bayes nets, one could hope to extend the analysis of that second lower bound from Canonne et al. [220 and get the desired (224/22/ lower bound. Unfortunately, there is major issue with this idea: namely, if the 2d-1 matchings are chosen independently, then the resulting overall distribution is unlikely to be a degree-d Bayes net instead, each vertex will have expected degree (((2)) (This was not an issue in the corresponding lower bound of Canonne ct al. 2020), since for them each of the 2d components of the mixture was a degree-O Bayes net, i.c. product distribution; so degrees could not "add up" across the components).
adapt the same idea to the matching construction: that is,
To circumvent this, we instead choose the matching M to be common to all 2 components of the mixture and only pick the sign of their n1/2 correlations independently; thus ensuring that every node in the resulting distribution P has degree d. This comes the 12(24/2 vT/=²) lower bound from Canonne et al. [2020) crucially relied on independence across those components, and thus can no longer be extended to our case (where the 2d-1 distributions Ps share the same matching M, and thus we only have independence across components conditioned on M). Handling this requires entirely new ideas, and constitutes the core of our lower bound. In particular, from a technical point of view this requires us to handle the semneettenneratig-fuug function of squares of Binomials, as well as that of (squared) truncated Binomials. To do so, we develop range of results on Binomials and Multinomial distributions we believe are of independent interest.
price, however: the analysis of
Finally, after establishing that ((20/2 / samples necessary to distinguish the resulting "mix- ture of trees" P from the uniform distribution U (Lemma 2.3). it remains to show that this implies our stronger statement on testing independence (not just uniformity). To do so, we need to show that P is not only far from U, but from every product distribution: doing so is itself far from immediate, and is established in Lemma 2.4 relating the distance from the mixture P to every product distribution to the distance between distinct components of the mixture, and lower bounding those directly by analyzing the concentration properties of each component PA of our construction.
Preliminaries. We use the standard asymptotic notation O(.), 2(.)) O(-), and write Ō(-) to omit polylogarithmic factors in the argument. Throughout, we identify probability distributions over discrete sets with their probability mass functions (pmf), and further denote by U (resp., Ua) the uniform distribution on {0, 13" (resp., (J.) We also write psm for the mn-old product of a distribution P, that is, P ② ... @ P (the distribution of a tuple of m i.i.d. samples from P); and [r]] for the set (1....,.)}
Bayesian networks. Given directed acyelic graph (DAG) over nodes, a probability distribution P over {0, 13"h is said to be Markov with respect to G if P factorizes according to G; we will also say that P has structure G. A DAG G is said to have in-degree d, if every node has at most d parents; for convenience, we use degree-d exclusively as "in-degree d' throughout the paper; we will denote by II, C [n] the set of parents of node i. Finally, a distribution P over {0, 1 1 is degree-d Bayes net P is Markov w.r.t. some degree-d DAG.
Distances between distributions. Given two distributions P, Q over the same (discrete) domain X, the total variation distance (TV) between P and Q is defined as
1 n (r, = sup (P(S) (P(S) = Σ PP(x) ZE
[o,
SCX
While TV distance will be our main focus, we will also rely in our proofs on two other notions of
distance between distributions: the Hellinger distance, given by du dn P, Q) = - IlVP VQll2. and
We note that generalizing this (weaker, in view of the dependence on n) Q(2d/2 /n/e²) sample complexity lower bound to setting is relatively simple, and we do so in Appendix D.I (specifically. Theorem D.3

---

Q(z)) TV distance, the chi-squared divergence, defiedd by dzs(P.Q)= LEx (P(x) squared Hellinger distance, and x2 divergence are all instances of f-divergences, and such satisfy the data processing inequality; further, they are related by the following sequence of inequalities:
di (P.Q) & (P & (P.( & (dsa(P.Q)
Tools from previous work. We finally state results from the literature which will rely upon.
Corollary 1.2 (Daskalakis and Pan (2017] Corollary 2.4]). Suppose P and Q are distributions E" with common factorization structure
"
P(x) Px, (11)
Px,1x (r//2n,), i=2
Q(x) Qx, (z1) II xx, (2,)an,), x E"
where we assume the nodes are topologically ordered, and II is the set parents of Then (P.(P.Q) (Px, + (Px..,.,,, Qx2.Xn.) + +... dit (Pxn.Xn, QxaxNn.)
In particular, if (P.Q) then there exists some such that di (Px,,Xn, Xn,) E.
Lemma 1.3 AAhaara et [2015] Lemma 4)). There exists an efficient algorithm which, given ...
samples from distribution P over [m1] x.... x [ma), outputs product distribution Q over [mi] x ...X x (na) such that, if a product distribution, then dza(p, (p. q) & x². with probability at least 5/6.
The algorithm uses O(EE me)/E?) samples from P.
Theorem 1.4 Daskalakis et al. 22188 Theorem 1]). There exists an efficient algoritim which, given samples from distribution P and a known reference distribution Q over [nz], as well as a distance parameter e E (0, 1.. distinguishes between the cases (i) (P, Q) & E² and (ii) du (P, Q) > with probability at least 5/6. The algorithu uses (n (e?) samples from P.
Lemma 1.5 (atuu et al. [2001] Proposition 1]). Let be discrete distribution supported on [n] x [m]. with marginals P1 and Pz. Then, we have minq, Q= drv(P, (PP, Q1 @ Q2) 2 hdrv & P2). where the minimum is taken over all distributions Q1 over [n] and Q2 over [m].
2 The (224/22/e²) Lower Bound
In this section, we prove our main technical result: lower bound on the sample complexity of testing whether a degree-d Bayes net is product distribution. In the interest of space, we omit some details of the derivations: the interested reader can find them in Appendix A
Theorem 2.1. Let d & c logn, n, where e > 0 a sufficiently small absolute constant. Then, testing whether an arbitrary degree-d Bayes net over {0, 13" is product distribution or is from every product distribution requires (2(2d22m/2) )/²)) samples.
This theorem considerably generalizes the lower bound of M(n/s²) established Canonne et al. (2220) for the case of E (d = 1). To establish our result, we build upon (and considerably extend) their analysis; particular, we will rely on the following "mixture of trees" construction, which can be seen as a careful mixture of (2d-1 of) the hard instances from the lower bound of [Canonne et al. 2020 Theorem 14]. Figure I shows an illustrative example of our lower bound constructions.
Notation. Throughout, for given n, d, e, we let N = n d + (without loss of generality assumed to be even), D == 2d-1 0 Vn and
1 + 46
1+ (48)2 21
1 (46)4
20
48'
1- (45)3*
1 (45)
Definition 2.2 (Mixture of Trees). Given parameters 0 < d < n and 8 E (0, 1], we define the probability distribution D,,d, over degree-d Bayes nets by the following process.
'Wiiee this can be better visualized as a forest, we use the term "tree" to refer to the structure of degree-1 Bayes nets. Technically, it still factorizes Bayesian path (tree), but not all edges necessary.
5

---

1. Choose a perfect matching À of [N] uniformly at random (where N = = n dd 1), i.e. set of N/2 disjoint pairs;
2. Draw i.i.d. ji.....: dD uniformly at random in {0. 1)
3. For & [D], let PE be the distribution over {0, 1 defined as the Bayes net with tree
structure X, such that if D (i.j) E then the corresponding covariance between
variables X;, Xj is
Cov(Xi, = (-1)"A
4. Let the resulting distribution PA, over {0, 10 10hb be
1 E (m) (6..
(x) =
where :: [0, [D] the indexing function, mapping the binary representation to the corresponding number.
That is, Dn,d,s is the uniform distribution over the of degree-d Bayes where the first d - 1 coordinates form a "pointer" one of the 2d-1 tree Bayes nets sharing the same tree structure (the matching A), but with independently chosen covariance parameters (the D parameters :....:pD)
Xx
XA
Xxa
X
X Pat (.7/2
X
Figure I: A depiction of our lower bound construction, where the arrows are the edges of the underlying Bayes of the distributions, rest the nodes are on. We write A [1] ==
net. The first (d 1) nodes be seen (d 1)-bit string that acts pointer
i.e. the value of the first nodes encodes which distribution and [2[ = j when A = j). There are two sources of randomness in the construction. The first one is the random matching on the 2/2 pairs represented in graph in the form of (Ax [1], (2) ..... (AN/2 [1), (2)2
which independent of the particular configuration Xt..... X. takes. The second one is the covariance parameters between each pair; these parameters are randomly and independently chosen for each configuration (in total 2 of them) the first nodes. Color (yellow and blue) marks how the value of covariance parameter fee& in cach pair depends on the first d nodes' configurations as well as the matching parameter k.
With this construction in hand, Theorem 2.1 will follow from the next two lemmas:
Lemma 2.3 (Indistinguishabiitt).. There exist absolute constants c, C. > O such that the following holds. For 2(1) & d & clog n, m-sample algorithm distinguish with probability at least 2/3 between a (randomly chosen) mixture of trees P ~ D Dn,de/// and the uniform distribution over (0,1)", unless m C. 22/2n/e²
Lemma 2.4 (Distance from product). Fix any 0 & d & and E (0. With probability at least 9/10 over the choice of P ~ Du,dee//a is ((E)-far from every product distribution on {0, 1)"".
Note that this guarantees farness from every product distribution, not just from the uniform distribution. We focus on the proof sketch of Lemma 2.3 in the next subsection, and defer the proof of Lemma 2.4 to the appendix A.2 Throughout, fix d, and E (0, 1].
2.1 Sample Complexity to distinguish from Uniform (Lemma
Proof sketch. Following the original analogous analysis, we first use Ingster's method to upper bound square TV distance in 4 and after a series of algebraic calculations, we arrive at 66. This is where we improve upon the original analysis by substituting a tighter upper bound 77. This leads us to some of the most technical portions of the paper. To upper bound the inner expectation of ( we use Lemma 2.5 to bound the unwieldy expression (average over 2, and raised by m) by an expectation of a miltinaaial variable ő in the expression I I some careful analysis and some tools on MGF (Moment Generating Function) of Binomial and
c2sh(2a;,,) in (9): then, with

---

Multinomial from Section B we can upper bound the latter expression in 12 which finally gives us the sample complexity lower bound.
Details. We now proceed with the proof of Lemma 2.3 starting with some convenient notations; some of the technical lemmas and facts used here are stated and proven in Appendix B Let 0
(X, Mi,.... (Mg--1) -Mge--))MMe--) ). where each [4k E {=1)///2 and let Po be the distribution for the mixture of trees
construction from Definition 2.2 the quantity
The following denotes the matching count between (2, 11) and x as
c(), 2)) = ((,,)) E (d.... .id.....,]?:: 31 < k < 2 Au = (2.5) and (-1) = ( (-1)
We will also introduce an analogous quantity with an "offset", for Fch = (Id..... ..a) referring exclusively to the child nodes of z (i.e., the last N nodes, which are the "children" of the first "pointer nodes" in our construction).
Cal Ichu) =
((.,5) (d.....
< 2 Av - (i-d+1, - d + 1) and (-
=
To denote the parameters of the "mixture of trees", we write 6; == (2, 14) (for i E [D]), recalling that the matching parameter À is common to all D tree components. Since each μ4; corresponds to one of the values of (#1....,zz Id-1) E {0, 1] 10 we as before use :: {0, 1]2-1 + [D] to denote the indexing function (so that, for instance, ((x1 = .... = Id- = 0) = 0). We finally introduce three more quantities, related to the matching and orientations parameters across the 1) components of the mixture:
A0, = {(8,t) E (1....,,//)"" A = X(4), [+] =4(0]
(common pairs, same orientation)
BB, = {(stt) E N/233. {[s] X(t)., [s[s] # nΔ[t)}
(common pairs, different orientation)
Co = (AUX)
(pairs unique to 8 or 6')
For ease of notation, we define A, == Ao, 0; B, = o and C, == 0e ; and note that C, C1. as it only depends on À (not on the orientation p4).
To prove the indistinguishability, we will bound the squared total variation distance (or equivalently, squared ( distance between the distributions of m samples from (the uniform mixture of) Pa and U by small constant; that is, between Q Eg [ and & From Ingster's method (see, e.g., AAchary et al., 2020, Lemma III.8.). )) by using chi-square divergence as an intermediate step we get
|1Q T@m |/2 < (Q, U (m)) Eg, [[1 + 700, 0'))" -1
(4)
] In order to get handle on this quantity T0,00', we start by writing the expression for the density Po. For any x E {0, 1)", recalling Item of Definition 2.2 Po(x) 2 (1 + 48) (8)c(Aii))))))))
where T(0, 0¹) = -Eew [( (ola)))(()) (
46) ) (()...c)))))))
Substituting this in the definition of we get an expression depending on 20 == 1+45
1-45 and the
brbabillity-eneratin function (PGF) of Cet (A, μ, æ). Observing that, as UN and for fixed X, we have that cch (A, 1) Bin( 2 1). we can then massage this expression to get
[
D
|A,
1 T,,, = D
Σ 1=1
(1- 18)N
+ 2 B, 20
II
E Eaw
(5)
2
a1:oo.134
where the product is taken over all cycles in the multigraph Gø.æ induced by the two matchings; and, given a cycle a, B(a)) is the probability distribution defined as follows. Say that a cycle a is even (resp., odd) if the number of edges with weight 1 along is even (resp., odd); that is, cycle is even or odd depending on whether the number of negatively correlated pairs along the cycle is an even or odd number. If a is even cycle, then B((r) is Binomial with parameters o and 1/2, conditioned on taking even values. Similarly, if a is an odd cycle, B(or) is Binomial with parameters |a| and 1/2, conditioned on taking odd values. It follows that Eg Ba~B(=) is given by the following expression.
a even] = (1+*0) (1+)(12))) |ol
={
E. Bin(lo)))))
if a is even
E Ea-~B(0)(30)
20
E BanBin [2 a odd] (1+z | |ol
if a is odd
2
7

---

Denote Se,i = (e, 8 = for E cycle(0,, 0(): |o| > 4, is even), and similarly So.s for odd cycles. We would drop X, p or i, when clear from context. We first expand E Ba- [aß] as follows:
(1+ za)
II 0:/7/34
Ba-8())[81 =
(L+ (-466))))
II (1 (-48)l01) dES,
(6)
2/
oES.
We now improve upon the analogous analysis from [Canonne al.
2020 Claim 12] obtain better
upper bound for the remaining terms; indeed, the bound they derived is eO(*"/n) /n), which was enough for their purposes but not ours (since it does not feature any dependence on d). Crucially, we instead derive the below inequality whose proof can be found in Appendix C.T
II (1+ aES,
II (1 (1- (-45) & o
II (1+(-4)))
II (1-(-40)) (7)
oES.:1o/=4
oES=:oo==1
for some absolute constant d' > We will have e and this restriction on D is satisfied for the regime of parameters considered in our lower bound, Ollog n). Letting = |Ail + |Bi] < N/2 and 21 = 1+(4
/Na/2 ce-mme//a/a
128me ((VDn) if D O(n/E*).
with
6 and some calculations,
(13)
E [11 + =00,0))")
(DD D
'T
= =AA (1 (1- (40) (4 F
Frl II (1+ (-45)oo) II (1 (-46))01) oES.
oES...
Fix pair X, X:: we have that the |A,l's are i.i.d. Bin( R, 1/2) random variables. We now introduce R' = |ai |oil 4H1 Ho; |o, = 4}/, which is the random variable denoting how many cycles have length exactly 4. In particular, we have R' < T. since Eo:/o/34 = |C| < N; more specifically, we have R' < N-2R < 4. Further, define '6 as the number cycles length 4 which have an even total number of negative correlations; that is, the number of cycles such that ps; P4 impose either 0, 2, or 4 negatively correlated pairs along that cycle.
N.
Since μ. pe are uniformly distributed, being odd Bin R', 2). Moreover, while Л₁ and A; both depend Pt: p4, they by definition depend on disjoint subsets of those two random variables: thus, because each correlation parameter chosen independently, we have that n; and A, are independent conditioned (R, R'). Now, recalling our setting of 22
each has probability 1/2,, and thus K2
(+8)) and fixing realization of R, R', we have (46)
TH
E
1
1
Σ
21
II
(1+
(40)*)
II
(1-(48)+) (1- (45)+)
D
D
1
= - (4 R Eg
1
< (1 (1- (48)
21
mR
E.
(cosh(2a,00)) 02), ( (coosh(2a,
(9)
where g follows from the following lemma:
Lemma 2.5. There exists an absolute constant de Rs 0.96 such that the following holds. Let K 3.
and Ri,..., Rg be integers, and 81,...,5y E (0, 8u]- Suppose that K5,1.... K,,, ~ Bin Rí, 1)
are i..dd and mutually independent across 1 < j < K, and 2j ==
1+4; 1-8, Then
T-8,"
E 2
m
11 71 Ex
II cosh (20,0))
where (ai, aD) follows multinomial distribution with parameters m and 1/D....,1/D)

---

We now focus on the expectation on the right (last factor of the RHS of (): using that cosh u < min(e" ("0 e²)) for b O, it can be shown, setting A == 1/62 n/E2 that
Ex II (ccsh(2
E
80, RI [A,2A
E
E
4n
(10)
where the threshold A was chosen the value for which the term realizing the minimum changes. We first bound the product of the last two expectations:
1/4
1/2
1/4
1/2
E
80 5th RI
E
II
Aa280 K
E
II
85 minn(??
E
II
e
to 20
R'
[E min( A 22)55"18 D/4 (/ D//22
(11)
< exp 328 m²
exp 328 m²
D R
D Rc)
(12)
where we applied negative association (see, e.g., Dubhashi and Ranjan 1996 Theorem 13]) on
both expectations for I and then got (12 by Lemmas [.. and B.3 (for the latter, noting that
Im 2 mR < 1/16; and, for the former, assuming with little loss of generality that 1/(42))). Applying Lemma to the first (remaining) factor of the LHS above as 86 R & 4 and D b 9(L). we get
D II e 80, R
1/4
D
1/4
D
1/2
E
So
((
E
< (1 (1+
o(1) o1+)
ex2(3 (32(*2R)) R).
recalling that R' < N/4 < n/4, and our assumption that m & C'v/Dn/e Combining and C. what we showed is
Eg.0 (1++ < (1 o(1))e
128 m²?
vou
(1 (40))3)))mR() (
BAN
(1
2 Bn 320
mR my
(1 + ((1)) 288-C'
228.C'E,,' ( 220
where the equality follows from the definition of 21, 22. To conclude. we will use the fact that, for every & > 0, Pr[R > k]] < g, which was established in Canonne et al. (2020) p.46). By summation
by parts, one can show that this implies E [ < 1+(1-e-))
a-u 1 1 1) for any
O, and so, in our case, Eg,e' [(1+ (0,)0)))))))) < (L+ (1+(1---32)) (e 2202 1))
In particular, the RHS can be made arbitrarily close to 1 by choosing a small enough value for the constant C" (in the bound for m)) By (4) this implies the desired bound on ||Q - @ ? and thus establishes Lemma
3 Upper Bound for Independence Testing
In this section, we establish the upper bound part of Theorem stated below:
Theorem 3.1. There is an algorithm (Algorithm) 7 with the following guarantees: given E (0, and sample access to unknown degree-d Bayes net P, the algorithm takes 24224 log(n) /s²) samples from P, and distinguishes with probability at least 2/3 between the cases (i) is a product distribution, and (ii) P is at total variation distance at least from every product distribution.

---

Algorithm 1: Independence testing for degree-d Bayes net
Input: Independent samples from a degree-d Bayes net P over (0, 1,"1,, E (0,1)
Set 8 1(111)
v2n(I+v2+T)) and O 24/3 log }
Take a multiset S of m samples from P. where å + 1/(3 (d+1))
for every subset T - [n] of d 1 nodes do
/ We can generate one sample from Pr given one from P Use the samples from S to generate m i..d. samples from Pr Call Algorithmm with distance parameter g' and failure probability 6, using the m samples from Pr /* This is over {0, 1jd-1
if all (d"11) lests accepted then return accept
return reject
As discussed in the introduction, the key components of our algorithm are performing the testing in Hellinger distance, in order to the subadditivity result of Daskalakis and Pan (017]: and using as subroutine an independence testing algorithm under Hellinger distance. As no optimal tester for this latter task was known prior to our work, our first step is to derive such algorithm by adapting the beesting-by-eearinng framework of AchAcyy et al. [201]]. We emphasize that, in view of the relation 1 ddiy < di < drv. this is a strictly stronger statement than the analogous known O / sammle algorithm for testing independence under total variation distance (Diakonikolas and Kane 2016 Acharya et al. 2015). which only implies an 0(2n/2/E*) sample complexity for testing independence under Hellinger distance.
Lemma 3.2. There exists an algorithm (Algorithm 2 with the following guarantees: given a param- eter e E (0, 1] and sample access to an unknown distribution P over {0, 1)", it takes ((2n/2 /s²) samples from P, and distinguishes with probability at least 2/3 between the cases (i) P is a product distribution, and (ii) P is at Hellinger distance at least from every product distribution.
Algorithm 2: Hellinger independence testing for general distributions
Input: Independent samples from the target distribution over {0, 1)". (0, 1]
Set my + On/=²), ) and m2 ((2n/2/8)) /sa)
Take two multisets S₁ and S₂ of samples with size my. m2 respectively from P
P t call the algorithm of Lemma 1.3 with the samples from S
Call the tester in Theorem 1.4 with samples from S2, to test P with reference to i with distance tester accepted then return accept
return reject
We will next require the following lemma, whose proof is deferred to Appendix
Lemma 3.3. Let P be a distribution on 10, and P = (T ... @ (n P) be the prod- uct of marginals of P. Denoting by Q the set of all product distributions on {0, 13", we have mingeo du (P, Q) 2 T+ dn, P').
We now have all the elements to prove Theorem 3.1 As discussed in the introduction, the idea is the following: when P is a product distribution, then the distribution induced by p' on any subset of d + 1 nodes is still a product distribution. However, by the above localization Corolloary 1.2 when P is far from every product distribution, we can localize the farness between P and Q in one of the subsets of d + 1 nodes. We also know that P', the product of marginals P. is not too bad of an approximation to the closest Q in the product space as suggested by Lemma 3.3 Thus, testing independence using P' as proxy and paying extra factor of O(d) to compensate in accuracy suffice. Details can be found in Appendix C.I
Acknowledgments. Yang would like to thank Vipul Arora and Philips George John for the helpful discussions on the lower bound analysis; and Vipul, specifically, for providing valuable feedback on the manuscript. Arnab and Yang were partially supported by an NRF Fellowship for Al (NRF- NRFAI11-200 12011-0002), This work was done in part while Arnab was visiting the Simons Institute for the Theory of Computing.
10

---

References
Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath. Optimal testing for properties of distributions. In NeurlPS, pages 3591-3599, 2015. Preprint available at arXiv: 100.05557.0 .05952.
Jayadev Acharya, Clément L.. Canonne, and Himanshu Tyagi. Inference under information constraints
I: Lower bounds from chi-square contraction. IEEE Trans. Inform. Theory, 66(12):7835-7755 2020. ISSN 0018-9448. doi: 10.1109/111200000024440 URL https: http::://doiooor///// 1109/TIV 2020. 3028440
/
Michal Adamaszek, Artur Czumaj, and Christian Sohler. Testing monotone continuous distributions on high-dimensional real cubes. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 56-65. SIAM, 2010.
Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, and Ning Xie. Testing k-wise and almost k-wise independence. In Proceedings of the thirty-ninth annual ACM symposium Theory of computing, pages 496-505, 2007.
Tugkan Batu, Eldar Fischer, Lance Fortnow, Ravi Kumar, Ronitt Rubinfeld, and Patrick White. Testing random variables for independence and identity. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 442-451. JEEE, 2001.
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep Meel, and N. Vinodchandran. Efficient distance approximation for structured high-dimensional distributions via learning. In NeurlPS, 2020.
Arnab Bhattacharyya, Sutanu Gayen, Saravanan Kandasamy, and NV Vinodchandran. Testing product distributions: A closer look. In Algorithmic Learning Theory, pages 367-396. PMLR, 2021.
Eric Blais, Clément Canonne, and Tom Gur. Distribution testing lower bounds via reductions from communication complexity. ACM Transactions on Computation Theory, 11(2):1-37, apr 2019. doi: 10.1145/3305270.
Clément Canonne. survey on distribution testing: Your data is big. but is it blue? Theory of Computing, pages 1-100, 2020.
Clément I.. Canonne, Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Testing bayesian works. IEEE Trans. Inf. Theory, 66(5):3132-31700 2020. Preprint available at arXiv: 662.03156
Constantinos Daskalakis and Qinxuan Pan. Square hellinger subadditivity for bayesian networks and its applications identity testing. In COLT, volume 65 of Proceedings of Machine Learning Research, pages 697-703. PMLR, 2017. Preprint available at arXiv:1612.033
Constantinos Daskalakis, Ilias Diakonikolas, and Rocco A Servedio. Learning k-modal distribu- tions via testing. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms,, pages 1371-1385. SIAM, 2012.
Constantinos Daskalakis, Gautam Kamath, and John Wright. Which distribution distances sublinearly testable? In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2747-2764. SIAM, 2018.
Constantinos Daskalakis, Nishanth Dikkala, and Gautam Kamath, Testing ising models. IEEE Trans. Inf. Theory,
2019.
Ilias Diakonikolas and Daniel M Kane. A new approach for testing properties of discrete distributions. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 685-694. IEBE, 2016.
Devdatt Dubhashi and Desh Ranjan. Balls and bins: A study in negative dependence. RANDOM STRUCTURES & ALGORITHMS, 13:99-124, 1996.
Nir Friedman, Michal Linial, Iftach Nachman, and Dana Pe'er. Using bayesian networks to analyze expression data. Journal of Computational Biology, 7(3-4):60i-62) 2000. doi: 10. 10.1099/1065277075500009999 PMID: 11 11108881.

---

Timothy S Gardner, Diego Di Bernardo. David Lorenz, and James J Collins. Inferring genetic networks and identifying compound mode of action via expression profiling, Science, 301(5629): 102-105, 2003.
Oded Goldreich, Shari Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM (JACM), 45(()) 1998.
Yi Hao and Ping Li. Bessel smoothing and multi-distributtin property estimation. In COLT, volume 125 of Proceedings of Machine Learning Research, pages 1817-1876. PMLR, 2020.
Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan R. Ullman. Privately learning high- dimensional distributions. In COLT, volume 99 of Proceedings of Machine Learning Research, pages 1853-1902. PMLR, 2019.
Erich Leo Lehmann, Joseph Romano, and George Casella. Testing statistical hypotheses, volume Springer, 2005.
Reut Levi, Dana Ron, and Ronitt Rubinfeld. Testing properties of collections of distributions. Theory of Computing, 9():2255-347 2013.
Matey Neykov, Junwei Lu, and Han Liu. Combinatorial inference for graphical models. The Annals of Statistics, 47(2):795-827, 2019.
Jerzy Neyman and Egon Sharpe Pearson. IX. on the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, (06))220 -37, 1933.
Liam Paninski. coincidence-based test for uniformity given very sparsely sampled discrete data. 2008.
IEEE Transactions on Information Theory,
Jie Peng, Pei Wang, Nengfeng Zhou, and Ji Zhu. Partial correlation estimation by joint sparse regression models. Journal of the American Statistical Association, 104(486):735-466 2009.
Ronitt Rubinfeld. Taming big probability distributions. XRDS: Crossroads, The ACM Magazine for Students, 19(1):24-28, 2012.
Ronitt Rubinfeld and Rocco A Servedio. Testing monotone high-dimensional distributions. Random Structures & Algorithms, 34(1):24 44, 2009.
Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252-271, 1996.
Martin J. Wainwright and Michael I. Jordan. Graphical models, exponential families, and variational inference. Found. Trends Mach. Learn., 1(1-2):1-305, jan 2008. ISSN 1935-8237. doi: 10.1561/ 2200000001. URL http://......00011..111...61101.
12


Reviews:
[{"review_id": "U_qQi_-erNE", "reviewer": "Reviewer_wLb1", "summary": "This study focuses on the independence test where a given bayeisan network distribution is a product distribution or it is epsilon-far in total variation distiance from any product distribution. This study shows that the required sampale size is O(2^{d/2} n/ epsilon^2) rather than exp(n) using the sparsity of a directed acyclic graph. \n", "questions": "1. Unclear main problem: This paper states that the main problem is whether the joint distribution of a Bayesian network is a production distribution. However, as stated on the page 4 in the paper, it satisfies the factorization property, and hence, the joint distribution is a product distribution. It would be better to clarify the focused problem. I am not sure if I understand correctly, is the proposed tester can distinguish P from a bayesian network with X_1 -> X_2 -> X_3, and Q from a bayesian network with X_1 <- X_2 <- X_3?\n2. This paper does not assume the known structure. However, I do not understand how this study can apply the unknown ordering of a graph, which is in general not solvable. \n3. This paper misuses the term degree as in-degree. This makes the paper is really unclear. The maximum indegree, d_{in} = \\max_{j \\in V} | \\Pi_j |,  the maximum degree, d = \\max_{j \\in V} | \\Pi_j \\cup {child of j} |,, and the maximum degree of the moralized graph is d_{m} = \\max_{j \\in V} | \\Pi_j \\cup {child of j} \\cup {spouse of j} |. \n4. It would be better to discuss that how to a given a distribution is from a sparge Bayesian netowrk?\n5. For the enhanced clarity, the theoretical findings would be better to be confrimed through numerical experiments.  ", "limitations": "None.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strenghts: Better sample complexity. \nWeakeness: Some unclear statements. ", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "JTWXV-H20F", "reviewer": "Reviewer_Fnfu", "summary": "This paper shows that for a distribution $P$ over $n$ binary variables such that it factorizes according to an underlying degree-$d$ Bayesian network, testing that $P$ is a product law versus $P$ is $\\varepsilon$-away from any product law in total variation, requires $O(2^{d/2} n / \\varepsilon^2 )$ samples. Further, the bound is shown to be tight. ", "questions": "1. The problem studied should be better motivated. \n\n(i) Why focused on testing complete independence (i.e., product measure)? Perhaps elaborate on *testing graphical structure* --- the problem is testing that the underlying Bayesian network has no edge, I suppose? \n\n(ii) Why focusing on the total variation distance? Does the result also extend to the problem posed in Hellinger distance?\n\n(iii) Does this problem bear any practical implication? \n\n2. Relation to Daskalakis et al. (2019) for Ising models. \n\nThe relation is dismissed as \"Ising models and Bayes nets are incomparable modeling assumptions\". But certain Ising models are Bayesian networks, e.g., when the undirected graph is chordal. Perhaps, at least for these cases, it is worth more clarification?\n\n3. Total variation vs. Hellinger\n\nThis issue arises again when reading the high-level description of techniques in $\\S$1.2, where the challenge seems to be that while previous testing algorithms are developed for total variation, the localization result in Daskalakis and Pan (2017) is in Hellinger. The authors chose to stick with Hellinger and devised a testing algorithm for Hellinger. \n\nMy question is about the alternative: can the localization result be extended to the total variation?\n\n4. Definition 2.2 is confusing. \n\nI am confused by the following. \n\n(1) $\\lambda$ is disconnected (as a perfect matching) but called a \"tree\". \n\n(2) The expression for $\\text{Cov}(X_i, X_j)$ does not make sense to me: $(-1)^{\\mu_{l,k}} = (-1)^{\\pm 1}$ is always $-1$?\n\n(3) What does \"pointer\" mean here?\n\nIn general, it is very difficult for me to parse how the construction works. For better clarity, I would suggest moving the text description from page 3 to follow the definition. Or, even better, illustrate with an example. \n\n5. The proof sketch in $\\S$2.1 is too dense. \n\nIt should be reduced and simplified to make it a readable **sketch**. Meanwhile, the paper should end properly with some discussion, which is currently impossible due to space limit. ", "limitations": "I do not foresee any potential negative societal impact of their work.\n\nI have listed my suggestions in the previous section. ", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n1. The paper solves the problem studied: the bound is tight.\n2. The problem and techniques are connected to and built upon many recent developments, e.g., Diakonikolas and Kane (2016), Daskalakis and Pan (2017), and  Canonne et al. (2020). \n3. The proofs seem solid. \n\n### Weakness\n1. The authors should better motivate the problem studied, e.g., why focusing on testing complete independence, why using the total variation, etc. \n2. The presentation of certain sections can be improved. ", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9_yfcEaLaut", "reviewer": "Reviewer_j9Gv", "summary": "The paper studies the independence testing problem. Given samples from a distribution $P$ over $n$ binary random variables, one should detect where all $n$ random variables are statistically independent or not (i.e., at least $\\epsilon$-far in TV from any product distribution).\n\nFor a general $P$'s, the sample complexity is in the order of $\\exp(n)$. The main contribution in this paper is to show that when $P$ is a Bayesian network with in-degree at most $d \\ll n$, the sample complexity is in the order of $n \\exp(d) / \\epsilon^2$.", "questions": "I would appreciate if the authors would address the following:\n\n1) Please comment on why the problem would be interesting from the viewpoint of applied Machine Learning.  Specifically, why a Machine Learning practitioner would like to run the independence testing algorithm?\n\n2) Learning the structure of Bayesian networks is useful for understanding independence between variables (e.g., genes, brain regions, etc.) in exploratory research. Why are Bayesian networks useful in the independence testing problem (besides the fact that it leads to a better sample complexity)?\n\n3) Besides the bounds on the MGF of squared binomials and the result for the Hellinger distance. Could the authors point out to other specific novel technical results (lemmas, equations, etc.)? Any argument related to the challenge of solving this problem as well as the technical novelty will be highly appreciated.\n\n4) Please clarify if the problem/algorithm assumes that data is observational, or whether the algorithm needs to perform interventions (fixing some variables and sample other variables). See for instance \"Use the $m$ samples from $S$ to generate $m$ i.i.d. samples from $P_T$\" in Algorithm 1.", "limitations": "As the paper is theoretical, there is no clear and direct societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- In section 1.2, I truly appreciate that the authors spent a good amount of space comparing their results with relatively simpler alternatives, but that have worse sample complexity than their result.\n- I also appreciate how the authors provide some intuition about the novelty of the techniques used in this paper, specifically in Lines 114-120 and Lines 147-156.\n- The theoretical result seem sound and thorough.\n\nWeaknesses:\n- The theoretical result is interesting, but the (possible) Machine Learning application is unclear.\n- It is unclear (at least to me) whether the problem/algorithm assumes observational data or it requires interventions.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept