Kernel Two-Sample Tests

The squared MMD can be expressed as:

$\text{MMD}^2(\mathcal{H}, P, Q) = \mathbb{E}_{x,x' \sim P}[k(x,x')] - 2\mathbb{E}_{x \sim P, y \sim Q}[k(x,y)] + \mathbb{E}_{y,y' \sim Q}[k(y,y')]$

If $k$ is a characteristic kernel (e.g., Gaussian RBF, Laplacian), then $\text{MMD}(\mathcal{H}, P, Q) = 0$ if and only if $P = Q$.

The three terms compare within-$P$ similarity, cross similarity between $P$ and $Q$, and within-$Q$ similarity. If $P = Q$, all three expectations are equal and the expression is zero. A characteristic kernel ensures that different distributions always produce different mean embeddings, so MMD is a true metric on distributions.

This theorem gives a computable expression for the distance between distributions that requires only kernel evaluations on samples. No density estimation is needed. This makes MMD practical in high dimensions where density estimation is intractable.

If the kernel is not characteristic, $\text{MMD} = 0$ does not imply $P = Q$. For example, a linear kernel $k(x,y) = x^\top y$ only compares means: $\text{MMD}^2 = \|\mathbb{E}[X] - \mathbb{E}[Y]\|^2$. It cannot detect differences in variance or higher moments.

Given $m$ samples from $P$ and $n$ samples from $Q$, the following U-statistic is an unbiased estimator of $\text{MMD}^2$:

$\widehat{\text{MMD}}^2_u = \frac{1}{m(m-1)} \sum_{i \neq j} k(x_i, x_j) - \frac{2}{mn} \sum_{i,j} k(x_i, y_j) + \frac{1}{n(n-1)} \sum_{i \neq j} k(y_i, y_j)$

Under $H_0: P = Q$, the statistic $m \cdot \widehat{\text{MMD}}^2_u$ converges in distribution to a weighted sum of chi-squared random variables. Under $H_1: P \neq Q$, the estimator converges to $\text{MMD}^2(P, Q) > 0$.

The estimator replaces population expectations with sample averages. Using $i \neq j$ (excluding diagonal terms) removes the bias that would come from $k(x_i, x_i)$ terms, which inflate the within-distribution similarity.

A biased estimator could be positive even when $P = Q$, inflating the false positive rate. The unbiased estimator centers correctly at zero under the null, making it suitable for hypothesis testing.

The U-statistic estimator has $O(m^2 + n^2)$ computation cost because it requires all pairwise kernel evaluations. For large datasets, this is expensive. Linear-time estimators exist (using random pairings) but have higher variance.

The MMD permutation test with a characteristic kernel is consistent: as $m, n \to \infty$, the test rejects $H_0$ with probability approaching 1 whenever $P \neq Q$. The test power depends on $\text{MMD}^2(P,Q) / \sqrt{\text{Var}(\hat{h})}$ where $\hat{h}$ is the kernel of the U-statistic. For a Gaussian RBF kernel with bandwidth $\sigma$, the power depends on the choice of $\sigma$: too small and the test only detects local differences; too large and the test only detects mean differences.

Consistency means the test eventually detects any departure from $P = Q$ given enough data. This is stronger than parametric tests, which can only detect departures in specific directions (e.g., mean shift for a t-test). The bandwidth $\sigma$ controls the "resolution" of the test.

A test that can detect any difference between distributions is valuable precisely because you typically do not know in advance how $P$ and $Q$ differ. The trade-off is that MMD may require more samples than a specialized test that targets a known difference type.

In practice, bandwidth selection strongly affects power. The median heuristic ($\sigma$ = median pairwise distance) is common but not optimal. Gretton et al. (2012) propose maximizing an estimate of test power over $\sigma$.