Efficient Aggregated Kernel Tests using Incomplete $U$-statistics
Authors: Antonin Schrab
Ilmun Kim
Benjamin Guedj
Arthur Gretton
Venue: NeurIPS 2022 Accept (2022)
Keywords: kernel methods
hypothesis tests
adaptivity

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

Efficient Aggregated Kernel Tests using Incomplete U-statistics
Antonin Schrab Centre for Artificial Intelligence Gatsby Computational Neuroscience Unit University College London & Inria London a. schhabuucl..... ac.uk
Ilmun Kim
Department of Statistics & Data Science
Department of Applied Statistics
Yonsei University
lmmu@yoonsei ac
Benjamin Guedj
Arthur Gretton
Centre for Artificial Intelligence University College London & Inria London b. quedj@ucl ac
Gatsby Computational Neuroscience Unit University College London arthur grwttonggaaal.........m.m. com
Abstract
We propose series of computationally efficient nonparametric tests for the two- sample, independence, and goodness-of-fit problems, using the Maximum Mean Discrepancy (MMD), Hilbert Schmidt Independence Criterion (HSIC), and Ker- nel Stein Discrepancy (KSD), respectively. Our test statistics are incomplete U-statisties, with computational cost that interpolates between linear time in the number of samples, and quadratic time, as associated with classical U-statistic tests. The three proposed tests aggregate over several kernel bandwidths to detect departures from the null on various scales: we call the resulting tests MMDAggIne HSICAggInc and KSDAggInc. This procedure provides solution to the funda- mental kernel selection problem as we can aggregate large number of kernels with several bandwidths without incurring a significant loss of test power. For the test thresholds, we derive quantile bound for wild bootstrapped incomplete U-staaisticss, which is independent interest. We derive non-asymptotic uniform separation rates for MMDAggInc and HSICAggInc, and quantify exactly the trade- off between computational efficiency and the attainable rates: this result is novel for tests based on incomplete U-statistics, to our knowledge. We further show that in the quadratic- time case, the wild bootstrap incurs no penalty to test power over the more widespread permutation-bass approach, since both attain the same minimax optimal rates (which in turn match the rates that use oracle quantiles). We support our claims with numerical experiments tational efficiency and test power. In all three testing frameworks, the linear-time versions of proposed tests perform least as well as the current linear-time state-of-the-art tests.
the trade-off between compu-
Introduction
Nonparametric hypothesis testing is fundamental field of statistics, and is widely used by the machine learning community and practitioners in numerous other fields, due the increasing availability of huge amounts of data. When dealing with large-scale datasets, computational cost can quickly emerge major issue which might prevent from using expensive tests practice; constructing efficient tests is therefore crucial for their real-world applications. this paper, we construct kernel-base based aggregated tests using incomplete U-statisties (Blom 1976) for the two-sample, independence and
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

