Universal Hypothesis Testing with Kernels:
Asymptotically Optimal Tests for Goodness of Fit

arXiv:1802.07581v1 [stat.ML] 21 Feb 2018

Shengyu Zhu 1 Biao Chen 2 Pengfei Yang 3 Zhitang Chen 1

Abstract
We characterize the asymptotic performance of
nonparametric goodness of fit testing, otherwise
known as the universal hypothesis testing that
dates back to Hoeffding (1965). The exponential
decay rate of the type-II error probability is used
as the asymptotic performance metric, hence an
optimal test achieves the maximum decay rate
subject to a constant level constraint on the typeI error probability. We show that two classes
of Maximum Mean Discrepancy (MMD) based
tests attain this optimality on Rd , while a Kernel Stein Discrepancy (KSD) based test achieves
a weaker one under this criterion. In the finite
sample regime, these tests have similar statistical
performance in our experiments, while the KSD
based test is more computationally efficient. Key
to our approach are Sanov’s theorem from large
deviation theory and recent results on the weak
convergence properties of the MMD and KSD.

1. Introduction
Goodness of fit tests play an important role in machine learning and statistical analysis. Given a model
distribution P and sample {xi }ni=1 := xn originating from an unknown distribution Q, the goal is to
decide whether to accept the null hypothesis that Q
matches P , or the alternative hypothesis that Q and
P are different. Traditional (parametric) approaches
may require space partitioning or closed-form integrals
(Beirlant et al., 1994; Györfi & Van Der Meulen, 1991;
Baringhaus & Henze, 1988; Bowman & Foster, 1993).
They become computationally intractable in machine
learning applications that involve high dimensional data
and complicated models, such as large graphical models and deep generative models (Koller & Friedman, 2009;
Salakhutdinov, 2015; Sutherland et al., 2017).
1

Huawei Noah’s Ark Lab, Hong Kong, China 2 Syracuse
University, Syracuse, NY, USA 3 Cubist Systematic Strategies, New York, NY, USA. Correspondence to: Shengyu Zhu
<szhu05@syr.edu>. Part of the work was done when the first
and third authors were students at Syracuse University.

Recently, several efficient tests have been proposed based
on Reproducing Kernel Hilbert Space (RKHS) embedding.
One is to conduct a Maximum Mean Discrepancy (MMD)
based two-sample test by drawing samples from the model
distribution P (Lloyd & Ghahramani, 2015). A difficulty
with this approach is to determine the number of samples
drawn from P relative to n, the sample number of the
test sequence. Other tests are based on classes of Stein
transformed RHKS functions (Chwialkowski et al., 2016;
Liu et al., 2016; Gorham & Mackey, 2017; Oates et al.,
2017; Gorham & Mackey, 2015), where the test statistic
is the norm of the smoothness-constrained function with
largest expectation under Q, referred to as the Kernel Stein
Discrepancy (KSD). The KSD has zero expectation under P and does not require computing integrals or drawing
samples. Additionally, constructing explicit features of distributions achieves a linear-time goodness of fit test that is
also more interpretable (Jitkrittum et al., 2017).
Despite being efficient and well-behaved in practice, fairly
little is known about the statistical optimality of these kernel embedding based tests in a nonparametric setting. Current statistical characterization is limited to consistency,
that is, the test type-II error probability decays to zero
in the large sample limit under a pre-defined significance
level, an upper bound on the type-I error probability. This
is established using the convergence of the test statistic to
the population statistic (the MMD or KSD between P and
Q) under suitable assumptions. Consistency, while being
a desired property of statistical tests, does not serve as a
meaningful criterion for claiming optimality—a consistent
test need not be optimal. An alternative and more insightful approach, one adopted in the current paper, is to study
the decay rate of the type-II error probability. However,
the current literature lacks such a characterization as the
asymptotic distribution of the test statistics either has no
closed form (Chwialkowski et al., 2016) or is hard to analyze (Liu et al., 2016; Jitkrittum et al., 2017). In light of
the important role and good performance of these kernel
tests, the present work seeks an exact characterization on
the decay rate of the type-II error probability and further a
practically meaningful optimality criterion.
Indeed, there is a long-standing open problem related to op-

Asymptotically Optimal Tests for Goodness of Fit

timal goodness of fit tests in information theory and statistics (Csiszár & Shields, 2004; Cover & Thomas, 2006),
dating back to Hoeffding’s test (Hoeffding, 1965). Given a
known distribution P , the hypothesis testing H0 : xn ∼ P
and H1 : xn ∼ Q can be extremely hard when Q is arbitrary but unknown, as opposed to the simple case when
Q is known. With independent sample and a known Q,
Stein’s lemma (cf. Lemma 1) states that the type-II error probability vanishes at most exponentially fast with
the exponential decay rate, referred to as the error exponent, being the Kullback-Leibler divergence (KLD) between P and Q. This motivates the so-called universal
hypothesis testing problem: does there exist a nonparametric goodness of fit test that achieves the same optimal
error exponent as the simple hypothesis testing problem
where Q is known? Over the years, universally optimal
tests only exist when the sample space is finite (Hoeffding,
1965; Unnikrishnan et al., 2011). For continuous sample
space like R, attempts have been largely fruitless with the
only exception of the works by Zeitouni & Gutman (1991);
Yang & Chen (2017). The results were obtained at the cost
of a weaker optimality and the proposed test is rather complicated due to the use of Lévy-Prokhorov metric.
In this work, we first show a simple kernel test, comparing the MMD between the reference distribution and the
sample empirical distribution with a proper threshold, as
an optimal approach to universal hypothesis testing on Polish, locally compact Hausdorff space, e.g., Rd . Taking into
account the computation difficulty of non-Gaussian distributions, we further cast the original problem into a twosample problem as in (Lloyd & Ghahramani, 2015). We
show that the same optimality can be attained provided that
ω(n) independent samples are drawn from P . In particular, when distributions are defined on Rd , the biased and
unbiased two-sample tests in (Gretton et al., 2012a) with
Gaussian kernels can be used to achieve the asymptotic optimality, regardless of the kernel parameters. We then discuss other distance measures for constructing goodness of
fit tests. The level constraint on the type-I error probability
then becomes difficult to meet for all possible sample sizes.
As such, we relax the constraint to an asymptotic one and
further show that a KSD based test also achieves the optimal type-II error exponent. Key to our approach is a useful
large deviation tool, Sanov’s theorem, together with recent
results on the weak convergence properties of the MMD
(Sriperumbudur, 2016; Simon-Gabriel & Schölkopf, 2016)
and the KSD (Gorham & Mackey, 2017).
We remark that the techniques of utilizing Sanov’s theorem
and the weak convergence property may be of independent
interest, and may be used to evaluate other kernel tests.
Other related work. Minimizing the type-II error probability (or equivalently, maximizing test power) subject to a

