Optimal Sample Complexity Lower Bounds on Conditional Independence Testing

摘要

We study the sample complexity of conditional independence testing. In this problem, given i.i.d. samples from a discrete distribution P_ABC, the goal is to distinguish whether A and C are conditionally independent with respect to B, i.e., P_ABC=P_A|BP_BP_C|B, or whether A and C are conditionally dependent, Δ(P_ABC,P_A|BP_BP_C|B)≥ε for some fixed threshold ε and distance measure Δ. We are interested in the cases where Δ is either the ℓ_1 distance or the KL-divergence. The study for the case of ℓ_1 distance was initiated by (Canonne et al., STOC 2018), and the KL-divergence was recently studied by (Seyfried et al., COLT 2025). Both works design algorithms whose sample complexities scale sublinearly in the dimensions of the subsystems, and showed tight lower bounds in some parameter regimes. While Canonne et al. derived partial lower bounds for the remaining regimes as well, the problem of fully resolving the sample complexity in all parameters remained open. In this work, we settle these open questions and prove optimal sample complexity lower bounds for both of these problems, thereby completely settling the sample complexities up to polylogarithmic factors.