- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper introduces BEGIN, a framework that characterizes conditional independence in binary and bit-encoded categorical data through zero blocks of a generalized Schur complement, including distributions with structural zeros. It develops graphical interpretations, a continuous-variable extension through increasingly fine binary expansions, and a maximum-interaction test with matching sample-complexity bounds under specified sparse alternatives. Validation consists of simulations evaluating power and computation, and an analysis of categorical Mushroom data.
Critical strengths
-
Exact and interpretable characterization. Theorem 3.2 and Proposition 3.3 connect conditional independence to a zero residual covariance block, whose entries have explicit interpretations as weighted conditional covariances. Accommodating structural zeros and singular encodings makes this characterization applicable to general finite categorical distributions.
-
Matching sparse-testing bounds. Under the stated design and sparsity assumptions, Theorem 4.1 establishes matching sample-complexity upper and lower bounds. This provides a substantive theoretical justification for Max BEGIN’s effectiveness against sparse interaction alternatives.
Critical weaknesses
-
Insufficiently established novelty. The characterization builds on complete binary interaction bases, existing residual-covariance criteria for conditional independence, and Schur complements. Moreover, under the simulation design, Max BEGIN’s coordinates coincide with fixed-weight WGCM residual numerators. The paper does not sufficiently distinguish its conceptual advances from these existing ingredients, making the significance of its methodological contribution difficult to assess.
-
Limited coverage of the testing guarantees. The optimal-power result requires a known conditional assignment law, independent fair conditioning bits, and sparse alternatives in a prescribed dictionary. It does not cover the within-cell permutation procedure used when the assignment law is unknown. The continuous extension provides a population characterization and approximation bounds, but no depth-selection rule or calibration accounting for discretization bias. Given prior work on CI testing from discretized continuous observations [1], the paper should clarify how its extension differs in assumptions, inferential targets, and statistical guarantees.
[1] Sun et al. A Conditional Independence Test in the Presence of Discretization. ICLR, 2025.
Questions for authors
-
Could you clarify which results constitute nontrivial advances over existing complete-function CI criteria, BELIEF, and WGCM?
-
Could you also report the Quadratic BEGIN and Interaction OLS dCRT comparisons already implemented in the supplementary code and explain their omission from the manuscript?
2 comments
(Continue from the previous comment) W2. Scope of the guarantees. Which conclusions require a known law, fair bits, sparsity or a choice of depth?
For i.i.d. observations of scalar binary endpoints and a known conditional law of given , the level guarantee holds for any distribution of . The matching sample order assumes independent fair conditioning bits, at most nonzero coefficients in a prespecified dictionary of size , and signal energy at least . The stated range is and for fixed .
You are right that Theorem 4.1 does not cover the within-cell permutation procedure. Under i.i.d. sampling with fixed encodings, that procedure controls the level of each fixed test in finite samples without knowledge of the assignment law. A matching power bound remains open. The data analysis in the revised Section 6 uses rank cutpoints estimated within each subset. Exact calibration then requires the codes of the permuted endpoint to be exchangeable within each cell conditional on the conditioning codes and the other endpoint codes. Appendix O.4 reports the estimated sample sizes needed for 80% pooled power on measurements from the light tunnel of Gamella, Peters and Bühlmann (2025).
The dyadic approximation theorem (submitted Theorem 3.7, revised Theorem 3.6) is a population result. At a fixed depth, the test targets independence of the encoded endpoints given the encoded conditioning variables. Choosing the depth from the data, and calibrating the original continuous null when the conditional law is unknown, remain open. For bivariate unconditional independence, BET suggests scanning depths up to (Zhang, 2019, Section 4.5). In the revised Section 6.2 we report four, five and six bits side by side instead of selecting a depth.
Sun et al. (2025) study a different observation model. They observe discretized versions of latent continuous variables and test conditional independence of the latent variables under a nonparanormal model, with asymptotic calibration. BEGIN assumes no parametric family, targets the observed discrete or encoded variables, and has finite-sample calibration under the exchangeability condition above.
Q2. Omitted comparisons. Why did the submission omit Quadratic BEGIN and Interaction OLS dCRT?
We initially conducted the following experiment. Max BEGIN had higher empirical power in this setting, so we emphasized it in the main text. The table below shows the rejection rates of the three tests under a one-interaction alternative.
Method
Power
Max BEGIN
0.980
Quadratic BEGIN
0.080
OLS dCRT
0.080
Settings for the table: and twelve conditioning bits to are independent fair signs, and is a sign with , with . Each test scans all products , including the constant. Max BEGIN takes the largest absolute mean of , Quadratic BEGIN sums the squares of these means, and OLS dCRT is the squared norm of the fitted values when is regressed jointly on all . Each test is calibrated by 199 redraws of from its known fair law, with and held fixed, and rejects at level 0.05. Each entry is a rejection rate over 200 datasets.
Space constraints also led us to focus on Max BEGIN, for which Theorem~4.1 gives a sparse-power guarantee. For the 37-product comparison in the originally submitted code at , the powers of Max BEGIN, Quadratic BEGIN and Interaction OLS dCRT were , and with one active interaction, and , and with sixteen. These results illustrate how relative power depends on the alternative. Under a sparse setting, Max BEGIN is more sensitive and powerful. For this paper we would like to focus on detecting sparse dependence signals. While Max BEGIN doesn't perform as well as the other tests in the other denser scenario, this illustrates a well-known point that no single test is uniformly most powerful against all alternatives in nonparametric dependence testing.
We thank the reviewer for the careful assessment, and for asking how BEGIN relates to existing criteria and to WGCM, what the guarantees cover, and how the omitted comparisons perform.
W1 and Q1. Novelty. How does BEGIN relate to complete-function criteria, BELIEF and WGCM?
Daudin (1980) and Fukumizu et al. (2008) characterize conditional independence through residual covariances over complete function classes. BEGIN makes that class explicit and finite for binary vectors. Theorem 3.2 gives the criterion S[L,R]=0 on the Schur cross block for two multivariate endpoints, valid for every joint pmf, including singular categorical encodings. Proposition 3.3 gives each entry in closed form, as a signed sum of cellwise conditional covariances weighted by the cell probabilities. The products label the entries to scan and identify the contrasts behind a rejection.
The conditional-mean expansion in our Theorem 3.2(b) comes from BELIEF (Brown, Zhang and Meng, 2025, Lemma 2.2). Its Theorem 2.1 also gives the endpoint-product criterion when applied within each supported conditioning cell. BEGIN identifies the conditioning group as the intersection of the groups generated by the bits on the two sides and gives the corresponding Schur cross block. In particular, with no conditioning variables, Theorem 3.2 reduces to BELIEF Theorem 2.1, and for a scalar response BELIEF Theorem 2.5 gives a related slope criterion under full predictor support. Its Theorem 2.6 gives a precision-matrix criterion under an additional interior conditional-mean condition.
For WGCM, take scalar signs A,C and a fixed product weight BΓ. A BEGIN coordinate is
=\mathbb E\left[B_\Gamma\operatorname{Cov}(A,C\mid B)\right].$$ As you note, the displayed quantity is the population moment targeted by fixed-weight WGCM. More generally, with the same endpoint features and conditioning weights, fixed-weight WGCM recovers the Max BEGIN. In the simulations of Section 5, both endpoints are scalar signs with known conditional means of zero, so the empirical numerators also agree for each matched weight. The test statistics and $p$-values can still differ because WGCM studentizes each score and the two tests may use different calibration methods. For binary data, BEGIN makes three novel contributions. A complete characterization of conditional independence. The group structure explains why these particular features and weights suffice. The groups of bit products generated by $(A,B)$ and $(B,C)$ share precisely the products generated by the conditioning bits $B$. After adjustment for this shared group, each entry of the Schur cross block depends on its two conditioning products only through their product (Proposition 3.3). Thus, for each pair of endpoint products, at most $2^{r_B}$ distinct scores determine all $4^{r_B}$ entries, where $r_B$ is the number of conditioning bits. These scores recover the conditional covariance in each supported cell, weighted by its probability. Theorem 3.2 shows that $A$ and $C$ are conditionally independent given $B$ if and only if all scores vanish for every pair of endpoint products, even when some bit patterns have zero probability. Interpretation of the maximizing score. In the light-tunnel example (Section 6.1, Figure 3), 36 scores suffice for all 144 Schur entries. In 48 of the 100 subsets, the maximizing score paired the high-versus-low infrared bit $C_1$ with the angle product $A_1A_2B_1B_2$. In 40 subsets, it paired $C_1$ with $A_1B_1$. The first angle pattern approximates the sign of the cosine product in (6.2), and the second approximates the sign of the sine product. The maximizing score thus identifies which physical pattern is most strongly associated with high versus low infrared readings in a given subset. Computational speed. BEGIN evaluates the sign products by packing observations into machine words and counting bits. At $n=512$, the full Max BEGIN test scanned 37 conditioning products and completed 199 randomizations in a median of 2.40 ms. The forest-weighted CRT, which fits a weight on half the sample, took 119.53 ms (Appendix N, Table 2). We did not time fixed-weight WGCM with the same products.