given level has been studied for kernel choice in goodness
of fit testing (Jitkrittum et al., 2017) and two-sample testing (Gretton et al., 2012b; Sutherland et al., 2017), based
on the asymptotic distribution of the test statistics. The
characterization of type-II error probability depends on the
sample size as well as the specific kernel for use. Instead,
we directly investigate the acceptance region under the alternative hypothesis assisted by Sanov’s theorem. Our tests
attain the optimal error exponent and are independent of
specific kernels as long as they meet the assumptions.
Another criterion, asymptotic Bahadur efficiency, is used
for comparing test performance in (Jitkrittum et al., 2017).
The proposed linear-time test is shown to always have
greater relative efficiency than the linear-time test in
(Liu et al., 2016) under a mean-shift alternative, regardless
of the choice of parameters for that test. It is not clear
whether this claim holds for general alternatives and further if the proposed test is optimal under this criterion.
Paper outline. We begin with a brief review of the MMD
and a formal statement of the universal hypothesis testing
problem in Section 2. Section 3 presents two classes of kernel tests to universal hypothesis testing and discusses their
implications to goodness of fit testing. Section 4 discusses
the KSD and other distance measures in constructing goodness of fit tests. All the necessary proofs are provided in
Section 5. We perform synthetic experiments in Section 6
to validate our findings and conclude the paper in Section 7.

2. Preliminary and Problem Statement
We briefly review kernel mean embedding and the MMD.
We then introduce goodness of fit testing, followed by a
formal statement of the universal hypothesis testing.
2.1. Maximum Mean Discrepancy
Let Hk be a Reproducing Kernel Hilbert Space (RKHS) defined on a topological space X with reproducing kernel k.
Let P be the set of all Borel probability measures defined
on X . The mean embedding of P ∈ P in Hk is a unique element µk (P ) ∈ Hk such that Ey∼P f (y) = hf, µk (P )iHk
for all f ∈ Hk (Berlinet & Thomas-Agnan, 2011). We assume that k is bounded continuous, hence the existence of
µk (P ) is guaranteed by the Riesz representation theorem.
The MMD between two probability measures P and Q is
defined as the RHKS-distance between their mean embeddings. An expression of the MMD is
MMD[Hk , P, Q]
= (Eyy′ k(y, y ′ ) + Exx′ k(x, x′ ) − 2Eyx k(y, x))
′

′

1/2

,

where y, y i.i.d. ∼ P and x, x i.i.d. ∼ Q. In the sequel,
we will write MMD[Hk , P, Q] := dk (P, Q). We also refer
the reader to a recent overview by Muandet et al. (2017).

Asymptotically Optimal Tests for Goodness of Fit

If the mean embedding µk is an injective map, then the
kernel k is said to be characteristic and the MMD dk becomes a metric on P (Sriperumbudur et al., 2010). Recently, Simon-Gabriel & Schölkopf (2016, Theorem 55)
and Sriperumbudur (2016, Theorem 3.2) have explored a
weaker metrizable property of dk . Throughout the rest of
this paper, let X be a Polish space. Consider the weak
topology on P induced by the weak convergence: Pl → P
weakly if and only if Ey∼Pl f (y) → Ey∼P f (x) for every
bounded continuous function f : X → R. The following
theorem states when dk metrizes this weak convergence.1
Theorem 1
(Simon-Gabriel & Schölkopf (2016);
Sriperumbudur (2016)). If X is Polish, locally compact Hausdorff, and k is continuous and characteristic,
then dk metrizes the weak convergence on P.
The above theorem indicates that the metric dk induces the
same topology as that of weak convergence. An example
of Polish, locally compact Hausdorff space is Rd , and both
Gaussian and Laplacian kernels defined on it are continuous and characteristic (Sriperumbudur, 2016).

The above limit is called type-II error exponent. Clearly,
β = 0 implies that the type-II error probability is bounded
away from 0 or decays to 0 sub-exponentially, while β =
∞ indicates it vanishes more than exponentially fast.
2.3. Universal Hypothesis Testing
We first present Stein’s lemma on the optimal exponential
decay rate of any level α test for simple hypothesis testing between two known distributions. Let D(P kQ) denote
the KLD between two distributions P and Q defined on a
Polish space X . The lemma is stated below.
Lemma 1 (Stein’s Lemma (Dembo & Zeitouni, 2009;
Cover & Thomas, 2006)). Let xn i.i.d. ∼ R. Consider hypothesis testing between H0 : R = P and H1 : R = Q,
with 0 < D(P kQ) < ∞. Given 0 < α < 1, let
Ω∗ (n, P, Q) = (Ω∗0 (n, P, Q), Ω∗1 (n, P, Q)) be the optimal
level α test with which the type-II error probability is minimized for each n. Then the type-II error probability decays
to 0 exponentially at a rate of D(P kQ) as n → ∞, that is,
lim −

n→∞

