📊 statistics

Multiscale Cochran-Mantel-Haenszel Scanning for Conditional Dependency

This paper proposes a nonparametric, multiscale scanning method that generalizes the Cochran-Mantel-Haenszel test to continuous sample spaces, enabling consistent conditional independence testing and association estimation without requiring large stratum sample sizes while offering linear scalability and interpretable summary statistics.

Original authors: Gyeonghun Kang, Jialiang Mao, Li Ma

Published 2026-04-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Gyeonghun Kang, Jialiang Mao, Li Ma

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery: Do two things, let's call them "X" and "Y," actually influence each other, or are they just pretending to be connected because of a third factor, "Z"?

In the real world, this is like asking: "Does the weather (Z) make people buy umbrellas (X) and wear raincoats (Y) at the same time, or do umbrellas actually cause people to wear raincoats?"

This paper introduces a new, super-smart detective tool called Multi-CMH. Here is how it works, explained without the heavy math jargon.

1. The Old Way: Trying to See the Forest for the Trees

Previous methods tried to solve this by either:

The "Kernel" Method: Trying to map every single relationship in a giant, complex 3D web. This is like trying to draw a map of every single leaf on a tree. It's incredibly accurate but takes forever to compute, especially if the tree is huge.
The "Discretization" Method: Cutting the world into big, chunky boxes (strata) and checking inside each box. The problem? If the boxes are too big, you miss the details. If they are too small, you don't have enough data inside them to make a decision. It's a frustrating "Goldilocks" problem that often fails when you have a lot of data or many variables.

2. The New Way: The "Zoom-Lens" Strategy (Multi-CMH)

The authors propose a method that combines the best of both worlds using a multiscale scanning approach. Think of it like using a camera with a powerful zoom lens that can snap photos at different levels of detail.

Step A: The "MedTree" (Organizing the Chaos)

First, the method organizes the data. Imagine you have a messy room full of people (your data points). Instead of trying to sort them by how similar they look (which is hard in a crowd), the method uses a median split.

It asks: "Who is in the top half of height?" and splits the room.
Then it splits the top half again, and the bottom half again.
It keeps doing this, creating neat, equal-sized groups (strata).
Why this is cool: It doesn't care about the "shape" of the crowd or complex distances. It just splits them down the middle, over and over. This is fast, fair, and works even if you have thousands of people.

Step B: The "2x2xT" Table (The Classic Detective Tool)

Once the data is sorted into these neat groups, the method uses a classic statistical tool called the Cochran-Mantel-Haenszel (CMH) test.

Imagine you have a stack of tiny 2x2 grids (like Tic-Tac-Toe boards).
Each grid represents a specific group of people (a "stratum").
The CMH test looks at all these grids at once to see if there is a pattern. It asks: "In almost every single group, do X and Y move together?"
The Magic: By looking at many small groups instead of one giant mess, the method avoids the "Goldilocks" problem. It doesn't need huge groups to work; it just needs many groups.

Step C: The "Divide and Conquer" (Scanning the Whole Picture)

Here is the real genius part. The method doesn't just look at the whole picture once. It scans the data at different resolutions:

Wide Angle: It looks at the whole room (low resolution) to see if there's a big, obvious connection.
Zoom In: If it doesn't see a clear pattern, or if it wants to find where the pattern is, it zooms in. It splits the room into smaller and smaller sections (high resolution).
The Scan: It runs the CMH test on every single little window it creates.

Because of some clever math, the results from all these little windows are independent. This means the method can check thousands of tiny spots without getting confused or making false alarms.

3. Why This Matters: The "Uber" Example

The authors tested this on real Uber data. They wanted to know: Does the wait time (ETA) affect whether a rider requests a ride, even after we account for the price?

