Kernel-Based Tests for Likelihood-Free Hypothesis Testing
Authors: Patrik Robert Gerber
Tianze Jiang
Yury Polyanskiy
Rui Sun
Venue: NeurIPS 2023 poster (2023)
Keywords: Kernel methods
Maximum mean discrepancy
Likelihood-free inference
Hypothesis testing
Minimax statistics

Abstract: Given $n$ observations from two balanced classes, consider the task of labeling an additional $m$ inputs that are known to all belong to \emph{one} of the two classes. 
Special cases of this problem are well-known: with complete
knowledge of class distributions ($n=\infty$) the
problem is solved optimally by the likelihood-ratio test; when
$m=1$ it corresponds to binary classification; and when $m\approx n$ it is equivalent to two-sample testing. The intermediate settings occur in the field of likelihood-free inference, where labeled samples are obtained by running forward simulations and the unlabeled sample is collected experimentally. In recent work it was discovered that there is a fundamental trade-off
between $m$ and $n$: increasing the data sample $m$ reduces the amount $n$ of training/simulation
data needed. In this work we (a) introduce a generalization where unlabeled samples 
come from a mixture of the two classes -- a case often encountered in practice; (b) study the minimax sample complexity for non-parametric classes of densities under \textit{maximum mean
discrepancy} (MMD) separation; and (c) investigate the empirical performance of kernels parameterized by neural networks on two tasks: detection
of the Higgs boson and detection of planted DDPM generated images amidst
CIFAR-10 images. For both problems we confirm the existence of the theoretically predicted asymmetric $m$ vs $n$ trade-off.

Kernel-Based Tests for Likelihood-Free Hypothesis Testing
Patrik Róbert Gerber"
Tianze Jiang"
Department of Mathematics, MIT
Department of Mathematics, MIT Cambridge, MA 02139 tj tjiangomit.es
Cambridge, MA 02139
prgerber@mit.eem edu
Yury Polyanskiy*
Rui Sun"
Department of EECS, MIT Cambridge, MA 02139 ypemit.en edu
Department of Mathematics, MIT Cambridge, MA 02139 eruisun@mit.c edu
Abstract
Given n observations from two balanced classes, consider the task of labeling additional m inputs that are known to all belong to one of the two classes. Special cases this problem are well-known: with complete knowledge of class distributions (n oc) the problem is solved optimally by the likelihood-ratte test; when m = 1 corresponds to binary classification; and when m n is equivalent to two-sample testing. The intermediate settings occur in the field of likelihood-fres inference, where labeled samples are obtained by running forward simulations and the unlabeled sample is collected experimentally. In recent work it was discovered that there is fundamental trade-off' between m and n: increasing the data sample m reduces the amount n of training/simulation data needed. In this work we (a) introduce a generalization where unlabeled samples come from mixture of the
often encountered in practice; (b) study the minimax sample complexity for non non-parametric classes of densities under maximum mean discrepancy (MMD) separation; and (c) investigate the empirical performance of kernels parameterized by neural networks on two tasks: detection of the Higgs boson and detection of planted DDPM generated images amidst CIFAR-10 images. For both problems we confirm the existence of the theoretically predicted asymmetric m vs n trade-off.
classes
1 Likelihood-Free Inference
The goal of likelihood- -reih inference (LFI) [8: 12; 17; 24], also called simulation- based inference (SBI), is to perform statistical inference in setting where the data generating process is black-box. but can be simulated. Given the ability to generate samples X, p for any parameter 0, and simulations learn about the truth 0*, LFI is
given real-world data Z p8m we want to particularly relevant in areas science where we have precise but complex laws nature, for which we can do (stochastic) forward simulations, but can not directly compute the (distribution) density Pg. The Bayesian community approached the problem under the name of Approximate Bayesian Computation (ABC) [6; 13; 47]. More recent ML-based methods where regressors and classifiers
Equul contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

