MMD-Fuse: Learning and Combining Kernels for Two-Sample Testing Without Data Splitting
Authors: Felix Biggs
Antonin Schrab
Arthur Gretton
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Testing
MMD
Kernel Methods
Two-sample testing
TL;DR: Adaptive MMD two-sample tests without data splitting, by fusing kernels.

Abstract: We propose novel statistics which maximise the power  of a two-sample test based on the Maximum Mean Discrepancy (MMD), by
adapting over the set of kernels used in defining it.
For finite sets, this reduces to combining (normalised) MMD values under each of these kernels via a weighted soft maximum.
Exponential concentration bounds are proved for our proposed statistics under the null and alternative.
We further show how these kernels can be chosen in a data-dependent but permutation-independent way, in a well-calibrated test, avoiding data splitting.
This technique applies more broadly to general permutation-based MMD testing, and includes the use of deep kernels with features learnt using unsupervised models such as auto-encoders.
We highlight the applicability of our MMD-Fuse tests on both synthetic low-dimensional and real-world high-dimensional data, and compare its performance in terms of power against current state-of-the-art kernel tests.

MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splitting
Felix Biggs"
Antonin Schrab'
Centre for Artificial Intelligence
Centre for Artificial Intelligence Gatsby Computational Neuroscience Unit University College London & Inria London a. wws.ccabuucl...... ac. uk
Department of Computer Science
University College London & Inria London contact&fe.l contact@@elizbiggs.co
Arthur Gretton
Gatsby Computational Neuroscience Unit
University College London
arthur wwwttoorgeamal.ccooomommmm com
Abstract
We propose novel statistics which maximise the power of a two-sample test based the Maximum Mean Discrepancy (MMD), by adapting over the of kernels used in defining it. For finite sets, this reduces to combining (normalised) MMD values under each of these kernels via weighted soft maximum. Exponential concentration bounds are proved for our proposed statisties under the null and alternative. We further show how these kernels can be chosen in data- data-dependent but permutation -inennendddddnnntt way, in well-calibrated test, avoiding data splitting. This technique applies more broadly to general permutation based MMD testing, and includes the use of deep kernels with features learnt using unsupervised models such as auto-encoders.
highlight the applicability of our MMD-FUSE test on both synthetic low-dimensional and real-world dimh-dime data, and compare its performance in terms of power against current saac-of-the-as kernel tests.
Introduction
The fundamental problem of non-parametric two-sample testing consists in detecting the difference between any two distributions having access only to samples from these. Kernel-based tests relying on the Maximum Mean Discrepancy (MMD; Gretton et al., 2012a) distributions are well-suited for this framework they can identify complex non-linear features in the data, and benefit from both strong theoretical guarantees and ease of implementation. This explains their popularity among practitioners and justifies their wide use for real-world applications.
measure of distance
However, the performance of these tests is crucially impacted by the choice of kernel. This is commonly tackled by either: choosing the kernel by some weakly data-dependent heuristic (Gretton al., 2012a); splitting off hold-out set of data for kernel selection, with the other half used for the actual test (Gretton et al., 2012 2b; Sutherland et al., 2017). This latter method includes training feature extractors such deep kernels the first selection half. Both of these methods incur a significant loss in test power, since heuristics may lead to poor kernel choices, and data splitting reduces the number of data points for the actual test.
Our contribution is to present MMD-based tests which can strongly adapt to the data without data splitting. This comes in two parallel parts: firstly we show how the kernel can be chosen in
"Equal contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

unsupervised fashion using the entire dataset, and secondly we show how multiple such kernels can be adaptively weighted in a single test statistic, optimising test power.
Data Splitting. The data splitting approach selects test parameters on a held-out half of the dataset, and applies the test the other half. Commonly, this involves optimising a kernel on held-out data in supervised fashion to distinguish which sample originated from which distribution, either by learning deep kernel directly (Sutherland et al., 2017; Liu et al., 2020, 2021), or indirectly through the associated witness function (Kübler et al., 2022a.b). Jitkrittum et al. (2016) propose tests which select witness function features (in either spatial or frequency space) on the held-out data, running the analytic representation test of Chwialkowski et al. (2015) on the remaining data.
Our first contribution is to show that it is possible to learn feature extractor for our test (e.g.. a deep kernel) on the entirety of the data in an unsupervised manner while retaining the desired non-asymptotic test level. Specifically, any method can he used that is ignorant of which distribution generated which samples. We can thus leverage many feature extraction methods, from auto-encoders (Hinton and Salakhutdinov, 2006) to recent powerful developments in self-supervised learning (He et al., 2020; Chen et al., 2,e0a, Chen and He, 2021; Grill et al., 2020; Caron et al., 2020; Zbontar al., 2021; Li et al., 2021). Remarkably, our method applies to any permutation-basee two-sample test, even non-kernel tests, provided the parameters are chosen in this unsupervised fashion. This includes a very wide array of MMD-based tests, and finally provides a formal justification for the commonly-used median heuristic (Gretton et al., 2012b; Ramdas et al., 2015; Reddi et al., 2015).
Adaptive Kernel Selection. A newer approach originating in Schrab al. (2023) performs adaptive kernel selection through multiple testing. Aggregating several MMD-based tests with different kernlss, each on the whole dataset, results in an overall adaptive test with optimal power guarantees in terms of minimax separation rate over Sobolev balls. Variants of this kernel adaptivity through aggregation have been proposed with linear-time estimators (Schrab et al., 2022b), spectral regularisation (Hagrass et al., 2022), kernel thinning compression DDomingo-Enricl et al., 2023), and in the asymptotic regime (Chatterjee and Bhattacharya, 2023). Another adaptive approach using the entire dataset for both kernel selection and testing is given by Kübler et al. (2020); this leverages the Post Selection Inference framework, but the resulting test suffers from low power in practice.
While our unsupervised feature extraction method is an extremely general technique and potentially powerful, particularly for high-dimensional structured data like images, it is not always sufficient for data where such feature extraction is difficult. This motivates our second contribution, a method for combining whole-dataset MMD estimates under multiple different kernels into single test statistics, for which we prove exponential concentration. Kernel parameters such as bandwidth can then be chosen in non-heuristic manner optimise power, even on data with less structure and varying length scales. Using a single statistic also ensures that single test can be used, instead of the multiple testing approach outlined above, reducing computational expense.
MMD-FUSE. By combining these contributions we construct two closely related MMD-FUSE tests. Each chooses a set of kemnels based on the whole dataset in unsupervised fashion, and then adaptively weights and fuses this (potentially infinite) set of kernels through our new statistics; both parts of this procedure we use in practice, the weighting procedure is done in closed form via a weighted soft maximum. We show these new tests to be well-calibrated and give sufficient power conditions which achieve the minimax optimal rate in terms of MMD. In empirical comparisons, our test compares favourably to the state-of-ther -hrt
done using the entire dataset without splitting. On the finite sets of kernels
art aggregated tests in terms of power and computational cost.
Outline and Summary of Contributions. In Section 2 we outline our setting, crucial results under- lying our work, and alternative existing approaches. Section 3 covers the construction of permutation tests and discusses how we can choose the parameters for any such test in any unsupervised fashion including with deep kernels and by those methods mentioned above. Section 4 introduces and moti- vates our two proposed tests. Section 5 discusses sufficient conditions for test power (at a minimax optimal rate in MMD), and the exponential concentration of our statistics. Finally, show that our test compares favourably with a wide variety of competitors in Section 6 and discuss in Section 7.
2

---

