A permutation-free kernel two-sample test
Authors: Shubhanshu Shekhar
Ilmun Kim
Aaditya Ramdas
Venue: NeurIPS 2022 Accept (2022)
Keywords: two-sample testing
kernel-mmd
permutation-free tests
U-statistics

Abstract: The kernel Maximum Mean Discrepancy~(MMD) is a popular multivariate distance metric between distributions. The usual kernel-MMD test statistic (for two-sample testing) is a degenerate U-statistic under the null, and thus it has an intractable limiting null distribution. Hence, the standard approach for designing a level-$(1-\alpha)$ two-sample test using this statistic involves selecting the rejection threshold as the $(1-\alpha)$-quantile of the permutation distribution. The resulting nonparametric test has finite-sample validity but suffers from large computational cost, since the test statistic must be recomputed for every permutation. 

We propose the cross-MMD, a new quadratic time MMD test statistic based on sample-splitting and studentization. We prove that under mild assumptions, it has a standard normal limiting distribution under the null. Importantly, we also show that the resulting test is consistent against any fixed alternative, and when using the Gaussian kernel, it has minimax rate-optimal power against local alternatives.  For large sample-sizes, our new cross-MMD provides a significant speedup over the MMD, for only a slight loss in power.

A permutation-free kernel two-sample test
Shubhanshu Shekhar
Immun Kim
Department of Statistics and Data Science Carnegie Mellon University
Department of Statistics and Data Science
Department of Applied Statistics
Pittsburgh, PA 15213
Yonsei University
shubhan2@andrew. cmu edu
i ilmun@yonsei. ac
Aaditya Ramdas
Department of Statistics and Data Science
Machine Learning Department
Carnegie Mellon University
aramdas@stat. cmu edu
Abstract
The kernel Maximum Mean Discrepancy (MMD) is a popular multivariate distance metric between distributions that has found utility in two-sample testing. The usual kerDel-MMD test statistic a degenerate U-statistic under the null, and thus it has intractable limiting distribution. Hence, to design level-a test, one usually selects the rejection threshold as the (1 11-a -1-aa--qunnille of the permutation distribution. The resulting nonparametric test has inite-sample validity but suffers from large computational cost, since every permutation takes quadratic time. We propose the cross- Cross-MMD, new quadratic-time tame MMD test statistic based on sample-splitinn and studentization. We prove that under mild assumptions, the cross-MMD has a limiting standard Gaussian distribution under the null. Importantly, also show that the resulting test is consistent against any fixed alternative, and when using the Gaussian kernel, it has minimax rate-optimal power against local alternatives. For large sample sizes, our new cross-MMD provides significant speedup over the MMD, for only slight loss in power.
Introduction
.,, iid
We study the taople testing problem: given (Yi...., Y,,) iid. Q, we test the null hypothesis Ho P Q against the alternative H1 P Q. This is nonparametric hypothesis problem with composite null hypothesis and a composite alternative hypothesis. finds applications in diverse areas such as testing microarray data, clinical diagnosis, and database attribute matching (Gretton et al. 2012a).
and Y
popular approach solving this problem is based on the kernel-MMD distance between the two empirical distributions (Gretton et al., 2006). Given a positive definite kernel k, the kernel-MMD distance between two distributions P and Q X', denoted by MMD(P, Q), is defined
MMD(P.Q) = || ulla, where vd-) / (dP,)))(()), and v(-) f (Qxx))Q((x). (1)
Above, (4 and are commonly called "kernel mean maps". and denote the kernel mean embeddings of the distributions P and Q into the reproducing kernel Hilbert space (RKHS) associated with the positive-defintte kernel kt and || | denotes the corresponding RKHS norm. Under mild conditions on the positive definite kemne & (Sriperumbudur et al.) 201 I). MMD is a metric the space of
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

probability distributions, Gretton et al. (2006) suggested using an empirical estimate of the squared distance as the test statistic. In particular, given X and Y. define the test statistic
MMD
1 n(n - 1 1)m(m
Σ 1siti 1Si Sm
XY,
where h(2, 2', y, v/) = x(,,'')=)))))) k(,, 5²) k(y x²) + tly 3/) The above statistic has an alternative form that only takes quadratic time to calculate.
The MMD test rejects the null if MMD exceeds a suitable threshold T = T(a) that ensures the false positive rate is at most a. For "characteristic kernels", this test is consistent against fixed alternatives, meaning the power (the probability of rejecting the null when P * Q) increases to one as m, n - oo.
The difficulty in practically determining T will play a key role in this paper. It is well known that is an instance of a "degenerate two-sample U-statistic", meaning that:
when P Q, MMD 2
Under Ho. Ep[h(a, y, Y")] = E (,(, Y. y')l = 0.
(Above, 2, B, y, y' are fixed, and the expectations are over X, Y, y lid. P.) As consequence, its (limiting) null distribution is unwieldy; it is an infinite sum of independent x² random variables weighted by the eigenvalues of an operator that depends on the kernel & and the underlying distribution P (see equation (10) in Appendix Ap. Since P is unknown, one cannot explicitly calculate т.
In practice, permutation -bsse approach is commonly used, where T is set as the (1 quuamtle of the kernel-MMD statistic computed on permuted versions of the aggregate data (X, Y). The resulting test has finite-sample validity, but its practical applicability is reduced due to the high computational complexity; if = 200 permutations are used, the (permuted) test statistic must be recomputed 201 times, rather than once (usually, B is chosen between 100 and 1000).
Due to the high computational complexity of the permutation test, some permutation-frre alternatives for selecting have been proposed. However, as we discuss in Section 1.2, these alternatives are either too conservative in practice (using concentration inequalities), or heuristics with no theoretical guarantees (Pearson curves and Gamma approximation) or are only shown to be consistent in the setting where the kernel does not vary with n (spectral approximation). We later recap some 2
computationally efficient alternatives to MMD but these have significantly lower power.
As far as we are aware, there exists no method in literature based on the kernel-MMD that is (i) permutation-free (does not require permutations), (ii) consistent against any fixed alternative, (iii) achieves minimax rate-optimality against local alternatives, and (iv) is correct for both the fixed kernel setting (k fixed as m, n + 20) and the changing kernel setting (k changes as function of m, n, for instance, by selecting the scale parameter of a Gaussian kernel in a data-driven manner).
Our work delivers novel and simple test satisfying all four desirable properties. We propose new variant of the kernel-MMD statistic that (after studentization) has a standard Gaussian limiting distribution under the null in both the fixed and changing kernel settings, in low- and high nigh-dimmesional -tattittoossststttsss tradcoff: our permutation -free test loses about v2 factor in power compared to the standard kernel-MMD test, but it is hundreds of times faster.
settings. There is
Remark 1. Let P(X) denote the set of all probability measures on the observation space X, where often use X = ddd for some d > 1. For simplicity, in the above presentation, the distributions P. Q. kernel A and dimension d did not change with sample size, and this is the setting considered in the majority of the literature. Later, we prove several of our results in significantly more general setting where P, Q, d, & can vary with n, m. Under the null, this provides a much more robust type-I error control in high- dighniimessional settings, even with data- dependentt kernels. Under the alternative, this provides a more fine-grained power result. To elaborate on the latter, we assume that for every m, the pair (P,Q) (P,, : Qx) E P("' C P(X) x P(X)) for some sequence (P(") n. m 2 2). The class ! is such that with increasing n and m. it contains pairs (P', .') that are increasingly closer in some distance measure 2 thus the alternatives
approach the null and be equal in the
limit. That is, Anm == inf (P' (P)())))( e(P', ,²) decreases with n, m, and such alternatives are called local alternatives (as opposed to fixed alternatives). This framework allows us to characterize the detection boundary of a test, that is, the smallest perturbation from the null (in terms of An,m) that can be consistently detected by test.
2

---

Paper outline. We present an overview of our main results in Section 1.1 and discuss related work in Seecciion I.2 In Section 2] we present the cross-MMD statistic and obtain its limiting null distribution in |n/ectiion22 2.1 We demonstrate its consistency against fixed alternatives and minimax rate- optimality against smooth local alternatives Section 2.2] Section B contains numerical experiments that demonstrate our theoretical claims. All our proots are in the supplement.
1.1 Overview of our main results
We propose a variant of the quadratic time kernel-MMD statistic of ( that relies on two key ideas: (i) sample splitting and (ii) studentization. In particular, we split the sample X of size n into
X1 and X2 sizes n1 2 and n22 2 1, respectively (and Y of size m 2 2 into Y and Y of sizes
mi 2 1 and m2 2 1), and define the two-sample cross kernel-MMD statistic xMMD as follows:
xMMD
1
B1
72
m1
122
Xx, My).
71711722122
Our final test statistic is xMMD == xMMD 16, where ē is an empirical variance introduced in
Our first set of results show that quite generally, xMMD has an (O, 1) asymptotic null distribution. Theorem obtains this result in the setting where both the kernel & and null distribution /' are fixed. This is then generalized to deal with changing kernels (for instance, Gaussian kernels with data-driven bandwidth choices) in Theorem 5| Finally, in TTherem 15 in Appendix A significantly expand the scope of these results by also allowing the null distribution to change with n, and also weakening the moment conditions required by Theorem 5]
Null distribution of xMMD
Power vs Sample-Size
Power Computation
0.4
d=10
Probability density
d=500
0.8
0.3
0.8
N(0.1)
Power
Power
0.6
0.6
0.2
MMD-perm
0.4
0.4
MMD-perm
xxMMD
0.1
xMMD
0.2
0.2
0
5
100
200
300
400
10
10
10
Statistic Value
Sample-Siz Size (n+m)
Running time (seconds)
The first figure shows the distribution of our proposed statistic xMMD predicted by Theo- rem 5) under the null for dimensions d = 10 and d = 100. The statistic is computed with Gaussian xxp(-snlla || y y)l2)) with scale parameter s, chosen by the median heuristic
Figure I:
kernel (k,,, (x. for different choices of n, m and d, and with samples X and Y drawn from a multivariate Gaussian distribution with identity covariance matrix. The second figure compares the power curves of the
2
two-sample test using the xMMD) statistic with the kernel-MMDD permutation test (with 200 per- mutations). The final figure plots the power vs computation time for the two tests. The size of the markers proportional to the sample-size used in the test.
Our main methodological contribution is the "xMMD test", denoted V, which rejects the null if 2
xMMD exceeds 21-a, which is the (1 a) -quuntie of (0, 1). Formally,
xMMD test: (XX, Y)
(3)
&MMD 241-a"
By the previous results, V has type-I error most a, meaning that E (X W) S under the null. We next study the power of the xMMD test in Section 2.2 First, the fixed alternative case, i.e., when the distributions P a Q do not change with n, show in Theorem 7 that the xMMD test
3

---

implemented with any characteristic kernel is consistent under bounded fourth moment condition. Next, we consider the more challenging case of local alternatives, i.e., when the distributions, Pa * Qn. change with n. In Theorem 8] we first identify general sufficient conditions for the xMMD test to be uniformly consistent over a class of alternatives. Then, we specialize this to the case when Pa and Qn admit densities Pn, and On with Pr In II 2 A, for some A, + 0. We show in Theorem 9| that the xMMD) test with a Gaussian kernel hi,, (I, y) = exp( - - y/12), with scale parameter 8n increasing at an appropriate rate can consistently detect the local alternatives {An n 2 1} decaying at the minimax rate.
Finally, we note that while our primary focus in the paper is on the special case of kernel-MMD statistic, the ideas involved in defining the xMMD statistic can be extended to the case of general two-sample U-statistics. We describe this in [Appendix D.I] and obtain sufficient conditions for asymptotic Gaussian limit of the resulting statistic, possibly of independent interest.
1.2 Comparisons to related work
Attempts to avoid permutations. There have been some prior attempts to avoid permutations, but they are either heuristics (no provable type-I error control) or have poor power (higher type-ll error).
The first approach to obtaining a rejection threshold is based on large deviation bounds for the MMD statistic (Gretton et al.] 2006, $ 3) or the permuted MMD statistic (Kim) 202T 5). The resulting tests esstrbuttion-free, but they tend to be too conservative (type-I error much less than a, resulting in low power). Another approach involves choosing the threshold based on parametric estimates of the limiting null distribution. For example, Gretton et al. (2006) suggested fitting to the Pearson family of densities based on the first four moments, while Gretton et al. (2009) introduced a more computationally efficient method using a two-parameter Gamma approximation. However, both of these methods are heuristic and do not have any consistency guarantees.
Gretton et al. (2099) introduced a spectral method for approximating the null distribution using the eigendecomppoition of the gram matrix. They showed that the resulting distribution converges to the true null distribution as long as the square roots of the eigenvalues associated with the kernel operator are summable. While this method is asymptotically consistent, the conditions imposed on the kernel more stringent than that used in our work. Furthermore, this method was shown to be consistent only in the fixed kernel (or low-dimensional) setting. Hence, it is unknown whether the results carry over to the case of kernels varying with sample size high-dimensional settings. This method is also computationally nontrivial due to the need for a full eigendecomposition. Keeping only the top few eigenvectors is another heuristic, but this introduces guarantees; as a result this method is rarely used in practice. Our methods are simpler (no extra hyperparameter), faster (closed-form threshold), and more robust (type error guarantees also hold for changing kernels, and in high-dimensional settings).
extra hyperparameter and loses theoretical
Changing the statistic: block-MMD and linear-MMD statistics. An idea more closely related to ours is that changing the test statistic itself would help make it cheaper to compute and also yield a tractable limiting distribution. One approach splits the observations into disjoint blocks, compute the kernel-MMD statistic on every block, and the final test statistic averages over all the blocks. If the size of each block is fixed, we get linear-time kcDDel-MMD (Gretton et al. 2012a b). The case of block sizes increasing with n. m was studied by Zaremba et al. x Ramdas et al. (2015). Depending on the block size (b), the computational complexity of block-MMI statistic varies from linear (constant
b) to quadratic (b- = ((n)). Further, if L = o(n), then one gets a Gaussian null distribution as well.
Our proposed statistic is fundamentally different from the block-MMD statistics, despite both being incomplete U-statistics (Lee) 1990). In particular, the block-MMD statistics can be understood as building block-diagonal approximation of the gram matrix. On the other hand, our proposed cross-MMD statistic uses the off-diagonal blocks of the gram matrix, exactly the blocks that the block-MMD with two blocks (b- n/ 22 excludes! The reason that this is a sensible thing to do is nontrivial, and our test is motivated quite differently from the block-MMD. In fact, when b = n/2. the block-MMDI does not have Gaussian null, but the cross-MMD does.
n222)
For the block-MMD with = o(ni). the Gaussian null distribution is achieved at the cost suboptimal power, as observed empirically in Zaremba et al. (2013), and proved by Reddi et al. (2015) for the case of linear-MMP and |Ramdas et al. (2015) for general block-MMDD statisties. particular, their power is worse by factors scaling with n, which means that they are not minimax rate optimal. In

