KSD Aggregated Goodness-of-fit Test
Authors: Antonin Schrab
Benjamin Guedj
Arthur Gretton
Venue: NeurIPS 2022 Accept (2022)
Keywords: kernel methods
goodness-of-fit
Stein methods
hypothesis testing

Abstract: We investigate properties of goodness-of-fit tests based on the Kernel Stein Discrepancy (KSD). We introduce a strategy to construct a test, called KSDAgg, which aggregates multiple tests with different kernels. KSDAgg avoids splitting the data to perform kernel selection (which leads to a loss in test power), and rather maximises the test power over a collection of kernels. We provide theoretical guarantees on the power of KSDAgg: we show it achieves the smallest uniform separation rate of the collection, up to a logarithmic term. For compactly supported densities with bounded score function for the model, we derive the rate for KSDAgg over restricted Sobolev balls; this rate corresponds to the minimax optimal rate over unrestricted Sobolev balls, up to an iterated logarithmic term. KSDAgg can be computed exactly in practice as it relies either on a parametric bootstrap or on a wild bootstrap to estimate the quantiles and the level corrections. In particular, for the crucial choice of bandwidth of a fixed kernel, it avoids resorting to arbitrary heuristics (such as median or standard deviation) or to data splitting. We find on both synthetic and real-world data that KSDAgg outperforms other state-of-the-art quadratic-time adaptive KSD-based goodness-of-fit testing procedures.

KSD Aggregated Goodness-of-fit Test
Antonin Schrab
Benjamin Guedj
Centre for Artificial Intelligence Gatsby Computational Neuroscience Unit University College London & Inria London schrabbucl..c..uu
Centre for Artificial Intelligence
University College London & Inria London b. quudj@uuc. ac
Arthur Gretton
Gatsby Computational Neuroscience Unit University College London arthur praturrggeetto@gmaal..m. com
Abstract
We investigate properties goodness-of-fit tests based on the Kernel Stein Dis- crepancy (KSD). We introduce a strategy to construct a test, called KSDAGG, which aggregates multiple tests with different kernels. KSDAGG avoids splitting the data to perform kernel selection (which leads to a loss in test power), and rather maximises the test power over a collection kernels. We provide con-asymptotic guarantees on the power of KSDAGG: we show it achieves the smallest uniform separation rate of the collection, up to a logarithmic term. For compactly supported densities with bounded model score function, we derive the rate for KSDAGG over restricted Sobolev balls; this rate corresponds the minimax optimal rate over unrestricted Sobolev balls, up to an iterated logarithmic term. KSDAGG can be computed exactly in practice as it relies either on a parametric bootstrap or on a wild bootstrap to estimate the quantiles and the level corrections. In particular, for the crucial choice bandwidth of a fixed kernel, avoids resorting to arbitrary heuristics (such median standard deviation) both synthetic and real-world data that KSDAGG outperforms other state-of -fate-of-the-art quadratic-ting adaptive KSD-based goodness-off fit testing procedures.
data splitting. We find
Introduction
Kernel selection remains a fundamental problem in kernel-based nonparametric hypothesis testing, it significantly impacts the test power. Kernel selection has attracted significant interest in the literature, and a number of methods have been proposed in the two- sample, independence and goodness-of-fh testing frameworks, such as using heuristics (Gretton al. 2012a), relying on data
splitting (Gretton et al., 2012b; Sutherland et al.
2017
Kübler et al.
2022 learning deep kernels
(Grathwohl al. [2000]
(020), working in the post-selection inference framework (Yamada
et al. 2019 Lim et al. 2019 2020 Kübler et al. 2020 Freidling et al. 2021b, to name but few.
In this work, focus on aggregated tests, which have been investigated for the two-sample problem by Fromont et al. (2013), Kim et al. (2022) and Schrab et al. (2021) using the Maximum Mean Diserepancy (MMD: Gretton et al. 2012a), and for the independence problem by Albert al. (002) and Kim et al. 2022) using the Hilbert Schmidt Independence Criterion (HSIC; Gretton et al. 2005).
We extend the use aggregated tests to the goodness-of-fit setting, where we are given model and some samples, and test whether the samples have been drawn from the model. We employ the Kernel Stein Discrepancy (KSD; Chwialkowski et al.) 2016 Liu al. (016) as our test statistic, which an ideal measure of distance for this setting: it admits an estimator which can be computed without
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

requiring samples from the model, and does not require the model to be normalised. To the best of our knowledge, ours represents the first aggregation procedure for the KSD test in the literature.
Related work.
Fromont et al. 2012 2013) introduced non-asymptotic aggregated tests for the
two-sample problem with sample sizes following Poisson process, using an unscaled version of the
MMD. Using a wild bootstrap. they derived uniform separation rates (Ingster 1987 1989, 1993a by
Baraud 2002). Albert et al. (2022) then proposed an independence aggregated test using the HSIC, with guarantees using a theoretical quantile, but relying on permutations to obtain the test threshold
in practice. Kim al. (202)) then extended those theoretical results to also hold for the quantile estimated using permutations, however. they did not obtain the desired level dependency in their HSIC bound. All those aforementioned results were proved for the Gaussian kernel only, [Schrab] et al. p generalised the two-sample results to hold for the usual MMD) estimator and for a wide range of kernels using either a wild bootstrap or permutations, and provided optimality results which hold with fewer restrictions. Our work builds and extends on the above con-asympiotic results: we consider the goodness-of fit framework, where we have samples from only one of the two densities. The main challenges arise from working with the Stein kernel which defines the KSD test statistic: for example, we lose the transition-invann
property of the kernel which is crucial to work in the Fourier domain. Balasubramanian et al. (202T) considered adaptive MMD-based goodness-of-fi tests and obtained their uniform separation rates over Sobolev balls in the asymptotic regime. More generally, Li and Yuan (2019) studied asymptotic adaptive kernel-based tests for the three testing frameworks. Tolstikhin et al. (2016) derived minimax rates for MMD estimators using radial universal kernel (Sriperumbudur et al.] (011)_ (Schrab et al. (2022 extends this work, together with those of Albert et al. (2022) and Schrab et al. (2021), to construct efficient aggregated tests for the three testing frameworks using incomplete Ufsstatistics. They quantify the cost in the minimax rate over Sobolev balls incurred for computational efficiency, and prove minimax optimality of the quadratic- HSIC permuted aggregated test by improving the bound of Kim al. (022). See Appendix for details.
Contributions. We propose a solution to the fundamental kernel selection problem for the widely- used KSD goodness-of-fit tests: construct an adaptive test KSDAGG which aggregates multiple tests with different kernels. Our contribution is in showing, both theoretically and experimentally, that the aggregation procedure works in this novel setting in which it has never been considered before. We work in the kernel selection framework; this general setting has many applications including the one of kernel bandwidth selection. Our aggregated test allows for two numerical methods for estimating the test thresholds: the wild bootstrap and the parametric bootstrap (a procedure unique to the goodness-of-fit framework). We conduct a theoretical analysis: we derive a general condition which guarantees test power for KSDAGG in terms of its uniform separation rate, with extra assumptions including regularity over restricted Sobolev balls we prove that KSDAGG attains the minimax rate over (unrestricted) Sobolev balls. We discuss the implementation of KSDAGG and experimentally validate our proposed approach on benchmark problems, not only on datasets classically used in the literature but also on original data obtained using state-of-the-art generative models (i.e. Normalizing Flows). We observe, both on synthetic and real-world data, that KSDAGG obtains higher power than other KSD-based adaptive state-of saree-of-thaatte art tests. Contributing to the real-world applications of these goodness-of-fit fit tests, we provide publicly available code to allow practitioners to employ our method: httpp::/giite thu.. com/ www/antonnneeee wwwpnninsshaaaadaaaaeea paper
2
Notation
We consider the goodness-of-fit problem where given access known model probability density p (which can be unnormalised since we actually only need access to its score function V log)(-)) and to some i.i.d. d-dimensional samples XN (X,) drawn from an unknown data density q, we want to decide whether p * holds. This can be expressed as a statistical hypothesis testing problem with null hypothesis Ho p- = q and alternative H. / q.
As a measure of distance between p and q, we use the Kernel Stein Discrepancy (KSD) introduced by Chwialkowski et al. (0016) and Liu et al. (016)). For a kernel k, the KSD is the Maximum Mean Discrepancy (MMD; Gretton et al. 2012a) between and using the Stein kernel associated to k:
KSD2 p.k (q) = MMD? b (p. q)
= Eg, ( (X,X Y) - 2Ep. D4 (X, Y)] + Ep. [hp (X, Y)) = E P (X, Y,Y)
2

