Research map / Learning theory and algorithms / Kernels and regression theory

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

NeurIPS 2026 · Learning theory and algorithms › Kernels and regression theory · approach: Kernel two-sample testing

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes CP-MMD, a complexity-penalized objective for data-driven MMD kernel selection that uses a two-sample uniform concentration bound to enable grid-free optimization over continuous kernel classes while keeping permutation-test Type-I validity via sample splitting.

Problem

Kernel choice dominates MMD two-sample test power, but data-driven kernel optimization breaks the i.i.d. assumption behind MMD test theory; ratio criteria overfit and collapse, while aggregation methods need finite grids that do not scale to continuous or deep kernel classes.

Approach

Treats kernel selection as model selection over a composite-kernel class k(h(x),h(x')) and subtracts a calibrated Lipschitz-based complexity penalty from the unbiased empirical MMD, derived from a uniform concentration inequality that holds over the whole class, so optimization can run directly over continuous parameters.

Key results

• On a multi-scale 2D mixture at mean shift 0.30, CP-MMD reaches power 1.00 versus 0.47 for the median heuristic.
• On the kurtosis task at df=20, CP-MMD gets 0.90 power versus 0.80 for MMDAgg.
• Deep-kernel table at d=20, n=50: CP-MMD 1.00 versus Liu 0.16 and Plain 0.14.

Surprising findings

• Liu's ratio criterion under H0 frequently collapses (variance collapse) with J_Liu values in the thousands while the empirical MMD is near zero.
• The calibrated penalty constant is about three orders of magnitude smaller than the worst-case theoretical constant (about 0.008 vs about 30).

Limitations

• Calibrated penalty constant is reliable only at moderate MLP widths and degrades at wider widths.
• Complexity proxy is conservative; worst-case and calibrated constants differ by three orders of magnitude and the gap is handled empirically.
• Liu's epsilon-mixture kernel lies outside the formal coverage; its inclusion is heuristic.

Experimental setup

Datasets: HDGM synthetic Gaussian mean-shift UCI Higgs CIFAR-10/10.1

Benchmarks: HDGM UCI Higgs CIFAR-10/10.1

Metrics: test power type-I error per-test runtime

Baselines: Median heuristic MMDAgg MMD-FUSE Liu deep-feature kernel Plain MMD maximization

Builds on: MMDAgg MMD-FUSE median heuristic Liu et al. deep kernel ratio criterion

Closest papers by meaning

• MMD-Fuse: Learning and Combining Kernels for Two-Sample Testing Without Data Splitting (NeurIPS 2023 · similarity 0.92)
• Kernel-based Maximum-of-difference Test for Two-sample Comparison (ICML 2026 · similarity 0.91)
• A permutation-free kernel two-sample test (NeurIPS 2022 · similarity 0.91)
• Learning Kernel Tests Without Data Splitting (NeurIPS 2020 · similarity 0.90)
• DUAL: Learning Diverse Kernels for Aggregated Two-sample and Independence Testing (NeurIPS 2025 · similarity 0.89)
• Kernel conditional tests from learning-theoretic bounds (NeurIPS 2025 · similarity 0.85)