The Old Way: Might just say, "Yes, they are connected," but couldn't tell you when or where it matters most.
The Multi-CMH Way: It zoomed in and found a specific pattern:
- When the wait time is short, people don't care much.
- But when the wait time gets really long (the "zoomed-in" window), people get very sensitive and cancel their rides, even if the price is the same.
- It also showed that this sensitivity changes depending on whether it's a busy time or a cheap time.

The Big Takeaway

This method is like a smart, fast, and flexible microscope.

Fast: It can handle millions of data points in seconds (unlike the slow, heavy methods).
Smart: It doesn't just say "Yes/No." It tells you where the relationship happens (e.g., "Only when wait times are long").
Robust: It works well even when the data is messy or high-dimensional.

In short, instead of trying to solve the whole puzzle at once, this method breaks the puzzle into tiny, manageable pieces, solves them all quickly, and then puts the picture back together to show you exactly where the hidden connections are.

1. Problem Statement

The paper addresses the challenge of testing Conditional Independence (CI) between two random variables $X$ and $Y$ given a set of conditioning variables $Z$ (i.e., testing $X \perp Y \mid Z$ ). This is a fundamental task in causal inference, feature selection, and graphical model learning.

Key Challenges Identified:

Scalability: Many state-of-the-art nonparametric tests (e.g., Kernel-based methods like RCIT, GCM) suffer from $O(n^2)$ computational complexity, making them infeasible for large datasets.
High-Dimensionality: Kernel methods often suffer from the "curse of dimensionality," where statistical power decays polynomially as the dimension of $Z$ increases.
The Discretization Paradox: Existing discretization-based methods (stratifying $Z$ ) face a trade-off: strata must be small enough to control Type I error (T1E) but large enough to contain sufficient samples for power. Most require stratum sizes to grow to infinity for consistency, which is impractical.
Lack of Diagnostic Capability: Many tests only provide a binary "reject/fail to reject" result without identifying where in the sample space the dependency exists or the nature of that dependency.

2. Methodology: MultiCMH

The authors propose MultiCMH, a nonparametric approach that generalizes the Cochran-Mantel-Haenszel (CMH) test to continuous sample spaces using a multiscale scanning strategy.

A. Core Concept: Sparse-Data Asymptotics

Instead of requiring stratum sample sizes to grow to infinity (standard asymptotics), MultiCMH leverages sparse-data asymptotics. It assumes the number of strata ( $T$ ) grows with the sample size ( $n$ ), while individual stratum sizes remain small (e.g., fixed $\eta$ ). Under this regime, the CMH statistic remains consistent without requiring large per-stratum counts.

B. Algorithmic Steps

Recursive Dyadic Partitioning (Discretization of $X$ and $Y$ ):
- The continuous spaces of $X$ and $Y$ are discretized using nested dyadic partitions (binary trees).
- This transforms the problem into testing independence across a series of coarse-to-fine $2 \times 2$ tables at different resolutions.
- Theorem 3 establishes that $X \perp Y \mid Z$ if and only if the log-odds ratios are zero for all such dyadic partitions.
Stratification of $Z$ (The medtree Algorithm):
- To handle continuous $Z$ , the authors propose a recursive partitioning algorithm based on sample medians (not distance-based clustering like k-means).
- The space is split recursively along coordinate axes at the sample median, creating hyper-rectangular strata with nearly equal sample counts.
- Advantages: This approach is invariant to monotone transformations, robust to high dimensions (avoiding distance concentration), and has $O(n \log n)$ complexity.
Multiscale Scanning & CMH Testing:
- The method scans the $(X, Y)$ space using "windows" defined by the dyadic partitions.
- For each window, the data is tabulated into a $2 \times 2 \times T$ contingency table (where $T$ is the number of strata of $Z$ ).
- A CMH test statistic is computed for each window to test for conditional independence within that local region.
Statistical Inference & Multiplicity Control:
- Independence: A key theoretical contribution (Theorem 5) proves that conditioned on the marginal totals of the strata, the p-values from these local CMH tests are mutually independent.
- Three-Stage Šidák Correction: To control the Family-Wise Error Rate (FWER) across the hierarchical structure of windows (nested partitions and varying resolutions), the authors apply a three-stage Šidák correction:
  1. Within the same partition resolution.
  2. Across partitions of the same resolution.
  3. Across all resolutions.
