# Kernel Robust Hypothesis Testing

Zhongchang Sun Shaofeng Zou  This paper was presented in part at the 2021 IEEE
International Symposium on Information Theory [1].Zhongchang Sun and Shaofeng
Zou are with the Department of Electrical Engineering, University at Buffalo,
Buffalo, NY 14228 USA (e-mail<EMAIL_ADDRESS>szou3@buffalo.edu).

###### Abstract

The problem of robust hypothesis testing is studied, where under the null and
the alternative hypotheses, the data-generating distributions are assumed to
be in some uncertainty sets, and the goal is to design a test that performs
well under the worst-case distributions over the uncertainty sets. In this
paper, uncertainty sets are constructed in a data-driven manner using kernel
method, i.e., they are centered around empirical distributions of training
samples from the null and alternative hypotheses, respectively; and are
constrained via the distance between kernel mean embeddings of distributions
in the reproducing kernel Hilbert space, i.e., maximum mean discrepancy (MMD).
The Bayesian setting and the Neyman-Pearson setting are investigated. For the
Bayesian setting where the goal is to minimize the worst-case error
probability, an optimal test is firstly obtained when the alphabet is finite.
When the alphabet is infinite, a tractable approximation is proposed to
quantify the worst-case average error probability, and a kernel smoothing
method is further applied to design test that generalizes to unseen samples. A
direct robust kernel test is also proposed and proved to be exponentially
consistent. For the Neyman-Pearson setting, where the goal is to minimize the
worst-case probability of miss detection subject to a constraint on the worst-
case probability of false alarm, an efficient robust kernel test is proposed
and is shown to be asymptotically optimal. Numerical results are provided to
demonstrate the performance of the proposed robust tests.

##  I Introduction

Hypothesis testing is a fundamental problem in statistical inference where the
goal is to distinguish among different hypotheses with a small probability of
error [2, 3, 4]. The likelihood ratio test is known to be optimal under
different settings, e.g., the Neyman-Pearson setting and the Bayesian setting
[2, 4]. For example, for binary hypothesis testing, we compare the likelihood
ratio between the two hypotheses with a pre-specified threshold to make the
decision. Therefore, the data-generating distributions under different
hypotheses are needed. In practice, these distributions are usually estimated
from historical data or designed using domain knowledge, and thus may deviate
from the true data-generating distributions. When the distributions applied in
the likelihood ratio test deviate from the true data-generating distributions,
the performance of the test may degrade significantly. To address this
problem, the approach of robust hypothesis testing is proposed, e.g., [5, 6,
7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20], where uncertainty sets
are introduced to model the uncertainty in the underlying distributions.
Generally, the uncertainty sets are constructed as collections of
distributions that lie in the neighborhood of nominal distributions based on
some distance measure. The goal is to design a test that performs well under
the worst-case distributions over the uncertainty sets.

The robust hypothesis testing problem has been widely studied and various ways
of constructing uncertainty sets have been introduced (see, e.g., [20, 7] for
a review). The $\epsilon$-contamination uncertainty sets and the total
variation uncertainty sets were investigated in [5] and a censored likelihood
ratio test was constructed and shown to be minimax optimal. The problem with
uncertainty sets defined via the Kullback-Leibler (KL) divergence was
investigated in [6, 7]. The least-favorable distributions (LFDs) were
identified under some conditions, and the robust likelihood ratio test based
on the LFDs were constructed. In [11], the robust hypothesis testing problem
under the Bernoulli distribution was investigated. In [12], the uncertainty
sets were constructed via distortion constraints. In those works, nominal
distributions are usually estimated from historical data. However, when it
comes to the high-dimensional data, which is common in the big data era, it is
in general difficult to obtain an accurate estimate of the data-generating
distributions. Existing studies are mostly limited to the 1-dimensional case,
and a generalization to high-dimensional data, e.g., finding the LFDs, is
still an open problem in the literature.

In this paper, we employ a data-driven approach [8, 9] to construct the
nominal distributions, and extend the robust hypothesis testing problem to the
high-dimensional setting. Specifically, a number of training samples are
available from the null and alternative hypotheses, respectively, and their
empirical distributions are used as the nominal distributions to design the
uncertainty sets. We note that in this case, the uncertainty sets defined via
the KL divergence [6, 7] are not applicable, since such uncertainty sets only
contain distributions supported on the training samples, which may be
problematic if the alphabet is actually infinite.

In [8, 9], the robust hypothesis testing problem was investigated where
uncertainty sets are centered around empirical distributions via the
Wasserstein distance. In [8], the original 0-1 loss, i.e., the error
probability, was firstly smoothed. Then, this relaxed formulation can be
solved efficiently, and the LFDs and the nearly-optimal robust detector were
identified. In [9], the minimax problem with the 0-1 loss, i.e., the exact
probability of error, was considered, where a computationally tractable
reformulation and the optimal robust test were characterized. In [10], the
data-driven robust hypothesis testing problem with the Sinkhorn divergence,
which is a variant of Wasserstein distance with entropic regularization, was
studied. The original 0-1 loss, i.e., the error probability, was smoothed as
in [8]. Then, a finite-dimensional convex optimization problem was proposed to
approximate the smoothed problem. The solutions were further used to
approximate the LFDs, and design the robust test. However, Wasserstein
distance based approach has certain drawbacks. First, the Wasserstein distance
between the empirical distribution with $m$ samples and its data-generating
distribution is bounded by $\mathcal{O}(m^{-1/d})$ [21], which depends on the
dimension $d$ of the data. Therefore, when choosing radii of uncertainty sets
to guarantee that the true data-generating distributions lie in the
uncertainty sets with high probability, it is too pessimistic when $d$ is
large. Moreover, coefficients in such a concentration bound depend on the true
distribution which is unknown, and thus makes it difficult to use in practice.
Second, Wasserstein distance is computationally expensive, especially in the
high-dimensional setting.

Moment information, such as mean and variance, is usually used to measure the
difference between distributions. In [22], the uncertainty sets are
constructed using moment classes, where a finite alphabet was considered, and
an asymptotically optimal test was designed. Specifically, the moment
uncertainty sets in [22] are defined as $\\{P:E_{P}[f]\leq\theta\\}$, where
$f$ is a real-valued function, $E_{P}[f]$ denotes the expectation of $f$ under
$P$, and $\theta$ is a constant. In this paper, we generalize the moment
classes to the reproducing kernel Hilbert space (RKHS) [23, 24, 25] and
construct uncertainty sets using the maximum mean discrepancy (MMD).
Specifically, let $f=g-E_{\hat{P}}[g]$, where $\hat{P}$ is the empirical
distribution of samples from $P$, $g$ is any function in the RKHS. We then
consider the worst-case and take the supremum of $g$ with bounded norm over
the RKHS. This leads to uncertainty sets centered at $\hat{P}$ and defined by
MMD (see more details in Section II). Compared with the Wasserstein distance,
the kernel MMD between the empirical distribution with $m$ samples and its
data-generating distribution can be bounded by $\mathcal{O}(1/\sqrt{m})$ [26,
27], which is dimension-free and also this bound does not depend on the data-
generating distribution. This makes it much easier to choose the radii of the
uncertainty sets. Moreover, the kernel MMD is computationally efficient to
evaluate.

The MMD-based test statistic has been widely used in statistical signal
processing and machine learning. For the one-sample testing problem, where the
goal is to distinguish if a sequence of samples come from a certain
distribution, and the two-sample testing problem, where the goal is to
distinguish if two sequences of samples come from the same distribution, the
MMD-based methods and some variants are proposed in [28, 29, 30, 31, 32, 33,
34, 35, 36]. In [37] and [38], MMD-based tests are proposed to detect
anomalous data streams and anomalous network structures, respectively, where
the anomalous samples generated from a different distribution from the normal
samples. In [39], an MMD-based M-statistic is proposed for data-driven
quickest change detection. In our paper, we apply MMD to design robust tests
which perform well under the worst-case distributions over the uncertainty
sets.

###  I-A Main Contributions

In this paper, we develop a data-driven approach with the kernel method to
design uncertainty sets for the problem of robust hypothesis testing.
Specifically, empirical distributions are used directly as the nominal
distributions, which avoids the estimation error when fitting the data into a
parametric family of distributions. We then use the kernel MMD as the distance
metric, which can be viewed as a generalization of the moment classes [22].
The advantage of the kernel method is that it scales well for high-dimensional
data, and choosing radii of the uncertainty set does not require the knowledge
of the underlying true distribution. More importantly, our designed
uncertainty sets contain continuous distributions (not only distributions
supported on the training data), and our robust kernel test generalizes with
guaranteed out-of-sample performance.

We first focus on the Bayesian setting where the goal is to minimize the
worst-case error probability. We first study the case with a finite alphabet,
and reformulate the original problem equivalently to a finite-dimensional
convex optimization problem via the strong duality of kernel robust
optimization [40] and then derive the optimal robust test. For the case with
an infinite alphabet, we propose a tractable approximation to quantify the
worst-case error probability. The basic idea is to generate a finite number of
samples randomly, and reduce the uncertainty set to be supported on these
samples. We then rewrite equivalently the original problem as a convex
optimization problem, and approximate the original objective function value
using the approximated uncertainty set supported on these randomly generated
samples. This approximation is tractable since it is a finite-dimensional
convex optimization, and it builds connection between the finite-alphabet case
and the infinite-alphabet case. We then show that the solutions to the
approximation converge almost surely to the solutions to the original
infinite-alphabet problem as the number of randomly generated samples goes to
infinity. The LFDs (for the approximation) can be recovered, which are also
supported on these randomly generated samples. To generalize to unseen data,
we further apply the kernel smoothing method on the LFDs, and design a robust
test that is the likelihood ratio test between the smoothed LFDs. We also
propose a direct robust kernel test that is computationally efficient, and
show that it is exponentially consistent. The basic idea is to compare the
closest MMD distance between the empirical distribution of samples and the two
uncertainty sets.

We then study the Neyman-Pearson setting, where the goal is to minimize the
worst-case probability of miss detection subject to a constraint on the worst-
case probability of false alarm. We first develop the universal upper bound on
the error exponent of miss detection under the Neyman-Pearson setting. The
analysis is based on a generalization of the Chernoff-Stein lemma [3, 41].
This upper bound also applies to robust hypothesis testing problems with other
uncertainty sets. We then design a novel robust kernel test, which is to
compare the closest distance between the empirical distribution of the test
samples and the uncertainty set with a threshold. We further demonstrate that
it is asymptotically optimal under the Neyman-Pearson setting. Our proposed
robust kernel test does not need to solve for the LFDs, which might be
computationally intractable in practice. We also show that our test can be
implemented efficiently with a quadratic complexity in the number of samples.

###  I-B Paper Organization

In Section II, we present the preliminaries on MMD and the problem
formulation. In Section III, we focus the Bayesian setting, and derive the
optimal test for the case with a finite alphabet. For the case with an
infinite alphabet, we provide a tractable approximation to quantify the worst-
case error probability and propose a kernel smoothing robust test. We also
propose an exponentially consistent direct robust kernel test. In Section IV,
we study the robust hypothesis testing under the Neyman-Pearson setting, and
propose an asymptotically optimal robust kernel test. In Section V, we provide
numerical results to validate our theoretical analysis. In Section VI, we
present some concluding remarks.

##  II Preliminaries and Problem Formulation

Let $\mathcal{X}\subset\mathbb{R}^{d}$ be a compact set where samples are
taken from. Denote by $\mathcal{P}$ the set of all probability measures on
$\mathcal{X}$.

###  II-A Maximum Mean Discrepancy (MMD)

We first give a brief introduction to the kernel mean embedding and the MMD
[23, 24]. Let $\mathcal{H}$ denote the RKHS associated with a kernel
$k(\cdot,\cdot):\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}$.
Specifically, $k(x,\cdot)$ denotes the feature map:
$\mathcal{X}\rightarrow\mathcal{H}$, and $k(x,y)=\langle
k(x,\cdot),k(y,\cdot)\rangle_{\mathcal{H}}$ defines an inner product on
$\mathcal{H}$. In this paper, we consider the bounded kernel: $0\leq
k(x,x^{\prime})\leq K$, $\forall x,x^{\prime}\in\mathcal{X}$, where $K>0$ is
some positive constant. The kernel mean embedding of a distribution is a
mapping from $\mathcal{P}$ to $\mathcal{H}$ defined as $\mu_{P}=\int
k(x,\cdot)dP$. Let $E_{P}[f]$ denote the expectation of a function
$f\in\mathcal{H}$. Denote by $\|\cdot\|_{\mathcal{H}}$ the norm on
$\mathcal{H}$. Define the MMD between two distributions $P_{0}$ and $P_{1}$
as:

$\displaystyle
d_{\text{MMD}}(P_{0},P_{1})=\sup_{f\in\mathcal{H}:\|f\|_{\mathcal{H}}\leq
1}E_{P_{0}}[f(x)]-E_{P_{1}}[f(x)].$ (1)

With the reproducing property of the RKHS, we have that $E_{P}[f]=\langle
f,\mu_{P}\rangle_{\mathcal{H}}$. The MMD between $P_{0}$ and $P_{1}$ can be
equivalently written as the distance between $\mu_{P_{0}}$ and $\mu_{P_{1}}$
in the RKHS [25]:

$\displaystyle
d_{\text{MMD}}(P_{0},P_{1})=\big{\|}\mu_{P_{0}}-\mu_{P_{1}}\big{\|}_{\mathcal{H}}$
$\displaystyle=\Big{(}E_{x\sim P_{0},x^{\prime}\sim
P_{0}}[k(x,x^{\prime})]+E_{y\sim P_{1},y^{\prime}\sim
P_{1}}[k(y,y^{\prime})]-2E_{x\sim P_{0},y\sim P_{1}}[k(x,y)]\Big{)}^{1/2}.$
(2)

Given samples $x^{n}=(x_{1},x_{2},\cdots,x_{n})\sim P_{0}$ and
$y^{m}=(y_{1},y_{2},\cdots,y_{m})\sim P_{1}$, an unbiased estimate of the
squared MMD between $P_{0}$ and $P_{1}$ is

$\displaystyle\hat{d^{2}}_{\text{MMD}}(P_{0},P_{1})=\frac{1}{n(n-1)}\sum_{i=1}^{n}\sum_{j\neq
i}k(x_{i},x_{j})+\frac{1}{m(m-1)}\sum_{i=1}^{m}\sum_{j\neq
i}k(y_{i},y_{j})-\frac{2}{nm}\sum_{i=1}^{n}\sum_{j=1}^{m}k(x_{i},y_{j}).$ (3)

If a kernel $k$ is characteristic [42], the kernel mean embedding is
injective, and then $d_{\text{MMD}}(\cdot,\cdot)$ is a metric on $\mathcal{P}$
[25, 43]. In this paper, we consider kernels such that the weak convergence on
$\mathcal{P}$ is metrized by MMD [44, 45], e.g., Gaussian kernels and
Laplacian kernels.

###  II-B Problem Setup

Let $\mathcal{P}_{0},\mathcal{P}_{1}\subseteq\mathcal{P}$ denote the
uncertainty sets under the null and alternative hypotheses, respectively. We
propose a data-driven approach to construct the uncertainty sets. Instead of
fitting nominal probability distributions in a parametric form, we have two
sequence of training samples:
$\hat{x}_{0}^{m}=(\hat{x}_{0,1},\hat{x}_{0,2},\cdots,\hat{x}_{0,m})$ and
$\hat{x}^{m}_{1}=(\hat{x}_{1,1},\hat{x}_{1,2},\cdots,\hat{x}_{1,m})$ from the
two hypotheses, respectively. Let
$\hat{Q}^{l}_{m}=\frac{1}{m}\sum_{i=1}^{m}\delta_{\hat{x}_{l,i}},$ be the
empirical distribution of $\hat{x}^{m}_{l}$, $l=0,1$, where
$\delta_{\hat{x}_{l,i}}$ denotes the Dirac measure on $\hat{x}_{l,i}$. The
nominal distributions are then the empirical distributions of data from the
two hypotheses, respectively. The uncertainty sets
$\mathcal{P}_{0},\mathcal{P}_{1}$ are defined via the MMD:

$\displaystyle\mathcal{P}_{l}=\Big{\\{}P\in\mathcal{P}:d_{\text{MMD}}(P,\hat{Q}^{l}_{m})\leq\theta\Big{\\}},\
l=0,1,$ (4)

where $\theta$ is the pre-specified radius of the uncertainty sets, and shall
be chosen to guarantee that the population distribution falls into the
uncertainty sets with high probability. It is assumed that
$\mathcal{P}_{0},\mathcal{P}_{1}$ do not overlap, i.e.,
$\theta<\frac{\|\mu_{\hat{Q}^{1}_{m}}-\mu_{\hat{Q}^{0}_{m}}\|_{\mathcal{H}}}{2}$.
Otherwise, the problem is trivial.

In [22], the moment class is defined as
$\\{P\in\mathcal{P}:E_{P}[f]\leq\theta\\}$, where $f$ is real-value function
on $\mathcal{X}$. In the definition of moment class, if we let
$f=g-E_{\hat{Q}_{m}^{l}}[g]$ and take the supremum over $g$ with
$\|g\|_{\mathcal{H}}\leq 1$ in the RKHS, it is then the MMD between $P$ and
$\hat{Q}_{m}^{l}$. Therefore, the MMD uncertainty sets can be viewed as a
generalization of moment classes to the RKHS.

In this paper, we focus on the robust hypothesis testing problem with MMD
uncertainty sets under the Bayesian setting and the Neyman-Pearson setting.

1) Bayesian Setting. Given a sample $x$ following an unknown distribution $Q$,
the goal is to distinguish between the null hypothesis
$H_{0}:Q\in\mathcal{P}_{0}$ and the alternative hypothesis
$H_{1}:Q\in\mathcal{P}_{1}$. For a randomized test
$\phi:\mathcal{X}\rightarrow[0,1]$, it accepts the null hypothesis $H_{0}$
with probability $1-\phi(x)$ and accepts the alternative hypothesis $H_{1}$
with probability $\phi(x)$. Let

$\displaystyle
P_{F}(\phi)\triangleq\sup_{P_{0}\in\mathcal{P}_{0}}E_{P_{0}}[\phi(x)],$
$\displaystyle
P_{M}(\phi)\triangleq\sup_{P_{1}\in\mathcal{P}_{1}}E_{P_{1}}[1-\phi(x)]$ (5)

denote the worst-case probability of false alarm (type-I error probability)
and the worst-case probability of miss detection (type-II error probability)
for the test $\phi$.