2 Background
Two-Sample Testing. The two-sample testing problem is to determine whether two distributions p and q are equal or not. In order to test this hypothesis, we are given access to two samples, X = iid
iid (XI...., .n) ~ p and Y == (Yi...... Ym) ~ as tuples of data points with sizes n and m. We write the combined (ordered) sample as Z == (Zi..... Zn+m) (x, Y) = (X1..... Xn, I....., mm).
We define the null hypothesis Hg as p = q and the alternative hypothesis H1 as p & q, usually with a requirement (p. q) for a distance D (such as the MMD) and some > 0. A hypothesis test A a {0, 1-valued function
Z, which rejects the null hypothesis if ( Z = 1 and fails to reject it otherwise. It will usually be formulated to control the probability of a type error at some level E (0, 1), so that TP pxp (Z( = 1) S a; while simultaneously minimising the probability of type II error, IP px A(Z) = 0). In the above we have used the notation IP pxx and P. "xx to indicate that the sample is either drawn from the null. p = or the alternative * q. Similar notation will be used for expectations and variances. When bound 3 E (0, 1) on the probability of a type II error is given (which may depend on the precise formulation of the alternative), we say the test has power 1 - B.
Maximum Mean Discrepancy. The Maximum Mean Discrepancy (MMD) is kernel-based measure of distance between two distributions p and 9. which is often used for two-sample testing. The MMD quantifies the dissimilarity between these distributions by comparing their mean embeddings in reproducing kernel Hilbert space (RKHS; Aronszajn, 1950) with kernel .).,)). Formally, if Hs is the RKHS associated with kernel function k; the MMD between distributions and is the integral probability metric defined by:
sup MMD (p, SEH I S
-Bx_
The minimum variance unbiased estimate of MMD is given by the sum of two U-statistics and a sample average as:²
MMD = n(n - 1) (t,7")ell2z
Σ X(x, m(m 1), (is')
EAC,, -
((,,
where we introduced the notation in]2 = ((t,t) E [n]3 + i'} for the set of all pairs of distinet indices in [n] = f1,...,, n). Tests based on the MMD usually reject the null when MMD3 exceeds some critical threshold, with the resulting power being greatly affected by the kernel choice. For characteristic kernel functions (Sriperumbudur et al., 201 1), it can be shown that MMD, (p. 7) O if and only if p- q. leading consistency results. However, on finite sample sizes, convergence rates of MMD estimates typically have strong dependence on the data dimension, so there are settings in which kernels ignoring redundant or unimportant features (i.e. non-characteristie kernels) will give higher test power in practice than characteristic kernels (which can over wer-weiigt redundant features).
Distributions Over Kernels. In our test statistic, will consider the where the kernel & e IC is drawn from a distribution o E .M (IC) (with the latter notation denoting a probability measure; c.f. Benton et al., 2019 in the Gaussian Process literature). This distribution will be adaptively chosen based on the data subject to a regularisation term based on a "prior" π E .M (IC) and defined through the Kullback-Lieble otherwise. When constructing these statistics the Donsker- Donsker-Varadhan equality (Donsker and Varadhan, 1975), holding for any measurable g K. + R. will be useful:
divergence: (plp = E log dd/dd)) for p < and (L(pl] == co
sup Ep .g] (L(pp| T) log E, [exp PEM (A)
This be further related to the notion of soft maxima. If is uniform distribution finite IC with [C] = r. then (l[p & log(r). Setting g = tf for some t > 0, Equation (1) relaxes to
max f(k) log(r) < log Σ (T(()) k
S max f(k), k
"Kim et al. (2022) note that MMD? can equivalently be written as a two-sample U-statistic with kernel he(a, d': w.)') = x') k(y. s') k(x, v') kexx, y), which is useful for analysis.
3

---

which approximates the maximum with error controlled by t. Our approach in considering these soft maxima is reminiscent of the PAC-Bayesian (McAllester, 1998; Seeger et al., 2001; Maurer, 2004; Catoni, 2007; see Guedj, 2019 or Alquier, 2021 for survey) approach to capacity control and generalisation. This framework has raised particular attention recently as it has been used to provide the only non-vacuous generalisation bounds for deep neural networks (Dziugaite and Roy, 2017, 2018; Dziugaite et al., 2021; Zhou et al., 2019; Perez-Ortiz et al., 2021; Biggs and Guedj, 2021, 2022a); it has also been fruitfully applied to other varied problems from ensemble methods (Lacasse et al., 2006, 2010; Masegosa et al., 2020; Wu et al., 2021; Zantedeschi et al., 2021; Biggs and Guedj, 2022b; Biggs et al., 2022) to online learning (Haddouche and Guedj, 2022). Our proofs draw on techniques in that literature for U-Statistics (Lever et al., 2013) and martingales (Seldin et al., 2012; Biggs and Guedj, 2023; Haddouche and Guedj, 2023; Chugg et al., 2023). By considering these soft maxima, we gain a major advantage over the standard approaches, as we can obtain concentration and power results for our statistics without incurring Bonferroni-type multiple testing penalties.
Tests. The tests we discuss in this paper use permutations of the data Z to approximate the null distribution. We begin our discussion in fairly general form to include other close settings such as independence testing (Albert et al., 2022; Rindt et al., 2021) or wild bootstrap-based two- sample tests (Fromont et al., 2012, 2013; Chwialkowski et al., 2014; Schrab et al., 2023). Let G be a group of transformations on Z; in our setting g = Gn+m. denoting the permutation (or GN [N] - [N]. We write gZ symmetric) group of [N] by GN and its elements by (a(t))......((tta (n(++m) for the group elements for the action of g E G on Z: e.g. defining o Z = (ZotI)....,
Permutation
Ga+m. We will suppose Z is invariant under the action of G when the sample is drawn from the null distribution, i.e. if the null is true than g = Z (by which we notate equality of distribution) for all g E g. This is clearly the case for G = G n+ in two-sample testing, since under the null iid Z = 17, ... ? p with 9, while under the alternative, the permuted sample o Z for randomised a Uniform(Sn41) simulates the null distribution.
We can use permutations to construct an approximate cumulative distribution function (CDF) of our test statistic under the null, and choose an appropriate quantile of this CDF our test threshold, which must be exceeded under the null with probability less that level a. For this we introduce a quantile operator (analogous to the max and min operators) for finite set {f(a)= E R: a E A}:
1
quantile f(a) = inf r T 9.aEA
E1f((a) ((f(a)s)12))) 5M22 LAI
(3)
aEA
Various different results can be used to choose the threshold giving a correct level; we will here highlight very general and easy-to-use theorem for constructing permutation tests, and in Section 3 will discuss previously unconsidered implications for using unsupervised feature extraction methods as part of our tests. Although this result is not new, we believe that its usefulness has been under- appreciated in the kernel testing community, and can be more conveniently applied than Romano and Wolf (2005, Lemma 1), which requires exchangeablity and is commonly used, e.g. in Albert et al. (2022, Proposition 1) and Schrab et al. (2023, Proposition 1).
Theorem 1 (Hemerik and Goeman, 2018, Theorem 2.). Let G be vector of elements from G. G = (g1, .e.....9++11 with 9B-1 = id (the identity permutation) for any B 2 1. The elements 91..... 9B are drawn uniformly from g either i.i.d. or without replacement (which includes the possibility G = G). If is a statistic of Z and Z =a gZ for all g E G under the null then
P Ppxp. (7(2)
-uantillan(ge (92)) Sa. 1-o.gEG
In other words, if we compare (Z) with the empirical quantile of 7( as test threshold, the type error rate no more than a.3 The potentially complex task of constructing a permutation test reduces to the trivial task of choosing the statistic r(Z). This result is also true for randomised permutations of any number B& Z 1 without approximation, so an exact and computationally efficient test can be straightforwardly constructed this way.
We finally mention the related approach of the MMD Aggregated test (MMDAgg: Schrab al., 2023), which combines multiple MMD- based permutation tests with different kernels, and rejects if
'This test is near-exact. Specifically, if the statistic realisations are distinct (r * r(g' Z) for + g') as is common for continuous data, the level is exactly [(B + 1)) 1).
4

---

any of these reject, using distinct quantiles for each kernel. To ensure the overall aggregated test is well-calibrated, these quantiles must be adjusted using a second level of permutations. This incurs additional computational cost, a pitfall avoided by our fused single statistic.
Faster Sub-Optimal Tests. While the main focus of this paper revolves around the kernel selection problem for optimal, quadratic MMD testing, we also highlight the existence of a rich literature on efficient kernel tests which run in linear (or near-linear) time. These speed improvements are achieved using various tools such as: incomplete U-statistics (Gretton et al., 2012b; 12; Yamada et al., 2019; Lim et al., 2020; Kübler et al., 2020; Schrab al., 2022b), block U-statistics (Zaremba et al., 2013; Deka and Sutherland, 2022), eigenspectrum approximations (Gretton et al., 2009), Nyström approximations (Cherfaoui al., 2022), random Fourier features (Zhao and Meng, 2015), analytic representations (Chwialkowski et al., 2015; Jitkrittum et al., 2016), deep linear kernels (Kirchler et al., 2020), kernel thinning (Dwivedi and Mackey, 2021; Domingo-Ennn Enrihh et al., 2023), etc.
The efficiency of these tests usually entail weaker theoretical power guarantees compared to their quadratic-time counterparts, which are minimax optimal* (Kim et al., 2022; Li and Yuan, 2019; Fromont et al., 2013; Schrab et al., 2023; Chatterjee and Bhattacharya, 2023). These optimal quadratic tests are either permutation-based non-asymptotic tests (Kim et al., 2022; Schrab et al., 2023) or studentised asymptotic tests (Kim and Ramdas, 2023; Shekhar et al., 2022; Li and Yuan, 2019; Gao and Shao, 2022: Florian et al., 2023). We emphasise that the parameters of any of these permutation- based two-sample tests can be chosen in the unsupervised way we outline in Section 3. We choose to focus in this work on optimal quadratic-tima results, but note that our general approach could be extended to sub-optimal faster tests as well.
3 Learning Statistics for Permutation Tests
Here we discuss how we can improve permutation-basele tests by learning parameters for them in unsupervised manner. The reason that highlighted Theorem in the previous section is that it holds for any T. For example, we could use the MMD with a kernel chosen based on the data, 7 TZ)) MMD =x(2) (Z): however, for each permutation
would need to re-compute Z). so the kernel being used would be different for each permutation. This has two major disadvantages: firstly, it might be computationally expensive to re-compute k for each permutation, especially for deep kernel.. Secondly, the scale of the resulting MMD could be dramatically different for each permutation, so the empirical quantile might not lead to a powerful test. This second problem is related to the problem of combining multiple different MMD values into a single test which our MMD-FUSE statistics are designed to combat (Section 4; c.f. also MMDAgg, Schrab et al., 2023).
Z = MMD
Our Proposal. In two-sample testing we propose to use a statistic Ta parameterised by some 0, where 0 is fixed for all permutations, but depends on the data in an unsupervised or permutation-invarian way, Specifically, we allow such a parameter to depend on (Z) = =1 1Z Zn+m); J. the unordered combined sample. Since our tests will not depend on the internal ordering of X and Y (which are assumed i.i.d. under both hypotheses), the only additional information contained in Z over (Z) is the label assigning Z, to its initial sample. This is justified since (Z) (a for all E Gn+m- so setting 7 ( ) = Toç ()) (Z) gives a fixed and statistic for all permutations to use in Theorem 1. The information in (Z) can be used to fine-tune test parameters for any test fitting this setup. This solves
both the computation and scaling issues mentioned above.
The above provides a first formal justification for the use of the median heuristic in Gretton et al. (2012a), since it is a cormuttaiooninvartti bilities are available even when restricting ourselves to these permutation-fis example, we can use any unsupervised or self- to use as the input to an MMD-based test statistic, while paying no cost in terms of calibration and needing to train such methods only once. Given the wide variety of methods dedicated to feature extraction and dimensionality reduction, this opens up a huge range of possibilities for the design of new and principled two-sample tests. The simplicity and generality of our proposal might lead one to
function of the data. However, far richer set of possi-
functions of Z. For learning method to learn representations
"With the exception the near-lineat test of Domingo-Entn et al. (2023) which achieves the same MMD separation rate as the quadratic test but under stronger assumptions on the data distributions. A possibility envisaged by e.g. Liu et al. (2020) and dismissed due the computational infeasability.
5

---

expect that this idea has been used before, but it has not to our best knowledge, underlined by the fact that the median heuristic has been widely used without such justification when one follows from this method. This potentially powerful and widely-applicable possibility represents one of our most practical contributions.
4 MMD-FUSE: Fusing U-Statistics by Exponentiation
Say we have computed several MMD values MMD3 under different kernels k E K. How might we combine these? One possibility is to perform multiple testing as the case of MMDAgg. An even simpler approach would simply take the maximum of those values max; MMD3 since Theorem 1 shows that this will not prevent us from controlling the level of our test by a note though that for each permutation we would take this maximum separately. Indeed, Cárcamo et al. (2022) show that for certain kernel choices the supremum of the MMD values with respect to the bandwidth is a valid integral probability metric (Mäller, 1997). There are two main problems with this approach: capacity control issue and normalisation issue.
Firstly, if the class over which we are maximising is sufficiently rich (for example a complex neural network), then the maximum may be able to effectively memorise the entire sample for each possible permutation, saturating the statistic for every permutation and limiting test power. Any convergence results would need to hold simultaneously for every le in K., and so power results suffer: for finite [K] we would incur sub-optimal Bonferroni correction (see Section 5); while for infinite classes, results would need involve capacity control quantities like Rademacher complexity. Further, only information from single maximising "base" kernel can be considered at a time.
Therefore, in both statistics, we prefer "soft" maximum, which considers information from every kernel simultancously and when more than one of the kernels is well-suited (Section 5) it therefore avoids the Bonferroni correction arising from uniform bounds. From Equation (1), our approach is equivalent to using KL complexity penalty, and is strongly reminiscent of PAC-Bayesian (Section capacity control. We note that other soft maxima could be considered, but our choice makes obtaining exponential concentration inequalities relatively easy (Appendix C), and the dual formulation (Equation (2)) allows us derive power results terms of MMD directly.
The second issue is that the MMD estimates might have different scales or variances per kernel which need to be accounted for. In order to be able meaningfully compare MMD values between each other, these need to be normalised somehow before taking a maximum. We use the common approach of dividing through by variance-like term (as in "studentised" tests, see Section 2). The specific normaliser is permutation invariant and gives our statistic tight sub-Gaussian null concentration (for well-chosen regularisation parameter X; see Appendix C).
Based on the above we introduce the FUSE-1 statistic which uses a log-sum-ert soft maximum, and the FUSE-N which combines this with normalisation. Both statistics use "prior" distribution on K., denoted TT( (Z)), which is either fixed independently of the data, or is a function of the data which is invariant under permutation (as discussed in Section 3).
We define the un-normalised (subscript I for normaliser 1) and normalised (subscript N) test statistics with parameter X >> O, respectively,
Definition 1.
FUSE, (Z) = X log (ENx((2)) exp (AMMI)(XX) r))
MMTDR(X))
FUSEN (2) = X
log ENwn(( exp
(a(Z))
where (z) n[n-T] E(.s)E/4+m) k(2,, 2j)² is permutation invariant.
Although these statistics appear complex, we note that in the case where has finite support, their calculation reduces to log-sum-exp of MMD estimates normalised by Nr. This is even clearer when v also uniform on its support, as we consider experimentally; then Equation (2) shows that our statistics reduce to soft maxima, with À controlling the smoothness or "temperature".

---

From this, we define the FUSE-1 I test (with the FUSE-N test APUSEN defined analogously) as FUSEE (Z) = FUSE (
> quantile FUSE](0Z) 1-a,0ES
(4)
for sampled set S of permutations as described above. It compares the test statistic FUSE, with its quantiles under permutation, and rejects if the overall value exceeds a quantile controlled by a. Note that since & Z)) permutation invariant, it only needs to be calculated once per kernel in ÅFUSE, (and not separately for each permutation) as per Section 3. See Appendix A.5 for its time complexity.
Comparison with MMDAgg. MMDAgg a different way to think about combining multiple kernels and MMD values, but it relies on a framework based on multiple testing. This can be problematic in the case where the number of kernels considered is large, since as this number increases in the multiple testing approach MMDAgg, the level needs to be corrected differently, so its theretical power behaviour becomes unclear (though empirically MMDAgg retains its power in this setting). By contrast, our proposed FUSE methods avoid multiple testing as single statistic and quantile are used, avoiding such issues. The FUSE statistics are even defined the limit of an infinite number of kernels ponninuuous/uncounaabe
collection of kernels) by considering distributions on the space of kernels, which is not the case for MMDAgg Moreover, while the MMDAgg approach is only useful for hypothesis testing, having a quantity like FUSE combining multiple kernel-basee measures of distance with exponential concentration bounds could be of interest in a wider range of applications.
FUSE-1 and the Mean Kernel. Although the un-normalised test has worse performance in practice than our normalised test, the FUSE-1 statistic is interesting in its own right because of various theoretical properties, as we discuss below. Firstly, we introduce the mean kernel Kp(æ, y) = Ex, y) under a "posterior" E MM (XC), which indeed a reproducing kernel in its own right. In the finite case, this is simply a weighted sum of "base" kernels.
Note that the linearity of MMD3 and MMD in the kemnel k implies that Ex-p MM. MMD K, (p, q), and similarly for MMD3 with these terms appearing in our power results (Section 5).
Combining this linearity with the dual formulation of FUSE; via Equation (1) gives
MMD (X.Y) KL(p,
FUSE, (Z) = sup PEMM (AC)
A
This re-states FUSE; in terms of "posterior" p. and makes the interpretation of our statistic as KL-regularised kernel-learning method clear. In the finite case, our test simply optimises the weightings of the different kernels in a constrained way. We note that for certain infinite kernel sets and choices of prior it is be possible to express the mean kernel in closed form. This happens because, e.g. the expectation of a Gaussian kernel with respect to a Gamma prior over the bandwidth is simply (closed form) rational quadratic kernel. We discuss this point further in Appendix B.
5 Theoretical Power of MMD-FUSE
In this section we outline possible sufficient conditions for our tests to obtain power at least at given level a. The conditions will depend on fixed data-independent "prior" π E (KC and thus hold even without unsupervised parameter optimisation. They are stated as requirements for the existence of a "posterior" p E MM (K) with corresponding mean kernel K, as defined in Section 4. In the finite case, K, is simply a weighted sum of kernels, so these requirements are also satisfied under the same conditions for any single kernel, corresponding to the case where the posterior puts all its weight on a single kernel.
Technically, these results require that there is some constant k upper bounding all of the kernels, and that n and m are within a constant multiple (i.e. n < m < en for some e > 1, notated n m). They hold when using randomised permutations provided B > d2 log(3-1) for small constant c' > 0. Theorem 2 (FUSE-1 Power). Fix prior independently of the data. For the un-normalised test FUSE-/ with X x n/R and n. x m, there exists a universal constant C > O such that
3p MMM)((K) : MMD? K, (p.9)= > CR
n ( +og a
+
kT))
is sufficient for FUSE-1 to achieve power at least - 3 at level a.
7

---

A similar result is obtained for FUSE-N under an assumption that the normalising term is well behaved (see assumption Theorem 3). This requirement will be satisfied for kernels (including most common ones) that tend to zero only in the limit of the data being infinitely far apart.
Theorem 3 (FUSE-N Power). Fix prior a independently of the data such that for all k E supp(=)) the expectation ( < e/K is bounded for some < co. For the normalised test FUSE-N with x n = m, there exists a universal constant C > O such that
3p E M) MMD (1,9)
Ck
(1
1 32 + log a
kT.(p..))
n
is sufficient for FUSE-N to achieve power at least 1 - B at level a.
Discussion. The conditions in Theorems 2 and give the optimal MMD separation rate in n (Domingo-Enrinn et al., 2023, Proposition 2). These results also imply consistency if the prior assigns non-zero weight to characteristic kernels. 6 Applying these results to uniform priors supported on points, the KL penalty can be upper bounded as (L TT S log(r). Thus in the worst case, where only single kernel achieves large 3 (p. q). the price paid for adaptivity is only log(r). In many cases, most of the kernels will give large MMD q). The posterior will then mirror the prior, and this KL penalty will be even smaller. Thus very large numbers of kernels could be considered, and if all give large MMD values the power would not be greatly affected.
Additional Technical Results. Aside from the presentation of our new statistics and tests, we make number of technical contributions on the way to proving Theorems 2 and 3, as well as proving some additional results. In particular, we give exponential concentration bounds for our statistics under permutations and the null, which do not require bounded kernels. This refined analysis requires the construction of a coupled Rademacher chaos and concentration thereof. We obtain intermediate results using variances from the proof' of Theorems 2 and 3 that could be used in future work to obtain power guarantees under alternative assumptions such as Sobolev spaces (Schrab et al., 2023). Finally, we prove exponential concentration for FUSE, under the alternative and bounded kernels, requiring the proof of "PAC-Bayesian" bounded differences-type concentration inequality. See the appendix for more detailed overview.
6 Experiments
We compare the test power of MMD-FUSE-N (A (/n(n-1) against various MMD-hased kernel selective tests (see Section for details) using: the median heuristic (MMD-Median; Gretton et al., 2012a), data splitting (MMD-Split: Sutherland et al., 2017), analytic Mean Embeddings and Smooth Characteristic Functions (ME & SCF; Jitkrittum et al., 2016), the MMD Deep kernel (MMD-D; Liu et al., 2020), Automated Machine Learning (AutoML; Kübler et al., 2022b), kernel thinning to (Aggregate) Compress Then Test (CTT & ACTT; Domingo-Eniien -nnicch et al., 2023), and MMD Aggregated (Incomplete) tests (MMDAgg & MMDAgglne; Schrab et al., 2023, 2022b). Additional details and code link for experimental reproducibility are provided in Appendix A.
Distribution on Kernels. We choose our kernel prior distribution x as uniform over a collection of Gaussian, (x. y) exp(-Ila: y/13/ [2 and Laplace, k, (ar, y) = exp(-V2|( yll1/1), kernels with various bandwidths 7 > 0. These bandwidths are chosen as the uniform discretisation of the interval between half the 5% and twice the 95% quantiles (for robustness) of {|| - - : :2, 2' E Z). with r E 2), respectively. This choice is similar to that of Schrab et al. (2023, Section 5.2), who empirically show that ten points for the discretisation is sufficient (Schrab et al., 2023, Figure 6), which we verify in Appendix A.4. This set of distances is permutation-invariant, so Theorem 1 guarantees well-calibrated test even though the kernels are data-dependent.
Mixture of Gaussians. Our first experiments (Figure 1) consider multimodal distributions p and q. each a 2-dimensional mixture of four Gaussians with means =μ) with μ 20 and diagonal covariances. For p. the four components all have unit variances, while for we vary the standard deviation a of one of the Gaussians, appropriate kernel bandwidth to distinguish p from q would correspond to that separating Gaussians
1 corresponds to the null hypothesis p = q. Intuitively, an
"Under this condition (L <o with the restriction of to characteristic kernels. K. is characteristic MMDx, (p. 9)>0 < p of g, and condition lower bound tends to zero with cc.
8

---

Mixture d
Perturbed Uniform
Perturbod Uniform
Galaxy --3x64x6
1.0
Power
0.5
0.04
0.5
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.2
0.8
0.6
0.8
1.0
0.1
0.2
0.3
0.
Standard deviation
Pertarbation amplitude
Pertarbation
amplitude
Commuttio probability
1.0
Power
0.5
0.0-
1000
2000
1000
2000
3000
1000
2003
3000
500
1000
1500
2000
2500
Sample size
Sample size
Sample sine
Sample size
MMD-FUSE
MMDAgg MMDAggln
ACTT
MMD-D AntoML
MMD-MMdiaa MMD-Spür
CTT
SCF
Figure Power experiments. The four columns correspond different settings: Mixture of Gaussians in two dimensions (null a = 1), Perturbed Uniform for d E {1, (null a 0), and 0). In the first row, the deviations away from the null are varied for fixed sample size = 500. In the second row, the sample size varies while the deviations are fixed as 1.3, a = 0.2, a 0.4, and 0.15, for the four respective problems. The plots correspond to the rejections of the null averaged over 200 repetitions.
Galaxy MNIST in dimension 12288 (null
with standard deviations and a. This is significantly smaller than the median bandwidth which scales with the distance y between modes.
Perturbed Uniform. In Figure I, we report test power for detecting perturbations uniform distributions in one and two dimensions. We vary the amplitude of two perturbations from 0 (null) to a (maximum value for the density to remain non-ne non-neggtive). A similar benchmark was first pro- posed by Schrab et al. (2023, Section 5.5) and considered in several other works (Schrab et al., 2022b; Hagrass et al., 2022; Chatterjee and Bhattacharya, 2023). Different bandwidths are required to detect different amplitudes of the perturbations.
Table 1: Test power for detecting the difference between CIFAR-I0 and CIFAR-10.1 images with test level a = 0.05. The averaged numbers of rejections over 1000 repetitions reported.
Tests
Power
We examine performance real-world data in Figure 1, through galaxy images (Walmsley et al., 2022) in dimension d 3 64 64 12288 captured by a ground- based telescope. These consist of four classes: 'smooth and cigar-shaped', 'edge-on-disk' 'unbarred spiral', and 'smooth and round'. One distribution uniformly samples images from the first three categories. while the other does the same with probability 1 - and uniformly samples 'smooth and round' galaxy image with probability of corruption null hypothesis corresponds to the case 0.
Galaxy MNIST.
MMD-FUSE
0.937
MMDAgg
0.883
MMD-D
0.744
CTT
0.711
MMD-Median
0.678
ACTT
0.652
[0, 1]. The
МE
0.588
AutoML
0.544
CIFAR 10 10.1. The aim of this experiment is to detect the difference between images from the CIFAR-10 (Krizhevsky, 2009) and CIFAR-10.1 (Recht al., 2019) test sets. This is a challenging problem as CIFAR- 10.1 was specifically created to consist of new samples from the CIFAR-I0 distribution that it can be used as an alternative test set for models trained on CIFAR-10. 10. Samples from the two distributions are presented in Figure 6 in Appendix A.3 (Liu et al., 2020, Figure 5). This benchmark was proposed by Liu et al. (2020, Table 3) who introduced the deep MMD test MMD-D and the MMD-Split test (here referred to MMD-O to point out that their implementation has been used rather than ours). They also compare to ME and SCF, as well as to C2ST-L. and C2ST-S (Lopez-Paz and Oquab, 2017) which correspond to Classifier Two-Sample Tests based Sign or
C2ST-L
0.529
C2ST-S
0.452
MMD-O
0.316
MMDAggInc
0.281
SCF
0.171

---

Linear kernels. For the tests slitting the data, 1000 images from both datasets are used for parameter selection and/or model training, and 1021 other images from each distributions are used for testing. Consequently, tests avoiding data splitting are given the full 2021 images from CIFAR-10.1 and 2021 images sampled from CIFAR-10.
Experimental Results of Figure 1. We observe similar trends in all eight experiments in Figure 1: MMD-FUSE matches the power of state-of-the-art MMDAgg while being computationally faster (both theoretically and practically). These two tests consistently obtain the highest power in every experiment, except when increasing the number of Galaxy MNIST images where MMD-D obtains higher power. However, we observe in Table 1 that MMD-FUF FUSE outperforms MMD-D on another image data problem, also with large sample size. On synthetic data, the deep kernel test MMD-D surprisingly only obtains power similar to MMD-Spli in most experiments (even lower in the 2- dimensional perturbed uniform experiment). The two near-linear aggregated variants ACTT and MMDAgg trade-off a small portion of test power for computational efficiency, with the former outperforming the latter for large sample sizes. The importance of kernel selection is emphasised by the fact that the two tests using the median bandwidth (MMD-Median and CTT) achieve very low power. While the linear-time SCF test, based in the frequency domain, attains high power in the Mixture of Gaussians experiments, it has low power in the three other experiments. Its spatial domain variant ME performs better on Perturbed Uniform d E {1.2] experiments but in general still has reduced power compared to both linear and quadratic time alternatives. Finally, the AutoML test performs well for fixed sample size m = n = 500 (first row of Figure 1), but its power compared to other tests considerably deteriorates as the sample size increases (second row of Figure 1). Overall, MMD-FUSE achieves state-of-the ohtt-r-rtttttttt-ee performance across all experiments on both low-dimensional synthetic data and high-dimensional real-world data.
We report in Table I the power achieved by each test on the CIFAR 10 vs 10.1 experiment, which is averaged over 1000 repetitions. We observe that MMD-FUSE performs the best and obtains power 0.937, which means that out of 1000 repetitions, it was 937 times able to distinguish between samples from CIFAR-10 and from CIFAR-10.1. This demonstrates that the images in CIFAR-10.J 10.1 do not come from the same distribution as those in CIFAR-10.
Experimental Results of Table 1.
Experimental Results of Figure 7. We observe in Figure 7 of Appendix A.4 that MMD-FUSE can achieve higher power than MMDAgg in some additional perturbed uniform experiment. We also note that using relatively small number of kernels (e.g.. 10) is enough to capture all the required information, and that the test power is retained when further increasing the number of kernels.
Conclusions
In this work, we propose MMD-FUSE, an MMD- test which fuses kernels through soft maximum and a method for learning general two-sample testing parameters in an unsupervised fashion. We demonstrate the empirical performance of MMD-FUSE and show that it achieves the optimal MMD separation rate guaranteeing high test power. This optimality holds with respect to the sample size and likely also for the logarithmic dependence in a, but believe the dependence on could be improved in future work; a general question is whether lower bounds in terms of a and B can be proved. Obtaining separation rates in terms of the 1.2-norm between the densities (Schrab et al., 2023) may also be possible but challenging since this distance is independent of the kernel.
An open question is in explaining the significant empirical power advantage of the normalised test over its un-normalised variant, which is currently not reflected in the derived rates. The importance of this normalisation is clear when considering kernels with different bandwidths, leading to vastly different scaling in the un-normalised permutation distributions. Work here could begin with finite- sample concentration guarantees for normalised statistic or other "studentised" variants, some of which might obtain better performance.
Future work could also examine computationally efficient variants of MMD-FUSE, by either relying on incomplete Utstatisties (Schrab et al., 2022b) and leading to suboptimal rates, or by relying on recent ideas of kernel thinning (Domingo-Entr) Enrich et al., 2023) which can lead to the same optimal rate under stronger assumptions on the data distributions, or by considering the permutation- approach of Shekhar et al. (2022). Finally, our two-sample MMD fusing approach could be extended to the HSIC independence framework (Gretton et al., 2005, 2008; Albert et al., 2022) and to the KSD goodness-of of-fi setting (Chwialkowski et al., 2016; Liu et al., 2016; Schrab et al., 2022a).
10

---

Acknowledgements
We would like thank the anonymous reviewers and area chair for their thorough reading of our work, for their constructive feedback, and for engaging in the discussions, all of which have helped to improve the paper. Felix Biggs and Antonin Schrab both gratefully acknowledge the support from the U.K. Research and Innovation under the EPSRC grant EP/S022566/1. Arthur Gretton acknowledges support from the Gatsby Charitable Foundation.
References
Mélisande Albert, Béatrice Laurent, Amandine Marrel, and Anouar Meynaoui. Adaptive test of independence based on HSIC measures. The Anmals of Statistics, 50(2):858-879, 2022. (Cited on pages 4 and 10.)
Pierre Alquier.
User-friendly introduction to PAC-Bayes bounds. CoRR, abs/21 10.11216, 2021. URL batpss//arxiv..rrg abs/ 2110. 11216. (Cited on page 4.)
Nachman Aronszajn. Theory of reproducing kernels. Transactions of the American Mathematical Society, 68(3):337-404 1950. (Cited on page 3.)
Gregory Benton, Wesley J Maddox, Jayson Salkey, Julio Albinati, and Andrew Gordon Wilson. Function-space distributions over kernels. In H. Wallach, H. Larochelle, A. Beygelzimer, F. Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, vol- ume 32. Curran Associates, Inc., 2019. URL https: / p http://rrrreediiggneeeeeippppppp neurips. cc/paper_ pdf. (Cited on
page 3.)
Felix Biggs and Benjamin Guedj. Differentiable PAC-Bayes objectives with partially aggregated neural networks. Entropy, 23(10): 2021. doi: 10.3390/e23101280. URL /ttps://dol
org/10. htgg//..390////// 3390/e23101280 (Cited on page 4.)
Felix Biggs and Benjamin Guedj. Non-vacuous generalisation bounds for shallow neural networks. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Ballimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 1963-1981 PMLR, 2022a. URL https: http://ppoceee..eceeee/e/e .ml..ngg.........mmmm.......m..m wwwpediinnn.....psesee.e wttppp/eeeeeeeeeeeeeeeeeeeeeeeee html. (Cited on page 4.)
Felix Biggs and Benjamin Guedj. On margins and derandomisation in PAC-Bayes. In Gustau Camps- Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 3709-3731. PMLR, 28-30 Mar 2022b. URL http:tts://pooeediiii mlr. wwr..pess//ee v1vvv11111111 /i/biggg/baaaa..//////a html. (Cited on page 4.)
Felix Biggs and Benjamin Guedj. Tighter pac-bayes generalisation bounds by leveraging example difficulty. In Francisco Ruiz, Jennifer Dy, and Jan- Jan-Willem van de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 3165-8182 PMLR, 25-27 Apr 2023. URL htttss//proceeednngg .aw.:eeddinnnm.........mmmmmme.e mlr. ptwps/eeeiiieeee w206/ be000//bggg22aa. html. (Cited on page 4.)
Felix Biggs, Valentina Zantedeschi, and Benjamin Guedj. On margins and generalisation for voting classifiers. In NewrlPS, 2022. doi: 10.48555/axx...2006.44466 046607 URL https::/doi..rgg.
18550/arXivv 2206 04607. (Cited on page 4.)
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013. (Cited page 31.)
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http://github com/google jaxx. (Cited on page 18.)
Javier Cárcamo, Antonio Cuevas, and Luis-Alberte Rodríguez. A uniform kemel trick for high- dimensional two-sample problems. arXiv preprins 1rXiv:2210.02171, 2022. (Cited on page 6.)
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. In Hugo Larochelle,
11

---

Marc' Aurelio Ranzato, Raia Hadsell,
Balcan, and Hsuan-Ticc Lin, editors, Ad- vances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, viriual, 2020. (Cited on page 2.)
Olivier Catoni. PAC- Bayyesiaa Supervised Classification: The Thermodynamics of Statistical Learn- ing. Institute of Mathematical Statistics lecture moneg-hon series. Institute of Mathemat- google fr/books? ?d==
ical Statistics, 2007. ISBN 9780940600720.. URL
acHaAAAAMAAJ. (Cited on page 4.)
Anirban Chatterjee and Bhaswar B. Bhattacharya. Boosting the power of kernel two-sample tests. arXiv preprint arXiv:2302. 2023. (Cited on pages 2, S, and 9.)
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey E. Hinton. A simple framework for contrastive learning of visual representations. Proceedings of the 37th International Conference on Machine Learning. ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 1597-1607. PMLR, 2020a. (Cited on page 2.)
Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E. Hinton. Big self-supervised models are strong remi-supervised learners. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 1-, 2020, virtual, 2020b. (Cited on page 2.)
Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. In IEFE Conference on Computer Vision and Pattern Recognition, CVPR 2021, virtual, June 19-25, 2021, pages 177081 Computer Vision Foundation IEEE, 2021. (Cited on page 2.)
Xinlei Chen, Haoqi Fan, Ross B. Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. CoRR, abs/2003.04297, 2020c. URL https: /ttp//aax....abb/a//////a/a 04297. (Cited on page 2.)
Farah Cherfaoui, Hachem Kadri, Sandrine Anthoine, and Liva Ralaivola. A discrete RKHS standpoint for Nyström MMD. IIAL preprint hul-03651849, 2022. (Cited on page 5.)
Ben Chugg. Hongjian Wang, and Aaditya Ramdas. A unified recipe for deriving (time-uniform)
pac-bayes bounds. CoRR, abs/2302.03422 2023. doi: 10448550aaXi..22220004111 URL https:
//doi. 48550/ 18550/arXiv. 2302. 03421. (Cited on page 4.)
Kacper Chwialkowski, Dino Sejdinovic, and Arthur Gretton. A wild bootstrap for degenerate kernel tests. In Advances in neural information processing systems, pages 3608-3616, 2014. (Cited on page 4.)
Kacper Chwialkowski, Heiko Strathmann, and Arthur Gretton. A kernel test of goodness of fit. In International Conference on Muchine Learning, pages 2606-2615. PMLR, 2016. (Cited on page 10.)
Kacper P Chwialkowski, Aaditya Ramdas, Dino Sejdinovic, and Arthur Gretton. Fast two-sample testing with analytic representations of probability measures. In Advances in Neural Information Processing Systems, volume 28, pages 1981-1989, 2015. (Cited on pages 2 and 5.)
Namrata Deka and Danica Sutherland. Mmd-b-fair: Learning fair representations with statistical 2022. doi: 10.448550/axxx.2221..00
testing. CoRR, abs/2211.0799 org/10. 08/50000455///// arxiv. 2211. 07907. (Cited on page 5.)
URL https:://ol
Carles Domingo-Enrich, Raaz Dwivedi, and Lester Mackey. Compress then test: Powerful kernel testing in near-linear time. The 26th International Conference on Artificial Intelligence and Statistics, AISTATS 2023, 2023. (Cited on pages 2, 5, 8, 10, and 18.)
M. D. Donsker and S. S. Varadhan. Asymptotic evaluation of certain markov process expectations for large time, i. Communications on Pure and Applied Mathematics, 28(1):1-47, 1975. doi: https: //doi. //doi.org//00 1002/ cpa. 31 60280102. (Cited on page 3.)
316220002. URL https:/
wiley.
A. Dvoretzky, J. Kiefer, and J. Wolfowitz. Asymptotic Minimax Character of the Sample Distribution Function and of the Classical Multinomial Estimator. The Annals of Mathematicul Statistics, 27 (3):642 669, 1956. doi: 10. /211///m//1177728111111 URL https://doii org/10. /ttg//0.111..... aoms// 1177728174. (Cited on page 34.)
Raaz. Dwivedi and Lester Mackey. Kernel thinning. Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado,
12

---

USA, volume 134 of Proceedings of Machine Learning Research, page 1753. PMLR, 2021. URL http:///proceedings mlr. mal..presse wrw.s/ ht////13///////// //3.///wiii22a....mm html..... (Cited on page 5.)
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. Conference on Uncertainty in Artificial Intelligence 33., 2017. (Cited on page 4.)
Gintare Karolina Dziugaite and Daniel M. Roy. Data-dependent PAC-Bayes priors via differential privacy. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa- Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages cc/paper/ 2018 htt////01//////////// page 4.)
2018. URL httpt:t:ss:pp//oeee prw.eedinoceeeeeeeeeeeee neurips. hww.:/33aao076b11btrrtraaoo html. (Cited on
Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, Gabriel Arpino, and Daniel Roy. On the role of data in PAC-Bayes. In Arindam Banerjee and Kenji Fukumizu, editors, The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pages 604- 612. PMLR, 2021. URL http://prroeediing. mlr, www.pp.es./...........m.. http:////rroo..immddaaaaaaaeeee
html. (Cited on page 4.)
Brück Florian, lean-David Fermanian, and Aleksey Min. Distribution free mmd tests for model selection with estimated parameters. arXiv preprint arXiv:2305.07549 2023. (Cited on page 5.)
Magalie Fromont, Béatrice Laurent, Matthieu Lerasle, and Patricia Reynaud- Reynaud-Bouret. Bouret. Kernels based tests with non-asymptotic bootstrap approaches for two-sample problems. In Conference on Learning Theory, volume 23 of Journal of Machine Learning Research Proceedings, 2012. (Cited on page 4.)
Magalie Fromont, Béatrice Laurent, and Patricia Reynaud-Bouret. The two-sample problem for Poisson processes: Adaptive tests with nonasymptotic wild bootstrap approach. The Annals of Statistics, 41(3):1431-1461, 2013. (Cited pages 4 and 5.)
Hanjia Gao and Xiaofeng Shao. Two sample testing high dimension via maximum mean discrep- ancy. arXiv preprint arXiv:2109. 14913, 2022. (Cited page 5.)
Arthur Gretton, Olivier Bousquet, Alex Smola, and Bernhard Schölkopf. Measuring statistical dependence with Hilbert-Schmidt norms. In International Conference on Algorithmic Learning Theory. Springer, 2005. (Cited on page 10.)
Arthur Gretton, Kenji Fukumizu, Choon H Teo, Le Song, Bernhard Schölkopf, and Alex Smola. kernel statistical test of independence. In Advances in Neural Information Processing Systems, volume 1, pages 585-592, 2008 (Cited on page 10.)
Arthur Gretton, Kenji Fukumizu, Zaid Harchaoui, and Bharath K Sriperumbudur. A fast, consistent kernel two-sample test. Advances in Neural Information Processing Systems, 22, 2009. (Cited on page 5.)
Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander J. Smola. A kernel two-sample test. J. Mach. Learn. Res., 773, 2012a. doi: 10.5555/2503308. 2 1188410. URL https://d/dl acm. www//oi/////oooooooooooooo http:///i.1...555/5555550005 8, and 18.)
2188410. (Cited on pages 1, 5,
Arthur Gretton, Dino Sejdinovic, Heiko Strathmann, Sivaraman Balakrishnan, Massimiliano Pontil, Kenji Fukumizu, and Bharath K Sriperumbudur. Optimal kernel choice for large-scale two-sample tests. In Advances in Neural Information Processing Systems, volume 1, pages 2205-1213, 2012b. (Cited on pages 1, 2, and 5.)
Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H. Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Ávila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, Bilal Piot, Koray Kavukcuoglu, Rémi Munos, and Michal Valko. Bootstrap your own latent- A new approach to self- celfssuper learning. Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. (Cited on page 2.)
13

---

Benjamin Guedj. A primer on PAC-Bayesian learning. In Proceedings of the second congress of the French Mathematical Society, volume 33, 2019. URL https:t//tatiiii wwtggaa//g/....... 05353. (Cited on page 4.)
Maxime Haddouche and Benjamin Guedj. NeurlPS, 2022.
Online pac-bayes learning.
In
URL. http::/papers. www..niisss.aapppeemeo wwwppppppre.iaaeeeeeee filea//fffeeeeeeeeee paaprr/022.
-tt.1ess1111122444440-----ooaaea Conference html. (Cited on page 4.)
Maxime Haddouche and Benjamin Guedj. Pac-bayes generalisation bounds for heavy-tailed losses through supermartingales. Trans. Mach. Learn. Res., 2023, 2023. URL htttps://opentt
net/fforumidd-qxreeefss. (Cited on page 4.)
Omar Hagrass, Bharath K. Sriperumbudur, and Bing Li. Spectral regularized kernel two-sample tests. arXiv preprint wtXi::22/2.092000 2022. (Cited on pages 2 and 9.)
Kaiming He, Haoqi Fan. Yuxin Wu, Saining Xie, and Ross B. Girshick. Momentum contrast for unsupervised visual representation learning. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020, pages 9726-9735.
Computer Vision Foundation IEEE, 2020. (Cited on page 2.)
Jesse Hemerik and Jelle Goeman. Exact testing with random permutations. TEST, 27(4):811-225 URL httpt::///di..rg//////
Dec 2018. ISSN 1863-8260. doi: 10. 1001000//11799-17--57711
(Cited on page 4.)
Geoffrey E Hinton and Ruslan R Salakhutdinov. Reducing the dimensionality of data with neural networks. science, 313(5786):504-077, 2006. (Cited on page 2.)
Wittawat Jitkrittum, Zoltán Szabó, Kacper P Chwialkowski, and Arthur Gretton. Interpretable distribution features with maximum testing power. In Advances in Neural Information Processing Systems, volume 29, pages 181-189, 2016. (Cited on pages 2, 5, 8, and 18.)
Ilmun Kim and Aaditya Ramdas. Dimension-agnnotic inference using cross u-statistics. 2023. (Cited on page 5.)
Ilmun Kim, Sivaraman Balakrishnan, and Larry Wasserman. Minimax optimality of permutation tests. Annals of Staristics, 50(1):225-2) 251, February 2022. ISSN 0090-5364. doi:
Funding Information: Funding. This work was partially supported by the NSF Grant DMS- 17130003 and EP-SRC Grant EP/N031938/ Publisher Copyright: C Institute of Mathematical Statistics, 2022. (Cited on pages 3, 5, 27, 34, and 35.)
Matthias Kirchler, Shahryar Khorasani, Marius Kloft, and Christoph Lippert. Two-sample testing us- ing deep learning. In Silvia Chiappa and Roberto Calandra, editors, The 23rd International Confer- ence on Artificial Intelligence and Statistics. AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy]. volume 108 of Proceedings of Machine Learning Research, pages 1387-1398. PMLR, 2020. URL
mlr. wwwpseeeeeeeee w11////irr/ee/0000000 html. (Cited on page 5.)
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009. (Cited on pages 9 and 21.)
J. M. Kübler, W. Jitkrittum, B. Schölkopf, and K. Muandet. Learning kernel tests without data splitting. In Advances in Neural Information Processing Systems 33, pages 6245-6255. Curran Associates, Inc., 2020. (Cited on pages 2 and 5.)
Jonas M Kübler, Wittawat Jitkrittum, Bernhard Schölkopf, and Krikamol Muandet. A witness two- sample test. In International Conference on Artificial Intelligence and Statistics, pages 1403-1419. PMLR, 2022a. (Cited on page 2.)
Jonas M Kübler, Vincent Stimper, Simon Buchholz, Krikamol Muandet, and Bernhard Schölkopf. AutoML two-sample test. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, 2022b. (Cited on pages 2, 8, and 18.)
Alexandre Lacasse, François Laviolette, Mario Marchand, Pascal Germain, and Nicolas Usunier. PAC-Bayes bounds for the risk of the majority vote and the variance of the Gibbs classifier. In Bernhard Schölkopf, John C. Platt, and Thomas Hofmann, editors, Advances in Neural Information Processing Systems 19, Proceedings of the Twentieth Annual Conference on Neural Informa- tion Processing Systems, Vancouver, British Columbia, Canada, December 4-7, 2006, pages 769-776. MIT Press, 2006. URL. httpt:tttt///teeeeee httppppee//roooeeinggs... wwwpiinnn...nnineeeeeeeee newrips cc/ pttpp/pppe/00/////////// /hash/ 779effoo2445577777eeedd383778763 Abstracct html. (Cited on page 4.)
14

---

Alexandre Lacasse, François Laviolette, Mario Marchand, and Francis Turgeon- Boooon. Learning with randomized majority votes. In José Balcázar, Francesco Bonchi, Aristides Gionis, and Michèle Sehag, editors, Machine Learning and Knowledge Discovery in Databases, European Conference, F.MLI. PKDD 2010, Barcelona, Spain, September 20-24, 2010, Proceedings, Part HI volume 6322 of Lecture Notes in Computer Science, pages 162-177. Springer, 2010. doi: 10. 186-3-642-15883-44 on page 4.)
URL httph::t///i.i. http//dii.oggg/g// 1ttp:/111100/97---3--11 642- 12888-4__20 4_1 (Cited
Justin Lee. U-statistics: Theory and Practice. Citeseer, 1990. (Cited on page 35.)
Guy Lever, François Laviolette, and John Shawe-Taylor. Tighter PAC-Bayes bounds through distributionn-deeendett priors. Theoretical Computer Science, 473:4-28, February 2013. ISSN 0304-3975. doi: 10.
URL https://Linkinghubb elsevier, com/ (Cited on puge 4.)
Tong Li and Ming Yuan. On the optimality of gaussian kernel based nonparametric tests against smooth alternatives. arXiv preprint arXhv:1909.03302 2019. (Cited on page 5.)
Yazhe Li, Roman Pogodin, Danica J. Sutherland, and Arthur Gretton. Self-supervised learning with kernel dependence maximization. In Mare Aurelio Ranzato, Alina Beygelz- imer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Ad- vances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 15543-15556, 2021. URL https: //ppoc/ed/ooc megriin.uipp.... cttccc///pppa (ppaper//2///aaae///apppaaa 83004190b
hataaeaaaaeebb--abaatttt.t..ee Abstract. (Cited on page 2.)
Jen Ning Lim, Makoto Yamada, Wittawat Jitkrittum, Yoshikazu Terada, Shigeyuki Matsui, and Hidetoshi Shimodaira. More powerful selective kernel tests for feature selection. In International Conference on Artificial Intelligence and Statisties, pages 820-830. PMLR, 2020. (Cited on page 5.)
Feng Liu, Wenkai Xu, Jie Lu, Guangquan Zhang, Arthur Gretton, and Dougal J Sutherland. Learning deep kernels for non-pane parameereeicc wample tests. In International Conference on Machine Learning, 2020. (Cited on pages 2, S, 8, 9, 18, and 21.)
Feng Liu, Wenkai Xu, Jie Lu, and Danica Sutherland. Meta two-sample testing: Learning kernels for testing with limited data. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 5848-5860, 2021. URL h neurips. cc/paper page 2.)
Abstract. html. (Cited on
Qiang Liu, Jason Lee, and Michael Jordan. A kernelized Stein discrepancy for goodness-offfe tests. In International Conference on Machine Learning, pages 276-284. PMLR, 2016. (Cited on page 10.)
David Lopez-Pazz and Maxime Oquab. Revisiting classifier two-sample tests. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Confer- ence Track Proceedings. OpenReview.net, 2017. URL
SJxxfE55x. (Cited on page 9.)
Andrés R. Masegosa, Stephan Sloth Lorenzen, Christian Igel, and Yevgeny Seldin. Second order PAC-Bayesian bounds for the weighted majority vote. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Aisun-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL https: / http:::ttt/ootooeoo pttp///eoocccc..c////////o/ wew.eeiiinnnnnnnnis...eee neurips. cc/papee/2220///s/33355444 http://///000.111110033303330000
html. (Cited on
puge 4.)
P. Massart. The Tight Constant in the Proretzky-KKefer-Wollel Probability, 18(3):1269 1283, 1990. doi: 10. 1992214440//1777999746 URL https:///oi. org/ 10. 2214///pp11769900000
Inequality. The Annals of
(Cited on page 34.)
Andreas Maurer. A note on the PAC-Bayesian theorem. CoRR, cs.LG/041109) 2004. URL (Cited on page 4.)
David A McAllester. Some PAC-Bayesian theorems. Proceedings of the eleventh annual conference on Computational Learning Theory, pages 230-234. ACM, 1998. (Cited on page 4.)
15

---

Alfred Müller. Integral probability metrics and their generating classes of functions. Advances in Applied Probability, 14429-443 1997. (Cited on page 6.)
Maria Perez-Ortiz, Omar Rivasplata, John Shawe-Taylor, and Csaba Szepesvari. Tighter risk cer- tificates for neural networks. Journal of Machine Learning Research, 22 2021. URL
http://jmlr org/ http//ppps//22222222 200vv/222200000 201//00-8979 html. (Cited on page 4.)
Aaditya Ramdas, Sashank Jakkam Reddi, Barnabás Póczos, Aarti Singh, and Larry Wasserman. On the decreasing power of kernel and distance based nonparametric hypothesis tests in high dimensions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015. (Cited on page 2.)
Benjamin Recht, Rebecca Roclofs, Ludwig Schmidt, and Vaishaal Shankar. Do ImageNet classifiers generalize to ImageNet? Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 5389-5400 5400. PMLR, 09-15 Jun 2019. URL.https:
mlr. wtt.press/v//// htt///rchtttt html. (Cited on pages 9 and 21.)
Sashank Reddi, Aaditya Ramdas, Barnaáss Póczos, Aarti Singh, and Larry Wasserman. On the high dimensional power of a linear-time two sample test under mean-shift alternatives. In Artificial Intelligence and Statistics, pages 772-780. PMLR, 2015. (Cited on page 2.)
David Rindt, Dino Sejdinovic, and David Steinsaltz. Consistency of permutation tests of independence using distance covariance, hsic and dhsic. Stat, 10(1):e364, 2021. doi: https://doi. 10. 1002/ sta4.364. URL https: ptrtts://ollln //on///nnllln inelibrary. wiley- com/ /ooi/abs/00../ 100./00a2.sa.a.ee 364. e364 sta4.364. (Cited on pages and 19.)
Joseph Romano and Michael Wolf. Exact and approximate stepdown methods for multiple
hypothesis testing. Journal of the American Statistical Association, 100(469):94-008, 2005. (Cited on page 4.)
Mark Rudelson and Roman Vershynin. Wriiht inequality and sub-gaussian concentration. Electronic Communications in Probability, 18(none):1 9, 2013. doi: 10.1214/EPP11--255
URL attpps://dbl org/oro//// 10. 1214/ECP
(Cited on page 25.)
Antonin Schrab, Benjamin Guedj, and Arthur Gretton. KSD aggregated goodness-of-fit test. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, 2022a. (Cited on page 10.)
Antonin Schrab, Ilmun Kim, Benjamin Guedj, and Arthur Gretton. Efficient aggregated kernel tests using incomplete U-statistics. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, 2022b. (Cited on pages 2, 5, 8, 9, 10, and 18.)
Antonin Schrab, Ilmun Kim, Mélisande Albert, Béatrice Laurent, Benjamin Guedj, and Arthur Gretton. MMD aggregated two-sample test. Journal of Machine Learning Research, 24(194):1-81 2023. URL http:// //jlrr./////r///////// org wtggpapprs//////11-11 1289//21111111111/111 .tml.. (Cited on pages 2, 4. 5, 8, 9, 10, 18. 22, and 35.)
Matthias Seeger, John Langford, and Nimrod Megiddo. An improved predictive accuracy bound for averaging classifiers. In Proceedings of the 18th International Conference on Machine Learning, number CONF, pages 290-297, 2001. (Cited on page 4.)
Yevgeny Seldin, François Laviolette, Nicolò Bisachiancci, John Shawe- Taylor, and Peter Auer. PAC-Bayesian inequalities for martingales. In Nando de Freitas and Kevin P. Murphy, editors, Proceedings of the Twenty-Eight Conference on Uncertainty in Artifi- cial Intelligence, Catalina Island, CA, USA, August 14-18, 2012, page 12. AUAI Press, jsp?mmmu ksmmu=28
2012. URL https::/dslpitt. http://////..//ap////aaaa..ocaaa article_ion id= wtweee_ddd22441pproeeeeee 2341approceeding_iee 18_ (Cited on page 4.)
Shubhanshu Shekhar, Immun Kim, and Aaditya Ramdas. A permutation-free kernel two-sample test. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NewrlPS 2022, 2022. (Cited pages 5 and 10.)
16

---

Bharath K Sriperumbudur, Kenji Fukumizu, and Gert RG Lanckriet. Universality, characteristic kernels and RKHS embedding of measures. Journal of Machine Learning Research, 12(7), 2011. (Cited on page 3.)
Danica Sutherland, Hsiao-Yu Yu Tung, Heiko Strathmann, Soumyajit De, Aaditya Ramdas, Alex Smola, and Arthur Gretton. Generative models and model criticism via optimized maximum mean discrepancy. In International Conference on Learning Representations, 2017. (Cited on pages 1, 2. and 18.)
Martin J. Wainwright. High-Diimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2019. doi: 10.1017/9781 108627771. (Cited on page 32.)
Mike Walmsley, Chris J. Lintott, Tobias Géron, Sandor Kruk, Coleman Krawczyk, Kyle W. Willett, Steven Bamford, William Keel, Lee S. Kelvin, Lucy Fortson, Karen L. Masters, Vihang Mchta, Brooke D. Simmons, Rebecca J. Smethurst, Elisabeth M. Baeten, and Christine Macmillan. Galaxy 200 decals: Detailed visual morphology measurements from volunteers and deep learning for 314, 000 galaxies. Monthly Notices of the Royal Astronomical Society, 509:3966-39988 2022. (Cited on pages 9 and 20.)
Yi-Shan Wu, Andrés Masegosa, Stephan Sloth Lorenzen, Christian Igel, and Yevgeny Seldin. Chebyshev-Cantelll PAC-Bayes-Bennet inequality for the weighted majority vote. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neurul Information Processing Systems 34: Annual Conference on Neu- ral Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 12625-12636. 2021. URL htttts://ptooeeeeeee /ttp:///oreeeeneeee//e/e neurips. cc/ wwcppppp////ae / 2021 ///21//hhh/// 99388f6bb.rree666622244488888888
Abstract html. (Cited on page 4.)
Makoto Yamada, Denny Wu, Yao-Hung Hubert Tsai, Hirofumi Ohta, Ruslan Salakhutdinov, Ichiro Takeuchi, and Kenji Fukumizu. Post selection inference with incomplete maximum mean dis- crepancy estimator. In International Conference on Learning Representations, 2019. (Cited on page 5.)
Valentina Zantedeschi, Paul Viallard, Emilie Morvant, Rémi Emonet, Amaury Habrard, Pascal Germain, and Benjamin Guedj. Learning stochastic majority votes by minimizing a PAC-Bayes generalization bound. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021. NeurIPS 2021, December 6-14, 2021, virtual, pages 455-467, 2021. URL httt:ps:/pproceediiiii 2021 hhtp/haah//00 0at.5770eaa44ddeeedd00..........
neurips cc/paper/ -astsfftbttttt.ttaao html. (Cited on page 4.)
Wojciech Zaremba, Arthur Gretton, and Matthew Blaschko. B-test: A non-parametric, low variance kernel two-sample test. Advances in neural information processing systems, 26, 2013. (Cited on page 5.)
Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: Sulf-supervieed learning via redundancy reduction. In Marina Mcila and Tong Zhang. editors, Proceedings the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 12310-12322 PMLR, 2021. URL httt http::://ppoooednggg.. mlr, press/v1333 /t/////oootr2aaaa html. (Cited on page 2.)
Zhao and Deyu Meng. FastMMD: Ensemble of circular discrepancy for efficient two-sample test. Neural computation, 2765):335511377 2015. (Cited on page 5.)
Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P. Adams, and Peter Orbanz. Non-vacuous gen- eralization bounds at the ImageNet scale: PAC- BCC-BBysiian compression approach. In International Conference on Learning Representations, 2019. URL httph:ts//// /ttpss//opeerrrieee net = BJgqgsAct7. (Cited on page 4.)
17

---

Overview of Appendices
Appendix A We give further experimental details, discuss time complexity of our results while graphing run-times.
Appendix We discuss how FUSE, can be expressed in a simple form for certain uncountable priors.
Appendix C We prove exponential concentration bounds for both our statistics under the null and permutations.
Appendix D We prove exponential concentration bounds for the FUSE; statistic under the alterna- tive hypothesis.
Appendix E We prove the power results stated in Section 5 and other interesting intermediate results.
A
Additional Experimental Details
A.1
Code and licenses
Our implementation of MMD-FUSE in Jax (Bradbury al., 2018), as well the code for the reproducibility of the experiments, are made publicly available at:
https://giie http:///gttttut.oo com/ aeatoninsccraabmmddfnoo paper
Our code under the MIT License, and we also implement ourselves the MMD-Median (Gretton et al., 2012a) and MMD-Split (Sutherland et al., 2017) tests. For ME & SCF (Jitkrittum et al., 2016), MMD-D (Liu et al., 2020), AutoML (Kübler et al., 2022b), CTT ACTT (Doningo-Enrich et al., 2023), MMDAgg & MMDAggInc (Schrab et al., 2023, 2022b), we use the implementations of the respective authors, which are all under the MIT license.
The experiments were run on an AMD Ryzen Threadripper 3960X 24 Cores 128Gb RAM CPU at 3.8GHz and on an NVIDIA RTX A5000 24Gb Graphics Card, with a compute time of couple of hours.
A.2
Test parameters
In general, the default test parameters recommended by the authors of the tests (listed above). For the ME and SCF tests, ten test locations are chosen on half of the data. AutoML is run with the recommended training time limit of one minute.
Kernels. As explained in Section (SDistribution on Kernels), for MMD-Fuse, we use Gaussian and Laplace kernels with bandwidths in (95% + =(( 05%) i 0,...,9, 9} where 35% is half the 5% quantile of all the inter-sample distances {|| - 2'11, x' E Z} with r = 1 and r = 2 for Laplace and Gaussian kernels, respectively. Similarly, 655% is twice the 95% quantile.
MMD-Split selects Gaussian kernel on half of the data with bandwidth in {45% - i(965% 1/99) i ...... 99} by maximizing a proxy for asympiotic power which is the ratio of the estimated MMD with its estimated standard deviation under the alternative (Liu et al., 2020, Equation 3). The
MMD test is then run the other half with the selected kernel.
CTT and MMD-Median both use a Gaussian kernel with bandwidth the median of {||2 2/112 2, E Z), while ACTT is run with Gaussian kernels with bandwidths in {95% + 2( 15% )/9
i= 0, .).
The MMDAgg and MMDAggInc tests use collections of 20 kernels split equally between Gaussian and Laplace kernels with ten bandwidths each, but they use different (non-uniform) discretisation of the intervals [955% : 15%
with their default implementations, which similarly
Permutations. For MMD-Median, MMD-Split, and MMD-FUSE, we use 2000 permutations to estimate the quantiles. MMDAgg and MMDAggInc use 2000 + 2000 and 500 500 permutations, respectively, to approximate the quantiles and the multiple testing correction. The CTT and ACTT tests are run with 39 and 299 + 200 permutations, respectively. AutoML uses 10000 permutations
18

---

and MMD-D 100 of them. The ME and SCF tests use asymptotic quantiles. We recall that using higher number of permutations for the quantile does not necessarily lead to more powerful test (Rindt et al., 2021, Section 7).
A.3 Details on the experiments of Section 6
In this section, we present figures illustrating the four experimental settings described in Section with results in Figure 1: Mixture of Gaussians (Figure 2), Perturbed Uniform d = (Figure 3), Perturbed Uniform (Figure 4), Galaxy MNIST (Figure 5), and CIFAR 10 vs 10.1 (Figure 6).
20-
20
Figure 2: Mixture of Gaussians. Both distributions are mixtures of four 2-dimensional Gaussians
with means (+20, +20) and standard deviations σi d2 d3 1. Samples from (orange) are drawn with 04 = while samples from (blue) are drawn with σ₁ = 2.
2.0
1.5
1.0
0.5
0.0
0.0
0.5
1.0
Figure 3: Perturbed Uniform d = 1. One-dimensional uniform densities with two perturbations are plotted for various amplitudes a.
19

---

05
0.5
0.5
Figure 4: Perturbed Uniform d = 2. Two-dimensional uniform densities with two perturbations per dimension plotted for various amplitudes a.
Figure 5: Galaxy MNIST (Walmsley et al., 2022) images in dimension x 64 x 64 across four categories: 'smooth cigar' (first row), 'edge disk' (second row), 'unbarred spiral' (third row), and 'smooth round' (fourth row).
20

---

(a) CIFAR-10 10 images
(b) CIFAR-10. 10.1 images
Figure 6: Images from the CIFAR-10 (Krizhevsky, 2009) and CIFAR-10.1 (Recht et al., 2019) test sets. This figure corresponds to Figure Liu et al. (2020).
21

---

A.4 Experiment varying the number of kernels
In Figure we provide an additional perturbed uniform experiment where we vary the number of kernels for MMD-FUS and for MMDAgg. We consider the task of detecting six me-dimensional perturbations with amplitude a 0.5 for sample sizes n 500 while varying the number of Gaussian and Laplace kernels from 10 to 1000.
Firstly, we observe that MMD-FUSE achieves higher power than MMDAgg in this setting. Secondly, both MMD-FUSEE and MMDAgg retain their power when increasing the number of bandwidths. This matches the empirical observation of Schrab et al. (2023, Section 5.7) that discretisation of 10 bandwidths is enough to capture all the information in certain two-sample problems and that using finer discretisation (which is computationally more expensive) does not improve the test power.
1.0
0.8
0.6-
Power
0.4
0.2
MMD-FUSE
MMDAgg
0.0
10
200
400
600
800
1000
Number of kernels
Figure 7:
Power experiment with perturbed uniform samples while varying the number of kernels.
A.5
Time complexity and runtimes
The time complexity of MMD-FUSE
о OK B (m² + n²))
(5)
where m and n are the sizes of the two samples, K is the number of kernels fused, and B is the number of permutations to estimate the quantile. Note that this is an improvement over the time complexity of MMDAgg (Schrab al., 2023)
o(K okK(BB (m² + +²))
(6)
where the extra parameter B' corresponds to the number of permutations used to estimate the multiple testing correction, often set as B' = B in practice (Schrab et al., 2023, Section 5.2). We indeed observe Figure that MMD-FUSE runs twice as fast as MMDAgg.
While the runtimes of most tests should not depend on the type data (only on the sample size and on the dimension), note that the runtimes of tests relying on optimisation (e.g. ME & SCF) can be affected. In the experiment of Figure 8, we consider samples from multivariate Gaussians centred zero with covariance matrices la and a La with 1.1. We vary both the sample sizes and the dimensions.
"The two constants hidden in the O-notations of Equations (5) and (6) are exactly the same, which is indeed verified by empirical observations.
22

---

Time (sccarrs)
Time (seconds)
10
109
10-2
10-2
Sample size
Diimmsiinn
MMD-FUSE
MMDA3s
ACTT
ME
MMD-D +
MMD-Mediin
MMDAAglie
CTT
SCF
AutoMI.
MMD-Spht
Figure 8: Test runtimes plotted using logarithmic scales. In the LHS figure, we vary the sample size for fixed dimension 10. In the RHS figure, we vary the dimension for fixed sample size 500. The mean and standard deviations the test runtimes over repetitions are reported. Recall that the tests are run with their default parameters with different numbers of permutations, and that AutoMI. has training time parameter which set to 60 seconds by default, as described Appendix A.2.
23

---

B Closed Form Mean Kernel
We have observed in the main text that in some cases where the prior has non-finite support, FUSE, still gives a straightforwardly expressed statistic. This happens because for certain kernel choices, the expectation of the kernel with respect some parameter is still closed form kernel. We give one example of such a statistic here.
Theorem 4. For any fixed a O, the following is an example of a FUSE1 statistic:
(Z) log R + 1/R
FUSE, (Z)
sup MMD 1=0
(ong)
A
where kygla.)) (1 + ||- - y / is a rational quadratic kernel, and no is the "prior" " bandwidth (which can essentially be absorbed into the data sealing).
Proof of Theorem 4. Firstly, we define general rational quadratic kernel
Brg(a.)) (z, 3) = 1 |
v12
2n²
Note that (r) e- with r = | U|12 is bounded kernel with parameter т. If take the expectation of with respect to Gamma distribution,
Ey-I(a, /²
7 -0-1
(xx(=3)xxpp-110 dr
T(a)
f
B p2
T(a)
I(a)
2
p2 aa
k (r)
23
where I denotes the gamma function. The KL divergence between Gamma distributions is
A(oa)
(o, ((o, Bo)) (a ao) + log T(a) ag log R -1
where R= 8/80 and ((a)) (a)))(((a) denotes the digamma function. Using the dual form of FUSE, we find that
(Z) KL(T( (), 3o))
FUSE
sup a>0,8>0
MMD
Restricting ap, prior 3o n and setting 3 = Rin gives the result.
24

---

C Null and Permutation Concentration Results
In this section we prove the following concentration results under the null (or equivalently, under the permutation distribution). These results show that for appropriate choices of X, both statistics converge to zero at rate at least ((1/n) under the null or permutations. We recall that without loss of generality n. S m.
Theorem 5. For bounded kernels S oo and parameter with probability at least 8 over
sample Z from the null,
4x
log
FUSE (Z) I
n1 1)
A
provided 0 < A Vn(n 1)/8v 2x, and
+ 32 log K 22m(n -1) 2
-FUSE1(Z) S
For potentially unbounded kernels and parameter X, with probability least 1 over sample Z from the null,
16A
log 5/
FUSE (2) S n(n 1)
provided 0 < X < Vn(n 1)/16/2, and
1 32 log
FUSEN -
/2n(n - 1)
The above bounds are also valid for FUSE I), FUSEN (a Z) and any fixed Z (potentially non- null) under permulation by Uniform (.)m)
While the upper bounds depend critically upon our choice of X, the lower bounds instead hold regardless of X. Choosing vn(n - 1) x n gives the desired upper bound rates (1/n))
C.1 Sub-Gaussian Chaos Theorem
We provided constants for Theorem 5, even though they are not strictly necessary, as we hope they could be useful when adapting FUSE statistics other settings. In particular, the constants help understand for which values of the bounds hold, and to understand the relation between the two different right hand side terms which can be matched by tuning X. In provide these constants, in this subsection we replicate the proof of a sub-result from Rudelson and Vershynin (2013), but unlike in that paper explicitly keep track of the constants. To be clear, Rudelson and Vershynin (2013) does not give numerical constants at all (only their existence is proved), and we need then for our statement of Theorem 5. We do not claim this contribution, the proof is only included so that are not stating the numerical constants without justification.
Theorem Subb-Gaussia Chaos; adapted from Rudelson and Vershynin, 2013). Let X; be mean- zero 1-sub- Saub-Gaussian variables, such that log Ex exp(t.X) S 1122 for every i E R. Let A E Raxn be real symmetric matrix with zeros on the diagonal and we define the sub-Gaut Gaussian chaos
W
A
=1
For all [t] S (4V2
Ex exp(IW) exp (161 (111)))))
Proof. This proof is closely adapted from Rudelson and Vershynin (2013) with some modifications to explicitly track numerical constants.
Let X, be mean-zero 1-sub- Gau-Saassii variables, such that log Ex exp(tX) s 2 for every t R. We are considering
W Σ AijX,X
25

---

where Ag has zeros on the diagonal. We introduce independent Bernoulli random variables ò; E {0, 1) with ES; = 1/2 and define the matrix A with entries (A²),s = 5;(1 - Aij. Note that E = 1,, since E - 6,) equals 1/4 4 for i * j.
Writing the set of indices As {i [n] 8 1}, introduce
W Σ Alj X,X,
E
A
Σ jEAS
X,
( AnXx)
Σ iEAa
NEAS.JEAS
By Jensen's inequality,
Ex exp(LW) S exxxex((.WW.))
Conditioned on d and (X Ws is linear combination of the mean-zero sub-gaussian random variables X,.J E Ag. follows that this conditional distribution of Ws is sub-gaussian, and so
Exxybsag exp(4lW,) exp
Σ JEAS
Σ EEAs
Anx))
Now introduce g also arise directly as the moment generating function of these Normal variables, so we make the further equality (for fixed and 8).
(g1 (g1..... 9n) (O, 1) i.i.d draws from normal and note that the above can
exp 2
Fayy E
(
Σ (EAsX)))
E, exp
41
Σ
96
Σ A xxxx)
JEAS
SEAr
jEAş
ieA:
Rearranging the terms, and using that the resulting term is linear combination of the uub-Gaussian X,, E As, we find that
Ex,g exp
4t
Σ jEAG
91
= Ex.g exp
4t Σ X;
Σ
Asg:))
=EAs
sEAs
jEAS
< Ex exp
(4t)
Σ
Aujgs)
2
ieAs
JEAS
8,(1 5,) -,))) )²
< Ex exp
8t Σ
Σ
< Ex, exp (8t² 1 (49913)
Now, by the rotation invariance of the distribution of the random variable ||,4% g is distributed identically with E; s where s, denote the singular values of A so by independence
Ex.g exp (8 = Eg exp 8t
Ey exp (812 87
< II exp (161²
where the last inequality holds if 812 max; of < and arises since the MGF of Chi-squared variable, Eetn² c² for < t S 1.
Since max; ||l || and Σ, = || |||| combine the above steps find that
Ex exp(tW) s exp (1441))))))))) for S (4v2)AAI)
26

