Kernel Selection is Model Selection: A Unified Complexity-Penalised Approach for MMD Two-Sample Tests

The Maximum Mean Discrepancy (MMD) is a cornerstone statistic for nonparametric two-sample testing, but its test power is dictated entirely by the chosen kernel. Because any fixed kernel inherently fails to distinguish certain distributions, the kernel must be dynamically optimised. However, data-driven optimisation violates the foundational i.i.d. assumption, forcing a strict trade-off in existing frameworks. Ratio criteria ignore this dependence, inducing overfitting and variance collapse on rich kernel classes. Conversely, aggregation methods bypass the dependence using finite grids, but this strategy cannot scale to continuous search spaces like deep kernels. To break this dichotomy, we establish data-driven kernel selection as a model selection problem. We propose Complexity-Penalised MMD (CP-MMD), a criterion derived from a uniform concentration inequality (extending Maurer's framework to the two-sample setting) that bounds the post-optimisation distribution by penalising the empirical MMD with the complexity of the kernel search space. Because this penalty mathematically absorbs the cost of optimisation, CP-MMD enables direct, grid-free maximisation over continuous parametric classes, including scalar bandwidths, polynomial coefficients, and deep network parameters. By formally accounting for optimisation complexity, we theoretically guarantee that CP-MMD maximises true test power while ensuring unconditional Type-I validity. Consequently, CP-MMD enables grid-free kernel selection across linear, polynomial, and deep regimes, matching or exceeding state-of-the-art test power.