1

Nonparametric Composite Hypothesis Testing
in an Asymptotic Regime
Qunwei Li, Student Member, IEEE, Tiexing Wang, Donald J. Bucci,
Yingbin Liang, Senior Member, IEEE, Biao Chen, Fellow, IEEE and

arXiv:1712.03296v1 [cs.IT] 8 Dec 2017

Pramod K. Varshney, Fellow, IEEE

Abstract
We investigate the nonparametric, composite hypothesis testing problem for arbitrary unknown distributions and in the asymptotic regime with the number of hypotheses grows exponentially large. Such
type of asymptotic analysis is important in many practical problems, where the number of variations
that can exist within a family of distributions can be countably infinite. We introduce the notion of
discrimination capacity, which captures the largest exponential growth rate of the number of hypotheses
(with the number of samples) so that there exists a test with asymptotically zero probability of error. Our
approach is based on various distributional distance metrics in order to incorporate the generative model
of the data. We provide example analyses of the error exponent using the maximum mean discrepancy
(MMD) and Kolmogorov-Smirnov (KS) distances and characterized the corresponding discrimination
rates (i.e., lower bounds on the discrimination capacity) for these tests. Finally, We provide an upper
bound on the discrimination capacity based on Fano’s inequality.

Index Terms
Nonparametric hypothesis testing, channel coding, maximum mean discrepancy, Kolmogorov-Smirnov
distance, error exponent
This material is based upon work supported in part by the Defense Advanced Research Projects Agency under Contract
No. HR0011-16-C-0135. The work of Y. Liang was also supported in part by the National Science Foundation under grant
CCF-1801855.
Q. Li, T. Wang, B. Chen, and P. K. Varshney are with the Department of Electrical Engineering and Computer Science, Syracuse
University, Syracuse, NY 13244, USA (e-mail: qli33@syr.edu; twang17@syr.edu; bichen@syr.edu; varshney@syr.edu).
D. J. Bucci is with Lockheed Martin - Advanced Technology Labs, Cherry Hill, NJ 08002, USA (e-mail: Donald.J.Bucci.Jr@lmco.com).
Y. Liang is with the Department of Electrical and Computer Engineering, The Ohio State University, Columbus, OH 43210,
USA (e-mail: liang.889@osu.edu).

2

I. I NTRODUCTION
Information theory was largely developed in the context of communication systems, where information
theoretic tools play an important role in the performance limits of such systems. However, another
important area where information theoretic approach has proved useful is in statistical inference, e.g.,
hypothesis testing. For parametric hypothesis testing problems, information theoretic tools such as joint
typicality, the equipartition property, and Sanov’s theorem have been developed to characterize the error
exponent [1]–[3]. Information theory has also been applied to investigate a class of parametric hypothesis
testing problems [4], [5], where correlated data samples are observed over multiple terminals and data
compression needs to be carried out in a decentralized manner. Additionally, information theory has also
been applied to solve nonparametric hypothesis testing problems under the Neyman-Pearson framework
[6], [7].
In this paper, we apply information theoretic tools to study the nonparametric hypothesis testing
problem, but with a focus on the average error probability instead of the Neyman-Pearson formulation.
We address a more general scenario, where each hypothesis corresponds to a cluster of distributions. Such
a nonparametric problem has not been quite explored in the literature yet. We develop two nonparametric
tests based respectively on the maximum mean discrepancy (MMD) and the Kolmogorov-Smirnov (KS)
distances, and characterize the exponential error decay rate for these tests. Such an analysis has not been
established in the literature before for the nonparametric hypothesis testing problem of interest here.
Furthermore, in contrast to previous works where the number of hypotheses is assumed to be fixed, we
study the regime where the number of hypotheses scales along with the sample size. This is analogous to
the information theoretic channel coding problem where the number of messages scales along with the
codeword length. Hence, in our study, information theory not only provides a technical tool to analyze the
performance, but also provides an asymptotic perspective to understand nonparametric hypothesis testing
problems in the regime where the number of hypotheses is large, i.e., in the large-hypothesis regime.
More specifically, this paper assumes that there are M hypotheses, each corresponding to a (cluster
of) distributions, which are unknown. Sequences of length-n training data samples generated by each
distribution are available. Suppose a length-n test data stream is observed, which are samples generated
by one of these distributions. The goal is to determine which cluster contains the distribution that generated
the observed test sequence. We are interested in the large-hypothesis regime, in which M = 2nD , i.e.,
the number of hypotheses scales exponentially in the number of samples with a constant rate D. As
an analogy to the channel coding problem [1] in which the exponent represents the transmission rate

3

(i.e., the transmission bits per channel use), here D represents the number of hypothesis bits that can be
distinguished per observation sample. Correspondingly, we refer to D as the discrimination rate, and the
largest such value is referred to the discrimination capacity that provides the fundamental performance
limit for the hypothesis testing problem in the large-hypothesis and large-sample regime.
A. Main Contributions
This paper makes the following major contributions.
•

