Testing conditional independence under isotonicity

1. Problem Statement and Motivation

The Challenge of Conditional Independence (CI) Testing:
Testing whether a variable $X$ is conditionally independent of $Y$ given a confounder $Z$ ($X \perp\!\!\perp Y \mid Z$) is a fundamental problem in statistics, underpinning causal inference and graphical modeling. However, Shah and Peters (2020) established a "hardness result": without further assumptions, no valid test can have non-trivial power against all alternatives in a distribution-free setting. Existing approaches typically rely on:

• Parametric models (e.g., Gaussian).
• Known or well-estimated conditional distributions ($P_{X|Z}$).
• Smoothness assumptions (e.g., Hölder continuity).

The Proposed Setting:
The authors propose a nonparametric framework based on a shape constraint: Stochastic Monotonicity.

• Assumption: The conditional distribution $P_{X|Z}$ is stochastically non-decreasing in $Z$. That is, if $z \preceq z'$, then $P(X \ge x \mid Z=z) \le P(X \ge x \mid Z=z')$ for all $x$.
• Motivation: This assumption is natural in many fields (e.g., higher education $\to$ higher salary; higher smoking intensity $\to$ higher disease risk) and does not require estimating the full conditional distribution or selecting tuning parameters.
• Goal: Develop a valid test for the Isotonic Conditional Independence (ICI) null hypothesis:
  $$H_0^{ICI}: X \perp\!\!\perp Y \mid Z \quad \text{and} \quad P_{X|Z} \text{ satisfies stochastic monotonicity.}$$

2. Methodology: The PairSwap-ICI Procedure

The core of the method is a permutation-based test that respects the stochastic monotonicity constraint.

A. Matching and Swapping:

1. Matching: Based on observed $Y$ and $Z$ (but without accessing $X$), the analyst constructs a set of $L$ disjoint pairs of indices $(i_\ell, j_\ell)$ such that $Z_{i_\ell} \preceq Z_{j_\ell}$.
2. Statistic Construction: A test statistic $T(X)$ is defined as a sum of anti-monotonic functions applied to the paired $X$ values:
   $$T(X) = \sum_{\ell=1}^L \psi_\ell(X_{i_\ell}, X_{j_\ell})$$
   where $\psi$ satisfies an anti-monotonicity property: $\psi(x+\Delta, x'-\Delta') - \psi(x'-\Delta', x+\Delta) \ge \psi(x, x') - \psi(x', x)$ for $\Delta, \Delta' \ge 0$.
   • Example: $\psi(x, x') = x - x'$ (linear) or $\psi(x, x') = \text{sign}(x - x')$.
3. Permutation (PairSwap): To calibrate the test, the method generates a null distribution by randomly swapping the $X$ values within each matched pair $(i_\ell, j_\ell)$. Let $s \in \{\pm 1\}^L$ be a vector of swap indicators. The permuted statistic is $T_s = T(X^s)$.

B. P-value Calculation:
The p-value is the proportion of permutations where the permuted statistic is greater than or equal to the observed statistic:
$$p = \frac{1}{2^L} \sum_{s \in \{\pm 1\}^L} \mathbb{I}\{T_s \ge T\}$$

• Validity: Under $H_0^{ICI}$, the stochastic ordering implies that $X_{i_\ell}$ is stochastically smaller than $X_{j_\ell}$. Consequently, the observed statistic $T$ tends to be smaller than its swapped versions. The test guarantees finite-sample Type I error control regardless of the dimension of $Y$ and $Z$.

C. Designing a Powerful Test:
To maximize power, the authors propose:

• Kernel Choice: Linear ($x-x'$) or truncated/signed versions for robustness.
• Matching Strategies:
  • Neighbor Matching: Pair consecutive sorted $Z$ values. Simple but discards $\approx 50\%$ of data if $Y$ ordering doesn't align.
  • Cross-Bin Matching: Partition $Z$ into bins and match high $Y$ in one bin with low $Y$ in the adjacent bin. This utilizes nearly all data and achieves near-optimal power.
• Weighting: Weights can be chosen based on the difference in $Y$ values ($w_\ell = (Y_{i_\ell} - Y_{j_\ell})_+$) or via "oracle" estimates of conditional moments if available.

3. Key Theoretical Contributions

A. Finite-Sample Validity:
Theorem 2 proves that the PairSwap-ICI test controls the Type I error at level $\alpha$ for any sample size $n$, any matching scheme, and any valid anti-monotonic kernel, provided the stochastic monotonicity assumption holds. This is a significant advantage over methods like the Conditional Randomization Test (CRT) which often require asymptotic validity or perfect knowledge of $P_{X|Z}$.

B. Power Analysis and Signal-to-Noise Ratio:
The authors introduce the Isotonic Signal-to-Noise Ratio (ISNR):
$$ISNR_n = \frac{\inf_{g \in \mathcal{C}_{ISO}} \mathbb{E}[\| \mu_n(Y, Z) - g(Z) \|^2]}{\sigma_n}$$
where $\mathcal{C}_{ISO}$ is the cone of non-decreasing functions.

• Fundamental Limit: Theorem 7 establishes that $ISNR_n$ provides a universal upper bound on the power of any valid test for $H_0^{ICI}$. If $ISNR_n$ is negligible, no test can distinguish the null from the alternative.
• Optimality: Theorem 8 and 9 show that the PairSwap-ICI test (with oracle or plug-in matching) achieves power asymptotically matching this fundamental limit.
• Heuristic Performance: Theorem 11 and 12 demonstrate that simple heuristics (Neighbor and Cross-Bin matching) achieve power that is within a constant factor (specifically $1/\sqrt{2}$ or better) of the optimal oracle test, and under symmetry assumptions, they achieve the exact lower bound.

C. Multivariate Extension:
Section 5 extends the framework to multivariate $X \in \mathbb{R}^{d_X}$ by defining stochastic monotonicity via coordinate-wise ordering and using projection directions to reduce the problem to the univariate case.

4. Empirical Results

Simulations:

• Type I Error: The test maintains strict control over Type I error even in finite samples, whereas asymptotic methods (like GCM, PCM, CRT) showed deviations from the nominal level in small samples.
• Power: The test detects deviations from conditional independence effectively.
  • Cross-Bin Matching generally outperforms Neighbor Matching, especially when the dependence between $X$ and $Z$ is strong, as it allows for more pairs.
  • The test is robust to heavy tails and non-linear dependencies where linear models fail.
• Comparison: In benchmark comparisons, PairSwap-ICI is the only method that simultaneously guarantees finite-sample validity and maintains competitive power across linear, quadratic, and interaction models.

Real Data Application (Diabetes Dataset):

• Context: Analyzing risk factors for diabetes in the Pima Indian dataset, controlling for Age ($Z$).
• Finding:
  • Marginal Tests: Identified Pregnancies, Glucose, Insulin, and BMI as significant.
  • Conditional Tests (PairSwap-ICI): After controlling for Age, only Glucose and BMI remained significant risk factors.
  • Interpretation: The associations for Pregnancies and Insulin were likely confounded by Age. The test successfully isolated the direct effect of variables on diabetes incidence.
• Synthetic Control: Using synthetic data generated to satisfy the null hypothesis confirmed that the p-values were uniformly distributed, validating the test's calibration.

5. Significance and Conclusion

Significance:

1. Bridging the Gap: The paper resolves the "impossibility" of distribution-free CI testing by introducing a minimal, application-motivated shape constraint (stochastic monotonicity) that is often naturally satisfied in practice.
2. Finite-Sample Guarantees: Unlike many modern CI tests that rely on asymptotic approximations or accurate estimation of conditional distributions, PairSwap-ICI offers rigorous finite-sample error control without requiring knowledge of $P_{X|Z}$.
3. Flexibility: The framework allows analysts to incorporate domain knowledge into the matching and weighting schemes to boost power without sacrificing validity.

Conclusion:
The PairSwap-ICI procedure provides a robust, nonparametric tool for conditional independence testing. It is particularly valuable in settings where variables exhibit monotonic relationships with confounders (common in medicine, economics, and risk modeling), offering a reliable alternative to parametric or smoothness-based methods. The authors demonstrate that simple, computationally efficient heuristics can achieve near-optimal power, making the method practical for high-dimensional real-world data.