goodness-of-fit problems (which we detail in Section 2 The quadratic-tima aggregation procedure has been shown to result in powerful tests (Fromont al. 2012 Fromont et al., 2013 Albert et al.)
2022, Schhab et al., 2021 2022), we propose efficient variants of these well-studied tests, with computational cost interpolating from the classical quadratic-time regime to the linear-time one.
Related work: aggregated tests. Kernel selection (or kernel bandwidth selection) is a fundamental problem in nonparametric hypothesis testing as this choice has major influence on test power. Motivated by this problem, non-asymptotic aggregated tests, which combine tests with different
kernel bandwidths, have been proposed for the two- saomal (Fromont et al. 2012 2013 Kim et al.
2022 Schrab et al. 2021). independence (Albert et al. 2022] Kim et al. (2022) and goodness- of fit (Schrab et al., (022) testing frameworks. Li and Yuan (011 and braammmaannnnn al. (202T) construct similar aggregated tests for these three problems. with the difference that they work in the
asymptotic regime. All the mentioned works study aggregated tests in terms of uniform separation rates (Baraud 2002). Those rates depend on the sample size and satisfy the following property: if the n,--norm difference between the densities is greater than the uniform separation rate, then the test guaranteed to have high power. All aggregated kernel-based tests in the existing literature have been studied using U-statistic estimators (Hoeffding. 1992) with tests running in quadratic time.
Related work: efficient kernel tests. Several linear-time kernel tests have been proposed for those three testing frameworks. Those include tests using classical linear-time estimators with median bandwidth (Gretton et al. [2012a] Liu et al. 2016) or selecting an optimal bandwidth on held-out data to maximize power (Gretton et al., 2012b). tests using eigenspectrum approximation (Gretton et al.) 2009), tests using post-selection inference for adaptive kernel selection with incomplete -sstatistics (Yamada et al. 2018 2019: Lim et al. 2019, 2020 Kübler et al.) 2020 Freidling et al.] [022] J tests which use Nyström approximation of the asymptotic null distribution (Zang et a 2018] 2018|Cherraoui
et al. 2022). random Fourier features tests Zhang et al. 2018 Zhao and Meng | (Chiiakooski
et al. 2015), tests based on random feature Stein discrepancies (Huggins and Mackey [0188), the
adaptive tests which use features selected on held-out data to maximize power (Jitkrittum et al. 2016
2017a b). as well as tests using neural networks to learn a discrepancy (Grathwohl et al. 20200. We
also point out the very relevant works of Kübler et al. (2022) on a quadratic- quadratic-time test, and of Ho and
Shich (206), Zaremba et al. (2133) and Zhang et al. (2018) on the use of block U-statisties with complexity (NN.5 for block size v N where N is the sample size.
Contributions and outline. In Section we present the three testing problems with their associated well-known quadratic- time kernel-based estimators (MMD, HSIC, KSD) which are U-statistics. We introduce three associated incomplete U-statistics estimators, which can be computed efficiently, in Section 3 We then provide quantile and variance bounds for generic incomplete U-statistics using wild bootstrap, in Section g We study the level and power guarantees at every finite sample sizes for our efficient tests using incomplete U-statistics for fixed kernel bandwidth, in Section S In particular, we obtain non non-asymptotic uniform separation rates for the two-sample and independence tests over a Sobolev ball, and show that these rates are minimax optimal up to the cost incurred for efficiency of the test. In Section 6 we propose our efficient aggregated tests which combine tests with multiple kernel bandwidths. We prove that the proposed tests are adaptive over Sobolev balls and achieve the same uniform separation rate (up to an iterated logarithmic term) as the tests with optimal bandwidths. As result of our analysis, have shown minimax optimality over Sobolev balls of the quadratic- time tests using quantiles estimated with a wild bootstrap. Whether this optimality result also holds for tests using the more general permutation-bant based procedure approximate HSIC quantiles, was an open problem formulated by Kim et al. (2022), we prove that it indeed holds in Section 7 As observed in Section g the linear-time versions of MMDAggIne, HSICAggInc and KSDAggIne retain high power, and either outperform or match the power of other state-of- the- lincar-time kernel tests. Our implementation of the tests and code for reproducibility of the experiments are available online under the MIT license: petps://githhe comtub..coomaaaa http://ooooinccaaaaaggnggeaa
2 Background
In this section, we briefly describe our main problems of interest, comprising the two-sample, independence and goodness-of-fii problems. probllssss We approach these problems from nonparametric point of view using the kernel-based statistics: MMD, HSIC, and KSD. We briefly introduce original forms of these statisties, which can be computed in quadratic time, and also discuss ways of calibrating tests proposed in the literature. The three quadratic-time expressions are presented in Appendix B

---

Two-sample testing, In this problem, we are given independent samples Xm = sxi) and Yn = (Xy)ss)gn consisting of i..d. random variables with respective probability density functions p and on R We assume we work with balanced sample sizes, that i ma n) X 1miinm n). We are interested in testing the null hypothesis Ho p = 9 against the alternative Hi : qi that is, we want to know if the samples come from the same distribution. Gretton et al. (2012al) propose nonparametric kernel test based on the Maximum Mean Discrepancy (MMD), a measure between probability distributions which uses a characteristic kernel k (Fukumizu et al. 2008 Sriperumbuduur al. 2011). It can be estimated using quadratic-time estimator (Gretton et al. 2012a Lemma 6)
which, as noted by Kim et al. (2022), can be expressed as two-sample U -statistc (both of second order) (Hoeftding 1992).
MMD, (Xmss kn)
Σ
Σ
MMD (X X2x Xxx))) h
(1)
(L,")) (J'EE
where 1o with a S b denotes the set of all a-tuples drawn without replacement from (1,...;10) so that [ = b (b + 1), and where, for æ1, 21, U2 E Rdd we let.
h MMD (x1, 22: 32) = k(x1, k(I1, 92) k(I2, 31) + (2).
(2)
Independence testing. In this problem, we have access to i.i.d. pairs of samples EN (Zi) ISiEN = ((X,, Xi)) with joint probability density Pay on IRd x RRd and marginals Pa on Rd== and Py on Rdd, We are interested in testing Ho : Pry = Pr Pyy against H, Pay # P2 2 Ppy that is, we want to know if two components of the pairs of samples are independent or dependent, Gretton et al. (2055 2008) propose a nonparametric kernel test based on the Hilbert Schmidt Independence Criterion (HSIC). It can be estimated using the quadratic-time estimator proposed by [Song al. 2201 Equation 5) which is a fourth-order one- sample U -tstatis
HSIC&,,(2N)
HSIC (Zi, Zj, Zo) lige
(3)
for characteristic kernels & on Rdd and on Rdd, Gretton 2015). and where for 2a (oa:ya)
Rd= Rd,, 1,...,4, 4, we let
1
(21, 22, 23, 24) = 4 1 (21,22; 23, x4)h MMD (y/1 y2: yo. 93. E.E
HSIC
MMD
(4)
Goodness-of-fi testing. For this problem, we are given a model density on Rd and i.i.d. samples
EN == (Zi) drawn from density q on Rd. The aim is again to test Ho : p = q against Hi : p + q. that is, we want to know if the samples have been drawn from the model. Chwialkowski et al. (2066) and Liu et al. (2016) both construct nonparametric goodness-of-fit test using the Kernel Stein Discrepancy (KSD). A quadratic-time KSD estimator can be computed as the second-order one-sample U-statistic,
KSD P.k (ZN) =
Σ (KJ)
KSD (Z,, Mi ( Zz),
(5)
where the Stein kernel KSD; Rd x gd R is defined Kpp
hg
KSD
(I, y) = (V logp(x) x))
logp(u)) (xx + v logp(u) Vak(I,))
a
(6)
log
()) dz,0y:
k(x,
In order to guarantee consistency of the Stein goodness-of-ft test (Chwialkowski et al. 2016 Theorem 2.2), we assume that the kernel ls is Co-universal (Carmeli al. 2010, Deñiiiion 4. 4.1) and that
p(2) 9(2)
Bg
KSD hk.p (2, 2)] ac
and
Eg
v log
All probability density functions in this paper are with respect the Lebesgue measure. We use the notation a S when there exists a constant C/ > such that I Cb. We similarly use the notation Z. We write a x bif a S 6 and a 2 b. We also use the convention that all constants are generically denoted by C, even though they might be different.
3

---

Quantile estimation. Multiple strategies have been proposed to estimate the quantiles of test statistics under the null for these three tests. We primarily focus on the wild bootstrap approach (Chwialkowski et al. (014)) though our results also hold using a parametric bootstrap for the goodness-of fit setting (Schrab et al., 2022). In Section t we show that the same uniform separation rates can be derived for HSIC quadratic-tima tests using permutations instead of a wild bootstrap.
More details on MMD, HSIC, KSD, and on quantile estimation are provided in Appendix B
3 Incomplete U-statistics for MMD, HSIC and KSD
As presented above, the quadratic-time statistics for the two-sample (MMD), independence (HSIC) and goodness-of-fi (KSD) problems can be rewritten as U-statistics with kernels h4 hMMD,, HHIIC and !gg
kKSD, respectively. The computational cost of tests based on these U-statistics grows quadratically kkpp
with the sample size. When working with very large sample sizes, as it is often the case in world uses of those tests, this quadratic cost can become very problematic, and faster alternative tests are better adapted to this 'big data" setting. Multiple linear-time kernel tests have been proposed in the three testing frameworks (see Section || for details). We construct computationally efficient variants of the aggregated kernel tests proposed by Fromont et al. (2013), Albert et al. (2022), Kim et al. (2022). and [cchrab et al. (202T (202)) for the three settings, with the aim of retaining the significant power advantages of the aggregation procedure observed for quadratic-time tests. To this end, we propose
to replace the quadratic-time U-statistics presented in Equations
(3 and (5) with second-order
incomplete U-statistics (Blom 1976, Janson 1984
Lee 1990
MMD k: (Xm,, En: DN) = |DN|
1
Σ
MMD (X,, Xy; Y, Yy).
(8)
(i.))DN
HSIC (ZN:
1
Σ
HSIC (Z,, Z, Z,+1N/2) (//1//)))))
(9)
|PLN/2s
(LN)E
KSD (ZN:
1
Σ
NKSD (Z,, Zz).
(10)
[DN]
(i.))Dyy
where for the two-sample problem we let N min(m (m, n), and where the design Dd is subset of 1 (the set of all 2-tuples drawn without replacement from
b)). Note that D [N/2]
C b 1/ C i
The design can be deterministic. For example, for the two-sample problem with equal even sample sizes m = n = N, the deterministic design D = (2a 1, 2a))= a = L...., N/22 corresponds to the MMD linear-time estimator proposed by Gretton et al. (2012a) Lemma 14). For fixed design size, the elements of the design can also be chosen at random without replacement, in which case the estimators Equations ( to TT) become random quantities given the data. For generality purposes, the results presented in this paper hold for both deterministic and random (without replacement) design choices while we focus on the deterministic design in our experiments. By fixing the design sizes in Equations to (10) to be, for example,
Dxl = | = cN
(1I)
for some small constant c E N \ {0}, we obtain incomplete U-statistics which can be computed in linear time. Note that by pairing the samples Z, == (X,, i = 1, ......NN NN for the MMD case and
Z, = (Z,, (1/+)N/2))) ). i = 1, ..... [N/2] for the HSIC case, we observe that all three incomplete U- statistics of second order have the same form, with only the kernel functions and the design differing. The motivation for defining the estimators in Equations
and (9) as incomplete U-statisties of order
2 (rather than of higher order) derives from the reasoning of Kim et al. (2022) Section 6) for permuted
complete U-statistics for the two-sample and independence problems (see Appendix
4 Quantile and variance bounds for incomplete U-statisties
In this section, we derive upper quantile and variance bounds for a second-order incomplete degenerate U -tsttistiic with a generic degenerate kernel h, for some design D C i defined
(DN: = D
Σ M(44, Zz).
(NJ)ED

---

We will use these results to bound the quantiles and variances of our three test statistics for our hypothesis tests in Section 5
The derived bounds are of independent interest.
In the following lemma, building on the results of Lee (990), we directly derive an upper bound on the variance of the incomplete U-statistic in terms of the sample size N and of the design size (D).
L
Lemma 1. The variance of the incomplete U Usstatistic can be upper bounded in terms of the quantities of = var((E))((2 (Z )')(?' 7z)
and o = var(h Z, Z)) with different bounds depending on the design choice. For deterministic (LHS) random (RHS) design D and sample size N, have
N D
1 var Far(U)= - N
var(U)
1
+
and
+ D 2
The proof of Lemma D is deferred to Appendix We emphasize the fact that this variance bound also holds for random design with replacement, as considered by [Blom| (1976) and Lee (1990). For random design, we observe that if [D] x 2 then the bound is of /N o2/N2 which is the variance bound of the complete U Utsttiiscic (Albert et al. 2022 Lemma 10), N S D
N2, the variance
bound is of/ /N + o D), and if [D] S N it 0 D
since of S oī/2 (Blom 1976 Equation 2.1).
Kim et al. 2022) develop exponential concentration bounds for permuted complete U-statistics,, and Clémençon et al. (013) study the uniform approximation of U'statistics by incomplete U-statistics. To the best our knowledge, no quantile bounds have yet been obtained for incomplete U-statistics in the literature. While permutations are well-suited for complete U-statistics (Kim et al.) 2022). using them with incomplete U-statistics results in having to compute new kernel values, which comes at an additional computational cost we would like to avoid. Restricting the set of permutations to those for which the kernel values have already been computed for the original incomplete U U-statistic corresponds exactly to using wild bootstrap (Schrab et al. 202T Appendix B). Hence, we consider the wild bootstrapped second-order incomplete U -ssatistti
U (ZN: = D
Σ (1))DD
4ech(Zi,
(12)
for i.i.d. Rademacher random variables Ei,..., EN with values in (-1, 1). for which we derive an exponential concentration bound (quantile bound). We note the in-depth work of @hWiillkowski et al. (2014) on the wild bootstrap procedure for kernel tests with applications to quadratic- MMD and HSIC tests. We now provide exponential tail bounds for wild bootstrapped incomplete U-statistics.
Lemma 2. There exists some constant C > Such that, for every 2 O, we have
Pe
U 2
ZN.
< 2 exp (-c-)) Aine
< 2exp
-C A
where Ane 1DI-2 E (i.j)DD h MZ, 22 and A = 1 Eiseey h(4, 2,)2.
Lemma is proved in Appendix While the second bound in Lemma 2 is less tight, has the benefit of not depending on the choice of design 'D but only on its size |D] which is usually fixed.
5 Efficient kernel tests using incomplete U-statistics
We now formally define the hypothesis tests obtained using the incomplete U-statisties with a wild bootstrap. This is done for tixed kernel bandwidths X E (0, o=) 4u E (0, do)dy, for the kernel
du 1 K,
dy
Ax v)
E
Vi A;
(x( v)
T.
37
V4
(13)
A;
14
for characteristic kernels (a, v) + K2(x y), (z. + L y) on x R for functions K,, L e L (RR) n L²RR integrating to 1. We unify the notation for the three testing frameworks. For the two- sample and goodness-of-fit problems, we work only with k and have d = d,. For the independence
'Our results are presented for bandwidth selection, but they hold in the more general setting of kernel selection, as considered by |Schrab et al. (2022). The goodness of fit results hold for wider range of kemels including the IMQ (inverse multiquadric) kernel Gorhhm and Mackey 2017). in Schrab et al. (2022)
5

---

problem, we work with the two kernels 4x and Eu. and for ease of notation we let d d= dg + dy and Ad = #4 for i = 1..... dyy We also simply write p Pxy and q Ps. @ Py. We let Ux x and
hy denote either MMD Ry and M or HSTCkx.f, and "..,, 1 or KSD p.A. and h KSD respectively.
We denote the design size of the incomplete U-statistics in Equations to TO by
L= |N|| |
For the three testing frameworks, we estimate the quantiles of the test statistics by simulating the null hypothesis using a wild bootstrap, as done in the case of complete U-statistics by Fromont et al.
(2022) and |Schrab et al. (2021) for the two-sample problem, and by [Schrab et al. (0022 for the
goodness-of-fit problem. This is done by considering the original test statistic Ux++1 = Ux together
with B1 wild bootstrapped incomplete U-statistics U/- A U computed as in Equation 12 and estimating the (1 (1-a))-qamnl) with a Monte Carlo approximation
B
Ti-a = inf 1 E 1- - a B
1
10
-0 (1-a))
U2
(14)
b=1
where Ux S < U are the sorted elements UZ...., U.,,U UBB+1.1 The test 4 is defined as rejecting the null if the original test statistic Ux is greater than the estimated (1 (1-o) a) quantile, that is,
(ZN) = (Ux) > -
The resulting test has time complexity L)) where L is the design size (1 < L N 1)).
We show in Proposition| | that the test A has well-calibrated asymptotic level for goodness-of-fi testing, and well-calibrated non-asymptotic level for two-sample and independence testing. The proof of the latter non-asymptotic guarantee is based on the exchangeability of U)...... 17.....,U U under the null hypothesis along with the result of Romano and Woll (2005) Lemma 1). A similar proof strategy can be found in Fromont et al. 2012 Proposition 2), Albert et al. (202] Proposition 1), and [Schrab al. (202T, Proposition I). The exchangeability of wild bootstrapped incomplete U-statisties for independence testing does not follow directly from the mentioned works. We show this through the HSIC and {he MMD, h hMMDD. the proof is deferred to Appendix F.1
interesting connection between h &,
The test A has level a E (0, i.. PHo(AN(ZN) = 1) S a. This holds non- asymptotically for the two-sample and independence cases, and asymptotically for goodness-of-Po
Proposition 1.
Having established the validity of the test A., we now study power guarantees for it in terms of the -nom of the difference in densities ||p up-91e -112- In Theorem we show for the three tests that, if ||p - 4/I2 exceeds some threshold, we can guarantee high test power. For the two-sample and independence problems, we derive uniform separation rates (Baraud 2002) over Sobolev balls
ST = {s L' (R)) LIRR) / |1511 [1(112) < R27)
(15)
with radius R > 0 and smoothness parameter > O, where / denotes the Fourier transform of f. The uniform separation rate over (R) is the smallest value of such that, for any alternative with ||p - 2ll2 > a g E (R), the probability of type II error of A can be controlled by 3 E (0, 1). Before presenting Theorem I we introduce further notation unified over the three testing
frameworks; we define the integral transtorm TAA as
(Txf)()) = f [(x))Cx(x,))) v) dy
(16)
for f (2RR), x Rd, where KA = k2 for the two-sample problem, K.A == 1x 6 for the independence problem, and KA AKSD for the goodness-of-fi problem. Note that, for the two- sample and independence testing frameworks, since K.2 is vranslatonninvarianl the integral transform corresponds to a convolution. However, this is not true for the goodness-ol setting as KSD is not iossslttio-invariann We are now in a position to present our main contribution in Theorem I we derive power guarantee conditions for our tests using incomplete U U-statistics, and uniform separation rates over Sobolev balls for the two-sample and independence settings.
'Level is aoy-tsymi for the goodness-of of-it fit case using a parametric bootstrap Schrab al. 2022 For the goodness-offfit setting, we also recall that the further assumptions in Equation need satisfied.
Wee stress that we only assume p- E (((R) and not p. 4 (J) as considered Li and Yuan 2019 Viewing g as perturbed version of p. we only require that the perturbation is smooth (f.e. lies in Sobolev ball).

---

Theorem 1. Suppose that the assumptions in Appendix 1.7 hold, and consider X E (0, 00)"
(i) For sample size N and design size I,, if there exists some C 0 such that
1p - 212 2 11 - 4) (D 2212 + -
N In(1/a)
B 02,7,
then PH, (A 0) (type II error), where 22 S 1/ 1/v ... Xa for MMD and HSIC.
(ii) Fix R 0 and s 0, and consider the bandwidths X; (N/L)a/(dstd)) for l,...y
i d. For
MMD and HSIC, the uniform separation rate of A overthe Sobolev ball (R) is (up to a constant)
(I//N) 2=/(4x)d)
The proof of Theorem Mrelies on the variance and quantile bounds presented in Lemmas [and]
and also uses results of Albert et al. (022) and Schrab et al. 22021 2022) on complete U-statistics. The details can be found in Appendix
The power condition in Theorem (i) corresponds to variance- srraance-bissaa decomposition; for large bandwidths the bias term (first term) dominates, while for small bandwidths the variance term (second term which also controls the quantile) dominates. While the power guarantees of Theorem hoold for any design (either deterministic or uniformly random without replacement) of fixed size I, the choice of design still influences the performance of the test in practice. The variance (but not its upper bound) depends on the choice of design; certain choices lead to minimum variance of the incomplete U-statistic (Lee) 1990 Section 4.3.2).
The minimax (i.e. optimal) rate over the Sobolev ball ( is N 22///2/ss for the two-sample
(Li and Yuan 2019, Theorem 5 (ii)) and independence (Albert et al. 2022 Theorem 4; |Berrett et al.] 2021 Corollary 5) problems. The rate for our incomplete U-statistic test with time complex-
ity (BBL)) has the same dependence in the exponent as the minimax rate; (L/N))2e/(4a)) -2s/(Ax+d)
d4++dd (N²/L) 20/(1++d) where L S N2 with L the design size and N the sample size.
N
L x 2 then the test runs in quadratic time and we recover exactly the minimax rate.
N & T. N2 then the rate still converges to O; there is trade-off between the cost (N²/L)2=>/4s++d incurred in the minimax rate and the computational efficiency O(B,L).
I N then there is no guarantee that the rate converges to O.
To summarize, the tests we propose have computational cost O(B, L) which can be specified by the user with the choice of the number of wild bootstraps B1, and of the design size L (as function of the sample size N). There is a trade-off between test power and computational cost. We provide theoretical rates in terms of L and N, working up to constant. The rate is minimax optimal in the case where L. grows quadratically with N. We quantify exactly how, as the computational cost decreases from quadratic to linear in the sample size, the rate deteriorates gradually from being minimax optimal to not being guaranteed to convergence to zero. In our experiments, we use a design size which grows linearly with the sample size in order to compare our tests against other linear-time tests in the literature. The assumption guaranteeing that the rate converges to 0 is not satisfied in this setting, however, it would be satisfied for any faster growth of the design size (e.g. L x N log log N).
6 Efficient aggregated kernel tests using incomplete U-statistics
We now introduce our aggregated tests that combine single tests with different bandwidths. Our aggregation scheme is similar to those of Fromont et al.] (2013), Allert et al. (202)) and Schrab et al. (221 ) and can yield a test which is adaptive to the unknown smoothness parameter of the Sobolev ball (RR), with relatively low price. Let A be a finite collection of bandwidths, (wx)xeλ be associated weights satisfying ΣxeA W. S 1, and uo be some correction term defined shortly in
Equation 17 Then, using the incomplete U-statistic U2, we define our aggregated test A as
(Z,)) = (Zx)) qi> for some À E A). The levels of the single tests are weighted and adjusted with a correction term
0. min wiinw5')) w5')==
Ba
UX [B((L-wos]]) >0) S {d)
Ua := supn,
u
max XEA
Ü
saj.
(17)
AEA
BB
7