2.2. Statistical Testing
Given the distribution P and independent sample xn from
an unknown distribution Q, we want to determine whether
to accept H0 : P = Q or H1 : P 6= Q. A decision
rule (test) Ω(n) = (Ω0 (n), Ω1 (n)) partitions X n into two
disjoint sets with Ω0 (n)∪Ω1 (n) = X n . If xn ∈ Ωi (n), i =
0, 1, a decision is made in favor of hypothesis Hi . We say
that Ω0 (n) is an acceptance region for the null hypothesis
H0 and Ω1 (n) the corresponding critical region. There are
two types of errors: a type-I error is made when P = Q is
rejected while H0 is true, and a type-II error occurs when
P = Q is accepted despite H1 being true. The type-I and
type-II error probabilities are respectively
αn = P (Ω1 (n)) = Pxn ∼P (xn ∈ Ω1 (n)) ,
βn = Q(Ω0 (n)) = Pxn ∼Q (xn ∈ Ω0 (n)) .
In general, the two types of error probabilities can not be
minimized simultaneously. Typical approach is to set an
upper bound α on the type-I error probability and consider
only level α tests, i.e., tests with αn ≤ α. A level α test is
consistent when it has vanishing type-II error in the large
sample limit. Such tests are said to be exponentially consistent if the type-II error probability additionally vanishes
exponentially fast with respect to the sample size, i.e., when
0 < lim inf −
n→∞

1
log βn := β < ∞.
n

1
log Q(Ω∗0 (n, P, Q)) = D(P kQ).
n

Let Ω(n) be a goodness of fit test of level α. When xn
i.i.d. ∼ Q under the alternative hypothesis, the corresponding type-II error probability βn = Q(Ω0 (n)) can not be
lower than Q(Ω∗0 (n, P, Q)). As a result, Stein’s lemma
indicates that the type-II error exponent is bounded by
D(P kQ). The problem is to find a test Ω(n) such that for
any given P ,
αn ≤ α,
1
lim inf − log βn = D(P kQ),
n→∞
n
for arbitrary Q satisfying 0 < D(P kQ) < ∞, giving rise
to the name universal hypothesis testing.

3. Maximum Mean Discrepancy Based Tests
for Universal Hypothesis Testing
In this section, we study two classes of MMD based goodness of fit tests that are universally asymptotically optimal,
followed by discussions on related aspects.
We summarize the assumptions that are made in the last
section and that will be used throughout this section: the
sample space X is Polish, locally compact Hausdorff; P
is the set of all Borel probability measures defined on X ;
kernel k is bounded continuous and characteristic. This
ensures that the MMD dk metrizes weak convergence.
3.1. Simple Kernel Tests

1

Indeed, Simon-Gabriel & Schölkopf (2016) show that X
only needs to be locally compact Hausdorff. We require X be
Polish in order to utilize some large deviation results.

The first test is based on the MMD between the target distribution P and the empirical distribution of sample xn .

Asymptotically Optimal Tests for Goodness of Fit

Though easy to come up with, its optimality for the universal hypothesis testing problem remains unknown.
n
To proceed,
Pnlet Q̂n denote the empirical measure of x , i.e.,
1
Q̂n = n i=1 δxi with δx being Dirac measure at x. We
have a simple kernel test with acceptance region
o
n
Ω0 (n) = xn : dk (P, Q̂n ) ≤ γn ,

where γn is a threshold and d2k (P, Q̂n ) is computed by
n
n
n
2X
1 XX
′
′ k(y, y ) −
Ey k(xi , y),
k(x
,
x
)
+
E
i
j
yy
n2 i=1 j=1
n i=1

with y, y ′ i.i.d. ∼ P . Throughout this paper, we will simply use dk (P, Q̂n ) ≤ γn to represent the set Ω0 (n). On the
one hand, we want the threshold γn to be small so that the
test type-II error probability is low; on the other hand, the
threshold cannot be too small in order to satisfy the level
constraint on the type-I error. The balance between the two
error probabilities is attained with a threshold that diminishes at an appropriate rate.
Theorem 2. For P ∈ P and xn i.i.d. ∼ Q ∈ P, assume
that D(P kQ) < ∞. Also assume 0 ≤ k(·, ·) ≤ K with K
being a constant
value.pFor a given level α, 0 < α < 1,
p
set γn = K/n(2 + 2 log α−1 ). Then the kernel test
dk (P, Q̂n ) ≤ γn is optimal to universal hypothesis testing.
That is, when the null hypothesis H0 : P = Q is true,


P dk (P, Q̂n ) > γn ≤ α;
and if the alternative hypothesis H1 : P 6= Q holds,

1 
lim inf − Q dk (P, Q̂n ) ≤ γn = D(P kQ).
n→∞
n
A proof is provided in Section 5.1.
SimilarP to P (Gretton et al., 2012a),
by replacing
n
n
1
k(xi , xj )
in
d2k (P, Q̂n )
with
j=1
i=1
n2
P
P
n
1
i=1
j6=i k(xi , xj ), we can obtain an unbin(n−1)

ased test statistic, denoted as d2u (P, Q̂n ). We remark that
d2u (P, Q̂n ) is not a squared quantity and can be negative,
due to the unbiasedness. Our result is summarized as
follows.
Corollary 1. Under the same conditions as in Theorem 2,
the test d2u (P, Q̂n ) ≤ γn2 + K/n is a level α asymptotically
optimal test for universal hypothesis testing.
The tests in this section still require computing integrals,
namely, Ey k(xi , y) and Eyy′ k(y, y ′ ). Our purpose here
is to show that the universally optimal error exponent is
indeed achievable, giving a reasonable criterion to claim
optimality for goodness of fit tests as well as a solution to
an open problem. In the next section, we consider another
class of MMD based tests, achieving this error exponent
without the need for computing integrals.

3.2. Kernel Two-Sample Tests
In the context of model criticism, Lloyd & Ghahramani
(2015) cast goodness of fit testing into a two-sample problem where one also draws samples y m from distribution P .
A question that arises is the choice of number of samples,
which is not obvious due to the lack of an explicit criterion. In light of universal hypothesis testing, we could ask
how many samples would suffice to attain the optimal error
exponent D(P kQ).
Denote by P̂m the empirical measure of y m . We consider
a two-sample test with acceptance region
Ω0 (m, n) = {(y m , xn ) : dk (P̂m , Q̂n ) ≤ γm,n },
where
γm,n =




p
1
1
2 + 2 log(2α−1 ) ,
(K/m) 2 + (K/n) 2

