A simple measure of conditional dependence

Mona Azadkia; Sourav Chatterjee

Source-linked AI summary

A simple measure of conditional dependence

Mona Azadkia, Sourav Chatterjee

arXiv:1910.12327v6Oct 27, 2019math.STcs.ITmath.PRstat.ME

TL;DR

The paper addresses the limited availability of nonparametric measures of conditional dependence. It proposes a coefficient with endpoint characterizations and a nonlinear partial-R2 interpretation, then develops FOCI for variable selection; the coefficient is estimated consistently, while testing remains subject to fundamental limitations.

Problem
Nonparametric conditional dependence has fewer established measures than dependence measurement generally, motivating a flexible coefficient for Y and Z given X1, . . . , Xp.
Method
The paper proposes a coefficient estimated from i.i.d. data and builds FOCI, a model-free forward variable-selection algorithm without tuning parameters.
Results
The coefficient converges to a limit in [0,1] without distributional assumptions, with 0 characterizing conditional independence and 1 characterizing conditional measurable dependence; its estimator is consistent.
Takeaways & Limitations
The coefficient provides a nonlinear generalization of partial R2, and FOCI offers a sparsity-consistent, model-free route to variable selection.
Takeaways & Limitations
Uniformly controlled consistent nonparametric conditional-independence testing is impossible over the whole null space without unverifiable additional assumptions, and the estimator’s rate may require distributional assumptions.

Abstract

from arXiv · show

We propose a coefficient of conditional dependence between two random variables $Y$ and $Z$ given a set of other variables $X_1,\ldots,X_p$, based on an i.i.d. sample. The coefficient has a long list of desirable properties, the most important of which is that under absolutely no distributional assumptions, it converges to a limit in $[0,1]$, where the limit is $0$ if and only if $Y$ and $Z$ are conditionally independent given $X_1,\ldots,X_p$, and is $1$ if and only if $Y$ is equal to a measurable function of $Z$ given $X_1,\ldots,X_p$. Moreover, it has a natural interpretation as a nonlinear generalization of the familiar partial $R^2$ statistic for measuring conditional dependence by regression. Using this statistic, we devise a new variable selection algorithm, called Feature Ordering by Conditional Independence (FOCI), which is model-free, has no tuning parameters, and is provably consistent under sparsity assumptions. A number of applications to synthetic and real datasets are worked out.

1. Introduction

The paper introduces a nonparametric conditional-dependence coefficient with sharp interpretations at 0 and 1, and uses it to build the model-free FOCI variable-selection algorithm.

1. Introduction: The coefficient measures conditional dependence between Y and Z given X1, . . . , Xp using i.i.d. data and requires no distributional assumptions.It has a simple expression, no tuning parameters, and avoids estimating conditional densities, characteristic functions, or mutual information.
1. Introduction: Its limit lies in [0, 1], equaling 0 if and only if Y and Z are conditionally independent given X1, . . . , Xp.The statistic is well-defined and bounded under the stated nondegeneracy condition.
1. Introduction: The limit equals 1 if and only if Y is almost surely a measurable function of Z given X1, . . . , Xp.Thus, the endpoints distinguish conditional independence from conditional functional dependence.
1. Introduction: The paper estimates the coefficient consistently from i.i.d. data and introduces FOCI, a model-free, tuning-free variable-selection algorithm provably consistent under sparsity assumptions.FOCI uses the conditional-dependence measure in a forward stepwise procedure.
1. Introduction: A general nonparametric conditional-independence test based on the coefficient remains constrained because uniformly controlled consistent testing is impossible over the whole null space without additional unverifiable assumptions.The paper contrasts this with unconditional independence testing, for which many useful methods exist.
1. Introduction: The coefficient generalizes partial R2 nonlinearly by aggregating partial R2 measures for binary threshold versions of Y.It measures variation in Y explained by (Z, X) but not solely by X, and reduces to partial R2 when Y is binary.

4. Rate of convergence

The estimator Tn converges to T at essentially rate n^-1/(p+q), up to a logarithmic factor, under regularity and tail assumptions. The paper notes that this rate may be intrinsic for continuous variables, while some cases remain conjectural.

Rate under assumptions: The rate analysis requires distributional assumptions because convergence may otherwise be arbitrarily slow.The stated motivation is to control how the conditional distribution of Y given X and Z changes with X and Z.
Rate under assumptions: Assumption (A1) controls the conditional distribution’s local Lipschitz sensitivity in (X, Z), allowing polynomial growth in their magnitudes.Assumption (A2) imposes exponential tail bounds on X and Z.
Rate under assumptions: n^-1/(p+q), up to an extra logarithmic term, is the established convergence rate for Tn under assumptions (A1) and (A2).The theorem applies when p ≥1 and q ≥1.
Open rate questions: The authors believe n^-1/(p+q) is the true continuous-variable rate, but do not know whether another statistic with the same properties can converge faster.The paper also leaves the p = 0 case outside Theorem 4.1 and conjectures a faster n^-1/2 rate when q = 1.
Open rate questions: The central-limit behavior of nTn in the p = 0, q = 1 case remains unproved.The authors explicitly identify these statements as conjectures.
Examples of applicability: For finite-support or normal distributions, the required assumptions are readily satisfied, and broader regularity and decay conditions also suffice.The paper gives conditional-density conditions involving differentiability, tail decay, and polynomially bounded conditional moments.