We provide an asymptotic viewpoint to understand the nonparametric hypothesis testing problem
in the regime where the number of hypotheses scales exponentially in the sample size. Based on
its connection to the information theoretic channel coding problem, we introduce the notions of the
discrimination rate and the discrimination capacity as the performance metrics in such asymptotic
regime.

•

We develop two nonparametric approaches to solve the hypothesis testing problem that are based
respectively on the maximum mean discrepancy (MMD) and the Kolmogorov-Smirnov (KS) distance. For both tests, we derive the corresponding error exponents and the discrimination rates.
Our results show that as long as the number M of hypotheses does not scale too fast, i.e., the
scaling (discrimination) exponent is less than a certain threshold, the derived tests are exponentially
consistent, i.e., the error probability converges to zero exponentially fast.

•

We also derive an upper bound on the discrimination capacity, which serves as an upper limit beyond
which exponential consistency cannot be guaranteed by any nonparametric composite hypothesis
testing rules.

B. Related Work
M -ary hypothesis testing: For parametric hypothesis testing problems, information theoretic tools

have been developed to characterize the error exponent [1]–[3], and to study a class of distributed
parametric hypothesis testing problems [4], [5]. For sequential multi-hypothesis testing, information
theoretic bounds on the sample size subject to constraints on the error probabilities have been developed
in [8]. A generalization of the classical hypothesis testing problem is studied in [9], where a Bayesian
decision maker is designed to enhance its information about the correct hypothesis. Information theory
has also been applied to study nonparametric hypothesis testing problems with the main focus being
on the Neyman-Pearson formulation [6], [7]. An information-theoretic approach to the problem of a
nonparametric hypothesis test with a Bayesian formulation is presented in [10]; by factorizing dependent

4

variables into mutually independent subsets, it has been shown that the likelihood ratio can be written
as the sum of two sets of Kullback-Leibler divergence (KLD) terms, which is then used to quantify loss
in hypothesis separability. Our study is different from the previous studies on nonparametric hypothesis
testing problems in that we focus on the asymptotic regime where the number of hypotheses scales with
sample size.
Supervised learning: The problem we study here can also be viewed as a supervised learning problem
studied in the machine learning literature. However, the problem formulated here is different from the
traditional supervised learning problem, e.g., [11], where sample points corresponding to the same label
are simply treated as individual samples, and their underlying statistical structure is not exploited in the
design of classification rules. For example, a support vector machine (SVM) is one of the important
classification algorithms for supervised learning, where the distance between samples is measured either
by the Euclidean distance or by a kernel-based distance. Such distances do not exploit the underlying
statistical distributions of data samples. In contrast, our formulation exploits the underlying statistical
structure of data samples and is more robust to missing data, system noise, etc.
A formulation of the supervised learning problem that is similar to our formulation has been studied
previously in [12]. An approach called support measure machine (SMM) was proposed, which exploits
the kernel mean embedding to estimate the distance between probability distributions. In fact, the comparison between SMM and SVM also reflects the differences between our formulation and the traditional
supervised learning problem. However, the study in [12] focused only on the regime with finite and fixed
number of classes, and did not characterize the decay exponent of the error probability, whereas our focus
is mainly on the asymptotic regime with infinite number of classes, and on the scaling behavior of the
number of classes under which the asymptotic small error probability can be guaranteed. Nevertheless, the
kernel-based approach developed in [12] as well as in various other papers [13]–[15] provide important
techniques that we exploit in our study.
Information theory in learning: Quite a few recent studies have applied various notions in information
theory for studying supervised learning problems. A minimax approach for supervised learning, where
the goal is to minimize the worst-case expected loss function over a certain set of probability distributions
was developed in [16]. The designed classification rules are expected to be robust over datasets generated
by any probability distribution in the set. A classification problem, where the observation is obtained
via a linear mapping of a vector input was studied in [17]. The notion of classification capacity was
proposed, which is similar to the discrimination capacity we propose. However, the results in [17] are
derived under the Gaussian model, whereas our formulation assumes no specific distributions and is

5

hence much more general. Furthermore, a parametric setting is implicitly assumed in [17], whereas our
focus is on the nonparametric problem. A supervised learning problem, where the joint distribution of
data sample and label is assumed to be known but with an unknown parameter, was studied in [18]. A
classifier was proposed and the corresponding performance was analyzed. The connection of the problem
to rate-distortion theory was explored. There are several key differences between the work in [18] and our
study. There is no notion of discrimination rate in [18], and the performance is not defined in terms of the
asymptotic classification error probability. Additionally, our study does not assume any joint distribution
of both data sample and its label.
II. P ROBLEM F ORMULATION
In this section, we first describe our composite nonparametric hypothesis model, and then connect it
to the channel coding problem, which motivates several information theory related definitions that we
will use to characterize system performance. For ease of readability, we also give preliminaries on the
parametric hypothesis testing problem.
A. Supervised Learning as Nonparametric Hypothesis Testing
Consider the following nonparametric hypothesis testing problem with composite distributions. Suppose
there are M hypotheses, and each hypothesis corresponds to a set Pm of distributions for m = 1, . . . , M .
For a given distance measure d(p, q) between two probability distributions p and q , we define
d(Pm ) :=