d2k (P̂m , Q̂n ) =

m X
m
X

k(yi , yj ) +

i=1 j=1

k(xi , xj )

i=1 j=1

m

−

n X
n
X

n

2 XX
k(yi , xj ),
mn i=1 j=1

and K is a finite bound on kernel k(·, ·). The statistic
d2k (P̂m , Q̂n ) for estimating squared MMD was originally
proposed in (Gretton et al., 2012a). Notice that the type-I
and type-II error probabilities depend on both P and Q in
the two-sample testing. Although additional randomness
is introduced, it does not hurt the statistical optimality in
terms of the type-II error exponent, as stated below.
Theorem 3. Assume the same conditions as in Theorem 2,
and that y m i.i.d. ∼ P and xn i.i.d. ∼ Q. Let Ω1 (m, n) =
X m+n \ Ω0 (m, n) be the critical region. Then under the
null hypothesis H0 : P = Q,
Pym xn (Ω1 (m, n)) ≤ α;
and under the alternative hypothesis H1 : P 6= Q,
lim inf −
n→∞

1
log Pym xn (Ω0 (m, n)) = D(P kQ),
n

provided that limn→∞

m
n

= ∞.

We present a proof in Section 5.2. Similar to previous simple kernel tests, we can alsoP
replace
the first two
n P
1
terms in d2k (P̂m , Q̂n ) with m(m−1)
i=1
j6=i k(yi , yj )
Pn P
1
and n(n−1) i=1 j6=i k(xi , xj ). This leads to an unbiased statistic which we denote as d2u (P̂m , Q̂n ) and that has
nearly optimal variance (Gretton et al., 2012a). The corollary below shows its universally asymptotic optimality.
Corollary 2. Under the same assumptions as in Theo2
+ K/m + K/n has
rem 3, the test d2u (P̂m , Q̂n ) ≤ γm,n
its type-I error probability below α and type-II error exponent being D(P kQ), given that m/n → ∞ as n → ∞.

Asymptotically Optimal Tests for Goodness of Fit

3.3. Discussions

orem 2 and is omitted.

We make the following remarks on the MMD based tests.

Proposition 1. Consider X = Rd . Let xn , P , Q and Q̂n
be assumed in Theorem 2. Let d(·, ·) be some metric of
weak convergence of probability measures. For a fixed α ∈
(0, 1), a test Ω(n) = (Ω0 (n), Ω1 (n)) has level α and is
universally asymptotically optimal if

Threshold choice. The distribution-free thresholds used
in the MMD based tests are generally too conservative, as
the actual distribution P is not taken into account. Alternatively, we may use Monte Carlo or bootstrap methods to empirically estimate the threshold (Gretton et al.,
2012a; Chwialkowski et al., 2016; Jitkrittum et al., 2017),
making the tests (asymptotically) level α. Notice that these
methods introduce additional randomness on the threshold
choice and further on the type-II error probability.2 A simple fix is to take the minimum of the Monte Carlo or bootstrap threshold and the distribution-free threshold, guaranteeing a vanishing threshold and hence the optimal error
exponent. In practice, the bootstrap threshold is mostly
smaller than the distribution-free threshold.
Finite vs. asymptotic regime. A finitely positive error exponent β = D(P kQ) implies
that the error probability de
cays with O e−n(β−ǫ) where ǫ ∈ (0, β) can be arbitrarily small. It further implies that kernels in our tests affect
only the sub-exponential term in the type-II error probability as long as they are bounded continuous and characteristic. When n is small, the sub-exponential term may
dominate and the test performance does depend on kernels.
Selecting a proper kernel is an ongoing research topic and
we refer the reader to related works such as (Gretton et al.,
2012b; Sutherland et al., 2017; Jitkrittum et al., 2017).
Non i.i.d. data. We notice that Chwialkowski et al. (2016)
consider non-i.i.d. data by use of wild bootstrap. In general,
statistical optimality with non-i.i.d. data, including sample
y m if drawn using the Markov Chain Monte Carlo method,
is difficult to establish even for simple hypothesis testing.
Fair alternative. A notion of fair alternative with fixed
KLD was raised in (Ramdas et al., 2015) for the twosample testing as dimension increases. In light of our results or Stein’s lemma, the same fair alternative can also be
considered for goodness of fit testing.

4. Kernel Stein Discrepancy (KSD) and Other
Distance Measures
We discuss other distance measures that may also be used
to construct goodness of fit tests in a similar manner to
the MMD. We present a sufficient condition for a test to
achieve the optimal type-II error exponent under a fixed
significance level. The proof follows the same idea of The2

We emphasize the subtlety here. That the bootstrap threshold
decays to zero in the limit suffices to meet an asymptotic constant
constraint, but does not guarantee the desired type-II decay rate.
In other words, we also require a decay rate characterization on
the bootstrap threshold, which is usually difficult.

(a) P (Ω1 (n)) ≤ α,
(b) Ω0 (n) ⊂ {xn : d(P, Q̂n ) ≤ γn }, γn → 0 as n → ∞.
For distributions defined on Rd , many other distance measures metrize weak convergence, including Lévy-Prohorov
metric, bounded Lipschitz metric, and Wasserstein distance. The total variation distance is an upper bound on
the MMD up to a constant (Sriperumbudur et al., 2010),
and the KSD can be lower bounded in terms of the MMD
or the bounded Lipschitz metric (involving some unknown
constants) (Gorham & Mackey, 2017, Theorems 5, 7, and
8). Therefore, comparing these distance measures between
P and Q̂n with a vanishing threshold meets Condition (b).3
However, to our best knowledge, there does not exist a uniform or distribution-free threshold that makes the tests meet
Condition (a). As such, these distance measures do not give
rise to asymptotically optimal tests with a fixed level.
We may, nevertheless, relax Condition (a) to an asymptotic
case, i.e, lim supn→∞ P (Ω1 (n)) ≤ α. We will focus on
the KSD as other distance measures are generally hard to
compute in practice. Let p and q be the respective density
functions for P and Q defined on Rd . Chwialkowski et al.
(2016) and Liu et al. (2016) define the KSD as
dS (P, Q) =