---

where the wild bootstrapped incomplete U-statistics U)...., Uh computed as in Equation 12 are used to perform Monte Carlo approximation of the probability under the null, and where the supremum is estimated using B3 steps of bisection method. Proposition [ along with the reasoning of [Schrab et al. 2021 Proposition 8), ensures that A has non non-asymptotii level a for the two- sample and independence cases, and asymptotic level a for the goodness-of- case. We refer to the three aggregated tests constructed using incomplete U-statistics as MMDAggInc, HSICAggInc and KSDAggInc. The computational complexity of those tests is ( (B) + L)) which means, for example, that x N as in Equation (TT) the tests run efficiently in linear time the sample size.
We formally record error guarantees of A and derive uniform separation rates over Sobolev balls. Theorem 2. Suppose that the assumptions in Appendix A.2 hold, and consider collection A. (i) For sample size N and design size L, if there exists some C > 0 such that
N In (n(1((wwx)
|lp -911 2
min AEA
1 TT(P 2)122 + C
22
B
then PHi (A = 0) s 3 (type II error), where 02 1/1/11 ..- for MMD and HSIC.
(ii) Assume > N so that In(In(L/N)) is well-defined. Consider the collections of bandwidths and weights (independent of the parameters s and R of the Sobolev ball (R))
:lE A = (2 ....,, 25. E x0) EE (1 (I.....
2
L/N In(In(L/N))
1}
6
log2
Wx
22
For the two-sample and independence problems, the uniform separation rate of A over the Sobolev balls (S) R. > 0, > 0} is (up to a constant)
L/N
-2s/(1e+d)
[n([n(L/N))
The extension from Theorem T to Theorem has been proved for complete U-statistics in the
two-sample (Fromont et al. goodness-of-in (Schrab et al.
2013 Schrab et al. 202T independence (Albert et al. 2022) and
2022 testing frameworks. The proof of Theorem 2 follows with the same reasoning by simply replacing N with L/N as we work with incomplete U-statistics; this 'replacement' is theoretically justified by Theorem Theorem shows that the aggregated test A is adaptive over Sobolev balls (S)(R) R > 0, 0}: the test A does not depend on the unknown smoothness parameter (unlike AA" in Theorem I and achieves the minimax rate, up to iterated logarithmic factor, and up to the cost incurred for efficiency of the test (i.e. L/N instead of N).
7 Minimax optimal permuted quadratic-time aggregated independence test
Considering Theorem 2 with our incomplete U-statistic with full design D = - for which L > 2 we have proved that the quadratic-time two-sample and independence ag aggregated tests using a wild bootstrap achieve the rate (N/In(In(N)) (N) -2s/(4s+d) over the Sobolev balls {SA (R2) R > 0, > 0}. This is the minimax rate (Li and Yuan 2019 Albert et al. 2022),, up some iterated logarithmic term.
For the two-sample problem, Kim et al. (022) and Schrab et al. (202T) show that this optimality result also holds when using complete U U-statisties with permutations. Whether the equivalent statement for the independence test with permutations holds has not yet been addressed; the rate can be proved using theoretical (unknown) quantiles with a Gaussian kernel (Albert et al., 2022), but has yet been proved using permutations. Kim et al. 2022, Proposition 8.7) consider this problem, again using a Gaussian kernel, but they do not obtain the correct dependence on a (i.e. they obtain or 1/2
rather than (1(1a)),, hence they cannot recover the desired rate. As pointed out by Kim et al. 2022 Section 8): 'It remains an open question as to whether [the power guarantee] continues to hold when
a 1/2 is replaced by In(1/a)'. We now prove that we improve the a-dependence to In(1/ / 3/2 for any bounded kernel of the form of Equation (13), and that this allows us to obtain the desired rate over Sobolev balls (S R) R 0, > d/ d/4). The assumption d/4 //4 imposes a stronger smoothness restriction p- q E (R)) which is similarly also considered by Li and Yuan 2019)
8

---

Theorem 3. Consider the quadratic-timg independence test using the complete U-statistic HSIC estimator with a quantile estimated using permutations as done by Kim et al. (2022) Proposition 8.7), with kernels as in Equation (13 for bounded functions K; and I.j for
1, I,..., dn, ..... dy.
(i) Suppose that the assumptions in Appendix A hold. For fixed R > 0, 8 > d/4, and bandwidths X = NN-- (2((tt))) for i 11...,,d, ,d, the probability of type II error of the test is controlled by 3 when
1 In(1/a)3/2 11(p 9) - (p- + C 9112
N NB ... X for some constant C > 0.
The uniform separation rate over the Sobolev ball (R(R) is, up constant, N-2=/(1s+d)
(ii) Suppose that the assumptions in Appendix hhold The uniform separation rate over the Sobolev
balls (R) R > 0, > d/4) is (N/ In((n(N))) (2+(())))) up constant, with the collections
2 = :.... 2- (0, 00) EE {1, {1..... d
In(In(N)) 1}}
N
6
loga
n 22
The proof of Theorem S in Appendix R5 uses the exponential concentration bound of Kim et al. (0022 Theorem 6.3) for permuted complete U-statisties. Another possible approach to obtain the correct dependency on a is to employ the sample-splittig method proposed by Kim et al. (002 Section 8.3) in order to transform the independence problem into two-sample problem. While this indirect approach leads to a logarithmic factor in a, the practical power would be suboptimal due to an inefficient use of the data from sample splitting. Theorem 3 (i) shows that In(1/a))/2 dependence is achieved by the more practical permutation- based HSIC test. Theorem B (ii demonstrates that this
leads to a minimax optimal rate for the aggregated HSIC test, up the In In(in( (N)) cost for adaptivity.
8 Experiments
For the two-sample problem, we consider testing samples drawn from a uniform density on [0, 1jdt against samples drawn from a perturbed uniform density. For the independence problem, the joint density is a perturbed uniform density on [O, 1jd,+4,, the marginals are then simply uniform densities. Those perturbed uniform densities can be shown lie in Sobolev balls (Li and Yuan 2019 Albert et al. 2022), to which our tests are adaptive. For the goodness-of problem, we use a Gaussian- Bernoull Restricted Boltzmann Machine as first considered by [Liu al. (2016) in this testing framework. We use collections of 21 bandwidths for MMD and HSIC and of 25 bandwidth pairs for
HSIC; more details on the experiments (e.g. model and test parameters) are presented in Appendix C
We consider our incomplete aggregated tests MMDAggInc, HSICAggInc and KSDAggInc, with parameter R. E [l...., .N - 1} which fixes the deterministic design to consist of the first R sub- diagonals of the N x N matrix, i.e. D = {(i, +) : =........ .N- - for r I,..., R} with size [D] RN R(R 1)/2. We run our incomplete tests with R E [1, 100, 200} and also the complete test using the full design D = i.y We compare their performances with current linear-time state-of- the-art tests: ME, SCF, FSIC and FSSD (Jitrittum al. 2016 2017a b which evaluate the witness functions at finite set of locations chosen to maximize the power, Cauchy RFF (random Fourier feature) and L1 IMQ (Huggins and Mackey 2018) which are random feature Stein discrepancies, LSD (Grthhwohl et al. 2020) which uses neural network to learn the Stein discrepancy, and OST PSI (Kübler et al. 2020 which performs kernel selection using post selection inference.
Similar trends are observed across all our experiments in Figure D for the three testing frameworks, when varying the sample size, the dimension, and the difficulty of the problem (scale of perturbations or noise level). The linear-time tests AggIne R = 200 almost match the power obtained by the quadratic-time tests AggCom in all settings (except in Figure D (i) where the difference is larger) while being computationally much more efficient as can be seen in Figure I (d. h, I). The incomplete tests with R 100 have power only slightly below the ones using R 200, and run roughly twice as fast (Figure (d, h, D)). In all experiments, those three tests (AggIne R = 100, 200 and AggCom) have significantly higher power than the linear-time tests which optimize test locations (ME, SCF, FSIC and FSSD); in the two-sample case the aggregated tests run faster for small sample size but slower for large sample size, the independence case the aggregated tests run much faster, and the goodness-of fit case FSSD runs faster. While both types of tests are linear, we note that the runtimes

---

Thme (osconte))
Poweer
Thwner
0.5
0.0
0.0
0.0
200
400
400
800
Samsle
Dimension
scoling paramestrr
Sample
(4)
(b)
(c)
(4)
ME
SCP
OST PSI
7
MMIDAggin A
MMDDgggin A 100
MMDAgglar it 200
MMMMMggCom
Tire (socondl)
0.5
Power
Pinezz
0.5-
0.5
0.5
0.0
0.0
0.0
0.0
200
400
400
800
Sample size
Dimnecio of
Inverso scaling, paraumeter
Sample size
(c)
(f)
(g)
(h)
FSTC
HSIAAghhe R
HSICAgghh R= 100
HSICAggee R= 200
HSSCCAggCom
1.0
0.5-
05
0.04
0.0
0.
200
000
0..0
800
1500
20
40
60
50
0:00 0.01
0.02 000
0.01
200
0.0
800
1000
Sample stae.3 N
Dimersiim
Noiso stazdaard devistion
Sumppe size N
(5)
(
(k)
(1)
1880
-+-
180
L1 IMQ ..... Caucly RFF -
KSDAggin it
K:DAAgg it 100
KSDAggfor i 200 - K50A4g5oom
Figure I: Two-sample (a-d) and independence (e-h) experiments using perturbed uniform densities. ofoddeess-of-ftt (i-l) experiment using Gaussian- Bernoulli Restricted Boltzmann Machine. The power results are averaged over 100 repetitions and the runtimes over 20 repetitions.
-eussian-Beroollli
of the tests of Ditkrittum et al. 6 2017a b) increase slower with the sample size than those of our aggregated tests with = 100, 200, but a fixed computational cost is incurred for their optimization step, even for small sample sizes. In the goodness-of of fit framework, LI IMQ performs similarly to FSSD which is line with the results presented by Huggins and Mackey 2018 Figure 4d) who consider the same experiment. All other goodness-of tests (except KSDAggInc R = 1) achieve much higher test power. Cauchy RFF and KSDAggIne R = 200 obtain similar power almost all the experiments. While KSDAggIne R 200 runs much faster in the experiments presented it seems that the KSDAggInc runtimes increase more steeply with the sample size than the Cauchy RFF and L1 IMQ runtimes (see Appendix D.3 for details). LSD matches the power of KSDAggInc R = 100 when varying the noise level in Figure I (k) (KSDAggInc R = 200 has higher power), and when varying the hidden dimension in Figure (i) where d, 100. When varying the sample size in Figure
M() (i), both KSDAggine tests with π 100, 200 achieve much higher power than LSD. Unsurprisingly, AggIne R = which runs much faster than all the aforementioned tests, has low power in every experiment. For the two-sample problem. it obtains slightly higher power than OST PSI which runs even faster. We include more experiments Appendix D we present experiments on the MNIST dataset (same trends are observed), we use different collection of bandwidths, we verify that all tests have well-calibrated levels, and illustrate the benefits of the aggregation procedure.
Acknowledgements
Antonin Schrab acknowledges support from the U.K. Research and Innovation (EP/S021566/1 Immn Kim acknowledges support from the Yonsei University Research Fund of 2021-22-0332, and from the Basic Science Research Program through the National Research Foundation of Korea funded by the Ministry of Education 2022RIA4A 1033384). 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/R013616/1) 1)), and &
by the French National Agency for Research (ANR-18 Arthur Gretton acknowledges support from the Gatsby Charitable Foundation.
The runtimes in Figure I (d. h. can also vary due the different implementations of the respective authors.
10

---

References
Albert, M., Laurent, B., Marrel, A., and Meynaoui, A. (2022). Adaptive test independence based on HSIC measures. The Annals of Statistics, 50(2):858-879,
Aronszajn, N. (1950). Theory reproducing kernels. Transactions of the American Mathematical Society, 68(3):337-45) 4044
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, Y. (2002). Non-asymptotic minimax rates of testing in signal detection. Bernoulli, 1(8(5)5577- 606).
Berrett, T. B., Kontoyiannis, I., and Samworth, R. J. (2021). Optimal rates for independence testing via u-statistic permutation tests. The Annals Statistics, 49(5):2457-2400.
Blom, G. (1976). Some properties of incomplete U-statistics. Biometrika, 63(3):573-580.
Carmeli, C., De Vito, E., Toigo, A., and Umanitá, V. (2010). Vector valued reproducing kernel Hilbert spaces and universality. Analysis and Applications. 8001):1961..
Chebyshev, P. L. (1899). Ocuvres. Commissionaires de l'Académie Impériale des Sciences, 1.
Cherfaoui, F., Kadri, H., Anthoine, S., and Ralaivola, L. (2022). A discrete RKHS standpoint for Nyström MMD. HAL preprint hal-03651849.
Chwialkowski, K., Sejdinovie, 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, A. (2016). kernel test of goodness of fit. In International Conference Machine Learning, pages 2606-2615 PMLR.
Chwialkowski, K. P., Ramdas, A., Sejdinovic, D., and Gretton, A. (2015). Fast two-sample test- ing with analytic representations of probability measures. In Advances in Neural Information Processing Systems, volume 28, pages 1981-1989.
Clémençon, S., Robbiano, S., and Tressou, J. (2013). Maximal deviations of incomplete U-statistics with applications to empirical risk sampling. Proceedings of the 2013 SIAM International Conference Data Mining, pages 19-27. SIAM.
de Peña, V. and Giné, E. (1999). Decoupling: From Dependence to Independence. Springer Science & Business Media.
Dinh, L., Sohl-Dickstein, J., and Bengio, (2017). Density estimation using real NVP. In International Conference Learning Representations.
Duembgen, L. (1998). Symmetrization and decoupling of combinatorial random elements. Statistics & probability letters, 39(4)3355-361
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.
Fithian, W. Sun, D., and Taylor, J. (2014). Optimal inference after model selection. arXiv preprint arXiv: 1410.2597.
Freidling, T., Poignard, B., Climente-Gonzzlez,, H., and Yamada, M. (2021). Post-selection inference with HSIC-Lasso. In International Conference on Machine Learning, pages 3439-3448. PMIR.
Reynaud-Bouret, Fromont, M., Laurent, B., Lerasle, M., and Reynaud- Bouret, P. (2012). Kernels based tests with
non-asymptotic bootstrap approaches for two-sample problems. In Conference on Learning Theory, PMLR.
11

---

Fromont, M., Laurent, B., and Reynaud- Beyynuud-Boure, P. (2013). The two-sample problem for Poisson processes: Adaptive tests with a nonasymptotic wild bootstrap approach. The Annals of Statistics, 41(3):1431-1461
Fukumizu, K., Gretton, A., Sun, X., and Schölkopf, B. (2008). Kernel measures of conditional dependence. In Advances in Neural Information Processing Systems, volume 1, pages 489-496.
Gorham, J. and Mackey, L. (2017). Measuring sample quality with kernels. In International Conference on Machine Learning, pages 1292-13000 1201. PMLR.
Grathwohl, W., Wang, K.-C., Jacobsen, J.-H., Duvenaud, D., and Zemel, R. (2020). Learning the Stein discrepancy for training and evaluating energy-base models without sampling. In International Conference on Machine Learning, pages 3732-3747. PMLR.
Gretton, A. (2015). A simpler condition for consistency of a kernel independence test. arXiv preprint arXiv:1501.06100
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., Fukumizu, K., Harchaoui, Z., and Sriperumbudur, two-sample test. Advances in Neural Information Processing Systems, 22.
(2009). A fast, consistent kernel
Gretton, A., Fukumizu, K., Teo, C. H., Song, L., Schölkopf, B., and Smola, A. J. (2008). A kernel statistical test of independence. In Advances in Neural Information Processing Systems, volume 1, pages 585-592.
Gretton, A., Herbrich, R., Smola, A., Bousquet, O., and Schölkopf, B. (2005). Kernel methods for measuring independence. Journal of Machine Learning Research, 6:2075-2129 2129
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 I, pages 1205-1213.
Ho, H.-C. and Shieh, G. S. (2006). Two-stage U-statistics for hypothesis testing. Scandinavian journal of statistics, 33(4):861-87) 8773
Hoeffding, W. (1992). A class of statistics 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.
Janson, S. (1984). The asymptotic distributions of incomplete U-statistics. Zeitschrift für Wahrschein- lichkeitstheorie und Verwandte Gebiete, 6654)-495-505
Jitkrittum, W., Szabó, Z., Chwialkowski, K. P., and Gretton, A. (2016). Interpretable distribution features with maximum testing power. In Advances in Neural Information Processing Systems, volume 29, pages 181-189.
Jitkrittum, W., Szabó, Z., and Gretton, A. (2017a). An adaptive test of independence with analytic kernel embeddings. In International Conference Machine Learning (ICML), pages 1742-1751.
Jitkrittum, W. Xu, W., Szabó, Z., Fukumizu, K., and Gretton, A. (2017b). A linear-time kernel goodness-of-fit test. In Advances in Neural Information Processing Systems, pages 262-271.
Key, O., Fernandez, T., Gretton, A., and Briol, F--X. (2021). Composite goodness-of-fit tests with kernels. arXiv preprint 1rXiv:2111.10275.
Kim, I., Balakrishnan, S., and Wasserman, L. (2022). Minimax optimality of permutation tests. The Annals of Statistics, 50(1):22--
Kingma, and Ba, J. (2014). Adam: A method for stochastic optimization, arXiv preprint 1rX.v:1412.6980
12

---

Kingma, D. P. and Dhariwal, P. (2018). Glow: Generative flow with invertible 1xl convolutions. In Advances in Neural Information Processing Systems. pages 10236-10245.
Kübler, J. M., Jitkrittum, W., Schölkopf, B., and Muandet, K. (2020). Learning kemnel tests without data splitting. In Advances in Neural Information Processing Systems 33, pages 6245-6255 Curran Associates, Inc.
Kübler, M., Jitkrittum, W., Schölkopf, B., and Muandet, K. (2022). witness two-sample test. In International Conference on Artificial Intelligence and Statistics, pages 1403-1419, PMLR.
LeCun, Y., Cortes, C., and Burges, C. (2010). MNIST handwritten digit database. AT&T Labs.
Lee, J. (1990). U-statistics: Theory and Practice. Citeseer.
Lee, J. D., Sun, D. L.,, Sun, Y., and Taylor, J. E. (2016). Exact post-selection inference, with application to the Lasso. The Annals of Statistics, 44(3):907-9211
Leucht, A. and Neumann, M. H. (2013). Dependent wild bootstrap for degenerate U- 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 arXiv:/909) 190.00332.
Lim, 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, Q., Lee, J., and Jordan, M. (2016). kernelized Stein discrepancy for goodness-of tests. In International Conference on Machine Learning, pages 276-284. PMLR.
Massart, (1990). The tight constant in the Sroretzky-Kiefere wieffo/ww inequality. The Annals of Probability, 18(3):1269-1 1283.
Müller, A. (1997). Integral probability metries and their generating classes of functions. Advances in Applied Probability, 1:429 443.
Rahimi, A. and Recht, (2007). Random features for large-scale kernel machines. Advances in Neural Information Processing Systems (NIPS), pages 1177-1184.
Ramachandran, P., Zoph, B., and Le, Q. V. (2017). Searching for activation functions. arXiv preprint arXiv:1710.05941.
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., Guedj, B., and Gretton, A. (2022). KSD Aggregated goodness-of-ft test. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022.
Schrab, A., Kim, L., Albert, M., Laurent, B., Guedj, B., and Gretton, A. (2021). MMD Aggregated two-sample test. arXiv preprint 10.
Shao. X. (2010). The dependent wild bootstrap. Journal of the American Statistical Association, (01(489):218-233
Song. L., Smola, A. J., Gretton, A., Bedo, J., and Borgwardt, K. M. (2012). Feature selection via dependence maximization. Journal of Machine Learning Research, 13:1393-1434.
Sriperumbudur, B. K., Fukumizu, K., and Lanckriet, (2011). Universality, characteristic kernels and RKHS embedding of measures. Journal of Machine Learning Research, 12(7).
13

---

Srivastava, N., Hinton, G., Krizhevsky, A., Sutskever, I., and Salakhutdinov, R. (2014), Dropout: simple way prevent neural networks from overfitting. Journal of Machine Learning Research, ((()):129-1198.
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.
Yamada, M., Umezu, Y., Fukumizu, K., and Takeuchi, I. (2018). Post selection inference with kernels. In International Conference on Artificial Intelligence and Statistics, pages 152-160. PMLR.
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.
7aremba, W., Gretton, A., and Blaschko, M. (2013). B-test: A non- po--paammtric, low variance kernel two-sample test. Advances neural information processing systems, 26.
Zhang, Q., Filippi, S., Gretton, A., and Sejdinovic, D. (2018). Large-scale kernel methods for independence testing, Statistics and Computing, 28(1):113-13)
Zhao, J. and Meng, D. (2015). FastMMD: Ensemble of circular discrepancy for efficient two-sample test, Neural computation, 27(6); 334--1372.
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 framed bullet points at the
end of Section 5 (limitation for the case .N)
(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 main text for Theorem and appendices for all other proofs.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either the supplemental material or as a URL)? [Yes] URL in Section I https://githut com/ http///toonnnncaaaaa//aoa watpi//shhccaaggannaaaeeeeeeeeee
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Appendix
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes] For the time plots in Figure we report the error bars which represent the standard deviation (they are really small and cannot always been seen). For the power plots in Figure ! since the test outputs are binary (0 or 1), there is no need to include error bars since these 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, cloud provider)? [Yes] See Appendix C
4. If you using existing assets (e.g., code, data, models) curating/releasing
assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Appendix C
(b) Did you mention the license of the assets? [Yes] See Appendix
(c) Did you include any new assets either the supplemental material URL? [Yes] bettps///gttae
URL in Section
[
com/ www.aantntnnnnannaaaaaaaaaaaaa pat.rrrraaaagggin-paaperrrr
(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 conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "xcw-bmiX8fN", "reviewer": "Reviewer_aMao", "summary": "Post rebuttal: after the authors response and reading the other reviews, I updated my score to 6 (from initially 4) see also my comment below.\n\n\n-------- original review ------\n\nThe paper considers a general framework for kernel-based hypothesis testing, where the test statistic is given by a U-statistic. The framework covers Two-sample testing, Independence Testing, and Goodness-of-fit testing.\nThe paper shows that using an incomplete U-statistic estimate allows to trade-off computational resources for statistical significance, which follows from general theory of incomplete U-statistics.\nFurthermore, it adopts recent advances to aggregate such tests over multiple kernels and provides insights into the minimax separation rates over Sobolev balls.\nLastly, the paper provides simple experiments on toy data, illustrating their findings and comparing to some other approaches to tackle the respective testing problems.", "questions": "- Are the tests really 'linear-time'? (see comment in limitations)\n- l. 152-156: why do you discuss the random design when in the end you are using the deterministic one?\n- How should one choose the number of bandwidths ($l$) in practice?\n\nMinor Comments:\n- l. 147: define what a degenerate kernel is.\n- Type in Equation before line 500: should be $x_{i_1}$,...", "limitations": "The work is theoretical and no direct negative societal impact is to be expected.\n\nThe theoretical results discuss minimax optimal rates, which leaves the impression that nothing can go wrong. But in practice there remain some parameters that users have to choose, for example how many bandwidths to include in the aggregation. For the experiments the authors only use 4 bandwidths, which in my opinion hardly suffices to illustrate the benefits of this aggregation. On the other hand, it is not clear what happens if too many bandwidths are included.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*:\n- the work applies to three different testing scenarios and illustrates their close connections.\n- Although the use of incomplete U-statistics is not completely new for kernel-based tests (see e.g. Yamada et al ICLR 2019) the provided non-asymptotic tests are relevant and nicely illustrate the trade-off between computational resources and statistical significance.\n- The tests provably control type-I error also at finite data, while some of the existing methods, like OST, do not.\n- The theoretical insights are concisely stated and the prior results properly attributed. Arguably, though the provided results are rather simple consequences and combinations of prior results.\n- The provided Code is clean and it is easy to reproduce the experiments. The code was submitted after the deadline, which might be a violation of the rules!\n\n*Weaknesses*:\n- Overall, I think the practical relevance is quite limited:\na) The experiments are limited to very simple toy data sets. While they illustrate the effect of using incomplete U-statistics, the effect of the aggregation procedure is not illustrated at all.\nb) Only very few (4!) kernels are aggregated over. IMO this does not suffice to illustrate the benefits of the aggregation procedure.\nc) Overall there should be more guidance for practitioners. How many kernels should one choose in practice?\n- The authors consider ‘linear-time’ tests (eq. 10), which I think is misleading. By their theoretical results Theorem 1 ii) and considering $L=c N$, the uniform separation rate is not guaranteed to converge to zero. I thus also think that the gray box on page 7 is actually wrong. IMO it should be changed to the following: let $L=N^{1+a}$. Then for $a=1$ one recovers the minimax rate. For $a> 0$ the rate still converges to zero, but slower. For $a\\leq 0$ there is no guarantee. **Overall the provided theory does not provide guarantees for linear-time tests**.\n- For the two-sample problem, the provided tests cannot handle imbalanced samples in a meaningful way. The provided approach simply truncates data ($N=min(m,n)$ in line 131).\n- I think the presentation of the initial statistics (1) and (3) is suboptimal. For unexperienced readers it seems that these statistics scale like N^4. So I think it would be better to directly introduce the statistics such that they correspond to the complete U-statistics of (7) and (8). Alternatively, it should be explained why this statistics scale quadratically (no need to tell me in the rebuttal).\n- The claim that the “aggregation procedure is known to lead to state-of-the-art powerful tests” (l. 26f) seems a bit biased.\n- Prior work (Sutherland (ICLR 2017), Liu (ICML 2020)) showed that continuously optimizing a kernel is quite advantageous and harnesses the beenfits of gradient-based optimization. The present work only allows to combine finitely many (prespecified) kernels. \n- The aggregation scheme is a direct adaption from prior work (the authors are transparent about this).", "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": "jxbEgKOM46u", "reviewer": "Reviewer_eJnC", "summary": "POST REBUTTAL:\n\nScore increased to 7.\n\n------ -------\nIn this work, the authors propose faster than quadratic tests for the two-sample, independence, and goodness-of-fit problems, using the Maximum Mean Discrepancy (MMD), Hilbert Schmidt Independence Criterion (HSIC), and\nKernel Stein Discrepancy (KSD), respectively. They are based on incomplete U statistics that can interpolate between linear time, and quadratic time costs (the latter cost is incurred by typical tests which are complete U-statistics). \n", "questions": "\n1. The work in Huggins and Mackey (e.g., the L1 IMQ and Cauchy RFF random feature Stein discrepancies) were all linear and not quadratic time as the authors mention in l 53. Given the focus on linear time tests in this work, I  believe that these tests should be treated as a useful baseline for goodness-of-fit comparison experiments. In particular, Huggins and Mackey's experiments showed that their tests typically outperformed the FSSD test (which is one of the key linear time baselines in the current work).\n\n2. In the separation rate, the dependence on alpha is logarithmic but that on beta is polynomial (1/x)--is the latter unavoidable? I can see from the proof that it is because of the nature of concentration inequalities used in the two contexts (namely Rademacher chaos concentration, and Markov's inequality)--but are the arguments known to be tight? Does there exist a setting where such dependence is necessarily needed?\n\n3. Is the tradeoff in Theorem 1 tight? I can see it's tight when L = N^2 but is it tight for smaller values of L? Some discussion on this would be very useful.\n\n\n4. Do you not need any requirements on p for Proposition 1? And does only the difference p-q need to lie in the Sobolev ball for Thm 1(ii)?\n\n\n5. Does the choice of design D not matter? Does it have to be an iid subsample? Can it be adaptive? (My guess is all the arguments go through relying on iidness of data points in D).\n\nMinor comment:\n- It would be easier to process the results if the assumptions on densities are stated in an assumption environment, and then referenced in the theorem results. ", "limitations": "See questions.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors provide a tradeoff between the computational cost used and the power achieved in Theorem 1---while achieving the minimax rates over Sobolev balls when using the quadratic runtime variant. The authors then use this result to also achieve appropriate power results for kernel selection (up to logarithmic inflation in the number of kernels). Notably, this result is adaptive and does not require the knowledge of the smoothness parameter of the difference between the null and the alternative density.\n\nThe authors also provide several experiments which demonstrate the advantages of the proposed methods.  \n\nThe writing of the paper is pretty clear and worth appreciating!", "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": "Xu8TZgu9auu", "reviewer": "Reviewer_STxK", "summary": "This paper studies a family of nonparametric two-sample, independence, and goodness-of-fit tests based on incomplete kernel-based U-statistics, for which it proves validity (Proposition 1) as well as guarantees on power, assuming the true densities lie in a Sobolev space and are sufficiently well separated in $L_2$ distance. The power guarantees are initially proven for a statistic depending on the true smoothness of the Sobolev space (Theorem 1), but Theorem 2 extends this to an estimate that is adaptive to unknown smoothness. Theorem 3 shows that, compared to existing results for independence testing, a tighter bound, with better dependence on the type-1 error probability, can be obtained. Finally, some experiments demonstrate how the performance of the proposed estimators varies with hyperparameters and how this compares with some other linear-time nonparametric tests.", "questions": "1. Lemma 1: The variance bound for random design includes a $\\frac{1}{|\\cal{D}_r|} + \\frac{1}{N^2}$ term. Since $|\\cal{D}_r| \\leq N^2$, isn’t the second term redundant (i.e., can’t it be absorbed into the constant $C$)?\n3. Line 144-146, “The motivation for defining the estimators… of order 2 (rather than of higher order) derives from the reasoning of Kim et al. (2022, Section 6)...”: I didn’t quite understand this sentence. I skimmed Section 6 of Kim et al. (2022), and, while they do indeed study U-statistics of order 2, the motivation for order 2 (rather than of higher order) wasn’t obvious to me. Could the authors clarify?\n2. I found the motivation for Theorem 3 (lines 241-256) a bit hard to understand. Am I understanding correctly that the improved (logarithmic rather than polynomial) dependence on $1/\\alpha$ has been previously shown for two-sample testing but not for independence testing. Later on (Lines 262-263), the paper says “As discussed by Kim et al. (2022, Section 8.3), their proposed sample-splitting method can also be used to obtain the correct dependency on $\\alpha$.” So what exactly is the new contribution of Theorem 3?\n4. Figure 1: The first row of plots includes a green curve that isn’t included in the legend. What is this? Also, the paper discusses results for some methods (e.g., OST PSI) for which I didn’t see any results in Figure 1. Where are these results reported?\n5. Could the authors elaborate on advantages of the proposed tests over previous tests that have been shown to be minimax optimal (e.g., the Gaussian-kernel-based tests of Li and Yuan (2019))?", "limitations": "The paper would definitely benefit from further discussion of the limitations of its present results and suggestions for future work. However, given space limitations, I don't think further discussion of this is strictly necessary for acceptance.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: This paper provides much more compelling theoretical results (minimax optimality, especially for an adaptive estimator (Theorem 2)) than most related work on two-sample testing, which usually only shows consistency. It’s also nice that a unified but rigorous discussion is given for the closely related problems of two-sample, independence, and goodness-of-fit testing.\n\nWeaknesses: The paper has a lot of notation that is very similar or overloaded, but not explained or disambiguated near where it is used. For example, $L$ is defined just before Line 177 as the design size of the incomplete U-statistic, but is also used as a kernel (in Eq. (12)) and for $L^p$ spaces (in Eq. (17)). This made it a bit hard for me to follow the paper’s notation. I think it would help if the paper was a bit more explicit (even redundant) with explaining its notation near where it is used (e.g., reiterating “where $L$ is the design size” after Theorem 1). The paper also is not particularly clear about its distinctions from prior work (see questions below, although I was able to piece this together from various parts of the paper and by reading some of the references).", "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