- This allows the method to identify specific "significant windows" where dependency exists, rather than just rejecting the global null.

3. Key Contributions

Generalization of CMH: Extends the classic CMH test (originally for discrete $Z$ ) to continuous $X, Y, Z$ via multiscale scanning and sparse-data asymptotics.
Theoretical Guarantees:
- Consistency: Proves the test is consistent even when stratum sizes do not diverge, provided the number of strata increases.
- T1E Control: Establishes asymptotic Type I error control under marginal smoothness assumptions.
- Local Consistency: Demonstrates that the method can detect local dependencies (specific regions of $X, Y$ ) even if global homogeneity does not hold.
Computational Efficiency: Achieves near-linear time complexity ( $O(n \log n)$ ) due to the median-based stratification and efficient table construction, avoiding the $O(n^2)$ bottleneck of kernel methods.
Diagnostic Capability: Unlike black-box tests, MultiCMH provides a "map" of the dependency, identifying specific regions (windows) and estimating the strength and direction (via log-odds ratios) of the conditional association.

4. Simulation Results

The authors compared MultiCMH against state-of-the-art methods (CDIT, CCIT, CMIknn, RCIT, GCM, wGCM, LPCIT).

Type I Error Control: MultiCMH successfully controls T1E at the nominal level (0.05) across various sample sizes and dimensions, whereas methods like CCIT and RCIT showed miscalibration.
Statistical Power:
- MultiCMH demonstrated robust power even in high-dimensional settings ( $d=128$ ), whereas many competitors (e.g., CDIT, CMIknn) suffered severe power degradation as dimension increased.
- It achieved an Area Under the ROC Curve (AUROC) approaching 1.0 for large sample sizes.
Scalability:
- Time: MultiCMH was the fastest method, scaling linearly with sample size ( $n$ ) and showing minimal sensitivity to dimension ( $d$ ). For $n=800, d=128$ , it took ~1 second, while others took minutes to hours or failed.
- Memory: It is memory-efficient, capable of handling datasets with $n > 1,000,000$ where other methods failed due to RAM constraints.

5. Case Study: Uber Ride-Share Data

The method was applied to a dataset of Uber ride requests to test if Pickup ETA ( $X$ ) influences the Request Decision ( $Y$ ) after conditioning on Pricing Context ( $Z$ ).

Result: The global null was rejected (p-value $\approx 0$ ).
Insight: The method identified specific "significant windows" where the dependency was strongest.
- It revealed that longer ETAs significantly discourage ride requests (negative log-odds ratio).
- Crucially, it showed heterogeneity: The sensitivity to wait time intensified at longer ETAs (e.g., users are more sensitive to delays when the wait is already long).
- It also detected interactions with pricing components, showing how pricing context modulates the ETA effect.
Significance: This demonstrates the method's ability to move beyond simple hypothesis testing to provide actionable, granular insights into complex conditional dependencies in real-world data.

6. Conclusion and Significance

MultiCMH represents a significant advancement in conditional independence testing by bridging the gap between statistical rigor and computational scalability.

Practical Impact: It offers a tool for practitioners working with large-scale, high-dimensional data (e.g., genomics, finance, tech platforms) where existing methods are either too slow or lack power.
Theoretical Impact: It resolves the "discretization paradox" by utilizing sparse-data asymptotics, proving that consistency can be achieved without infinite stratum sizes.
Interpretability: By inheriting the structure of the CMH test, it provides interpretable summary statistics (odds ratios) and localizes dependencies, making it a powerful diagnostic tool for understanding the nature of relationships in complex systems.