For the simple hypothesis testing with equal priors on the two hypotheses, the
error probability in the Bayesian setting is given by

$\displaystyle P_{E}(\phi)$
$\displaystyle\triangleq\frac{1}{2}E_{P_{0}}[\phi(x)]+\frac{1}{2}E_{P_{1}}[1-\phi(x)]$
$\displaystyle=\frac{1}{2}\int\phi(x)dP_{0}(x)+\frac{1}{2}\int\big{(}1-\phi(x)\big{)}dP_{1}(x),$
(6)

where $P_{0}$ and $P_{1}$ denote the distributions under the null and
alternative hypotheses, respectively. For the Bayesian robust hypothesis
testing, the goal is to solve the following problem:

$\displaystyle\inf_{\phi}\sup_{P_{0}\in\mathcal{P}_{0},P_{1}\in\mathcal{P}_{1}}P_{E}(\phi).$
(7)

The results in this paper can be easily generalized to the case with non-equal
priors.

Denote a sequence of independent and identically distributed (i.i.d.) samples
by $x^{n}=(x_{1},x_{2},\cdots,x_{n})$. The worst-case type-I error exponent
$e_{F}$ and the worst-case type-II error exponent $e_{M}$ are defined as
follows:

$\displaystyle
e_{F}(\phi)=\inf_{P_{0}\in\mathcal{P}_{0}}\lim_{n\rightarrow\infty}-\frac{1}{n}\log
E_{P_{0}}[\phi(x^{n})],$ $\displaystyle
e_{M}(\phi)=\inf_{P_{1}\in\mathcal{P}_{1}}\lim_{n\rightarrow\infty}-\frac{1}{n}\log
E_{P_{1}}[1-\phi(x^{n})].$ (8)

######  Definition 1.

A test $\phi$ is said to be exponentially consistent if $e_{F}(\phi)>0$ and
$e_{M}(\phi)>0$.

2) Neyman-Pearson Setting. In this paper, we focus on the asymptotic Neyman-
Pearson setting, where the goal is to solve the following problem:

$\displaystyle\sup_{\phi:P_{F}(\phi)\leq\alpha}\inf_{P_{1}\in\mathcal{P}_{1}}\lim_{n\rightarrow\infty}-\frac{1}{n}\log
E_{P_{1}}[1-\phi(x^{n})],$ (9)

where $\alpha\in(0,1]$ is a pre-specified constraint on the worst-case false
alarm probability. Specifically, among the tests that satisfy the false alarm
constraint $P_{F}(\phi)\leq\alpha$, we aim to find one that maximizes the
worst-case type-II error exponent.

In this paper, any distributions $P_{0},P_{1}$ are assumed to admit
probability density functions (PDFs) $p_{0},p_{1}$, since we can always choose
a reference measure $\mu$ such that both $P_{0}$ and $P_{1}$ are absolutely
continuous with respect to $\mu$. In general, $\mu$ can be chosen as
$\mu=P_{0}+P_{1}$. For the continuous distributions and the discrete
distributions, $\mu$ can be chosen as the Lebesgue measure and the counting
measure, respectively.

##  III Robust Hypothesis Testing Under Bayesian Setting

In this section, we focus on the Bayesian setting. We aim to solve the minimax
problem for the average probability of error in (7).

###  III-A Finite-Alphabet Case

Consider the case with a finite alphabet, i.e., $|\mathcal{X}|<\infty$. Let
$\mathcal{X}=\\{z_{1},z_{2},\cdots,z_{N}\\}$, $N=|\mathcal{X}|$. Then,
$\hat{x}_{l,j}\in\\{z_{i}\\}_{i=1}^{N}\ \text{for}\ l=0,1,j=1,\cdots,m$. In
this case,

$\displaystyle
P_{E}(\phi)=\sum_{i=1}^{N}(1-\phi_{N}(z_{i}))P_{1}^{N}(z_{i})+\phi_{N}(z_{i})P_{0}^{N}(z_{i}),$
(10)

where we introduce the superscript $N$ on $P_{0}$ and $P_{1}$ to emphasize its
dependence on $N$. Therefore, (7) can be written as

$\displaystyle\inf_{\phi_{N}}\sup_{P_{0}^{N}\in\mathcal{P}_{0},P_{1}^{N}\in\mathcal{P}_{1}}\sum_{i=1}^{N}(1-\phi_{N}(z_{i}))P_{1}^{N}(z_{i})+\phi_{N}(z_{i})P_{0}^{N}(z_{i}).$
(11)

Note that (11) is a minimax problem. We then provide the following strong
duality result for (11), which is a finite-dimensional convex optimization
problem.

######  Theorem 1.

The minimax problem in (11) has the following strong dual formulation:

$\displaystyle\inf_{\phi_{N},f_{0},g_{0}\in\mathbb{R},f_{1},g_{1}\in\mathcal{H}}$
$\displaystyle
f_{0}+g_{0}+\frac{1}{m}\sum_{i=1}^{m}f_{1}(\hat{x}_{1,i})+\frac{1}{m}\sum_{i=1}^{m}g_{1}(\hat{x}_{0,i})+\theta\|f_{1}\|_{\mathcal{H}}+\theta\|g_{1}\|_{\mathcal{H}}$
subject to $\displaystyle 1-\phi_{N}(z_{i})\leq f_{0}+f_{1}(z_{i}),\
\text{for}\ i=1,\cdots,N$ $\displaystyle\phi_{N}(z_{i})\leq
g_{0}+g_{1}(z_{i}),\ \text{for}\ i=1,\cdots,N$ $\displaystyle
0\leq\phi_{N}(z_{i})\leq 1,\ \text{for}\ i=1,\cdots,N,$ (12)

which is a finite-dimensional convex optimization problem.

###### Proof.

From the strong duality of kernel robust optimization [40, Theorem 3.1], we
have that (1) is a dual problem for (11) and the strong duality holds. From
the robust representer theorem [40], the functions $f_{1},g_{1}$ admit the
finite expansions $f_{1}(\cdot)=\sum_{i=1}^{N}\alpha_{i}k(z_{i},\cdot)$ and
$g_{1}(\cdot)=\sum_{i=1}^{N}\beta_{i}k(z_{i},\cdot)$. Therefore, the
optimization problem in (11) can be reformulated as a finite-dimensional
convex optimization problem thus can be solved efficiently in practice. ∎

Note that (1) is a convex optimization problem with linear constraints, and
thus can be solved using standard optimization tools [46]. By solving (1), we
obtain the optimal robust test $\phi_{N}^{*}$ and can also find the optimal
solutions $P_{0}^{*,N},P_{1}^{*,N}$ for the inner problem in (11) by plugging
$\phi_{N}^{*}$ back to (11). When $\phi_{N}^{*}$ is known, (11) reduces to a
finite-dimensional convex optimization problem and can be solved efficiently.
In the following section, we also show that the results in the finite-alphabet
case can be used to provide an asymptotically accurate approximation for the
infinite-alphabet case.

###  III-B Infinite-Alphabet Case

Consider the case where $\mathcal{X}$ is infinite. Then, (1) is infinite-
dimensional, and is not directly solvable. To simplify the analysis of (7), we
first interchange the $\sup$ and $\inf$ operators in (7) based on the
following proposition. Since the likelihood ratio test is optimal for the
binary hypothesis testing problem, the inner problem can be solved by applying
the likelihood ratio test. The original problem is then converted to a
maximization problem.

######  Proposition 1.

The minimax problem in (7) has the following reformulation:

$\displaystyle\inf_{\phi}\sup_{P_{0}\in\mathcal{P}_{0},P_{1}\in\mathcal{P}_{1}}P_{E}(\phi)=\sup_{P_{0}\in\mathcal{P}_{0},P_{1}\in\mathcal{P}_{1}}\inf_{\phi}P_{E}(\phi)$
$\displaystyle=$
$\displaystyle\frac{1}{2}\sup_{P_{0}\in\mathcal{P}_{0},P_{1}\in\mathcal{P}_{1}}\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx.$
(13)

###### Proof.

The error probability $P_{E}(\phi)$ is continuous, real-valued and linear in
$\phi$, $P_{0}$ and $P_{1}$. For any distributions
$Q_{1},Q_{2}\in\mathcal{P}_{l}$, $l=0,1$, from the triangle inequality of MMD
[25], the convex combination $\lambda Q_{1}+(1-\lambda)Q_{2},0<\lambda<1$,
lies in $\mathcal{P}_{l}$. Therefore, the uncertainty set $\mathcal{P}_{0}$
and $\mathcal{P}_{1}$ are convex sets and
$\mathcal{P}_{0}\times\mathcal{P}_{1}$ is also convex. Denote by $\Phi$ the
collection of all $\phi$. We have that $\Phi$ is the product of uncountably
many compact sets of $[0,1]$. Since $\mathcal{X}$ is compact, from the
Tychonoff’s theorem [47, 48], $\Phi$ is compact with respect to the product
topology. Moreover, for any $\phi_{1},\phi_{2}\in\Phi$, the convex combination
$\lambda\phi_{1}+(1-\lambda)\phi_{2},\ 0<\lambda<1$, also lies in $\Phi$.
Therefore, $\Phi$ is convex. From the Sion’s minimax theorem [49], we have
that

$\displaystyle\inf_{\phi}\sup_{P_{0}\in\mathcal{P}_{0},P_{1}\in\mathcal{P}_{1}}P_{E}(\phi)$
$\displaystyle=$
$\displaystyle\sup_{P_{0}\in\mathcal{P}_{0},P_{1}\in\mathcal{P}_{1}}\inf_{\phi}P_{E}(\phi)$
$\displaystyle=$
$\displaystyle\sup_{P_{0}\in\mathcal{P}_{0},P_{1}\in\mathcal{P}_{1}}\frac{1}{2}\int\mathbb{I}_{\big{\\{}\frac{p_{1}(x)}{p_{0}(x)}\geq
1\big{\\}}}p_{0}(x)dx+\frac{1}{2}\int\mathbb{I}_{\big{\\{}\frac{p_{1}(x)}{p_{0}(x)}<1\big{\\}}}p_{1}(x)dx$
$\displaystyle=$
$\displaystyle\frac{1}{2}\sup_{P_{0}\in\mathcal{P}_{0},P_{1}\in\mathcal{P}_{1}}\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx,$
(14)

where $\mathbb{I}$ denotes the indicator function and the second equality is
due to the fact that the likelihood ratio test is optimal for the binary
hypothesis testing problem [2, 4]. ∎

Observe that the problem in (1) is an infinite-dimensional optimization
problem and the closed-form optimal solutions $P_{0}^{*},P_{1}^{*}$ are
difficult to derive. In the following, we propose a tractable approximation
for the minimax error probability in (1). With this approximation, the worst-
case error probability in (1) can be quantified. The optimal solutions of this
tractable approximation can be further used to design a robust test that
generalizes to unseen samples.

Let $P$ be an arbitrary distribution supported on the whole space
$\mathcal{X}$, and is absolutely continuous w.r.t. a uniform distribution on
$\mathcal{X}$. Let $\\{z_{i}\\}^{N}_{i=1}$ be $N$ i.i.d. samples generated
from $P$. We then propose the following approximation of (1) by restricting to
distributions supported on the $N$ samples:

$\displaystyle\frac{1}{2}\sup_{P_{0}^{N}\in\mathcal{P}_{0}^{N},P_{1}^{N}\in\mathcal{P}_{1}^{N}}\
\ $
$\displaystyle\sum_{i=1}^{N}\min\big{\\{}P_{0}^{N}(z_{i}),P_{1}^{N}(z_{i})\big{\\}},$
(15)

where $\mathcal{P}_{l}^{N}(l=0,1)$ denotes the collection of distributions
that are supported on $\\{z_{i}\\}_{i=1}^{N}$ and satisfy
$\big{\|}\mu_{P_{l}^{N}}-\mu_{\hat{Q}^{l}_{m}}\big{\|}_{\mathcal{H}}\leq\theta$.
We note that (15) is a finite-dimensional convex optimization problem which
can be solved by standard optimization tools. Let

$\displaystyle
f(\mathcal{P}_{0},\mathcal{P}_{1})=\frac{1}{2}\sup_{P_{0}\in\mathcal{P}_{0},P_{1}\in\mathcal{P}_{1}}\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx,$
$\displaystyle
f(\mathcal{P}^{N}_{0},\mathcal{P}^{N}_{1})=\frac{1}{2}\sup_{P_{0}^{N}\in\mathcal{P}_{0}^{N},P_{1}^{N}\in\mathcal{P}_{1}^{N}}\sum_{i=1}^{N}\min\big{\\{}P_{0}^{N}(z_{i}),P_{1}^{N}(z_{i})\big{\\}}.$
(16)

Clearly, (15) is a lower bound of (1), i.e.,
$f(\mathcal{P}^{N}_{0},\mathcal{P}^{N}_{1})\leq
f(\mathcal{P}_{0},\mathcal{P}_{1})$. The following theorem demonstrates that
as $N\rightarrow\infty$, the value of (15) converges to the value of (1)
almost surely.

######  Theorem 2.

As $N\rightarrow\infty$, $f(\mathcal{P}^{N}_{0},\mathcal{P}^{N}_{1})$
converges to $f(\mathcal{P}_{0},\mathcal{P}_{1})$ almost surely.

Before we prove Theorem 2, we will first show that
$\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx$ is upper semi-continuous in
$P_{0},P_{1}$ with respect to the weak convergence in the following lemma.

######  Lemma 1.

$\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx$ is upper semi-continuous in
$P_{0},P_{1}$ with respect to the weak convergence.

###### Proof.

The proof of Lemma 1 can be found in Appendix B. ∎

With Lemma 1, we are ready to prove Theorem 2.

###### Proof sketch.

We first show that the solutions to
$\sup_{P_{0}\in\mathcal{P}_{0},P_{1}\in\mathcal{P}_{1}}\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx$
exist and let $P_{0}^{*},P_{1}^{*}$ denote the optimal solutions. We then show
that there exist distributions $P_{0}^{s},P_{1}^{s}$ supported on $s$ samples
converging weakly to $P_{0}^{*},P_{1}^{*}$ respectively, as
$s\rightarrow\infty$. Thirdly, for a fixed $s$, we show that there exist
distributions $P_{0}^{s,N},P_{1}^{s,N}$ supported on $\\{z_{i}\\}_{i=1}^{N}$
converging weakly to $P_{0}^{s},P_{1}^{s}$ almost surely as
$N\rightarrow\infty$ and

$\displaystyle\sum_{i=1}^{N}\min\big{\\{}P_{0}^{s,N}(z_{i}),P_{1}^{s,N}(z_{i})\big{\\}}\geq\int\min\\{p_{0}^{*}(x),p_{1}^{*}(x)\\}dx.$
(17)

Moreover, we show that for any $\epsilon>0$, there exists large $s$ and $N$
such that the MMD between $P_{0}^{s,N},P_{1}^{s,N}$ and
$\hat{Q}^{0}_{m},\hat{Q}^{1}_{m}$ can be bounded by $\theta+\epsilon$.
Finally, by letting $\epsilon\rightarrow 0$, we prove the convergence result
in Theorem 2.

The full proof of Theorem 2 can be found in Appendix C. ∎

Though the optimal solutions $P_{0}^{*},P_{1}^{*}$ for (1) is difficult to
derive, (15) provides a lower bound on the worst-case error probability, and
is asymptotically accurate as $N\rightarrow\infty$.

###  III-C Robust Test via Kernel Smoothing

The optimal solutions $P_{0}^{*},P_{1}^{*}$ of (1), and thus the likelihood
ratio test between $P_{0}^{*}$ and $P_{1}^{*}$ are difficult to derive. Note
that $P_{0}^{*,N},P_{1}^{*,N}$ are optimal solutions to (15). The following
proposition show that a subsequence of
$\\{P^{*,N}_{0},P^{*,N}_{1}\\}_{N=1}^{\infty}$ converges weakly to an optimal
solution of (1). The fact that $P_{0}^{*,N},P_{1}^{*,N}$ are reasonable
approximations of $P_{0}^{*},P_{1}^{*}$ as $N\rightarrow\infty$ further
motivates our kernel smoothing method to design a robust test that generalizes
to the entire alphabet in this section.

######  Proposition 2.

There exists a subsequence of $\\{P^{*,N}_{0},P^{*,N}_{1}\\}_{N=1}^{\infty}$
that converges weakly to an optimal solution of (1).

###### Proof.

Observe that for any $N$, $\\{P^{*,N}_{0},P^{*,N}_{1}\\}$ lies in the compact
set $\mathcal{P}_{0}\times\mathcal{P}_{1}$. Therefore, there exists a
subsequence of $\\{P^{*,N}_{0},P^{*,N}_{1}\\}_{N=1}^{\infty}$ that converges,
and the limit lies in $\mathcal{P}_{0}\times\mathcal{P}_{1}$. Denote the
sequence by $\\{P_{0}^{*,N(t)},P_{1}^{*,N(t)}\\}_{t=1}^{\infty}$. Suppose
$\\{P_{0}^{*,N(t)},P_{1}^{*,N(t)}\\}_{t=1}^{\infty}$ converges weakly to
$\\{P_{0}^{\prime},P_{1}^{\prime}\\}$. Since $P_{0}^{*,N},P_{1}^{*,N}$ are
optimal solutions to (15), we have that

$\displaystyle\int\min\\{p_{0}^{*}(x),p_{1}^{*}(x)\\}dx$
$\displaystyle=\lim_{t\rightarrow\infty}\sum_{i=1}^{N}\min\\{P_{0}^{*,N(t)}(z_{i}),P_{1}^{*,N(t)}(z_{i})\\}$
$\displaystyle\leq\int\min\\{p_{0}^{\prime}(x),p_{1}^{\prime}(x)\\}dx,$ (18)

where the equality is from Theorem 2, and the inequality is due to the upper
semi-continuity of $\int\min\\{p_{0}(x),p_{1}(x)\\}dx$. Since
$P_{0}^{*},P_{1}^{*}$ are optimal solutions of (1) and
$P_{0}^{\prime}\in\mathcal{P}_{0},P_{1}^{\prime}\in\mathcal{P}_{1}$, from
(III-C), $P_{0}^{\prime},P_{1}^{\prime}$ are optimal solutions of (1). This
completes the proof. ∎

Note that $P^{*,N}_{0},P^{*,N}_{1}$ are convex combinations of Dirac measures.
We then extend them to the whole space via kernel smoothing to approximate
$P_{0}^{*},P_{1}^{*}$, i.e.,