---

contrast, our test uses exactly half the elements of the gram matrix, and its power is about v2 worse than the MMD test, independent of and d, and we prove explicitly that achieves the minimax rate.
Beyond the kernel-MMD. The literature on two-sample testing is vast, and one can move even further away from the kernel-MMD (than the block-MMD) while retaining some of its intuition. For example, Chwialkowski et al. 2015) proposed linear-time test statistic by computing the average squared-distance between the empirical kernel embeddings at J randomly drawn points. Jitkrittum iet al. (2016) proposed a variant of this statistic in which the J points are selected to maximize a lower bound on the power. In both cases, when the kernel & being used is analytic, in addition to being characteristic and integrable, the authors showed that the limiting distribution under null for this statistic is a combination of independent x2 random variables. However, similar to the spectral method of Gretton et al. (2009), the high-dimensional behavior of these statistics are unknown. In fact, some preliminary experiments with R n in Amppeeddix H.3 suggest that these linear-time statistics have different null distribution in this regime. Further, the authors only proved consistency of these tests against fixed alternatives, but their power is not known to be minimax rate optimal. In contrast, our statistic has the same limiting distribution in low- and high-dimensional settings even with changing kernels, and is provably minimax rate optimal for smooth alternatives, and it is a much more direct tweak of the usual MMD test.
One-sample (goodness-of-fit testing. Kim and Ramdas (2200) proposed and analyzed a similar studentized cross U-statistic in the simpler one-sample setting. Our work has different motivations: our primary goal in this paper is to design a permutation-
kemel-MMMD test that does not significantly sacrifice the power, while Kim and Ramdas (2020) pursued the related but different inference, which means having the same limiting distribution in low-
goal of dimension-agnone dimensional and high-dimensional settings. Nevertheless, our results can be seen as an extension of their methods to two-sample testing. Our proof's also build on their advances, but we require a more involved analysis since in their case the second distribution is known (making it point null).
2 Deriving the cross-MMD test
In this section, we present our test statistic and investigate its limiting distribution. First note that the squared kernel-MMD distance between two probability measures P and Q can be expressed as an inner product, namely (u 1. 14 v)k. The usual kemel-MMD statistic is obtained by plugging the empirical kernel embeddings into this inner product expression and removing the diagonal terms to make it unbiased. Our proposal instead considers pairs of empirical estimates (Pi, (2) and (2) constructed via sample splitting, and use the inner product between م in and fi2 - Bo instead. This careful construction allows us to obtain a Gaussian limiting distribution after studentization. To elaborate, recall from /ecction 1.1 that we partition X into X, and X2, and similarly Y into Y1 and Y2. We then compute empirical kernel embeddings based on each partition, yielding p1 := ni E ", P == n² Em= k(Xp, -), P1 == m, EØ=1 AY,,.-) and 02 := m2 Σn= k(yr,)). )). Using these embeddings coupled with the kernel trick, the cross U-
statistic (2) can be written xMMD (ū 22 Øo 22) To further motivate our test statistic, denote x,i == (k(X,,.) -, A22 - 12)2 for i = 1..... n2 and Uy == (A(Y,,.), fi 22)x for j 1, ......... m1. Then the cross U-statistic can be viewed the difference between two sample means: xMMDD
2 1 Ee Ux 1. ET Uv.j- Since the summands are independent conditional on mi
n1
X2 and Y2. one may expect that xMMD is approximately Gaussian after studentization. Our results in Section 2.1 2. formalize this intuition under standard moment conditions, where takes some care to remove the above conditioning, since we care about the unconditional distribution.
Let us further denote the sample means of Ux, 's and Uy.5 's by Ux and Uy respectively, and define
x
Σ -x)= ni
1
03
1
(Uv. Uy)² and 22 1 nn
xx
Log-
1
oy-
(4)
mi
mi
Now we have completed the description of our studentized cross U-statistic xMMD = xMMD and the resulting test V in (3) The asymptotic validity of the xMMD test is guaranteed by Theorem that establishes the asymptotic normality of XMMD under the null.
/
15
5

---

Kemel-MMD
Block MMD
Cross-MMD
X1
KLA, X2)
k(X,, X,)
kLX,,
A(X, X))
R(X..
X1
%1
15
JLY. Ki)
A.E.
%
X,),
RCY, YD
R(Y, x))
RIX,
X
X1
X2
Figure 2: The figures visually illustrate the main differences in computing the usual quadratic-time kernel-MMD statistic (left), block-MMD (center) statistic, and our new cross-MMD statistic. In particular, the quadratic-time kernel-MMD statistic considers all pairwise kernel evaluations, with the exception of the diagonal terms. For block-MMD, we obtain the statistic by partitioning the data into several disjoint blocks; and then taking the average of the kernel-MMD statistic calculated over these disjoint blocks. Finally, our cross-MMI statistic first splits the data into two disjoint parts (red and black), and then uses the pairwise kernel evaluations with data from different splits. Interestingly, the observation pairs included by our cross-MMD statistic are exactly complementary to those included by the block-MMII statistic.
Remark 2 (Computational Complexity). The overall cost of computing the statistic XMMD is O ((n + m))), and in particular, both xMMD and ō have quadratic complexity. To see this, note that xMMD can be expanded into (f1,(t)) (22) (21, (p1, P2)x (in, 22)/- Each of these terms can be computed in O (nn+ m))). Similarly, each in the summations defining σ and oy also require ((n + m))) computation, implying that the ā also has O(n + m)²) complexity. Remark 3. To simplify notation in what follows, denote m my, where m. is some unknown nondecreasing sequence such that lim my = oc. This still permits m. to be separate quantities growing infinity at potentially different rates, but it allows to index the sequence of problems with the single index (rather than m, n1). We will use kn, dn. Xn. Pn and Qn to indicate that quantities could (but do not have to) change as increases, and drop the subscript when they are fixed. Furthermore, unless explicitly stated, we will focus on the balanced splitting scheme, i.e., 72 = |n/2] and my m/2 in what follows, because we currently see no apriori reason split asymmetrically.
2.1 Gaussian limiting distribution under the null hypothesis
As shown in Figure 1, the empirical distribution of xMMD resembles standard normal distribution for various choices of m, n and dimension under the null. In this section, we formally prove this statement. Recalling the mean embedding μ from (I). define
k(æ, v) (k<(z.-) μe, k(y, U)kk-
(5)
Theorem Suppose that and P do not change with n. Ifo < Ep(M(X,X')9) < xc for
X, X' idd P. then xMMD d (0,
general result that implies Theorem 4 Theorem 5. Suppose P fixed, but the kernel kn changes with If
We next present
lim Ep (x) 1-0000 Eplk, (X1, )22
X2
m, = O, and
lim n00
exists,
(6)
Σ X2
where 1E denote the eigenvalues of introduced in 16 then we have xMMD N(O.
easy to check that condition (6) trivially satisfied the kernels {hi : n 2 1} are uniformly bounded by some constant; prominent examples the Gaussian or Laplace kernel with sample size

---

dependent bandwidth. Thus, the above condition really exists to handle unbounded kernels and heavy- tailed distributions. To motivate this requirement, we recall Bentkus and Götze| (1996) (see (see/Fact IT in Appendix A) who proved studentized CLT for i.i.d. random variables in a triangular array setup: Wi,.: W2......, Wn,n iid. Pr. Define Va VT W (W w,)) where Wn ( Wt,.\nn n/. They showed that sufficient condition for the asymptotic normality of V2 is that lim Er, [WP,n) / Br,, [W?,, 1 0. (This last condition is trivially true if Pr does not change with n,, meaning that the triangular array setup is irrelevant and Wi.n can be replaced by W1.)
Our requirement is slightly stronger: condition (6) with Kn 1,, replaced by WI.n implies the previous condition of Bentkus and Götze (996) (details in Remark 12 in Appendix A). We need
this stronger condition, because the terms in the definition of xMMD are not i..dd (indeed, not even independent), and thus we cannot directly apply the result of Bentkus and Götze (1996). Instead, we take a different route by first conditioning on the second half of data (X2, X2), then showing the
conditional asymptotic normality of the standardized x.MD (i.e., divided by conditional standard deviation instead of empirical), and finally showing that the ratio of conditional and empirical standard deviations converge in probability to 1 (see Appendix B
Finally, we note that the result of Theorem 5 can be further generalized in several ways: (i) instead of a fixed P and changing ki,, we can consider a sequence of pairs {(Pa, k,) 2 1} changing with n, (ii) we can let P. E P!!) for a class of distributions changing with n, and obtain the Gaussian limit uniformly over all elements of p((), and finally, (iti) the moment requirements on kn stated in condition in (6) can also be slightly weakened. We state and prove this significantly more general version of Theorem 5|in Appendix B
Remark 6. In the statement of the two theorems of this section, the splits (X1, 11) and (X2, 12) are assumed to be drawn i.i.d. from the same distribution P. However, a closer look at the proof of [Theorem 5) indicates that the conclusions of the above two theorems hold even when the two splits are independent and drawn i.i.d. from possibly different distributions; that is (X1, Y1) and (X2, Y2) are independent of each other and drawn i.i.d. from distributions P1 and P2 respectively.
with Pi * Pg. In particular, under this more general condition, the asymptotic normality of xMMD still holds, and the resulting test L still controls the type-1 error the desired level. This may be useful for two-sample testing in settings where the entire set of data is not i.i.d., but two different parts of the data were collected in two different situations. The usual MMD can also handle such scenarios by using a subset of permutations that do not exchange the data across the two situations.
2.2 Consistency against fixed and local alternatives
Here, we show that the xMMD test V introduced in (3) is consistent against fixed alternative and also has minimax oute-optimal power against smooth local alternatives separated in L norm.
We first show that analogous to Theorem 4 xMMD is consistent against fixed alternatives.
Theorem 7. Suppose P, Q, k do not change with n, and P + Q. If l: is a characteristic kernel satisfying O < Ep (K(,, [] < oc, and 0 < Bo Y2) < co, then the xMMD test is consistent, meaning it has asymptotic power
The moment conditions required above are mild, and are satisfied trivially, for instance, by bounded kernels such as the Gaussian kemne. The "characteristic" condition is also needed for the consistency of the usual MMD test (Gretton et al. 2012a), and is also satisfied by the Gaussian kernel.
Recalling Remark I we next consider the more challenging setting where dn, kn can change with n. and (Pn, Q..)) can vary within class (2) P(Xx)) P(X,) that can also change with n. We present a sufficient condition under which the xMMD test & is consistent uniformly over ((1) Define Tn, MMD(Pa, Qn), which is assumed nonzero for each n but could approach zero in the limit.
Theorem 8. Let (6n : n 2 2} denote any positive sequence converging to zero. If
Er..Q, (22)
Vr..q. (xMMD' O, where V denotes variance, (7)
lim 20000
sup (P..Q.)EP!!)
7

---

((1) n = {(P, Q) with densities p, q E ( : |lp 9ll62 2 An), then limn->o (r Q.)..)))) Q...Q. - V (X, Y) = 0, meaning the xMMD test is consistent.
Note that while any sequence {6,) converging to zero suffices for the general statement above, the condition (7) is easiest to satisfy for slowly decaying 6n, such as 6, 1/ log log for instance.
2
The sufficient conditions for consistency of V/ stated in terms of ō and xMMD in 7 can also be translated into equivalent conditions on the kernel function kn similar to ( and we present the details in Appendix C Importantly, if Pn.. Qn, dn are fixed and k, is bounded, then both EE[²") and
V(xMMD ) are (11/n) and "t is a constant, so the condition trivially satisfied, and fact the above condition is even weaker than the fourth-moment condition of the previous theorem.
2.3 Minimax rate optimality against smooth local alternatives
We now apply the general result of Theorem 8 to the case where the distributions P., and Qn admit Lebesgue densities Pn. and On that lie in the order /3 Sobolev ball for some >> 0, defined as W1..((M {f X R f is continuous, and f'1 w [[] [ww M < oc).
Formally, we define the null and alternative class of distributions as follows:
p(00) (P with density p: p (M)), and
for some sequence A, decaying to zero. In particular, we assume that under Ho, P.. = On and Pn E (00), while under H1, we assume that (Px, Qn) E (())
Our next result shows that for suitably chosen scale parameter, the xMMD test V with the Gaussian kernel is minimax rate-optimal for the above class of local alternatives. For simplicity, we state this result with n m, noting that the result easily extends the case when there exist constants 0 < c S C, such that c S n/m m < C.
Theorem 9. Consider the case when n = m, and let (An n 2 1} be a sequence such that lim,-+oc A₂ An = cc. On applying the xMMD test & with the Gaussian kernel ki,, (I. y) = exp(- 181--8,11 -,1111 1| - -y12), if we choose the scale as 8n x n (d++4)))) then we have
lim 1-+00 (o)
sup Ep. (X,
and lim
inf
(V. 1.
(8)
(Pa. (a
The proof of this statement is in Appendix C and it follows by verifying that the conditions required by Theorem 8 are satisfied for the above choices of A, and 8n.
Remark 10. Li and Yuan (2019) Theorem 5 (ii) showed converse of the above statement: if 30, then there exists an a E (0, 1) such that any asymptotically level a test
lim,--so A, (a (a=
T must have o inf (P. E..Q D (X, Y)] 1. Hence, the sequence of {An 2 1} used in Theorem represents the smallest Le-deviati that can be detected by any test, and (8)
shows that our xMMD test V can detect such changes, establishing its minimax rate-optimality.
3 Experiments
We now present experimental validation of the theoretical claims of the previous section. In particular, experiments demonstrate that (i) the limiting null distribution of x.MDD is N (0, 1) under wide range of choices of dimension d, sample sizes n, m and the kernel k, and (ii) the power of our xMMD test is competitive with the kemne-MMMD permutation test. We now describe the experiments in more detail. Additional experimental results are reported in Appendix
2 Limiting null distribution of xMMDD. We showed in Theorem 15 that the statistic xMMD has a limiting normal distribution under some mild assumptions. We empirically test this result when X and W are drawn from NO, Ia) with 0 denoting the all-zeros vector in IRd, and in particular, study the effects of (i) dimension: d = 10 versus d 500, (ii) skewness of the samples: n/m = versus n/m = 0,1, and (iii) choice of kernel: Gaussian versus Quadratic, both with data-dependent scale parameters using median heuristic.
8

---

As shown in the first row of Figure 3/ the distribution of xMMD is robust to all these effects, and is close to (0, 1) in all cases. In contrast, the distribution of the kernel-MMD statistic scaled by its empirical standard deviation (obtained using 200 bootstrap samples) in the bottom row Figure 3) shows strong changes with these parameters. We present additional figures and details of the implementation in Appendix
xMMD (n/m- = 0.1)
xMMD (n/m- 1)
xMMD (n/m 10)
xMMD (n/m 1)
Probability density
10
500
N 1j
MMD (n/m 0.1)
MMD (n/m
MMD (n/m 10)
MMD (n/m
Probubility density
Figure 3: The first two columns show the null distribution of the xMMD statistic (top row) and the MMD statistic scaled by its empirical standard deviation (bottom row) using the Gaussian kernel with scale-parameter chosen using the median heuristic. The last two columns show the null distribution for the two statisties using the Quadratic kernel with scale parameter chosen using the
median heuristic. The figures demonstrate that the null distribution of MMD changes significantly with dimension (d), the ratio n/m m and the choice of the kemel, unlike our proposed statistic.
Evaluation of the power of V. For d 2 and j < d, let Ge,j denote the element of idd with first j coordinates equal e, and others equal O. We consider the two-sample testing problem with P ((, Ia) Q N(a..j. Ia) for different choices of and d and j. We compare the performance of our proposed test with the kerDel-MMD permutation test, implemented with B = 200 permutations, and plot the power-curves (using 200 trials) in [Figure 4 We also propose a heuristic for predicting the power of the permutation test (denoted by Ppem) using the power of V (denoted by pv) as follows (with & denoting the standard normal edf, and za its ax-quantile):
Ppem &b (za + 2
(Φ ( (0='(pv) za))
This heuristic motivated by the power expressions derived by Kim and Ramdas (2020) for the problems of one-sample Gaussian mean and covariance testing (we discuss this further in Apppenix E).
The term v/2 in the above expression quantifies the price to pay for sample-splitting. As shown in/Figure 4] this heuristic gives us accurate estimate of the power of the kernel-MMD permutation test, without incurring the computational burden.
We now ROC curves compare the tradeoff between type-I and type- II errors for the usual MMD,
linear and block-MMDs with xMMD) We the distributions P N Ta) and Q N (o Ia) as before, and plot results for (d, j) {100 5, 0.2), (100, 20, 0.15), (500, 100, 0.1)}
in Figure 5) Due to sample splitting, the tradeoff achieved by our proposed statistic is slightly
2
worse than that of MMD but significantly better than other computationally efficient variants of kernel-MMD statistics. More details about the implementation are presented in Appendix E
4 Conclusion and future work
We proposed variant of the kernel-MMD statistic, called cross-MMD, based on the ideas of sample- splitting and studentization, and showed that it has standard normal limiting null distribution. Using

---

(d.j..c) = (10,5,04 0.3)
(d.j..c) c) (50,5, 0.4.)
(d.i. = (100, 0.5))
1
0.8
0.8
0.8
Power
Power
Power
0.6
0.6
0.6
-emm
0.4
xMMD
0.4
0.4
predicted
0.2
0.2
0.2
100
200
300
200
300
100
300
Sample- Size (n+m)
Sample- Size (n+m)
Sample- Size (u+m)
Figure 4: Curves showing the variation in power versus sample-size for the xMMD test and the kerDel-MMD permutation test. X are drawn from N Iu) ii.d. and is drawn from (a..j. Ia) where Ge,j is obtained by perturbing the first S d coordinates of O by c, the kernel used is the Gaussian kernel with scale parameter chosen via the median heuristic. The dashed curve shows the predicted power of the kernel-MMD) permutation test using the heuristic defined in
(d, c. (10,0.15,3 0.15.5)
(d, (,) (100, 0.15, 10)
(d, (500, 0.15, 50)
True Positive Rate
0.5
MMD
0.5
0.5
B-MMD (2)
B-MMD (x
L-MDD)
0
0
0.5
0
0.5
0
0.5
False Positive Rate
False Positive Rate
False Positive Rate
Figure 5: ROC curves highlighting the trade-off between type-I and type-ll errors achieved by the MMD, cross-MMD, batch-MMD with batch sizes 1/2 and 1/3, and linear-MMD statistics. In all the figures,
m 200.
this key result, we introduced permutation-free (and hence computationally efficient) MMD test the two-sample problem. Experiments indicate that the power achieved by our test is within /2-factor of the power the kernel-MMD permutation test (that requires recomputing the statistic hundreds of times). In other words, our results achieve the following favorable tradeoff:: we get significant reduction in computation at the price of small reduction in power.
Sejdinovic et al. (2013) establish in some generality that distance-based two-sample tests (like the energy distance (Székely and Rizzo 2013)) can be viewed kernel-MMD tests with particular choice of kernel k. Hence our results are broadly applicable to distance-based statistics as well. Since two-sample testing and independence testing can be reduced each other, it is interesting direction for future work to see if the ideas developed in our paper can be used for designing permutation free versions of kernel-based independence tests like HSIC (Gretton et al. 2007) or distance covariance (Székely and Rizzo 2009 Lyons 2013). Our techniques seem to rely on the specific structure of two-sample U-statistics of degree Extending these to more general U-statistics of higher degrees is another important question for future work. A final question is to figure out whether it is possible to achieve minimax optimal power using a sub-quadratic time test statistic. One potential approach would be to work with kernel approximated by random Fourier features (Rahimi) and Recht 2007: Zhao and Meng 2015). Depending on the number of random features, our test statistic can be computed in sub-quadratic time and it would be interesting to see whether the resulting test can still be minimax optimal power. We leave this important question for future work.
10

---

References
Z. Bai and H. Saranadasa. Effect of high dimension: by an example of a two sample problem. Statistica Sinica, pages 311-329, 1996.
V. Bentkus and F. Götze. The Berry- Esseen bound for Student's statistic. The Annals of Probability,
24( 24(1):491-503, 1996.
K. P. Chwialkowski, A. Ramdas, D. Sejdinovic, and A. Gretton, Fast two-sample testing with analytic representations of probability measures. Advances in Neural Information Processing Systems, 28, 2015.
R. D' Agostino and E. S. Pearson. Tests for departure from normality. empirical results for the distributions of by and vb,, Biometrika, 60(3):613 622, 1973.
R. Durrett. Probability: theory and examples, volume 49. Cambridge University Press, 2019.
J. H. Friedman and L. C. Rafsky. Multivariate generalizations of the wald-wolfowitz and smirnov two-sample tests. The Annals of Statistics, pages 697-717, 1979.
A. Gretton, K. Borgwardt, M. Rasch, B. Schölkopf, and A. Smola. A kernel method for the two- sample-problem. Advances in Neural Information Processing Systems, 19, 2006.
A. Gretton, K. Fukumizu, C. Teo, L. Song, B. Schölkopf, and A. Smola. A kernel statistical test of independence. Advances in Neural Information Processing Systems, 20, 2007.
A. Gretton, K. Fukumizu, Z. Harchaoui, and B. K. Sriperumbudur. A fast, consistent kernel two- sample test. Advances in Neural Information Processing Systems, 22, 2009.
A. Gretton, K. M. Borgwardt, M. J. Rasch, B. Schölkopf, and A. Smola. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012a.
A. Gretton, D. Sejdinovic, H. Strathmann, S. Balakrishnan, M. Pontil, K. Fukumizu, and B. K. Sriperumbudur. Optimal kernel choice for large-scale two-sample tests. Advances in Neural Information Processing Systems, 25, 2012b.
N. Henze and M. D. Penrose. On the multivariate runs test. Annals of statistics, pages 290-298, 1999.
W. Jitkrittum, Z. Szabó, K. Chwialkowski, and A. Gretton. Interpretable distribution features with maximum testing power. Advances in Neural Information Processing Systems, 29, 2016.
I. Kim. Comparing a large number of multivariate distributions. Bernoulli, 27(1):419-441 2021.
I. Kim and A. Ramdas. Dimension-agnostic inference using cross U-statistics. arXiv preprint arXiv:2011.05063 2020.
Lee. U-staristics: Theory and Practice. Citeseer, 1990.
E. L. Lehmann and J. Romano. Testing Statistical Hypotheses. Springer Science Business Media, 2006.
T. Li and M. Yuan. On the optimality of Gaussian kernel based nonparametric tests against smooth alternatives. arXiv preprint 1exxiv:/99..0 03302, 2019.
R. Lyons. Distance covariance in metric spaces. The Annals of Probability, 41(5):3284-300, 2013.
A. Rahimi and B. Recht. Random Features for Large-Scale Kernel Machines. Advances Neural Information Processing systems, 20, 2007.
A. Ramdas, S. J. Reddi, B. Poczos, A. Singh, and I.. Wasserman. Adaptivity and computation- statisties tradeoffs for kernel and distance based high dimensional two sample testing. arXiv preprint /008::5508.006
2015.
S. Reddi, A. Ramdas, B. Póczos, A. Singh, and L. Wasserman. On the high dimensional power of linear-time two sample test under mean-shift alternatives. In Artificial Intelligence and Statistics, pages 772-780. PMLR, 2015.

---

D. Sejdinovic, B. Sriperumbudur, A. Gretton, and K. Fukumizu. Equivalence of distance- and RKHS-basee statistics hypothesis testing. The Annals of Statistics, 41(5):2263-2299 2013.
B. K. Sriperumbudur, K. Fukumizu, and R. Lanckriet. Universality, Characteristic Kernels and RKHS Embedding of Measures. Journal of Machine Learning Research, 12(7), 2011.
G. J. Székely and M. L. Rizzo. Brownian distance covariance. The Annals of Applied Statistics, 3(4): 1236-122 1265, 2009.
G. Székely and M. L. Rizzo. Energy statistics: A class statistics based on distances. Journal of Statistical Planning and Inference, (4398):2249-127) 2013.
A. Wald and J. Wolfowitz. On test whether two samples are from the same population. The Annals of Mathematical Statistics, 11(2):177-162, 1940.
W. Zaremba, A. Gretton, and M. Blaschko. B-test: low variance kernel two-sample test. Advances in Neural Information Processing Systems, 2013.
J. Zhao and D. Meng. FastMMD: Ensemble of circular discrepancy for efficient two-sample test. Neural Computation, 176,,,31131, 2015.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] In cases where computation cost
not an issue, the power achieved by our test will be slightly smaller (approximately
by a factor of /2) as compared to the kernel-MMD permutation test.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] All the proof's are in the appendix.
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] We will include the code with the supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We include all the details of the experiments in the appendix.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] The experiments were run on workstation, whose specifications are provided in AAppendix E.
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're ror're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
12

---

5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "v0_mXHHGCBG", "reviewer": "Reviewer_794f", "summary": "This proposes a variant of the kernel-MMD statistic, called cross-MMD, based on the ideas of sample splitting and studentization, and showed that it has a standard normal limiting null distribution. Using this key result, they introduced a permutation-free (and hence computationally efficient) MMD test with 100 times faster and a sacrifice in performance that is better than the factor sq(2) (expected due to splitting). ", "questions": "Considering the current presentation of the results It is not clear if always sqrt(2) factor is always guaranteed. Please correct me if I misunderstood. For example In cases of Figure 3 for samplesizes of 50 to 100 is it true? Please try to discuss if there are cases where the test's performance is not sufficient (therefore the test is not recommended).", "limitations": "Authors are discussing sufficiently both limitations and perspectives. The weaknesses that I mentioned could also become part of this discussion.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n-Well written paper. Nice and simple theory. No \"wordy\" sentences, No blurry experiments or non-understandable mathematical expressions. No overselling. Well done. \n\nWeaknesses\n- Focus on performance and time consumption but (MMD-related weakness) no information concerning interpretability in terms of Variable influence and how mmd can be used as an alternative to traditional approaches (multiple testing etc).\n- The splitting scheme is always problematic in cases with low sample sizes (and the time gain is negligible) and studentization more risky. \n- I see a contribution only in cases where extremely big datasets occur. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "nn2blWK3Dq", "reviewer": "Reviewer_ja6F", "summary": "This paper proposes a novel two-sample test based on the MMD test. This test has a closed-form of null distribution (a normal distribution), and the intuition for the resulting null distribution is that the proposed test can be thought of as performing a student's t-test.  ", "questions": "Please see above.", "limitations": "Please see above.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: It is creative to split the dataset into two pairs to studentize the original MMD test, therefore resulting to a traceable null distribution.  \nWeakness: Comparison with other permutation two-sample test which also has closed-form of the null distribution is missing. One example is the Friedman-Rafsky (FR) test[Friedman, 1979]. In fact, both the FR test and the proposed test have the same null distribution, I think the FR test would be a good baseline would be good to compare with. Besides, the price of deriving such an ''exact'' null distribution test is to decrease the power. Is that possible to have a sample complexity analysis regarding the Type II error of the proposed MMD variant compared with the original MMD test? \nFriedman, Jerome H., and Lawrence C. Rafsky. \"Multivariate generalizations of the Wald-Wolfowitz and Smirnov two-sample tests.\" The Annals of Statistics (1979): 697-717.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-FbWtaC3bR", "reviewer": "Reviewer_ocYj", "summary": "The paper proposes and investigates an alternative estimator for maximum mean  discrepancy (MMD), a popular kernel-based two sample test. The benefit of the estimator is that it has a standard normal distribution under the null hypothesis of equal distributions. Thus, there is no need to perform costly permutation tests in order to get a p-value from the surrogate null distribution. The theoretical results go beyond this to include cases where the kernel is sample size dependent, as well as showing a mini-max optimality against local alternative hypotheses where the distributions are close in terms of a probability metric. ", "questions": "Could cross-MMD be used to choose from amongst different kernel sizes and then use MMD for the test? \n\n\nSuggestion: Equation (9) it could be made clear to the reader what $z_\\alpha$ is.", "limitations": "Requiring larger sample sizes for computational ease may not be warranted in situations where data collection is costly. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe paper is an original and important contribution that is well-written, having a comprehensive introduction and discussion of related work, goes into technical details with what appears to be rigorous theory. The paper is rather complete with key implications for future work on other distance or kernel based tests including tests of dependence. \n\nWeaknesses: \nThe application and implication to some real scenarios is not completely discussed. In real cases where the data is collected (or will be collected) the sample sizes are fixed (or wouldn't want to be larger). In these cases, is the computational savings going to be meaningful? ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-EFNxczMd28", "reviewer": "Reviewer_qgsP", "summary": "The paper proposes a variant of the quadratic time MMD test, whose null distribution is a standard normal, and whose statistic is computed based on splitting the available samples (e.g. in half).\nThis, while reducing the test-power, allows for easy test threshold estimation, and in particular avoid the permutation-based approach of the original quadratic time MMD test.\nThe authors formally derive this null distribution, and proove a number of properties of the resulting test, including consistency against fixed local alternatives, and finally a minimax rate-optimal power against local alternatives (Gaussian kernel only).\nA number of experiments show that the theory translates into practice.\n\n\nEDIT after rebuttal. The authors have provided an excellent and careful reply to all of my concerns. I have increased my score and think this is a great paper which should be accepted.", "questions": "See my points on the computational claims above.\nI strongly suggest to add the linear time test baseline mentioned above.", "limitations": " ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "A great paper that tackles a worthwhile problem in a creative manner, and is thoroughly executed, in particular theory wise.\nI am not sure about the practical impact of the paper though, because hundredfold computational improvements stated by the authors are somewhat academic, and do not hold true against careful implementations. In practice, I suspect the different to be much smaller, which then raises the question whether the loss in test power can really be justified.\nThe paper in my opinion also misses an important baseline test.\n\n\nOriginality:\nThe idea of building an MMD test with a normal null distribution has been around since the original MMD test has been first described.\nBack then, however, the test statistic was linear time which meant the test wasn't as powerful.\nIt is great that the authors found a way to achieve a standard normal null using a quadratic time test, and I consider this very original work.\n\nQuality: \nThe paper is executed on a very high technical level, all claims have substantial proofs.\nI in particular appreciate the generalization of Theorem 6 to the case where the kernel is allowed to change. Great work.\nThe minimax optimality is great too, though only established for Gaussian kernels (this should be stated in the abstract, where it appears that this is a general results)\n\nExperimentally, I think one baseline that is clearly missing is the linear time test with learned features, described in https://arxiv.org/pdf/1605.06796.pdf. The paper reports experiments where a linear time test performs *better* than the standard quadratic time MMD. So this is highly relevant for this paper as well. In fact, I think the paper should not be published without these baselines.\n\nOn a side note, the authors do not experimentally demonstrate that their test has a well calibrated type 1 error for a given threshold, which I think would be a nice addition.\n\nAnother side note, the authors could run a standard goodness of fit test on the results in Fig 2, to test for normality.\n\nClarity: \nClearly written throughout.\n\nSignificance: \nFrom a theoretical and methodological perspective, this work is significant, as it improves the ever growing set of tools around MMD tests.\n\nHowever, I am not so sure about practical impact, and this is my main critique of the paper.\n1. The authors argue that the permutation computations requires for the original test are prohibitive. In practice however, these are trivially parallelizable and not time critical. The idea behind the quadratic time MMD has always been \"the best possible test for a given set of samples\". Making that faster is useful, but not at the cost of sacrificing power, as in practice maximum power is usually what is wanted.\n2. A more severe point is that the authors argue that the permutation test is in fact hundreds of times slower than their proposed test. This is only true asymptotically. In practice, permutation tests can be implemented in an extremely efficient manner by precomputing the kernel matrix, and then using memory sequential read operations to compute the permutations. As also mentioned above, this can be easily parallelized. E.g. https://arxiv.org/abs/1611.04488 reported that a naive python implementation (using precomputed kernel matrices) can be made >10x faster using these simple strategies, and before parallelization, plus another 5-10x using multithreaded implementations. In summary, with a little implementation effort, the computational gain (in wallclock time, with efficient implementations and parallel hardware), will surely not be hundredfold.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept