  Over the last decade, an approach that has gained a lot of popularity to
tackle nonparametric testing problems on general (i.e., non-Euclidean) domains
is based on the notion of reproducing kernel Hilbert space (RKHS) embedding of
probability distributions. The main goal of our work is to understand the
optimality of two-sample tests constructed based on this approach. First, we
show the popular MMD (maximum mean discrepancy) two-sample test to be not
optimal in terms of the separation boundary measured in Hellinger distance.
Second, we propose a modification to the MMD test based on spectral
regularization by taking into account the covariance information (which is not
captured by the MMD test) and prove the proposed test to be minimax optimal
with a smaller separation boundary than that achieved by the MMD test. Third,
we propose an adaptive version of the above test which involves a data-driven
strategy to choose the regularization parameter and show the adaptive test to
be almost minimax optimal up to a logarithmic factor. Moreover, our results
hold for the permutation variant of the test where the test threshold is chosen
elegantly through the permutation of the samples. Through numerical experiments
on synthetic and real data, we demonstrate the superior performance of the
proposed test in comparison to the MMD test and other popular tests in the
literature.