$\displaystyle\widetilde{P}_{0}^{*}(x)=\sum_{i=1}^{N}P_{0}^{*,N}(z_{i})k(x,z_{i}),$
$\displaystyle\widetilde{P}_{1}^{*}(x)=\sum_{i=1}^{N}P_{1}^{*,N}(z_{i})k(x,z_{i}).$
(19)

The kernel functions have various choices. For example, the Gaussian kernel
with bandwidth parameter $\sigma$:
$k(x,y)=\frac{1}{\sqrt{2}\sigma}\exp\big{(}-\frac{\|x-y\|^{2}}{2\sigma^{2}}\big{)}$.
After kernel smoothing, we define the likelihood ratio test $\tilde{\phi}$
between $\widetilde{P}_{1}^{*}(x)$ and $\widetilde{P}_{0}^{*}(x)$ over the
whole space $\mathcal{X}$ as follows to approximate the optimal test:

$\displaystyle\tilde{\phi}(x)=\left\\{\begin{array}[]{ll}1,&\text{ if
}\log\frac{\widetilde{P}_{1}^{*}(x)}{\widetilde{P}_{0}^{*}(x)}\geq 0\\\
0,&\text{ if
}\log\frac{\widetilde{P}_{1}^{*}(x)}{\widetilde{P}_{0}^{*}(x)}<0.\end{array}\right.$
(22)

The numerical results in Section V show that $\tilde{\phi}$ performs well in
practice, and is robust to model uncertainty.

###  III-D A Direct Robust Kernel Test

In this section, we consider the problem of testing a sequence of samples
$x^{n}$, where $n$ is the sample size. We propose a direct robust kernel test
and further show that it is exponentially consistent as $n\rightarrow\infty$
under the Bayesian setting.

Motivated by the facts that the MMD can be used to measure the distance
between distributions when the kernel $k$ is characteristic, we propose a
direct robust kernel test as follows

$\displaystyle\phi_{B}(x^{n})=\left\\{\begin{array}[]{ll}1,&\text{ if
}S(x^{n})\geq\gamma\\\ 0,&\text{ if }S(x^{n})<\gamma,\end{array}\right.$ (25)

where

$\displaystyle
S(x^{n})=\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}-\inf_{P\in\mathcal{P}_{1}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}},$
(26)

and $\gamma$ is a pre-specified threshold. In the construction of $S(x^{n})$,
we use “inf” to tackle the uncertainty of distributions and compare the
closest distance between the empirical distribution of samples and the two
uncertainty sets. The test statistic involves two infinite-dimensional
optimization problems, and thus is difficult to solve in general. In the
following proposition, we show that it can actually be solved analytically in
closed-form, and the computational complexity is $\mathcal{O}(m^{2}+n^{2})$.

######  Proposition 3.

For any $l=0,1$, if
$\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}^{l}_{m}}\big{\|}_{\mathcal{H}}>\theta$,
then

$\displaystyle\inf_{P\in\mathcal{P}_{l}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}=\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}^{l}_{m}}\big{\|}_{\mathcal{H}}-\theta$
$\displaystyle=\Big{(}\frac{1}{n^{2}}\sum_{i=1}^{n}\sum_{j=1}^{n}k(x_{i},x_{j})+\frac{1}{m^{2}}\sum_{i=1}^{m}\sum_{j=1}^{m}k(\hat{x}_{l,i},\hat{x}_{l,j})-\frac{2}{nm}\sum_{i=1}^{n}\sum_{j=1}^{m}k(x_{i},\hat{x}_{l,j})\Big{)}^{1/2}-\theta;$
(27)

and otherwise,
$\inf_{P\in\mathcal{P}_{l}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}=0$.

###### Proof.

Note that MMD is non-negative. If
$\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}\leq\theta$,
we have that $\hat{P}_{n}\in\mathcal{P}_{0}$. Therefore,
$\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}=0$.
We then consider the case that
$\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}>\theta$.
For any $P\in\mathcal{P}_{0}$,
$\big{\|}\mu_{P}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}\leq\theta$, and
thus by the triangle inequality [25], we have that

$\displaystyle\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}$
$\displaystyle\geq\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}-\big{\|}\mu_{P}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}$
$\displaystyle\geq\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}-\theta.$
(28)

It then follows that

$\displaystyle\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}\geq\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}-\theta.$
(29)

The equality in (29) can be achieved when the following condition holds for a
$P\in\mathcal{P}_{0}$:

$\displaystyle\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}=\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}-\theta.$
(30)

We then construct such a $P$. Let
$\lambda=\frac{\theta}{\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}}$.
Since
$\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}>\theta$,
we have that $0<\lambda<1$. Let
$P=\lambda\hat{P}_{n}+(1-\lambda)\hat{Q}^{0}_{m}$ be a linear combination of
two distributions $\hat{P}_{n}$ and $\hat{Q}^{0}_{m}$. We then have that
$P\in\mathcal{P}$ and

$\displaystyle\mu_{P}=$ $\displaystyle\int
k(x,\cdot)d\big{(}\lambda\hat{P}_{n}+(1-\lambda)\hat{Q}^{0}_{m}\big{)}$
$\displaystyle=$ $\displaystyle\lambda\int
k(x,\cdot)d\hat{P}_{n}+(1-\lambda)\int k(x,\cdot)d\hat{Q}^{0}_{m}$
$\displaystyle=$
$\displaystyle\lambda\mu_{\hat{P}_{n}}+(1-\lambda)\mu_{\hat{Q}^{0}_{m}}.$ (31)

It then follows that

$\displaystyle\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}=$
$\displaystyle\big{\|}(1-\lambda)\mu_{\hat{P}_{n}}-(1-\lambda)\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}$
$\displaystyle=$
$\displaystyle(1-\lambda)\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}$
$\displaystyle=$
$\displaystyle\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}-\theta.$
(32)

and

$\displaystyle\big{\|}\mu_{P}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}=$
$\displaystyle\big{\|}\lambda\mu_{\hat{P}_{n}}-\lambda\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}$
$\displaystyle=$
$\displaystyle\lambda\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}$
$\displaystyle=$ $\displaystyle\theta.$ (33)

Therefore, $P=\lambda\hat{P}_{n}+(1-\lambda)\hat{Q}^{0}_{m}\in\mathcal{P}_{0}$
and achieves the equality in (29). Therefore, when
$\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}>\theta$,
we have that

$\displaystyle\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}=\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}-\theta,$
(34)

From (II-A), it follows that

$\displaystyle\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}=\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}-\theta$
$\displaystyle=\Big{(}\frac{1}{n^{2}}\sum_{i=1}^{n}\sum_{j=1}^{n}k(x_{i},x_{j})+\frac{1}{m^{2}}\sum_{i=1}^{m}\sum_{j=1}^{m}k(\hat{x}_{0,i},\hat{x}_{0,j})-\frac{2}{nm}\sum_{i=1}^{n}\sum_{j=1}^{m}k(x_{i},\hat{x}_{0,j})\Big{)}^{1/2}-\theta.$
(35)

Following the same idea as in solving
$\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}$,
the closed-form solution can also be derived for
$\inf_{P\in\mathcal{P}_{1}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}$.
∎

In the following theorem, we show that with a proper choice of $\gamma$,
$\phi_{B}$ is exponentially consistent.

######  Theorem 3.

1) If
$\gamma\in\Big{(}-\big{\|}\mu_{\hat{Q}_{m}^{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}+2\theta,\big{\|}\mu_{\hat{Q}_{m}^{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}-2\theta\Big{)}$,
$\phi_{B}$ is exponentially consistent.
2) $\phi_{B}$ can be equivalently written as

$\displaystyle\phi_{B}^{\prime}(x^{n})=\left\\{\begin{array}[]{ll}1,&\text{if
}\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}-\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}\geq\gamma\\\
0,&\text{if
}\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}-\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}<\gamma,\end{array}\right.$
(38)

and its computational complexity is $\mathcal{O}\big{(}m^{2}+n^{2}\big{)}$.

###### Proof.

1) For the type-I error exponent, from the Sanov’s theorem [3], we have that
for any $P_{0}\in\mathcal{P}_{0}$,

$\displaystyle\lim_{n\rightarrow\infty}-\frac{1}{n}E_{P_{0}}[\phi_{B}(x^{n})]$
$\displaystyle=\lim_{n\rightarrow\infty}-\frac{1}{n}\log
P_{0}\Big{(}\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}-\inf_{P\in\mathcal{P}_{1}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}\geq\gamma\Big{)}$
$\displaystyle\geq\inf_{P^{\prime}\in\Gamma_{0}}D(P^{\prime}\|P_{0}),$ (39)

where
$\Gamma_{0}=\Big{\\{}P^{\prime}:\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{P^{\prime}}-\mu_{P}\big{\|}_{\mathcal{H}}-\inf_{P\in\mathcal{P}_{1}}\big{\|}\mu_{P^{\prime}}-\mu_{P}\big{\|}_{\mathcal{H}}\geq\gamma\Big{\\}}$
and $D(P^{\prime}\|P_{0})$ denotes the KL-divergence between two distributions
$P^{\prime}$ and $P_{0}$. For any $P_{0}\in\mathcal{P}_{0}$ and
$\gamma\in\Big{(}-\big{\|}\mu_{\hat{Q}_{m}^{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}+2\theta,\big{\|}\mu_{\hat{Q}_{m}^{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}-2\theta\Big{)}$,
we have that

$\displaystyle\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{P_{0}}-\mu_{P}\big{\|}_{\mathcal{H}}-\inf_{P\in\mathcal{P}_{1}}\big{\|}\mu_{P_{0}}-\mu_{P}\big{\|}_{\mathcal{H}}$
$\displaystyle=-\inf_{P\in\mathcal{P}_{1}}\big{\|}\mu_{P_{0}}-\mu_{P}\big{\|}_{\mathcal{H}}$
$\displaystyle=-\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}+\theta$
$\displaystyle\leq\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}-\big{\|}\mu_{\hat{Q}_{m}^{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}+\theta$
$\displaystyle\leq-\big{\|}\mu_{\hat{Q}_{m}^{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}+2\theta$
$\displaystyle<\gamma,$ (40)

where the first and second equalities are from Proposition 3, the first
inequality is from the triangle inequality of MMD [25] and the second
inequality is because $P_{0}\in\mathcal{P}_{0}$. We then have that for any
$P_{0}\in\mathcal{P}_{0}$, when
$\gamma\in\Big{(}-\big{\|}\mu_{\hat{Q}_{m}^{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}+2\theta,\big{\|}\mu_{\hat{Q}_{m}^{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}-2\theta\Big{)}$,
$P_{0}\notin\Gamma_{0}$. Therefore,
$\inf_{P^{\prime}\in\Gamma_{0}}D(P^{\prime}\|P_{0})>0$ thus the type-I error
probability of $\phi_{B}$ decreases exponentially fast with $n$.

Similarly, for the type-II error exponent, we have that for any
$P_{1}\in\mathcal{P}_{1}$,

$\displaystyle\lim_{n\rightarrow\infty}-\frac{1}{n}\log
E_{P_{1}}[1-\phi_{B}(x^{n})]$
$\displaystyle=\lim_{n\rightarrow\infty}-\frac{1}{n}\log
P_{1}\Big{(}\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}-\inf_{P\in\mathcal{P}_{1}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}<\gamma\Big{)}$
$\displaystyle\geq\inf_{P^{\prime}\in\Gamma_{1}}D(P^{\prime}\|P_{1}),$ (41)

where
$\Gamma_{1}=\Big{\\{}P^{\prime}:\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{P^{\prime}}-\mu_{P}\big{\|}_{\mathcal{H}}-\inf_{P\in\mathcal{P}_{1}}\big{\|}\mu_{P^{\prime}}-\mu_{P}\big{\|}_{\mathcal{H}}\leq\gamma\Big{\\}}$.
For any $P_{1}\in\mathcal{P}_{1}$ and
$\gamma\in\Big{(}-\big{\|}\mu_{\hat{Q}_{m}^{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}+2\theta,\big{\|}\mu_{\hat{Q}_{m}^{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}-2\theta\Big{)}$,
we have that

$\displaystyle\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{P_{1}}-\mu_{P}\big{\|}_{\mathcal{H}}-\inf_{P\in\mathcal{P}_{1}}\big{\|}\mu_{P_{1}}-\mu_{P}\big{\|}_{\mathcal{H}}$
$\displaystyle=\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{P_{1}}-\mu_{P}\big{\|}_{\mathcal{H}}$
$\displaystyle=\big{\|}\mu_{P_{1}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}-\theta$
$\displaystyle\geq\big{\|}\mu_{\hat{Q}_{m}^{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}-\big{\|}\mu_{P_{1}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}-\theta$
$\displaystyle\geq\big{\|}\mu_{\hat{Q}_{m}^{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}-2\theta$
$\displaystyle>\gamma,$ (42)

where the first and second equalities are from Proposition 3, the first
inequality is from the triangle inequality of MMD [25] and the second
inequality is because $P_{1}\in\mathcal{P}_{1}$. Therefore, for any
$P_{1}\in\mathcal{P}_{1}$, we have that $P_{1}\notin\Gamma_{1}$, and thus
$\inf_{P^{\prime}\in\Gamma_{1}}D(P^{\prime}\|P_{1})>0$ and the type-II error
probability of $\phi_{B}$ decreases exponentially fast with $n$. Therefore,
the direct robust kernel test $\phi_{B}$ is exponentially consistent.

2) We will then prove that with
$\gamma\in\Big{(}-\big{\|}\mu_{\hat{Q}_{m}^{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}+2\theta,\big{\|}\mu_{\hat{Q}_{m}^{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}-2\theta\Big{)}$,
$\phi_{B}$ and $\phi^{\prime}_{B}$ are equivalent. When
$\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}\leq\theta$,
we have that $\hat{P}_{n}\in\mathcal{P}_{0}$. From (III-D), it follows that

$\displaystyle\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}-\inf_{P\in\mathcal{P}_{1}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}<\gamma.$
(43)

Moreover, from triangle inequality [25], we have that

$\displaystyle\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}-\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}$
$\displaystyle\leq\theta-\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}$
$\displaystyle\leq\theta-\big{\|}\mu_{\hat{Q}_{m}^{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}+\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}$
$\displaystyle\leq-\big{\|}\mu_{\hat{Q}_{m}^{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}+2\theta$
$\displaystyle<\gamma.$ (44)

Therefore, when
$\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}\leq\theta$,
$\phi_{B}=\phi^{\prime}_{B}=0$.

When
$\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}\leq\theta$,
we have that $\hat{P}_{n}\in\mathcal{P}_{1}$. From (III-D), it follows that

$\displaystyle\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}-\inf_{P\in\mathcal{P}_{1}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}>\gamma.$
(45)

From the triangle inequality [25], we have that

$\displaystyle\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}-\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}$
$\displaystyle\geq\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}-\theta$
$\displaystyle\geq\big{\|}\mu_{\hat{Q}_{m}^{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}-\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}-\theta$
$\displaystyle\geq\big{\|}\mu_{\hat{Q}_{m}^{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}-2\theta$
$\displaystyle>\gamma.$ (46)

Therefore, when
$\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}\leq\theta$,
$\phi_{B}=\phi^{\prime}_{B}=1$.

When
$\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}>\theta$
and
$\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}>\theta$,
from Proposition 3, we have that

$\displaystyle\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}-\inf_{P\in\mathcal{P}_{1}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}=\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}-\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}.$
(47)

Combining the three different cases, we have that $\phi_{B}$ and
$\phi^{\prime}_{B}$ are equivalent. We note that $\phi^{\prime}_{B}$ only
consists of MMD between empirical distributions, thus it can be implemented
efficiently. From (II-A), we have that

$\displaystyle\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}-\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}^{1}_{m}}\big{\|}_{\mathcal{H}}$
$\displaystyle=\Big{(}\frac{1}{n^{2}}\sum_{i=1}^{n}\sum_{j=1}^{n}k(x_{i},x_{j})+\frac{1}{m^{2}}\sum_{i=1}^{m}\sum_{j=1}^{m}k(\hat{x}_{0,i},\hat{x}_{0,j})-\frac{2}{nm}\sum_{i=1}^{n}\sum_{j=1}^{m}k(x_{i},\hat{x}_{0,j})\Big{)}^{1/2}$
$\displaystyle-\Big{(}\frac{1}{n^{2}}\sum_{i=1}^{n}\sum_{j=1}^{n}k(x_{i},x_{j})+\frac{1}{m^{2}}\sum_{i=1}^{m}\sum_{j=1}^{m}k(\hat{x}_{1,i},\hat{x}_{1,j})-\frac{2}{nm}\sum_{i=1}^{n}\sum_{j=1}^{m}k(x_{i},\hat{x}_{1,j})\Big{)}^{1/2}.$
(48)

This completes the proof. ∎

It can be seen that the direct test for robust hypothesis testing naturally
reduces to comparing the MMD distance between the empirical distribution of
samples and two centers of uncertainty sets which is computationally
efficient. The exponential consistency of $\phi_{B}$ implies that the error
probabilities decay exponentially fast with the sample size $n$. In practice,
we can choose a proper threshold to balance the trade-off between the two
types of errors.

The error exponent in Theorem 3 is in an asymptotic sense, and is in the form
of an optimization problem without a closed-form solution. In the following
proposition, we consider a special case with $\gamma=0$ and derive the closed-
form upper bound of the worst-case error probabilities.

######  Proposition 4.

Set $\gamma=0$ in (25). Then, the worst-case type-I and type-II errors can be
bounded as follows,

$\displaystyle\sup_{P_{0}\in\mathcal{P}_{0}}E_{P_{0}}[\phi_{B}(x^{n})]\leq\exp\Bigg{(}-\frac{n\Big{(}\big{\|}\mu_{\hat{Q}_{m}^{1}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}^{2}-2\theta\big{\|}\mu_{\hat{Q}_{m}^{1}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}\Big{)}^{2}}{8K^{2}}\Bigg{)}$
(49)

and

$\displaystyle\sup_{P_{1}\in\mathcal{P}_{1}}E_{P_{1}}[1-\phi_{B}(x^{n})]\leq\exp\Bigg{(}-\frac{n\Big{(}\big{\|}\mu_{\hat{Q}_{m}^{1}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}^{2}-2\theta\big{\|}\mu_{\hat{Q}_{m}^{1}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}\Big{)}^{2}}{8K^{2}}\Bigg{)}.$
(50)

###### Proof.

The proof of Proposition 4 can be found in Appendix D. ∎