6. Consistency of FOCI

FOCI selects variables by maximizing conditional-dependence gains, with consistency established under regularity and sparsity-related assumptions. The theory guarantees a sufficient selected subset with high probability, while practical examples show strong performance on nonlinear relationships.

Consistency framework: FOCI measures added predictive power through Q(S′) − Q(S) when variables are appended to an existing predictor set.The increase is zero exactly when the appended variables are conditionally independent of Y given the current predictors.
Consistency framework: δ requires every insufficient subset to have some remaining variable that increases Q by at least δ, encoding a sparsity condition.The definition implies that at least one sufficient subset has size at most 1/δ.
Consistency framework: Under assumptions (A1′) and (A2′), FOCI selects a sufficient subset with probability at least 1 − L1pL2e−L3n.The constants depend on C, β, C1, C2, and δ.
Consistency framework: When δ is not too small and n ≫ log p, FOCI selects a sufficient set with high probability even when p is large relative to n.The theorem does not guarantee that the selected subset itself is small, and proving such a guarantee remains open.
Gaussian interpretation: In Gaussian linear regression, δ is equivalent up to constants to the analogous minimum partial-R2 gain over insufficient subsets.This connects the model-free criterion to familiar regression-based variable selection.
Examples: FOCI selected the correct nonlinear predictor subset in more than 90% of simulations for one interaction model and 99.5% for another.Linear-model methods generally missed nonlinear effects, while random forests and mutual information required substantially more computation.

9. Restatement of Theorems 2.1 and 2.2

Theorems 2.1 and 2.2 are restated through almost-sure limits of the numerator and denominator statistics. These limits characterize conditional independence and conditional functional dependence, with a separate unconditional case.

Setup: The paper uses “function” to mean equality almost surely to a measurable function of the other variable.This convention applies throughout the proof sections.
Conditional case: For p ≥ 1, Qn(Y, Z|X) and Sn(Y, X) converge almost surely to deterministic limits a and b.The limits satisfy 0 ≤ a ≤ b; a = 0 characterizes conditional independence, while a = b characterizes conditional functional dependence.
Unconditional case: For p = 0, Qn(Y, Z) and Sn(Y) converge almost surely to deterministic limits c and d.Here c = 0 characterizes independence, c = d characterizes functional dependence, and d > 0 exactly when Y is nonconstant.
Unconditional case: When Y has a continuous distribution, the denominator limit d equals 1/6; otherwise, d may depend on Y’s distribution and must be estimated.This distinction determines whether denominator estimation is needed.

10. Proofs of Theorems 2.1 and 2.2 using Theorems 9.1 and 9.2

The proofs derive the coefficient’s properties by expressing it as a ratio of empirical quantities whose limits are already characterized. The p = 0 case follows analogously from the unconditional theorem.

Proof strategy: For p ≥ 1, the coefficient is written as T = a/b using the limits from Theorem 9.1.The denominator is positive when Y is not a function of X, so the ratio is well-defined.
Proof strategy: Theorem 9.1 yields 0 ≤ T ≤ 1, T = 0 exactly under conditional independence, and T = 1 exactly under conditional functional dependence.These conclusions follow by dividing the corresponding properties of a and b.
Unconditional case: For p = 0, the same argument uses T = c/d and the limits from Theorem 9.2.The empirical ratio Tn = Qn/Sn converges in probability to c/d.

11. Preparation for the proofs of Theorems 9.1 and 9.2

The preparatory results establish properties of conditional laws, nearest-neighbor geometry, and the population dependence functional needed for the main convergence proofs. In particular, Q increases when conditioning variables are augmented, with equality characterizing conditional independence.

Conditional laws: Regular conditional probabilities provide measurable conditional laws of Y given X, represented by μx.These conditional laws support the construction of conditional distribution functions used throughout the arguments.
Dependence functional: Q(Y, X) equals zero exactly when Y and X are independent.The proof shows independence makes conditional distribution functions nonrandom, while the converse recovers independence from zero variance.
Dependence functional: Adding Z to X cannot decrease Q: Q(Y, (X, Z)) ≥ Q(Y, X), with equality exactly under conditional independence of Y and Z given X.This monotonicity underlies the interpretation of Q differences as added predictive power.
Nearest-neighbor tools: Nearest-neighbor distances converge to zero almost surely, and each point can be the nearest neighbor of at most C(p) others.The geometric bound depends only on the predictor dimension and supports control of nearest-neighbor statistics.

i. Then only N(i) can change, and hence A′

The proof combines three steps to control the relevant change and completes the resulting probability bound.

The argument concludes the proof after combining the three preceding steps.
The bound holds for P(|A_n−E(A_n)| ≥ 2t) when t ≥ 3n^−1/2.
For t < 3n^−1/2, choosing C1 ≥ 6 makes the bound trivial.