sup

d(pi , pi0 ),

pi ,pi0 ∈Pm

d(Pm , Pm0 ) :=

inf

(1)

pi ∈Pm ,pi0 ∈Pm0

d(pi , pi0 )

for m 6= m0 .

Hence, d(Pm ) represents diameter of the m-th distribution set and d(Pm , Pm0 ) represents the inter-set
distance between mth and m0 th sets.
We assume that
max

m=1,...,M

d(Pm ) < DI ,

min d(Pm , Pm0 ) > DO ,

(2)

m6=m0

DI < DO .

That is, the intra-set distance (diameter) is always smaller than the inter-set distance for the composite
hypothesis testing. We assume that none of the distributions in the sets Pm for m = 1, . . . , M are
known. Instead, for m = 1, . . . , M , we assume that each distribution pm,im ∈ Pm , where im ∈ I1Mm =

6

{1, 2, . . . , Mm } is the index of the distribution, generates one training sequence xm,im consisting of

independently and identically distributed (i.i.d.) samples. We use Xm to denote all training sequences
generated by the distributions in Pm . We assume that a test sequence y is generated by one of the
distributions in one of the sets Pm for m = 1, . . . , M . The goal is to determine which hypothesis that
the test sequence y belongs to, i.e., which set contains the distribution that generated y.
Let δ({Xm }M
m=1 , y) denote a test based on given data. Then, the average probability of error for δ is
defined as
Pe =

M
X


P

δ({Xm }M
m=1 , y)


6= m0 y ∼ pm0 ,j ∈ Pm0

m0 =1

· P (m0 ),

(3)

where P (m0 ) is the a priori probability that y is drawn from the m0 -th set of distributions.
For the above M -ary hypothesis testing problem, we are interested in the regime, in which the number
M of hypotheses scales with the number of samples. In particular, we assume M = 2nD , where the

parameter D captures how fast M scales with n. We refer to D as the discrimination rate.
Definition 1. The discrimination rate D is achievable, if there exists a classification rule δ for the
multi-hypothesis testing problem such that the probability of error converges to zero as the number n of
observation samples converges to infinity.
For a given composite hypothesis testing problem, we define the largest possible discrimination rate,
D, to be the discrimination capacity, and denote it as D̄.

B. Connection to the Channel Coding Problem
We next discuss the connection between the asymptotic regime of the hypothesis testing problem and
the channel coding problem studied in communications, which in fact motivated our definition of the
discrimination rate and the discrimination capacity.
In the channel coding problem (see Figure 1(a)), assume there are M = {1, . . . , 2nR } messages to be
transmitted with equal probability. An encoder maps each message m ∈ M one-to-one onto a length-n
n = {y
codeword ym
m1 , . . . , ymn }, which is transmitted over the channel. The channel maps each input

symbol to an output symbol in a discrete memoryless fashion with the transition probability PX|Y (x|y) for
each channel use, and the corresponding output sequence is given by xn = {x1 , . . . , xn }. A decoder then
estimates the original message as m̂ based on the output sequence. Essentially, in the channel coding

7

(a) An illustration of the channel coding problem.

(b) An illustration of the multiple hypothesis testing problem.

Fig. 1: Illustrations of the channel coding problem and the multiple hypothesis testing problem