In Proposition 4, we provide an upper bound on the worst-case error
probability of $\phi_{B}$ when $\gamma=0$. It can be seen that the error
probabilities decay exponentially fast with an exponent of
$\Big{(}\big{\|}\mu_{\hat{Q}_{m}^{1}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}^{2}-2\theta\big{\|}\mu_{\hat{Q}_{m}^{1}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}\Big{)}^{2}/8K^{2}$,
which validates the fact that $\phi_{B}$ is exponentially consistent.
Moreover, the decay rate is a function of the radius $\theta$ and the MMD
distance between centers of two uncertainty sets. When the centers of two
uncertainty sets are fixed, the upper bound on the error probabilities will
increase with the radius $\theta$. Proposition 4 provides a closed-form non-
asymptotic upper bound on the worst-case error probability. In practice, this
upper bound can be used to evaluate the worst-case risk of implementing
$\phi_{B}$ for a finite sample size $n$. Moreover, combining Theorem 2 and
Theorem 3, the performance gap between $\phi_{B}$ and the optimal test can be
approximated.

##  IV Robust Hypothesis Testing under Neyman-Pearson Setting

In this section, we focus on the Neyman-Pearson setting. We propose a robust
kernel test, and show that it is asymptotically optimal under the Neyman-
Pearson setting.

###  IV-A Universal Upper Bound on the Worst-Case Error Exponent

In this section, we derive the universal upper bound on the error exponent for
the problem in (9). The following proposition is a robust version of the
Chernoff-Stein lemma [3, 41].

######  Proposition 5.

Consider the robust hypothesis testing problem in (9), we have that

$\displaystyle\sup_{\phi:P_{F}(\phi)\leq\alpha}\inf_{P_{1}\in\mathcal{P}_{1}}\lim_{n\rightarrow\infty}-\frac{1}{n}\log
E_{P_{1}}[1-\phi(x^{n})]$
$\displaystyle\leq\inf_{P_{0}\in\mathcal{P}_{0},P_{1}\in\mathcal{P}_{1}}D(P_{0}\|P_{1}).$
(51)

###### Proof.

For any $P_{0}\in\mathcal{P}_{0},P_{1}\in\mathcal{P}_{1}$, from the Chernoff-
Stein lemma [3, 41], we have that

$\displaystyle\sup_{\phi:E_{P_{0}}[\phi(x^{n})]\leq\alpha}\lim_{n\rightarrow\infty}-\frac{1}{n}\log
E_{P_{1}}[1-\phi(x^{n})]=D(P_{0}\|P_{1}).$ (52)

Since
$P_{F}(\phi)\triangleq\sup_{P_{0}\in\mathcal{P}_{0}}E_{P_{0}}[\phi(x^{n})]$,
we have that
$\\{\phi:P_{F}(\phi)\leq\alpha\\}\subseteq\\{\phi:E_{P_{0}}[\phi(x^{n})]\leq\alpha\\}$.
Therefore, for any $P_{0}\in\mathcal{P}_{0},P_{1}\in\mathcal{P}_{1}$, we have
that

$\displaystyle\sup_{\phi:P_{F}(\phi)\leq\alpha}\inf_{P_{1}\in\mathcal{P}_{1}}\lim_{n\rightarrow\infty}-\frac{1}{n}\log
E_{P_{1}}[1-\phi(x^{n})]$
$\displaystyle\leq\sup_{\phi:E_{P_{0}}[\phi(x^{n})]\leq\alpha}\lim_{n\rightarrow\infty}-\frac{1}{n}\log
E_{P_{1}}[1-\phi(x^{n})]$ $\displaystyle=D(P_{0}\|P_{1}).$ (53)

The solutions to
$\inf_{P_{0}\in\mathcal{P}_{0},P_{1}\in\mathcal{P}_{1}}D(P_{0}\|P_{1})$ exist
since $D(P_{0}\|P_{1})$ is lower semi-continuous and lower semi-continuous
functions attain its infimum on a compact set. Since (IV-A) holds for any
$P_{0}\in\mathcal{P}_{0},P_{1}\in\mathcal{P}_{1}$, we then have that

$\displaystyle\sup_{\phi:P_{F}(\phi)\leq\alpha}\inf_{P_{1}\in\mathcal{P}_{1}}\lim_{n\rightarrow\infty}-\frac{1}{n}\log
E_{P_{1}}[1-\phi(x^{n})]$
$\displaystyle\leq\inf_{P_{0}\in\mathcal{P}_{0},P_{1}\in\mathcal{P}_{1}}D(P_{0}\|P_{1}).$
(54)

∎

Proposition 5 implies that for any test, the achievable error exponent is no
better than
$\inf_{P_{0}\in\mathcal{P}_{0},P_{1}\in\mathcal{P}_{1}}D(P_{0}\|P_{1})$. This
theorem also applies to robust hypothesis testing problems with different
uncertainty sets.

###  IV-B Asymptotically Optimal Robust Kernel Test

In this section, we propose a robust kernel test for the problem in (9), and
further prove that it is asymptotically optimal.

Motivated by the fact that when the kernel $k$ is characteristic, the MMD is a
metric and can be used to measure the distance between distributions and the
kernel test is asymptotically optimal under the Neyman-Pearson setting for the
two-sample test problem [34], we design our robust kernel test as follows:

$\displaystyle\phi_{N}(x^{n})=\left\\{\begin{array}[]{ll}1,&\text{ if
}\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}>\gamma_{n}\\\
0,&\text{ if
}\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}\leq\gamma_{n},\end{array}\right.$
(57)

where $\gamma_{n}=\sqrt{2K/n}\big{(}1+\sqrt{-\log\alpha}\big{)}$ is chosen to
satisfy the false alarm constraint that $P_{F}(\phi_{N})\leq\alpha$, and
$\hat{P}_{n}$ is the empirical distribution of $x^{n}$. We use “inf” in the
test statistic to tackle the uncertainty of distributions. A heuristic
explanation of our test is that we use the closest distance between the
empirical distribution of the test samples and the uncertainty set
$\mathcal{P}_{0}$. Our test statistic does not depend on $\mathcal{P}_{1}$,
but later we will show that it is asymptotically optimal under the Neyman-
Pearson setting, i.e., solves the problem in (9).

From Proposition 3, we have that the test statistic of our robust kernel test
can be solved analytically in closed-form with a computational complexity of
$\mathcal{O}(m^{2}+n^{2})$. We then show that the kernel robust test in (57)
is asymptotically optimal for the problem in (9) in the following theorem,
i.e., it achieves the universal upper bound on the worst-case error exponent
in Proposition 5.

######  Theorem 4.

The robust kernel test in (57) is asymptotically optimal under Neyman-Pearson
setting:
1) under $H_{0}$,

$\displaystyle\sup_{P_{0}\in\mathcal{P}_{0}}E_{P_{0}}[\phi_{N}(x^{n})]=\sup_{P_{0}\in\mathcal{P}_{0}}P_{0}\Big{(}\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}>\gamma_{n}\Big{)}\leq\alpha;$
(58)

and 2) under $H_{1}$,

$\displaystyle\inf_{P_{1}\in\mathcal{P}_{1}}\lim_{n\rightarrow\infty}-\frac{1}{n}\log
E_{P_{1}}[1-\phi_{N}(x^{n})]$
$\displaystyle=\inf_{P_{1}\in\mathcal{P}_{1}}\lim_{n\rightarrow\infty}-\frac{1}{n}\log
P_{1}\Big{(}\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}\leq\gamma_{n}\Big{)}$
$\displaystyle=\sup_{\phi:P_{F}(\phi)\leq\alpha}\inf_{P_{1}\in\mathcal{P}_{1}}\lim_{n\rightarrow\infty}-\frac{1}{n}\log
E_{P_{1}}[1-\phi(x^{n})]$
$\displaystyle=\inf_{P_{0}\in\mathcal{P}_{0},P_{1}\in\mathcal{P}_{1}}D(P_{0}\|P_{1}).$
(59)

###### Proof.

For any $P_{0}\in\mathcal{P}_{0}$, we have that

$\displaystyle
P_{0}\Big{(}\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}>\gamma_{n}\Big{)}\leq
P_{0}\Big{(}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P_{0}}\big{\|}_{\mathcal{H}}>\gamma_{n}\Big{)}.$

Set $\gamma_{n}=\sqrt{2K/n}\big{(}1+\sqrt{-\log\alpha}\big{)}$. From Lemma 2
in Appendix A, we have that for any $P_{0}\in\mathcal{P}_{0}$,

$\displaystyle
P_{0}\Big{(}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P_{0}}\big{\|}_{\mathcal{H}}>\gamma_{n}\Big{)}\leq\alpha.$
(60)

We then have that

$\displaystyle\sup_{P_{0}\in\mathcal{P}_{0}}P_{0}\Big{(}\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}>\gamma_{n}\Big{)}\leq\alpha.$
(61)

Note that $\gamma_{n}\rightarrow 0$ as $n\rightarrow\infty$. For any
$\gamma>0$, there exists an integer $n_{0}$ such that $\gamma_{n}<\gamma$ for
all $n>n_{0}$. We then have that for large $n$,

$\displaystyle\Big{\\{}P^{\prime}\in\mathcal{P}:\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{P^{\prime}}-\mu_{P}\big{\|}_{\mathcal{H}}\leq\gamma_{n}\Big{\\}}\subseteq\Big{\\{}P^{\prime}\in\mathcal{P}:\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{P^{\prime}}-\mu_{P}\big{\|}_{\mathcal{H}}\leq\gamma\Big{\\}}.$
(62)

It then follows that

$\displaystyle\inf_{P_{1}\in\mathcal{P}_{1}}\lim_{n\rightarrow\infty}-\frac{1}{n}\log
P_{1}\Big{(}\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}\leq\gamma_{n}\Big{)}$
$\displaystyle\geq\inf_{P_{1}\in\mathcal{P}_{1}}\lim_{n\rightarrow\infty}-\frac{1}{n}\log
P_{1}\Big{(}\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}\leq\gamma\Big{)}$
$\displaystyle\geq\inf_{P_{1}\in\mathcal{P}_{1}}\inf_{\big{\\{}P^{\prime}\in\mathcal{P}:\inf_{P\in\mathcal{P}_{0}}\|\mu_{P^{\prime}}-\mu_{P}\|_{\mathcal{H}}\leq\gamma\big{\\}}}D(P^{\prime}\|P_{1}),$
(63)

where the last inequality is from the Sanov’s theorem [3] and the fact that
$\\{P^{\prime}\in\mathcal{P}:\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{P^{\prime}}-\mu_{P}\big{\|}_{\mathcal{H}}\leq\gamma\\}$
is closed w.r.t. the weak topology. Let

$\displaystyle\Gamma=\\{P^{\prime}\in\mathcal{P}:\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{P^{\prime}}-\mu_{P}\big{\|}_{\mathcal{H}}\leq\gamma\\}.$
(64)

Since MMD metrizes the weak convergence on $\mathcal{P}$ [44, 45], and KL
divergence is lower semi-continuous with respect to the weak topology of
$\mathcal{P}$ (see Lemma 3 in Appendix A), we have that for any $\epsilon>0$
and $P_{1}\in\mathcal{P}_{1}$, there exists a neighborhood $U$ of $P_{0}$
defined by MMD such that $D(P^{\prime}\|P_{1})\geq D(P_{0}\|P_{1})-\epsilon$
for any $P^{\prime}\in U$.

Specifically, for any $P_{0}\in\mathcal{P}_{0}$, define the neighborhood of
$P_{0}$ with radius $\gamma$ as
$U(P_{0},\gamma)=\\{P\in\mathcal{P}:\|\mu_{P}-\mu_{P_{0}}\|_{\mathcal{H}}\leq\gamma\\}$.
From the lower semi-continuity of KL divergence, we have that for any
$\epsilon>0$ and $P_{1}\in\mathcal{P}_{1}$, there exists
$\gamma(\epsilon,P_{0})>0$ such that $D(P^{\prime}\|P_{1})\geq
D(P_{0}\|P_{1})-\epsilon$ for any $P^{\prime}\in
U(P_{0},\gamma(\epsilon,P_{0}))$. Therefore, for any
$P^{\prime}\in\bigcup_{P_{0}\in\mathcal{P}_{0}}U(P_{0},\gamma(\epsilon,P_{0}))$,
there exists $P_{0}\in\mathcal{P}_{0}$ such that $D(P^{\prime}\|P_{1})\geq
D(P_{0}\|P_{1})-\epsilon$.

For a given $\epsilon>0$ and $P_{1}\in\mathcal{P}_{1}$, let
$\gamma^{*}=\min_{P_{0}\in\mathcal{P}_{0}}\gamma(\epsilon,P_{0})$. Since
$\gamma(\epsilon,P_{0})>0$ holds for any $P_{0}\in\mathcal{P}_{0}$ and
$\mathcal{P}_{0}$ is a closed set, we have that $\gamma^{*}>0$. Let

$\displaystyle\Gamma^{*}=\\{P^{\prime}\in\mathcal{P}:\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{P^{\prime}}-\mu_{P}\big{\|}_{\mathcal{H}}\leq\gamma^{*}\\}.$
(65)

We then have that

$\displaystyle\Gamma^{*}=\bigcup_{P_{0}\in\mathcal{P}_{0}}U(P_{0},\gamma^{*})\subseteq\bigcup_{P_{0}\in\mathcal{P}_{0}}U(P_{0},\gamma(\epsilon,P_{0})).$
(66)

We then have that for any $P^{\prime}\in\Gamma^{*}$, there exists a
$P_{0}\in\mathcal{P}_{0}$ such that

$\displaystyle D(P^{\prime}\|P_{1})\geq D(P_{0}\|P_{1})-\epsilon.$ (67)

It then follows that there exists $P_{0}\in\mathcal{P}_{0}$ such that

$\displaystyle\inf_{P^{\prime}\in\Gamma^{*}}D(P^{\prime}\|P_{1})\geq
D(P_{0}\|P_{1})-\epsilon.$ (68)

We then have that for any $\epsilon>0$,

$\displaystyle\inf_{P^{\prime}\in\Gamma^{*}}D(P^{\prime}\|P_{1})\geq\inf_{P_{0}\in\mathcal{P}_{0}}D(P_{0}\|P_{1})-\epsilon.$
(69)

Since $\epsilon$ can be arbitrarily small, it then follows that

$\displaystyle\inf_{P_{1}\in\mathcal{P}_{1}}\lim_{n\rightarrow\infty}-\frac{1}{n}\log
P_{1}\Big{(}\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}\leq\gamma_{n}\Big{)}\geq\inf_{P_{0}\in\mathcal{P}_{0},P_{1}\in\mathcal{P}_{1}}D(P_{0}\|P_{1}).$
(70)

Combining (70) with Proposition 5, we have that

$\displaystyle\inf_{P_{1}\in\mathcal{P}_{1}}\lim_{n\rightarrow\infty}-\frac{1}{n}\log
E_{P_{1}}[1-\phi_{N}(x^{n})]$
$\displaystyle=\inf_{P_{1}\in\mathcal{P}_{1}}\lim_{n\rightarrow\infty}-\frac{1}{n}\log
P_{1}\Big{(}\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}\leq\gamma_{n}\Big{)}$
$\displaystyle=\sup_{\phi:P_{F}(\phi)\leq\alpha}\inf_{P_{1}\in\mathcal{P}_{1}}\lim_{n\rightarrow\infty}-\frac{1}{n}\log
E_{P_{1}}[1-\phi(x^{n})]$
$\displaystyle=\inf_{P_{0}\in\mathcal{P}_{0},P_{1}\in\mathcal{P}_{1}}D(P_{0}\|P_{1}).$
(71)

This completes the proof. ∎

The optimality result for the kernel robust test (57) in Theorem 2 holds for
general robust hypothesis testing problems, i.e., it applies to robust
hypothesis testing problems defined using different uncertainty sets
$\mathcal{P}_{0},\mathcal{P}_{1}$ and using any arbitrary nominal
distributions. However, to solve the optimization problem in the test
statistic
$\inf_{P\in\mathcal{P}_{0}}\big{\|}\mu_{\hat{P}_{n}}-\mu_{P}\big{\|}_{\mathcal{H}}$
for any arbitrary uncertainty set $\mathcal{P}_{0}$, it may not always be
tractable, since it is an infinite-dimensional problem.

##  V Simulation Results

In this section, we provide some numerical results to demonstrate the
performance of our proposed tests.

###  V-A Kernel Smoothing Test and Direct Robust Kernel Test

For the Bayesian setting, we compare the performance of our kernel smoothing
robust test $\tilde{\phi}$ in (22) and the direct robust kernel test
$\phi_{B}$ in (25). We choose the Gaussian kernel
$k(x,y)=\exp\big{(}-\frac{\|x-y\|^{2}}{2\sigma^{2}}\big{)}$ with the bandwidth
parameter $\sigma=1$. We first compare their performance under the
multivariate Gaussian distributions. We use $50$ samples from
$\mathcal{N}(\mathbf{0},\mathbf{I})$ and $50$ samples from
$\mathcal{N}(0.22\mathbf{e},\mathbf{I})$ to construct the uncertainty sets
under $H_{0}$ and $H_{1}$ respectively, where $\mathbf{e}$ is a vector with
all entries equal to 1, and $\mathbf{I}$ is the identity matrix. The data
dimension is 20. The radii are chosen such that the uncertainty sets do not
overlap. For the kernel smoothing robust test, we use training samples as the
support of the finite-dimensional robust optimization problem in (11). We then
use the data-generating distributions to evaluate the performance of the two
tests. We plot the log of the error probability under the Bayesian setting as
a function of testing sample size $n$. It can be seen from Fig. 1 that our
kernel smoothing robust test has a better performance than the direct robust
kernel test. Moreover, with the increasing of sample size $n$, the error
probabilities of the direct robust kernel test and kernel smoothing robust
test decay exponentially fast, which validates the theoretical result that the
direct robust kernel test is exponentially consistent.

Figure 1: Comparison of the Kernel Smoothing Robust Test and the Direct Robust
Kernel Test on Synthetic Dataset.

We then validate the performance of our robust tests using real data collected
from human activity detection. The dataset was released by the Wireless Sensor
Data Mining (WISDM) Lab in October 2013, which was collected with the
Actitracker system [50, 51, 52]. Users carried smartphone and were asked to do
different activities. For each person, the dataset records the user’s name,
activities and the acceleration of the user in three directions. We use the
jogging data collected from the person indexed by 685 and the walking data
collected from the person indexed by 669 to form $H_{0}$ and $H_{1}$
respectively. A small portion of the data is used to construct the uncertainty
sets. The radius $\theta$ of the uncertainty sets is chosen to be 0.03. We
plot the log scale error probability as a function of testing sample size $n$.
In Fig. 2, we have that the performance of the kernel smoothing robust test is
better than the direct robust kernel test. Moreover, from Fig. 2, it can be
seen that the error probabilities of the kernel smoothing robust test and the
direct robust kernel test decay exponentially fast with sample size $n$, which
validates our theoretical results.