12. Proof of Theorem 9.2

The proof establishes convergence of the relevant quantities and verifies the three characterization claims for the limiting dependence coefficient.

Q_n(Y,Z) converges to a deterministic limit, while S_n(Y) converges to d using the strong law of large numbers.The convergence of Q_n follows from Corollary 11.10, and the convergence of S_n is handled separately.
If Y and X are independent, the limiting coefficient c equals 0.
If Y is a function of Z almost surely, the proof establishes the corresponding equality condition.
The limits satisfy 0 ≤ c ≤ d, and c = 0 if and only if Y and Z are independent.
When c = d, the support argument shows that Y is almost surely a function of Z.

13. Proof of Theorem 9.1

The proof shows that the sample conditional-dependence quantities converge almost surely and that their limits characterize conditional independence and functional dependence.

The identity Q(Y,Z|X) = Q(Y,W) − Q(Y,X), with W = (X,Z), is used to establish the conditional limit.
Q_n(Y,Z|X) converges almost surely to Q(Y,Z|X), while S_n(Y,X) converges to S(Y,X).The two convergence claims are obtained from Lemmas 13.1–13.3.
If Y and Z are conditionally independent given X, then the limiting quantity a equals 0.
If Y is a function of Z conditional on X, then a = b.
Because b − a is nonnegative, 0 ≤ a ≤ b; the reverse implications complete the characterization.

14. Proof of Theorem 4.1

Under assumptions (A1) and (A2), the proof derives nearest-neighbor concentration bounds and uses them to establish Theorem 4.1.

The analysis assumes (A1) and (A2), with X_n,1 defined as the nearest neighbor of X_1 among the remaining observations.
Nearest-neighbor distance control is obtained by partitioning a radius-t ball into small sets and bounding the probability that nearby observations are absent.The argument uses a partition with at most C t^p ε^−p sets and conditions on X_1.
The resulting bound is Cn^−1(log n)^3 for p = 1 and Cn^−1/p(log n)^(p+1) for p ≥ 2.
Exponential tail assumptions control both ||X_1|| and ||X_n,1||, enabling completion of the concentration proof.
The theorem proof combines the convergence results for Q and S with the claims established earlier.

15. Proof of Proposition 4.2

The proof establishes integrability and polynomial bounds needed to apply dominated convergence and verify the relevant condition.

The boundedness and rapid decay of g(y) make g(y)h(y) integrable in y.This permits application of the dominated convergence theorem.
Derivative assumptions on log f(y|x), together with conditional moment bounds, yield a polynomial upper bound in ∥x∥.The proof then obtains the second inequality in (A1) directly from this bound.

16. Proof of Theorem 6.1

The proof shows that FOCI’s empirical criterion uniformly approximates its population counterpart along the selected ordering, which guarantees that the selected set is sufficient with high probability.

FOCI orders variables as j1,…,jp and evaluates population and empirical criteria Q(Y, XS) and Qn(Y, XS) along the resulting nested sets.The proof defines Sk from the complete ordering and sets both criteria to zero for the empty set.
On event E′, the empirical criterion is within δ/8 of the population criterion for every selected set through step K.This uniform approximation is the premise used by the subsequent lemmas.
At each step, the selected variable maximizes Qn among candidates not already selected, so the approximation transfers the selection rule to the population criterion.If the stopping condition is met, this implies the current set is sufficient.
If no selected set satisfies the sufficient-set condition, bounded variance of [0,1]-valued variables contradicts the maximum possible value Q ≤ 1/4.Therefore some Sk with k ≤ K must be sufficient.
When FOCI stops before step K, its stopping rule and E′ imply the returned set is sufficient; stopping at or after K gives the same conclusion through SK.This covers both possible stopping regimes.

17. Proof of Theorem 7.1

The proof compares the conditional-dependence criterion with partial R^2 under joint normality, then uses that comparison to show that every insufficient predictor set has a useful next variable.

The proof begins with a variance bound for functions of normal random variables and a lemma comparing Q(Y, Z|X) with partial R^2.The comparison assumes jointly normal variables and nonzero conditional variances.
The Gaussian c.d.f. bound provides constants C1 and C2 controlling the relevant variance expressions.The proof derives the bound by treating the normal variables symmetrically and using boundedness of the function involved.
The normal-variable variance argument represents conditional expectations through Gaussian variables and relates their conditional variance difference to α^2 and β^2.These quantities are then bounded using properties of normal distributions.
For any insufficient predictor set S, some excluded variable j has Q(Y, Xj|XS) ≥ δ.This establishes a population-level criterion for finding an additional informative predictor.
The comparison lemma converts the conditional-dependence lower bound into a lower bound on the corresponding partial-R^2 threshold, δ′ ≥ σ^2δ/(C2τ^2).The proof uses σ^2 as the residual variance given all predictors and τ^2 as the marginal variance of Y.
Conversely, every insufficient set has an excluded variable whose partial R^2 is at least δ′, and the reverse comparison completes the equivalence of the two thresholds.The final variance inequalities use β^2 ≥ σ^2, α^2 ≤ τ^2, and α^2 ≤ β^2.