Adaptivity and Computation-Statistics Tradeoffs for Kernel and Distance
  based High Dimensional Two Sample Testing
  Nonparametric two sample testing is a decision theoretic problem that
involves identifying differences between two random variables without making
parametric assumptions about their underlying distributions. We refer to the
most common settings as mean difference alternatives (MDA), for testing
differences only in first moments, and general difference alternatives (GDA),
which is about testing for any difference in distributions. A large number of
test statistics have been proposed for both these settings. This paper connects
three classes of statistics - high dimensional variants of Hotelling's t-test,
statistics based on Reproducing Kernel Hilbert Spaces, and energy statistics
based on pairwise distances. We ask the question: how much statistical power do
popular kernel and distance based tests for GDA have when the unknown
distributions differ in their means, compared to specialized tests for MDA?
  We formally characterize the power of popular tests for GDA like the Maximum
Mean Discrepancy with the Gaussian kernel (gMMD) and bandwidth-dependent
variants of the Energy Distance with the Euclidean norm (eED) in the
high-dimensional MDA regime. Some practically important properties include (a)
eED and gMMD have asymptotically equal power; furthermore they enjoy a free
lunch because, while they are additionally consistent for GDA, they also have
the same power as specialized high-dimensional t-test variants for MDA. All
these tests are asymptotically optimal (including matching constants) under MDA
for spherical covariances, according to simple lower bounds, (b) The power of
gMMD is independent of the kernel bandwidth, as long as it is larger than the
choice made by the median heuristic, (c) There is a clear and smooth
computation-statistics tradeoff for linear-time, subquadratic-time and
quadratic-time versions of these tests, with more computation resulting in
higher power.