Figure 2: Comparison of the Kernel Smoothing Robust Test and the Direct Robust
Kernel Test on the Real Dataset.

###  V-B Robust Kernel Test

For the Neyman-Pearson setting, we show the good performance of our robust
kernel test. We first demonstrate the performance of our tests using
multivariate Gaussian distributions. For hypotheses $H_{0}$, we use $50$
samples generated from a multivariate Gaussian distribution with mean
$[0,0,0,0]$ and covariance matrix $[[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]$
to construct the uncertainty set. For $H_{1}$, we use $50$ samples generated
from multi-variate Gaussian distribution with a different mean
$[0.5,0.5,0.5,0.5]$ and the same covariance matrix to construct the
uncertainty set. The radius $\theta$ of the uncertainty sets is set to be
$0.12$. The choice of $\theta$ guarantees that the uncertainty sets
$\mathcal{P}_{0}$ and $\mathcal{P}_{1}$ do not overlap.

To test the robustness of our tests, we choose an arbitrary pair of
distributions $P_{0}$, $P_{1}$ that lie on the boundary of the uncertainty
sets $\mathcal{P}_{0}$, $\mathcal{P}_{1}$. The reason we did not simulate the
worst-case is due to the challenge that for our problem the LFDs are not
directly solvable. Specifically, $P_{0}$ and $P_{1}$ are multi-variate
Gaussian distributions with mean matrix $[0.1,0.1,0.1,0.1]$ and
$[0.4,0.4,0.4,0.4]$, respectively, and with the same covariance matrix. For
this case, the tests based on the KL divergence uncertainty sets [6] are not
applicable since test samples are not supported on the training samples almost
surely.

(a) Type-I error v.s. sample size

(b) Type-II error v.s. sample size.

Figure 3: Error Probability of Robust Kernel Test on Synthetic Dataset.

We set the false alarm constraint $\alpha=0.1$. With a proper choice of
threshold, in Fig. 3(a), we plot the type-I error probability as a function of
sample size $n$. We repeat the experiment for 10000 times. In Fig. 3(b), we
plot the the type-II error probability as a function of sample size $n$. It
can be seen that the type-II error probability of our robust kernel test
decays exponentially fast with the sample size $n$ while the type-I error
probability satisfies the false alarm constraint.

We then use the real data set as in Section V-A to demonstrate the performance
of our robust kernel test. We use the walking data collected from the person
indexed by 685 and the walking data collected from the person indexed by 669
to form hypotheses $H_{0}$ and $H_{1}$. A small portion of the data is used to
construct the uncertainty sets. The radius $\theta$ of the uncertainty sets is
chosen to be 0.1 so that the two uncertainty sets do not overlap.

We set the false alarm constraint $\alpha=0.1$. With a proper choice of
threshold, we plot the type-I and type-II error probability as a function of
sample size $n$. From Fig. 4, it can be seen that the type-II error
probability of our robust kernel test decays exponentially fast with sample
size $n$ while the type-I error probability satisfies the false alarm
constraint.

(a) Type-I error v.s. sample size

(b) Type-II error v.s. sample size.

Figure 4: Error Probability of Robust Kernel Test on the Real Dataset.

##  VI Conclusion

In this paper, we studied the robust hypothesis testing problem. We proposed a
data-driven approach to construct the uncertainty sets using distance between
kernel mean embeddings of distributions. Under the Bayesian setting, we first
found the optimal test for the case with a finite alphabet. For the case with
an infinite alphabet, we proposed a tractable approximation to quantify the
worst-case error probability, and we developed a kernel smoothing method to
generalize to unseen data in the alphabet. We also developed a direct robust
kernel test which was further shown to be exponentially consistent. Under the
Neyman-Pearson setting, we constructed a robust kernel test which can be
implemented efficiently and further proved that the proposed test is
asymptotically optimal. Specifically, we derived an universal upper bound on
the type-II error exponent, and then showed that our robust kernel test
achieved this universal upper bound. We also provided some numerical results
to demonstrate the performance of our tests. Our approaches provide useful
insights for robust hypothesis testing problems in high-dimensional setting.

In the future, it is of interest to investigate the robust multiple hypothesis
testing problem with kernel uncertainty sets, where the design of robust
detector is significantly more challenging. Another possible extension is to
consider the kernel robust sequential hypothesis testing. In this case, we aim
to minimize the worst-case probability of errors regarding the hypothesis
using as few samples as possible, for which a data-driven approach needs to be
developed.

##  Appendix A Useful Lemmas

In this section, we list some useful lemmas for our proof.

######  Lemma 2.

[26, 27] Assume $0\leq k(\cdot,\cdot)\leq K$. Given samples
$x^{n}=(x_{1},x_{2},\cdots,x_{n})$ i.i.d. generated from $P_{0}$, denote by
$\hat{{P}}_{n}$ the empirical distribution of $x^{n}$, we then have that

$\displaystyle
P_{0}\Big{(}\big{|}\big{|}\mu_{\hat{P}_{n}}-\mu_{P_{0}}\big{|}\big{|}_{\mathcal{H}}>\big{(}2K/n\big{)}^{1/2}+\epsilon\Big{)}\leq\exp\Big{(}-\frac{\epsilon^{2}n}{2K}\Big{)}.$

######  Lemma 3.

[53, 54] For any $P_{1}\in\mathcal{P}$, the KL-divergence $D(\cdot\|P_{1})$ is
a lower semi-continuous function with respect to the weak topology of
$\mathcal{P}$. That is, for any $\epsilon>0$, there exists a neighborhood
$U\subset\mathcal{P}$ of $P_{0}$ such that for any $P^{\prime}\in
U,D(P^{\prime}\|P_{1})\geq D(P_{0}\|P_{1})-\epsilon$ if
$D(P_{0}\|P_{1})<\infty$, and $D(P^{\prime}\|P_{1})\rightarrow\infty$ as
$P^{\prime}$ converges to $P_{0}$ if $D(P_{0}\|P_{1})=\infty$.

##  Appendix B Proof of Lemma1

###### Proof.

To prove Lemma 1, we will first show that
$\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx$ is concave in $p_{0},p_{1}$.
Let $B$ be the $\sigma$-field on $\mathcal{X}$. Let
$\mathcal{A}=\\{\mathcal{A}_{1},\mathcal{A}_{2},\cdots,\mathcal{A}_{|\mathcal{A}|}\\}$
be a finite partition of $\mathcal{X}$ which divides $\mathcal{X}$ into a
finite number of sets and $|\mathcal{A}|$ denotes the number of partitions in
$\mathcal{A}$. Denote by $\Pi$ the collection of all finite B-measurable
partitions. Let $P_{0}^{\mathcal{A}_{i}}=P_{0}(\mathcal{A}_{i})$ and
$P_{1}^{\mathcal{A}_{i}}=P_{1}(\mathcal{A}_{i})$ for
$i=1,2,\cdots,|\mathcal{A}|$. We will then prove that
$\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx=\inf_{\mathcal{A}\in\Pi}\sum_{i=1}^{|\mathcal{A}|}\min\big{\\{}P_{0}^{\mathcal{A}_{i}},P_{1}^{\mathcal{A}_{i}}\big{\\}}$,
and show the upper semi-continuity.

Step 1. Let $f_{0}(p_{0},p_{1})=p_{0}$ and $f_{1}(p_{0},p_{1})=p_{1}$. Since
$f_{0}(p_{0},p_{1})$ and $f_{1}(p_{0},p_{1})$ are linear in $p_{0},p_{1}$,
$\min\\{p_{0},p_{1}\\}$ is the minimum of two linear functions thus is
concave. Therefore, $\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx$ is concave
in $p_{0},p_{1}$.

Step 2. For any partitions $\mathcal{A}\in\Pi$, we have that
$\mathcal{A}_{i}\in B,\forall i\in\\{1,2,\cdots,|\mathcal{A}|\\}$. For any
$\mathcal{A}\in\Pi$, from the concavity of
$\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}$ and Jensen’s inequality [55], we
have that

$\displaystyle\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx\leq\sum_{i=1}^{|\mathcal{A}|}\min\big{\\{}P_{0}^{\mathcal{A}_{i}},P_{1}^{\mathcal{A}_{i}}\big{\\}}.$
(72)

We note that $0\leq\min\big{\\{}\frac{p_{0}(x)}{p_{1}(x)},1\big{\\}}\leq 1$.
Therefore, for any $\epsilon>0$, there exists a partition
$\\{\mathcal{A}_{1},\mathcal{A}_{2},\cdots,\mathcal{A}_{|\mathcal{A}|}\\}$
such that $\bigcup_{i=1}^{|\mathcal{A}|}\mathcal{A}_{i}=\mathcal{X}$ and
$\bar{h}_{i}-\underline{h}_{i}<\epsilon$, where
$\bar{h}_{i}=\sup_{x\in\mathcal{A}_{i}}\min\big{\\{}\frac{p_{0}(x)}{p_{1}(x)},1\big{\\}},\
\underline{h}_{i}=\inf_{x\in\mathcal{A}_{i}}\min\big{\\{}\frac{p_{0}(x)}{p_{1}(x)},1\big{\\}}$
for $i=1,2,\cdots,|\mathcal{A}|$. We then have that

$\displaystyle\int_{\mathcal{A}_{i}}\bar{h}_{i}p_{1}(x)dx\geq\int_{\mathcal{A}_{i}}\min\Big{\\{}\frac{p_{0}(x)}{p_{1}(x)},1\Big{\\}}p_{1}(x)dx\geq\int_{\mathcal{A}_{i}}\underline{h}_{i}p_{1}(x)dx.$
(73)

It follows that

$\displaystyle
P_{1}(\mathcal{A}_{i})\bar{h}_{i}\geq\int_{\mathcal{A}_{i}}\min\Big{\\{}\frac{p_{0}(x)}{p_{1}(x)},1\Big{\\}}p_{1}(x)dx\geq
P_{1}(\mathcal{A}_{i})\underline{h}_{i}.$ (74)

Moreover,

$\displaystyle P_{1}(\mathcal{A}_{i})\bar{h}_{i}\geq
P_{1}(\mathcal{A}_{i})\min\Big{\\{}\frac{P_{0}(\mathcal{A}_{i})}{P_{1}(\mathcal{A}_{i})},1\Big{\\}}\geq
P_{1}(\mathcal{A}_{i})\underline{h}_{i},$ (75)

where the first inequality is because when $\bar{h}_{i}=1$,
$\min\big{\\{}\frac{P_{0}(\mathcal{A}_{i})}{P_{1}(\mathcal{A}_{i})},1\big{\\}}\leq
1$, and when $\bar{h}_{i}=\sup_{\mathcal{A}_{i}}\frac{p_{0}(x)}{p_{1}(x)}$,
$\bar{h}_{i}=\frac{\bar{h}_{i}\int_{\mathcal{A}_{i}}p_{1}(x)dx}{\int_{\mathcal{A}_{i}}p_{1}(x)dx}\geq\frac{\int_{\mathcal{A}_{i}}p_{0}(x)dx}{\int_{\mathcal{A}_{i}}p_{1}(x)dx}=\frac{P_{0}(\mathcal{A}_{i})}{P_{1}(\mathcal{A}_{i})}$.
The second inequality can also be proved similarly.

It then follows from (74) and (75) that

$\displaystyle\bigg{|}P_{1}(\mathcal{A}_{i})\min\Big{\\{}\frac{P_{0}(\mathcal{A}_{i})}{P_{1}(\mathcal{A}_{i})},1\Big{\\}}-\int_{\mathcal{A}_{i}}\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx\bigg{|}\leq(\bar{h}_{i}-\underline{h}_{i})P_{1}(\mathcal{A}_{i})<\epsilon
P_{1}(\mathcal{A}_{i}).$ (76)

Therefore,

$\displaystyle\bigg{|}\sum_{i=1}^{|\mathcal{A}|}P_{1}(\mathcal{A}_{i})\min\Big{\\{}\frac{P_{0}(\mathcal{A}_{i})}{P_{1}(\mathcal{A}_{i})},1\Big{\\}}-\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx\bigg{|}\leq\epsilon.$
(77)

We then have that

$\displaystyle\sum_{i=1}^{|\mathcal{A}|}P_{1}(\mathcal{A}_{i})\min\Big{\\{}\frac{P_{0}(\mathcal{A}_{i})}{P_{1}(\mathcal{A}_{i})},1\Big{\\}}\leq\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx+\epsilon.$
(78)

Let $\epsilon\rightarrow 0$, we have that

$\displaystyle\inf_{\mathcal{A}\in\Pi}\sum_{i=1}^{|\mathcal{A}|}\min\big{\\{}P_{0}^{\mathcal{A}_{i}},P_{1}^{\mathcal{A}_{i}}\big{\\}}\leq\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx.$
(79)

Combining (72) and (79), we have that

$\displaystyle\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx=\inf_{\mathcal{A}\in\Pi}\sum_{i=1}^{|\mathcal{A}|}\min\big{\\{}P_{0}^{\mathcal{A}_{i}},P_{1}^{\mathcal{A}_{i}}\big{\\}}.$
(80)

Step 3. Let $C$ be the field of Borel sets of $\mathcal{X}$ that are sets of
continuity for both $P_{0}$ and $P_{1}$. It was shown in [56, Theorem 1] that
$C$ generates $B$ in the sense that $B$ is the smallest $\sigma$-field
containing $C$.

Let
$\mathcal{A}^{C}=\big{\\{}\mathcal{A}_{1}^{C},\mathcal{A}_{2}^{C},\cdots,\mathcal{A}^{C}_{|\mathcal{A}|}\big{\\}}$
be a finite partition of $\mathcal{X}$ such that $\mathcal{A}_{i}^{C}\in C,\
\forall i\in\\{1,2,\cdots,|\mathcal{A}|\\}$. Let $\Pi^{C}$ be the collection
of all such finite partitions. Since $\Pi^{C}\subseteq\Pi$, we have that

$\displaystyle\inf_{\mathcal{A}^{C}\in\Pi^{C}}\sum_{i=1}^{|\mathcal{A}^{C}|}\min\big{\\{}P_{0}^{\mathcal{A}_{i}^{C}},P_{1}^{\mathcal{A}_{i}^{C}}\big{\\}}\geq\inf_{\mathcal{A}\in\Pi}\sum_{i=1}^{|\mathcal{A}|}\min\big{\\{}P_{0}^{\mathcal{A}_{i}},P_{1}^{\mathcal{A}_{i}}\big{\\}}.$
(81)

Since $C$ generates $B$, applying Theorem D of section 13 [57] to the measure
$\nu=P_{0}+P_{1}$, for any $\epsilon>0$ and $\mathcal{A}\in\Pi$, we can find
$E_{i}^{\prime}\in C$ such that $P_{0}(\mathcal{A}_{i}\Delta
E_{i}^{\prime})\leq\nu(\mathcal{A}_{i}\Delta E_{i}^{\prime})\leq\epsilon$ and
$P_{1}(\mathcal{A}_{i}\Delta E_{i}^{\prime})\leq\nu(\mathcal{A}_{i}\Delta
E_{i}^{\prime})\leq\epsilon$, where $\Delta$ denotes the symmetric difference
between two sets. Define

$\displaystyle
E_{1}=E^{\prime}_{1},E_{2}=E_{2}^{\prime}-E_{1},\cdots,E_{|\mathcal{A}|-1}=E_{|\mathcal{A}|-1}^{\prime}-E_{1}\cup
E_{2}\cup\cdots\cup E_{|\mathcal{A}|-2},$ (82)

and

$\displaystyle E_{|\mathcal{A}|}=\mathcal{X}-E_{1}\cup E_{2}\cup\cdots\cup
E_{|\mathcal{A}|-1}.$ (83)

We have that $\nu(\mathcal{A}_{1}\Delta E_{1})=\nu(\mathcal{A}_{1}\Delta
E^{\prime}_{1})\leq\epsilon$. Since
$\mathcal{A}_{1},\mathcal{A}_{2},\cdots,\mathcal{A}_{|\mathcal{A}|}$ are
disjoint, we have that $\nu(A_{2}\cap E_{1})\leq\epsilon$. It then follows
that

$\displaystyle\nu(\mathcal{A}_{2}\Delta
E_{2})=\nu\big{(}\mathcal{A}_{2}\Delta(E_{2}^{\prime}-E_{1})\big{)}\leq\nu(\mathcal{A}_{2}\Delta
E_{2}^{\prime})+\nu(\mathcal{A}_{2}\cap E_{1})\leq 2\epsilon.$ (84)

Similarly, we can show that for any $1\leq i\leq|\mathcal{A}|-1$,

$\displaystyle\nu(\mathcal{A}_{i}\Delta
E_{i})=\nu\big{(}\mathcal{A}_{i}\Delta(E_{i}^{\prime}-E_{1}\cup
E_{2}\cup\cdots\cup E_{i-1})\big{)}\leq i\epsilon$ (85)

and

$\displaystyle\nu(\mathcal{A}_{|\mathcal{A}|}\Delta E_{|\mathcal{A}|})=$
$\displaystyle\nu\big{(}(\mathcal{X}-\mathcal{A}_{1}\cup\mathcal{A}_{2}\cup\mathcal{A}_{|\mathcal{A}|-1})\Delta(\mathcal{X}-E_{1}\cup
E_{2}\cup\cdots\cup E_{|\mathcal{A}|-1})\big{)}$ $\displaystyle=$
$\displaystyle\nu\big{(}(\mathcal{A}_{1}\cup\mathcal{A}_{2}\cup\mathcal{A}_{|\mathcal{A}|-1})\Delta(E_{1}\cup
E_{2}\cup\cdots\cup
E_{|\mathcal{A}|-1})\big{)}\leq\frac{|\mathcal{A}|(|\mathcal{A}|-1)}{2}\epsilon.$
(86)

Therefore, for any $\epsilon>0$ and $\mathcal{A}\in\Pi$, there exists
$E_{1},E_{2},\cdots,E_{|\mathcal{A}|}\in C$ such that

$\displaystyle P_{0}(E_{i})\leq
P_{0}(\mathcal{A}_{i})+\frac{|\mathcal{A}|(|\mathcal{A}|-1)}{2}\epsilon,P_{1}(E_{i})\leq
P_{1}(\mathcal{A}_{i})+\frac{|\mathcal{A}|(|\mathcal{A}|-1)}{2}\epsilon,\forall
1\leq i\leq|\mathcal{A}|.$ (87)

