Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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).

For 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$.
strengths_and_weaknesses: Strengths:
- 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.
- 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.
- The theoretical result seem sound and thorough.

Weaknesses:
- The theoretical result is interesting, but the (possible) Machine Learning application is unclear.
- It is unclear (at least to me) whether the problem/algorithm assumes observational data or it requires interventions.

questions: I would appreciate if the authors would address the following:

1) 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?

2) 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)?

3) 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.

4) 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
strengths_and_weaknesses: ### Strengths
1. The paper solves the problem studied: the bound is tight.
2. 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). 
3. The proofs seem solid. 

### Weakness
1. The authors should better motivate the problem studied, e.g., why focusing on testing complete independence, why using the total variation, etc. 
2. The presentation of certain sections can be improved. 
questions: 1. The problem studied should be better motivated. 

(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? 

(ii) Why focusing on the total variation distance? Does the result also extend to the problem posed in Hellinger distance?

(iii) Does this problem bear any practical implication? 

2. Relation to Daskalakis et al. (2019) for Ising models. 

The 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?

3. Total variation vs. Hellinger

This 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. 

My question is about the alternative: can the localization result be extended to the total variation?

4. Definition 2.2 is confusing. 

I am confused by the following. 

(1) $\lambda$ is disconnected (as a perfect matching) but called a "tree". 

(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$?

(3) What does "pointer" mean here?

In 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. 

5. The proof sketch in $\S$2.1 is too dense. 

It 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.

I have listed my suggestions in the previous section.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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. 

strengths_and_weaknesses: Strenghts: Better sample complexity. 
Weakeness: Some unclear statements. 
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?
2. 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. 
3. 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} |. 
4. It would be better to discuss that how to a given a distribution is from a sparge Bayesian netowrk?
5. For the enhanced clarity, the theoretical findings would be better to be confrimed through numerical experiments.  
limitations: None.
review_title: null

Meta-review: metareview: The manuscript studies the independence testing problem, given samples from a distribution over several binary random variables. While the sample complexity is exponential (in the number of variables), this paper shows that when the distribution is a Bayesian network with small in-degree, the sample complexity is linear.

All reviewers asked for a clarification in the motivation, and some reviewers asked for comparison to literature and/or possible alternatives. The authors addressed this well during the rebuttal phase. I recommend adding this to the camera-ready version of the paper, as well as other discussions and clarifications raised by all the reviewers.
confidence: Certain
Decision: Accept