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

Kernel two-sample tests based on Maximum Mean Discrepancy (MMD) are widely used, but the standard quadratic time MMD statistic requires evaluating $\Theta(N^2)$ kernel pairs where $N$ is the pooled sample size. Several subquadratic approximated MMD tests have been proposed to alleviate this issue, but the existing methods either compromise the test power or assume additional distributional constraints to achieve power comparable to the quadratic-time MMD test. Motivated by this gap, we propose a sub-quadratic time computational method to approximate the MMD test, achieving minimax rate-optimal power with minimal distributional assumptions. Building on ideas in fast kernel density estimation and exponentially convergent trapezoidal rule in numerical analysis, our approximation reduces all-pairs kernel summation to fast Fenwick-tree prefix-sum queries. For fixed dimension, this yields subquadratic-time algorithms for several common characteristic kernels, including Laplace, Mat\'ern, Gaussian, and inverse multiquadric kernels. The approximation error is controlled tightly enough to have the equivalent power as the minimax-optimal quadratic-time unapproximated MMD test. The same implementation remains subquadratic for the dimension $d=o(\log N/\log\log N)$, and can be paired with dimensionality-reduction algorithms when the signal is low-dimensional.