n ) given y n ,
problem, there are a total of M possible conditional distributions pm (xn ) = PX|Y (xn |ym
m

where m = 1, . . . , M , and the decoder determines which distribution p∗ ∈ {p1 , . . . , pM } most probably
generated the observed channel output xn .
The decoding process of the channel coding problem described above is a hypothesis testing problem.
Inspired by the channel coding problem, our total number of hypotheses corresponds to the total number
of messages in channel coding, and the discrimination rate D we define corresponds to the communication
rate R in channel coding, which represents the transmitted message bits per coded symbol. By analogy,
the discrimination rate D can be interpreted as the number of class-bits that can be distinguished per
observation sample. Similarly, the discrimination capacity D̄ corresponds to the capacity in channel
coding, and serves as the fundamental testing limit in hypothesis testing problems.
Essentially, Shannon’s channel coding theorem guarantees error-free transmission of an exponentially
increasing number of messages provided that the transmission rate R is less than the channel capacity C .
In other words, Shannon’s theorem implies that codewords {y n } can be designed such that exponentially
increasing number of conditional probability distributions can be distinguished given the channel output.
Here, for the hypothesis testing problem, channel coding motivates us to investigate the following
problems:
•

Which tests distinguish an exponentially increasing number of hypotheses with asymptotically small
error probability based on n observation samples?

•

What are the corresponding discrimination rates?

8

C. Preliminaries on Parametric Hypothesis Testing
The aforementioned questions can be answered for the parametric hypothesis testing problem in the
asymptotic regime based on existing studies, e.g., [1]. We explain this in detail for single distributions
below as preliminary material before we delve into the main focus of this paper on the nonparametric
composite hypothesis testing problem.
Consider the parametric hypothesis testing problem, where there are M = 2nD known distinct distributions p1 , ..., pM corresponding respectively to M hypotheses. Given a test sequence xn consisting of
n i.i.d. samples generated from one of these distributions, the goal is to determine which hypothesis is

true, i.e., which distribution pi generated the test sequence.
We apply the likelihood test given by:
δ(xn ) = arg max PX|Hi (xn )
i

(4)

where the test labels the observed test data as hypothesis i if pi generates xn with the largest probability.
It can be shown [1] that the likelihood test in (4) is equivalently given by
δ(xn ) = arg min DKL (γ(xn )kpi ),
i

(5)

where DKL (·k·) is the KLD between two distributions, and γ(·) is the empirical distribution of the
sequence. It suggests that the testing rule labels the test data as hypothesis i if the empirical distribution
of the test data is closest to pi in terms of KLD.
We next analyze the average error probability of the above testing rule as follows.
nD

2
1 X
Pe =
P (δ(xn ) 6= j|Hj )
M
j=1

=

1
M

2nD
X

P (∃ i 6= j s.t. E1 |Hj )

j=1
nD

2
1 XX
≤
P (E1 |Hj )
M
j=1 i,i6=j

=

1
M

2nD
X

X

exp{−nC(pi , pj )}

j=1 i,i6=j

≤ 2nD−n log e mini,j C(pi ,pj ) ,

(6)

where C(·, ·) denotes the Chernoff distance, and E1 denotes the event that given Hj , the KLD between

9

xn and pj is greater than the KLD between xn and pi for some i 6= j , i.e., for i 6= j ,
DKL (γ(xn )kpi ) < DKL (γ(xn )kpj ).

(7)

Thus, if D ≤ log e mini,j C(pi , pj ), then the error probability is asymptotically small as n goes to infinity,
which proves the following proposition.
Proposition 1. For the parametric multiple hypothesis testing problem, the discrimination rate D is
achievable if
D ≤ log e min C(pi , pj ).
i,j

III. M AIN R ESULTS
In this section, we obtain the performance bounds for the nonparametric hypothesis testing problem,
with two different distance measures, i.e., MMD and KS distance.

A. MMD-Based Test
We construct a nonparametric hypothesis test based on the MMD distance between two distributions
p and q [15] defined as follows

MMD2 (p, q) := kµp − µq kH .

(8)

where µp (·) maps a distribution p into an element in a reproducing kernel Hilbert space (RKHS) associated
with a kernel k(·, ·) as
Z
µp (·) = Ep [k(·, x)] =

k(·, x)dp(x).

(9)

An unbiased estimator of MMD2 [p, q] based on n samples of x and m samples of y , represented
respectively by xn and y m , is given by [15] that
n

n

XX
1
MMD (x , y ) =
k(xi , xj )
n(n − 1)
2

n

m

i=1 j6=i

1
+
m(m − 1)

m X
m
X
i=1 j6=i

n

m

2 XX
k(yi , yj ) −
k(xi , yj ).
nm

(10)

i=1 j=1

We apply the MMD to measure the distance between the test sequence and the training sequences,
and declare the hypothesis of the test sequence to be the same as the training sequence that has the
smallest MMD to the test sequence. The constructed MMD-based nonparametric composite hypothesis

10

test is given by
2
δMMD ({Xm }M
m=1 , y) = arg min MMD (xm,im , y).
m,im

(11)

The following theorem characterizes the average probability of error performance of the proposed
MMD-based test under composite distributions.
Theorem 1. Suppose the MMD-based test in (11) is applied to the nonparametric composite hypothesis
testing problem under assumption (2), where the kernel satisfies 0 ≤ k(x, y) ≤ K for all (x, y). Then,
the average probability of error is upper bounded as


n(DO − DI )2
nD
Pe ≤ 2 exp −
.
96K2
Thus, the achievable discrimination rate is
D=

log e
(DO − DI )2 .
96K2

(12)

Proof: See Appendix A.
Next, we study a special case where each hypothesis is associated with one individual distribution,
i.e., m-th hypothesis is associated with only one distribution pm , m = 1, . . . , M . Then, we have the
following corollary.
Corollary 1. Suppose the MMD-based test is applied to the nonparametric hypothesis testing problem
and each hypothesis is associated with a single distribution, where the kernel satisfies 0 ≤ k(x, y) ≤ K
for all (x, y). Then, the average probability of error under equally probable hypotheses is upper bounded
as
log e

Pe ≤ 2nD−n 96K2 mini,j MMD

4

(pi ,pj )

.

(13)

Thus, the achievable discrimination rate is
D=

log e
min MMD4 (pi , pj ).
96K2 i,j

(14)

Proof: By Theorem 1, we set DI = 0 and DO = mini,j MMD2 (pi , pj ). Therefore, we can bound

11

the probability of error as the number of classes scales according to M = 2nD


n mini,j MMD4 (pi , pj )
Pe ≤ M exp −
96K2
log e

≤ 2nD−n 96K2 mini,j MMD

4

(pi ,pj )

(15)

Then, it is straightforward to obtain the following achievable discrimination rate for the MMD test as
D=

log e
min MMD4 (pi , pj ).
96K2 i,j

(16)

B. Kolmogorov-Smirnov Test
In this section, we construct a nonparametric hypothesis testing test based on the KS distance defined
as follows. Suppose x = {x1 , . . . , xn } is generated by the distribution p. Then the empirical CDF of p
is given by

n

1X
Fx (a) =
1[−∞,a] (xi ) :=
n
i=1

a

Z

dFx ,

(17)

−∞

where 1[−∞,x] is the indicator function. The KS distance between x and y having respectively been
generated by p and q in an i.i.d. fashion is defined as
DKS (x, y) =

|Fx (a) − Fy (a)|.

sup

(18)

a∈{x1 ,...,xn }∪{y1 ,...,yn }

We construct the following KS based nonparametric composite hypothesis test
δKS ({Xm }M
m=1 , y) = arg min DKS (xm,im , y),
m,im

(19)

The following theorem characterizes the performance of the proposed KS-based test.
Theorem 2. Suppose the KS-based test in (19) is applied to the nonparametric hypothesis testing problem
under assumption (2). Then, the average probability of error is upper bounded as
Pe ≤ 6 · 2nD exp −

n(DO − DI )2 
.
8

Thus, the achievable discrimination rate is
D=

Proof: See Appendix B.

log e
(DO − DI )2 .
8

(20)

12

We next consider the case where each hypothesis is associated with a single distribution. Then, we
have the following corollary.
Corollary 2. Suppose the KS-based test is applied to the nonparametric hypothesis testing problem and
each hypothesis is associated with a single distribution. Then, the average probability of error under
equally probable hypotheses is upper bounded as
Pe ≤ 6 · 2nD−n

log e
8

mini,j d2KS (pi ,pj )

(21)

Thus, the achievable discrimination rate is
D=

log e
min d2 (pi , pj ).
8 i,j KS

(22)

Proof: By Theorem 2, we set DI = 0 and DO = mini,j dKS (pi , pj )2 , and have
Pe ≤ 6 · 2nD−

log e
8

≤ 6 · 2nD−n

Do2

log e
8

mini,j d2KS (pi ,pj )

.

Then, it is straightforward to obtain the following achievable discrimination rate for the KS test as
D=

log e
min d2 (pi , pj ).
8 i,j KS

(23)

C. Upper Bound on the Discrimination Capacity
We now develop an upper bound on the discrimination capacity for the composite hypothesis testing
problem using Fano’s inequality. Let h be a random index representing the actual hypothesis that occurs.
We assume that h takes uniform distribution over the M hypotheses, and h0 has the same distribution
as m, but is independent from h. We have the following theorem regarding the upper bound of the
discrimination capacity D̄.
Theorem 3. The discrimination capacity D̄ is upper bounded as given by
D̄ ≤ Eh,h0 DKL (ph kph0 ),

where DKL (·k·) is the KLD between two distributions.
Proof: See Appendix C.

(24)

13

IV. N UMERICAL R ESULTS
In this section, we present numerical results to compare the performance among the proposed tests.
The experiment sets the number of classes to be five, and plots the error probability versus the number
of samples for the proposed algorithms.
0.5

MMD
KS
likelihood, parametric
lower bound

0.4

P

e

0.3

0.2

0.1

0
5

10

15

20

25

30

35

40

45

Sample size per sequence

Fig. 2: Comparison of error probabilities among different algorithms for Gaussian hypotheses with
different means.

0.8

MMD
KS
likelihood, parametric
lower bound

0.7
0.6

Pe

0.5
0.4
0.3
0.2
0.1
5

10

15

20

25

30

35

40

45

Sample size per sequence

Fig. 3: Comparison of error probabilities among different algorithms for Gaussian hypotheses with
different variances.

In the first experiment, all the hypotheses correspond to Gaussian distributions with the same variance
σ 2 = 1 but different mean values µ = {−2, −1, 0, 1, 2}. A training sequence is drawn from each

14

distribution and a test sequence is randomly generated from one of the five distributions. The sample size
of each sequence ranges from 5 to 45. A total of 105 monte carlo runs are conducted. The simulation
results are given in Fig. 2. It can be seen that all the tests give better performance as the sample size
n increases. We can also see that the MMD-based test slightly outperforms the KS-based one. We also

provide the parametric likelihood test as a lower bound for performance comparison. It can be seen that
the performance of the two nonparametric tests are close to the parametric likelihood test even with a
moderate number of samples.
In the second experiment, all the hypotheses correspond to Gaussian distributions with the same
mean µ = 1 but different variance values σ 2 = {0.52 , 12 , 1.52 , 22 , 2.52 }. The simulation results are
given in Fig. 3. In this experiment, the MMD-based test yields the worst performance, which suggests
that this method is not quite suitable when the distributions overlap substantially with each other. The
two simulation results also suggest that none of the three tests performs the best universally over all
distributions.
We now conduct experiments with composite distributions. First, we still use five hypotheses with
Gaussian distributions with variance σ 2 = 1 and different mean values µ = {−2, −1, 0, 1, 2}. For each
hypothesis, we vary the mean values by ±0.1. Thus, within each hypothesis, there are three different
distributions with mean values in {µ−0.1, µ, µ+0.1}. The results are presented in Figure 4. As expected,
the performance improves as the sample size n increases. The two tests perform almost identically, with
the MMD-based test slightly outperforming the KS-based test for small n. Although there is a gap between
the performance of MMD and KS tests and that of the parametric likelihood test, we still observe that
the error decay rates of these tests are still close.
We again vary the variances of the Gaussian distributions as in the second experiment in a similar way.
In particular, the variances in the same class are {(σ − 0.1)2 , σ 2 , (σ + 0.1)2 }, and σ ∈ {0.5, 1, 1.5, 2, 2.5}
. In Figure 5, we observe the performance improvement as the sample size n increases. Different from
the results in the second experiment, the MMD-based test outperforms the KS-based test in the composite
setting.
V. C ONCLUSION
This paper developed a nonparametric composite hypothesis testing problem for arbitrary distributions
based on the maximum mean discrepancy (MMD) and Kolmogorov-Smirnov (KS) distance measure
based tests. We introduced the information theoretic notion of discrimination capacity that was defined
for the regime where the number of hypotheses scales along with the sample size. We also provided

15
0.45

MMD
KS

0.4
0.35
0.3

Pe

0.25
0.2
0.15
0.1
0.05
0
5

10

15

20

25

30

35

40

45

Sample size per sequence

Fig. 4: Comparison of error probabilities among different algorithms for composite Gaussian hypotheses
with different means.
0.75

MMD
KS

0.7

P

e

0.65

0.6

0.55

0.5
5

10

15

20

25

30

35

40

45

Sample size per sequence

Fig. 5: Comparison of error probabilities among different algorithms for composite Gaussian hypotheses
with different variances.

characterization of the corresponding error exponent and the discrimination rate (i.e., a lower bound on
the discrimination capacity). Our framework can been extended to unsupervised learning problems and
similar performance limits can be investigated.
A PPENDIX
A. Proof of Theorem 1
The proof uses the following inequality.

16

Lemma 1 (McDiarmid’s Inequality). Let f : X m → R be a function such that for all i ∈ {1, . . . , m},
there exist ci ≤ ∞ for which
sup

|g(x1 , . . . , xi−1 , x̃, xi+1 , . . . , xm )| ≤ ci ,

(25)

X∈X m ,x̃∈X

where g(x1 , . . . , xi−1 , x̃, xi+1 , . . . , xm ) = f (x1 , . . . , xm ) − f (x1 , . . . , xi−1 , x̃, xi+1 , . . . , xm ). Then for all
probability measure p and every  > 0,
22
PX (f (X) − EX [f (X)] > ) < exp − Pm





2
i=1 ci

,

(26)

where X denotes (x1 , . . . , xm ), EX [·] denotes the expectation over the m random variables xi ∼ p, and
PX denotes the probability over these m variables.

To apply the McDiarmid’s inequality, we first define the following quantity
4m (xα ) = MMD2 (xm,im , y) − MMD2 (xm0 ,im0 , y)

(27)

where xα := {xm,im , xm0 ,im0 , y}consists of 3n data samples.
Given Hi , i.e., the test sequence y is generated by Pm , it can be shown that
E[MMD2 (xm,im , y)] ≤ DI

(28)

E[MMD2 (xm0 ,im0 , y)] ≥ DO .

(29)

and

We next define xα−s the same as xα except that the s-th component xαs is removed. We also define x̃αs
as another sequence generated by the same underlying distribution for xαs . Then, xαs affects 4m (xα ) via
the following three cases.
•

Case 1: xαs is in the sequence xm,im . In this case, xαs affects 4m (xα ) through the following terms
n
n
X
2 X
2
α
k(xs , xim l ) − 2
k(xαs , yl ).
n(n − 1)
n
l=1,l6=s

•

(30)

l=1

Case 2: xαs is in the sequence xnj . In this case, xαs affects 4m (xα ) through the following terms
−

n
n
X
2
2 X
k(xαs , xjl ) + 2
k(xαs , yl ).
n(n − 1)
n
l=1,l6=s

j=1

(31)

17

•

Case 3: xαs is in the sequence xn . In this case, xαs affects 4m (xα ) through the following terms
n
n
2 X
2 X
α
k(xs , xil ) + 2
k(xαs , xjl ).
− 2
n
n
l=1

(32)

l=1

Thus, since the kernel is bounded, i.e., 0 ≤ k(x; y) ≤ K for any (x, y), considering the above three
cases, the variation in the value of 4m (xα ) is bounded by

4K
n

when xαs varies. Then, we can obtain the

following bound
| 4m (xα−s , xαs ) − 4m (xα−s , x̃αs )| ≤

8K
.
n

(33)

Assuming the test sequence is generated from the true underlying set of distributions, Pm , we now apply
Lemma 1 and obtain the following bound on the probability of error between two classes

P MMD2 (xm,im , y) ≥ MMD2 (xm0 ,im0 , y)
= P (MMD2 (xm,im , y) − MMD2 (xm0 ,im0 , y) ≥ 0)
= P (4m (xα ) − E[4m (xα )] ≥ −E[4m (xα )])
≤ P (4m (xα ) − E[4m (xα )] ≥ DO − DI )
!
2(DO − DI )2
≤ exp −
2
3n 64K
n2


n(DO − DI )2
= exp −
.
96K2

(34)

The first inequality is based on the results in (28) and (29) that
−E[4m (xα )] ≥ DO − DI .

(35)

Therefore, we can bound the probability of error as


M0
Pe = P ∃m0 6= m, i0m ∈ I1 m , 4m (xα ) ≥ 0, ∀im ∈ I1Mm


M
1 X X
n(DO − DI )2
min exp −
≤
M
96K2
i ∈I Mm
m=1 m0 6=m m 1


n(DO − DI )2
≤ M exp −
.
96K2

(36)

18

Thus, the achievable discrimination rate is
D=

log e
(DO − DI )2 .
96K2

(37)

B. Proof of Theorem 2
We first introduce two lemmas to help establish the theorem.
Lemma 2. [19] Suppose x is generated by p and Fx (a) is the corresponding empirical c.d.f.. Then



P sup Fx (a) − Fp (a) >  ≤ 2 exp − 2n2 .
a∈R

Lemma 3. Suppose two distribution clusters P1 and P2 satisfy (2). Assume that for j = 1, 2, xj ∼ pj
satisfying pj ∈ Pj . Then for any x3 ∼ p3 satisfying p3 ∈ P1 ,


n(Do − DI )2 
.
P dKS (x1 , x3 ) ≥ dKS (x2 , x3 ) ≤ 6 exp −
8
Proof: By the triangle inequality and the property of supremum, we have
dKS (x1 , x3 ) < dKS (p1 , x1 ) + d1 + dKS (p3 , x3 ),
dKS (x2 , x3 ) > −dKS (p3 , x3 ) + d2 − dKS (p2 , x2 ).

where DI < d1 < d2 < Do . Then


P dKS (x1 , x3 ) ≥ dKS (x2 , x3 )


ˆ
≤ P dKS (p1 , x1 ) + dKS (p3 , x3 ) + 2dKS (p2 , x2 ) > d



dˆ
dˆ
≤ P dKS (p1 , x1 ) >
+ P dKS (p3 , x3 ) >
4
4


dˆ
+ P dKS (p2 , x2 ) >
4
ndˆ2 
≤ 6 exp −
.
8


where dˆ = d2 − d1 . By the continuity of the exponential function, we have


n(Do − DI )2 
P dKS (x1 , x3 ) ≥ dKS (x2 , x3 ) ≤ 6 exp −
.
8

Without loss of generality, assume that the probability that y is generated from pk,ik is

1
M

for all

19

m ∈ {1, . . . , M } and im ∈ {1, . . . , Mm }. By Lemma 3 and the union bound, the probability of error is

bounded by
Pe ≤

Mm X M
M X
m0
X
X


P dKS (xm,im , y) ≥

m=1 im =1 m0 6=m im0 =1


dKS (xm0 ,im0 , y) y ∼ pm,im , im ∈ {1, . . . , Mm }
≤ 6M exp −

1
M

n(Do − DI )2 
.
8

Thus, the achievable discrimination rate is
D=

log e
(DO − DI )2 .
8

(38)

C. Proof of Theorem 3
By Fano’s inequality [1], we obtain
H(h|y) ≤ 1 + Pe log(M − 1).

(39)

Since h is uniformly distributed over all the hypotheses, we have that
log(M ) = H(h) = I(h; y) + H(h|y)
≤ I(h; y) + 1 + Pe log M.

(40)

Let Ph (h), Py (y), and Ph,y (h, y) represent the marginal and joint distributions of h and y. Recall that
we represent the likelihood function of y under m as P (y|h) = ph (y). The mutual information between

20

h and y can be expressed in terms of likelihood functions as
I(h; y) =

M X
X

Ph,y (h, y) log

h=1 y

=

Ph,y (h, y)
Ph (h)Py (y)

M
1 XX
ph (y)
ph (y) log
M
P
y (y)
y
h=1

M
1 XX
ph (y)
=
ph (y) log PM 1
M
ph0 (y)
h0 =1
y
M

h=1

=

M X
X

1
M
h=1
"

ph (y)

y

#
M
X
1
ph0 (y)
· log pm (y) − log
M
0

(41)

m =1

Applying Jensen’s inequality, the mutual information can be further upper bounded as
M

I(h; y) ≤

1 XX
ph (y)
M
y
h=1
"
#
M
X
1
· log ph (y) −
log ph0 (y)
M
0

(42)

h =1

Simplifying, we finally have
M

I(h; y) ≤

1 XX
ph (y)
M
y
h=1
#
" M
M
X
X 1
1
log ph (y) −
log ph0 (y)
·
M
M
0
0
h =1

h =1

=

=

1 1
MM

M X
M
X

X

ph (y) log

h=1 h0 =1 y

ph (y)
ph0 (y)

M M
1 1 XX
nDKL (ph kph0 )
MM
0
h=1 h =1

=nEh,h0 DKL (ph kph0 ).

(43)

where m0 has the same distribution as m, but is independent from m. Substituting (43) into the (40), we
obtain
log M ≤ nEh,h0 DKL (ph kph0 ) + 1 + log M Pe

(44)

21

which implies that
Eh,h0 DKL (ph kph0 )
1
log M
+
≤
.
n
1 − Pe
n(1 − Pe )

(45)

Since M = 2nD and the above right-hand side is independent on D, we can have
D≤

Em,m0 DKL (pm kpm0 )
1
+
.
1 − Pe
n(1 − Pe )

(46)

Thus, for any test that satisfies Pe → 0 as n → ∞, D ≤ Em,m0 DKL (pm kpm0 ) as n → ∞. Therefore,
the discrimination capacity D̄ is upper bounded by
D̄ ≤ Em,m0 DKL (pm kpm0 ).

(47)

R EFERENCES
[1] T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd Edition.
[2] R. G. Gallager, Information Theory and Reliable Communication.

New York: Wiley, 2006.

New York: Wiley, 1968.

[3] I. Csiszár and J. Körner, Information Theory: Coding Theorems for Discrete Memoryless Systems.

Akadémiai Kiadó:

Budapest, 1981.
[4] T. S. Han, “Hypothesis testing with multiterminal data compression,” IEEE Trans. Information Theory, vol. 33, no. 11,
pp. 759–772, Nov. 1987.
[5] T. S. Han and S. I. Amari, “Statistical inference under multiterminal data compression,” IEEE Trans. Information Theory,
vol. 44, no. 10, pp. 2300–2324, Oct. 2002.
[6] M. Gutman, “Asymptotically optimal classification for multiple tests with empirically observed statistics,” IEEE Trans.
Information Theory, vol. 35, no. 2, pp. 401–408, Feb. 1989.
[7] E. Levitan and N. Merhav, “A competitive neyman-pearson approach to universal hypothesis testing with applications,”
IEEE Trans. Information Theory, vol. 48, no. 8, pp. 2215–2229, Aug. 2002.
[8] T. L. Lai, “Sequential multiple hypothesis testing and efficient fault detection-isolation in stochastic systems,” IEEE
Transactions on Information Theory, vol. 46, no. 2, pp. 595–608, Mar 2000.
[9] M. Naghshvar and T. Javidi, “Sequentiality and adaptivity gains in active hypothesis testing,” IEEE Journal of Selected
Topics in Signal Processing, vol. 7, no. 5, pp. 768–782, Oct 2013.
[10] A. T. Ihler, J. W. Fisher, and A. S. Willsky, “Nonparametric hypothesis tests for statistical dependency,” IEEE Transactions
on Signal Processing, vol. 52, no. 8, pp. 2234–2249, Aug 2004.
[11] C. M. Bishop, Pattern Recognition and Machine Learning.

New York: Springer, 2006.

[12] K. Muandet, K. Fukumizu, F. Dinuzzo, and B. Scholkopf, “Learning from distributions via support measure machines,” in
Proc. Advances in Neural Information Processing Systems (NIPS), 2012.
[13] B. Sriperumbudur, A. Gretton, K. Fukumizu, G. Lanckriet, and B. Schölkopf, “Injective Hilbert space embeddings of
probability measures,” in Proc. Annual Conference on Learning Theory (COLT), 2008.
[14] K. Fukumizu, B. Sriperumbudur, A. Gretton, and B. Schölkopf, “Characteristic kernels on groups and semigroups,” in
Proc. Advances in Neural Information Processing Systems (NIPS), 2009.

22

[15] A. Gretton, K. Borgwardt, M. Rasch, B. Schölkopf, and A. Smola, “A kernel two-sample test,” J. Mach. Learn. Res.,
vol. 13, pp. 723–773, 2012.
[16] F. Farnia and D. Tse, “A minimax approach to supervised learning,” in Proc. Advances in Neural Information Processing
Systems (NIPS), 2016.
[17] M. Nokleby, M. Rodrigues, and R. Calderbank, “Discrimination on the Grassmann manifold: Fundamental limits of
subspace classifiers,” in Proc. IEEE Int. Symp. Information Theory (ISIT), 2014.
[18] M. Nokleby, A. Beirami, and R. Calderbank, “Rate-distortion bounds on bayes risk in supervised learning,” in Proc. IEEE
Int. Symp. Information Theory (ISIT), 2016.
[19] P. Massart, “The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality,” The Ann. of Probability, vol. 18, pp. 1269–
1283, 1990.

