  We propose a series of computationally efficient nonparametric tests for the
two-sample, independence, and goodness-of-fit problems, using the Maximum Mean
Discrepancy (MMD), Hilbert Schmidt Independence Criterion (HSIC), and Kernel
Stein Discrepancy (KSD), respectively. Our test statistics are incomplete
$U$-statistics, with a computational cost that interpolates between linear time
in the number of samples, and quadratic time, as associated with classical
$U$-statistic tests. The three proposed tests aggregate over several kernel
bandwidths to detect departures from the null on various scales: we call the
resulting tests MMDAggInc, HSICAggInc and KSDAggInc. This procedure provides a
solution to the fundamental kernel selection problem as we can aggregate a
large number of kernels with several bandwidths without incurring a significant
loss of test power. For the test thresholds, we derive a quantile bound for
wild bootstrapped incomplete $U$-statistics, which is of independent interest.
We derive non-asymptotic uniform separation rates for MMDAggInc and HSICAggInc,
and quantify exactly the trade-off between computational efficiency and the
attainable rates: this result is novel for tests based on incomplete
$U$-statistics, to our knowledge. We further show that in the quadratic-time
case, the wild bootstrap incurs no penalty to test power over the more
widespread permutation-based approach, since both attain the same minimax
optimal rates (which in turn match the rates that use oracle quantiles). We
support our claims with numerical experiments on the trade-off between
computational efficiency and test power. In all three testing frameworks, the
linear-time versions of our proposed tests perform at least as well as the
current linear-time state-of-the-art tests.