max Ex∼Q [sp (x)f (x) + ∇x f (x)] ,

kf kHk ≤1

where kf kHk ≤ 1 are functions from the unit ball in a
RKHS Hk , and sp (x) = ∇x log p(x) is the score function of p(x). With a C0 -universal kernel (Carmeli et al.,
2010) and Ex∼Q k∇x log p(x) − ∇x log q(x)k2 ≤ ∞,
Chwialkowski et al. (2016, Theorem 2.2) show that
dS (P, Q) = 0 if and only if P = Q. The squared KSD
can also be written as
d2S (P, Q) = Ex∼Q Ex′ ∼Q hp (x, x′ ),
where hp (x, y) = sTp (x)sp (y)k(x, y) + sTp (y)∇x k(x, y) +
sTp (x)∇y k(x, y)+trace(∇x,y k(x, y)). Then d2S (P, Q) can
Pn Pn
be estimated by d2S (P, Q̂n ) = n12 i=1 j=1 hp (xi , xj ),
3

Specifically, let dBL and dS denote the bounded Lipschitz
metric and the KSD, respectively. Gorham & Mackey (2017,
Theorems 7 and 8) showed that dBL (P, Q̂n ) ≤ g(dS ) where
g(dS ) → 0 as dS → 0. Thus, there exists γn′ such that
{xn : dS (P, Q̂n ) ≤ γn } ⊂ {xn : dBL (P, Q̂n ) ≤ γn′ } and
γn′ → 0 as n → ∞.

Asymptotically Optimal Tests for Goodness of Fit

which is a degenerate V-statistic under the null hypothesis
(Chwialkowski et al., 2016).
An acceptance threshold for d2S (P, Q̂n ) can be empirically computed through bootstrap (Arcones & Gine, 1992;
Chwialkowski et al., 2014; Leucht et al., 2012), and the resulting test satisfies the given level asymptotically. As discussed in Section 3.3, bootstrap introduces randomness on
the threshold and further on the type-II error probability,
making it difficult to verify Condition (b). Our approach
still requires a (deterministically) vanishing threshold that
satisfies the asymptotic constraint on the type-I error. Here
we use the result of Chwialkowski et al. (2016, Proposition 3.2), which establishes that nd2S (P, Q̂n ) converges
weakly to some distribution under the null hypothesis.
We assume a fixed α-quantile γα of the limiting cumulative distribution function, so that limn→∞ P (d2S (P, Q̂n ) >
γα /n)p= α. Thus, if we pick γn = o(n), e.g., γn =
(1 + log α−1 )n−1/2 , we get γn > γα /n in the limit and
thus limn→∞ P (d2S (P, Q̂n ) > γn ) ≤ α.

Lemma 2. Assume 0 ≤ k(·, ·) ≤ K. Given y m i.i.d. ∼ P ,
denote by P̂m the empirical measure of y m . It follows that
 2 


1
ǫ m
2
.
Pym dk (P, P̂m ) > 2 (K/m) + ǫ ≤ exp −
2K
Proof. Apply Mcdiarmid’ inequality and Rademacher average, following the same idea of (Gretton et al., 2012a,
Theorem 7).

Theorem 4. Let P and Q be defined onp
Rd , and consider
2
the test dS (P, Q̂n ) ≤ γn with γn = (1 + log α−1 )n−1/2 .

We also need two large deviation results: lower semicontinuity of KLD and Sanov’s theorem .
Lemma 3 (Van Erven & Harremos (2014)). For a fixed
Q ∈ P, D(·kQ) is a lower semi-continuous function with
respect to the weak topology of P. That is, for any ǫ > 0,
there exists a neighborhood U ⊂ P of P such that for any
P ′ ∈ U , D(P ′ kQ) ≥ D(P kQ) − ǫ if D(P kQ) < ∞, and
D(P ′ kQ) → ∞ as P ′ tends to P if D(P kQ) = ∞.
Theorem 5 (Sanov’s Theorem (Sanov, 1958;
Dembo & Zeitouni, 2009)). Let xn i.i.d. ∼ Q ∈ P.
For a set Γ ⊂ P,
1
lim sup − log Pxn (Q̂n ∈ Γ) ≤ inf D(RkQ),
R∈int Γ
n
n→∞
1
lim inf − log Pxn (Q̂n ∈ Γ) ≥ inf D(RkQ).
n→∞
R∈cl Γ
n

(a) If h is Lipschitz continuous, Ex∼Q hp (x, x) <
∞, and a technical condition on τ -mixing holds
(Chwialkowski et al., 2016, Proposition 3.1), then

where int Γ and cl Γ are the interior and closure of Γ with
respect to the weak topology on P, respectively.

We summarize the above discussions in the following theorem.

lim P (d2S (P, Q̂n ) > γn ) ≤ α.

n→∞

(b) If 1) d = 1, k(x, y) = Φ(x − y) for some Φ ∈ C 2
(twice continuous differentiable) with a non-vanishing
generalized Fourier transform; 2) k(x, y) = Φ(x − y)
for some Φ ∈ C 2 with a non-vanishing generalized
Fourier transform, and (Q̂n )n≥1 is uniformly tight; 3)
k(x, y) = (c2 + kx − yk22)η for c > 0 and η ∈ (−1, 0)
(Gorham & Mackey, 2017, Theorems 5, 7, and 8),
then under H1 : P 6= Q with D(P kQ) < ∞,
lim inf −
n→∞

1
log Q(d2S (P, Q̂n ) ≤ γn ) = D(P kQ).
n

Similar to the distribution-free thresholds in Section 3, γn
is usually not good enough for finite sample cases. A simple fix is to take the minimum of this threshold and the
bootstrap one.

5. Proofs of the Main Results
5.1. Proofs of Simple Kernel Tests
We first present the following lemma for deriving a suitable
threshold to make the test satisfy the given level constraint.