It then follows that there exists $\mathcal{A}^{C}\in\Pi^{C}$ such that

$\displaystyle\sum_{i=1}^{|\mathcal{A}^{C}|}\min\big{\\{}P_{0}^{\mathcal{A}_{i}^{C}},P_{1}^{\mathcal{A}_{i}^{C}}\big{\\}}\leq\inf_{\mathcal{A}\in\Pi}\sum_{i=1}^{|\mathcal{A}|}\min\big{\\{}P_{0}^{\mathcal{A}_{i}},P_{1}^{\mathcal{A}_{i}}\big{\\}}+\frac{|\mathcal{A}|^{2}(|\mathcal{A}|-1)}{2}\epsilon.$
(88)

Let $\epsilon\rightarrow 0$ and use (81), we then have that

$\displaystyle\inf_{\mathcal{A}^{C}\in\Pi^{C}}\sum_{i=1}^{|\mathcal{A}^{C}|}\min\big{\\{}P_{0}^{\mathcal{A}_{i}^{C}},P_{1}^{\mathcal{A}_{i}^{C}}\big{\\}}=\inf_{\mathcal{A}\in\Pi}\sum_{i=1}^{|\mathcal{A}|}\min\big{\\{}P_{0}^{\mathcal{A}_{i}},P_{1}^{\mathcal{A}_{i}}\big{\\}}.$
(89)

Therefore,

$\displaystyle\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx=\inf_{\mathcal{A}^{C}\in\Pi^{C}}\sum_{i=1}^{|\mathcal{A}^{C}|}\min\big{\\{}P_{0}^{\mathcal{A}_{i}^{C}},P_{1}^{\mathcal{A}_{i}^{C}}\big{\\}}.$
(90)

Let $P_{0}^{s}$ and $P_{1}^{s}$ be the sequence of probability distribution
such that $P_{0}^{s}$ converges weakly to $P_{0}$ and $P_{1}^{s}$ converges
weakly to $P_{1}$ as $s\rightarrow\infty$. Let
$\mathcal{A}^{C}=\big{\\{}\mathcal{A}_{1}^{C},\mathcal{A}_{2}^{C},\cdots\mathcal{A}_{|\mathcal{A}|}\big{\\}}\in\Pi^{C}$.
We then have that $\mathcal{A}^{C}_{i}\in C$ for all
$i\in\\{1,2,\cdots,|\mathcal{A}|\\}$. From the Portmanteau theorem [58] and
the fact that $\mathcal{A}_{i}^{C}$ is a continuity set of $P_{0}$ and
$P_{1}$, the weak convergence implies
$P_{0}^{s}(\mathcal{A}_{i}^{C})\rightarrow P_{0}(\mathcal{A}_{i}^{C})$ and
$P_{1}^{s}(\mathcal{A}_{i}^{C})\rightarrow P_{1}(\mathcal{A}_{i}^{C})$. It
then follows that for any $\epsilon>0$, there exists $s_{0}$ such that for any
$s>s_{0}$,

$\displaystyle
P_{0}(\mathcal{A}_{i}^{C})+\frac{\epsilon}{|\mathcal{A}^{C}|}>P_{0}^{s}(\mathcal{A}_{i}^{C}),P_{1}(\mathcal{A}_{i}^{C})+\frac{\epsilon}{|\mathcal{A}^{C}|}>P_{1}^{s}(\mathcal{A}_{i}^{C}).$
(91)

Therefore, for any $\epsilon>0$, there exists $\mathcal{A}^{C}\in\Pi^{C}$ such
that

$\displaystyle\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx+2\epsilon$
$\displaystyle\geq\sum_{i=1}^{|\mathcal{A}^{C}|}\min\big{\\{}P_{0}^{\mathcal{A}^{C}_{i}},P_{1}^{\mathcal{A}^{C}_{i}}\big{\\}}+\epsilon$
$\displaystyle=\sum_{i=1}^{|\mathcal{A}^{C}|}\min\bigg{\\{}P_{0}^{\mathcal{A}^{C}_{i}}+\frac{\epsilon}{|\mathcal{A}^{C}|},P_{1}^{\mathcal{A}^{C}_{i}}+\frac{\epsilon}{|\mathcal{A}^{C}|}\bigg{\\}}$
$\displaystyle\geq\lim_{s\rightarrow\infty}\sum_{i=1}^{|\mathcal{A}^{C}|}\min\big{\\{}P_{0}^{s}(\mathcal{A}^{C}_{i}),P_{1}^{s}(\mathcal{A}^{C}_{i})\big{\\}}$
$\displaystyle\geq\lim_{s\rightarrow\infty}\int\min\big{\\{}p_{0}^{s}(x),p_{1}^{s}(x)\big{\\}}dx,$
(92)

where the first inequality is from (90), the last inequality is from (72). Let
$\epsilon\rightarrow 0$, we have that
$\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx$ is upper semi-continuous in
$P_{0},P_{1}$ with respect to the weak convergence. This completes the proof.
∎

##  Appendix C Proof of Theorem 2

###### Proof.

Since $\mathcal{X}$ is compact, $\mathcal{P}$ is tight, thus is sequentially
compact with respect to the topology of weak convergence from the Prokhorov’s
theorem [59]. Therefore, $\mathcal{P}$ is compact with respect to weak
convergence. Therefore, $\mathcal{P}_{0},\mathcal{P}_{1}$ are compact since
$\mathcal{P}_{0},\mathcal{P}_{1}$ are closed subsets of a compact set. We then
have that the solutions to
$\sup_{P_{0}\in\mathcal{P}_{0},P_{1}\in\mathcal{P}_{1}}\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx$
exist because upper semi-continuous function attains its supremum on a compact
set. Let $P_{0}^{*},P_{1}^{*}$ denote the optimal solutions to
$\sup_{P_{0}\in\mathcal{P}_{0},P_{1}\in\mathcal{P}_{1}}\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx$.

Let
$\mathcal{A}_{s}=\\{\mathcal{A}_{s}^{1},\mathcal{A}_{s}^{2},\cdots,\mathcal{A}_{s}^{s}\\}$
be a partition of $\mathcal{X}$. We define the diameter of each partition
$\mathcal{A}_{s}^{i}$ as
$dia(\mathcal{A}_{s}^{i})=\sup_{x,y\in\mathcal{A}_{s}^{i}}\|x-y\|_{2}$. Since
$\mathcal{X}$ is compact, we can choose the partition $\mathcal{A}_{s}$ such
that $dia(\mathcal{A}_{s}^{i})\rightarrow 0$ as $s\rightarrow\infty$ for
$1\leq i\leq s$.

For any partition $\mathcal{A}_{s}^{j}$, let $x_{s}^{j}$ be an arbitrary point
in $\mathcal{A}_{s}^{j}$. Denote by $P_{0}^{s},P_{1}^{s}$ discrete
distributions with
$P_{0}^{s}(x_{s}^{j})=P_{0}^{*}(\mathcal{A}_{s}^{j}),P_{1}^{s}(x_{s}^{j})=P_{1}^{*}(\mathcal{A}_{s}^{j})$.
Let $g:\mathcal{X}\rightarrow\mathbb{R}$ be an arbitrary bounded, continuous
function. Let $a_{s}^{j}=\inf_{x\in\mathcal{A}_{s}^{j}}g(x)$ and
$b_{s}^{j}=\sup_{x\in\mathcal{A}_{s}^{j}}g(x)$. Since $g$ is continuous and
the diameter of $\mathcal{A}_{s}^{j}$ goes to $0$ as $s\rightarrow\infty$, we
then have that $\max_{j=1,\cdots,s}(b_{s}^{j}-a_{s}^{j})\rightarrow 0$ as
$s\rightarrow\infty$. It then follows that

$\displaystyle\Big{|}\int gdP_{0}^{s}-\int
gdP_{0}^{*}\Big{|}=\Big{|}\sum_{j=1}^{s}\int_{\mathcal{A}_{s}^{j}}\big{(}g-g(x_{s}^{j})\big{)}dP_{0}^{*}\Big{|}$
$\displaystyle\leq\max_{j=1,\cdots,s}(b_{s}^{j}-a_{s}^{j})\rightarrow 0,\
\text{as}\ s\rightarrow\infty.$ (93)

Therefore, $P_{0}^{s}$ converges weakly to $P_{0}^{*}$ as
$s\rightarrow\infty$. Similarly, $P_{1}^{s}$ converges weakly to $P_{1}^{*}$
as $s\rightarrow\infty$. Moreover, from Jensen’s inequality [55], we have that

$\displaystyle\int\min\big{\\{}p_{0}^{*}(x),p_{1}^{*}(x)\big{\\}}dx\leq\sum_{j=1}^{s}\min\big{\\{}P_{0}^{*}(\mathcal{A}_{s}^{j}),P_{1}^{*}(\mathcal{A}_{s}^{j})\big{\\}}$
$\displaystyle=\sum_{j=1}^{s}\min\big{\\{}P_{0}^{s}(x^{j}_{s}),P_{1}^{s}(x^{j}_{s})\big{\\}}.$
(94)

Since MMD metrizes the weak convergence [44, 45], for any $\epsilon>0$, there
exists an integer $s_{0}$ such that for any $s>s_{0}$,
$\big{\|}\mu_{P_{0}^{s}}-\mu_{P_{0}^{*}}\big{\|}_{\mathcal{H}}\leq\frac{\epsilon}{2}$
and
$\big{\|}\mu_{P_{1}^{s}}-\mu_{P_{1}^{*}}\big{\|}_{\mathcal{H}}\leq\frac{\epsilon}{2}$.
Therefore, from the triangle inequality [25], we have that for any $s>s_{0}$,

$\displaystyle\big{\|}\mu_{P_{0}^{s}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}\leq\big{\|}\mu_{P_{0}^{s}}-\mu_{P_{0}^{*}}\big{\|}_{\mathcal{H}}+\big{\|}\mu_{P_{0}^{*}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}\leq\theta+\frac{\epsilon}{2}.$
(95)

Similarly, we have
$\big{\|}\mu_{P_{1}^{s}}-\mu_{\hat{Q}^{1}_{m}}\big{\|}_{\mathcal{H}}\leq\theta+\frac{\epsilon}{2}$.

Rewrite
$P_{0}^{s}=\sum_{j=1}^{s}\alpha_{j}\delta_{x_{s}^{j}},P_{1}^{s}=\sum_{j=1}^{s}\beta_{j}\delta_{x_{s}^{j}}$,
where $\delta_{x_{s}^{j}}$ denote the Dirac measure on $x_{s}^{j}$,
$\alpha_{j}=P^{*}_{0}(\mathcal{A}_{s}^{j}),\beta_{j}=P^{*}_{1}(\mathcal{A}^{j}_{s}),\forall
j=1,\cdots,s$, and $\sum_{j=1}^{s}\alpha_{j}=1,\sum_{j=1}^{s}\beta_{j}=1$. Let
$dis(x,y)$ denote a distance metric on $\mathcal{X}$ between $x$ and $y$. Note
that $\\{z_{i}\\}_{i=1}^{N}$ are generated from a distribution $P$ supported
on $\mathcal{X}$. Therefore, for any $x_{s}^{j}$, we have that
$\min_{z\in\\{z_{i}\\}_{i=1}^{N}}dis(z,x_{s}^{j})\rightarrow 0$ as
$N\rightarrow\infty$. Therefore, there exists a sequence
$\\{z_{sj}^{N}\\}_{N=1}^{\infty}$ such that
$z_{sj}^{N}\in\\{z_{i}\\}_{i=1}^{N}$ and $dis(z_{sj}^{N},x_{s}^{j})\rightarrow
0$ as $N\rightarrow\infty$. Assume that $z_{sj}^{N}$ are distinct for all $j$.
We then construct the following distributions:
$P_{0}^{s,N}=\sum_{j=1}^{s}\alpha_{j}\delta_{z_{sj}^{N}},P_{1}^{s,N}=\sum_{j=1}^{s}\beta_{j}\delta_{z_{sj}^{N}}$.
For any arbitrary bounded, continuous function
$g:\mathcal{X}\rightarrow\mathbb{R}$, since
$dis(z_{sj}^{N},x_{s}^{j})\rightarrow 0$ as $N\rightarrow\infty$, we have that
for a fixed $s$,

$\displaystyle\Big{|}\int gdP_{0}^{s,N}-\int
gdP_{0}^{s}\Big{|}=\Big{|}\sum_{j=1}^{s}\alpha_{j}\big{(}g(z^{N}_{sj})-g(x^{j}_{s})\big{)}\Big{|}$
$\displaystyle\leq\max_{j=1,\cdots,s}\big{|}g(z^{N}_{sj})-g(x^{j}_{s})\big{|}\rightarrow
0,\ \text{as}\ N\rightarrow\infty.$ (96)

Therefore, we have that $P_{0}^{s,N}$ converges weakly to $P_{0}^{s}$ as
$N\rightarrow\infty$. Similarly, $P_{1}^{s,N}$ converges weakly to $P_{1}^{s}$
as $N\rightarrow\infty$. Moreover, we have that

$\displaystyle\sum_{j=1}^{s}\min\big{\\{}P_{0}^{s,N}(z_{sj}^{N}),P_{1}^{s,N}(z_{sj}^{N})\big{\\}}=\sum_{j=1}^{s}\min\big{\\{}P_{0}^{s}(x^{j}_{s}),P_{1}^{s}(x^{j}_{s})\big{\\}}=\sum_{j=1}^{s}\min\\{\alpha_{j},\beta_{j}\\}.$
(97)

Since $P_{0}^{s},P_{1}^{s}$ converges weakly to $P_{0}^{*},P_{1}^{*}$,
respectively, as $s\rightarrow\infty$, and $P_{0}^{s,N},P_{1}^{s,N}$ converges
weakly to $P_{0}^{s},P_{1}^{s}$, respectively, as $N\rightarrow\infty$, we
have that for any $\epsilon>0$, there exists an integer $s_{0}$ such that for
all $s>s_{0}$,
$\big{\|}\mu_{P_{0}^{s}}-\mu_{P_{0}^{*}}\big{\|}_{\mathcal{H}}\leq\frac{\epsilon}{2}$
and
$\big{\|}\mu_{P_{1}^{s}}-\mu_{P_{1}^{*}}\big{\|}_{\mathcal{H}}\leq\frac{\epsilon}{2}$.
For a fixed $s>s_{0}$, there exists an integer $N(s)$ such that for any
$N>N(s)$,
$\big{\|}\mu_{P_{0}^{s,N}}-\mu_{P_{0}^{s}}\big{\|}_{\mathcal{H}}\leq\frac{\epsilon}{2}$
and
$\big{\|}\mu_{P_{1}^{s,N}}-\mu_{P_{1}^{s}}\big{\|}_{\mathcal{H}}\leq\frac{\epsilon}{2}$.
Therefore, for a fixed $s>s_{0}$ and any $N>N(s)$, from the triangle
inequality [25], we have that

$\displaystyle\big{\|}\mu_{P_{0}^{s,N}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}$
$\displaystyle\leq\big{\|}\mu_{P_{0}^{s,N}}-\mu_{P_{0}^{s}}\big{\|}_{\mathcal{H}}+\big{\|}\mu_{P_{0}^{s}}-\mu_{P_{0}^{*}}\big{\|}_{\mathcal{H}}+\big{\|}\mu_{P_{0}^{*}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}$
$\displaystyle\leq\theta+\epsilon.$ (98)

Similarly, we have that
$\big{\|}\mu_{P_{1}^{s,N}}-\mu_{\hat{Q}^{1}_{m}}\big{\|}_{\mathcal{H}}\leq\theta+\epsilon$.
It then follows that for large $N$,

$\displaystyle\sup_{\begin{subarray}{c}P_{0}^{N}\in\mathcal{P}:\big{\|}\mu_{P_{0}^{N}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}\leq\theta+\epsilon\\\
P_{1}^{N}\in\mathcal{P}:\big{\|}\mu_{P_{1}^{N}}-\mu_{\hat{Q}^{1}_{m}}\big{\|}_{\mathcal{H}}\leq\theta+\epsilon\\\
P_{0}^{N},P_{1}^{N}\ \text{are supported on}\
\\{z_{i}\\}_{i=1}^{N}\end{subarray}}\sum_{i=1}^{N}\min\big{\\{}P_{0}^{N}(z_{i}),P_{1}^{N}(z_{i})\big{\\}}$
$\displaystyle\geq\sum_{j=1}^{s}\min\big{\\{}P_{0}^{s,N}(z_{sj}^{N}),P_{1}^{s,N}(z_{sj}^{N})\big{\\}}$
$\displaystyle\geq\int\min\big{\\{}p_{0}^{*}(x),p_{1}^{*}(x)\big{\\}}dx,$ (99)

where the second inequality is from Jensen’s inequality [55]. Therefore, for
any $\epsilon>0$,

$\displaystyle\lim_{N\rightarrow\infty}\sup_{\begin{subarray}{c}P_{0}^{N}\in\mathcal{P}:\big{\|}\mu_{P_{0}^{N}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}\leq\theta+\epsilon\\\
P_{1}^{N}\in\mathcal{P}:\big{\|}\mu_{P_{1}^{N}}-\mu_{\hat{Q}^{1}_{m}}\big{\|}_{\mathcal{H}}\leq\theta+\epsilon\\\
P_{0}^{N},P_{1}^{N}\ \text{are supported on}\
\\{z_{i}\\}_{i=1}^{N}\end{subarray}}\sum_{i=1}^{N}\min\big{\\{}P_{0}^{N}(z_{i}),P_{1}^{N}(z_{i})\big{\\}}\geq\int\min\big{\\{}p_{0}^{*}(x),p_{1}^{*}(x)\big{\\}}dx.$
(100)

Moreover, we have that for any $\epsilon>0$,

$\displaystyle\sup_{\begin{subarray}{c}P_{0}\in\mathcal{P}:\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}\leq\theta+\epsilon\\\
P_{1}\in\mathcal{P}:\big{\|}\mu_{P_{1}}-\mu_{\hat{Q}^{1}_{m}}\big{\|}_{\mathcal{H}}\leq\theta+\epsilon\end{subarray}}\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx$
$\displaystyle\geq\lim_{N\rightarrow\infty}\sup_{\begin{subarray}{c}P_{0}^{N}\in\mathcal{P}:\big{\|}\mu_{P_{0}^{N}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}\leq\theta+\epsilon\\\
P_{1}^{N}\in\mathcal{P}:\big{\|}\mu_{P_{1}^{N}}-\mu_{\hat{Q}^{1}_{m}}\big{\|}_{\mathcal{H}}\leq\theta+\epsilon\\\
P_{0}^{N},P_{1}^{N}\ \text{are supported on}\
\\{z_{i}\\}_{i=1}^{N}\end{subarray}}\sum_{i=1}^{N}\min\big{\\{}P_{0}^{N}(z_{i}),P_{1}^{N}(z_{i})\big{\\}},$
(101)

