General Frameworks for Conditional Two-Sample Testing

Technical Summary: General Frameworks for Conditional Two-Sample Testing

Problem Setup
This paper addresses the problem of conditional two-sample testing, which seeks to determine whether two populations share the same conditional distribution of a response variable $Y$ given a covariate $X$, after accounting for potential confounding factors. Formally, given two independent samples $\{(X^{(1)}_i, Y^{(1)}_i)\}_{i=1}^{n_1} \sim P^{(1)}_{XY}$ and $\{(X^{(2)}_i, Y^{(2)}_i)\}_{i=1}^{n_2} \sim P^{(2)}_{XY}$, the goal is to test the null hypothesis:
$$H_0: P^{(1)}_{Y|X}(\cdot | X) = P^{(2)}_{Y|X}(\cdot | X) \quad \text{almost surely}$$
against the alternative that they differ with positive probability. This problem arises in critical applications such as domain adaptation (validating covariate shift assumptions) and algorithmic fairness (detecting bias conditional on demographic attributes).

Hardness Result
The authors first establish a fundamental hardness result for this problem. They demonstrate that, without additional assumptions, no valid conditional two-sample test can possess non-trivial power against any single alternative when the conditioning variable $X$ is continuous. This finding parallels the negative result for conditional independence testing established by Shah and Peters (2020). A key technical distinction in their proof is that, unlike standard conditional independence settings where group indicators are random, the sample sizes $n_1$ and $n_2$ in the two-sample problem are deterministic. The authors bridge this gap using concentration arguments to show that the problem remains intrinsically difficult, necessitating structural assumptions (e.g., smoothness or boundedness of density ratios) to make the problem feasible.

Methodological Frameworks
To overcome these difficulties, the paper introduces two general frameworks that implicitly or explicitly incorporate reasonable assumptions to enable valid testing.

1. Framework via Conditional Independence Testing (CIT)
The first framework leverages the equivalence between conditional two-sample testing and conditional independence testing. By introducing a binary group indicator $Z$, the problem $P^{(1)}_{Y|X} = P^{(2)}_{Y|X}$ is equivalent to testing $Y \perp\!\!\!\perp Z \mid X$.

• Algorithm 1: The authors propose a generic "black-box" conversion method that transforms any existing conditional independence test into a conditional two-sample test. The algorithm constructs a dataset of i.i.d. triples $(X, Y, Z)$ by subsampling from the original fixed-size groups based on a Binomial distribution. If the subsampled sizes exceed the original group sizes, the null is accepted; otherwise, a standard conditional independence test is applied to the permuted data.
• Theoretical Guarantees: Theorem 2 proves that this conversion preserves the asymptotic validity (Type I error control) and consistency (power) of the underlying conditional independence test, provided the test statistic is "coupling-stable" or the subsampling loss is asymptotically negligible.

2. Framework via Density Ratio Estimation (DRT)
The second framework transforms the conditional comparison into a marginal comparison using density ratio estimation.

• Principle: The null hypothesis holds if and only if the joint density $f^{(1)}_{XY}$ equals a re-weighted version of $f^{(2)}_{XY}$, specifically $f^{(1)}_{XY}(x,y) = r_X(x) f^{(2)}_{XY}(x,y)$, where $r_X(x) = f^{(1)}_X(x)/f^{(2)}_X(x)$ is the marginal density ratio.
• Implementation: The problem is recast as a marginal two-sample test between $f^{(1)}_{XY}$ and the re-weighted $f^{(2)}_{XY}$. The authors demonstrate this via two concrete approaches:
  • Classifier-based approach: Training a classifier to distinguish between the two groups, where the loss function for the second group is weighted by the estimated density ratio $r_X$.
  • Kernel-based approach (MMD): Using Maximum Mean Discrepancy with importance weighting. The authors propose a unified block-wise MMD statistic governed by a parameter $\gamma \in [0, 1]$.
    • Regime I ($0 \le \gamma < 1$): Uses block-wise U-statistics to achieve asymptotic normality.
    • Regime II ($\gamma = 1$): Recovers the standard quadratic-time MMD, calibrated via a multiplier bootstrap to handle the non-Gaussian limiting distribution.
• Sample Splitting: To avoid plug-in bias, the authors employ sample splitting (or cross-fitting) to separate the estimation of $r_X$ from the evaluation of the test statistic.

Key Contributions

1. Hardness Characterization: Rigorous proof that conditional two-sample testing is as difficult as conditional independence testing under continuous conditioning, highlighting the necessity of assumptions.
2. Generic Conversion Algorithm: A novel algorithm (Algorithm 1) that allows practitioners to apply any existing conditional independence test to the two-sample setting while maintaining theoretical guarantees.
3. Density Ratio Framework: A flexible framework converting conditional testing to marginal testing via density ratios, instantiated with both classifier-based and kernel-based methods.
4. Unified MMD Theory: Theoretical development of a unified MMD framework covering both linear-time (block-wise) and quadratic-time regimes, including bootstrap calibration for the latter.

Results and Empirical Findings
The paper evaluates the proposed methods on synthetic data (covering linear, high-variance, and post-nonlinear models) and real-world datasets (Diamonds and Superconductivity).

• Synthetic Data:
  • DRT methods (relying on density ratios) show superior power when the marginal density ratio is bounded and easily estimable.
  • CIT methods (via Algorithm 1) and conditional kernel methods (CMMD, CGED) are more robust to unbounded density ratios but may suffer in specific high-variance scenarios.
  • No single method dominates uniformly; performance depends heavily on the data-generating mechanism and the difficulty of estimating the density ratio.
• Real Data:
  • In high-dimensional settings (Superconductivity dataset), the choice of density ratio estimator is critical. Linear Logistic Regression (LLR) failed to control Type I error, whereas Kernel Logistic Regression (KLR) restored validity, albeit at a higher computational cost.
  • Conditional kernel methods (CMMD, CGED) achieved competitive power but incurred significantly higher computational costs (orders of magnitude slower than other methods).

Significance and Claims
The paper claims to provide a systematic foundation for conditional two-sample testing, a problem previously underexplored in nonparametric statistics. By establishing the inherent hardness and offering two distinct, theoretically grounded frameworks, the work expands the toolkit available to practitioners.

• The CIT framework offers a practical pathway to leverage the extensive literature on conditional independence testing for two-sample problems.
• The DRT framework connects conditional testing to the well-studied field of importance weighting and marginal testing, offering flexibility in method selection (classification vs. kernels).
• The authors emphasize that the validity of these methods relies on specific assumptions (e.g., boundedness or estimability of density ratios), and they provide empirical guidance on the trade-offs between computational cost, power, and Type I error control across different data regimes.

The work concludes by identifying future directions, such as extending the frameworks to conditional $K$-sample testing ($K \ge 2$) and exploring resampling-based approaches like Sampling Importance Resampling (SIR).