Outline of proof. Sanov’s theorem states that the probability of Q̂n ∈ Γ vanishes at least exponentially fast if the
underlying distribution Q ∈
/ cl Γ. Notice that deciding if
xn ∈ {xn : dk (P, Q̂n ) ≤ γn } is equivalent to deciding
if its empirical measure Q̂n ∈ {P ′ : dk (P, P ′ ) ≤ γn }.
Thus, if Q is eventually excluded by the closure of {P ′ :
dk (P, P ′ ) ≤ γn }, we get an exponential decay rate of typeII error probability. The rest is to show that the error exponent reaches D(P kQ) using the weak metrizable property
of the MMD and the lower semi-continuity of the KLD.
Proof of Theorem 2. That the test dk (P, Q̂n ) ≤ γn has
level α can be directly seen from Lemma 2. Since Stein’s
lemma gives an upper bound on the type-II error exponent
for any level α test, i.e., β ≤ D(P kQ), what remains is to
show β ≥ D(P kQ).
By our assumption, dk metrizes weak convergence on P
(cf. Theorem 1). For any constant γ > 0, there exists an
integer n0 such that γn < γ for all n > n0 . Therefore,


1
β = lim inf − log Q dk (P, Q̂n ) ≤ γn
n→∞
n


1
≥ lim inf − log Q dk (P, Q̂n ) ≤ γ
n→∞
n
≥ ′
inf ′
D(P ′ kQ),
(1)
{P ∈P:dk (P,P )≤γ}

Asymptotically Optimal Tests for Goodness of Fit

where the last inequality is from Sanov’s theorem and that
{P ′ ∈ P : dk (P, P ′ ) ≤ γ} is closed with respect to weak
topology. Since γ can be arbitrary, we have
β ≥ lim+
γ→0

inf

{P ′ ∈P:dk (P,P ′ )≤γ}

D(P ′ kQ).

Using the lower semi-continuity of the KLD in Lemma 3
and the assumption that D(P kQ) < ∞, the limit on the
right-hand side is greater than D(P kQ) − ǫ for arbitrarily
given ǫ > 0. This further implies β ≥ D(P kQ).
Proof of Corollary 1. We first have

p
p
′
and γm,n
= 2 K/m + 2KnD(P kQ)/m. It suffices to
u
l
show that max{βm,n
, βm,n
} decreases exponentially as n
scales. We first have


u
′
βm,n
≤ Pym dk (P, P̂m ) > γm,n
≤ e−nD(P kQ) . (2)

u
The last inequality is also due to Lemma 2. Thus, βm,n
vanishes at least exponentially fast with the error exponent
being D(P kQ).

l
For βm,n
, we have it equal to
  

X
P P̂m Q dk (P̂m , Q̂n ) < γm,n
′
{P̂m :dk (P,P̂m )≤γm,n
}

d2u (P, Q̂n ) − d2k (P, Q̂n )
n X
n
X
1
1 X
k(xi , xi )
= 2
k(xi , xj ) − 2
n (n − 1) i=1
n i=1
j6=i

It holds that
{x

sup
′
{P̂m :dk (P,P̂m )≤γm,n
}



Q dk (P̂m , Q̂n ) < γm,n



′
≤ Q dk (P, Q̂n ) ≤ γm,n + γm,n
,
where the last inequality is because dk is a metric. Similar
to Eq. (1), we get

≤ K/n.
n

≤

: d2k (P, Q̂n ) ≤ γn2 }

⊂

⊂

n

{x : d2u (P, Q̂n ) ≤ γn2 + K/n}
{xn : d2k (P, Q̂n ) ≤ γn2 + 2K/n}.

Thus, under H0 : P = Q, we have




P d2u (P, Q̂n ) > γn2 + K/n ≤ P d2k (P, Q̂n ) > γn2
≤ α,

where the last inequality is from Lemma 2 and the fact that
dk (P, Q̂n ) ≥ 0. The type-II error exponent follows from


1
lim inf − log Q d2u (P, Q̂n ) ≤ γn2 + K/n
n→∞
n


1
≥ lim inf − log Q d2k (P, Q̂n ) ≤ γn2 + 2K/n
n→∞
n
≥ D(P kQ).
The last inequality can be shown by similar argument of
Eq. (1) as γn2 + 2K/n → 0 as n → ∞. Applying Stein’s
lemma completes the proof.
5.2. Proof of Two-Sample Tests
Proof of Theorem 3. That the two-sample test is level α
can be verified by (Gretton et al., 2012a, Theorem 7).
We can write the type-II error probability as

1
l
log βn,m
≥ D(P kQ),
n
′
because γm,n + γm,n
→ 0 as n → ∞. Together with
Eq. (2), we have under H1 : P 6= Q,
lim inf −
n→∞

lim inf −
n→∞

1
log Pym xn (Ω0 (m, n)) ≥ D(P kQ).
n

We next show the other direction under H1 . We have


Pym xn dk (P̂m , Q̂m ) ≤ γm,n


(a)
′
, dk (P, Q̂n ) ≤ γn′
≥ Pym xn dk (P̂m , P ) ≤ γm

 