are used to summarize data, select regions of interest, approximate likelihoods or likelihood-ratios [14; 29; 30; 42; 49] have also emerged for this challenge.
Despite empirical advances, the theoretical study of frequentist LFI is still in its infancy. We focus on the nonparametric and non-asymptotic setting, which we justify as follows. For applications where tight error control is critical one might be reluctant to rely on asymptotics. More broadly, the non- asymptotic regime can uncover new phenomena and provide insights for algorithm design. Further, parametric models are clearly at odds with the black-box assumption. Recently, [18] proposed likelihood-free hypothesis testing (LFHT) as a simplified model and found minimax optimal tests for a range of nonparametric distribution classes, thereby identifying a fundamental simulation- experimentation trade-off between the number of simulated observations n and the size of the experimental data sample m. Here we extend [18], and prior related work [19; 26; 27; 32; 33], to a new setting designed to model experimental setups more truthfully and derive sample complexity (upper and lower bounds) for kernel-based tests over nonparametric classes.
While minimax optimal, the algorithms of [18: 19] are impractical they rely on discretizing the observations on a regular grid. Thus, both in our theory as well as experiments we turn to kernel methods which provide an empirically more powerful set of algorithms that have shown success in nonparametric testing [20; 21; 22; 31; 39].
Contributions Our contributions are twofold. Theoretically, we introduce mixed likelihood hypothesis testing (mLFHT), which is a generalization of (LFHT) and provides a better model of applications such as the search for new physics [11; 38]. We propose a robust kernel-based test and derive both upper and lower bounds on its minimax sample complexity over a large nonparametric class of densities, generalizing multiple results in [18; 19; 26; 27; 32; 37]. Although the simulation- experimentation (m vs n) trade-off has been proven in the minimax sense (that is, for some worst-case data distribution). is not clear whether it actually occurs in real data. Our second contribution is the empirical confirmation of the existence of an asymmetric trade-off, cf. Figure 1.2. To this end we construct state-of-the tests building on ideas of [39; 48] on learning good kernels from the data. We execute this program in two settings: the Higgs boson discovery [5], and detecting diffusion [25] generated images planted in the CIFAR-10 [35] dataset.
1.1 LFHT and the CumulltionnEEperimeentee
Trade-off
Suppose we have i.i.d. samples X, Y each of size n from two unknown distributions Px, Py on measurable space X. as well as a third i.i.d sample ~ Pz of size m. In the context of LFI, we may think of the samples X, Y as being generated by our simulator, and Z being the data collected in the real world. The problem we refer to as Eielihood-free hypothesis testing is the task of deciding between the hypotheses
Ho Pz = Px versus P2
(LFHT)
This problem originates in [23; 52]. where authors study the exponents of error decay for finite X and fixed Px, Py as n ~ m + oc; more recently [2: 18; 19; 26: 27; 32; 33; 37] it is studied in the non-asymptotic regime. Assuming that Px, Py belong to a known nonparametric class of distributions P and are guaranteed to be c-separated with respect to total variation (TV) distance (i.e. TVx.x Pv) 2 <), [18] characterizes the sample sizes n and m required for the sum of I and type-Il errors to be small, as a function of e and for several different P's. Their results show, for three settings of P, that (i) testing (LFHT) at vanishing error is possible even when n is not large enough to estimate Px and Py within total variation distance Ole), and that (ii) to achieve a fixed level of error, say a, one can trade off m vs. n along a curve of the form {min (n, /mn) 2 (as e, P). m 2 log log(1/a)/e"). Here Its denotes the minimax sample complexity of two-sample testing over P, i.c. the minimum number of observations n needed from Px, Py E P to distinguish the cases (Px.x.Py 2 e versus Px = Py. Here& 2 suppresses dependence on constants and untracked parameters.
It is unclear, however, whether predictions drawn from minimax sample complexities over specified distribution classes can be observed in real-world data. Without the theory, a natural expectation is that the error contour {(,,)) : a test with total error S a.) would look similar to that of minimax two-sample testing with unequal sample size, namely {m,, min m) Z RTs(aa, e, P)), i.e. and m simply need to be above a certain threshold simultaneously (as is the case for e.g. two-sample testing over smooth densities [4; 37D. However, from Figures 2 and 1.2 we see that there is indeed

---

non-trivial trade-ofi off between n. and m: the contours are not always parallel to the axes and aren't t symmetric about the line m n. The importance of Fig. 1.2 is in demonstrating that said trade-off is not a kink of theory that arises due to some esoteric worst-case data distribution, but is instead a real effect observed in state-of-the-an I.FI algorithms ran on actual data. We remark that the used in this plot is the total number of simulated samples (most of which are used for choosing neural-networl network parameterized kernel) and are not just the n occuring in Theorems 3.1 and 3.2 which apply to fixed kernel. See Section 4 for details sample division.
1.2 Mixed Likelihood-Free Hypothesis Testing
prominent application likelihood- free inference lies the field particle physics. Scientists run sophisticated experiments in the hope of finding phenomenon can be predicted from theory, and thus can be simulated, as was the case for the Higgs boson whose existence verified after nearly 50 years at the Large Hadron Collider (LHC) [3; 9].
particle phenomenon. Often said
Suppose we have n simulations from the background distribution Px and the signal distribution Py- Further, we also have m (real-world) datapoints from Pz (1 - Px + =Py, i.e. the observed data a mixture between the background and signal distributions with rate parameter v. The goal of physicists is to construct confidence intervals for v, and discovery corresponds to 50 confidence interval that excludes 0. We model this problem by testing
Hu : V versus H1 2
(mLFHT)
for fixed (usually predicted) 8 0. See the rigorous definition of (mLFHT) in Section In particular, a discovery can be claimed if Ho is rejected.
Type error + Type Il error
2 The Likelihood-Free Test Statistic
Higgs experiment
This section introduces the testing procedure based on Maximum Mean Discrepancy (MMD) that study throughout the paper both theoretically and empirically. First, introduce the necessary background MMD in Section 2.1. Then, we define our test statistics in Section 2.2.
0.69
0.40
0.10
3.1-10
4.9-10-7
1.4-0
15 10-40
2.1 Kernel Embeddings and MMD
10010-400
65-10-15
Given a set X, we call the function K : X + R kernel the matrix with i''th th entry K K( xr) symmetric positive semidefinite for all choices of æı...., Tn E X and n 2 There is a unique reproducing kernel Hilbert space (RKHS) HK associated to K. HK consists of functions X - and satisfies the reproducing property f(x) for all f H4 and x X, in particular K K(x,) -) E HK. Given probability measure P on X, define its kernel embedding 0r as
2.0
2.5
3.5
4.0
5.0
5.5
(m(m)
CIFAR experiment
4.0
0.90
(K(x, ") H)
2.5
2.0
Op Exar x(x.))= K(x,.)
(1)
1.5
Given the kernel embeddings of two probability measures P. Q. we can measure their distance in the RKHS by MMD(P,Q) Q) A ||0r follHx. where MMD stands for maximum mean discrepancy. MMD has a closed form thanks to the reproducing property and linearity:
1.0
1.5
2.0
2.5 (g(m)
3.0
3.5
Figure versus m trade-off for Higgs and CIFAR experiments using our test in Sec- tion 2. Error probabilities estimated by normal approximation for Higgs and simu- lated for CIFAR.
MMD 3 Q) = E K(X,X') K(YYY') - 2
where (X, X', YY,YYY' Y") p82 x0 82 In particular, P,Q
empirical measures based on observations, evaluate the MMD exactly, which is crucial
3

---

in practice. Yet another attractive property of MMD is that (under mild integrability conditions) it an integral probability metric (IPM) where the supremum is over the unit ball of the RKHS Hxx. See e.g. [41; 46] for references. The following result is consequence of the fact that self-adjoint compact operators are diagonalizable.
Theorem 2.1 - Suppose that K E [2 p)) is symmetric. Then there ex- ists a sequence (2z) E l and an orthonormal basis (e) of (2( such that K K(x, y) = Eş² A3cz(1))e (V) for all j 2 1, where convergence is in L (p (188 nt).
Assumption 1. Unless specified otherwise, we implicitly assume a choice of a non-negative measure 1 and kernel K for which the conditions of Theorem 2.1 hold. Note that X 2 and depend on p.
Removing the Bias In our proofs we work with the kernel embedding of empirical measures for which we need to modify the inner product (: Hy (and thus MMD) slightly by removing the diagonal terms. Namely, given i.i.d. samples X, Y of size n, m respectively and corresponding empirical measures Px, Px,Pr, we define
K(,,,,))
K(Y, M,)
Y
MMD Pv)
m(m -2 -2 -
+
(2)
nnn - 1)
1.
We also write p0px Ppxuu. The stands for unbiased, since E MMD 8 (Px, Py) general.
p 1|,, Hk
w(त Eitj K ((X, X3) and extend linearly. MMD* (Px, Py) * (MMDM(PxP.F Py) in
2.2 Test Statistic
With Section 2.1 behind us, we are in a position to define the test statistic that we use to tackle (mLFHT). Suppose that we have samples X, Z of sizes n, n, m from the probability measures Pr, Write Px for the empirical measure of sample X, and analogously for Y, Z. The core of our test statistic for (mLFHT) is the following:
(() 2 10pz - 0 Ppxlu.tt
((Z - K(2,.
(3)
TET
Note that T is of the additive form En ((z)) where f(z) 2 02, (z) pp (z) can be interpreted
as the witness function of [21; Given some π E [0, 1] (taken to be half the predicted signal rate 5/2 in our proofs), the output of our test
V T(X,X, Y,) 2 7X, m where >Xx, Y,, n MMD Px)+ (4)
The threshold gives V a natural geometric interpretation: it checks whether the projection of
0 0/ 0p onto the vector 0p., - 0p falls further than क along the segment joining 0p to 0 0p. (up to deviations due to the omitted diagonal terms, see Section 2.1).
Setting 6 = 1 in (mLFHT) recovers (LFHT), and the corresponding test output is 1/ = 11/2 = if and only if MMD (P2, Pxx 2 MMD,(PP. Py). This very statistic (i.e. MMD,, (P2, Px) MMD, (Px, )) has been considered in the past for relative goodness-of-fis testing [7] where it's asymptotic properties are established. In the non-asymptotic setting, if MMD is replaced by the I -ii-tinance we recover the test statistic studied by [18; 27: 33). However, we are the first to introduce 1 for 8 # 1 and to study MMD-based tests for (m)LFHT in non-asymptotic setting.
Variance cancellation At first sight may seem more natural to the reader to threshold the distance MMD,, (P2,, Px), ), resulting in rejection if, say, MMD,, (P2, Px) 2 MMD,,, (P )8/2 The geometric meaning of this would be similar the outlined above. However, there is a crucial difference: (LFHT) (the case 5 = 1) is possible with very little experimental data m due to the cancellation of variance. More precisely, the statistic MMD? (Pz. contains the term mmm-1j Eizy (ZZ Z3) - whose variance prohibitively large and would inflate the m required for reliable testing- - but this can be canceled by subtracting MMD2 py). Our statistic T(X, Y, 2) r(X, Y, simply generalizes this idea to (mLFHT).

---

3 Minimax Rates of Testing
3.1 Upper Bounds on the Minimax Sample Complexity of (mLFHT)
Let us start by reintroducing (mLFHT) in a rigorous fashion. Given C, R 2 0. let (c R) denote the set of triples (Px, Pz, of distributions such that the following three conditions hold: Px, and Pz have y-densities bounded by C.
MMD(Px. x Pr) 2 6, and
i1
MMD(Pz, (1 - v) Px uPy) - R. MMD Pr),
where we define v(Px. Py, Pz) arg Min MMD v')Px +/))), For some > 0, consider the two hypotheses
Ho e, 8, R) (Px, Py, P2) E E, R) and = 0
(S)
Hi(C,e, 8, R): (Px, Pz) E P,(C,e, R) and 2 6,
which we regard as subsets of probability measures. Notice that R controls the level of mis- specification in the direction that is orthogonal to the line connecting the kernel embeddings of Px and Py. Setting R = 0 simply asserts that Pz is guaranteed to be mixture of Px and Py, as is the case for prior works on LFHT. Before presenting our main result on the minimax sample complexity of mLFHT, let us define one final piece of terminology. We say that test V, which takes some data as input and takes values {0, 1]. has total error probability less than a for the problem testing Ho vs H1 if
sup P(V= +)+ sup Q( = =0) a.
(6)
PEHo
QEHi
Theorem 3.1. Suppose we observe three i.i.d. samples X,Y, 7. from distributions Px, Py, Pz composed of n. n. m observations respectively and let C E (0) and R 2 O and ō (0, 1).
There exists a universal constant c > O such that 1622 defined Section 2.2 tests Ho vs HJ, as defined in (5), total error a provided
min(m,n) n) 2 Cl log(1/a) (co/(1+R))*
Cl|Al12 log(//)
and
min(n, vnm 2 c
de2
Note that Theorem 3.1 does not place assumptions on the distributions Px, Py beyond bounded density with respect to the base measure μr. This is different from usual results in statistics, where prior specification of dis- tribution classes is crucial. On the other hand, instead of standard distances such LP, we assume separation with respect to MMD and the latter is potentially harder to interpret than, say, L i.e. total variation. We do point out that our Theorem 3.1 can be used to derive results in the classical setting; discuss this further in Section 3.4.
Type-I error
1e4
0.40
4e3
0.35
2e3
0.30
0.25
402
0.20
2e2
lc2
0.15
0.10
4e1
2e1
0.05
In an appropriate regime the parameters, the sufficient sample complexity in Theorem 3.1 exhibits trade-off of the form min Vmnz Z ||||| log(1 (//aa////////// between the number of simulation samples and real observations m. This trade-off is shown in Figure using data from a toy problem. The trade-off is clearly asymmetric and the relationship m n 2 const. also seems to appear. In this toy problem set R 0, 1,c .3, k 100 and Px P2,Py are distributions on {1, 2....... }} with Px(1) = (1 c2 (2 1fi [dd} - 1))/k =
le1
201
461
le2
202
ae2
163
203
463
164
0.00
Figure 2: n versus m trade-off for the toy experiment, verifying Theorem 3.1. Probabil- itics estimated over 10" runs, and smoothed using Gaussian noise.
2/k (i) for all = 1, 1, ... k. The kernel we take is K(x, () = Σ 1(x 1xx=1 if and is simply the counting measure; the resulting MMD is simply the - 2i-diittnce on pmfs.
Figure 1.2 illustrates a larger scale experiment using real data using trained kernel. Note that plot the total number n of simulation samples, including those used for training the kernel itself (see Section 4); which ensures that Figure 1.2 gives realistic picture of data requirements. However, due to the dependence between the kernel and the data, Theorem 3.1 no longer applies. Nevertheless, we observe trade-off similar Figure 2.
5

---

3.2 Lower Bounds on the Minimax Sample Complexity of (mLFHT)
In this section we prove minimax lower bound on the sample complexity of mLFHT, giving a partial converse to Theorem 3.1. Before we can state this results, we must make some technical definitions. Given J 2 2. let | - د 2 and define
J a max {J: sup
J Σ ==
||A|l2
V X
7h
S
2e S
m==11
Theorem 3.2 (Lower Bounds for mLFHT). Suppose that 1xx K(x, y)u(dr) = X p(²) and supzex K(x, 2) < 1. There exists universal constant 0 such that any test of Ho H1, as defined in (5), with total error at most a must use a number (n, m. of observations that satisfy
m A2 A2 and n 1Alls vlog(1/a) and 8m <mm ||Allas (log(1/a)
2282
228
Remark 3.3. Recall that the eigenvalues depend the choice of so that by choosing a different base measure μ one can optimize the lower bound. However, since Px. Py, Pz are assumed to have bounded density with respect to μ., this appears rather involved.
Remark 3.4. The requirements supzex K (xx,)) x) S 1 and px(²) generality, as μ and K can be rescaled. The condition fxx K (az, v)u(dr) A implies that the top eigenfunction é1 is equal to constant equivalently, that y ((x, v)p(cz) defines Markov kernel up to a normalizing constant.
are essentially without loss of
3.3 Tightness of Theorems 3.1 and 3.2
Dependence on ||al|2 An apparent weakness of Theorem 3.2 is its reliance on the unknown value J. which depends on the specifics of the kernel K and base measure μ.. Determining is potentially highly nontrivial even for simple kernels. Slightly weakening Theorem 3.2 we obtain the following corollary, which shows that the dependence on |||l| is tight, at least for small e.
Corollary 3.5. Suppose J is such that Σj= X3 2 1A12 for some S 1. Then |Allz can be replaced by cl|All2 in Theorem 3.2 whenever e S (2/ -
Dependence R and a Due the general nature of our lower bound constructions, it difficult to capture the dependence on the misspecification parameter R. As for the probability of error o, based on related work [16] we expect the gap of size (log(1/a) to be a shortcoming of Theorem 3.1 and not the lower bound. Closing this gap may require a different approach, however, tests based on empirical L distances are known to have sub-optimal concentration [27].
Dependence on 8 The correct dependence the signal rate ö is the most important question left open by our theoretical results. Any method requiring n larger than a function of 5 irrespective of m (as in Theorem 3.1) is provably sub-optimal because taking 2 1/(8e)² and large enough to estimate both Px, Py to within accuracy e/1 always suffices to reach a fixed level of total error.
3.4 Relation to Prior Results
In this section diseuss some connections of Theorem 3.1 to prior work. Specifically, discuss how Theorem 3.1 recovers some known results in the literature [4; 18; 37] that are minimax optimal. Details omitted in this section are included in Appendix B.
Binary Hypothesis Testing Suppose the two distributions Px, Py are known, we are given m i.i.d. observations Zı..... Zm Pz and our task is to decide between the hypotheses Ho Px Pz versus H1 Py = Pz. Then, we may take n = 20, R 0, in Theorem 3.1 to conclude that
al log(1/a)
m 2
observations suffice to perform the test total error
Two-Sample Testing Suppose we have two i.i.d. samples and Y. both of size n, from unknown distributions Px, Py respectively and our task is to decide between Ho Px Py against H1

---

MMD(PxxPPP)) 2y) We split our Y sample in half resulting in Y and Y(3) and form the statistic Ts & V1)2(X,
V 11/2(Y(1,, X, ),Y where 1/2 is defined in Section 2.2. Then E Ts| is equal to 0 under the null hypothesis and is at least 1 - 201 under the alternative, where a1 is the target total error probability of v 1/22. Taking a1 5%. by repeated sample splitting and majority voting we may amplify the success probability to provided
CilAlla log(1/a)
n M
(7)
e²
where > 0 is universal (see Appendix for details). The upper bound (7) partly recovers [37, Theorem 3 and 5] where authors show that thresholding the MMD with Gaussian kernel (r y)
o- expe(p1111> | yll²/a²) achieves the minimax optimal sample complexity n -28++4/2)/ for the problem of two-sample testing over the class Pa.a of d-dimensional (3, 2oSholoeev-s distributions (defined in Appendix B.3) under e-L--separation. For this, taking a X e4/3 ensures that
X MMD(P, Q) over Q.Q& E Pa.a- Taking e.g. du(x)) exp(-1|> [2) as the base measure, (7) recovers the claimed sample complexity since ||^ll = G (1, y ()) O d) hiding dimension dependent constants. Our result requires a bounded density with respect to Gaussian.
likelihood-Free Hypothesis Testing By taking a x Rx = (() in Theorem 3.1 we can recover many of the results in [18; 32; 33]. When X' is finite, we can take the kernel k(x, y) = Exex 1(2 y 2} in Theorem 3.1 to obtain the results for bounded discrete distributions (defined in Appendix B. which state that under T-V-separation the minimax optimal sample complexity is given by m 2 m v / Z /xT//2. A similar kemel recovers the optimal result for the class of B-Hölder smooth densities on the hypercube [0, 1]d (see Appendix B.2).
Curse of Dimensionality Using the Gaussian kernel G. as for two-sample testing above, one can conclude by Theorem 3.1 that the required number of samples for (mLFHT) over the class Pa under c- --?-separatioon grows at most like & ((1)((() }.) for some e > 1, instead of the expected Ω ((.)) This may be interpreted as theoretical support for the success of I.FI in practice where
signal and background can be rather different (cf. [5, Figures 2-3]) and the difficulty of the problem stems from the rate of signal events being small (i.e. R 1 but 5 < 1).
4 Learning Kernels from Data
Given a fixed kernel K, our Theorems 3.1 and 3.2 show that the sample complexity is heavily dependent on the separation c under the given MMD as well as the spectrum A = A(H, K) of the kernel. Thus, to have good test performance we need to use a kernel K that is well-adapted to the problem at hand. In practice, however, instead of using a fixed kernel it would be only natural to use part of the simulation sample to try to learn a good kernel.
In Sections 4 and 5 we report experimental results after training kernel parameterized by a neural network on part of the simulation data. In particular, due the dependence between the data and the kernel, Theorem 3.1 doesn't 't directly apply. Our main contribution here is showing the existence of an asymmetric cnmullation-xpprmmennttiono trade-off (cf. Figure 1.2 and also Section 1.1) even in this realistic setting. Figure 1.2 plots the total number n of simulations used, including those used for training, so as to provide a realistic view of the amount of data used, The experiments also illustrate that the (raiined)kkemel-baaee
statistic of Section 2.2 achieves otate-of-the-art performance.
4.1 Proposed Training Algorithm
Consider splitting the data into three parts: (X"*, Y*r is used for training (optimizing) the kernel; (X"", yev) is used to evaluate our test statistic at test time; and (Xcaal ycal) is used for calibrating the distribution of the test statistic under the null hypothesis. We write n, = =X = |Y* for E (tr, ev, cal]. Given the training data X ytr with empirical measures Px., Pyn, we maximize the objective in
MMD (Px.. Pyu; K) ,(",,y") K)
T(x" y";
(8)
which was introduced in [48]. Here 22 is an estimator of the variance of MMD)((Xx Pyu; K) and is defined in Appendix F.I.
7

---

Algorithm mLFHT with learned deep kernel
Input: (X", "x",, (Y", Y y parametrized kernel Kw; hyperparameters and initialization.
# Phase 1: Kernel training (optimization) on X and Y".
maximize objective as defined (8) # Phase 2: Distributional calibration of test statistic (under null hypothesis).
w f arg max_ Detiees J(x", y"; Kw):
for = 1, do Zoal."" sample y points without replacement from X
Tr nomm En, (Ku(Z y1ah) Kw (7, x5
end for
# Phase 3: Inference with input Z.
- Ees (Kw / - Ku (2,, (2,1,))) X²1): Output: Estimated p-value: k - 11 T
Intuitively, the objective J aims to separate Px from py while keeping variance low. For a heuristic justification of its use for (mLFHT) see Appendix.
In Algorithm I we describe the training and testing procedure, which produces unbiased p-values for (mLFHT) when there is no misspecification (R in Theorem 3.1). During training, use the Adam optimizer [34] with stochastic batches.
Proposition 4.1. When there is no misspecification (R = 0 in Theorem 3.1), Algorithm outputs an unbiased estimate of the p-value that is consistent as mina k} 00.
Time complexity Algorithm runs in three separate stages: training, calibration, and inference.
The first two take O (#epochs B² + k)) total time, where B the batch size, whereas Phase 3 takes only (1 time, which is generally much faster especially if nev < <hr
Sample usage Empirically, data splitting in Algorithm can have non-trivial effects on performance. Instead of training the kernel on only a fraction of the data ([X*, y"] n _xer, Ø), we discovered that taking {Xee yev] C {X"r, y"] results in more efficient use of data. The stronger condition {xev, yev) {X ytr) can also be applied; we take S to reduce time complexity. We do, however, crucially require X yeal in Phase 2 to be independently sampled ("held-out") for consistent p-value estimation. Finally, we remark also that splitting this way is only valid in the context of Algorithm 1. For the test (4) using the data-dependent threshold 7 one needs {X", Y") n (Xer, Y") = Ø to estimate
4.2 Classifier-Based Tests and Other Benchmarks
Let 6: : X X cross-entropy loss of classifier net. There two natural test statisties based Φ:
+ [o, 1] be classifier, assigning small values to Px and high values to Py by minimizing
Scheffé's Test. The first idea, attributed to Scheffé folklore [15, Section 6). to take the statistic T(Z) = - DE 1 (( 7.) > /} where / is some (learn-able) threshold.
Approximate Sayman--Parsoon / Logit Methods. If o is trained perfection, then ((2) = 22) would be the likelihood and d(z)/(1 o(2)) would equal precisely the likelihood ratio between By and Px This motivates the use of T(Z)= m Σ log( / ((Z)))). See also [10].
Let us list the testing procedures that we benchmark against each other in our experiments.
1. MMD-M: The MMD statistic (3) using K with the mixing architecture
K(x, v) [(1 r) G) (PL Pw)) + + r]. Go + (l y + (1)).
Here G. is the Gaussian kernel with variance a²: yp,, p are NN's (with parameters w, w'), and a, Jo, T, 7, w' are trained.
2. MMD-G: The MMD statistic (3) using the Gaussian kernel architecture K (2, y) G. (v)) where ya is the feature mapping parametrized by trained network and
(y))
a is trainable parameter.
3. MMD-0: The MMD statistic (3) using the Gaussian Kernel K(x, v) = Go(r,)) y) with optimized bandwidth First proposed in [7; 39].
8

---

MMD-M
UME
SCH
MMD
Rejection Rate (al5ha=0.05)
Expected P-Value
Error Probability At
ROC curves for different
78
0.8
M-384
m-256
3.4
04
0.2
0.4
m=192 19
m=128
3.0
50
300
350
200
299
952
000
350
2:30
250
999
350 253 3750
100
15.0
0.0
0.2
0.4 0.
1.0
FPR
Figure 3: Empirical performance on (9) for the CIFAR detection problem when = 1920. Plots from left to right are follows. (a) rejection rate under the alternative if test rejects whenever the estimated p-value smaller than 5%: (b) expected p-value [45] under the alternative; (c) the average of type-I and II error probabilities when thresholded at (different from (4), see Appendix); and (d) ROC curves for different m using MMD-M and Algorithm 1. Shaded area shows the standard deviation across 10 independent runs. Missing benchmarks (thresholded MMD, MMD-O, -O, LBI, RFM) are weaker, see Appendix for full plot.
4. UME: An interpretable model comparison algorithm proposed by [31], which evaluates the kernel mean embedding
chosen "witness set".
5. SCHE, LBI: Scheffé's test and Logit Based Inference methods [10], based on binary classifier network ø trained via cross-entropy, introduced above.
6. RFM: Recursive Feature Machines, a recently proposed kernel learning algorithm by [44].
4.3 Additive Statisties and the Thresholding Trick
Given a function (usually obtained by training) and test data = (Z,,...; 7m), we call a test additive if its output is obtained by thresholding (Z) & 1
Tu Ei=1 f(z)). We point out that all of MMD-M/G/O, SCHE, LBI, UME, RFM are of this form, see the Appendix for further details. Similarly to [39], we observe that any such statistic can be realized by our kernel-based approach.
Proposition 4.2. The sernel-based statistic defined (3) with the kernel K(x, y) = f(y is equal to T up to multiplicative and additive constant independent of Z.
Motivated by the Scheffé's test, instead of directly thresholding the additive statistic (Z) we found empirically that replacing f by fe(x) & 1{f(x) > {} can yield improved power. We set t by maximizing an estimate of the significance under the null using normal approximation, iec. by solving topt A arg max, ()"""" -T,, (X**))
(X= (X=x3) where X yopt satisfy { yopt n
([xcal, yea) (Xev, ye*)) = Ø. This trick improves the performance of our tester on the Higgs dataset Section 5.2 but not for the image detection problem in Section 5.1.
Experiments
Our code can be found at
comp: 11/LFI.
5.1
Image Source Detection
Our first empirical study looks at the task of detecting whether images come from the CIFAR-10 [36] dataset or a SOTA generative model (DDPM) [25: 51]. While source detection is on its own interesting, it turns out that detecting whether group of images comes from the generative model versus the real dataset can too "easy" (see experiments in [31]). Therefore, we consider a mixed alternative, where the alternative hypothesis is not simply the generative model but CIFAR with planted DDPM images. Namely, our n labeled images come from the following distributions:
1 Px CIFAR, and py = DDPM + CIFAR.
2
The goal is test whether the unlabeled observations Z have been corrupted with p more fraction of DDPM images (versus uncorrupted CIFAR); this corresponds to (LFHT) (or equivalently (mLFHT) with 5 = 1). Figure 3 shows the performance of approach with this mixed alternative.
Network Architecture With standard deep CNN, the difference is only the final layer: for the kernel-batt based tests it is feature output; for classifiers, add an extra linear layer to logits.

---

We see from Figure 3 that our kernel-based test outperforms other benchmarks at a fixed training set size Mty One potential cause is that MMD has an "optimization" subroutine (which it solves in closed form) as it is an IPM. This additional layer of optimization may lead to better performance at small sample sizes. The thresholding trick does not seem to improve power empirically. We omit several benchmarks from this figure for graphic presentation and they do not exhibit good separating power, see the Appendix for the complete results. The bottom plot of Figure 1.2 shows m and n on trade-off.
log-scale against the total probability of error, exhibiting the simulation-exprrimentaii
5.2 Higgs- Higgs-Bosson Discovery
MMD-M with fage
UME
The 2012 announcement of the Higgs boson's 's discovery by the ATLAS and CMS experiments [1; 9] marked significant milestone in physics.
SCHE with Caps
LBI
Significance of discoveryla
5.0
The statistical problem inherent in the exper- iment is well-modeled by (mLFHT), using signal rate 8 predicted by theory and misspec- ification parameter
4.5
0 (as was assumed in the original discovery). We consider our algo- rithm's power against past studies in the physics
3.5
literature [5] as measured by the significance
of discovery. We note an important distinction
3.0
from Algorithm in this application,
Estimating the Significance In physics, the threshold for claiming a "discovery" is usually significance of 50, corresponding to p- value of 2.87 x 10-7. Approximately neat >> (2.87) 10 samples would be necessary for Algorithm 1 to reach such a precision. For- tunately the distribution of the test statistic is approximated by Gaussian customarily. We adopt this approach for our experiment hereby assuming that m is large enough for the CLT to apply. We use the "expected significance of discovery" as our metric [5] which, for the additive statistie Ty Em f(Zz), is given by -I, If the thresholding trick (Section 4.3) / ((x+)(((")))mm
2.6
Training set size 2n/million
Figure 4: Expected significance of discovery on a mix- ture of 1000 backgrounds and 100 signals in the Higgs experiment. Shaded area shows the standard deviation over 10 independent runs. See Appendix for full plot including missing benchmarks.
applied we use the more precise Binomial tail, which case the significance estimated by . (PiBn(mm, Tim (Xraa) 2 T (Z))). where Tb is the standard normal CDF.
Newtowk Architecture The architecture is a 6-layer feedforward net similar for all tests (kernel- based and classifiers) except for the last layer. We leave further details to the Appendix.
As can be seen in Figure 4, Scheffé's s test and MMD-M with threshold topt are the best methods, achieving similar performance the algorithm of [5]; reaching the significance level of 5a on 2.6 million simulated datapoints and a test sample made up of mixture of 1000 backgrounds and 100 signals. The top plot of Figure 1.2 shows and log-scale against the total probability of error through performing the test (4), exhibiting the asymmetric momulaiion-exprrmmentee trade-off.
Conclusion
In this paper, we introduced (mLFHT) as a theoretical model of real-world likelihood-free signal detection problems arising in science. We proposed a kernel-based test statistic and analyzed its minimax sample complexity, obtaining both upper (Theorem 3.1) and lower bounds (Theorem 3.2) in terms of multiple problem parameters, and discussed their tightness (Section 3.3) and connections to prior work (Section 3.4). On the empirical side, we described method for training a parametrized kernel and proposed a consistent p-value estimate (Algorithm and Proposition 4.1.. ). We examined the performance of our method in two experiments and found that parametrized kernels achieve state-of-the-ae performance compared to relevant benchmarks from the literature. Moreover, we confirmed experimentally the existence of the asymmetric simulation experiintexpiiiinnaattioon trade-off (Figure 1.2) which is suggested by minimax analysis. We defer further special cases of Theorem 3.1, all relevant proofs and experimental details to the Appendix.
10

---

Acknowledgments and Disclosure of Funding
YP was supported part by the National Science Foundation under Grant No CCF-2131115. Research sponsored by the United States Air Force Research Laboratory and the Department of the Air Force Artificial Intelligence Accelerator and was accomplished under Cooperative Agreement Number FA8750-19-22 19-2-1000. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Department of the Air Force the U.S. Government. The U.S. Government authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
References
[1] Aad, G., Abajyan, T., Abbott, B., Abdallah, J., Khalek, S. A., Abdelalim, A. A., Aben, R., Abi, B., Abolins, M., AbouZeid, O., et al. Observation of new particle the search for the standard model Higgs boson with the ATLAS detector at the LHC. Physics Letters B, 716(1):1-29, 2012.
[2] Acharya, J., Das, H., Jafarpour, A., Orlitsky, A., Pan, S., and Suresh, A. Competitive classifica- tion and closeness testing. In Conference on Learning Theory, pages 22-1. JMLR Workshop and Conference Proceedings, 2012.
[3] -ouuddoou,, C., Cowan, G., Germain, C., Guyon, I., Kégl, B., and Rousscau, D. The Higgs boson machine learning challenge. In NIPS 2014 workshop high-energy physics and machine learning, pages 19-55. PMLR, 2015.
[4] Caasto,astro, E., Pelletier, B., and Saligrama, V. Remember the curse of dimensionality: The case of goodness-of fit testing in arbitrary dimension. Journal of Nonparametric Statistics, 30 (2):448 471, 2018.
[5] Baldi, P., Sadowski, P., and Whiteson, D. Searching for exotic particles in high-energy physics with deep learning. Nature communications, 5(1):1-9, 2014.
[6] Beaumont, M. A. Approximate bayesian computation. Annual review of statistics and its application, 6:379 403, 2019.
[7] Bounliphone, W., Belilovsky, E.,, Blaschko, M. B., Antonoglou, I., and Gretton, A. A test of relative similarity for model selection in generative models. In Bengio, Y. and LeCun, Y., editors, 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Truck Proceedings, 2016.
[8] Brehmer, J., Louppe, G., Pavez, J., and Cranmer, K. Mining gold from implicit models to improve likelihood inference. Proceedings of the National Academy of Sciences, 117(10): 5242-5249, 2020.
[9] Chatrchyan, S., Khachatryan, V., Sirunyan, A. M., Tumasyan, A., Adam, W., Aguilo, E., Bergauer, T., Dragicevic, M., Erö, J., Fabjan, C., et al. Observation of new boson a mass of 125 GeV with the CMS experiment at the LHC. Physics Letters B, 716(1):30-6 61, 2012.
[10] Cheng, X. and Cloninger, A. Classification logit two-sample testing by neural networks. CoRR, 0bs/11909111 12298, 2019.
[11] Cowan, G., Cranmer, K., Gross, E., and Vitells, O. Asymptotic formulae for likelihood-basee tests of new physics. The European Physical Journal C. 12(2)1119, 2011.
[12] Cranmer, K., Brehmer, J., and Louppe, G. The frontier of iimulation-baseee inference. Proceed- ings of the National Academy of Sciences, 117(44) 20200.
[13] Csilléry, K., Blum, G., Gaggiotti, O. E., and François, O. Approximate bayesian computation (abc) in practice. Trends in ecology & evolution, 25 418, 2010.
[14] Dalmasso. N., Izbicki, R., and Lee, A. Confidence sets and hypothesis testing in a likelihood- free inference setting. In International Conference on Machine Learning, pages 2323-2334. PMLR, 2020.
[15] Devroye, L. and Lugosi, G. Combinatorial Methods in Density Estimation. Springer Series in Statistics. Springer New York, 2012. ISBN 978 17114213

---

[16] Diakonikolas, I., Gouleakis, T., Kane. D. M., Peebles, J., and Price. E. Optimal testing of discrete distributions with high probability. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 542-555, 2021.
[17] Diggle, P. J. and Gratton, R. J. Monte carlo methods of inference for implicit statistical models. Journal of the Royal Statistical Society: Series B (Methodological), 46(2):193-213 1984.
[18] Gerber, P. R. and Polyanskiy, Y. Likelihood-free hypothesis testing. CoRR, abs/2211.01
2022. doi: 10.485500axx...2111..01
[19] Gerber, P. R., Han, Y., and Polyanskiy, Y. Minimax optimal testing by classification, 2023.
[20] Gretton, A., Fukumizu, K., Harchaoui, Z., and Sriperumbudur, B. K. A fast, consistent kernel
two-sample test. Advances in neural information processing systems, 22, 2009.
[21]
Gretton, A., Borgwardt, K. M., Rasch, M. J., Schölkopf, B., and Smola, A. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773 2012.
[22] Gretton, A., Sejdinovic, D., Strathmann, H., Balakrishnan, S., Pontil, M., Fukumizu, K., and Sriperumbudur, B. K. Optimal kernel choice for large-scale two-sample tests. Advances in neural information processing systems, 25, 2012.
[23] Gutman, M. Asymptotically optimal classification for multiple tests with empirically observed statistics. IEEE Transactions on Information Theory. 35(2):401-408, 1989.
[24] Gutmann, M. U., Dutta, R., Kaski, S., and Corander, J. Likelihood-free inference via classifica- tion. Statistics and Computing, 28:41 1-425, 2018.
[25] Ho, J., Jain, A., and Abbeel, P. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840-685/1 2020.
[26] Huang, D. Hypothesis Testing and Learning with Small Samples. PhD thesis, Citeseer, 2012.
[27] Huang, D. and Meyn, S. Classification with high-dimensional sparse samples. In 2012 IEEE International Symposium on Information Theory Proceedings, pages 2586-2590. IEEE, 2012.
[28] Ingster, Y. I. Minimax testing of nonparametric hypotheses on distribution density in the 1p metrics. Theory of Probability & Its Applicationns, 31(2):333-333 337, 1987. doi: 10.1 1371/ 1310422
[29] Izbicki, R., Lee, A., and Schafer, C. High- nigh-ddimesiionll density ratio estimation with extensions to approximate likelihood computation. In Artificial intelligence and statistics, pages 420-429. PMIR, 2014.
[30] Jiang, B., Wu, T.-y., Zheng. C., and Wong, W. H. Learning summary statistic for approximate bayesian computation via deep neural network. Statistica Sinica, pages 1595-1618, 2017.
[31] Jitkrittum, W., Kanagawa, H., Sangkloy, P., Hays, J., Schölkopf, B., and Gretton, A. Informative features for model comparison. Advances in Neural Information Processing Systems, 31, 2018.
[32] Kelly, B. G., Tularak, T., Wagner, A. B., and Viswanath, P. Universal hypothesis testing in the learning-limited regime. In 2010 IEEE International Symposium on Information Theory, pages
1478-1482. IEEE, 2010.
[33] Kelly, B. G., Wagner, A. B., Tularak, T., and Viswanath, P. Classification of homogeneous data with large alphabets. IEEE transactions on information theory, 59(2))782-795, 2012.
[34] Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. In Bengio, Y. and LeCun, Y., editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
[35] Krizhevsky, A. Learning multiple layers of features from tiny images. University of Toronto,
2009.
[36] Krizhevsky, A., Nair, V., and Hinton, G. The eifar-10 dataset (2014). Online: http://www: cs. toronto. edu/kriz/cifar. himl, 55, 2020.
[37] Li, T. and Yuan, M. On the optimality of gaussian kernel based nonparametric tests against smooth alternatives. arXiv preprint 1xXiv:190.003300 2019.
[38] Lista, L. Statistical methods for data analysis in particle physics, volume 941. Springer, 2017.
[39] Liu, F., Xu, W., Lu, J., Zhang, G., Gretton, A., and Sutherland, D. Learning deep kernels for por-marametric two-sample tests. International conference on machine learning, pages PMLR, 2020.
12

---

[40] Lopez-Paz, D. and Oquab, M. Revisiting classifier two-sample tests. In International Conference on Learning Representations, 2017.
[41] Muandet, K., Fukumizu, K., Sriperumbudur, B., Schölkopf, B., al. Kernel mean embedding of distributions: A review and beyond. Foundations and Trendy@ in Machine Learning, 10
(1-2):1-141, 2017.
[42] Papamakarios, G., Sterratt, D., and Murray, I. Sequential neural likelihood: Fast likelihood- free inference with autoregressive flows. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 837-848. PMLR, 2019.
[43] Polyanskiy, Y. and Wu, Y. Information Theory: From Coding to Learning- Cambridge University Press, 2023+.
[44] Radhakrishnan, A., Beaglehole, D., Pandit, P., and Belkin, M. Feature learning in neural networks and kernel machines that recursively learn features. arXiv preprint arXiv:2212.1388) 2022.
[45] Sackrowitz, H. and Samuel-Cahn, E. P values random variables-expected p values. The American Statistician, 53(4))326-331, 1999. ISSN 00031305.
[46) Schölkopf, B. and Smola, Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. The MIT Press, 06 2001. ISBN 9780262256933. doi: 10.7551)
mitpress/4175.001. 100.00..000...
[47] Sisson, S. A., Fan, Y., and Beaumont, M. Handbook of approximate Bayesian computation. CRC Press, 2018.
[48] Sutherland, D. J., Tung, H., Strathmann, H., De, S., Ramdas, A., Smola, A. J., and Gretton, A. Generative models and model criticism via optimized maximum mean discrepancy. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
[49] Thomas, O., Dutta, R., Corander, J., Kaski, S., and Gutmann, M. U. Likelihood-free inference by ratio estimation. Bayesian Analysis, 17(1):1-31, 2022.
[50] Tsybakov, B. Introduction to Nonparametrie Estimation. Springer Publishing Company, Incorporated, 1st edition, 2008. ISBN 0387790519,
[51] von Platen, P., Patil, S., Lozhkov, A., Cuenca, P., Lambert, N., Rasul, K., Davaadorj, M., and Wolf, T. Diffusers: State-of-the-art diffusion models. https: // /gi thub. com/huggingface/ diffusers, 2022.
[52] Ziv, J. On classification with empirically observed statistics and universal data compression. IEEE Transactions Information Theory, (4(2))278-228) 1988.
13

---

Appendix
A Notation
We use A 2 B,A - B, = B denote QQB), ((A) and @(B) respectively, where the hidden constants depend on untracked parameters multiplicativelyy.
We write TV, KL, x2 for total-variation, KL-divergence and >=-divergence, respectively. We write D 1Qjxx|xx/ = Ex~Px D(Prix lQQ x) as the conditional divergence for any probability measures P. Q on two variables X, Y and divergence D
We write S for the usual @ sequence space and LP for the usual L space with respect to the Lebesgue measure. Both the & norm and the L norm are written as || llp if no ambiguity arises.
For real numbers b E R we also write m b} V b and min(a, b) as A
We use 1. to denote an d-dimensional all I's vector.
For integer k E Zt, write [k] short notation for the set (1,2....:4 k)..
In the proofs of Theorem 3.1 and Theorem 3.2, we use - for an equality that we are trying to prove.
B Applications of Theorem 3.1
Usually, minimax rates of testing are proven under separation assumptions using more traditional measures of distance such as L where E [o]. In this section we show one example of how Theorem 3.1 can be used to recover known results, and also obtain some novel results under T.?-separation and T -s--appaaa..o.
B.1 Bounded Discrete Distributions Under LL L2/LL-Separatiin SSeaaatiion
Sample Complexity Upper Bounds Let Pos(k, C`) be the set of all discrete distributions P supported on [k] = 21. k} satisfying maxişis* p(i) I C/k, where p is the probability mass function of P (here Σ==1 p(k) = 1). For distributions Px, Py, Pz we shall write px, ,y,Pz as their probability mass functions, respectively.
Let us apply Theorem 3.1 with underlying space X = [k] and measure μ = = Σう 8, Take the kernel K K(x, y) 1 1z y) Eim 1(z y i}. and note that for any two distributions Px Py
we have
MMD Pv) E [(X, X' + K(Y,Y') 2k(x,)) Σ -
where (X,X,,,Y") P p@² So the corresponding MMD is the l distancce on prob- where
ability mass functions. Note also that K Σ (vk1 (v
[Vi1 - i3} forms an orthonormal basis of (1))).. So K has only one nonzero eigenvalue,
namely
=... , ^ = 1/k.
Ao
of multiplicity k. Suppose that we observe samples X, of size n, from Px. Py, Pz Pos (k, C"), where MMD(Px, Py) VI, Ipx (i) Py (1)2 2 e. Plugging into Theorem 3.1 shows that:
For example, the first equation in (10) means that there exists constant e independent of k, 6, R, such that min(m, n) 2 c (o /11
ke4g2
14

---

Proposition B.1. For any two Py (bb C), if the l -ddistnnce between Px Py is at least e, then testing (mLFHT) possible total error a using simulation samples and m real data samples provided that
C/ log(1/o)(1 + R)
log log(1/a)(1 R)2
min(m,n) n 2
8262
ke26²
(10)
C (og(1/a)
Vlog(1/a)
min Vmn}
288
Vke28
where is defined as in the assumption (iit) of Section 3.1.
We can convert the above results to measure separation with respect to total variation (recall
TV 9)
E, (p(i) ((0) = 2 -lp 9|l1) using the AM-QM inequality l|xx - Py ll S
Vkllpx - py 122 Then, taking R = = 5 ((1) recovers the minimax optimal results of [18; 32; 33], for LFHT over the class PDb. Note that analogous results for two-sample testing follow from the above using the reduction presented in Section 3.4.
Sample Complexity Lower Bounds Recall the definition of J and note that |A|l,, = min(J-11A)
for all J 2 2. By Corollary 3.5 we see that J Z k as soon as S 1/k. Thus, for S 1/h the necessity
log(1/a) m 2 k2282 n 2
Vlog(1/a) and m + /mn 2
Vlo((1/a)
(11)
Viea
Vieao
follows by Theorem 3.2. Here it is crucial to note that when 5 = 0(1), we have
Vlog(1/a) and n 2 vke²
Vlog(1/a)
Vlog(1/a) and 2 Vlog(1/a)
m + Vmn 2
/mn 2
Vke²
vie²
vke²
and hence the upper bound (10) meets with the lower bound (11) provided R 8 O()) Once again, setting R x 5 x = O11) we the optimal lower bounds recovering the results of [18] (in the regime+ 6 5 1/k). In short we can also recover the following result for LFHT.
Proposition B.2 ([18, Theorem 1, adapted]). On the class (bs C), using simulation samples and m real data samples, if
1
n A
mn
(12)
Vke²
KE
VkE²
then for any two distributions Px,Py E Poolk, C) with lipx-Py 122 2 testing (LFHT) is possible with total error of 1%. Conversely, to ensure the existence of a procedure that can test (LFHT) with a total error of 1% for any Px, Py E Pos(ki C) with llpx prll2 2 the number of observations (n,, m) must satisfy
T1 N
Vke²
m
ke
TITE
VkE
(13)
The implied constants in (12) and (13) do not depend on l and e, but may differ.
B.2 3-Hölder Smooth Densities on [0, 1]d Under ( SSeparatin
Sample Complexity Upper Bounds Let PH(3, d, C) be the set of all distributions [0, 1] with
3-Hölder smooth Lebesgue-densing p satisfying ||plic < C for some constant C > 1, where
(x) - - (())
lpplcc
max 0310
sup ==vE[0.1j
||x - v112 1-1--11
where [ 1] is the largest integer strictly smaller than 3 and |a| E, a; is the norm of multi-
index E Nd. Abusing notation, we also use PH(3, d, C) to denote the set of all corresponding density functions.
We take K K(x,v) = E, H2,y5 B,}, where {B, (Byb is the j'th cell of the regular grid of size nd on (0, 1j4, i.e., Bj = [0- T.)/k,j/m for j E [x]]d Clearly there are n nonzero eigenvalues, each equal to 1. The following approximation result is due to Ingster [28], see also [4, Lemma 7.2].
15

---

Lemma B.3. Let f.g E PH(3, d. C) with |lf 2ll2 2 c. Then, there exist constants c, c' independent of such that for any K 2 cE 1/8
MMD(f.g) c'llf -
Now, suppose that we have samples X, Z of size n, nt m from Px, Py, Pz E PH((,d, d, C) with densities Px, P2 such that ||xx Py 2| 2 Then, Theorem 3.1 combined with Lemma B.3 and the choice K c1/
1/8 shows that
Proposition B.4. Testing (mLFHT) PH(3, d, C) at total error a using simulation and real data samples is possible provided
C log(1/a)(1 R)²
log(1/a) R)²
min
8262
8262
CllAll2 log(1/a)
[og(1/a)
min Vnmj
Z
288
(28+d/3)/88
where is L Li-dittance lower bound between Px. Py and R is defined as in the assumption (tii) of Section 3.1.
Setting x a x 8= ((1) recovers the optimal results of [18] for the class Ph. Once again, identical
results under L separation follow from Jensen's 's inequality || ([o))() I || ((o.)() Note that analogous results for two-sample testing follow from the above using the reduction presented in Section 3.4.
suitable for constructing lower bounds over the class Ph because its eigenfunctions do not necessarily lie in Ph. would be possible to consider different kernel that is more adapted to this problem/class but we do not pursue this here.
Sample Complexity Lower Bounds The kernel defined in the previous paragraph
B.3 (3, 2)Sbolee Smooth Densities on IRd' Under L SSparattion
Sample Complexity Upper Bounds Let Ps(B, d, C) the class of distributions that are supported on Rd and whose Lebesgue density p satisfies [|p|a,,2 S C, where
||lla,2 [[ || II) Flill1
(14)
and FF denotes the Fourier transform. Again, abusing notation, write Ps(3, d, C) both as the set of distributions and the set of density functions.
We take the Gaussian kernel G (x. v) rー exp(- vll5/0²) on X = RR with base measure du(xx) = >xp(-x2)dxx. In [37] the authors showed that the two-sample test that thresholds the Gaussian MMD with appropriately chosen variance o² achieves the minimax optimal sample com- plexity over Ps. when separation is measured by L². A key ingredient in their proof the following inequality.
Lemma B.5 ([37, Lemma 5)). Let f,g Ps(3, d, C) with Ilf gll2 2 Then, there exist constants é independent of such that for any S ce-/8, we have
MMD(f. 9) 2 e' llf gl12.
Now, suppose that we have samples X, Y, 2 of sizes n, m from Px, Py, Pz E Ps(8, d, C)) for some constant C with densities Px Py PY. Py satisfying |px py lla 2 6.
Note that the heat-semigroup is an L conttraatiio (|All & 1) and that
|A / /Golo,,) (dd(r,,))d((z)ddld ad
up to constants depending the dimension. Theorem 3.1 combined with Lemma B.5 and choice 1/9 yields the following result.
16

---

Proposition B.6. Testing (mLFHT) over the class Ps with total enorr a is possible provided
Cl log(1/a)(1 R32
log(1/a)(1 - R)²
min n} 2
8²
6º
C||Al|2 1og(1/a)
/lo((//a) (2844/3)/88
min vum
228
where is the lower bound on the L distaacce between Px, Py and R is defined as in the assumption (iti) of Section 3.1.
Taking R x 6 x a= (1) above, we obtain new results for LFHT and using the reduction from two-sample testing given Section 3.4 we partly recover [37, Theorem 5J. Only partly, because the above requires bounded density with respect to our base measure du(xz) = exp(-x²)dr.
Sample Complexity Lower Bounds Note that our lower bound Theorem 3.2 doesn't apply because the top cigenfunction of the Gaussian kernel is not constant. Once again, more careful choice of the base measure (or kernel) might lead a more suitable argument for the lower bound. We leave such pursuit open.
C Black-box Boosting of Success Probability
In this section we briefly describe how upper bounds on the minimax sample complexity in the constant error probability regime (a (1)) can be used to obtain the dependence log(1/a) in the small error probability regime (a o(1)). We will argue abstractly in way that applies to the setting of Theorem 3.1.
Suppose that from some distributions P1, P2....., P& we take samples X .x.....xX _ of size n1, .2...... ng respectively and able to decide between two hypotheses Hg and H1 (fixed but arbitrary) with total error probability at most 1/3. Call this test as (1 X²) {0, 1}. so that
P(V ,.... SUUXX"...,XX. x = Ho) 2 2/3
and P(V(X) x²) = 1181) 2 2/3.
Now, to each an error o(1), instead, we take 18n; log(2/a), 18n, log(2/a) observations from Pi through Pk. and split each sample into 18 log(2/a) equal sized batches {X*.] (E(AA),E loggo/// (2)(2/a)] Here log(2/a) assumed to be an integer without loss of generality. The split samples form 18 log(2 (2/ a) independent binary random variables
A₁ A (X X
for j = 1,2,... 1..2...,1111g/222 18gog/)/a). We claim that the majority voting test
{
1
V. (aX'
otherwise
tests Hg against H, with total probability of error at most o, where
18 log(2/a)
Ā A
Σ
A
18 (2/a)
Indeed, by Hoeffding's inequality, we have
P ( 1/2 Ho) & a//2
A = 1/2 H1 S a/2.
Therefore, in the remainder of our upper bound proofs, only focus achieving constant probability of error (a = (1)) as the logarithmic dependence follows by the above.
Remark C. As mentioned in the discussion succeeding Corollary 3.5, we do conjecture the light dependence in the upper bound to be / 11o instead of log(a -1) shown by this method.
17

---

D Proof of Theorem 3.1
D.1 Notation and Technical Tools
We use the expansion
( (vee(())eel))
extensively, where - A1,......) are K's eigenvalues (regarded as integral operator on (z)) in non-increasing order and 61, f..... are the corresponding eigenfunctions forming an orthonormal basis for (p),, and convergence is to be understood in (u)). We use the notation (-) _ f dd. For all u E (p) we define
Ue (uez), uee A (uczer); = 1,2,...
and consequently Ee ugee. We also define
K-ui(-) - f
(((t, ((tt)))(t)p(ddt
Σ deurer()),
where the second equality follows from the orthonormality of {ee) Note that the RKHS embed- ding satisfies 0n _ [ [xx ))(x))d((x)) = K[u]. Now, for Px we write
Ft (px)e (pxet), Jee' - (px)ee (xxece)),
1,2,
where x the j-density of Px. The similar notations also apply to Py, The following identities will be very useful in our proofs.
Pz.
Lemma D.1. For each identity below, let f,g.h (p) be such that the quantity is well defined. Then,
|10 |10,1|2x
Σ Nole
(15)
MMD Exelfe-
(16)
|K111 1
(17)
Σ Nefese (fK(g)) (K(fl9)
(18)
Σ dedehee fege (hK())K(g)
(19)
E
Σ gexe Σ Xe(fecKlgel).
(20)
Suppose that f. are probability densities with respect to μ that are bounded by C. Then
0 Σ ded See S Ca1111E.
(21)
Proof. We prove each claim, starting with (15). Clearly
|10,
K [[]l
/ K(a, ((x,))(())dd()))
2
/ (K((,)), K(y. - Mr /ww.
Σ Xes?
18

---

as required. The second claim (16) follows immediately from (15) by definition. For (17) by orthogonality have
||[l| Σ xefeeell
Σ X252.
For (18) by the definition of K[-] have
Σ Erelese [(E 10
(K(()))-
For (19) write
rete ((I Xeguer hee
Σ
rederree fige
8.
Σ (ele(K(o)hee>
= -KKlg)nK(f).
Finally, for (20) we have
se (EE xegerre (Evergerce) fel
rede = Σ de
- de(Kgeee)
Suppose now that f. g are probability densities with respect to μ that are bounded by C > Let X, Y be independent random variables following the densities f.9. Then
[ Σ [xeeeXiee(r)) |
Σ xed ferger = E E2
C f J E (xee(())e(())) dp(z)dμ(v)
= C2 |
as claimed, where we used that the et are orthonormal.
D.2 Mean and Variance Computation
We take 8/2. Our statistic reads
T(X, Y, Z) + > Y, = (0pz (#0p) + 1 :002)).0p5 - Biy)a,H
k(X;, 2z)
nm Σ kYY, 2z)
1
2
Σ X(x,,xx)
n2(n 1)
2x
k(Y,, Yo) + # π
+ (n 1)
k(X..Ys).
n2
IV
19

---

Recall that // arg yeR 22
Let write 2 1
where the residual term is denoted as E (P)... Let 8, = (rt ))( be the mean embedding of r. Under both hypotheses we assume that ||0,||иı R MMD( .yy) moreover (0r, Py 0px 0 by the definition of v. We look each of the 5 (2) 15 terms of the variance separately.
var(I) ((11)=Eap
dede n(n Exederfne 1)m 2,22 Dag + nm(m 1)(ee) x1D0 2212
+ nmm[wwzw -2000220000002)))
var(II)= Ededef (aee 1)m zize Jyeee + rmm(m 1)(ee yeyee ) 2zEZ
221
+ nnm(ye ye (1)z))zz))
var(III) - reder ( (2ter - 222220
(n)
12
2
n
4
1
(ree xeze Joere)
2
2
4
18
var(IV) = Σ
seder (m)
11
(vée - viv2) +
11
11
(4)
n
(see - yeye yaye
2)
2
E8
var(V) = Jedderfn (n 1)(yer yeye IrET + n2
1)(e zzZe Webe
221
+ n² (xee - xxeeeeee)
For the cross terms we obtain
cov(I, II) Σ Andemmllzee - 2222 JrEVe
EP
cov(1, III) = Σ
Xedeminn - 1)m - xgye )
Et'
cov(1, IV) =
cov(1, V) = Σ
Xedene x(T 22
E
cov(1l, III) = 0
cov IV) Σ
Xedernin - 1)mluuer yeye zeye
E
cov(1l, V) = Σ
Xeden2 - Beye 2200
Et
cov(Ill, IV) =
cov(Ill, V) Σ
Nede (n-en22--11(xe)) 222 )
E
cov(IV = Σ
xeden 11) (eee)
8
20

---

Note that (2) (2) (2)(
(3) n(n 1)² n(n 1). Collecting terms, and simplifying, get
the coefficient of the 1.2 n
term:
deder Cocf (2) = Σ E
(ree ( DEDE))22 (e + (yee - Yeyl Jzeze + (x - xEWe )xeae
var(!)
var(Il)
var(Il))
4m "nne -eye Weye ( - (T) - YeVe DoEE + ( - > - x800 Weye
var(IV)
var(V)
4th (xee DE0E ) 2 x)(x - xgze )eeye'
cov(1.111
cov(1.V)
(y Yeye 220y - 2( =)(y yeye 2200
cnv(II.VV)
cov(II.)
4 (x 2ea Jarye
4m π) (uer yeur yueae
(ll()
(IV
After expanding 2ς as 2e Dzg + yBe + we split the calculation into multiple parts to simplify it. First, we focus on terms that are multiplied by (Zee ZgZee) and do not contain rt or re. Using Lemma D.1 extensively and the fact that ã = n. D =1- - v, we find that the sum of these terms equals
12 (xK[y)> (0v(cK 22x 2 (x][[=1) -
x²
( + -)) [y)} (f
+ 45
+ 2( -
2(
2( x)u(ok(())
(xK[x -(V ) (/)
SC |/ MMD2 (P,, Py).
Similarly, the terms involving (yee yeyer) but not re or re sum up the quantity 2
v| - [uK( - u/}?) S C/ MMD Py). Next, collecting the terms involving both (zeer ) and rr or To we get
(yK[x (x)
[[]] (z< + (xK(r]3) - (z)
20(c (xK])) (x](T)))
[a<x K [r]) + (=)
+ 2( - (z K [r)) - 2( (x (x=
=2( - 2 (z=Krr v)) (xk(r) w|)) (xK(T)))) (xIK(r))
SC | (R + RR²) MMD3((x.... Py).
Finally, collecting the terms involving both (yerr vege.) and re re we get
2(v 2T)) (y =)) (yK())))) =1)) + (y](r13) (r)) S CIA + R²) (Px.
Similarly we get
- m
Coef
Erede
(z (zw- z2z0 )1EF3 + (zt z420 Weee 2(ze0 ze Jaewe
var(1)
var(I)
cov(1.11)
(=K(æ y]3 (17)-(zk)) (2K(z =
S alAlllo MM. PP.)
21

---

The remaining coefficients don't 't rely on subtle cancellations, and simple bounds yield
Coef
mnn-11)
Σ E6
Aede
4
2 Glo8e
1
(ate ZgZe JaiTe xZxx3e
nnn
vur(Ill)
(1
+ 4x²
:(uir -Zbu²) (yee yeye Jyeve
2
var(IV)
2 1
Coef
1
Σ
tede
((zee zeze )x:0
(xee x2z0 2202
(x1 2220
mum
var(!)
(zw
ZzZN
Yyeye
(yer
yeue
zzze
(ye YEye
var(I)
11121112
Coef
Σ
xede
yeye doEEE (xe xeDe Jyeye + (xee xxye ( T) (-(yee
n
E8'
var(V)
1A
Summarizing, we' ve found that
v -X,,, x
(-+
Cl +R) Pr)
m
(22)
c 1I
nm
Using that (0,,0py - Hx = 0, we compute the expectation to
E [-T((X,), Y, Z) (X,Y,, = (r (PM Py).
Taking π - 8/2 and applying Chebyshev's incquality shows that there exists a universal constant > 0, such that the testing problem is possible constant error probability (say 5%). provided that the sample sizes m, n satisfy the following inequalities:
min n} 2 Cl (1 + R²)
8222
C|AAI2
min V 2
SE2
By repeated sample splitting and majority voting (see Appendix C), we can boost the success probability of this test to the desired level 1 - by incurring multiplicative @(log(1/a)) factor on the sample sizes n, m, which yields the desired result.
E Proof of Theorem 3.2
E.1 Information theoretic tools
Our lower bounds rely on the method of two fuzzy hypotheses [50]. Given measurable space S, let (SS) denote the of all probability measures on S. We call subsets M(S) hypotheses. The following is the main technical result that our proofs rely
22

---

Lemma E.1. Take hypotheses Hu. H1 S ((() and Po. Pi E M(S) random with P(P: E H,) 1.
Then
1 2 TV(BBB,
inl max sup P( + 0, rett,
where the infimum is over all tests vp X + {0.
Proof. For any v)
max sup =001 P.CH
+1) sup (Po(y) = Pi(e== = =0)
2 F.HH.
E Polv 1) + P (v = -0)
Optimizing over db we get that the RHS above equal to (1 TV(E Po. E Pt)) as required.
Therefore, prove lower bound on the minimax sample complexity of testing with total error prob- ability a, we just need to construct two random measures P. E H; such that 1 - TV(E Po, P1) a(ar). In our proofs also the following standard results on f-divergences.
Lemma E.2 ([43, Section 7]). For any probability distributions P. Q the inequalities
1 1 1 -VV((P.Q) exp( (xP(-KL(P)Q)) 2 2
1
1
21 21 21+
hold.
Lemma E.3 (Chain rule for x2 -divergeence.. Let Px,y, Qx,y be probability measures such that the marginals on X are equal (Px- = Qx). Then
(xxx XXXxxxxXXXXXXXXXXXXXXX
Proof. Let Px,,,xx,y have densities p, with respect to some μ. Then, by some abuse notation, we have
(Pxxr =-1 /
p(a, p(a,,)² u)
du(r,y)
g(x, v)
--1+ f
p(ulo)) p(x) du((,, v)
((y(a)
| p(x) /
plullo22
-1) du((, x)
= ((PPxxx11QxxxX
E.2
Constructing hard instances
Recall that in the statement of Theorem 3.2, we assume that y((²) 1, supzex K(x,z) < 1 and K (a, v)u(dx) >1. Let fo and for each E {#1) define
fn =1= Σ Pympez
(23)
J22
Egn
where {pz3222 is chosen as Pj 1(2 < J S JWATs/AA/2... where we define ||||2,J
V Eesjes X3 for some 2 Notice that f (=)x))(d = μ(²)
due to orthogonality
of the eigenfunctions. Assume from here on that is chosen so that for r) we have f7(x) 1/2 for all æ E X. This makes f, into valid probability density with respect to the base measure μ. Before continuing, we prove the following Lemma, which gives a lower bound on the maximal J for which f, 2 1/2 for all 17.
23

---

Lemma E.4. J S J holds provided 2evJ-1 S ||
Proof of Lemma E.4. Notice that
|leyllo - sup (K (K, < sup [K(x,, Mllllllll s Vx sE
(24)
ZEX
where we use [x, 11p = v (K(x22) 2.).
We have
1, = <|| Σ
PM = =suup [[r
<(sup((Tr, :) Σ Epmess
J22
NEX
J22
EVJ
$ <<ll Σ
Pymeell =
Σ 09/2,
||ll,,j
J22
122
and the result follows.
Note that Lemma E.4 immediately gives us proof of Corollary 3.5.
Proof of Corollary 3.5. Suppose that J is such that Σド= X3 2 e 1111 Then, by Lemma E.4, e < [2 1) then J < J By assumption, this is implied by the inequality <
(2V]=/ and the result follows.
Continuing with our proof, note that by construction have
M/. = 1xp0==e E
(25)
322
E.2.1 Lower Bound on m
Again, we apply Lemma E.1 with the new (deterministic) construction
Po #M @1+ / X2) & (1+6cez) Az) 28m.
= f0 o & 3000. (26)
where we write f1 ((.,....)) and similarly for 91- By the data-processing inequality for x²- divergence (also by Lemma E.3), we may drop the first 2n coordinates and obtain
(PP = x21(11 + S6e2/ V A2)
8m mm (
(1 + 5262 (2/
$ exp
1.
d2
By Lemma E.2
1-) Z
(2(E).EPR)- 2 cxp(-83 ((a).
The lower bound m 2 A2 logglo////0// (1)))(/)))(6 now follows readily.
E.2.2 Lower Bound on
Once again, apply Lemma E.1 to the construction
6on Po fo
X fn
8n
26om
Pi f0- @ fo 8n @ f0m
(27)
where we put uniform prior on v [ before. Using the subadditivity of total variation under products, we compute
EP,
TV & HE R @m 69 f
2'V 1 -
24

---

Just as in Appendix E.2.3 we upper bound by the diveereeee to get
x2(1E: [ (E ") 1 + Ean / (1)
==1
1 + E exp(ne Epnmm))
j22
=-14 + II cosh P9)
.22
S - + exp(n2 cd Σ
p3)
j22
= =- + x /1111
Again, by Lemma E.2 obtain
1 1 TV(E) 2(EPo 2 exp((n' 1 A(a).
The lower bound n 2 Vlog(1/a)]lMla./// now follows readily.
E.2.3 Lower Bound on
We take uniform prior 1 and consider the random measures
Po for
S 2 ((1 fo + fff)) )
and
Pi =1= @ f X fm
(28)
Our goal to apply Lemma E. P1. Notice that (1 - 8) 8f, + degn. Let us write X, Y, Z for the marginals first n. second n and last m coordinates of Po and P1. By the data processing inequality and the chain rule Lemma E.3 have
(B P1)
x(E Po)r, (E Pi)y;)
>²2(EE ((IEPo)zyy l (E Po))) E (E (1 + deg,)) 60m Y] (1 =: (t).
Notice that the expectation inside the diveeregee is with respect to 1 given the variables Y, or other words, over the posterior 1) with uniform prior given n observations from the density 1 + <gg f.. The outer expectation is over Y. Given Y, let and o/ be i.i.d. from said posterior. We get the bound
(t) +1)+ E II
[1 + Seg, (z:)) + deg, (I:))p(dx;)
E(1 + 5²2²
p
J22
<Eep((0 2m
Σ
122
Define the collections of variables 7-; = {11 \ {mp}} and v'a, similarly, We shall prove the following claim:
E (e nーン" (5 mn)p?)
(29)
for some universal constant >> 0. Assuming that (29) holds, by induction we can show that
(f) + < exp(c6 + mn)e Σ
322
= -x m² + mn)e /
Thus. if mn + 8m2 (1>')),,/66''')) then testing is impossible.
25

---

We now prove (29). Since the variable 7//77 is either 1 or -1, we have
E exp(6 coxp(82emmpp) empp)n - = (e pmp e 2 P(n = -nn + Amm
Let us write 7 for the vector of signs equal to but whose j'th coordinate is #1 respectively. Looking at the probability above, and using the independence of 77. 7/ given Y, we have
P(nn) = 1|V, n-)) = P(n; = 1y, P(1; = n
(f (Y)) + (f (Y))²
(2 (Y) + 2 1, (Y)) 2
Taking the expectation E1- 17 v/55] and using the HM-AM inequality (5 + 4)) s + valid for æ, y > 0 gives
Th= Syn (xa))² + (TT Jn 15 (mx)))
F(n.n' 1|m-). -
p(dx)) ... u(dxn)
3 I san (ri) + 2 -11- sn-1, (Ii)
1
[ Soy (xi))² (Tk- In (1x1))
$
u(dx)).. ... ((ddx))..,((zz,)) (x).
8
I Ims (1:) (mi(
Note that [n, sn-13 Pepzeg.
Using the lower bound f fanis (x) 2 for all x X and the
inequality 1 S exp(x),, get
1 (+) 5 + 8
|+
462 (6203e3(0)
) +
11 "+(1+
/
462 462
u(dcr) )]
In (x)
Jms (x)
s H + @cenott @
Recall that (+) is probability (+) S 1, and we obtain
(+) (1 Ge n833n3))
Putting together and applying Lemma E.5 we get
LHS of (29) S (e (eppm -5- 2 1 1 (1 + se3mo3glu3) + ppp
nB2 2 (m2
for universal c= = 16 O. Thus, by Lemma E.2 we obtain
- -V(PEE. Z Po. EP) 2 exp( (60m=
1 2(a).
The necessity of
log(1/a)|l>133
mn + 8mm2
82e4
follows immediately. 3
Lemma E.5. For a, b 2 0, the following inequality holds:
1 (e - e eaa) + AMm + t - 2(ab+aa),
Proof. b 2 I or a 2 we have:
LHS < 4 (c e -- 1n + a S aaagatt
b < In3 and a < 1, we have
b <
2
1 26,
@ a
< 0da²
ea e e- a S 20,
In3
2
2
We have mn m² & (Vmn + m)² < 2(mn m² /mn + Vmn m²
26

---

and then
e
4 (e - E] +..) te
2 fee +e =)))
cea - e
4
$ e + 2ab
2 "²
(1 + 2ab)
c +2ab
The result follows from In3 1.
F Proofs From Section
F1
Computing 6
We follow the implementation of 62 [39]. Given XI...., X sampled from Px and YI, Yi,..., Y sampled from Py, denote
Hi (X, xx) + (Y, K (3) , i.j E [nd..
(30)
Then 0² is computed via
2
2
Tly
Tle
Ry
0² (X y K)
Hij
Hij
(31)
Tlar
i1
Note that 62 being non-negative follows from the AM-GM inequality.
F.2 Heuristic Justification of the Objective (8)
As usual, let X, Y. Z denotes samples sizes n, nt, m from Px. : Py, Pz respectively. Let us give a heuristic justification for using the training objective defined in (8) for the purpose of obtaining kernel for LFHT HOHTT/LFFH FLL.HT. Note that originally was proposed as a training objective for kernels to be used in two sample testing. Recall that our test for LFHT can be written as
V 11/2
{ TLE 2 20}
where
TL MMD? (Pz, K) MMD (x:;
Heuristically, to maximize the power of (mLFHT), we would like to maximize the following popula- tion quantity
JUF A Eo [iF - [TiF]
varu(TLF)
where
Eo[TiF = Ex,v [TF Pz Px] MMDD Py; K);
Eg [TL]] = Ex,y [TL ( Pz = Py] - 1M-MM (Px,) Py: K).
Let Tis AMM,((xx Py) be the usual statistic that is thresholded for two-sample testing. Then, computation analogous that Section D.2 show (cf. (22)) that
(aro(IiF) ~ A(K, Px, Pv) + Ax,,Px, + B(K, (IK,Px,PP) + B(K, Px, Pv)
n2
A(K,Px, Pv, PK,
(TTo) R
n2
for some A(K) and BK)). Therefore, we have approximately
2 MMDD Pr; K)
JLF ~
V1 m
varo TTS)
2 2,
V
m
+
J(
27

---

which only differs from our optimization objective defined in (8) by constant factor.
Second, notice that MMD(Px,Py:K) depends only on Px Py and that ((1 8) + +Py) Px &
var(Trs)
Py Px. therefore is sensible use (8) as our training objective for is also sensible for (mLFHT),
and we don't even need to observe the sample Z.
F.3 Proof of Proposition 4.1
Proof. In this proof regard D a (X" _ Y", yY) and the parameters of the kernel fixed. Recall that we are looking at the problem mLFHT with a misspecification parameter R (see Theorem 3.1). Given test set {24 hiefm) test statistic is (((2)e)(m) E f(z)) where
Bey
[(z;) =
Σ j=1
(2s: XT1))
Thev
In Phase of Algorithm observe the value 7 = T(Z)
E ((zz) and reject the null
hypothesis for large values of T. Thus, the p-value defined as
p = D(Z,D) - P P- (T(Z) T).
Phase 2 of our Algorithm produces random variables T,.... Ts that have the distribution of T( Z2 [e(m)), so that 11T, 2 T) (r (r= 1,....k) are unbiased estimates the p-value. However, the Ti are not independent, because they sample from the finite collection of calibration samples X=a
However, as Real + Do the covariances between Tr Try for TT # r2 tend zero, and we obtain consistent estimate of p.
F,4 Proof of Proposition 4.2
Proof.
The test statistic T(X, Y, 2) in (3) is given by
T(X,Y,2) 1 Σ f2
1=1
where
fk(2) fg (2) pppxxxxx (2). (2).
This simplifies (consider K(x,y) f(z)(()))
1 f(3)) - - ((x)))
fk(2)
where C(X,Y) does not depend on z. Therefore, for any witness function f, we obtain the desired additive test.
F.5
Additive Test Statistics
In this section we prove accordingly that the test statisties of all of MMD-M/G/O, SCHE, LBI, UME, RFM are of the form (2) Em 1111 f(2;) (where f might depends on X, Y). The test is compare T2( (Z) with some threshold (X,
Note that in the setting of Algorithm 1, the X and Y here correspond to X and yev
MMD-M/G/O As described in (3) we have
T,(2)
(K Y2) -((Z,))))
1=
28

---

SCHE
As described in Section 4.2 we have
Tz(Z) 1(²(2)) > 1).
LBI
As described in Section 4.2 we have
log 2(Z)) ==1 1 ò (2.)
Ty(Z)
UME
As described in [31], the UME statistic evaluates the squared witness function at Jg test (wx Jn X. Formally for any distributions P, Q we define
locations W
J4 Σ (wq(ws) 0p(ww)) Jq
1
U2 ||0g - 0p112a(w)
However, note crucial difference that their result only considers the case of n m, and their proposed estimator for (P2, Px) can not be naturally extended to the case of n + m. Here we generalize it m f where we (conveniently)
biased estimate of their distance. Given samples X, Y, Z and a set of witness locations W, the test statistic is a (biased yet) consistent estimator of (2,P,, Py) (P2 Px). Let (/w(2)
(Kl (2, wI)..... K(2, w.,)) RR| the "feature VJg
function," then:
1
(2,
dw (Zi)
ww (Xi)
71
j=1
2
ww (Zi)
+
dw (X:)
2
Σ
(Vw (Zi) s/w (X,))
ISiSM,IS/S
Here (..) denotes the usual inner product. Therefore, the difference between distances is
m
n
(( m
vww (Zi).
72 Σ (sbw (X,) 2'w (w)()))) F(X,Y)
where F is sum function based only on X, Y. This is clearly an additive statistic for Z.
RFM Algorithm 1 in [44] describes method for learning kernel from data given binary classification task. For convenience lets concatenate the data to XRFM = (X,Y) E R2axd and
labels y RRM (Ōn, Im)) E R2122n Given a learned kernel K, we write the Gram matrix as (K(X (XRRMM XRFM))),, [XXFFM X.FMM)) S i,j S 2n). Let K (XXRFMM 2) be column vec- tor with components ((X RFM 2) (1 < < 2n). The classifier is then defined as
RFM
RFM
K K(X RFM XREM)-1, K(X
(32)
Though in [44] the kernel learned from RFM is used to construct a classifier as in Equation (32), since RFM feature learning method, we also apply the RFM kernel to our MMD test, namely
RREM MMD (2) (K(2,Y,) K(2,X,((,))
G Application: Diffusion Models vs CIFAR
We defer more fine-grained detail to our code submission, which includes executable programs (with PyTorch) once the data-generating script from DDPM has been run (see README in the Jcodes/CIFAR folder).
29

---

Figure 5: Data visualization for CIFAR-10 (left) DDPM diffusion generated images (right)
G.1 Dataset Details
We use the CIFAR-10 dataset available online at htttps:/wwwr
tooootoooooo.. www.wkrri///eeeaeeeee cifrr html, which contains 50000 colored images of size 32 x 32 with 10 classes. For the diffusion generated images,
the SOTA Hugging Face model (DDPM) that can be found at https: / //uugiiggface co/ google/ ddpm CIFAR- 32. We generated 10000 artificial images for our experiments. The code can be found at code supplements.
For dataset balancing. we randomly shuffled the CIFAR-10 10 dataset and used 10000 images as data in our code. Most of our experiments are conducted with the null Px as CIFAR images, and the alternate as Py
CIFAR + 3 DDPM. To this end, we matched 20000 images from CIFAR to belong the alternate hypothesis, and the remaining 30000 images stay in the null hypothesis. For the alternate dataset, we simply sample without replacement from the 20000 + 10000 mixture. This sampled distribution is almost the same as mixing (so long the sample bank is large enough compared to the acquired data, so that each item the alternate has close to 1/3 probability of being in DDPM, which is indeed the case).
G.2 Experiment Setup and Benchmarks
We use a standard deep Conv-net [40], which has been employed for SOTA GAN discriminator tasks in similar settings. It has four convolutional layers and one fully connected layer outputting the feature space of size (300, 1). For SCHE and LBI, we simply added a linear layer of (300, 2) after applying ReLU to the 300-dimensional layer and used the cross-entropy loss train the network. Note that this equivalent to first fixing the feature space and then performing logistic regression to the feature space. For kernels, add extra trainable parameters after the 300-d feature output.
For the MMD-based tests, we simply train the kernel on the neural net and evaluate our objective. For UME, we used slightly generalized version of the original statistic in [31] which allows for comparison on randomly selected witness locations in the null hypothesis with m * n (sce Appendix F.5). The kernel is trained using heuristic (see (8) and Appendix F.2), with MMD replaced by UME. The formula for UME variance can found in [31]. For RFM, we use Algorithm 1 in [44] to learn a kernel on (stochastic batched) samples, and then use our MMD test the trained kernel.
We use 80 training epochs for most of our code from the CNN architecture (for classifiers, this is well after interpolating the training data and roughly when validation loss stops decreasing), and batch size of 32 which has a slight empirical benefit compared to larger batch sizes. The learning rates are tuned separately in MMD methods for optimality, whereas for classifiers they follow the discriminator's original setting from [40]. In Phase 2 of Algorithm 1, we choose l 1000 for the
30

---

MMD M
MND MyThrashaldl
RPM
MND
Rejection Rate (alpha=0.05)
False Positive Rate
Expected P-Value
Error Probability At 0
0.1
0.33
03
54
0.2
20
206
250
200
220
330
353
106 330 306
m 400
56
280
353
200
250
200
356
28
100
250
250
250
300
326
m
m
m
Figure 6: Relevant plots following the setting in Figure (in the main text) of fixing fhr = 1920 and varying sample size in the x-axis for the comparison with missing benchmarks. Errorbars projected showing standard deviation across runs. We replaced part (d) in Figure 3 (in the main text) sanity check in our FPR when thresholded at 0.05.
desired precision while not compromising runtime. For each task, we run 10 independent models and report their performances as the mean and standard deviation those 10 runs as estimates. We refer to full set of hyper-paramann parameters in our code implementation.
Our code implemented in Python 3.7 (PyTooch 1.1) and was ran on an NVIDIA RTX 3080 GPU equipped with standard torch library and dataset extensions. Our code setup for feature extraction similar that of [39]. For benchmark implementations, our code follows from the original code templated provided by the cited papers.
G.3 Sample Allocation
We make a comment on why (4) is different from just thresholding MMD (Z, YT) MMD (Z, X O, which what did in part (c) of Figure 3 (and hence the difference along the curve of MMD-M vs Figure 1.2). Our theory assumes that the samples are i.i.d. conditioned on the kernel being chosen already. However, in the experiments, the kernel is dependent on the training data. Therefore, to evaluate the MMD estimate (between experimentations), one needs extra data that does intersect with training.
In fact, it can experimentally shown by comparing Figure 1.2 and Figure 2(c) that doing so (while reducing the sample complexity on ngy) hurts performance. Indeed, we found out that when X Yev are non-intersecting with training, performance (almost) always better at a cost of hurting the overall sample complexity of n.
G.4 Remarks on Results
Figure 6 lists all our benchmarks the setting of Figure 3 (in the main text) on missing benchmarks, where the last figure is replaced by the false positive rate at thresholding at 0.05 to verify our results. As mentioned the main text, our MMD-M method consistently outperforms other benchmarks on both the expected p-value (of alternate) and rejection rate at = 0.05, while all of our tests observe a empirical false positive rate close to a = 0.05% (Part (b)), showing the consistency of methods.
Application: Higgs-Boson Detection
H.1 Dataset Details
We use the Higgs dataset available online http://archiv/ ics uei. edu/nl/datasets/ HIGGS, produced using Monte Carlo simulations [5]. The dataset is nearly balanced, containing 5, 829, 122 signal instances and 5, 170, 877 background instances. Each instance 28-dimensional vector, consisting of 28 features. The first 21 features are kinematic properties measured by the detectors the accelerator, such as momentum and energy. The last properties are invariant masses, derived from the first 21 features.
31

---

Background
Signal
3.5
Above threshold
Below threshold
Frequenc of events
2.5
1.5
0.4
0.6
0.8
1.0
1.2
1.4
1.6
mwao(normalized)
Figure 7: This figure visualizes the distribution of the 26th feature, the invariant mass mo The red and black lines are the histograms the original dataset. We employ MMD-M as classifier, trained and evaluated using fer 1.3 106 and nev Nopp 2 10* through Algorithm 3. The blue(green) line represents all instances 2 whose "witness scores" {2; X Yor)'s are larger(smaller) than opt-
H.2
Experiment Setup and Training Models
The modified Algorithm I is shown in Algorithm 2 and Algorithm 3. Compared with Algorithm 2, we implement the thresholding trick (Section 4.3) Algorithm 3.
H.2.1 Configuration and Model Architecture
We implement all methods in Python 3.9 and PyTorch 1.13 and run them on an NVIDIA Quadro RTX 8000 GPU.
For all classifier-based methods in this study (SCHE and LBI), we adopt the same architecture as previously proposed in [5]. The classifiers are six-layer neural networks with 300 hidden units in each layer, all employing the tanh activation function. For SCHE, the output layer is single sigmoid unit and we utilize the binary cross-entrope loss for training. For LBI, the output layer is linear unit and we utilize the binary cross entropy loss combined with logit function (which more numerically stable than simply using a sigmoid layer followed by a cross entropy loss).
For all MMD-based methods (MMD-M, MMD-G, MMD-O, and UME), the networks and yp are both six-layer neural networks with 300 ReLU units each layer. The feature space, which is the output of the neural network sp. is set be 100-dimensional. Here UME has the same kernel architecture as MMD-M, and the number of test locations is set to be J, 4096. For RFM, we adopt the same architecture as in [44], where the kernel Ka (ar, y) exp(- -pp(-((00 T - y)) with constant y and learnable positive semi-definite matrix M. We set
The neural networks are initialized using the default setting in PyTorch, and the bandwidths a, of are initialized using the median heuristic [22]. The parameter is initially set to 0.5. For UME, the witness locations are initially randomly sampled from the training set. For RFM, the initial equals the median bandwidth times identity matrix.
H.2.2 Training
The size of our training set, denoted as fhtr varies from 1.0 102 to 1.6 x 105, For given we select the first nhr datapoints from each class of Higgs dataset to form Xtr and yo i.e.
y Bar- Subsequently, randomly select rhaalidation min( /10n 0. points
32

---

from each of Xt.. Yr to constitute the validation set, while the remainder of Xtr. Yt are used for running gradient descent. The optimizer is set be a minibatch SGD, with a batch size of 1024, learning rate of 0.001, and a momentum of 0.99. Training is halted once the validation loss stops to decrease for 10 epochs, then we choose the checkpoint (saved for each epoch) with the smallest validation loss thus far our trained model. Beyond the general setting above, in RFM a batch size of 1024 doesn't t work well and instead we use a batch size of 20, 000.
H.3 Evaluating the Performance
H.3.1 Evaluating the p- Value with the Methodology of Algorithm
We call the "witness score" of an instance 2 E X'
f(;; xe)) 1 neaa
neal Σ
k(2,
(33)
For a vector of instances 7 = 07 (Z,,..., 7m), we write
f" y = (f(Z): y f( x )o))..
The testing procedure is summarized in Phases 2, 3 and 4 in Algorithm and Algorithm 3. In the Higgs experiment, utilize the Gaussian approximation method to determine the p-values when the witness function f is not thresholded, which allows us to reach very small p-values and errors under limited computational resource. In cases where the score function f is thresholded by value t, using the Binomial distribution as in Algorithm is more precise and also fast enough.
Given trained kernel K trained on X and Y we set X = X and Yov = Y"", and accordingly Dev = Ter- This results in a more efficient use of data (since we reuse X y also as Xey, yε)). Then, out of the untouched portion of the data, we randomly choose flaal = 20, 000 datapoints from both classes to populate X and ycal, i.e., |Xaa|| = |Ycl| ?aa = 20, 000. In addition to the general setting above, for RFM, we need to solve dimeeniimlll linear equation during inference, which arises from the inverse matrix in Equation (32) (solving K K(XRFM, XRFM)u = REM""" for E ) So we set Rev min( 10, 000) that X Yeu are randomly sampled from the training set.
In order to compare different benchmarks, we evaluate the expected significance of discovery on a mixture of 1000 backgrounds and 100 signals. For each benchmark and each n4r, we train 10 independent models. Then for each trained model we proceed through the Phases 2, 3 (and 4) in Algorithm 2 and Algorithm by 10 times for 10 different (Xee, Xcal, Xopt yev yeal, yopt). The mean and standard deviation from these 100 runs are reported in Figure 8.
We also display in Figure the trade-off'b b (m, nev) and (m, ner) to reach certain levels of significance of discovery in MMD-M. From the bottom left plot, we see that the (averaged) significance is not sensitive Tly when ig Nov is large. So taking Bev 20, 000 is sufficient.
H.3.2 Evaluating the Error of the Test (4)
We set the parameters to be 8 = 0.1 and π = 1ō in our experiments. As explained Appendix G.3, here we no longer take Xev = X Empirically, taking X = X yields a very bad threshold y (eev, yev T). Instead, x is sampled from untouched datapoints other than Xtr, and the same applies for Y. We still take nev
here, resulting in a total size of nev + 74r = 2n. Specifically, when nev 2 10, 000, computing a Nev X Nev Gram matrix becomes computationally expensive, so we adopt Monte Carlo method to compute 7(Xev, Yev л), in which we subsample 10, 000 points from x and yev to calculate y and repeat this process 100 times.
Again, we utilize the Gaussian approximation. Recall that the test is to compare T = 1 En f(Z))
with 7. The type and type 2 error are estimated as CDF (- __XX", -= and /var[f Ho)/m
'If the kernel K(--)) = PE (Tx"",, y²)))]+ + -on (x" y Z)]). However this is no longer true (X" yn and (x*,y*%) intersect.
is independent of XN you then we have 7X"M, y 8/2) x
33

---

3| -X (X*,)% ,r) /varlf
for the witness function f, which can be estimated efficiently
using the calibration samples Xccal ycal.
We consider both the regimes of fixing kernels and varying kernels (training kemel based on n)). The results shown in the top plot in Figure 1.2 and the top plot in Figure 9. For each point on the plot, we train 30 independent models and test each model 10 times, and report the average of these 300 runs. In both plots, we observe the asymmetric m n trade-off.
Algorithm 2 Estimate the significance of discovery of an input Zieat, using the original statistic
Input: (X X X,ai), (Y yev, yraa);; parametrized kernel Kwi input Zuest # Phase 1: Kernel training X and Y # maximize objective J(x", kw) in (8)
arg max opiimizer J(X Y :w)
Phase 2: Distributional calibration of test statistic
Scores (0) < f(X=al, (e))
Scores (0) has a length of naal
Scores - f(Ycal, xev, Yev)
Scores has a length of Yeal
Pg + mean (Scores" (0))
# estimate [ ~ Px]
0, - mean(Scores(1)
# estimate [Z Pyl
do std(Scores )
estimate / var (Z) Px
# Phase 3: Inference with input Zient
m length Zue))
T - T (Ziesi _ Yev) = mean (Zreati N Y
# compute test statistic
Zdiscovery f- T-
oa//m
Output: Estimated significance: Zdiscovery
Algorithm 3 Estimate the significance of discovery of an input Zwat applying the thresholding trick
Input: (X X X X (Y"r, yev, y yopt); parametrized kernel Kwi input Zesst.
Phase 1: Kernel training on X" and Ytr optimizer J(X", Y"; Kw)
f- arg max
# maximize objective T y"; Kw) in (8)
Phase 2: Find the best threshold
Scores t f(Xoot, X ye))
Scores (1) f- opy X Yov) for i = 1,2, Mop do (Scores U Scores [1]
# witmess function in (33)
TP. TN mScnnSsores (1) >> f), mean mean power; = TP-TN-1
# true positive and true negative rate # find t to maximize the (estimated) p-value
VIN(I-N)
end for
topt (Scores (0) U Scores (1) ) max, power,]
Phase 3: Distributional calibration of test statistic (under null hypothesis) Scores (f(Xaal, X y t)
# Scores [0, 1)
Scores (1) - (f( Xey, Yev) > t)
# Scores (1) E [0, 1)"
On + mean mean(Scores, (0))
estimate [[fa(Z) ~ Px] E [0,
0, + mean (Soores
# estimate [ffe ~ Py] E [0.
Phase 4: Inference with input Z
m + length Zres)
T T, (Zusti 0 yev) = mean( (f (Zresti N yov) t)
# compute test statistic
Zuiscovery &- CDF (CDF (CDF (T))
Output: Estimated significance: Zaiscovery
34

---

Eapt
SCHE Eapt
MMD-M
SCHE with t-0.5
MMD-G
LBI
MMD-O
RFM classifier
UME
RFM for MMD
5.0
4.5
discoveryjo
4.0
3.5
3.0
Significance
2.5
2.0
1.5
1.0
0.4
Training set size 2n/million
Figure 8: Complete image of Figure 1.2 in the main text. The mean and standard deviation are calculated based on 100 runs. See Appendix for details.
35

---

Type erro + error
4.0
3.5
0.81
3.0
0.66
(g(ncv)
2.5
0.44
0.20
1.0 10-2
1.5
1.5
1.0
2.4 10-4
6.0 10-22
0.5
2.5
lg(m)
Significance
Significance
21.0
6.0
14.4
18.0
5,5
12.8
15.0
9.6
12.0
5.0
2.0
9.0
4.5
1.5
6.0
4.8
4.0
1.0
3.0
1.6
0.5
0.0
3.5
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
Ig(m)
(g(m)
Figure 9: The top plot displays the (m, nev) trade-off reach certain levels of total error using Mer = 1.3 10 in MMD-M. The bottom figures show the trade-off of (m, nev) and (m, nu.) to reach certain level of significance of discovery in MMD-M. the bottom left figure, fix fer 1.3 10
In the bottom right figure, we fix Tay = 20, 000. See Appendix H for details.
I Limitations and Future Directions
Finally, we discuss several limitations of our work and raise open questions that we hope will be addressed in future works. From the theoretical side of our arguments, we point out several aspects. First, upper bound (on the minimax sample complexity) Theorem 3.1 has a likely sub-optimal dependence on a, 8. Second, it might be possible to improve our lower bound to a more natural form by replacing ||>||..r by |||| and removing the constraint that the top eigenfunction has be constant. Third, it remains open to extend our theory to include data-dependent K, as opposed to fixed K.
Empirically, our proposal Algorithm can be inefficient in Phase 2 (prior works such as [39] have used permutation-baal based arguments for more efficient estimate), which we adopted due to its simplicity and universality in all benchmarks. Moreover, one might hope that LFHT/mLFHT can be extended to more complex applications, such text data videos. Such questions important to investigate as a future direction.
36


Reviews:
[{"review_id": "QHsmB2YkqR", "reviewer": "Reviewer_5XYH", "summary": "This paper proposes a test statistic that can be used for likelihood-free hypothesis testing [LFHT] (for distributions $P_X, P_Y$, given a sample from $P_Z$, decide if $P_Z = P_X$ versus $P_Z = P_Y$) and mixed likelihood-free hypothesis testing [MLFHT] (for $P_Z = (1 - \\nu) P_X + \\nu P_Y$, decide if $ \\nu = 0 $ versus $ \\nu \\ge \\delta$). \n\nThe test statistic is defined as the MMD distance between $P_Y$ and $P_X$ for an appropriately chosen kernel $K$. The paper then shows an upper and lower bound for these two testing problems. These depend on a base measure $\\mu$ and a kernel $K$, both of which can be chosen, such that if $e_j$ are eigenfunctions of $\\mu$, then $K(x, y) = \\sum_j \\lambda_j e_j(x) e_j(y) $. The bounds are then stated in terms of $\\lambda$ (either $\\mid\\mid \\lambda \\mid \\mid_\\infty $ or $ \\mid \\mid \\lambda \\mid\\mid_2$).\n\n", "questions": "See weaknesses section.", "limitations": "The authors discuss differences between the upper and lower bounds, but apart from that, there's no discussion of limitations. There should be more discussion about drawbacks of this approach wrt existing approaches -- surely there must be some based on how general these results are in comparison to existing work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The results are very general with reasonable assumptions. The authors assume that the distributions $P_x, P_y, P_z$ have bounded densities wrt the base measure $\\mu$, and the sample complexity scales linearly with this bound on the density. This is in contrast to existing work, which assumes more descriptive assumptions on these distributions.\n\n- There is empirical support for the asymmetric sample complexity between the train sample $n$ and the test sample $m$.\n\n- The lower bounds are general, in that although they are minimax, they apply for any choice of $\\mu, K$.\n\n- The upper bound allows for distribution mismatch, i.e., the test sample need not be a perfect mixture of $P_X, P_Y$. The bound holds as long as the true distribution is close in MMD to some mixture of $P_x, P_y$.\n\n- This approach also allows for learning a kernel from the data, although the theory bounds don't hold in this case as it violates independence between choice of the kernel and the training samples.\n\n", "weaknesses": "- The bounds are a little non-intuitive / roundabout, as they depend only on the base measure $\\mu$ and the kernel $K$, both of which do not directly depend on the hypothesis class containing $P_x, P_y$. From my understanding, the only place the hypothesis class shows up is that it must have bounded density with respect to the measure $\\mu$.\n\n- The novelty of the results over existing work is not explained fully. Is the main contribution of the work bounds for the mixed-distribution testing? Or is the test statistic and the analysis also entirely new?\n\n- As mentioned by the authors, there is gap between the upper and lower bounds for the training set size $n$ and its dependence on the mixture coefficient $\\delta$. However, I think this is acceptable and a good open question.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the helpful comments in the review and will make sure to address them in the revision. In the following we will address some of the questions mentioned in the review.\n\n1. $\\textbf{“The bounds are a little non-intuitive / roundabout.”}$\n\nPlease see our general response #1. We believed that having a mild assumption on the hypothesis class helps our setting to model real-world tasks better. \n\nOn the other end, indeed the dependency between the trained kernel and finite observations from the hypotheses distributions lacks a satisfying theory. We consider this as a major open problem worth investigating in not only (m)LFHT but also other applications of kernel methods (e.g. two-sample testing [3]).\n\n2. $\\textbf{“The novelty of the results over existing work is not explained fully.”}$\n\nPlease see our general response #2 on our novelty over [1]. To specifically address the other points, a version of our MMD test statistic was indeed proposed in prior work (e.g., [2]). However, the theoretical analysis of the MMD statistic (especially non-asymptotically) on the (m)LFHT problem is novel to our knowledge. We will make sure the novelties are highlighted and contrasted properly in the revision.\n\n3. $\\textbf{“Discussion of limitations.”}$\n\nBeyond limitations in Appendix L, some other limitations include our kernel optimization lacking sufficient theory (and therefore, the upper bound must rely on fixed kernels), dependency on certain parameters being open, and several open questions when model misspecification ($R>0$) is present. We will make sure to include a more thorough discussion in the revision.\n\n$\\textbf{References}$\n\n[1] Gerber, P. R. and Polyanskiy, Y. Likelihood-free hypothesis testing. 2022.\n\n[2] Bounliphone, W., Belilovsky, E., Blaschko, M. B., Antonoglou, I., and Gretton, A. A test of relative similarity for model selection in generative models. 2015.\n\n[3] Liu, F., Xu, W., Lu, J., Zhang, G., Gretton, A., and Sutherland, D. J. Learning deep kernels for non-parametric two-sample tests. 2020.\n"}, {"review_id": "CACt2l9ZoJ", "reviewer": "Reviewer_92Pk", "summary": "The paper addresses a likelihood-free hypothesis testing (LFHT) scheme, where the data distribution is a mixture of two distributions. The null hypothesis is given by one of these distributions, whereas the alternative hypothesis is that the mixture coefficient is lower-bounded by some delta.  The motivation for such a scheme is that it is tied to some applications in particle physics, for example, the Higgs boson discovery. This is a generalization of the original LFHT scheme, which is recovered if delta=1. Goal of the paper is to characterize the tradeoff between n, i.e., the size of the dataset and m, the number of samples available from the mixture data distribution available at test time. Specifically, the authors derive lower and upper bounds on the minimal sample complexity. They also empirically verify this trade-off for kernel based hypothesis testing, where the kernels are parameterized via neural networks.", "questions": "See weaknesses.", "limitations": "Does not apply.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "An interesting result is the dependency between n and m for which the authors derive lower and upper bounds, with a non-trivial trade-off  between these quantities. It seems though that this was already addressed in prior work, but this is not my research area and I may be missing other contributions.", "weaknesses": "It seems that the applications for the proposed mixture LFHT are quite limited. In particular, the Higgs boson discovery is a very specific application, and therefore it is unclear whether this work extends to other key applications.\n\nThe authors mention in Section 4 that the results from Theorem 3.2 cannot be directly applied because of the dependency of data and kernel. This is not clear to me. Isn’t the main idea of a kernel that it is learned from the data? It also seems to be the reason why their proposed generalization bounds cannot be included in Fig. 1 as a reference, which questions the usefulness of these bounds as fundamental limits of the scenario at hand.\n\nThe statement in line 274 seems like a trivial observation, typically the validation set is always chosen much smaller than the training set.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the helpful comments in the review and will make sure to address them in the revision. In the following we will address some of the questions mentioned in the review.\n\n1.$\\textbf{”It seems that the applications for the proposed mixture LFHT are quite limited.”}$\n\nOur motivation for defining mLFHT is in fact very much practically driven: if one tries to model high-energy physics (LHC) or gravitational waves experiments (LIGO) those typically do have an alternative (non-null) hypothesis under which samples come from a mixture of noise and signal distributions. One good illustration of the interest of the physics community is [4] with over 8000 citations which studies a problem essentially equivalent to mLFHT in an asymptotic and parametric setting. Furthermore, since it is both an extension of LFHT and two-sample testing, mLFHT shares many applications arising therein (e.g. generative model comparisons, bioinformatics, etc, [1, 2]). The main objective of this work is to propose a theoretically provable efficient algorithm that is also practical in handling real-world data (which is well-modeled by our mixture framework), including the two examples shown in this paper. Specifically, what is crucial in the mLFHT setting is that despite the fact that the weight of the “signal” component in the alternative hypothesis can be very small, the number of simulation samples does not need to be large because the simulation samples can be forced to come directly from the signal component of the mixture. This prevents a certain kind of “curse of dimensionality” as we attempted to explain in the last paragraph of Section 3. We will make sure to explain the motivation and novelty of mLFHT more clearly in a revision. \n\n2. $\\textbf{“Connection of Figure 1 and Theorem 3.2.”}$\n\nAs you point out, our theoretical upper bounds rely on an a priori fixed kernel, while in our empirical experiments we train the kernel based on part of the data. Instead of using artificial experiments with a fixed kernel to empirically illustrate the soundness of our sample complexity bounds, we chose to use a state-of-the-art algorithm. The purpose of Fig. 1 is to show that an asymmetric simulation-experimentation tradeoff arises on real data and with complex real-world (kernel-training) algorithms beyond the theoretical minimax fixed kernel setting. We view Fig. 1 as important empirical evidence and motivation for further study of this simulation-experimentation tradeoff in (m)LFHT. \n\n3. $\\textbf{“L274 is trivial”}$\n\nWe believe that the observation is not entirely trivial since $X^{ev}, Y^{ev}$ are not used for validation in the traditional sense but rather serve as samples in estimating (evaluating) the test statistics conditioned on the kernel trained on a held-out set. \n\n$\\textbf{References}$\n\n[1] Lintusaari, J., Gutmann, M. U., Dutta, R., Kaski, S., and Corander, J. Fundamentals and recent developments in approximate Bayesian computation. 2017.\n\n[2] Bounliphone, W., Belilovsky, E., Blaschko, M. B., Antonoglou, I., and Gretton, A. A test of relative similarity for model selection in generative models. 2016\n\n[3] Gerber, P. R. and Polyanskiy, Y. Likelihood-free hypothesis testing. 2022.\n\n[4] Cowan, G., Cranmer, K., Gross, E. and Vitells, O. Asymptotic formulae for likelihood-based tests of new physics. 2011."}, {"review_id": "YrmN6gIogO", "reviewer": "Reviewer_m3Zx", "summary": "This paper introduces a new framework for likelihood-free hypothesis testing (LFHT), denotes as Mixed-LFHT or mLFHT. The setting of mLFHT is as follows: assume $n$ i.i.d. samples from a background disttribution $P_X$, and the same number of samples from a signal distribution $P_Y$. Also, assume we are given another $m$ i.i.d. samples from a mixed distribution $P_Z=\\nu P_Y + \\left(1-\\nu\\right)P_X$, and the aim is to \"test\" and see if $\\nu$ is greater than some positive threshold $\\delta$. Paper proposes a new kernel-based test statistic for this problem and then analyzes it from both theoretical and experimental perspectives. The main idea is to somehow \"map\" the empirical distributions of observed data into an RKHS (for some kernel of choice) and then measure the discrepancies of the observed data from both $P_X$ and $P_Y$.\n\nFrom a theoretical POV, authors claim to acheieve non-trivial sample complexity bounds for the non-asymptotic regime. Both upper and lower-bounds on the error have been established in Thms 3.2 and 3.3, respectively. From an experimental side, authors propose a new algorithm to learn the kernel from data, and also showcase the applicability of their test statistic and algorithm on a number of real-world tasks.\n\nI am not an expert in this particular field and therefore not much aware of other similar works. However, paper is not well-written and seems a little rushed. Regarding the technical contribution, I have a number of questions (please see questions section) before reaching a final conclusion. For now, my vote is borderline reject, with a relatively low confidence.", "questions": "- Please position your work w.r.t Ref. [18], since they also have achieved a similar non-symmetric and non-aasymptotic relation between $m$ and $n$.\n\n- Please justify the assumptions (i) and (iii) in L.165 and L.167, respectively. Assumption (ii) makes sense, but I assume (i) and (iii) might be limiting. Are they necessary in general (are they fundamentally required)? If yes, then please elaborate. If not, please explain how this will affect the applicability of this method in real-workd tasks.\n\n- In Theorem 3.2, how can we deal with $R$? While reading Section 3.5, I noticed $R$ automatically becomes zero in other existing works since they assume $P_Z=P_X$ or $P_Z=P_Y$. This makes the comparison a little troublesome. Again, is the appearance of $R$ inevitable in your equations? or is it a limitation of this work?\n\n- Related to previous question: In L.101 it has been said that $P_Z\\triangleq (1-\\nu)P_X+\\nu P_Y$. Then, in L.163 we have $\\nu=\\arg \\min_{\\nu'} \\mathrm{MMD}(P_Z,(1-\\nu')P_X+\\nu' P_Y)$. Does this mean $R$ is always zero, since $P_Z$ is already assumed to be a convex combination of $P_X$ and $P_Y$? This part is confusing, please clarify.", "limitations": "-", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Paper investigates an important problem for the ML community in general.\n- The mathematical tools (specially those from functional analysis and RKHS-related areas) used for the theoretical parts are sufficiently sophisticated and might be interesting for many researchers in this field.\n- Paper attempts to propose a new setting which comes with both a) theoretical guarantees and b) applicability on real-world data,\n- I did not completely checked the proofs, however, so far I have not found any miscalculations or mathematical flaws.", "weaknesses": "- IMO paper is not well-written, and this might be the biggest weakness of this work. Introduction seems short and not that much informative. Also, transitions from one part or section to another do not seem to be smooth enough. There are some cases where an equation or formula is referred to, but in fact it appears (for the first time) at least two pages later which makes the paper a little confusing for a general reader. Positioning of the work w.r.t prior papers is lacking in some ways, and some assumptions are not sufficiently justified. Overall, it seems that authors have tried to compress too much information into a 9-page limited manuscript which has degraded its readability. I suggest a major reconsideration in the writing, or even maybe considering this work for a journal paper instead of a conference.\n\n- One of the main theoretical contributions, as far as I have understood, is the claimed \"non-trivial\" behavior of the sample complexity bound which is outlined in Theorem 3.2, where authors show a non-symmetic behaviour between $m$ and $n$. However, in L.79 authors mention a similar relation in an existing work (Ref. [18]), which I assume is achieved for a slightly different problem. If this non-symmetric relation has been already discovered, it might affect the contribution level of this paper (please correct me if I am wrong).\n\n- In Thm. 3.3 authors claim to achieve an error lower-bound for mLFHT which matches (more or less) the error upper-bound in Thm 3.2. However, my understanding is that the bound in Thm 3.3 is mainly for the particular kernel-based solution of this paper, and not for mLFHT in general. The actual error lower-bound might be a lot smaller (or not). Again, please correct me if I am wrong. \n\n- I have some questions regarding a number of assumptions and derivation in the paper to see how they might limit the applicability of this solution (please see Questions section).\n\n-----------------------------------------------------------------\n\nMinor comments:\n\n- Caption of Fig. 1: Eq. (4) appears on page 4, but figures is on page 2.\n\n- L.82 to L.89: explanations are vague, please consider some improvements.\n\n- Section 1.2 is a key part of the technical contribution (introducing mLFHT), but there are no prior announcements or motivations for it. Please highlight it more.\n\n- L.105 to L.109: Explanations seem to be non-informative, and can be removed.\n\n- Transition from Section 1.2 to 2.1 is not smooth at all. Also, the math that comes afterwards is unncessarily intense and some of it can be moved to appendix (Specially the \"Removing the Bias\" part, I guess it won't hurt the paper it this part is moved).\n\n- Again, section 2.2 needs more prior advertisement and explanations.\n\n- L.140 to L.151: explanations seem vague.\n\n- L.154: please consider citing some ref. paper for the theorem, otherwise it might look like it is your contribution.\n\n- L.179: Authors claim that this paper imposes less restrictions on the class of distributions for $P_X$ and $P_Y$ compared to other works. I am not completely sure about this claim (see questions), however, it might be a good idea to advertise it more. For example, authors can bring it up in the Introduction section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s comments on our writing as well as the ‘minor comments’; our revision will incorporate all of the helpful suggestions. The page limit is indeed challenging, but we believe we are able to make the improvements necessary for good readability. Below, we address some more specific questions brought up in the review.\n\n1. $\\textbf{ “Comparisons to Ref. [18].”}$\n\nIn short, we study a generalization of the problem studied in [18], and we obtain results that imply many of the results therein. Indeed, [18] was the first to identify the trade-off between m and n, but we show that this phenomenon apply much more generally and are the first to empirically demonstrate it in real datasets (beyond information theoretically worst case constructions) via a novel, theoretically provable, efficient algorithm. Please see also our general response #2. \n\n2. $\\textbf{ “Thm 3.3 applies only to the particular kernel-based solution and not mLFHT in general.”}$\n\n\nOur lower bounds in Thm 3.3 apply to the mLFHT problem in general (not algorithm based). In other words, any algorithm for mLFHT must use a number of samples greater than the bound in Thm 3.3. Our proof (Appendix E) uses information-theoretic techniques and bounds the total variation distance between classes of constructed hard instances involving the eigenfunctions of the kernel. We will clarify this in the revision. \n\n3. $\\textbf{ “Justify the assumptions (i) and (iii) in L.165 and L.167.”}$\n\n\nAssumption (i) is crucially required for our results and we believe is somewhat mild (the upper bound on the density). Note also that the base measure can be selected arbitrarily, giving a lot of flexibility in what is considered “bounded” density (e.g. the base measure could become singular at the border of the manifold, etc). As for (iii), it is less restrictive than requiring that R=0 (i.e. that P_Z is exactly a mixture of P_X and P_Y) which was done in prior work [18]. Therefore, (iii) is a relaxation of a commonly used assumption. Specifically, tuning $R$ controls how misspecified the problem is allowed to be. See also our general response #3 about (iii).\n\n4. $\\textbf{ Questions 3-4}$\n\nIn L101-105 we describe a not fully general version of mLFHT (to keep the introduction simple), which corresponds to the case R=0 of L162-167. Our referencing equation (mLFHT) in Theorem 3.2 indeed makes this confusing, we will correct this. The introduction of $R$ should be viewed as an extension (or relaxation, cf. previous part) not as a limitation, we think. Please also see general response #3 for more. \n"}, {"review_id": "Hy9Lte7DMO", "reviewer": "Reviewer_x91N", "summary": "This paper studies a problem in the area of likelihood-free testing, where one is given black-box access to samples $X\\sim P_X$, $Y \\sim P_Y$ of size n, as well as \"real-world data\" $Z \\sim P_Z$ of size m. The authors propose a new model (\"Mixed likelihood-free testing\") where it is known that $P_Z = (1 - \\nu) P_X + \\nu P_Y$ for rate parameter $\\nu$, and the goal is to determine whether $\\nu = 0$ or $\\nu \\ge \\delta$. They propose a kernel based test statistic for this problem, and analyze its performance theoretically, and also provide lower bounds. They also perform experiments based on Higgs Boson detection and detecting images produced by a diffusion model to support their theoretical claims.", "questions": "1) What is the relationship between this problem/likelihood-free testing more generally, and the distribution testing literature in theoretical CS? Can you include a brief comparison?\n\n2) While Proposition 4.1 says that the p-value estimate is good as n_cal-> infty, what is the finite-sample relationship between n_cal, n_eval and the test statistic? Is there something quantitative that can be said here? What happens if $R > 0$?\n\n3) Is it possible to say anything about the kernel training phase theoretically?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper is well written, and the problem is well motivated from the point of view of practical applications (Higgs Boson detection, diffusion image detection). The paper has an extensive set of experiments on real data, and there is an interesting theory to support empirical findings. Overall, I think this is an interesting paper.", "weaknesses": "The upper and lower bounds in the theory are a little difficult to interpret, especially the dependence on the eigenvalues of the kernel - it would be useful if the authors could provide some examples with simple kernels to illustrate better what the bounds are saying.\n\nSome of the things done in the experiments, such as training a kernel on the test data (especially overlap between training and evaluation data), are not captured/explained by the theory. Also, while Figure 1 seems like it agrees with the theory, it includes all the samples, including ones used for training, calibration, and evaluation. On the other hand, the plot involving only the evaluation samples (Figure 8 in appendix) seems like it agrees more with the naive expectation of $\\min\\{n, m\\} \\gtrsim n_{TS}(\\alpha, \\epsilon, \\mathcal P)$. Since the theory is supposed to reflect performance relative to evaluation samples for a fixed kernel, it would be useful if the authors could provide a more detailed explanation of both these plots. It would also be useful if the authors could provide a simple synthetic experiment to illustrate the theoretical bounds for the setting that it is supposed to explain (with a fixed kernel)\n\nThe dependence on mis-specification parameter $R$ is not captured by the lower bounds, and Proposition 4.1 (which is about the calibration of the test statistic) assumes that $R=0$. I would be curious to know if proposition 4.1 can be made stronger. In particular, can anything be said about the empirical settings where presumably $R > 0$?\n\nOne very interesting thing the authors do in experiments is to use a fraction of the samples from $P_X$ and $P_Y$ to train a kernel that maximizes the (normalized) expectation gap of the statistic. While this seems to work well, there doesn't seem to be a theoretical explanation for why this is a good idea. Of course, while it may not currently be possible to make theoretical claims about a neural net based kernel, is it possible to make a theoretical claim about some simpler model? Or make some abstract claim given black box access to an algorithm that can take samples and generate a kernel with some good properties?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the helpful comments in the review and will make sure to address them in the revision. In the following we will address some of the questions mentioned in the review.\n\n1. $\\textbf{“The upper and lower bounds in the theory are difficult to interpret.”} $\n\nIn terms of simple examples, we would like to highlight those given in Section 3.5 as well as the three examples (discrete distributions, Holder-smooth distributions, and Sobolev-smooth densities) of specific kernels provided in Appendix B, which show that our upper bounds recover minimax optimal results in past literature ([1]). Among them, the discrete case could be the simplest example to provide the reader with some intuition. In the revision, a more focused discussion will be included to help readers understand our results by adding explicit evaluations of kernel spectra. Please also see general response #1 for more. \n\n2. $\\textbf{“What is the relationship between LFHT and the distribution testing literature in TCS ?”} $\n\nThe closest work to LFHT in the TCS literature is two-sample testing with unequal sample size which is in fact equivalent to LFHT in the regime m > n for discrete distributions (this can be found in [1]). There has also been some work on LFHT in information theory [5]. We recommend the papers [1,3] as a good resource for connections to prior results. To the best of our knowledge, the mLFHT problem hasn’t been considered by the TCS community and we are not aware of related/similar work. \n\n3. $\\textbf{“What is the finite-sample relationship between $n_\\mathsf{cal}$, $n_\\mathsf{eval}$ and the test statistic? Is there a version of Proposition 4.1 when $R>0$? ”} $\n\nThat is an important question that we hadn’t considered before. A naive answer would be to force all the k batches to be disjoint, namely take $k=\\lfloor n_\\mathsf{cal}/m \\rfloor$. In this case, the variance would be of order $\\mathcal O(m/n_\\mathsf{cal})$ and thus $n_\\mathsf{cal} = \\omega(m)$ is sufficient for the variance to decay to zero. Improving this naive bound, or alternatively studying the hardness of estimating the p-value could be an interesting direction. \n\nWhen $R>0$ estimation of the p-value becomes subtle. By definition the p-value of the composite hypothesis is $p:=\\sup_{\\nu(P)=0}(P(\\hat{T}<T))$. However, here the maximizer might not be $P=P_X$, which invalidates the current algorithm. Due to the generality of our setup, designing an algorithm to consistently estimate the p-value in the misspecified setting seems like a challenging open problem. \n\n4. $\\textbf{“Is it possible to say anything about the kernel training phase theoretically?”}$\n\nIn the context of two-sample testing, Theorem 6 in [2] shows under mild assumptions, that estimating the kernel by optimizing the objective J is a consistent procedure (i.e. it identifies a maximizing kernel). The same paper (page 3, left column, bottom) includes a justification of using J as the objective that relies on the asymptotic power of the resulting test. In a similar vein we include a heuristic justification of our use of the objective J in Appendix F1. However, these results leave much to be desired. Studying the problem of kernel selection in a simplified/toy setting (even finding the right way to pose the question) might uncover interesting phenomena, although we have not spent time on this. \n\n6. $\\textbf{Figures 1,8 and the trade-off}$\n\nFigure 1 agrees with our theory insofar as it exhibits a clear asymmetric trade-off between n and m with m leveling off at a lower value than n (although we do not claim that our theoretical results strictly imply that this should be the case for trained kernels). We view Fig. 1 as important empirical evidence and motivation for further study of this simulation-experimentation tradeoff in (m)LFHT. We agree that on Figure 8 the precise nature of the trade-off is visually less clear, this may be due to the high numerical precision and/or samples required to observe the trade-off. We are happy to include a synthetic experiment to verify the soundness of our theoretical trade-off in the revision. \n\n$\\textbf{References}$\n\n[1] Gerber, P. R., and Polyanskiy, Y. Likelihood-free hypothesis testing. 2022.\n\n[2] Liu, F., Xu, W., Lu, J., Zhang, G., Gretton, A., and Sutherland, D. J. Learning deep kernels for non-parametric two-sample tests. 2020.\n\n[3] Gerber, P.R., Han, Y. and Polyanskiy, Y. Minimax optimal testing by classification. 2023.\n\n[4] Bhattacharya, B. and Valiant, G. Testing closeness with unequal-sized samples. 2015.\n\n[5] Huang, D. and Meyn, S. Classification with high-dimensional sparse samples. 2012.\n"}]

Author rebuttal:
We greatly appreciate the valuable suggestions given by reviewers and will revise our manuscript accordingly. In this response, we would like to address several comments that appear in multiple reviews.

1. $\textbf{“Interpretation of the bounds and its dependence on kernel, base measure, hypotheses”}$

Due to the minimal assumptions for the generality of our results, our bounds can indeed be challenging to interpret. We note that the dependence on the kernel spectrum is unavoidable as can be seen from comparing our upper and lower bounds. To build intuition, in Section 3.5 and Appendix B our upper bound (Thm 3.2) is applied with some explicit kernels (Gaussian kernels/discrete kernels) and to classical nonparametric classes such as smooth densities and bounded discrete PMFs. These applications recover minimax optimal sample complexity shown in past work [1,2]. We hope these concrete examples help in interpreting our results within a broader context. We will take more care in the revision to emphasize these.

2. $\textbf{“Novelty over [1] (Ref. [18] in our paper)”} $

[1] is an important inspiration for our study, however, we innovate over [1] in several ways, which we try to summarize below. 

i) $\textbf{New problem setting.}\quad$ [1] derived the minimax tradeoff for several specific classes of distributions that are different from our own (they studied smooth densities on finite-dim spaces and discrete PMFs under TV distance, whereas we study $\underline{\text{unconstrained densities}}$ but under kernel distance). Moreover, our work extends [1] to a more general setting (mLFHT), which on one hand is more practical, and on the other hand, exhibits a different tradeoff (e.g. mitigates the curse of dimensionality in # of simulated samples (L236)). This setting arises in several scientific disciplines (HEP, LIGO, etc) and is more realistic (without assuming smoothness).

ii) $\textbf{More general results.}\quad$ Although under different settings, our upper bound results, applied with specific kernels (Appendix B), recover several of [1]’s key (minimax optimal) results for LFHT as well as several of [2] in two-sample testing. Thus, our theoretical bounds are more general while still being optimal when specialized to prior settings. 

iii) $\textbf{Practical algorithm and empirical trade-off.}\quad$ Our (novel) kernel-based algorithm is efficient and able to solve real-world tasks, whereas the tests considered in [1] require discretizing space into a large (exponential in dimension) number of bins and are thus impractical (though minimax optimal). Furthermore, our experiments confirm the validity of the theoretical insight that one can trade off m versus n and that in general one needs more simulation samples n than real samples (asymmetry of the trade-off). 

We will make sure that our contributions are clarified and emphasized in the revision.

3. $\textbf{“Dependence on R” and “Assumption (iii)”}$

First, we want to clarify that L.101 is informal and, in fact, the special case ($R=0$) of the mLFHT problem stated in Section 3.2. The latter can be formally written as 
\begin{align*}
	H_0: P_Z\in \lbrace P_Z : \nu(P_Z)=0 \rbrace \quad \text{versus} \quad H_1: P_Z\in\lbrace P_Z:\nu(P_Z)\geq\delta\rbrace
\end{align*}
where $\nu(P_Z)=\arg\min_{\nu’}\mathrm{MMD}(P_Z,(1-\nu’)P_X+\nu’ P_Y))$. Intuitively, (iii) says that “the test distribution P_Z should not be too far away from some mixture of labeled data,” where $R$ governs how mis-specified we allow the problem to be. Thus, (iii) shouldn't be thought of as an 'assumption', but rather as a relaxation of the assumption (present in prior work on LFHT) that P_Z is an exact mixture of P_X and P_Y. 

We want to clarify that the major focus of our paper is on the case when $R=0$, i.e. when there is no model mis-specification and $P_Z$ comes from a mixture of $P_X$ and $P_Y$, as is assumed in many applications and past literature. Our theory and experiments cover this scenario perfectly by simply plugging in $R=0$ in Thm 3.2. 

In Thm 3.2, we included the more general case where $R$ can be positive in order to present the most general result possible. The dependence on $R$ is not a crucial part in the theory or experiments. While a direct controlled study involving $R$ would be hard (since it depends on the kernel learned from samples), we believe that further investigation of (m)LFHT involving non-trivial model mis-specification is an interesting open direction worth investigating.

$\textbf{References}$

[1] Gerber, P. R. and Polyanskiy, Y. Likelihood-free hypothesis testing. CoRR, abs/2211.01126, 2022.

[2] Li, T. and Yuan, M. On the optimality of gaussian kernel based nonparametric tests against smooth alternatives. arXiv preprint arXiv:1909.03302, 2019


Meta-review: This paper studies the likelihood-free testing problem, recently introduced by Gerber and Polyanskiy, motivated by practical questions in physics experiments. The contributions were well appreciated by the reviewers, and the authors used the rebuttal phase successfully to clarify misunderstandings about their theoretical results.
Decision: Accept (poster)