which is due to the fact that the right-hand side and the left-hand side of
(C) have the same objective function and the feasible region of the right-hand
side is a subset of the feasible region of the left-hand side. It then follows
that

$\displaystyle\lim_{\epsilon\rightarrow
0}\sup_{\begin{subarray}{c}P_{0}\in\mathcal{P}:\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}\leq\theta+\epsilon\\\
P_{1}\in\mathcal{P}:\big{\|}\mu_{P_{1}}-\mu_{\hat{Q}^{1}_{m}}\big{\|}_{\mathcal{H}}\leq\theta+\epsilon\end{subarray}}\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx$
$\displaystyle\geq\lim_{\epsilon\rightarrow
0}\lim_{N\rightarrow\infty}\sup_{\begin{subarray}{c}P_{0}^{N}\in\mathcal{P}:\big{\|}\mu_{P_{0}^{N}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}\leq\theta+\epsilon\\\
P_{1}^{N}\in\mathcal{P}:\big{\|}\mu_{P_{1}^{N}}-\mu_{\hat{Q}^{1}_{m}}\big{\|}_{\mathcal{H}}\leq\theta+\epsilon\\\
P_{0}^{N},P_{1}^{N}\ \text{are supported on}\
\\{z_{i}\\}_{i=1}^{N}\end{subarray}}\sum_{i=1}^{N}\min\big{\\{}P_{0}^{N}(z_{i}),P_{1}^{N}(z_{i})\big{\\}}$
$\displaystyle\geq\int\min\big{\\{}p_{0}^{*}(x),p_{1}^{*}(x)\big{\\}}dx.$
(102)

We will then show that all the inequality holds with equality in (C). Define

$\displaystyle
g(\theta)=\sup_{\begin{subarray}{c}P_{0}\in\mathcal{P}:\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}\leq\theta\\\
P_{1}\in\mathcal{P}:\big{\|}\mu_{P_{1}}-\mu_{\hat{Q}^{1}_{m}}\big{\|}_{\mathcal{H}}\leq\theta\end{subarray}}\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx.$
(103)

We will show that $\lim_{\epsilon\rightarrow 0}g(\theta+\epsilon)=g(\theta)$,
thus

$\displaystyle\lim_{\epsilon\rightarrow
0}\sup_{\begin{subarray}{c}P_{0}\in\mathcal{P}:\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}\leq\theta+\epsilon\\\
P_{1}\in\mathcal{P}:\big{\|}\mu_{P_{1}}-\mu_{\hat{Q}^{1}_{m}}\big{\|}_{\mathcal{H}}\leq\theta+\epsilon\end{subarray}}\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx=\int\min\big{\\{}p_{0}^{*}(x),p_{1}^{*}(x)\big{\\}}dx.$
(104)

It suffices to show that $g(\theta)$ is continuous in $\theta$. To show that,
we will show that $g(\theta)$ is concave in $\theta$. Let
$P_{0,\theta_{1}},P_{1,\theta_{1}}$ be the optimal solutions to
$g(\theta_{1})$ and $P_{0,\theta_{2}},P_{1,\theta_{2}}$ be the optimal
solutions to $g(\theta_{2})$. Consider $\lambda
P_{0,\theta_{1}}+(1-\lambda)P_{0,\theta_{2}},\lambda
P_{1,\theta_{1}}+(1-\lambda)P_{1,\theta_{2}}$ for $0<\lambda<1$. From the
triangle inequality [25], we have that

$\displaystyle\|\lambda\mu_{P_{0,\theta_{1}}}+(1-\lambda)\mu_{P_{0,\theta_{2}}}-\mu_{\hat{Q}^{0}_{m}}\|_{\mathcal{H}}$
$\displaystyle\leq\lambda\|\mu_{P_{0,\theta_{1}}}-\mu_{\hat{Q}^{0}_{m}}\|_{\mathcal{H}}+(1-\lambda)\|\mu_{P_{0,\theta_{2}}}-\mu_{\hat{Q}^{0}_{m}}\|_{\mathcal{H}}$
$\displaystyle\leq\lambda\theta_{1}+(1-\lambda)\theta_{2}.$ (105)

Similarly, we have that
$\|\lambda\mu_{P_{1,\theta_{1}}}+(1-\lambda)\mu_{P_{1,\theta_{2}}}-\mu_{\hat{Q}^{1}_{m}}\|_{\mathcal{H}}\leq\lambda\theta_{1}+(1-\lambda)\theta_{2}$.
Therefore, $\lambda P_{0,\theta_{1}}+(1-\lambda)P_{0,\theta_{2}},\lambda
P_{1,\theta_{1}}+(1-\lambda)P_{1,\theta_{2}}$ are feasible solutions to
$g(\lambda\theta_{1}+(1-\lambda)\theta_{2})$. It then follows that

$\displaystyle g(\lambda\theta_{1}+(1-\lambda)\theta_{2})$
$\displaystyle\geq\int\min\big{\\{}\lambda
p_{0,\theta_{1}}(x)+(1-\lambda)p_{0,\theta_{2}}(x),\lambda
p_{1,\theta_{1}}(x)+(1-\lambda)p_{1,\theta_{2}}(x)\big{\\}}dx$
$\displaystyle\geq\lambda\int\min\big{\\{}p_{0,\theta_{1}}(x),p_{1,\theta_{1}}(x)\big{\\}}dx+(1-\lambda)\int\min\big{\\{}p_{0,\theta_{2}}(x),p_{1,\theta_{2}}(x)\big{\\}}dx$
$\displaystyle=\lambda g(\theta_{1})+(1-\lambda)g(\theta_{2}).$ (106)

Therefore, $g(\theta)$ is concave in $\theta$, and thus is continuous in
$\theta$. From (C) and the continuity of $g(\theta)$, we have that for any
$\theta\geq 0$,

$\displaystyle\lim_{\epsilon\rightarrow
0}\sup_{\begin{subarray}{c}P_{0}\in\mathcal{P}:\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}\leq\theta+\epsilon\\\
P_{1}\in\mathcal{P}:\big{\|}\mu_{P_{1}}-\mu_{\hat{Q}^{1}_{m}}\big{\|}_{\mathcal{H}}\leq\theta+\epsilon\end{subarray}}\int\min\big{\\{}p_{0}(x),p_{1}(x)\big{\\}}dx$
$\displaystyle=\lim_{\epsilon\rightarrow
0}\lim_{N\rightarrow\infty}\sup_{\begin{subarray}{c}P_{0}^{N}\in\mathcal{P}:\big{\|}\mu_{P_{0}^{N}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}\leq\theta+\epsilon\\\
P_{1}^{N}\in\mathcal{P}:\big{\|}\mu_{P_{1}^{N}}-\mu_{\hat{Q}^{1}_{m}}\big{\|}_{\mathcal{H}}\leq\theta+\epsilon\\\
P_{0}^{N},P_{1}^{N}\ \text{are supported on}\
\\{z_{i}\\}_{i=1}^{N}\end{subarray}}\sum_{i=1}^{N}\min\big{\\{}P_{0}^{N}(z_{i}),P_{1}^{N}(z_{i})\big{\\}}$
$\displaystyle=\int\min\big{\\{}p_{0}^{*}(x),p_{1}^{*}(x)\big{\\}}dx.$ (107)

We will then show that

$\displaystyle\lim_{N\rightarrow\infty}\sup_{\begin{subarray}{c}P_{0}^{N}\in\mathcal{P}:\big{\|}\mu_{P_{0}^{N}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}\leq\theta\\\
P_{1}^{N}\in\mathcal{P}:\big{\|}\mu_{P_{1}^{N}}-\mu_{\hat{Q}^{1}_{m}}\big{\|}_{\mathcal{H}}\leq\theta\\\
P_{0}^{N},P_{1}^{N}\ \text{are supported on}\
\\{z_{i}\\}_{i=1}^{N}\end{subarray}}\sum_{i=1}^{N}\min\big{\\{}P_{0}^{N}(z_{i}),P_{1}^{N}(z_{i})\big{\\}}$
$\displaystyle=\lim_{\epsilon\rightarrow
0}\lim_{N\rightarrow\infty}\sup_{\begin{subarray}{c}P_{0}^{N}\in\mathcal{P}:\big{\|}\mu_{P_{0}^{N}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}\leq\theta+\epsilon\\\
P_{1}^{N}\in\mathcal{P}:\big{\|}\mu_{P_{1}^{N}}-\mu_{\hat{Q}^{1}_{m}}\big{\|}_{\mathcal{H}}\leq\theta+\epsilon\\\
P_{0}^{N},P_{1}^{N}\ \text{are supported on}\
\\{z_{i}\\}_{i=1}^{N}\end{subarray}}\sum_{i=1}^{N}\min\big{\\{}P_{0}^{N}(z_{i}),P_{1}^{N}(z_{i})\big{\\}}.$
(108)

Define

$g_{N}(\theta)=\sup_{\begin{subarray}{c}P_{0}^{N}\in\mathcal{P}:\big{\|}\mu_{P_{0}^{N}}-\mu_{\hat{Q}^{0}_{m}}\big{\|}_{\mathcal{H}}\leq\theta\\\
P_{1}^{N}\in\mathcal{P}:\big{\|}\mu_{P_{1}^{N}}-\mu_{\hat{Q}^{1}_{m}}\big{\|}_{\mathcal{H}}\leq\theta\\\
P_{0}^{N},P_{1}^{N}\ \text{are supported on}\
\\{z_{i}\\}_{i=1}^{N}\end{subarray}}\sum_{i=1}^{N}\min\big{\\{}P_{0}^{N}(z_{i}),P_{1}^{N}(z_{i})\big{\\}}.$

Let $g^{*}(\theta)=\lim_{N\rightarrow\infty}g_{N}(\theta)$. This limit exists
because for any $\theta>0$, $\\{g_{N}(\theta)\\}_{N=1}^{\infty}$ is a non-
decreasing sequence and has upper bound $g(\theta)$.

For any $N$, denote by $P_{0,\theta_{1}}^{N},P_{1,\theta_{1}}^{N}$ the optimal
solutions to $g_{N}(\theta_{1})$ and
$P_{0,\theta_{2}}^{N},P_{1,\theta_{2}}^{N}$ the optimal solutions to
$g_{N}(\theta_{2})$. Consider $\lambda
P_{0,\theta_{1}}^{N}+(1-\lambda)P_{0,\theta_{2}}^{N},\lambda
P_{1,\theta_{1}}^{N}+(1-\lambda)P_{1,\theta_{2}}^{N}$ for $0<\lambda<1$. We
have that

$\displaystyle
g^{*}(\lambda\theta_{1}+(1-\lambda)\theta_{2})=\lim_{N\rightarrow\infty}g_{N}(\lambda\theta_{1}+(1-\lambda)\theta_{2})$
$\displaystyle\geq\lim_{N\rightarrow\infty}\sum_{i=1}^{N}\min\big{\\{}\lambda
P_{0,\theta_{1}}^{N}(z_{i})+(1-\lambda)P_{0,\theta_{2}}(z_{i}),\lambda
P_{1,\theta_{1}}^{N}(z_{i})+(1-\lambda)P_{1,\theta_{2}}(z_{i})\big{\\}}$
$\displaystyle\geq\lim_{N\rightarrow\infty}\lambda\sum_{i=1}^{N}\min\big{\\{}P_{0,\theta_{1}}^{N}(z_{i}),P_{1,\theta_{1}}^{N}(z_{i})\big{\\}}+(1-\lambda)\sum_{i=1}^{N}\min\big{\\{}P_{0,\theta_{2}}^{N}(z_{i}),P_{1,\theta_{2}}^{N}(z_{i})\big{\\}}$
$\displaystyle=\lambda\lim_{N\rightarrow\infty}\sum_{i=1}^{N}\min\big{\\{}P_{0,\theta_{1}}^{N}(z_{i}),P_{1,\theta_{1}}^{N}(z_{i})\big{\\}}+(1-\lambda)\lim_{N\rightarrow\infty}\sum_{i=1}^{N}\min\big{\\{}P_{0,\theta_{2}}^{N}(z_{i}),P_{1,\theta_{2}}^{N}(z_{i})\big{\\}}$
$\displaystyle=\lambda g^{*}(\theta_{1})+(1-\lambda)g^{*}(\theta_{2}),$ (109)

where the first equality is because the limits
$\lim_{N\rightarrow\infty}\sum_{i=1}^{N}\min\big{\\{}P_{0,\theta_{1}}^{N}(z_{i}),P_{1,\theta_{1}}^{N}(z_{i})\big{\\}}$
and
$\lim_{N\rightarrow\infty}\sum_{i=1}^{N}\min\big{\\{}P_{0,\theta_{2}}^{N}(z_{i}),P_{1,\theta_{2}}^{N}(z_{i})\big{\\}}$
exist. Therefore, $g^{*}(\theta)$ is concave in $\theta$, and thus is
continuous in $\theta$. From the continuity of $g^{*}(\theta)$ and (C), we
have that (C) holds. This completes the proof. ∎

##  Appendix D Proof of Proposition 4

###### Proof.

For any $P_{0}\in\mathcal{P}_{0}$, we have that

$\displaystyle E_{P_{0}}[\phi_{B}(x^{n})]$
$\displaystyle=P_{0}\Big{(}\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}-\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}\geq
0\Big{)}$
$\displaystyle=P_{0}\Big{(}\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}^{2}-\big{\|}\mu_{\hat{P}_{n}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}^{2}\geq
0\Big{)}$
$\displaystyle=P_{0}\Big{(}E_{x\sim\hat{P}_{n},x^{\prime}\sim\hat{P}_{n}}[k(x,x^{\prime})]+E_{y\sim\hat{Q}_{m}^{0},y^{\prime}\sim\hat{Q}_{m}^{0}}[k(y,y^{\prime})]-2E_{x\sim\hat{P}_{n},y\sim\hat{Q}_{m}^{0}}[k(x,y)]-E_{x\sim\hat{P}_{n},x^{\prime}\sim\hat{P}_{n}}[k(x,x^{\prime})]$
$\displaystyle\hskip 33.28966pt-
E_{y\sim\hat{Q}_{m}^{1},y^{\prime}\sim\hat{Q}_{m}^{1}}[k(y,y^{\prime})]+2E_{x\sim\hat{P}_{n},y\sim\hat{Q}_{m}^{1}}[k(x,y)]\geq
0\Big{)}$
$\displaystyle=P_{0}\Big{(}-\frac{2}{n}\sum_{j=1}^{n}\frac{1}{m}\sum_{i=1}^{m}k(x_{j},\hat{x}_{0,i})+\frac{2}{n}\sum_{j=1}^{n}\frac{1}{m}\sum_{i=1}^{m}k(x_{j},\hat{x}_{1,i})+E_{y\sim\hat{Q}_{m}^{0},y^{\prime}\sim\hat{Q}_{m}^{0}}[k(y,y^{\prime})]$
$\displaystyle\hskip 33.28966pt-
E_{y\sim\hat{Q}_{m}^{1},y^{\prime}\sim\hat{Q}_{m}^{1}}[k(y,y^{\prime})]\geq
0\Big{)}.$ (110)

We will then bound the error probability in (D) using the McDiarmid’s
inequality [60]. Define

$\displaystyle
F(x_{1},x_{2},\cdots,x_{n})=-\frac{2}{n}\sum_{j=1}^{n}\frac{1}{m}\sum_{i=1}^{m}k(x_{j},\hat{x}_{0,i})+\frac{2}{n}\sum_{j=1}^{n}\frac{1}{m}\sum_{i=1}^{m}k(x_{j},\hat{x}_{1,i}).$
(111)

To apply the McDiarmid’s inequality [60], we first need to bound

$\displaystyle\sup_{x_{1},\cdots,x_{j},\cdots,x_{n},x^{\prime}_{j}\in\mathcal{X}}\Big{(}F(x_{1},\cdots,x_{j},\cdots,x_{n})-F(x_{1},\cdots,x^{\prime}_{j},\cdots,x_{n})\Big{)},\forall
1\leq j\leq n.$ (112)

It can be shown that

$\displaystyle\sup_{x_{1},\cdots,x_{j},\cdots,x_{n},x^{\prime}_{j}\in\mathcal{X}}\Big{(}F(x_{1},\cdots,x_{j},\cdots,x_{n})-F(x_{1},\cdots,x^{\prime}_{j},\cdots,x_{n})\Big{)}$
$\displaystyle=\sup_{x_{1},\cdots,x_{j},\cdots,x_{n},x^{\prime}_{j}\in\mathcal{X}}\frac{2}{n}\Big{(}\frac{1}{m}\sum_{i=1}^{m}\big{(}k(x^{\prime}_{j},\hat{x}_{0,i})-k(x_{j},\hat{x}_{0,i})\big{)}+\frac{1}{m}\sum_{i=1}^{m}\big{(}k(x_{j},\hat{x}_{1,i})-k(x^{\prime}_{j},\hat{x}_{1,i})\big{)}\Big{)}$
$\displaystyle\leq\frac{4K}{n},$ (113)

where the last inequality is due to the fact that the kernel $k(\cdot,\cdot)$
is bounded. We will then consider the expectation of
$F(x_{1},x_{2},\cdots,x_{n})$. From similar steps in (D), it follows that

$\displaystyle
E_{P_{0}}\big{[}F(x_{1},x_{2},\cdots,x_{n})\big{]}+E_{y\sim\hat{Q}_{m}^{0},y^{\prime}\sim\hat{Q}_{m}^{0}}[k(y,y^{\prime})]-E_{y\sim\hat{Q}_{m}^{1},y^{\prime}\sim\hat{Q}_{m}^{1}}[k(y,y^{\prime})]$
$\displaystyle=\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}^{2}_{\mathcal{H}}-\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}^{2}_{\mathcal{H}}.$
(114)

Note that for any $P_{0}\in\mathcal{P}_{0}$, we have that
$\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}^{2}_{\mathcal{H}}-\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}^{2}_{\mathcal{H}}\leq
0$. It then follows that

