📊 statistics

Maximum Mean Discrepancy with Unequal Sample Sizes via Generalized U-Statistics

This paper extends Maximum Mean Discrepancy (MMD) two-sample testing to unequal sample sizes by leveraging generalized U-statistics, thereby eliminating the need to discard data, providing new asymptotic characterizations and power optimization criteria, and clarifying the relationship between degenerate estimators and nonzero MMD values.

Original authors: Aaron Wei, Milad Jalali, Danica J. Sutherland

Published 2026-07-10

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Aaron Wei, Milad Jalali, Danica J. Sutherland

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: Are these two piles of data actually different, or are they just random noise from the same source?

In the world of machine learning, this is called a "two-sample test." You have a pile of photos from a control group (let's call it Pile A) and a pile from a treatment group (Pile B). Your job is to figure out if the treatment changed anything. To do this, detectives use a tool called Maximum Mean Discrepancy (MMD). Think of MMD as a super-sensitive scale that weighs the "shape" of the data clouds. If the clouds look different, the scale tips, and you know there's a difference.

The Old Problem: The "Equal Sides" Rule

For a long time, this scale had a weird, annoying rule: It only worked if you had the exact same number of photos in Pile A and Pile B.

In the real world, this is a nightmare. Maybe you have 1,000 photos from a rare disease (Pile A) but 10,000 healthy photos (Pile B). The old methods said, "Oh no, we can't use this! We must throw away 9,000 of your healthy photos so the piles match." That's like throwing away 90% of your evidence just because the boxes don't match in size. It wastes data and makes your test weaker.

The New Solution: The "Generalized" Scale

This paper introduces a new way to use the MMD scale that doesn't care about equal pile sizes. The authors, Aaron Wei, Milad Jalali, and Danica J. Sutherland, figured out how to make the math work even when one pile is tiny and the other is huge.

They did this by upgrading the math from a standard "U-statistic" (which needs equal sides) to a "Generalized U-statistic."

Here is the magic trick they discovered:
Instead of scaling the result based on the total number of photos (which gets messy when sizes are different), they found you should scale it based on the smaller pile.

Old Way: Scale by $n_A + n_B$ .
New Way: Scale by $\min(n_A, n_B)$ .

They proved mathematically that if you use the smaller pile's size as your ruler, the results stay stable and accurate, no matter how lopsided your data is. They even showed that if you have a tiny pile of 100 items and a giant pile of 10,000, you can still get a very precise answer by using the 100 as your anchor.

A Surprising Twist: The "Degenerate" Mystery

While fixing the size problem, the authors stumbled upon something that might surprise other experts in the field regarding the relationship between the MMD score and the "degeneracy" of the math.

Usually, people think: "If the MMD score is zero, the two piles are identical, and the math becomes 'degenerate' (meaning the variance is zero)."
But the authors proved that the reverse isn't always true. They showed that it is sometimes possible to have a degenerate estimator (zero variance) even when the MMD score is NOT zero.

In other words, you can have a situation where the two piles are actually different (so the MMD is non-zero), but the math behaves in a "degenerate" way that usually only happens when the piles are identical. They constructed a specific example where the piles are distinct, yet the estimator is degenerate. However, they also proved that in most common, real-world situations (like using standard Gaussian kernels on data with overlapping shapes), this weird "degenerate but non-zero MMD" scenario does not happen. So, for practical purposes, you don't need to panic, but the math is now more honest about these edge cases.

The "Power-Up": Using All Your Data

The best part of this new method is that it lets you use every single piece of data you have.

The Old Way: If you had 1,000 rare cases and 10,000 common cases, you'd throw away 9,000 common cases to make a fair fight.
The New Way: You keep all 11,000.

The authors ran simulations using real image data (CIFAR-10 and CIFAR-10.1). They set up a test where one group had 1,000 images and the other had $r \times 1,000$ images (where $r$ was 1, 2, 4, or 8).

When they used the old method (throwing away data), the test power was okay.
When they used the new method (keeping all data), the test became significantly more powerful.
In their experiments, when the ratio was 8-to-1, the new method detected the difference 99.9% of the time, compared to only 82.1% for the old method.

What They Didn't Do (And What They Ruled Out)

It's important to know what this paper doesn't claim:

They did not invent a new way to pick the best kernel (the "lens" you look through). They just showed how to use the existing best-kernel methods when sample sizes are unequal.
They did not say this works for every possible mathematical weirdness. They proved it works for "common situations" (like continuous kernels with overlapping data). If the data is in two completely separate, disjoint worlds (like data that never touches), the math gets tricky, and they admit they haven't fully solved that specific edge case yet.
They did not claim to have solved the problem of "permutation testing" (a way to set the passing grade for the test). They still use permutation testing to set the threshold, but now they can do it with unequal piles.

The Bottom Line

The authors have built a bridge. Before, if your data piles were different sizes, you had to cut off the excess and hope for the best. Now, you can feed the whole, messy, unequal pile into the MMD scale. The math holds up, the test gets stronger, and you don't have to throw away any valuable evidence.

They proved this with rigorous math (theorems about asymptotic distributions) and backed it up with simulations on real image datasets. It's a solid, practical upgrade for anyone trying to compare two groups of data that aren't the same size.

Problem Statement
Two-sample testing is a fundamental problem in statistical inference aimed at determining whether two distributions, $P$ and $Q$ , differ based on samples drawn from each. While Maximum Mean Discrepancy (MMD) based tests have gained popularity for their flexibility and theoretical properties, existing techniques often rely on the assumption of equal sample sizes ( $n_X = n_Y$ ). In practice, sample sizes are frequently unequal. Applying standard MMD estimators in these scenarios typically requires discarding valuable data (e.g., by subsampling to the smaller set) to maintain the theoretical framework of U-statistics, which unnecessarily reduces test power. Furthermore, the asymptotic behavior of MMD estimators with unequal sample sizes, particularly outside proportional regimes (where $n_X/n_Y$ converges to a constant), has remained underdeveloped.

Methodology
The authors address this limitation by extending the theory of generalized U-statistics to the MMD estimator.

Generalized U-Statistics: The standard unbiased MMD estimator ( $\widehat{\text{MMD}}^2$ ) is identified as a generalized U-statistic with $c=2$ samples and kernel order $m_1=m_2=2$ . Unlike standard U-statistics which require equal sample sizes, generalized U-statistics accommodate $n_X \neq n_Y$ .
Scaling and Asymptotics: The paper derives the asymptotic distributions of the MMD estimator under both the null hypothesis ( $P=Q$ ) and the alternative ( $P \neq Q$ ). A critical methodological shift is the identification of $\min(n_X, n_Y)$ as the correct scaling factor for convergence, rather than the sum $n_X + n_Y$ used in previous proportional-regime results. This allows the theory to hold even in non-proportional regimes (e.g., $n_Y = n_X^2$ ).
Variance Characterization: The authors provide a new, cleaner characterization of the variance of the MMD estimator with unequal sample sizes. This involves decomposing the variance into terms involving the mean embeddings ( $\mu_P, \mu_Q$ ) and covariance operators ( $C_P, C_Q$ ) of the distributions.
Degeneracy Analysis: The paper rigorously analyzes the "degeneracy" of the estimator. It clarifies that while zero MMD implies a degenerate estimator, the converse is not always true: a degenerate estimator can exist with non-zero MMD under specific conditions (e.g., disjoint supports with certain kernels), though this is impossible in common settings (e.g., overlapping supports with continuous kernels).
Power Optimization: Leveraging the derived asymptotic normality for non-degenerate cases, the authors propose a criterion for optimizing kernel selection. They maximize the signal-to-noise ratio ( $\text{MMD}^2 / \sigma$ ) using plug-in estimators for the variance $\sigma^2$ , allowing for the selection of kernels that maximize test power for specific sample size ratios.

Key Contributions

Theoretical Extension: The paper extends the asymptotic theory of MMD to unequal sample sizes by applying generalized U-statistics, removing the need to discard data.
Correct Scaling Factor: It establishes that $\min(n_X, n_Y)$ is the appropriate scaling factor for convergence in both proportional and non-proportional regimes, correcting previous assumptions that relied on $n_X + n_Y$ .
Variance and Degeneracy Insights: The authors provide explicit variance formulas for unequal sample sizes and offer a refined understanding of estimator degeneracy. They prove that while zero MMD implies degeneracy, degeneracy does not necessarily imply zero MMD, a nuance often overlooked in literature. They also prove that under common conditions (Setting B: real-analytic kernels, overlapping supports), degeneracy occurs if and only if $\mu_P = \mu_Q$ .
Optimization Framework: The paper derives a practical method for optimizing kernel parameters by maximizing an estimated signal-to-noise ratio, which is shown to converge uniformly to the population optimum.
Empirical Validation: Experiments on CIFAR-10 and CIFAR-10.1 demonstrate that utilizing all available data via the proposed $\widehat{\text{MMD}}^2$ estimator and variance-based optimization yields significantly higher test power compared to methods that subsample to equal sizes (Ratio/Equal) or use standard U-statistics.

Results

Asymptotic Distributions: Under the null hypothesis ($MMD=0$), the scaled estimator $\min(n_X, n_Y)\widehat{\text{MMD}}^2$ converges to an infinite mixture of centered chi-squared distributions. Under the alternative ($MMD > 0$), if the estimator is non-degenerate, $\sqrt{\min(n_X, n_Y)}(\widehat{\text{MMD}}^2 - \text{MMD}^2)$ converges to a normal distribution.
Variance Reduction: Theoretical analysis shows that the variance of the generalized estimator $\widehat{\text{MMD}}^2$ is strictly lower than the standard U-statistic estimator $\widehat{\text{MMD}}^2_U$ when sample sizes are unequal, and can be up to a factor of two lower when one sample size is asymptotically dominant.
Experimental Performance: In experiments distinguishing CIFAR-10 from CIFAR-10.1 with varying sample size ratios ( $r$ ), the proposed "Ratio/Ratio" (RR) method, which uses all data and optimizes the signal-to-noise ratio, consistently outperformed the "Ratio/Equal" (RE) baseline. As the imbalance increased ( $r=8$ ), the power of the RR method approached 1.0, while the RE method plateaued at roughly 0.82.

Significance
The paper claims to resolve a long-standing limitation in MMD-based two-sample testing by providing a theoretically rigorous framework for unequal sample sizes. By preserving all available data, the proposed method enhances test accuracy and applicability in realistic settings where data collection is often asymmetric. The unification of the framework ensures that the new approach reduces to existing methods when sample sizes are equal, maintaining theoretical consistency while extending utility. The work also corrects misconceptions regarding the relationship between MMD values and estimator degeneracy, providing a more robust foundation for kernel selection and test design.