Characteristic Kernels and HSIC Consistency

Why Characteristic Kernels Matter

A dependence measure is useful as a test statistic only if it can distinguish dependence from independence in the population. A covariance-based measure can miss nonlinear relationships, so a natural question is whether a kernel-based measure can detect every departure from independence. The answer depends on the kernels: their feature representations must preserve enough information about the distributions being compared.

For a random variable \(X\), a kernel maps each possible value \(x\) to a feature vector in a reproducing kernel Hilbert space (RKHS). Averaging these vectors gives a representation of the distribution of \(X\). A kernel is characteristic when no two different probability distributions have the same average feature vector. This property connects the distribution-level question of independence to the operator defining population HSIC.

Throughout, take \(\mathcal X\) and \(\mathcal Y\) to be standard Borel spaces, and let \(k\) and \(l\) be bounded measurable positive definite kernels on them, with separable RKHSs \(\mathcal H_k\) and \(\mathcal H_l\). These conditions ensure that the feature means and cross-covariance operator below are well-defined. Boundedness also ensures that every RKHS function is bounded: if \(k(x,x)\leq K\), then \(|f(x)|\leq \|f\|_{\mathcal H_k}\sqrt K\).

Population HSIC as a Distributional Difference

Write \(\phi(x)=k(x,\cdot)\), \(\psi(y)=l(y,\cdot)\), \(\mu_X=E[\phi(X)]\), and \(\mu_Y=E[\psi(Y)]\). The cross-covariance operator \(C_{XY}:\mathcal H_l\to\mathcal H_k\) is defined by \(C_{XY}g=E[(\phi(X)-\mu_X)\langle\psi(Y)-\mu_Y,g\rangle_{\mathcal H_l}]\). Population HSIC is the squared Hilbert–Schmidt norm of this operator.

There is a useful equivalent description. The product kernel on \(\mathcal X\times\mathcal Y\) is \(q((x,y),(x',y'))=k(x,x')l(y,y')\), with feature map \(\phi(x)\otimes\psi(y)\). Its mean embedding under the joint distribution is \(E[\phi(X)\otimes\psi(Y)]\). Under the product of the marginal distributions, the embedding is \(\mu_X\otimes\mu_Y\). Their difference is precisely \(C_{XY}\), viewed as a Hilbert–Schmidt operator or its corresponding tensor.

Here \(\operatorname{MMD}_{q}\) is the maximum difference in expectations over functions in the unit ball of the RKHS of \(q\); equivalently, its square is the squared distance between the two \(q\)-mean embeddings. This identity explains why HSIC compares the joint distribution with the distribution that would result from making the margins independent. The next result gives the precise zero criterion needed for that comparison.

Proof. If \(X\) and \(Y\) are independent, then for any \(f\in\mathcal H_k\) and \(g\in\mathcal H_l\), \(E[(f(X)-E f(X))(g(Y)-E g(Y))]=0\). Thus \(C_{XY}=0\), and HSIC is zero.

For the converse, suppose HSIC is zero. Then \(C_{XY}=0\), so the same covariance is zero for every \(f\in\mathcal H_k\) and \(g\in\mathcal H_l\). Fix \(f\in\mathcal H_k\), and let \(r_f(y)=E[f(X)\mid Y=y]-E[f(X)]\), using a regular conditional distribution, which exists on standard Borel spaces. This function is integrable and has mean zero. Conditional expectation gives, for every \(g\in\mathcal H_l\),

Define the finite signed measure \(\nu_f\) by \(d\nu_f(y)=r_f(y)dP_Y(y)\). It has total mass zero, and the displayed equality says that its kernel mean embedding is zero: \(\int\psi(y)d\nu_f(y)=0\). Characteristicness of \(l\) implies that a finite signed measure of total mass zero with zero embedding must itself be zero. To see this, write its Jordan decomposition as \(\nu_f=\nu_f^+-\nu_f^-\). The two positive measures have equal mass; if that mass is positive, normalizing them gives probability measures with equal embeddings, so characteristicness makes them equal. If the mass is zero, both are zero. Hence \(r_f=0\) \(P_Y\)-almost surely.

It follows that for each \(f\in\mathcal H_k\), the conditional expectation \(E[f(X)\mid Y]\) equals \(E[f(X)]\) almost surely. Because \(\mathcal H_k\) is separable, choose a countable dense subset and intersect the corresponding probability-one events. On the resulting single probability-one set of \(y\)'s, the equality holds for every function in that subset. It extends to every \(f\in\mathcal H_k\): convergence in RKHS norm implies uniform convergence because \(k\) is bounded. Thus, for almost every \(y\), the conditional distribution \(P_{X\mid Y=y}\) and the marginal \(P_X\) have equal \(k\)-mean embeddings. Characteristicness of \(k\) gives \(P_{X\mid Y=y}=P_X\) for almost every \(y\). This is exactly independence of \(X\) and \(Y\). \(\square\)

Worked Examples

What the Result Does—and Does Not—Guarantee

Characteristicness is a population identification property. It says that distinct distributions cannot collapse to the same mean embedding. The theorem applies this property twice: characteristicness of \(l\) turns zero cross-covariance into constant conditional expectations for all functions of \(X\); characteristicness of \(k\) then turns those equalities into equality of conditional and marginal distributions. Both margins matter in this argument.

Population separation is the key ingredient behind consistency against fixed alternatives. In particular, suppose a sequence of nonnegative statistics \(T_n\) estimates population HSIC and satisfies \(T_n\xrightarrow{p}h\), where \(h=\operatorname{HSIC}(P_{XY};k,l)>0\). If its rejection threshold \(c_n\) tends to zero, then

for all sufficiently large \(n\), since then \(c_n<h/2\). Thus population separation, together with suitable estimation and calibration, yields power tending to one for each fixed dependent distribution. This argument alone does not establish a particular estimator's convergence or a valid null threshold; those require separate analysis.

A common mistake is to assume that a characteristic kernel on just one margin is enough. For example, if \(X=Y\) is the dependent binary pair above but the kernel on \(Y\) is the constant kernel \(l(y,y')=1\), then every centered feature \(\psi(Y)-\mu_Y\) is zero. HSIC is therefore zero regardless of the dependence, even though the kernel on \(X\) is characteristic. The constant kernel cannot distinguish probability distributions on a nontrivial space. The theorem's guarantee requires characteristic kernels on both margins.