′
Q dk (P, Q̂n ) ≤ γn′ ,
= P dk (P̂m , P ) ≤ γm
where (a) is p
because dk is p
a metric, and we choose
′
−1 )) K/m and γ ′ = (2 +
γ
=
(2
+
2
log(2α
n
p
pm
′
2 log(2α−1 )) K/n so that γm,n = γm
+ γn′ . Then
′
Lemma 2 implies P (dk (P̂m , P ) ≤ γm
) > 1 − α/2 and
′
P (dk (P, Q̂n ) ≤ γn ) > 1 − α/2. Together with Stein’s
Lemma, we get


1
lim inf − log Pym xn dk (P̂m , Q̂n ) ≤ γm,n
n→∞
n



1
≤ lim inf − log (1 − α/2) Q dk (P, Q̂n ) ≤ γn′
n→∞
n
≤ D(P kQ).

u
l
+ βm,n
,
Pym xn (Ω0 (m, n)) = βm,n

where


′
u
,
βm,n
= Pym xn dk (P̂m , Q̂n ) ≤ γm,n , dk (P, P̂m ) > γm,n


′
l
,
βm,n
= Pym xn dk (P̂m , Q̂n ) ≤ γm,n , dk (P, P̂m ) ≤ γm,n

Proof of Corollary 2. We have
d2u (P̂m , Q̂n ) − d2k (P̂m , Q̂n ) ≤ K/n + K/m.
The rest follows the same idea of Corollary 1, along with
(Gretton et al., 2012a, Theorem 7)

Asymptotically Optimal Tests for Goodness of Fit

We evaluate the following tests with a fixed level α =
2
0.1, all using Gaussian kernel k(x, y) = e−kx−y||2 /(2w) :
1) Simple: the simple kernel test dk (P, Q̂n ). The threshold is estimated by drawing i.i.d. samples under the model
P , i.e., the Monte Carlo method. The number of trials is
500. 2) Two-sample: the two-sample test dk (P̂m , Q̂n )
with m = n1.5 . Threshold is obtained from the bootstrap method in (Gretton et al., 2012a), with 500 bootstrap replicates. 3) KSD: a KSD based test. We simply use the test proposed in (Chwialkowski et al., 2016),
as other KSD based tests (Liu et al., 2016; Jitkrittum et al.,
2017) have comparable performance in terms of the typeII error probability. We use wild bootstrap method
(Chwialkowski et al., 2016) with 500 replicates to estimate
the α-quantile.
Gaussian vs. Laplace. We √
consider a one-dimensional
problem in which P : N (0, 2 2) and Q : Laplace(0, 2),
a zero-mean Laplace distribution with scale parameter 2.
The parameters are chosen so that P and Q have the same
mean and variance. We repeat 500 trials of each hypothesis with respect to different sample sizes, and pick a fixed
bandwidth w = 1 for all the kernel tests. We also evaluate
the likelihood ratio test LR, an oracle approach assuming
both P and Q are known. In Figure 1a, the test LR has
the lowest type-II error rate as expected, while Simple
and Two-sample perform slightly better than KSD. All
the kernel tests have the type-I error rates around the given
level α = 0.1, shown in Figure 1b.
1.0

0.125
type-I error rate

type-II error rate

0.8

0.6

0.4

0.2

0.100
0.075
0.050
0.000

0.0
0

20

40

60

80

100

120

Simple
Two-sample
KSD
LR

0.025
0

20

40

n

(a)

60
n

80

100

120

(b)

Figure 1. Gaussian vs. Laplace.

Gaussian Mixture. We next consider a similar experiment

With the median heuristic for bandwidth choice, KSD and
Two-sample perform similarly whereas Simple has its
type-II error probability decreasing slowly, as shown in
Figure 2a. Picking a fixed bandwidth w = 1 for Simple
again achieves a better performance. In light of the role of
kernels, we then search over the kernel bandwidths in [0, 8]
for a fixed sample size n = 50. In Figure 2b, Simple and
Two-smaple tend to have lower type-II error rates when
w is small, while KSD achieves lower error rates around
w = 5. The optimal type-II error rates of Simple and KSD
are close and are slightly lower than that of Two-sample.
Drawing more samples y m from P may reduce the gap but
also increases the computation cost. Besides, we observe
that KSD is more computationally efficient in this experiment, as it does not need to draw samples.
1.0

1.0

0.8

0.8

type-II error rate

We present empirical results to validate our theoretic findings. We note that there have been extensive experiments on performance comparisons of the
MMD based two-sample tests and the KSD based
tests in (Chwialkowski et al., 2016; Liu et al., 2016;
Jitkrittum et al., 2017), where the number m of samples
drawn from P is usually fixed. Our focus will be to compare statistical performance of KSD based tests and the
tests of dk (P, Q̂n ) and dk (P̂m , Q̂n ) in the finite sample
regime.

We draw i.i.d. sample xn from
setting
P5to (Liu et al., 2016).
2
Q : k=1 ak N (x; µk , σ ) with ak = 1/5, σ 2 = 1, and µk
randomly drawn from Uniform[0, 10]. We then generate P
by adding standard Gaussian noise (perturbation) to µk . In
(Liu et al., 2016), the number of samples y m drawn from
P is fixed while varying the observed sample number n.
Here we pick m = n1.5 and report the type-II error rates in
Figure 2, averaged over 500 random trials.

type-II error rate

6. Experiments

0.6

0.4

0.2

0.0
20

40

60

80

100

n

(a)

Simple
Two-sample
KSD
Simple, fixed width

0.6
0.4
0.2
0.0

0

2

4
w

6

8

(b)

Figure 2. Gaussian mixture. (a) median bandwidth for Simple,
Two-sample, and KSD, and a fixed bandwidth w = 1 for
Simple; (b) fixing n = 50 and varying kernel bandwidths.

7. Concluding Remarks
In this paper, we have shown that two classes of MMD
based tests are universally asymptotically optimal for goodness of fit testing, and that a KSD based test achieves a
weaker optimality in the sense that a relaxed level constraint is placed on the type-I error probability. In the finite sample regime, these kernel tests have similar performance, while the KSD based test is more efficient. Our
work not only solves a long-standing open problem in information theory and statistics, but also provides theoretic
guarantee for these kernel tests in terms of statistical performance. We believe that the technique of using Sanov’s
theorem and the weak convergence properties of the MMD
and the KSD can be further used to evaluate other kernel
tests.

Asymptotically Optimal Tests for Goodness of Fit