---

C.2 Permutation Bounds for Two-Sample U-Statistics
The main technical result we use for the null bounds is the following. Here we assume the permutation invarriacc property of the U statistic kernel that h(21, 225 91. M2) h(22, 31 y2) h(21, 225 92, 81). This can always be ensured by symmetrizing the kemel,, and is satisfied by the kernel used by MMD which we consider in this paper.
Theorem 7. Fix combined sample of size n + m with n S m and let h(21, 222 U2) be two-sample U-statistic kernel described above. Define
(Z)
E (L,P))lnla (Id)))(m)a
E
MZ Zui Zntss Z
n(n 1)m(m - 1)
and
(x( = nln 1)m(m - 1) dEEntm
sup
Σ
Σ h(Zo(1) Zo(e)) Zo(n+s)> Zo(u+z)))
(L.))(1)2
((55))(m]
ff E Uniform(@xto)) is random permutation of the dataset, then then for all [t] < (4v (4V)
E. exp((U((oo)) exp (2))
Theorem 8 (Normaliser Bound). 2' = k( xx) + k(y. v') k(x,,0) - k(x', ,2) then
16
(x n(n 1)
(z)
where S and
(Z) n(n 1)
Σ
k(Zz,
(1.))
Additionally, if0 S k(xxx²) S for all x', then
4x
(Z) < n(n 1)
Proof of Theorem Firstly, we make the following definitions based on the work of Kim et al. (2022): let L = (l...., (n) be n-tuple drawn uniformly without replacement from [m]] Then for any fixed
Eg (Z)) (2)
where we define
(Z) n(n
Σ
12 Zzz Zutti Znttl)-
((J))(n)
Note that in the above we have used the invariance h(01, 82i 31 V2) = h(x1, T25 y2. V1). Now additionally define Çi as i.i.d. Rademacher variables, and let a Uniform(Gntte For any fixed Z
(oZ) = it (oZ)
(8)
where we have defined
(Z):= = nnn 1)
Σ Glih(Z,, Zj: Zutte Zuti,)-
(6.))e/ml2
This works because we can first define 2, = Z, or Ż, Zn+te each with probability }. The distribution of (a = Ü Z)) and then using the symmetry of k(z, y) in its arguments gives the equivalence Equation (8) (c.f. eq. 28, Kim et al., 2022).
Now for fixed Z, combining Equations (7) and (8) and Jensen's 's inequality we gives
E, exp(tU> (a Z)) E, exp(tE, (o (o)
27

---

E. exp((tB..cUU 1. (o (
< Bo, exp
Σ
(igh(Za()) Zo() (o Lo(+)))) Lo (o(m-1s)))
n(n 1)
(IJ))|mla
Eo. exp
1 n(n 1) 1) (15))(nl2
GGEEE, [1(2)))) Zo(s); Zo(ntl)) 2oca+t,))lo)
=: Eg exp
Si
In the final step we have defined the matrix A", with entries AG = (n(n
1)) E (z)) Zot (n+t)) [o for j and A 0 for all i.
We note that is independent and satisfies the conditions of Theorem 6, so applying this theorem we obtain that
Eo. exp
i=
< E, exp (1612 ||
for [4| < (4
s E exp (1612) || (11))²))
for | < (4v2|111 ||])
eep
1612
sup GEG.-m
||4
for |4| < (4v2
sup
||
o6
where in the second line we have used that || S || for any matrix M. Now note that
|| 3
(2
Σ
(EL [M(Z(()), Zo(ry Zo(nti)) Zo(a+)a))o)))
n 1)2 (1,7)))lla
2
Σ
h(Zo(S); Zotsyi (o(nts) Zo(n+s))
n² - 1)2 (L,))(nn)
m(m 1)
(i
We complete the proof by noting that ÜR (Z)² SuPoEentm 11
Proof of Theorem 8. We have
(2(Z)= = n²(n 1)2
Σ
Σ
h M(Z((). Zotey; Zo(ns)) Zo Zo(n+))))
m(m 1)
(jd')E(lle
Σ
M(Z(()) Zo(e); Zo(n+))> Zo (n+
n² n²(n 1)3m(m-1 1)
(1,7) (id')((m)
Σ
Σ
(k(Zo()) 22(r))² + ke (Z Z Zo(n+)))
n2(n 1)2m(m-) (l,)) (J)
+ k(Z0(0) Zo(n+gg)² + k((o(())) Zo +
m(m - 1)
Σ
M(Zo(1) 22
n2(n - mm
ml m - 1)
28

---

+ +n(n - 1) Σ
k[Zo(x+))) Zo(n+)))
+ (m - 1)(n - 1)
Σ
Σ
(()) Za(n+)))2
Ssigh 15jsm
+ (m -1) Σ
1)
Σ
k(Z Z)(
ISiEn ISism
16
Σ
23)
n²(n 1)2
(k.))(m+tlla
16
(Z)
n(n
where the first inequality holds by Jensen's inequality, the second by convexity (so that (a + b d)² < 4(a² + 62 + c² d) and the third inequality using n S m to upper bound each of the four scalars inside the parentheses by m(m 1), and we also upper bounded each of sums over subsets of terms by the sum over all possible terms.
For the second part note that since h E [-2x, 2nc]
(Z( n2(n 1)²
Σ
1 m(m 1)
Σ (1.))(ml)
h(Zo(s, Zoteri Zo(nts), Zointzr)
Σ
(2x)
n²(n 1)²
((,"))(n)2
4x²
n(n - 1)
C.3 Bounds for MMD-FUSE under Null: Proof of Theorem 5
Proof of Theorem 5. Note under the null Z is permutation invariant. We will use Theorem with the MMD 2-statistic kernel, that U&(Z) MM (for fixed k). We will use the notation
S1-8 to denote that the inequality holds with probability at least 1 - over the random variables being considered.
Note that 02 S 4k" (n2/nn(n - 1) from Theorem 8, so that log Ba>r((Z)) exp AMMD (MMD)(X.Y) X)
S1-8 log Ez BBx exp
(XMMD)(X,)) + +log~
Markov
log F, z F. xxxx((22)
exp
( +log
Null Permutation-
log Ez E k (2)) E.r exp
AMMD +log
Prior Permutation-Fiee
1 5
< log E (2)) E exp (X²U?) + log
1 n(n - 1) + log n'
2x²
where the penultimate result holds using Theorem 7 provided [X] < (4V2sup, (z)) Using the bound on Ug from above gives the | < Vn(n 1)/8 in the theorem statement.
By dividing MMD by the permutation invariant Ñú in every one of the above, we also find that
MMD Y)
X²02
1 5
log ((2)) exp
S1-5 log Ez (a exp
+ log
Na((Z))
V ((()
29

---

16A2 n(n - 1) + log 5
(10)
(11)
the first inequality using that NR is permutation-invariant and holding for xx]
ssup, 2uup UL( The final step uses that 02 S 16Nx - 1) from Theorem
which also shows that [|] vn(n 1)/16/22 sufficient.
The upper tail bounds for FUSEN and FUSE, immediately follow from the above by dividing through À and from their definitions.
Lower Bounds.
For the lower tails,
-FUSE; (Z)
log E B exp eXp(AMMD) (Z)
À
< R [M)]
Jensen
1
log o (x)(EE))((2))
sMDD
introduce dummy > 0
8
log
Jensen on exp
8
4x²s
1
S1-5
+ log 8'
n(n
1)
where the last line follows from Equation (9) replacing À by dummy variable -s for < s < we importantly note that this bound held for negative by Theorem 7.
By following the same process for FUSEN and instead using Equation (10), also holding for potentially negative A, we obtain
16s
FUSEN S1-6 n(n 1)
log
for < < - 1)/16
For the small 5 we generally use, these are tightest when is at its maximum permissible value, so we substitute these values for the theorem statement.
Under Permutation. Z and our application of Markov's inequality introducing expectation over with one over a. This changes nothing else in the derivations.
To prove the equivalent result for o Z under permutations, we replace Z by
L
30

---

D Concentration under the alternative
We give the exponential convergence bounds for FUSE, under the alternative and relate it to its mean. In the following we will assume that K. is class of kernels bounded by 0 < < oo, so that FUSE; [-2x, 2n.]. We also introduce the following quantity (for fixed, data-free prior T) which is closely related to the expectation of FUSE1.
KT((p T) A
FUSE1 = sup MMD K. (P..9) PEMi (K)
Theorem 9. FUSE, is bounded in the following ways:
( m
FUSE, < 2 FUSE, s FUSE, +8
n
and
M (p.
FUSE,
sup (EM
MMD K2 K, (p,9) S sup MM.
kEsupp(x)
Under the null hypothesis FUSE, =0
We can now state concentration results for FUSE, in terms of FUSE1
Theorem 10. With probability at least 1 - over the sample
(1
1
log 5
FUSE, (Z) FUSE, 2
+
m
and with the same probability.
FUSE, FFUSE, S 20// ( log
1 m
D.1 Proofs
Note on the proofs. The "bounded difference lemma" (Theorem 11) we give below is not the same as the bounded difference inequality, though closely related. In fact, our result could be used as an intermediate step in proving the latter, but we note that this would not be the usual method (e.g. Boucheron al., 2013, use an "entropy" method instead), and the converse that we have to prove variant form of an existing concentration inequality to get concentration for our log-sum-exp statistics similar to how the same is required PAC-Bayesian proofs, where e.g. PAC-Bayes Bernstein inequalities also require modified proof techniques that mirror those used to prove usual Bernstein inequalities.
true. The fact
The usual bounded difference inequality cannot be used to prove Theorem 9, since it is not concentration bound. It also does not give the concentration we need in Theorem 10, since the FUSE statistics do not have the bounded difference property, only MMD; does; this is why our proof' cannot use "plug-in" concentration bound.
Theorem 11 (Bounded Difference Lemma). A function f has the bounded difference property there exist constants L3 < oc E [n]] such that
1f( 2k................ 2n) - f(2 2e,...,,n,)) S L
for any choices of 2i...,, 2ns 2/ and e [n].
For such a function and any independent random variables Zi...., Zn and t E R (subject to appropriate measurability restrictions)
1 L
L
Ecxp(t(f(Zz,.... Zn) Ef(Zz..... (,,))) s exp
t=1
31

---

Proof of Theorem 11. We introduce the Doob construction, defining
Dj This is martingale difference sequence with
7.. Zr] [Z] 7n) 7,. Ze-1)
D 2n) 18[ Zn).
It is shown by (for example) Wainwright (2019, Ch. 2.2, p.37) that D; lies in an interval of length at most Le by the bounded differences assumption. Thus, applying iterated expectation and Hoeffding's lemma for the MGF of bounded random variables,
Ee Zn) - (, Zn))) E Eexp
Dr 1
E
exp
Di
E (exp (ADn) 12,,..., Zn-i]
8=1
{8" (LD2L,
(
E
exp
Σ
De
exp
8=1
I exp
Σ
L
The MGF of 2MD can then be bounded using the following result, proved via the above.
Theorem 12. For bounded kernel k S E R and sample sizes m. n,
Eexp(((MMD2 Y) MMD S exp (122 1 m
(
Proof of Theorem 12. We show that MMD (ar, y) has the bounded differences property and then apply Theorem 11. Denote by ve for l E [rx] that the 8-th example in the sample is changed. Then
MM v) 3M0MMMM(B3 (x)e, .2)1
2
Σ
(k(1), - k((e, xz))
2 m
(k(
1i(a'e v;))
n(n 1)
mi
j=1
2
Σ |k(ze, 2;) - k(t'r,05))
2
|x( U₁) - k(0'e.
n(n2
mn
(E(N][16)
2
2 m
(n 1) +
nnn 1)
mn
8k6
A similar process for the sample gives bounds of 8k/m, so that MMD5² has the bounded differences property with
n
8Pc
81G
2 = 64
1
1 m
1 n.
+
Proof of Theorem 9. For the first lower bound, note
KL
KL
Ez EzSEEE (Z) Ez sup E, MMD?
sup L2 .
2MD?
FUSE
32

---

For the upper bound, note that
FUSUSED (Z) v log EzEEN
[AMMMDDE]]
Jensen
< log Ex Bz (cAMiNIE))
Independence of π from Z
< log (RRET
(e
(AMMD; +8A* (m +m--))
Theorem 12
-+-
= FUSEL +882 A
The lower bound on FUSE, is obtained by relaxing the supremum with p= π. The upper bounds come since the supremum over o M1 (K) KL(p. 7)) < oo of MMD² clearly greater than the KL-regularised version. Under the null hypothesis, MMD q) = 0 for every kernel (regardless of them being characteristic or not), so FUSE, O.
Proof of Theorem 10. For the upper bound,
FUSE, (2) =
log EKWw
AMMM;
|]
log 8 8-1
11-8 8 2 log (EZEENT (AMMDEE)
+
Markov
A
log EANNEZ e @MMMDe))
log Ō-1
Independence of x from Z
A
log ER E AMMDD +8A2 + (0m"""((m""" (1)))))))))))))
log 8-1
Theorem 12
(=
+ ( n1 m
log 0-
FUSE 2
For the lower bound, let p" be the value of achieving the supremum in the dual form of FUSE, (which we note is independent of the sample), so that
KL(P,T) mT)
KL(p, m)
FUSE, FUSE, (Z) sup Bp [MMD]]
sup
[MIM
KI.(p", x)
KI(p, mT)
Ep- [MMD]]
sup
E MMMD
A KI(P",
KL(Pp, m))
E,- [MD
Ep
MMD
X
E.- [MMD] MMD
MMD? K, (p.9)
MMD k. (Z).
Now the above is for fixed kernel Kn- independent of the data, so by Markov's inequality and Theorem 12, for any > 0 we find
K-- (Z) MMD k2 (p.4) - &MD
S1-5 - log Ez exp (s (MMMDD (p.9) MMD (2))) + - 5--log
|-
< 8
+ n
+ 2og8-
m
Optimising for yields x- /log(1/6)/ /8L/m 1/n) which gives the desired result.
33

---

E
Power Analysis
E.1
General Recipe for Power Analysis of Permutation Tests
The general outline for power analysis consists of the following: First we start with the Type II error probability. Then we attempt to upper bound by iteratively applying the following simple lemma to the different terms.
Monotonicity in High Probability. Let X, be e.v., such that S Y w.p. 2 1 - Then F(X 2 c) S P(Y 2 c) + 6. This result can be applied both when X S Y a.s. giving ó 0, or if Y = a is constant.
Iteratively applying this lemma gives P(Type II) I N6, and then we set NO = B.
As first step in the above process we will the following useful result (adapted from Kim et al., 2022) to convert from the random permutations we use in practice to the full set of permutation. This result shows that when B is taken sufficiently large (roughly U(a -2 1og(B-1))), the only changes to the final power results will be in constants multiplying a and B.
Theorem 13 (From Randomised to Deterministic Permutations). Suppose G = ".b.....9++1 consists of B uniformly drawn permatations from G. plus the identity permutation as gB+1. Then
P
T(Z)=
S quantile ((9 1-a,G
S P T(()) S quantile r(22) quantile
1-02.9
where - o: =
B+1 a:) +
log(2/8)
2B
We note that provided B 2 8a log(2/5), then 1 - ag S aa/2.
Proof. We note the D Wolffoitz inequality Dvoretzky et al. (1956); Massart (1990)
for empirical CDF F2 of n samples from original CDF F:
sup Fx (z) F(=)) 2t)
F(x))
S 2e 2nt
(12)
for every >>
The permutation CDF for a group 9 take the form
Fø(x)
1
Σ (7(
<x)
DEg
and given sample ō ........ (B) added to G),, the empirical CDF is
i..dd uniformly from 9 (this excludes the identity permutation
Fo(x) = 1 1 S x}
B
9EG
We can also write Fo(x) including the identity permutation gn+ 1, and note that Po (x)
Define the good event
log(2/6)
A= sup (al)FF(())))))))))))))))))) Fo(x)) S
2B
which holds with probability least 1 1 by Equation (12). Given A, have
4G
quantile (oantile-(gZ))) (gZ)= IR B+1
Σ
211
o}
I 9EG
9EG
< inffr R
1
Σ
Sr110 a}
B+1
9EG
34

