  Recent years have seen a surge in methods for two-sample testing, among which
the Maximum Mean Discrepancy (MMD) test has emerged as an effective tool for
handling complex and high-dimensional data. Despite its success and widespread
adoption, the primary limitation of the MMD test has been its quadratic-time
complexity, which poses challenges for large-scale analysis. While various
approaches have been proposed to expedite the procedure, it has been unclear
whether it is possible to attain the same power guarantee as the MMD test at
sub-quadratic time cost. To fill this gap, we revisit the approximated MMD test
using random Fourier features, and investigate its computational-statistical
trade-off. We start by revealing that the approximated MMD test is pointwise
consistent in power only when the number of random features approaches
infinity. We then consider the uniform power of the test and study the
time-power trade-off under the minimax testing framework. Our result shows
that, by carefully choosing the number of random features, it is possible to
attain the same minimax separation rates as the MMD test within sub-quadratic
time. We demonstrate this point under different distributional assumptions such
as densities in a Sobolev ball. Our theoretical findings are corroborated by
simulation studies.