References
Arcones, Miguel A and Gine, Evarist. On the bootstrap of
U and V statistics. The Annals of Statistics, pp. 655–674,
1992.
Baringhaus, L and Henze, N. A consistent test for multivariate normality based on the empirical characteristic
function. Metrika, 35(1):339–348, 1988.
Beirlant, Jan, Györfi, László, and Lugosi, Gábor. On the
asymptotic normality of the L1 - and L2 -errors in histogram density estimation. Canadian Journal of Statistics, 22(3):309–318, 1994.
Berlinet, Alain and Thomas-Agnan, Christine. Reproducing Kernel Hilbert Spaces in Probability and Statistics.
Springer Science & Business Media, 2011.
Bowman, AW and Foster, PJ. Adaptive smoothing and
density-based tests of multivariate normality. Journal of
the American Statistical Association, 88(422):529–537,
1993.
Carmeli, Claudio, De Vito, Ernesto, Toigo, Alessandro, and
Umanitá, Veronica. Vector valued reproducing kernel
Hilbert spaces and universality. Analysis and Applications, 8(01):19–61, 2010.
Chwialkowski, Kacper, Strathmann, Heiko, and Gretton,
Arthur. A kernel test of goodness of fit. In International
Conference on Machine Learning, 2016.
Chwialkowski, Kacper P, Sejdinovic, Dino, and Gretton,
Arthur. A wild bootstrap for degenerate kernel tests.
In Advances in Neural Information Processing Systems,
2014.
Cover, Thomas M and Thomas, Joy A. Elements of Information Theory. New York: Wiley, 2nd edition, 2006.
Csiszár, Imre and Shields, Paul C. Information theory and
statistics: A tutorial. Foundations and Trends in Communications and Information Theory, 1(4):417–528, 2004.
Dembo, Amir and Zeitouni, Ofer. Large Deviations Techniques and Applications. New York: Springer, 2009.
Gorham, Jackson and Mackey, Lester. Measuring sample
quality with Stein’s method. In NIPS, 2015.
Gorham, Jackson and Mackey, Lester. Measuring sample
quality with kernels. In ICML, 2017.
Gretton, Arthur, Borgwardt, Karsten M, Rasch, Malte J,
Schölkopf, Bernhard, and Smola, Alexander. A kernel
two-sample test. Journal of Machine Learning Research,
13(Mar):723–773, 2012a.

Gretton, Arthur, Sejdinovic, Dino, Strathmann, Heiko, Balakrishnan, Sivaraman, Pontil, Massimiliano, Fukumizu,
Kenji, and Sriperumbudur, Bharath K. Optimal kernel
choice for large-scale two-sample tests. In Advances in
Neural Information Processing Systems, 2012b.
Györfi, László and Van Der Meulen, Edward C. A consistent goodness of fit test based on the total variation
distance. In Nonparametric Functional Estimation and
Related Topics, pp. 631–645. Springer, 1991.
Hoeffding, Wassily. Asymptotically optimal tests for multinomial distributions. The Annals of Mathematical Statistics, pp. 369–401, 1965.
Jitkrittum, Wittawat, Xu, Wenkai, Szabo, Zoltan, Fukumizu, Kenji, and Gretton, Arthur. A linear-time kernel
goodness-of-fit test. In NIPS, 2017.
Koller, Daphne and Friedman, Nir. Probabilistic Graphical
Models: Principles and Techniques. MIT Press, 2009.
Leucht, Anne et al. Degenerate U- and V-statistics under weak dependence: Asymptotic theory and bootstrap
consistency. Bernoulli, 18(2):552–585, 2012.
Liu, Qiang, Lee, Jason, and Jordan, Michael. A kernelized
stein discrepancy for goodness-of-fit tests. In International Conference on Machine Learning, 2016.
Lloyd, James Robert and Ghahramani, Zoubin. Statistical
model criticism using kernel two sample tests. In Advances in Neural Information Processing Systems, 2015.
Muandet, Krikamol, Fukumizu, Kenji, Sriperumbudur,
Bharath, and Schlkopf, Bernhard. Kernel mean embedding of distributions: A review and beyond. Foundations
and Trends in Machine Learning, 10(1-2):1–141, 2017.
Oates, Chris J, Girolami, Mark, and Chopin, Nicolas. Control functionals for Monte Carlo integration. Journal
of the Royal Statistical Society: Series B (Statistical
Methodology), 79(3):695–718, 2017.
Ramdas, Aaditya, Reddi, Sashank Jakkam, Póczos,
Barnabás, Singh, Aarti, and Wasserman, Larry A. On
the decreasing power of kernel and distance based nonparametric hypothesis tests in high dimensions. In AAAI,
2015.
Salakhutdinov, Ruslan. Learning deep generative models.
Annual Review of Statistics and Its Application, 2:361–
385, 2015.
Sanov, Ivan N. On the probability of large deviations of
random variables. Technical report, North Carolina State
University. Dept. of Statistics, 1958.

Asymptotically Optimal Tests for Goodness of Fit

Simon-Gabriel, C.-J. and Schölkopf, B. Kernel distribution embeddings: Universal kernels, characteristic kernels and kernel metrics on distributions. arXiv preprint
arXiv:1604.05251, 2016.
Sriperumbudur, Bharath. On the optimal estimation of
probability measures in weak and strong topologies.
Bernoulli, 22(3):1839–1893, 08 2016.
Sriperumbudur, Bharath K, Gretton, Arthur, Fukumizu,
Kenji, Schölkopf, Bernhard, and Lanckriet, Gert RG.
Hilbert space embeddings and metrics on probability
measures. Journal of Machine Learning Research, 11
(Apr):1517–1561, 2010.
Sutherland, D., Tung, H-Y, Strathmann, H., De, S., Ramdas, A., Smola, A., and Gretton, A. Generative models
and model criticism via optimized maximum mean discrepancy. In ICLR, 2017.
Unnikrishnan, Jayakrishnan, Huang, Dayu, Meyn, Sean P,
Surana, Amit, and Veeravalli, Venugopal V. Universal
and composite hypothesis testing via mismatched divergence. IEEE Transactions on Information Theory, 57(3):
1587–1603, 2011.
Van Erven, Tim and Harremos, Peter. Rényi divergence
and Kullback-Leibler divergence. IEEE Transactions on
Information Theory, 60(7):3797–3820, 2014.
Yang, Pengfei and Chen, Biao. Robust Kullback-Leibler
divergence and universal hypothesis testing for continuous distributions. arxiv preprint arxiv:1711.04238,
2017.
Zeitouni, Ofer and Gutman, Michael. On universal hypotheses testing via large deviations. IEEE Trans. Inf.
Theory, 37(2):285–290, 1991.