---

B ++1
= i Fo(r) 2
(1 [1-a]]
B
B + 1
log 2/0)
Sinl
(1 a)) V
B
2B
quantile T(gZ) =
1-ag.geg
where we have defined a as above.
Overall we find PT qc) P(T S (GlA) P(AA) S P(T S 9) +
E.2 Variance of MMD
In proving our power results necessary to upper bound the variance of MMD
Theorem 14. For any kernel k upper bounded by K, if S m S en for 2 there exists universal constant C > 0 depending only c, such that
4 MMD
2
R²
VIMMD SC
12
n2
Proof. We define
0 Vx Xx ( y. (X,,
01 (y [XX,,
ii max (F (X, (X),
From well-known bound (based on Lee, 1990, Equation 2, p.38; see also Kim et al., 2022, Appendix Equation 59 Schrab al., 2023, Proposition 3).
2
1 + 1 )
VIMMD S
+
+
2
11
010
2
U11
2
i
n
where we used that n < < cn. and the result in red above, and the boundedness of the kernel for the final term. This gives the further bound
4 MMD k
VIMMD SC
n
n
since
010
varx (EX 11 X', YY,'"))
Ex (Ex // [x( X',
Ex
TEx:x...11((0 -0)))(())))) o(x)) -
Ex (0(X) - 1Q,11 - -
I Exx [lx(x) - me mel11) 1PPP
< 2x|lup mell
2x MMD2
similar result for dol, and the simple bound 01 < n
35

---

E.3
Proof of Theorem 2
Proof.
Define ag as in Theorem 13, noting that ag a/2 under the assumption 2 8a 22 (4g/3/)). From Theorem 13 we can consider the full permutation set as
Ppxq.0
(PSS;(() quantile UuiantileFUSE, (USE((02) 1-a,6
S SPxx
FUSE1(2) 2 quantile F FUSE + 3/22.
1-as.9
We also recall that from Theorem 5 when À = =n/KK,
quantile (o Cin(1 + loga
1-08,G
so that
CiK(1 + +lg
P
FUSE (Z) S quantile FUSE, (
< P pxxa
FUSE, (Z) S
1-ag.6
For any P. define
KL(
C1x(1 + logaa Gogga+loga?!
Sp MMD K, (p.9)
A
which substitute into
P pxg
FUSE (2) v
=
MMD K, (p.g)
KL T) - FUSE, (Z) 2 5,
P MMDD K, (p. 9) KL T) sup /'
MMD (2) - kL(D', 2
(2)
25,) S.
< P (MMD K. (p.9) 9) MMD (2) 2 sp))
V
MMD K, [Z)
=
53
pxg
C2
4xx 2
+ x2)
<
5
n
n
After substituting Sp. we used the dual form of FUSE, and the inequalities sup f(p) 2 f(p), Chebyshev's, s, and Theorem 14. This term upper bounded by B/2 we set
202
4k MMD
8
B
n2
We also note that for 6, x all non-negative, if x² x² ar b is equivalent to 2
a²
+ 26, then x² > az 6. This works because
2
2
+
a
4
+b
by taking the positive root, and
2
2
a²
a2 +b ab
b
+
b
2
4
2
using Young's inequality 2AB < A B
Combining the above the Type II error rate is controlled by 3 provided any of the following statements are true for any a (with each new result implying the former):
MMD3 k, (p.9) KL(p.T)
C1a(1 + log -0
2C₂
4n
2
R²
+
n2
36

---

<L(p,*)
+ill++ogaa
802x
V2C2R
MMD K2 k,(0,9)> >
+
+
MMD +
A
n
n3
nVB
MMD K2 (p,9) > 2KT(p,,T) A
20in(1 + log
8C
2/202k
+
+
+
n
nB
nyB
Cyn
MMD K, (p.9)
+ log
+ kL(p
n
a
where we used that v + S x + vD. the result above, and À = en/K.
E.4 Proof of Theorem
The proof of this statement proceeds similarly to the proof of Theorem 2. Using Theorem 5 with cn and Theorem 13 we find that
P Ppx.,6
FUSEN
& quantile FUSEN(O2)) 1-a,G
Ci(1 +lg log a )
P pxq FUSEN(Z)
+ 8/2.
n
For any P such that KL[p, n) < 20 we define
Tp = MMD K2
1 (I Cin(1+logee loga
Sp = T A
We assumed that depending only on m/n E [1, c]. and (since MMD? 2 is strictly non-negate non-negative, unlike MMD2 which can be negative).
I en for some 2 1. Based this, note that N' /2/CCT for Ci
MMD
Ci ERup [MMD]] = -T
Ep
(13)
Z))
Now we introduce these definitions to bound
C1 + log
FUSEN(2)
n
1 Tp <K((PT) FUSEE 2 So
P
MMD ZZ)
P
Tp T KL T) sup P'
EnnN'
(L(dd xx)
S.
Na
MMD (Z)
<
Tp Ex-p
2 Sp
sup 2 2((
(x)
MMD
MMD 2
MMD (Z)
P
T Ekup
Sp
Na(Z)
(Z)
(e
MMD
MMD MMD (Z)
Tp
ExuU
+ +Epup
2 SSp
[z)
(x
MMD
MMD MMD
P
Tg Ekpup
+ ERNP
> SSp
(2(
(2(Z)
37

---

MMD - MMD (Z)
P
EReP
Sp
by Equation (13)
(z)
MMD MMD Z
P
EkEu
2 Sp
8 S |
(2)
MMD MMD Z
P
EREP
Sp
|ar| convex, Jensen
(Z)
MMD (M)
Exuu
2 Sp
N positive
(Z)
1
MMD K MMD (2)
Ez Bkmp
NA positive, Markov
Sp
(z
1
|MMM MMMD
Ez EyE
1
Cauchy-Schwar
Sp
Nx(Z)
Thus the type II error will be controlled by /3 if for any P
[MMD] (MM)((2))
S,
Ez Ekmp
Bz EkOO
3
(x(2)
Provided there is a > 0 with
1
E Epxq
c
(Z)
for all k, this reduces to the condition
loga-
KL π
MMD (p. 9) > C25
Eg
pxx
MMD (Z)
B
n
n
Applying Theorem 14, the proof is completed in essentially the same way as the result for FUSE, (with slightly different 3 dependence).
38


Reviews:
[{"review_id": "y9R9tlRt40", "reviewer": "Reviewer_1tja", "summary": "This paper proposes a new statistic that can incorporate with the permutation test where we can learn features of data in an unsupervised way. From the perspective of testing, this paper contributes a new idea and paves a new way to perform two-sample testing without data splitting. If we can safely use all data to find a proper kernel, the test power will increase for sure. Theorems and proofs also verify the proposed methods.", "questions": "Please address the points in Weakness. The presentation can be improved to make this paper even better.", "limitations": "N/A", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "1. This paper focuses on an important problem: two-sample testing, which will be very important when generators are like humans nowadays.\n\n2. The selected research direction, testing without data splitting, is very important. As demonstrated in summary, a proper kernel selection in this direction can directly boost the test power.\n\n3. Experiments include simple data and complex data (Galaxy MNIST and CIFAR), verifying the effectiveness of the proposed statistics.", "weaknesses": "1. The presentation can be improved a lot. The major issue is the lack of motivation for many choices. For example, what is the motivation to consider a mean kernel? what is the motivation to have this kind of design: log( E( exp( ) ) )? Can we consider more possibilities? The finding of this paper is exciting, however, it looks like a rush version. A revised version with a better presentation is required during the rebuttal.\n\n2. Section 3 is a little bit long. The authors can consider introducing the theorem in the preliminary (as it is not proposed in this paper). Or the authors can remove the permutation test from Section 2. You can also consider merging Sections 2 and 3, making demonstrations more compact.\n\n3. After removing the necessary parts in Sections 2 and 3, more experimental results can be put into the main body. For example, CIFAR results look very promising and should be moved into the main body.\n\n4. In line 115, there is a notation typo.\n\n5. Marks are recommended in Figure 1. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*[Comment to all reviewers (Author Rebuttal) posted above]*\n\nThank you for your valuable feedback, for highlighting the strengths of our paper, as well as ways in which we can present and motivate our ideas more clearly. We will include the above discussions into the body of the paper.\n\n&nbsp;\n\n> what is the motivation to consider a mean kernel?\n\nThe mean kernel simply arises naturally when considering distributions over kernels: since the squared MMD is linear, the expectation of it with respect to the kernel is equivalent to a single MMD^2 with a mean kernel (c.f. discussion l.238-243). When considering a fixed finite set of kernels of size $|K|$ with uniform prior as in our experiments, the equation on l.243 gives\n\n$$\n\\widehat{\\mathrm{FUSE}}_1(Z) = \\sup^\\rho\\ \\mathbb{E}^\\rho[\\widehat{\\mathrm{MMD}}^2(X,Y; k)]  - \\mathrm{KL}(\\rho,\\pi) / \\lambda\n$$\n($\\rho$ should be a subscript but this syntax does not work)\n\n$$\n\\widehat{\\mathrm{FUSE}}_1(Z) = \\sup_w\\ \\sum_i w_i\\widehat{\\mathrm{MMD}}^2(X,Y; k_i)  - \\sum_i w_i \\log(w_i |K|) / \\lambda\n$$\n\nwhich shows that the $\\widehat{\\mathrm{FUSE}}_1$ statistic is just optimising the weightings of these kernels. \n\nWe also illustrate in Appendix B that under certain choices (e.g. Gaussian kernel with a Gamma prior), the mean kernel can be expressed in closed form and corresponds to some commonly-used kernels (e.g. rational quadratic). This can theoretically enable continuous optimisation of the parameters of such mean kernels, while all previous methods required a discretisation of the parameter space.\n\n\n&nbsp;\n\n> what is the motivation to have this kind of design: log( E( exp( ) ) )? Can we consider more possibilities?\n\nUsing the maximum directly is possible but would lead to a Bonferroni-type $\\log(|K|)$ term in the power, and be limited to a finite number of “base” kernels. Also, only information from the single maximising “base” kernel can be considered at a time. For these reasons we use a “soft” maximum, which avoids the Bonferroni correction when more than one of the kernels is good, and considers information from every kernel simultaneously.\n\nOther soft maxima (see eq. 3) could certainly be considered, but the logsumexp variant we use is by far the most common choice. This is because it makes obtaining exponential concentration inequalities (by bounding the MGFs; see Theorem 10 in Appendix D) possible, and because the dual formulation (eq. 2 and l.243) allows us to derive power results in terms of MMD directly instead of in terms of the FUSE statistic.\n\n&nbsp;\n\n> The authors can consider introducing the theorem in the preliminary (as it is not proposed in this paper). Or the authors can remove the permutation test from Section 2. You can also consider merging Sections 2 and 3, making demonstrations more compact.\n\nWe will work to remove unnecessary redundancy in these sections.\n\n> After removing the necessary parts in Sections 2 and 3, more experimental results can be put into the main body. For example, CIFAR results look very promising and should be moved into the main body.\n\nThank you for highlighting the relevancy of this experiment - we will include it in the main body.\n\n> In line 115, there is a notation typo.\n\nWe will add a definition for the notation $X =^d Y$ (i.e. $X$ and $Y$ follow the same distribution).\n\n> Marks are recommended in Figure 1.\n\nThanks for pointing this out, we will add this.\n"}, {"review_id": "5NFyhenseI", "reviewer": "Reviewer_xB7K", "summary": "The paper studies the question of choice of critical values for the MMD test. The authors introduce a new MMD-based test that allows data-driven critical values based on permutation test, without the need to train a new kernel for every permutation. The main advantage of this new method is that it does not require sample splitting and the whole sample can be utilized for the computation of the test value.\n\npros:\n- Experiments show improvements in some cases compared to sample-splitting methods.\n- The authors provide plenty of theoretical results in the appendix, including concentration results for the test both under null and alternative.\n\ncons:\n- The analysis is very conservative. At no point we can state that the distribution of the permuted test conditional on the observed data approximates that of the original test. Theorem 1 in particular is an upper bound, so there is no guarantees that the type I error of the test will be close to the desired level alpha. It is not clear how crude this upper bound is. I suggest this limitation should be emphasised in the text below.\n- I think theoretical analysis can be simplified. For example, proof of Theorem 6 does not have to reproduce Vershynin and Rudelson's proof, it is sufficient to integrate their bound. Also, it is not clear to me why it is necessary to include a proof of Bounded Differences Inequality in the appendix. Instead, one can refer to Lugosi et al Concentration Inequalities, Theorem 6.7.\n- There is no dependence of prior on the data in the experiments, please correct me if I'm wrong.\n\nother comments:\n\nline 174 m+ m -> n + m\n\nline 222 inconsistent notation MMD_k or MMD(.; k)\n\nline 829, display below: not sure why t appeared in second line and why it disappeared in the third line\n\nline 747 FUSE depends on lambda, what depends on t then?\n\nline 872 sup_y -> sup_rho?\n\nline 873 what is N?\n\nSerious concerns:\n\n- Section E.3 proof of Theorem 2 (which in my understanding one of the main theoretical contributions of the paper). Could the authors please elaborate on what happens below line 926 in detail? The sup over rho disappears in line 2. The \"object\" S_rho appears to be random, depending on the observed data Z, and it appears in the final bound thanks to the Markov inequality. \n- I can't find proof of Theorem 3 in the appendix with Ctrl + F\n\nTo my best understanding if there are mistakes above section E.3 they should be fixable.\n\n### My rating is conditional on whether the authors can fix these two serious concerns. Otherwise, the paper must be rejected.\n", "questions": "-", "limitations": "-", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "-", "weaknesses": "-", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*[Comment to all reviewers (Author Rebuttal) posted above]*\n\nThank you for your thorough feedback, positive evaluation of our work, and for pointing out ways in which we can more clearly communicate our contribution. We also thank you for pointing out the small error in the proof of Th 2 due to incorrect ordering of steps, the fix to which we give below.\n\n> The analysis [...] \n\nThe statement of Th 1 which states only that the level is smaller than $\\alpha$ appears to be conservative, but in fact we can make stronger statements about the test arising from this theorem. Specifically, assuming distinct data points, the level can be shown to be **exactly** equal to $\\lfloor (B +1) \\alpha\\rfloor / (B +1)$ (this result follows from Prop 2 of H&G). Thus the bound is extremely tight, and in many cases the equality is achieved (e.g. if $\\alpha=0.05$ and $B+1$ is a multiple of $\\alpha^{-1}=20$). Even the assumption of distinct data points can be relaxed (Proposition 3 of Hemerik and Goeman) using a tie-breaking strategy (randomly choosing an ordering of the equal points) while preserving the exact level $\\lfloor (B +1) \\alpha\\rfloor / (B +1)$. This is an important point which we will add to the paper.\n\n> Th 6 V&R\n\nTh 6 is actually derived from an intermediate result (not a full theorem) in V&R's paper, which they do not derive with explicit constants. In order to provide the concentration results (Th 5) with the (surprisingly small) constants, we need these, so we reproduce this part of their proof with explicit constants.\n\n> Bounded Diff. Ineq. Lugosi\n\nThe “bounded difference lemma” (Th 11) we give is not the same as the bounded difference inequality, though it is closely related. In fact, our result could be used as an intermediate step in proving the latter, but we note that this would not be the usual method (e.g. Lugosi et al. use an “entropy” method instead).\n\nThe usual bounded difference inequality does **not** give the concentration we need, since the FUSE statistics do not have the bounded difference property, only $\\widehat{\\mathrm{MMD}}^2$ does. Our “bounded difference lemma” is an MGF bound and leads to the $\\widehat{\\mathrm{MMD}}^2$ MGF bound of Theorem 12. This is applied to prove Theorems 9 and 10, since $\\widehat{\\mathrm{FUSE}}_1$ takes the approximate form of an MGF. The fact that we have to prove a variant form of an existing concentration inequality to get concentration for our logsumexp statistics is similar to how the same is required in PAC-Bayesian proofs, where e.g. PAC-Bayes Bernstein inequalities also require modified proof techniques that mirror those used to prove the usual Bernstein inequalities. \n\n> prior dependence\n\nThe prior used in the experiments uses data in a permutation-independent way to choose bandwidths for a fixed set of kernels (cf l.317-324) as it uses the set of inter-sample distances $\\|z-z'\\|$ for $z,z'\\in Z$ (l.320) for bandwidth selection. The prior is a uniform distribution over a support chosen using the data.\n\n> l.174, 222, 829, 872\n\nWe thank the reviewer for pointing these typos out, which are now fixed throughout the paper.\n\n> l.747 \n\nWe will clarify this in the final version. FUSE depends on $\\lambda$ and the same $\\lambda$ appears on the RHS of the equation l.745. For the bound on -FUSE of l.746, FUSE depends on $\\lambda$ but the RHS holds for any $t$ in the range specified on l.747, in particular the parameter $t$ can be optimised to match the orders of the two terms on the RHS which is not possible for the bound on l.745.\n\n> l.873 \n\nWe will fix this, here 1/N = 1/n + 1/m.\n\n> Section E.3 [...] \n\nThank you for pointing this out, you are correct, as currently written $S_\\rho$ depends on Z, when it should not. The problem here is that as presented, the bound from Theorem 5 (l. 929) is used **after** Markov, where instead it should be used **before**. This can easily be fixed by redefining $S_\\rho$, replacing this quantile term by a data-independent upper bound on it. The same issue appears with the same fix in the proof of Th 3.\n\nFor clarity, we present the details of this modified proof below along with additional details to clarify what is happening below 926:\n\nFrom Th 5 with $\\lambda = cn / \\kappa$, we have \n$\\mathrm{quantile}\\ \\widehat{\\mathrm{FUSE}}(\\sigma Z) \\leq C_1 \\kappa (1+\\log(1/\\alpha))/n$\nfor some positive constant $C_1$.\nWe now define $S_\\rho$ using this quantile upper bound, so that $S_\\rho$ is not data-dependent, we let\n$$\nS_\\rho := \\mathrm{MMD}^2(p,q;K_\\rho) - \\mathrm{KL}(\\rho,\\pi) / \\lambda - C_1 \\kappa (1+\\log(1/\\alpha))/n.\n$$\n\nFrom l.926 onwards:\n\nUnder the alternative and using Th 5,  we have\n$$\n\\mathbb{P}(\\widehat{\\mathrm{FUSE}}(Z) \\leq \\mathrm{quantile}\\ \\widehat{\\mathrm{FUSE}}(\\sigma Z))\n\\ \\leq\\ \n\\mathbb{P}(\\widehat{\\mathrm{FUSE}}(Z) \\leq C_1 \\kappa (1+\\log(1/\\alpha))/n)\n$$\n\nNow, we add $S_\\rho$ to both sides and cancel out the quantile upper bound to obtain\n\n$$\n\\mathbb{P}(\\widehat{\\mathrm{FUSE}}(Z) \\leq C_1 \\kappa (1+\\log(1/\\alpha))/n) = \n\\mathbb{P}( \\mathrm{MMD}^2(p,q;K_\\rho) - \\mathrm{KL}(\\rho,\\pi) / \\lambda - \\widehat{\\mathrm{FUSE}}(Z)\\geq S_\\rho).\n$$\n\nContinuing from the second line after l.926 the reasoning continues as given below:\n\nThe third line of the equations l.926 holds by definition of $\\widehat{\\mathrm{FUSE}}_1(Z)$ (note that there is a typo and the MMD term in the supremum over $\\rho'$ should depend on $\\rho'$ rather than on $\\rho$).\n\nThe fourth line holds since the supremum over all $\\rho'$ is greater than when it is evaluated at the specific $\\rho$.\nWe note there is no supremum over $\\rho$ since the above applies for any fixed $\\rho$.\n\nThe fifth line (which should be an inequality) holds by Markov/Chebyshev's inequality (valid since $S_\\rho$ is now data-independent), and the last line holds by Th 14.\n\nThe rest of the proof is completed as given.\n\n> can't find proof Th 3\n\nThe proof of Th 3 is presented in Appendix E.4 directly after the proof of Theorem 2. We will rename this section more appropriately."}, {"review_id": "SBglftDNK8", "reviewer": "Reviewer_jkkz", "summary": "This paper looks into the problem of permutation based kernel two-sample testing. The paper is motivated by two main challenges: \n\n1. The first one being the fact that selecting kernel hyper-parameters through standard data splitting often reduces the statistical power due to using less data than we actually have.\n2. The second challenge being that if we don't select a data specific hyperparameter for the test, a poor kernel choice will also lead to a decrease in statistical power.\n\nTo tackle these problems, the authors proposed the MMD-FUSE method that can select kernels adapted to the data without data splitting. They first restate a result from Hemerik and Goeman Theorem 2 to justify/emphasise that any permutation invariant representation/function of the data can be used a statistic that have controlled type 1 error rate. In addition justifying the adequacy of median heuristics. \n\nThe second contribution is that they proposed to combine multiple MMD via a set of kernels, and as such optimise the test power.\n", "questions": "Although you have this prior over a set of kernels which this set could potentially be infinite, in practice you would sample from this prior to compute the test statistic right? How would your approach compare to standard Bongerroni correction technique or its extension weighted bonferroni correction? Would be interesting to hear about your comments on this.", "limitations": "No.", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The problem is well motivated as the trade off between data splitting to learn optimal kernel v.s. not splitting the data but selecting some heuristic kernel has been a long standing problem in the community. This authors explained their arguments very clearly. In addition, not only did they justify their method by showcasing the optimal MMD separation rate (Typo in line 290 btw), I appreciate they included a discussion with computationally faster sub-optimal tests to highlight between the trade off of test power and computational efficiency.", "weaknesses": "The authors have discussed the weakness in their conclusion section so I don't think I have much to add. There is some recent work on not using permutation test at all to do two sample test, such as the work of Shekhar et al. 2022. I understand it is not necessary to compare the two types of approach but might be also good to mention non-permutation based approach as a side note to complete your already-detailed background section on testing?\n\n\n---\n\nShekhar et al. 2022 \"A Permutation-free Kernel Two-Sample Test\" arXiv:2211.14908 ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*[Comment to all reviewers (Author Rebuttal) posted above]*\n\nThank you for your generous praise, and comments. We will incorporate answers to the following into our revised work.\n\n&nbsp;\n\n> There is some recent work on not using permutation test at all to do two sample test, such as the work of Shekhar et al. 2022. I understand it is not necessary to compare the two types of approach but might be also good to mention non-permutation based approach as a side note to complete your already-detailed background section on testing?\n\nWe briefly mentioned this work in our Background section on line 157 as part of the 'studentised asymptotic tests' as opposed to ‘permutation-based non-asymptotic tests’. We will expand our discussion of this interesting alternative to constructing a two-sample test with advantages (still quadratic but computationally more efficient as no permutation required) and disadvantages (inevitable loss of power due to the fact that the kernel matrix cannot be used entirely, otherwise asymptotic normality is broken), which is the usual tradeoff between power and computational efficiency. This could also be a topic for investigation in future work.\n\n&nbsp;\n\n> Although you have this prior over a set of kernels which this set could potentially be infinite, in practice you would sample from this prior to compute the test statistic right? \n\nThere are three possible settings. \n\nFirstly, the prior can have support over a finite set of kernels, in which case the expectation can easily be evaluated as an average. This is the case in our experiments which directly compare against other similar tests (e.g. MMDAgg). \n\nSecondly, in some cases the prior can have support over an infinite set of kernels but the expectation might still admit a known closed form which can easily be evaluated. This is for example the case when using FUSE1 with a Gaussian kernel and a Gamma prior on its bandwidth parameter, as shown in Appendix B the resulting expectation (i.e. the mean kernel) is the commonly-used rational quadratic kernel which can be implemented in practice.\n\nThirdly, the prior can have support over an infinite set of kernels and the expectation cannot be expressed in a known closed form. As mentioned by the reviewer, in this case, it would certainly be sensible to sample from the prior to produce a new prior with finite support, for which the expectation becomes a simple weighted average. This would still be very different from performing multiple testing with a (weighted) Bonferroni correction of the test levels (we get a different quantile for each kernel), since we would still be using a 'soft maximum' via FUSE and thus be avoiding multiple testing (we have a single quantile for our FUSE statistic which combines many MMD values with different kernels). Note that empirically FUSE would greatly outperform the Bonferroni multiple testing approach, as it matches the performance of the multiple testing approach MMDAgg which itself greatly outperforms the Bonferroni multiple testing correction (both theoretically and empirically).\n\n\n> How would your approach compare to standard Bonferroni correction technique or its extension weighted Bonferroni correction? Would be interesting to hear about your comments on this.\n\nStandard Bonferroni correction is needed when we do multiple testing with different kernels. However, this leads to a term of $O(\\sqrt{\\log(|K|)})$ in the power.\nIn the worst case for our method, where only a single kernel gives rise to a large normalised MMD and the rest give approximately zero normalised MMD, we would incur such a penalty; but in the case that several kernels do so the penalty would be considerably smaller. This is what is empirically observed. Further, this makes testing with very large or infinite sets of kernels possible (though not always computationally practical), since otherwise $|K| \\to \\infty$ leads to zero power."}, {"review_id": "aKQpyYKo05", "reviewer": "Reviewer_fFeS", "summary": "[Update: After intensive discussion with the authors, I changed my score from 6 to 7. I further increase the score for \"Contribution\" from 2 to 3.]\n\nThe paper introduces two new test statistics for permutation-based two-sample tests that are related to the MMD -- called FUSE_N and FUSE_1. These are motivated by selecting/combining good kernels for an MMD-based two sample test *without splitting* the data.\nThe authors theoretically show that FUSE_1 corresponds to a (regularized) supremum of the MMD over the possible kernel combinations. FUSE_N, which empirically performs much stronger, is derived from FUSE_1 but where the kernels are weighted by their normalized (squared) MMD estimates instead of simply by their (squared) MMD estimates. There is no theoretical justification for using FUSE_N.\n\nThe authors provide a theoretical power analysis of the proposed tests. Furthermore they run experiments that show their test has competitive power against a recent SOTA MMDAgg, while having a constant speed-up. The code is provided in a well-structured repository, such that it can be easily reproduced or the community can build on it.\n\nThe paper also gives some general insights into what test selection strategies are generally possible when using a permutation test. Whilst this might not be very new in itself, having a clear presentation of the general thoughts in one place, might be very useful for scientist entering the field.", "questions": "Please also see my points in the weakness section.\n### Questions I would like to discuss / understand:\n- What is the motivation for FUSE_N (except that it works well on your experiments)?\n- In Section A.4. you discuss the time-complexity relative to MMDAgg:\n  - The difference is a factor of 2, so I do not think that the $\\mathcal{O}$ notation is adequate here. \n  - I also experienced that computing the kernel matrix is quite costly, compared to the permutations. But this only needs to be done once in both methods. Could it be that this difference is only visible because you used a very large number of permutations (20,000)?\n- l. 143 \"without incurring Bonferrony-type multiple testing penalties\": I understand that your method does not have such a penalty, but what exactly is it that leads to it?\n- What's the \"N\" or \"1\" in the naming of FUSE_ standing for?\n\n\n### Questions / Remarks that do not require a response:\n- l.57 \"Our unsupervised feature extraction method is extemely powerful\": I do not see any support for this statement. I agree that it is very general, but whether it works well, I do not see evidence in the paper.\n- l.108f: Note that Kübler et al (AutoML Two-Sample Test) show in App. B.1 that the asymptotically optimal kernel for a fixed problem is indeed 1-dimensional.\n- l. 116: I do not think that permuting the samples is exactly the same as sampling from 1/2 (p+q). In the permutation there are always exactly half the samples still from p and half from q. Whilst drawing from 1/2(p+q) can by chance (and most likely will) result unbalanced.", "limitations": "nothing specific", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The delivered experiments are done very thoroughly and structured and the code is provided in a high quality.\n- The paper is very well written and clarifies important (although not really new) aspects of permutation-based tests in an accessible way.\n- The proposed test convinces in terms of power and runtime -- (although I am not 100% convinced by the speed-up over MMDAgg yet).\n- Originality and significance: Two-sample testing is an ongoing research area and improvements and new ideas are published at NeurIPS and similar conferences regularly. The community seems nevertheless relatively small. The test statistic seems new, although its motivation is not really clear.", "weaknesses": "- The motivation for the proposed test statistic is not clear enough for me. FUSE_1 has somewhat a motivation (Sec. 4.1.) but:\n  - it does not perform well and also the motivation does not arise from test power considerations.\n  - It is well-known that selecting the kernel by maximizing the MMD is not a theoretically justified strategy (not scale invariant for example).\n- Sutherland et al (2017) give a criterion for optimizing the kernel in terms of asymptotic power, which results in optimizing a Signal-to-noise ratio. The normalized statistic FUSE_N seems to go in this direction, but there is no motivation for the normalization given.\n- Generally I am not really understanding the starting point for this paper. What motivated you to do this work and what where you trying to solve? In particular what is the similarity/difference to MMDAgg? \n- The test statistic has a parameter $\\lambda$. For the theoretical results, $\\lambda$ depends on the sample size. However, in the experiments (as far as I understood) $\\lambda=1$ irrespectively of the sample size. How was this value determined and where is it discussed? And what is the recommended way to do this in practice?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Reply to reviewer fFeS Part 1**\n\nThank you for your valuable feedback and questions which will help us improve the presentation of our ideas.\n\n\n## Permutation tests\n> The paper is very well written and clarifies important (although not really new) aspects of permutation-based tests in an accessible way.\n\nWe are glad you found the paper to be well written, and that it clarifies important aspects of permutation-based tests. We would like to emphasise that although the result of Hemerik and Goeman is not a new one, the consequences of that result appear not to have been previously fully understood in the field. The simplicity and generality of our proposal to use permutation-invariant tuning of the statistic might lead one to expect that this idea has been used before, but to our best knowledge it has not. This is underlined by the fact that the median heuristic has been widely used without a formal justification, when one follows so straightforwardly from Theorem 1; or by the fact that the well-developed techniques of unsupervised and self-supervised learning have not been combined with two-sample permutation testing before, again despite this potential usage being a simple mathematical corollary of Theorem 1. We believe this latter fact alone has the potential to be highly impactful in this field.\n\n\n## Motivation\n> The motivation for the proposed test statistic is not clear enough for me.\n\n> Sutherland et al (2017) give a criterion for optimising the kernel in terms of asymptotic power ... FUSE_N seems to go in this direction, but there is no motivation for the normalisation given.\n\n> Generally I am not really understanding the starting point for this paper. What motivated you to do this work and what where you trying to solve? In particular what is the similarity/difference to MMDAgg?\n\nPlease see the overall discussion and motivation in the response to all reviewers.\n\n\n\n\n## Time complexity\n\n> I also experienced that computing the kernel matrix is quite costly, compared to the permutations. But this only needs to be done once in both methods. Could it be that this difference is only visible because you used a very large number of permutations (20,000)? \n\nUsing our code in Jax with a GPU, we find that computing the permuted MMD values is significantly more costly than computing the Gaussian kernel matrix (and this even for only 11 permutations). This explains why we observe that MMD-FUSE *always* runs twice as fast as MMDAgg.\n\n1)\n- Sample size $m = n = 100$\n- Dimension $d = 100$\n- Compute kernel matrix: 3.8 ms\n- Given kernel matrix, compute MMD for $B+1$ permutations\n- - $B = 10$: 35 ms\n- - $B = 100$: 65 ms\n- - $B = 1000$: 573 ms\n- - $B = 2000$: 983 ms\n\n2)\n- Sample size $m = n = 500$\n- Dimension $d = 100$\n- Compute kernel matrix: 3.82 ms\n- Given kernel matrix, compute MMD for $B+1$ permutations\n- - $B = 10$: 22 ms\n- - $B = 100$: 278 ms\n- - $B = 1000$: 2110 ms\n- - $B = 2000$: 4250 ms\n\n3)\n- Sample size $m = n = 1000$\n- Dimension $d = 100$\n- Compute kernel matrix: 4.87 ms\n- Given kernel matrix, compute MMD for $B+1$ permutations\n- - $B = 10$: 71 ms\n- - $B = 100$: 555 ms\n- - $B = 1000$: 4240 ms\n- - $B = 2000$: 8490 ms\n\n4)\n- Sample size $m = n = 2500$\n- Dimension $d = 100$\n- Compute kernel matrix: 29.6 ms\n- Given kernel matrix, compute MMD for $B+1$ permutations\n- - $B = 10$: 161 ms\n- - $B = 100$: 1170 ms\n- - $B = 1000$: 10800 ms\n\n\n\n\n\n\n> In Section A.4. you discuss the time-complexity relative to MMDAgg: \n> The difference is a factor of 2, so I do not think that the $O$ notation is adequate here.\n\nAgreed, this will be clarified in the final version.\n\n\n\n\n\n\n## Bonferroni\n\n> l. 143 \"without incurring Bonferroni-type multiple testing penalties\"\n\nSuch a penalty usually arises through multiple testing (where a correction is needed to ensure the correct threshold for all of the tests). More closely to our setup, it could also arise when looking at the concentration of a maximum of sub-Gaussian variables; specifically a term of $O(\\sqrt{\\log(|K|)})$ would be added when considering the maximum of multiple MMD values. This term would be carried over into the power expression, giving rise to the same penalty there as would arise in standard multiple testing. In the worst case for our method, where only a single kernel gives rise to a large normalised MMD and the rest give approximately zero normalised MMD, we would incur such a penalty; but in the case that several kernels do so the penalty would be considerably smaller. This makes testing with very large or infinite sets of kernels possible (though not always computationally practical).\n\n\n\n## Miscellanea\n\n> $\\lambda=1$ ?\n\nIn the implementation, the parameter $\\lambda$ is set to $\\lambda = \\sqrt{n(n-1)}$ (see line 222 of mmdfuse.py) which is chosen so that the two terms on the RHS of the FUSE bound in Theorem 5 are of the same order. We chose to define $\\lambda$ only in terms of the sample size (ignoring constants). This value of $\\lambda$ is of the order $n$ which is used to derive the power results l.929. We will include this explanation in Appendix A.2 \"Test parameters\". \n\nThe confusion with $\\lambda=1$ may have arisen from the fact that in our code we defined lambda = sqrt(m+n) * lambda_multiplier and have lambda_multiplier as a parameter with default value 1.\n\n> What's the \"N\" or \"1\" in the naming of FUSE_ standing for?\n\nThe N for FUSE_N is not a parameter, it simply stands for 'Normalised'. The unnormalised version is referred to as FUSE_1 as it can be thought of as FUSE_N with the normaliser being equal to 1.\n\n> l.57 \"Our unsupervised feature extraction method is extremely powerful\"\n\nWe believe the method has the potential to be extremely powerful, particularly when applied to large-scale and high-dimensional data, but we will clarify that further evidence is needed to demonstrate this conclusively.\n\n> l.108f: Kübler et al show [...]\n\nThank you for pointing this out, we will cite this specific result."}]

Author rebuttal:
# Comment to all reviewers

We warmly thank all reviewers for their time and detailed commentary on our work. We are highly encouraged by the positive evaluations of all reviewers: **reviewer 1tja** points out that our FUSE method *'paves a new way to perform two-sample testing without data splitting'*; **reviewer fFeS** that *'the delivered experiments are done very thoroughly and structured and the code is provided in a high quality*'; and **reviewer xB7K** that we prove *'concentration results for the test both under null and alternative'* which as noted by **reviewer jkkz** allows us to *'justify [our] method by showcasing the optimal MMD separation rate'*.

We appreciate the insights and feedback provided which can greatly improve the presentation of our ideas. Individual answers to reviewer questions are given below, and will be incorporated into the paper. We hope these address any remaining concerns raised by the reviewers, and if so, that they would kindly consider upgrading their evaluation scores.


# Additional Motivation for our proposed statistics and work
This is particularly relevant to reviewer fFeS.
We will add the following additional simple motivation for FUSE (different from the one presented in Section 4.1) to our work.

Say we are interested in two-sample testing, and know the MMD is a useful kernel measure in that setting, so using all the data available we decide to compute some MMD values 
$$
\widehat{\mathrm{MMD}}_1,\ \dots\ ,\widehat{\mathrm{MMD}}_L
$$
for various kernels $k_1,\dots,k_L$ (finitely many for simplicity). A natural question is then 'What can we do with these values?' One possibility is to perform multiple testing as done in the case of MMDAgg. However, an even simpler and more intuitive answer would be to simply take the maximum of those values 
$$
\max_i \widehat{\mathrm{MMD}}_i
$$
since after all the aim is to detect differences between the distributions (if they exist). 

Now, there are two issues. 

Firstly, this would lead to a Bonferroni-type $\log(|K|)$ term in the power (see discussion below), and be limited to a finite number of “base” kernels. Also, only information from the single maximising “base” kernel can be considered at a time. For these reasons we use a “soft” maximum, which avoids the Bonferroni correction when more than one of the kernels is good, and considers information from every kernel simultaneously. Other soft maxima (see eq. 3) could certainly be considered, but the logsumexp variant we use is by far the most common choice. (see also discussion in response to Reviewer 1tja).

The second issue is that, as you point out, the MMD values might have different scales and hence cannot be compared to each other meaningfully. Simply requiring that the kernels integrate to one is not enough, as the MMD estimates with different kernels can have varying variances which need to be accounted for. For this reason, in order to be able to meaningfully compare MMD values between each other, these need to be normalised before the maximum is taken. FUSE1 is a first step towards the idea of using soft maxima, but it does not solve the scaling problem, so FUSE_N is effectively a “studentised” variation, dividing through by a variance-like term, which is a common approach as in Sutherland et al. (and others, see l.157-158).

The specific form of the normalizer is motivated by the following. In order to make our statistic perform well we would like its null distribution to be sub-Gaussian-like (i.e. sub-Gaussian for optimal settings of lambda). From theorem 7, normalising by a term at least as big as $\bar{U}$ will achieve this, but this term is not permutation invariant and so would lead to large additional computation. We therefore replace it with a permutation-invariant upper bound. This gives an overall statistic FUSE_N which can be efficiently computed, but has tight null concentration leading to good power.


### Motivation versus MMDAgg

MMDAgg is a different way to think about combining multiple kernels and MMD values, but it relies on a framework based on multiple testing. 
By contrast, our proposed FUSE method avoids multiple testing: a single statistic and quantile are used. 

This can be beneficial in the case where the number of kernels considered increases (is large).
In that setting, the multiple testing approach MMDAgg combines more and more kernels, the level needs to be corrected differently depending on the number of kernels, and it is not theoretically guaranteed how the power of MMDAgg behaves in that setting (i.e. it could maybe go to zero). 
We do not suffer from such issues with FUSE as even when increasing the number of kernels we still have only one statistic and quantile. 
The FUSE statistic is even defined in the limit of an infinite number of kernels (continuous/uncountable collection of kernels) by considering distributions on the space of kernels, which is clearly not the case for MMDAgg (only defined for discrete collection of kernels). 
Moreover, while the MMDAgg approach is only useful for hypothesis testing, having a quantity like FUSE combining multiple kernel-based measures of distance with exponential concentration bounds could be of interest in a wide range of applications.




Meta-review: Reviewers agree that the paper significantly contributes to an important problem and includes convincing experiments. 

During the rebuttal and discussion period, the authors undertake to improve the initial manuscript by including many clarifications, notably concerning the motivations of the proposed approach, the theoretical results, the proofs, and extended numerical results. It is essential to carefully include all of these in the camera-ready version of the paper.
Decision: Accept (spotlight)