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

Minimax Optimal Kernel Two-sample Testing in Sub-quadratic Time

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 abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a sub-quadratic-time kernel two-sample test based on MMD that aims to match the power of the quadratic-time MMD test without extra distributional assumptions, per the abstract.

Problem

Quadratic-time MMD two-sample tests require Theta(N^2) kernel evaluations on pooled sample size N; existing subquadratic approximations either lose power or impose extra distributional assumptions.

Approach

Abstract only states the goal: a subquadratic MMD-based test that is minimax optimal in power without additional distributional assumptions; the specific mechanism is not stated in the provided text.

Experimental setup

Baselines: quadratic-time MMD test subquadratic approximated MMD tests

Builds on: maximum mean discrepancy test

Closest papers by meaning

• A permutation-free kernel two-sample test (NeurIPS 2022 · similarity 0.91)
• Kernel Selection is Model Selection: A Unified Complexity-Penalised Approach for MMD Two-Sample Tests (NeurIPS 2026 · similarity 0.89)
• MMD-Fuse: Learning and Combining Kernels for Two-Sample Testing Without Data Splitting (NeurIPS 2023 · similarity 0.89)
• Kernel-based Maximum-of-difference Test for Two-sample Comparison (ICML 2026 · similarity 0.88)
• Subquadratic Algorithms for Kernel Matrices via Kernel Density Estimation (ICLR 2023 · similarity 0.87)
• The Polynomial Stein Discrepancy for Assessing Moment Convergence (ICML 2025 · similarity 0.84)