---

where the Stein kernel hp.x: R R + R is defined as
hp (z. y) = V log p(x) V logp(y) k(a, y) + V logp(v)
(V Vzk(z.y)
Vogg((z) Vy (z, y) + dr,0y;
k(2.))
and satisfies the Stein identity Ep (X. .I 0. Additional background details on the KSD
are presented in Appendix C A quadratic-time KSD estimator can be computed as the U-statistic
(Hoeftding 1992)
KSD (XN) N(N- -
Σ
(I)
ISHJJN
In this work, the score of the model density is always known, we do not always explicitly write the dependence on p of all the variables we consider. We assume that the kernel & such that
KSD p. (q) a (X,, Y)] < oo and
C == 1/ E (X, Y) <
(2)
We now address the requirements for consistency (i.e. test power converges to as the sample size goes to 20) of the Stein test (Chwialkowski et al., 2016 Theorem 2.2): we assume that the kernel is
Co-universal (Carmeli et al. 2010 Definition 4.1) and that Bg
v
log ((x) x(x)
c0.
We use the notations Pp and F. to denote the probability under the model distribution p and under the data distribution y, respectively. Given a kernel w: TRd IRd + and function f: Rd -> RR in T,2 (R.), we consider the integral transform Tv defined as
(Tx (v) = / <(x ((x,,))(x))
for E Rd. When the kernel 6 is translationiinvaiinn convolution. However, the lack of translation invariance of the Stein kernel introduces new challenging problems. First, working the integral transform of the Stein kernel is more complicated since it does not correspond to a simple convolution. Second, for the expectation of the Stein kernel squared, C == Eg p X, 2) it is not possible to extract the bandwidth parameter À outside of the expectation as is the case when using the usual kernel directly for the MMD and HSIC.
the integral transform corresponds to
3
Construction of tests and bounds
We now introduce the single and aggregated KSD tests. We show that these control the probability of type error as desired, and provide conditions for the control of the probability of type II error.
3.1 Single test
We first construct KSD test for fixed kernel as proposed by Chwialkowski al. (2016) and Liu
et al. (2016). To estimate the test threshold, we can either use wild bootstrap (Shao) 2010 Leucht
and Neumann 2013 Fromont al., 2012 Chwialkowski et al. 2014) or parametric bootstrap
Stute al., 1993). Both methods work by simulating sampling values (K)..... K. KB
from the
(asymptotic) distribution of KSD, p.k under the null hypothesis and estimating the (1 - a) quantile for (0, 1) using Monte Carlo approximation)
B1+1
q inf u QuER: a B
ml Re ((B
where Rel < ... < R.B. are the sorted elements 2 KSD k (K The single test is then defined as test function outputs when the null is rejected and 0 otherwise)
(R, RBit2) with KB =
k (Kx)) = 1 KSD
P.kk (X T
We do not write explicitly the dependence of - on other variables, but those are implicitly considered when writing probabilistic statements.
3

---

For the parametric bootstrap, we directly draw new samples (x))= from the model distribution (it might not always possible so) and compute the KSD
Kg N(N
E (x,,
(4)
ISGASN
For the wild bootstrap, we first generate n. i.i.d. Rademacher random variables 61, En. each taking value in {-,,1}, and then compute
K N(N
E (x)
ISRAJN
By repeating either procedure B₁ times, we obtain the bootstrapped samples Rg..... K
Since it uses samples from the model the parametric bootstrap (Stute et al. 1993 results in test with non-asymptotic level a. This comes the cost of being computationally more expensive and assuming that we are able to sample from p (which may be out of reach in some settings). Conversely, the wild bootstrap has the advantage of not requiring to sample from p. which makes it computationally more efficient as only one kernel matrix needs to be computed, but it only achieves the desired level a asymptotically (Shao) 2010: Leucht and Neumann 2013 Leucht 2012)
Chwialkowski et al.) 2014 2016) assuming Lipschitz continuity of dp,s (see Appendix D for details).
Note that we cannot obtain a non-asymptotic level for the wild bootstrap by relying on the result of
Romano and Wolf 20055 Lemma 1) as done in the two-sample framework by Fromont et al. (2013)
and Schrab et al. (2021 This is because in our case K₂ and KSD P.A (Xx)) are not exchangeable
variables under the null hypothesis, due to the asymmetry of the KSD statistic with respect to p and
Having discussed control of the probability of type eπгог of the single test A we now provide a condition on ||p 4||2 which ensures that the probability of type error is controlled by some 3 E (0, 1). The smallest such value of lpp - 2112- provided that p lies in some given class of regular functions, called the uniform separation rate (Ingster 1987 1989 1993a D Baraud 2002).
Theorem 3.1. Suppose the assumptions listed in Appendix A.2 hold, and let 1b == 9. There exists a positive constant C such that the condition
1
VCk BN
1 2 1
TTp. +
C log
guarantees control over the probability of type error, such that P. (A (XN) S
Theorem 3.I. which is proved in Appendix provides power guaranteeing condition consisting of two terms. The first term ||el The v indicates the size of the effect of the Stein integral transform operator on the difference densities vé == 9. it is a measure of distance from the null (where this quantity is zero). The second term Colo (1/a) (3N)- VC is obtained from upper bounding the variance of the KSD U U-statisticc, it depends on the expectation of the squared Stein kernel Cs Ey (X, Y)². This second term also controls the quantile of the test.
3.2
Aggregated test
We can now introduce our aggregated test, which motivated by the earlier works of Fromont et al. 2212 2013 Albert al. (2022). and Schrab et al. (2021) for two-sample and independence testing.
We compute K!...., K. further KSD values simulated from the null hypothesis obtained using either a parametric bootstrap or a wild bootstrap as in Equations H or ( respectively. We consider finite collection IC of kernels satisfying the properties presented in Section 2 We construct an aggregated test A called KSDAGG, which rejects the null hypothesis one of the single tests (At, )ex rejects it, that is
Ax = I(A (xx)= = 1 for some k E K).
The levels of the single tests are adjusted to ensure the aggregated test has the prescribed level a. This adjustment is performed by introducing positive weights (Wk)eek satisfying E Wk S. 1 and some correction
Ua = sup a E (o. min wh kEk
Pr sa
(6)

---

Algorithm KSDAGG
Inputs: samples X (aa b density p V Foggp p()). finite kernel collection K. weights (wa)eex level a E (0, )),, estimation parameters B1, B2, B3 E N, parametric or wild bootstrap
Output: (fail reject Ho) or 1 (reject Ho)
Algorithm:
for
do
compute KB+t1 = KSD P.b (KN) as in Equation ! T=B
compute (K I5bSB, as in Equations or
sort 15b in ascending order to obtain (K*) bb) 1505
as in Equations or 5 compute (K 1,
0, Mmax for 1 l,..., B3 do
min " kER
B₂
1 u 2 Umnnn + Umax), ), Pu
max REK.
R
( [B) (11)))1-0w6]]]] ( 20)
B2
b=1
if Ps S a then Umin u else Umax = u
Umin
KSD p.k (XN) - ((
if max KEK.
> then return
else return 0
Time complexity: ([I[[(B, + B2) N2)
where
P
max
K
kg (11))(1-wwp)) >0)
B2
REK
b=1
is Monte Carlo approximation of the type error probability of the aggregated test with correction
Pa Pp
max REK
KSD
(X,)
0 uur
To compute Was we estimate the supremum in Equation by performing B3 steps of the bisection method, the theoretical results account for this extra approximation. Detailed pseudocode for KSDAGG provided in Algorithm [ and details regarding our aggregation procedure are provided in Appendix G We discuss potential limitations of KSDAgg in Appendix H
We verify in the next proposition that performing this correction indeed ensures that our aggregated test A has the prescribed level a.
Proposition 3.2. For E (0, 1) and collection of kernels K,, the aggregated test A satisfies (A = S a
asymptotically using a wild bootstrap (with Lipschitz continuity of hy.k required) and non- asymptotically using parametric bootstrap.
The proof of Proposition 3.2 is presented in Appendix
2 Details about the asymptotic result for the We now provide guarantees for the power of our
wild bootstrap case are reported in Appendix D aggregated test KSDAGG in terms of its uniform separation rate.
Theorem 3.3. Suppose the assumptions listed in Appendix A.3 hold, and let vb == p 9. There exists positive constant C such that if
VC
2
min
(10~-Ten Thy.u
Clogg
REK
BN
then the probability of type Il error of A. is controlled by B, that is, P., (X = 8.
The proof Theorem 3.3 can be found in Appendix 33 relies upper bounding the probability of intersection some events by the minimum of the probabilities of each event, and on applying Theorem 3.1 after having verified that its assumptions are satisfied for the tests with adjusted levels. We observe that the aggregation procedure allows achieve the smallest uniform separation rate of the single tests (A)) kER up some logarithmic weighting term log(1/ur wx).
5

---

3.3 Bandwidth selection
specific application of the setting we have considered is the problem of bandwidth selection for fixed kernel. Given kernel k R= x F + R. the function
h kx(x,))== = T
is also a kernel for any bandwidth > 0. A common example is the Gaussian kernel, for which we have k(r, y) = exp(-ll> v1l2) and (x y) exp ( ル - ylla/ X²). As shown by Gorham and Mackey (017), more appropriate kernel for goodness-of-it testing using the KSD IS the -Pu for fixed
IMQ (inverse multiquadrie) kernel, which is defined with k(z, v) = + ||= - parameter 3y E =0,1
(x v) (
22 (x² (A²+110
v113) -Bx & (2²+ 1| w1(3) -B
(7)
which is the well-known form of the IMQ kernel with parameters À > 0 and Br E (0, 1). Note that is justified to consider the kernel up to multiplicative constant because the single and aggregated tests are invariant under this kernel transformation.
In practice, as suggested by Gretton et al. (2122a), the bandwidth is often set to heuristic such as the median or the standard deviation of the L distaancs between the samples (Xx)) however, these are arbitrary choices with no theoretical guarantees. Another common approach proposed by Gretton al. (2012b) for the linear-time setting. and extended to the quadratic-ting setting by Liu al. (2020) is to resort to data splitting in order to select bandwidth on held-out data, by maximising for a proxy for asymptotic power (see Section 4.1 for details). Both methods were originally proposed for the two-sample problem, but extend straightforwardly to the goodness-of-fit setting.
By considering kernel collection KA {Kx : À E } for a collection of bandwidths A, we can use our aggregated test KSDAGG to test multiple bandwidths using all the data and without resorting to arbitrary heuristics. We now obtain expression for the uniform separation rate of A in terms of the bandwidths À E A.
Corollary 3.4. Suppose the assumptions listed in Appendix A.3 hold for K= K.A = [kx : :
and let th = p 9. There exists a positive constant C such that the condition
AeA [
u
1
11112
min
C'log
awx
3N
ensures control over the probability of type error of the aggregated test P. (A [A (Xx) 0) S 3.
Corollary 3.4 follows from applying Theorem 3 to the collection of kernels KA Our results hold with great generality as we have not imposed any restrictions on == p-q such as assuming it belongs to specific regularity class. For this reason, the dependence À in the terms | Thp,,, A, 201 and log(1 (1/()>>)) (BN)-1V /Ck, is not explicit. In Section 3.4 we characterise this dependence with regularity assumptions on si p - q, and derive uniform seperation rates in terms of the sample size.
3.4 Uniform separation rates over restricted Sobolev balls
In this section, we derive uniform separation rates with stronger assumptions on and This provides settings in which the power guaranteeing conditions of Theorems 3.1 and 3.3 are satisfied, and illustrates the interactions between the two terms in those conditions. We make the following assumptions.
The model density is strictly positive on its connected and compact support S C Rdd
The score function V ((g)(()) is continuous and bounded on S.
The support of the density q is a connected and compact subset S.
The kernel used a scaled Gaussian kernel (x y) = 2 exp (-11s: - y12// /2).

---

In particular, any strictly positive ditceeiiffreettablee density on R truncated to some d-dimensional interval will satisfy the assumptions for the model p. Any density truncated the same d-dimenssioal interval will satisfy the assumption for the density q. As an example, one can consider truncated normal densities.
Given some smoothness parameter s > O, radius R > 0 and dimension d E IN \ (0), the Sobolev ball S defined as the function space
()) = { (R*)
3d 1K
2- (()) de S (2T)
where î denotes the Fourier transform of J. For 8, d, R, L all strictly positive, we define the restricted Sobolev ball " L.) as containing all functions (2(R) satisfying
f 1k
F(() de de 1 / de.
2
(8)
With the Sobolev assumption p E (R.). the densities and can differ at any frequencies. The
restricted Sobolev assumption p q E S (R, L) does not include the case in which the densities and g differ only at low frequencies due the additional restriction in Equation (
Theorem 3.5. Suppose the assumptions listed in Appendix A.4 hold K.A = [ıx E A}. Ler
3 == 4- We show that there exists some L > 0 such that if E (R,
" L) then (i) & (ii) hold.
(i) Under the assumptions of Theorem 3.1 for the KSD test with bandwidth À = N- 2/(+ttd) the condition
1 2 CN-4s/(4s+d)
for some C > 0 guarantees control over the probability of type Il error (A 0) S B.
(ii) Under the assumptions of Theorem 3.3 for KSDAGG with the collection
2 d logz (n((n(N))
(mm(
N
and weights wx = 6/ we have P. (A
= 0) S provided that, for some C 0,
4s/(4s+
N
| 2 C In(In(N))
The proof of Theorem 3.5 is presented in Appendix L4
The uniform separation rate Ne1e/((e+d) in Theorem 3.5 is known to optimal in the minimax sense over (unrestricted) Sobolev balls ( (Li and Yuan 2019 Balasubramanian et al. 2021; Albert et al. 2022] Schrab et al. 202T). However, this rate for the KSD test with bandwidth depending on the smoothness parameter s > 0 which is unknown in practice. Note that even methods which split the data to perform kernel selection are not able to select this bandwidth depending on s and cannot achieve the minimax rate. The aggregation procedure is adaptive to this unknown parameter s: crucially, the collection of bandwidths A does not depend on 8, and so, the aggregated KSDAGG test of Theorem 3.3 (ii) can implemented in practice, unlike the single KSD test of Theorem 3.5 (i). The price to pay for this adaptivity is only an iterated logarithmic factor in the minimax rate over Sobolev balls (²) The uniform separation
rates presented in Theorem 3.5 are over the restricted Sobolev balls St (R, L). Whether those rates also be derived under less restrictive assumptions and in the more general setting of (unrestricted) Sobolev balls (Rt), is challenging problem, which is left for future work.
Implementation and experiments
We consider three diffeerntt experiments based on a Gamma one-dimensional distribution, a Gaussian- Bernoulli Restricted Boltzmann Machine, and a Normalizing Flow for the MNIST dataset. We compare our proposed aggregated test KSDAGG against three alternatives: the KSD test which uses the median bandwidth, a test which splits the data to select an 'optimal' bandwidth according to a proxy for asymptotic test power, and test which uses extra data for bandwidth selection. The 'extra data' test is designed simply to provide a best-case scenario for the bandwidth selection procedure which maximises asympiotic test power, but it cannot be used in practice as it has access to extra data compared to the other tests. In order to ensure that our tests always have correct levels for all bandwidth values, dimensions and sample sizes, we the parametric bootstrap in our experiments.
7

---

4.1 Alternative bandwidth selection approaches
Gretton al. 2012a proposed to use the median heuristic as kernel bandwidth, it consists in the median of the L disttneess between the samples given by
Amed == median[||z; 2y : -
Gretton et al. (0122) first proposed, for the two-sample problem using a linear-time MMD estimator, to split the data and to use half of it to select an 'optimal' bandwidth which maximises a proxy for asymptotic power. This procedure was extended to quadratic-timg estimators and to the goodness- of-fit framework by Pitkrittum et al. (2017). (Sutherland et al. (0177) and Liu et al. (2020). These strategies rely on the asymptotic normality of the test statistic under Ha. In our setting, the asymptotic power proxy to maximise is the ratio
KSD p. (XN) ÕH.
where 0 is closed-for form regularised positive estimator of the asymptotic variance of KSD p.k under H. (Liu et al. 2020, Equation 5). In our experiments, we also consider a test which has access to NN extra samples drawn from q select an 'optimal" bandwidth to run the KSD test the original N samples Xx. This test is interesting to compare to because it uses an 'optimal' bandwidth without being detrimental to power (as it uses all N samples X to run the test with the selected bandwidth).
4.2 Experimental details
Inspired from Theorem B.5 in each experiments, we use KSDAGG with different collections of bandwidths of the form ((,,, ()=,+)=== (2 Amed : = l_,..... L+ } for the median bandwidth Amed and integers 8_ < 4 with uniform weights wx == 11/(4 - - + 1). For the tests which split the data, we select the bandwidth, out of the collection A(E_, (4), which maximises the power proxy discussed
in Section 4.1 All our experiments are run with level a = 0.05 using the IMQ kernel defined in Equation 7 with parameter B& 0.5. We use a parametric bootstrap with B1 B- 500 bootstrapped KSD values to compute the adjusted test thresholds, and B3 = 50 steps of bisection method to estimate the correction u, Equation 6 For our aggregated test, we have also designed another collection which is parameter-free (no varying parameters across experiments) and performs as well as the previous variant whose parameters are chosen appropriately for each experiments. The collection is obtained using the maximal inter-sample distance normalised by the dimension (see details in Appendix B). We denote the resulting robust test by KSDAGG* for which we use either a wild or parametric bootstrap with Bi = B2 2000 and B3- = 50, this is the variant we recommend using in practice. To estimate the probability of rejecting the null hypothesis, we average the test outputs across 200 repetitions. All experiments have been 3960X 24 Cores 128Gb RAM CPU at 3. 3,8GHz, the runtime is of the order of a couple of hours (significant speedup can be obtained by using parallel computing). We have used the implementation of litkrittum et al.] (2017) to sample from a Gaussian -ernnuulll Restricted Boltzmann Machine, and Phillip Lippe's implementation of MNIST Normalizing Flows, both under the MIT license.
AMD Ryzen Threadripper
4.3 Gamma distribution
For our first experiment, we consider a one-dimensional Gamma distribution with shape parameter and scale parameter 5 as the model For g, we draw 500 samples from Gamma distribution with the same scale parameter 5 and with shifted shape parameter + a for s E 0.1, 0.2, 0.3, 0.4). We consider the collection of bandwidths A(0, 10).
The results we obtained are presented in Figure la We observe that all tests have the prescribed level 0.05 under the null hypothesis, which corresponds to the case = 0. As the shift parameter increases, the two densities p and q become more different and rejection of the null becomes an easier task, thus the test power increases. Our aggregated test KSDAGG achieves the same power as the KSD test with an 'optimal' bandwidth selected using extra data by maximizing the proxy for asymptotic power. The median test obtains only slightly lower power, this closeness in power can be explained by the fact that this one-dimensional problem is a simple one. All four tests KSDAGG AO, 10), KSDAGG* KSD median, and KSD split, all achieve very similar power. We note that the normal splitting test has significantly lower power: this is because, even though it uses an 'optimal' bandwidth, it is then run on only half the data, which results in loss of power.
8

---

Probability of rejecting Ho
Probubility of rejecting Ho
0.8
0.8
0.0
0.0
0.4
0.0
0.0
0.4
0.00
0.03
Shape parameter shift
Perturbation standard deviation
KSDAGG A(O, 10)
KSD median
KSDAGG A( 20,0)
KSD median
KSDAcc
KSD split
KSDAcc
KSD split
KSD split data
KSD split. data
(a)
(b)
Figure 1: (a) Gamma distribution. (b) Gaussian-Beroulli Restricted Boltzmann Machine.
4.4
Gaussian-Bernoulle Restricted Boltzmann Machine
As first considered by Liu et al. (016)) for goodness-of-ff testing using the KSD, we consider a Goussian-Bernoulle Restricted Boltzmann Machine. It is a graphical model with binary hidden variable E 1-1,1 and continuous observable variable x E Rdd Those variables have joint density
p(z,h) h) =
Z exp -" Bh +b
x + c
2 |1=1
where Z is an unknown normalizing constant. By marginalising over h, we obtain the density of
p(x)
Σ p(a, h).
We can sample from it using a Gibbs sampler with 2000 burn-in iterations. We use the dimensions 50 and d₁ 40 as considered by Jitkrittum al. (2017) and Grathwohl al. (2020). Even though computing is intractable for large dimension dn. the score function admits convenient closed-form expression
exp exp x
logp(æ) =
ex (2 xc))++))++
We draw the components of b and from Gaussian standard distributions and sample Rademacher variables taking values {, 1} for the elements of B for the model p. We draw 1000 samples from distribution & which is constructed in similar way as p but with the difference that some Gaussian noise (O, or) is injected into each of the elements of B. For the standard deviations of the perturbations, consider E {0, 0.01, 0.02, 0.03). We use the collection A(-20) 0) (different from Section 4.3 for KSDAGG* we use a wild bootstrap, the results are provided in Figure [b
Again, we observe that our aggregated tests KSDAGG A(0, 20) and KSDAGG* match the power obtained by the test which uses extra data to select an 'optimal' bandwidth. This means that, this experiment, the aggregated tests obtain the same power the 'best' single test. The difference with the median heuristic test is significant this experiment, and the splitting test obtains the lowest power of the four tests. Again, all tests have well-calibrated levels (case 0) and increasing the noise level a results in more power for all the tests.
4.5 MNIST Normalizing Flow
Finally, we consider high-dimensional problem working with images in dimensions 28 784. We consider a multi-scale Normalizing Flow (Dinh et al. 2017, Kingma and Dhariwal 2018) which has been trained on the MNIST dataset (LeCun et al. 1998 2010). it is generative model which has

---

6
7 6
9
8
$
3
(b)
(c)
Figure 2: (a) Digits from the MNIST dataset. (b, c) Digits sampled from the Normalizing Flow.
probability density p. As observed in Figure 2 some samples produced by the model can look exactly like MNIST digits, while others do not resemble digits. This Normalizing Flow has been trained to "ideally' produce samples from the MNIST dataset. We are interested in whether or not we can detect able tell if those
the difference in densities. Given some images of digits, from the Normalizing Flow model? We consider the case where the samples from @ are drawn from the MNIST dataset (power experiment), and the case where the images from g are sampled from the Normalizing Flow model (level experiment, confirming performance for the power experiment). The experiments are run with the collection of bandwidths (--20, 0). The results are displayed in Figure 3a and Figure 3b We use a parametric bootstrap for KSDAGG"
sampled
observe that the four tests have correct levels (around 0.05) for the five different sample sizes considered (the small fluctuations about the designed test level can be explained by the fact that
In Figure 5a
averaging 200 test outputs estimate these levels). The well-calibrated levels obtained Figure 3a demonstrate the validity of the power results presented in Figure 5
As seen in Figure 3b only our aggregated tests KSDAGG and KSDAGG* obtain high power; they are able to detect that MNIST samples are not drawn from the Normalizing Flow. The power of the other tests increases only marginally as the sample size increases. The test which uses extra data to select an 'optimal' bandwidth performs poorly when compared to the aggregated tests. This could be explained by the fact that this test selects the bandwidth using proxy for the asymptotic power, and that in this high- high-dimensional setting, the asymptotic regime is not attained with sample sizes below and for details regarding selected bandwidths and for reported runtimes.
500. See Appendices
Probabiiity of rejecting Ho
0.8
0.6
Sample
KSDAGG
KSD
KSD split
KSD split
M(20,0)
KSDAGG
0.4
100
0.05
0,035
0.04
0.05
0.04
200
0.06
0.05
0.055
0.2
300
0.045
0.055
0.085
0.08
0.085
400
0.04
0,03
0,055
0,03
0.055
0.0
500
0.035
0.035
0.045
0.04
0.045
100
200
300
400
500
(a)
Sample size
KSDAGG A(-20, 0)
KSD median
KSDAGG
KSD split
KSD split extra data
(b)
Figure 3: Normalizing Flow MNIST. (a) Level experiment. (b) Power experiment.
5
Acknowledgements
Antonin Schrab acknowledges support from the U.K. Research and Innovation (EP/S021566/1 Benjamin Guedj acknowledges partial support by the U.S. Army Research Laboratory and the U.S. Army Research Office, and by the U.K. Ministry of Defence and the U.K. Engineering and Physical Sciences Research Council (EP/RO13616/1) and by the French National Agency for Research MANN-18-CEE00001---0 & ANR-18-CCE23-0115-02) Arthur Gretton acknowledges support from the Gatsby Charitable Foundation.
10

---

References
Albert, M., Laurent, B., Marrel, A., and Meynaoui, (2022). Adaptive test of independence based on HSIC measures. The Annals of Statistics, 50(2):858-877
Anastasiou, A., Barp, A., Briol, F.-X., Ebner, B., Gaunt, R. E., Ghaderinezhad, F., Gorham, J., Gretton, A., Ley, C., Liu, Q. al. (2021). Stein's method meets statisties: A review of some recent developments. arXiv preprint arXiv:2105.03481
Aronszajn, N. (1950). Theory of reproducing kernels. Transactions of the American Mathematical Society, 68(3)3337-404
Balasubramanian, K., Li, T., and Yuan, M. (2021). On the optimality of kernel-embedding based goodness-of-fit tests. Journal of Machine Learning Research, 22(1).
Baraud, (2002). Non-asymptotic minimax rates of testing in signal detection. Bernoulli, 1(8(5):577- 606).
Barp, A., Briol, F., Duncan, A. B., Girolami, M. A., and Mackey, L. W. (2019). Minimum Stein discrepancy estimators. In Wallach, H. M., Larochelle, H., Beygelzimer, A., d' Alchh-BBBee F., Fox, E. B., and Garett, R., editors, Advances in Neural Information Processing Systems.
Carmeli, C., De Vito, E., Toigo, A., and Umanitá, V. (2010). Vector valued reproducing kernel Hilbert spaces and universality. Analysis and Applications. 8001):19-61.
Chebyshev, P. L. (1899). Oeuvres. Commissionaires de l'Académie Impériale des Sciences, 1.
Chwialkowski, K., Sejdinovic, D., and Gretton, A. (2014). A wild bootstrap for degenerate kernel tests. In Advances in neural information processing systems, pages 3608-3616.
Chwialkowski, K., Strathmann, H., and Gretton, (2016). kernel test of goodness of fit. In International Conference Machine Learning, pages 2606-2615. PMLR.
de la Peña, V. H. and Giné, E. (1999). Decoupling: From Dependence to Independence. Springer Science & Business Media.
Dinh, I.,, Sohl-Dickstein, J., and Bengio, S. (2017). Density estimation using real NVP. In International Conference on Learning Representations.
Dvoretzky, A., Kiefer, J., and Wolfowitz, J. (1956). Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, pages 642-669.
Fernandez, and Gretton, A. (2019). A maximum- saiiiuuu-mman-ddiccreaaanng discrepancy goodness-of-fit test for censored data. In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 2966-2975. PMLR.
Fernandez, T. and Rivera, N. (2022). A general framework for the analysis of kernel-based tests. arXiv preprint 2xXh:2200900/224
Fernandez, T., Rivera, N., Xu, W., and Gretton, A. (2020). Kernelized Stein discrepancy tests of goodness-of-fit for time-to-event data. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 3112-3122. PMLR.
Freidling, T., Poignard, B., Climente-Gonzálee H., and Yamada, M. (2021). Post-selection inference with HSIC-Lasso. In International Conference Machine Learning, pages 3439-3448. PMLR.
Fromont, M., Laurent, B., Lerasle, M., and Reynaud- Reynaud-Bouret, P. (2012). Kernels based tests with non-asymptotic bootstrap approaches for two-sample problems. In Conference on Learning Theory, PMLR.
Fromont, M., Laurent, B., and Reynaud-Bouret, P. (2013). The two-sample problem for Poisson processes: Adaptive tests with a nonasymptotic wild bootstrap approach. The Annals of Statistics, 4133)11431-1411.

---

Gorham, J. and Mackey, L. (2017). Measuring sample quality with kernels. In International Conference on Machine Learning, pages 1292-1301. PMLR.
Gorham, J. and Mackey, L. W. (2015). Measuring sample quality with Stein's method. In Cortes, C., Lawrence, N. D., Lee, D. D., Sugiyama, M., and Garnett, R., editors, Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 226-234.
Grathwohl, W. Wang, K.-C., Jacobsen, J.-H., Duvenaud, D., and Zemel, R. (2020). Learning the Stein discrepancy for training and evaluating energy-based models without sampling. In International Conference Machine Learning, pages 3732-3747. PMLR.
Gretton, A., Borgwardt, K. M., Rasch, M. J., Schölkopf, B., and Smola, A. (2012a). A kernel two-sample test. Journal of Machine Learning Research, 13:723-773.
Gretton, A., Bousquet, O., Smola, A., and Schölkopf, B. (2005). Measuring statistical dependence with Hilhert-Schmidt norms. In International Conference Algorithmic Learning Theory. Springer.
Gretton, A., Sejdinovic, D., Strathmann, H., Balakrishnan, S., Pontil, M., Fukumizu, K., and Sriperumbudur, B. K. (2012b). Optimal kernel choice for large-scale two-sample tests. In Advances in Neural Information Processing Systems, volume 1, pages 1205-1213.
Hoeffding, W. (1992). class of statisties with asymptotically normal distribution. In Breakthroughs in Statistics, pages 308-334. Springer.
Huggins, J. and Mackey, L.. (2018). Random feature Stein discrepancies. Advances in Neural Information Processing Systems, 31.
Ingster, (1987). Minimax testing of nonparametric hypotheses on distribution density in the Lp metrics. Theory of Probubility & its Applications, (1):3333-337.
Ingster, Y. I. (1989). An asymptotically minimax test of the hypothesis of independence. Journal of Soviet Mathematics, 1(44:466-476).
Ingster, I. (1993a). Asymptotically minimax hypothesis testing for nonparametric alternatives. Journal of Soviet Mathematics, 1(44:466-476)
Ingster, Y. I. (1993b). Minimax testing of the hypothesis of independence for ellipsoids in lp. Zapiski Nauchnykh Seminarov POMI, 1(20::77-77).
Jitkrittum, W., Kanagawa, H., and Schölkopf, B. (2020). Testing goodness of fit of conditional density models with kernels. In Peters, J. and Sontag, D., editors, Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence ConiceeUAA (UAI), volume 124 of Proceedings of Machine Learning Research, pages 221 221-230. PMLR.
Jitkrittum, W., Xu, W., Szabó, Z., Fukumizu, K., and Gretton, A. (2017). A linear-time kernel goodness-of-fit test. In Advances in Neural Information Processing Systems, pages 262-271
Kanagawa, H., Jitkrituum, W., Mackey, I.., Fukumizu, K., and Gretton, A. (2019). A kernel Stein test for comparing latent variable models. arXiv: /007000590 [cs, staf]. arXiv: 1907.00586.
Key, O., Fernandez, T., Gretton, A., and Briol, F.-X. (2021). Composite goodness-of-fit tests with kernels. arXiv preprint urXiv:2111.10275.
Kim, I., Balakrishnan, S., and Wasserman, L. (2022). Minimax optimality of permutation tests. The Annals of Statistics, 50(1):22--
Kingma, D. P. and Dhariwal, P. (2018). Glow: Generative flow with invertible 1x1 convolutions. In Advances in Neural Information Processing Systems, pages 10236-10245.
Korba, A., Lubbi-FFranowski P., Majewski, S., and Ablin, P. (2021). Kernel Stein discrepancy descent. In Meila, M. and Zhang, T., editors, Proceedings of the 38th International Conference on Machine Learning, ICMI 2021, 18-24 July 2021, volume 139 Proceedings of Machine Learning Research, pages 5719-5730. PMLR.
12

---

Kübler, J. M., Jitkrittum, W., Schölkopf, B., and Muandet, K. (2020). Learning kernel tests without data splitting. In Advances in Neural Information Processing Systems 33, pages 6245-6255 Curran Associates, Inc.
Kübler, J. M., Jitkrittum, W., Schölkopf, B., and Muandet, K. (2022). A witness two-sample test. In International Conference on Artificial Intelligence and Statistics, pages 1403-1419. PMLR.
LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P. (1998). buddeent-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-232)
LeCun, Y., Cortes, C., and Burges, C. (2010). MNIST handwritten digit database. AT&T Labs.
Leucht, A. (2012). Degenerate U- and -sstatistics under weak dependence: Asymptotic theory and bootstrap consistency. Bernoulli, 18(2)5522 585.
Leucht, A. and Neumann, M. H. (2013). Dependent wild bootstrap for degenerate and V-statistics. Journal of Multivariate Analysis, 117:257-280.
Li, T. and Yuan, M. (2019). On the optimality of gaussian kernel based nonparametric tests against smooth alternatives. arXiv preprint 17XXvx:909.033000
Lim, J. N., Yamada, M., Jitkrittum, W., Terada, Y., Matsui, S., and Shimodaira, H. (2020). More powerful selective kernel tests for feature selection. International Conference on Artificial Intelligence and Statistics, pages 820- 830. PMLR.
Lim, N., Yamada, M., Schölkopf, B., and Jitkrittum, W. (2019). Kernel Stein tests for multiple model comparison. In Advances in Neural Information Processing Systems, pages 2240-2250.
Liu, F., Xu, W., Lu, J., Zhang. G., Gretton, A., and Sutherland, D. J. (2020). Learning deep kernels for non-parametric two-sample tests. International Conference on Machine Learning.
Liu, Q., Lee, J., and Jordan, M. (2016). A kernelized Stein discrepancy for goodness-of tests. In International Conference on Machine Learning, pages 276-284. PMLR.
Massart, (1990). The tight constant in the Kvorerkky-KieferrWoofovvii inequality. The Annals of Probability, (269):16691228..
Oates, C. J., Cockayne, J., Briol, F.-.., and Girolami, M. (2019). Convergence rates for class of estimators based on Stein's 's method. Bernoulli, 25(2):114) - 1159.
Oates, C. J. and Girolami, M. A. (2016). Control functionals for quasi-Monte Carlo integration. In Gretton, A. and Robert, C. C., editors, Proceedings of the 19th International Conference on Arlificial Intelligence and Statistics, AISTATS 2016, Cadiz, Spain, May 9-11, 2016, volume 51 of JMLR Workshop and Conference Proceedings, pages 56-65. JMLR.org.
Romano, J. P. and Wolf, M. (2005). Exact and approximate stepdown methods for multiple hypothesis testing. Journal of the American Statistical Association, 100(469):94-108.
Schrab, A., Kim, L,, Albert, M., Laurent, B., Guedj, B., and Gretton, A. (2021). MMD Aggregated two-sample test, arXiv preprint 10 150733.
Schrab, A., Kim, I., Guedj, B., and Gretton, A. (2022). Efficient aggregated kernel tests using incomplete U-statistics. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022.
Shao, X. (2010). The dependent wild bootstrap. Journal of the American Statistical Association, 105(489):218-23.
Sriperumbudur, B. K., Fukumizu, K., and Lanckriet, G. R. (2011). Universality, characteristic kernels and RKHS emhedding of measures. Journal of Machine Learning Research, 12(7).
Stein, C. (1972). A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. In Proceedings of the sixth Berkeley symposium on mathematical statistics and probability, volume 6, pages 583-603, University of California Press.
13

---

Stein, C., Diaconis, P., Holmes, S., and Reinert, G. (2004). Use of exchangeable pairs in the analysis of simulations. Lecture Notes-Monograph Series, pages 1-26.
Stute, W., Manteiga, W. G., and Quindimil, M. P. (1993). Bootstrap based goodness-of-fit-eess.. Meirika, 40(1):243-256.
Sutherland, D. J., Tung, H.-Y., Strathmann, H., De, S., Ramdas, A., Smola, A., and Gretton, A. (2017). Generative models and model criticism via optimized maximum mean discrepancy. In International Conference Learning Representations.
Tolstikhin, I., Sriperumbudur, B. K., and Schölkopf, B. (2016). Minimax estimation of maximum mean discrepancy with radial kernels. Advances in Neural Information Processing Systems, 29.
Weckbecker, M., Xu, W., and Reinert, G. (2022). On RKHS choices for assessing graph generators via kernel Stein statistics. arXiv preprint 2xXiv:2200005740
Wenliang, L. K. and Kanagawa, H. (2020). Blindness of score-based methods to isolated components and mixing proportions. arXiv preprint arXiv:2008.1008:
Wynne, G. and Duncan, A. B. (2022). A kernel two-sample test for functional data. Journal of Machine Learning Research, 23(73)11-31.
Wynne, G., Kasprzak, M., and Duncan, A. B. (2022). A spectral representation of kernel stein discrepancy with application to goodness-of-fit tests for measures on infinite dimensional hilbert spaces. arXiv preprint arXiv:2206. 04552.
Xu, W. (2021). Generalised kernel Stein discrepancy (GKSD): A unifying approach for non- parametric goodness-of-fe testing. arXiv preprint arXiv:2 /2
Xu, W. (2022). Standardisation-funeee function kernel Stein discrepancy: A unifying view on kernel Stein discrepancy tests for goodness-of-fit In Camps- Vallss-Valls, G., Ruiz, F. J. R., and Valera, I., editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 1575-1597. PMLR.
Xu, W. and Matsuda, T. (2020). A Stein goodness-of-it test for directional distributions. In Chiappa, S. and Calandra, R., editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statisticx, volume 108 of Proceedings of Machine Learning Research, pages 320-330. PMLR.
Xu, W. and Matsuda, T. (2021). Interpretable Stein goodness-off -ff-ftt tests on Riemannian manifold. In Meila, M. and Zhang, T., editors. Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1 11502-11513. PMLR.
Xu, W. and Reinert, G. (2021). A Stein goodness-of-test for exponential random graph models. In Banerjee, A. and Fukumizu, K., editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 423. PMLR.
Xu, W. and Reinert, G. (2022a). AgraSSt: Approximate graph Stein statistics for interpretable assessment of implicit graph generators. arXiv preprint arXiv:2203.0366
Xu, W. and Reinert, G. (2022b). kernelised Stein statistic for assessing implicit generative models. arXiv preprint
Yamada, M., Wu, D., Tsai, Y. H., Ohta, H., Salakhutdinov, R., Takeuchi, I., and Fukumizu, K. (2019). Post selection inference with incomplete maximum mean discrepancy estimator. In International Conference on Learning Representations.
Zhang, M., Key, O., Hayes, P., Barber, D., Paige, B., and Briol, F.-X. (2022). Towards healing the blindness of score matching. arXiv preprint arXiv:2209.07390
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Appendix H
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendices.
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either the supplemental material or as a URL)? [Yes] See link in httts:///iithnr
Section D
com/ wwwoiiishhaaaksdaaa.e...ee -aper
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 4.2
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [N/A] Since the test outputs are binary (0 or 1), there no need to include error bars since these are deterministic given the average which is plotted.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 4.2
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes] See Section 4.2
(b) Did you mention the license of the assets? [Yes] See Section
(c) Did you include any new assets either the supplemental material or as URL? Yes]
See link in Section 1 https: thub. com/ att//annnnnncaaaaaaaa www.innahaaaaaaaaagegeeee paper
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "fpUlJ3r_RYB", "reviewer": "Reviewer_ys6t", "summary": "This work provides guarantees for goodness-of-fit tests (whether a given set of samples comes from a given null distribution) based on kernel stein discrepancies (KSD). They construct a test that allows for kernel selection to maximize power by using all data rather than using data split while maintaining the type I error level. In particular, the work extends the idea of aggregated tests already used for the two-sample problems via MMDs, and the independence problem via HSIC, to the goodness-of-fit setting via KSD. To estimate the test thresholds, they make use of a Monte Carlo strategy based on (a) parametric bootstrap (which requires samples from the null distribution p) and provides a non-asymptotic level, and power; and (b) wild bootstrap that provides the same guarantees asymptotically. ", "questions": "1. Can the authors clarify what the constant C depends on in Theorem 3.1?\n\n2. Corollary 3.4 has a logarithmic inflation factor in front of the sample size N (in the second term). If one uses an equal sample split to do kernel selection first and then test, isn't that factor just 2? If yes, then is KSDAGG better than sample split only if log(#kernels) <=2? If not, it would help to clarify what the rate for sample split is known to be.\n\n3.  Given the non-transparent nature of the Stein operator, can the authors provide some examples of q's that satisfy theorem 3.1 / 3.3 for a given simple distribution p, say Gaussian distribution? The authors make a comment in l 175--176, but it would be helpful to provide concrete examples (also relevant for comment 2).\n\n4. In Proposition 3.2, is there no requirement on B1, B2, and B3?\n\n5. Can the authors state a mathematically precise asymptotic result for wild bootstrap? (Like how is the limit for N to infinity taken?) \n\n6. Is there no setting, where the KSD median would be competitive? It would be helpful to comment on the limitations of KSDAGG, namely when does KSDAGG either perform poorly or not better than the other sensible benchmarks. \n\n7. Do we really need to know the model density? Or just the gradient of log density, and a sampler of p for parametric bootstrap? (OPTIONAL: What if the sampler is approximate?)\n\n8. Given the unknown nature of constants in the uniform separation rate, can the authors comment on how the power degrades when the separation deteriorates from the mentioned lower bound?\n\nMinor comments: \n\n- To my understanding from the proof, Theorem 3.3 is effectively a corollary of Theorem 3.1 and a union bound; it would be helpful to provide that comment if true?\n", "limitations": "See questions.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ Their Theorem 3.1 characterizes the uniform separation rate between the null and the alternative densities so as to assert a certain power for a given test, and Theorem 3.3 extends it to multiple aggregated tests. The authors provide several numerical experiments that showcase that KSDAGG performs better than some other benchmarks.\n\n+ Writing of the paper is very good, and the authors cover a fair amount of related work! \n\n- This work applies only to those settings where model density is known. \n\nFor more comments, see questions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "R1y1pUORQ3a", "reviewer": "Reviewer_ZqFj", "summary": "This paper proposed a new goodness-of-fit (GOF) testing method based on KSD, which sidesteps the challenge of selecting a single kernel for the test. Instead, the proposed method, KSDAGG, can aggregate tests with a collection of kernels so that it maximises the test power over these kernels. This is achieved by performing a GOF test with each kernel in the collection and rejecting the null hypothesis if any one of the tests rejects it. To ensure that the KSDAGG can still control the user-defined type-I error, the author proposed a bisection algorithm to select the proper test interval for each kernel in the collection. Theoretically, the author showed a condition for a uniform separation rate so that the KSDAGG can also control the type-II error. This condition shows that KSDAGG achieves the smallest uniform separation rate of the collection.\n\nEmpirically, the author applied KSDAGG to the kernel bandwidth selection problem and compared it with kernel selection baselines including data splitting, median heuristic and kernel selection with extra data. It shows that it achieves similar test power as the kernel selection with extra data on synthetic data and the best performance for MNIST normalising flow. ", "questions": "1. Like I have mentioned, the author should consider elaborating more on their novel contributions: why the extension to GOF is not trivial? Is it because of the derivation of the bound for uniform separation rate?\n\n2. Another concern is the computational cost. It seems that with the aggregation trick, it performs a single test for each kernel in the collection. This means with a large collection (or the number of bootstrap samples), the computational cost can be much larger than a single test (with kernel selection). Can the author provide the performances with wall clock time? I am curious to see the trade-off. \n\n3. For a fixed set of weight $w_k$ and level $\\alpha$, do we have a \"fixed\" choice of $u_\\alpha$? Clearly, from the bisection algorithm, we won't have exactly the same $u_\\alpha$, but they are closed to each other. So here \"fixed\" means a very distinct set of $u_\\alpha$. Another question is can we select the best kernel using the KSDAGG. For example, if one kernel in the collection rejects the null hypothesis, does it mean this is the best kernel?\n\n4. The introduction of KSD can be improved. For example, instead of directly introducing KSD and the complicated Stein kernel and Stein identity. Maybe consider adding a bit of intuition on Stein discrepancy. In line 87, consider adding one sentence to explain what is the consistency of the Stein test? Also for corollary 3.4, it seems that this is identical to theorem 3.3, which doesn't need to be re-introduced. Saving this space allows the author to expand a bit more on the background. \n\n5. For the synthetic experiment, why KSDAGG is better than KSD split extra data in RBM? It will be interesting to see the optimised bandwidth and the bandwidth of one that rejects the null in the collection. ", "limitations": "This paper does not have any negative societal impact. But this paper does not seem to discuss its limitations enough. For example, the trade-off between high computational cost and test power. It seems that this method cannot be applied to kernels that require training like the deep kernel. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**:\nThis paper takes an alternative point of view on the kernel selection problem, where it extends the recently proposed two-sample test aggregation method to goodness-of-fit with Stein discrepancy. \nThe presentation clarity is reasonable but can be much improved. In terms of significance, I think the targeted community is generally limited but it is a nice addition to it. \n\n**Weakness**:\nOne of my confusions is its contribution. The author mentioned that the aggregation trick is not novel, which has already been proposed in the two-sample test. Thus, I fail to see the main contributions of KSDAGG. I saw the contribution section but I suggest the author summarise what are the key points and why they are novel. For example, why the extension to the GOF test is non-trivial (expand a bit on the challenge mentioned in related work?), what method do I use to solve this non-trivial extension, etc. So that the contribution and novelty are clearer.  \n\nIn terms of clarity, the background material to KSD is a bit dense. Since I have worked with the Stein method before, it is clear to me, but I can see that for a more general audience, it can be a bit difficult to understand. I suggest considering adding a more detailed background section in the appendix?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LXuucxdJHyO", "reviewer": "Reviewer_CDhe", "summary": "In this work, the authors propose a natural extension to the existing KSD goodness of fit tests, but allowing aggregate testing over multiple kernels (in particular, multiple kernel hyper-parameters) without requiring strategies such as data-splitting etc.    They achieve this by rescaling the critical value of each individual test by a positive weight, summing up to <= 1.  When the weights are equal to 1/N (where N is the number of tests), this is essentially a Bonferroni-type correction for aggregating finitely many independent tests.   \n\nThe authors provide an algorithm for performing this multiple testing protocol, based on wild-bootstrap or parametric bootstrap.  They then establish control over type II error through a uniform separation rate (USR) argument. \n\nMany of the arguments are similar to what is proposed in the preprint [Schrab, A., Kim, I., Albert, M., Laurent, B., Guedj, B., and Gretton, A. (2021). MMD aggregated two-sample test], which considers the similar case of MMD testing.  But in that situation things are more straightforward since terms within the USR argument can be bounded explicitly in terms of best approximation rates for densities with a given regularity, yielding minimax optimal rates, etc.     In this setting it is far less straightforward to obtain similar bounds.", "questions": "1. Do the authors have any intuition on the behaviour of the terms in the uniform separate rates established for the aggregate test in terms of dimension?  Even just heuristics or a case study on a Gaussian Stein kernel would be of interest.  \n2. Do the authors have any recommendations on the choice of the weights?  This seems arbitrary and not really addressed anywhere in this work?  Is there any scenario where taking the sum to be < 1 make sense?   \n3.  One often wishes to select a kernel over an infinite continuum family of parameters, and it's sometimes less obvious how to discretise this.  Are the authors aware of any strategies which would enable them to generalise to this setting.", "limitations": "I am satisfied with how the authors addressed the limitations of this work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* (Quality + Clarity) It is very well written.  The arguments are presented cleanly which made following the proofs quite easy.   \n* (Significance) It tackles an important challenge which provides a principled alternative to the median heuristic or data-splitting approaches to addressing this problem.\n\nWeaknesses:\n * (Originality) It is a bit incremental, and builds very obviously on previous work which tackled aggregate tests for MMD in the same light.\n * (Significance) While the uniform separation rates established in this paper are of theoretical interest, they aren't actionable in any manner due to the complexity of the Stein kernel.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept