Conditional independence (CI) tests are widely used in statistical data
analysis, e.g., they are the building block of many algorithms for causal graph
discovery. The goal of a CI test is to accept or reject the null hypothesis
that $X \perp \!\!\! \perp Y \mid Z$, where $X \in \mathbb{R}, Y \in
\mathbb{R}, Z \in \mathbb{R}^d$. In this work, we investigate conditional
independence testing under the constraint of differential privacy. We design
two private CI testing procedures: one based on the generalized covariance
measure of Shah and Peters (2020) and another based on the conditional
randomization test of Cand\`es et al. (2016) (under the model-X assumption). We
provide theoretical guarantees on the performance of our tests and validate
them empirically. These are the first private CI tests that work for the
general case when $Z$ is continuous.

本研究探讨在差分隐私的约束下的条件独立性检验，设计了两种基于广义协方差度量的私有 CI 检验以及基于 Candës 等人的条件随机化检验（在模型 - X 假设下），这是第一种适用于 $ Z $ 为连续型变量的私有 CI 检验。

差分隐私条件独立性检验

Differentially Private Conditional Independence Testing

The conditional randomization test (CRT) was recently proposed to test
whether two random variables X and Y are conditionally independent given random
variables Z. The CRT assumes that the conditional distribution of X given Z is
known under the null hypothesis and then it is compared to the distribution of
the observed samples of the original data. The aim of this paper is to develop
a novel alternative of CRT by using nearest-neighbor sampling without assuming
the exact form of the distribution of X given Z. Specifically, we utilize the
computationally efficient 1-nearest-neighbor to approximate the conditional
distribution that encodes the null hypothesis. Then, theoretically, we show
that the distribution of the generated samples is very close to the true
conditional distribution in terms of total variation distance. Furthermore, we
take the classifier-based conditional mutual information estimator as our test
statistic. The test statistic as an empirical fundamental information theoretic
quantity is able to well capture the conditional-dependence feature. We show
that our proposed test is computationally very fast, while controlling type I
and II errors quite well. Finally, we demonstrate the efficiency of our
proposed test in both synthetic and real data analyses.

本文提出了一种无需假设 X 给定 Z 的精确分布的条件随机化检验的新方法，并利用计算高效的 1 最近邻来近似编码空假设的条件分布。经实验证明，该方法不仅计算速度快，而且对于合成和实际数据分析都非常有效。