$\displaystyle
P_{0}\Big{(}-\frac{2}{n}\sum_{j=1}^{n}\frac{1}{m}\sum_{i=1}^{m}k(x_{j},\hat{x}_{0,i})+\frac{2}{n}\sum_{j=1}^{n}\frac{1}{m}\sum_{i=1}^{m}k(x_{j},\hat{x}_{1,i})+E_{y\sim\hat{Q}_{m}^{0},y^{\prime}\sim\hat{Q}_{m}^{0}}[k(y,y^{\prime})]$
$\displaystyle\hskip 18.49411pt-
E_{y\sim\hat{Q}_{m}^{1},y^{\prime}\sim\hat{Q}_{m}^{1}}[k(y,y^{\prime})]\geq
0\Big{)}$
$\displaystyle=P_{0}\bigg{(}-\frac{2}{n}\sum_{j=1}^{n}\frac{1}{m}\sum_{i=1}^{m}k(x_{j},\hat{x}_{0,i})+\frac{2}{n}\sum_{j=1}^{n}\frac{1}{m}\sum_{i=1}^{m}k(x_{j},\hat{x}_{1,i})$
$\displaystyle\hskip 34.71239pt-
E_{P_{0}}\Big{[}-\frac{2}{n}\sum_{j=1}^{n}\frac{1}{m}\sum_{i=1}^{m}k(x_{j},\hat{x}_{0,i})+\frac{2}{n}\sum_{j=1}^{n}\frac{1}{m}\sum_{i=1}^{m}k(x_{j},\hat{x}_{1,i})\Big{]}$
$\displaystyle\hskip 34.71239pt\geq
E_{y\sim\hat{Q}_{m}^{1},y^{\prime}\sim\hat{Q}_{m}^{1}}[k(y,y^{\prime})]-E_{y\sim\hat{Q}_{m}^{0},y^{\prime}\sim\hat{Q}_{m}^{0}}[k(y,y^{\prime})]$
$\displaystyle\hskip 34.71239pt-
E_{P_{0}}\Big{[}-\frac{2}{n}\sum_{j=1}^{n}\frac{1}{m}\sum_{i=1}^{m}k(x_{j},\hat{x}_{0,i})+\frac{2}{n}\sum_{j=1}^{n}\frac{1}{m}\sum_{i=1}^{m}k(x_{j},\hat{x}_{1,i})\Big{]}\bigg{)}$
$\displaystyle=P_{0}\bigg{(}-\frac{2}{n}\sum_{j=1}^{n}\frac{1}{m}\sum_{i=1}^{m}k(x_{j},\hat{x}_{0,i})+\frac{2}{n}\sum_{j=1}^{n}\frac{1}{m}\sum_{i=1}^{m}k(x_{j},\hat{x}_{1,i})$
$\displaystyle\hskip 34.71239pt-
E_{P_{0}}\Big{[}-\frac{2}{n}\sum_{j=1}^{n}\frac{1}{m}\sum_{i=1}^{m}k(x_{j},\hat{x}_{0,i})+\frac{2}{n}\sum_{j=1}^{n}\frac{1}{m}\sum_{i=1}^{m}k(x_{j},\hat{x}_{1,i})\Big{]}$
$\displaystyle\hskip
34.71239pt\geq\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}^{2}_{\mathcal{H}}-\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}^{2}_{\mathcal{H}}\bigg{)}$
$\displaystyle\leq\exp\Bigg{(}-\frac{n\Big{(}\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}^{2}_{\mathcal{H}}-\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}^{2}_{\mathcal{H}}\Big{)}^{2}}{8K^{2}}\Bigg{)},$
(115)

where the last inequality is from the McDiarmid’s inequality [60]. We then
have that

$\displaystyle\sup_{P_{0}\in\mathcal{P}_{0}}E_{P_{0}}[\phi_{B}(x^{n})]\leq\sup_{P_{0}\in\mathcal{P}_{0}}\exp\Bigg{(}-\frac{n\Big{(}\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}^{2}_{\mathcal{H}}-\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}^{2}_{\mathcal{H}}\Big{)}^{2}}{8K^{2}}\Bigg{)}.$
(116)

Since
$\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}^{2}_{\mathcal{H}}-\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}^{2}_{\mathcal{H}}\geq
0$ and the exponential function is monotonically increasing, the optimization
problem on the right-hand side of (116) can be solved by solving
$\inf_{P_{0}\in\mathcal{P}_{0}}\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}^{2}_{\mathcal{H}}-\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}^{2}_{\mathcal{H}}$.
We then have that

$\displaystyle\inf_{P_{0}\in\mathcal{P}_{0}}\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}^{2}_{\mathcal{H}}-\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}^{2}_{\mathcal{H}}$
$\displaystyle=\inf_{P_{0}\in\mathcal{P}_{0}}\Big{(}\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}+\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}\Big{)}\Big{(}\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}-\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}\Big{)}.$
(117)

From the triangle inequality of MMD [25], we have that

$\displaystyle\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}+\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}\geq\big{\|}\mu_{\hat{Q}_{m}^{1}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}.$
(118)

Moreover, since
$\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}\leq\theta$,
it can be shown that

$\displaystyle\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}_{\mathcal{H}}-\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}\geq\big{\|}\mu_{\hat{Q}_{m}^{1}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}-2\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}\geq\big{\|}\mu_{\hat{Q}_{m}^{1}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}-2\theta.$
(119)

It then follows that

$\displaystyle\inf_{P_{0}\in\mathcal{P}_{0}}\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{1}}\big{\|}^{2}_{\mathcal{H}}-\big{\|}\mu_{P_{0}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}^{2}_{\mathcal{H}}\geq\big{\|}\mu_{\hat{Q}_{m}^{1}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}\Big{(}\big{\|}\mu_{\hat{Q}_{m}^{1}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}-2\theta\Big{)}.$
(120)

Therefore, we have that

$\displaystyle\sup_{P_{0}\in\mathcal{P}_{0}}E_{P_{0}}[\phi_{B}(x^{n})]\leq\exp\Bigg{(}-\frac{n\Big{(}\big{\|}\mu_{\hat{Q}_{m}^{1}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}^{2}-2\theta\big{\|}\mu_{\hat{Q}_{m}^{1}}-\mu_{\hat{Q}_{m}^{0}}\big{\|}_{\mathcal{H}}\Big{)}^{2}}{8K^{2}}\Bigg{)}.$
(121)

Following the same idea as in the proof of (49), (50) can also be proved. This
completes the proof. ∎

## References

  * [1] Z. Sun and S. Zou, “A data-driven approach to robust hypothesis testing using kernel MMD uncertainty sets,” in Proc. International Symposium on Information Theory (ISIT), pp. 3056–3061, 2021.
  * [2] P. Moulin and V. V. Veeravalli, Statistical Inference for Engineers and Data Scientists.  Cambridge University Press, 2018.
  * [3] T. M. Cover and J. A. Thomas, Elements of Information Theory.  New York, NY, USA: John Wiley & Sons, 2006.
  * [4] S. M. Kay, Fundamentals of Statistical Signal Processing.  Prentice Hall PTR, 1993.
  * [5] P. J. Huber, “A robust version of the probability ratio test,” Annals of Mathematical Statistics, vol. 36, no. 6, pp. 1753–1758, 1965.
  * [6] B. C. Levy, “Robust hypothesis testing with a relative entropy tolerance,” IEEE Transactions on Information Theory, vol. 55, no. 1, pp. 413–421, 2009\.
  * [7] G. Gül and A. M. Zoubir, “Minimax robust hypothesis testing,” IEEE Transactions on Information Theory, vol. 63, no. 9, pp. 5572–5587, 2017.
  * [8] R. Gao, L. Xie, Y. Xie, and H. Xu, “Robust hypothesis testing using Wasserstein uncertainty sets,” in Proc. Advances Neural Information Processing Systems (NeurIPS), pp. 7902–7912, 2018.
  * [9] L. Xie, R. Gao, and Y. Xie, “Robust hypothesis testing with Wasserstein uncertainty sets,” arXiv preprint arXiv:2105.14348, 2021.
  * [10] J. Wang and Y. Xie, “A data-driven approach to robust hypothesis testing using Sinkhorn uncertainty sets,” arXiv preprint arXiv:2202.04258, 2022.
  * [11] M. Barni and B. Tondi, “The source identification game: An information-theoretic perspective,” IEEE Transactions on Information Forensics and Security, vol. 8, no. 3, pp. 450–463, 2013.
  * [12] Y. Jin and L. Lai, “On the adversarial robustness of hypothesis testing,” IEEE Transactions on Signal Processing, vol. 69, pp. 515–530, 2021.
  * [13] H. Rieder, “Least favorable pairs for special capacities,” The Annals of Statistics, vol. 5, no. 5, pp. 909–921, 1977.
  * [14] F. Österreicher, “On the construction of least favourable pairs of distributions,” Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, vol. 43, pp. 49–55, 1978.
  * [15] T. Bednarski, “On solutions of minimax test problems for special capacities,” Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, vol. 58, pp. 397–405, 1981.
  * [16] R. Hafner, “Simple construction of least favourable pairs of distributions and of robust tests for Prokhorov-neighbourhoods,” Series Statistics, vol. 13, no. 1, pp. 33–46, 1982.
  * [17] S. Kassam, “Robust hypothesis testing for bounded classes of probability densities (corresp.),” IEEE Transactions on Information Theory, vol. 27, no. 2, pp. 242–247, 1981.
  * [18] R. Hafner, “Construction of minimax-tests for bounded families of probability-densities,” Metrika, vol. 40, no. 1, pp. 1–23, 1993.
  * [19] K. Vastola and H. Poor, “On the p-point uncertainty class (corresp.),” IEEE Transactions on Information Theory, vol. 30, no. 2, pp. 374–376, 1984.
  * [20] M. Fauß, A. M. Zoubir, and H. V. Poor, “Minimax robust detection: Classic results and recent advances,” IEEE Transactions on Signal Processing, vol. 69, pp. 2252–2283, 2021.
  * [21] N. Fournier and A. Guillin, “On the rate of convergence in Wasserstein distance of the empirical measure,” Probability Theory and Related Fields, vol. 162, no. 3, pp. 707–738, 2015.
  * [22] C. Pandit, S. Meyn, and V. Veeravalli, “Asymptotic robust Neyman-Pearson hypothesis testing based on moment classes,” in Proc. International Symposium on Information Theory (ISIT), p. 220, 2004.
  * [23] A. Berlinet and C. Thomas-Agnan, Reproducing Kernel Hilbert Spaces in Probability and Statistics.  Springer, 2004.
  * [24] B. Sriperumbudur, A. Gretton, K. Fukumizu, G. Lanckriet, and B. Sch$\ddot{\text{o}}$lkopf, “Hilbert space embeddings and metrics on probability measures,” Journal of Machine Learning Research, vol. 11, pp. 1517–1561, 2010.
  * [25] A. Gretton, K. M. Borgwardt, M. J. Rasch, B. Schölkopf, and A. Smola, “A kernel two-sample test,” Journal of Machine Learning Research, vol. 13, no. 25, pp. 723–773, 2012.
  * [26] Y. Altun and A. Smola, “Unifying divergence minimization and statistical inference via convex duality,” in Proc. Annual Conference on Learning Theory, pp. 139–153, 2006.
  * [27] Z. Szabó, A. Gretton, B. Póczos, and B. Sriperumbudur, “Two-stage sampled Learning theory on distributions,” in Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), vol. 38, pp. 948–957, 2015.
  * [28] K. Chwialkowski, A. Ramdas, D. Sejdinovic, and A. Gretton, “Fast two-sample testing with analytic representations of probability measures,” in Proc. Advances Neural Information Processing Systems (NeurIPS), p. 1981–1989, 2015.
  * [29] K. Fukumizu, A. Gretton, G. Lanckriet, B. Schölkopf, and B. K. Sriperumbudur, “Kernel choice and classifiability for RKHS embeddings of probability distributions,” in Proc. Advances Neural Information Processing Systems (NeurIPS), vol. 22, pp. 1750–1758, 2009.
  * [30] A. Gretton, K. Fukumizu, Z. Harchaoui, and B. K. Sriperumbudur, “A fast, consistent kernel two-sample test,” in Proc. Advances Neural Information Processing Systems (NeurIPS), vol. 22, pp. 673–681, 2009.
  * [31] A. Gretton, D. Sejdinovic, H. Strathmann, S. Balakrishnan, M. Pontil, K. Fukumizu, and B. K. Sriperumbudur, “Optimal kernel choice for large-scale two-sample tests,” in Proc. Advances Neural Information Processing Systems (NeurIPS), vol. 25, pp. 1205–1213, 2012.
  * [32] D. J. Sutherland, H. Tung, H. Strathmann, S. De, A. Ramdas, A. J. Smola, and A. Gretton, “Generative models and model criticism via optimized maximum mean discrepancy,” in Proc. International Conference on Learning Representations (ICLR), 2017.
  * [33] W. Zaremba, A. Gretton, and M. Blaschko, “B-test: A non-parametric, low variance kernel two-sample test,” in Proc. Advances Neural Information Processing Systems (NeurIPS), vol. 26, pp. 755–763, 2013.
  * [34] S. Zhu, B. Chen, Z. Chen, and P. Yang, “Asymptotically optimal one- and two-sample testing with kernels,” IEEE Transactions on Information Theory, vol. 67, no. 4, pp. 2074–2092, 2021.
  * [35] J. R. Lloyd and Z. Ghahramani, “Statistical model criticism using kernel two sample tests,” in Proc. Advances Neural Information Processing Systems (NeurIPS), vol. 28, pp. 829–837, 2015.
  * [36] B. Kim, R. Khanna, and O. O. Koyejo, “Examples are not enough, learn to criticize! Criticism for Interpretability,” in Proc. Advances Neural Information Processing Systems (NeurIPS), vol. 29, pp. 2288–2296, 2016\.
  * [37] S. Zou, Y. Liang, H. V. Poor, and X. Shi, “Nonparametric detection of anomalous data streams,” IEEE Transactions on Signal Processing, vol. 65, no. 21, pp. 5785–5797, 2017.
  * [38] S. Zou, Y. Liang, and H. V. Poor, “Nonparametric detection of geometric structures over networks,” IEEE Transactions on Signal Processing, vol. 65, no. 19, pp. 5034–5046, 2017.
  * [39] S. Li, Y. Xie, H. Dai, and L. Song, “M-statistic for kernel change-point detection,” in Proc. Advances Neural Information Processing Systems (NeurIPS), vol. 28, pp. 3366–3374, 2015.
  * [40] J.-J. Zhu, W. Jitkrittum, M. Diehl, and B. Schölkopf, “Kernel distributionally robust optimization: Generalized duality theorem and stochastic approximation,” in Proc. International Conference on Artifical Intelligence and Statistics (AISTATS), vol. 130, pp. 280–288, 2021\.
  * [41] A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications.  Springer Berlin Heidelberg, 2009.
  * [42] K. Muandet, K. Fukumizu, B. Sriperumbudur, and B. Schölkopf, “Kernel mean embedding of distributions: A review and beyond,” Foundations and Trends in Machine Learning, vol. 10, no. 1-2, pp. 1–144, 2017.
  * [43] B. K. Sriperumbudur, A. Gretton, K. Fukumizu, B. Schölkopf, and G. R. Lanckriet, “Hilbert space embeddings and metrics on probability measures,” Journal of Machine Learning Research, vol. 11, no. 50, pp. 1517–1561, 2010\.
  * [44] C.-J. Simon-Gabriel and B. Schölkopf, “Kernel distribution embeddings: Universal kernels, characteristic kernels and kernel metrics on distributions,” Journal of Machine Learning Research, vol. 19, no. 44, pp. 1–29, 2018.
  * [45] B. Sriperumbudur, “On the optimal estimation of probability measures in weak and strong topologies,” Bernoulli, vol. 22, no. 3, pp. 1839–1893, 2016\.
  * [46] M. Grant and S. Boyd, “CVX: Matlab software for disciplined convex programming, version 2.2.” http://cvxr.com/cvx, Jan. 2020.
  * [47] A. Tychonoff, “Über die topologische erweiterung von räumen,” Mathematische Annalen, vol. 102, pp. 544–561, 1930.
  * [48] P. Johnstone, “Tychonoff’s theorem without the axiom of choice,” Fundamenta Mathematicae, vol. 113, no. 1, pp. 21–35, 1981.
  * [49] M. Sion, “On general minimax theorems,” Pacific Journal of Mathematics, vol. 8, no. 1, pp. 171 – 176, 1958.
  * [50] J. W. Lockhart, G. M. Weiss, J. C. Xue, S. T. Gallagher, A. B. Grosner, and T. T. Pulickal, “Design considerations for the WISDM smart phone-based sensor mining architecture,” in Proc. International Workshop on Knowledge Discovery from Sensor Data, pp. 25–33, 2011.
  * [51] J. R. Kwapisz, G. M. Weiss, and S. A. Moore, “Activity recognition using cell phone accelerometers,” ACM SigKDD Explorations Newsletter, vol. 12, no. 2, p. 74–82, 2011.
  * [52] G. M. Weiss and J. W. Lockhart, “The impact of personalization on smartphone-based activity recognition,” in Proc. AAAI Workshop on Activity Context Representation: Techniques and Languages, pp. 98–104, 2012\.
  * [53] W. Hoeffding, “Asymptotically optimal tests for multinomial distributions,” Annals of Mathematical Statistics, vol. 36, no. 2, pp. 369–401, 1965.
  * [54] T. V. Erven and P. Harremos, “Rényi divergence and Kullback-Leibler divergence,” IEEE Transactions on Information Theory, vol. 60, no. 7, pp. 3797–3820, 2014.
  * [55] J. L. W. V. Jensen, “Sur les fonctions convexes et les inégalités entre les valeurs moyennes,” Acta Mathematica, vol. 30, no. none, pp. 175 – 193, 1906.
  * [56] E. Posner, “Random coding strategies for minimum entropy,” IEEE Transactions on Information Theory, vol. 21, no. 4, pp. 388–391, 1975.
  * [57] M. S. Halmos, Measure Theorey.  New York, NY, USA: Springer-Verlag, 1950.
  * [58] A. Klenke, Probability Theory.  Springer-Verlag London, 2014.
  * [59] Y. V. Prokhorov, “Convergence of random processes and limit theorems in probability theory,” Theory of Probability & Its Applications, vol. 1, no. 2, pp. 157–214, 1956.
  * [60] C. McDiarmid, “On the method of bounded differences,” in Surveys in combinatorics, pp. 148–188, Cambridge University Press, 1989.