$I_{\epsilon}(\theta)<\infty$, and let $q^{*}_{\epsilon}$ denote the
I-projection of $p_{\theta}$ onto the set
$\\{q\in\mathscr{D}(\mathcal{X}):\text{d}_{\text{TV}}(q,p_{0})\leq\epsilon\\}$.
Then $q^{*}_{\epsilon}$ is sandwiched between $p_{0}$ and $p_{\theta}$.

###### Proof.

It suffices to show that for any density $q\in\mathscr{D}(\mathcal{X})$, there
is a density $\bar{q}\in\mathscr{D}(\mathcal{X})$ sandwiched between $p_{0}$
and $p_{\theta}$ such that
$\text{d}_{\text{TV}}(\bar{q},p_{0})\leq\text{d}_{\text{TV}}(q,p_{0})$ and
$\operatorname{KL}(\bar{q}|p_{\theta})\leq\operatorname{KL}(q|p_{\theta})$. We
can then complete the proof by noting that $\bar{q}=q^{*}_{\epsilon}$ if we
set $q=q^{*}_{\epsilon}$.

Let $q\in\mathscr{D}(\mathcal{X})$ be given, and suppose that the set
$S^{+}=\\{q>\max(p_{0},p_{\theta})\\}$ has non-zero Lebesgue measure. Letting

$v=\int_{S^{+}}(q-\max(p_{0},p_{\theta}))\,d\lambda,$

note that

$\text{d}_{\text{TV}}(q,p_{\theta})=\int_{\\{q>p_{\theta}\\}}(q-p_{\theta})\,d\lambda\geq
v.$

Define the density

$\bar{q}(x)=\begin{cases}\max(p_{0}(x),p_{\theta}(x))&\text{ if }x\in S^{+}\\\
q(x)+\frac{v}{\text{d}_{\text{TV}}(q,p_{\theta})}(p_{\theta}(x)-q(x))&\text{
if }p_{\theta}(x)>q(x)\\\ q(x)&\text{ otherwise }\end{cases}.$

Then it is not hard to verify that $\bar{q}$ integrates to one and satisfies
$\bar{q}(x)\leq\max(p_{0}(x),p_{\theta}(x))$ everywhere. Next, applying Lemma
4 with $p=p_{0}$, $q=q$ and $r=\bar{q}$, we obtain
$\text{d}_{\text{TV}}(\bar{q},p_{0})\leq\text{d}_{\text{TV}}(q,p_{0})$ since
$\\{\bar{q}<q\\}=S^{+}\subseteq\\{p_{0}\leq\bar{q}\\}$ holds. Additionally,
$\bar{q}$ is sandwiched between $p_{\theta}$ and $q$. Next, Proposition 2
implies that
$\operatorname{KL}(\bar{q}|p_{\theta})\leq\operatorname{KL}(q|p_{\theta})$.

Now let $q\in\mathscr{D}(\mathcal{X})$ such that $S^{+}$ is empty but the set
$S^{-}=\\{q<\min(p_{0},p_{\theta})\\}$ is non-empty. Letting

$v=\int_{S^{-}}(\min(p_{0},p_{\theta})-q)\,d\lambda,$

note that $0<v\leq\text{d}_{\text{TV}}(q,p_{\theta})$, and define the density

$\bar{q}(x)=\begin{cases}\min(p_{0}(x),p_{\theta}(x))&\text{ if }x\in S^{-}\\\
q(x)+\frac{v}{\text{d}_{\text{TV}}(q,p_{\theta})}(p_{\theta}(x)-q(x))&\text{
if }p_{\theta}(x)<q(x)\\\ q(x)&\text{ otherwise }\end{cases}.$

Then observe that $\bar{q}$ is a density and it is sandwiched between $q$ and
$p_{\theta}$. Similar arguments as above using Lemma 4 and Proposition 2 show
that $\text{d}_{\text{TV}}(\bar{q},p_{0})\leq\text{d}_{\text{TV}}(q,p_{0})$
and
$\operatorname{KL}(\bar{q}|p_{\theta})\leq\operatorname{KL}(q|p_{\theta})$. ∎

##  Appendix B Convergence of OKL estimator in finite spaces

In this section, we will work with a finite data space but allow for a more
general distance function. To this end, let $\boldsymbol{d}(p,q)$ denote the
distance between probability vectors $p,q\in\Delta_{\mathcal{X}}$. Then the
OKL function for a general distance in eq. 11 translates to this setting as

$I_{\epsilon}(\theta)=\inf_{\begin{subarray}{c}q\in{\Delta}_{\mathcal{X}}\\\
\boldsymbol{d}(p,p_{0})\leq\epsilon\end{subarray}}\operatorname{KL}(q|p_{\theta}).$
(12)

Given a dataset $x_{1},\ldots,x_{n}\in\mathcal{X}$, the finite approximation
to the OKL for general distance $\boldsymbol{d}$ is given by

$\displaystyle\hat{I}_{\epsilon,\textnormal{fin}}(\theta)=\inf_{\begin{subarray}{c}q\in{\Delta}_{\mathcal{X}}\\\
\operatorname{supp}(q)=\hat{\mathcal{X}}_{n}\\\
\boldsymbol{d}(q,\hat{p}_{\textnormal{fin}})\leq\epsilon\end{subarray}}\sum_{x\in\hat{\mathcal{X}}_{n}}q(x)\log\frac{q(x)}{p_{\theta}(x)},$
(13)

where $\hat{\mathcal{X}}_{n}=\\{x_{1},\ldots,x_{n}\\}$ is the observed support
and $\hat{p}_{\textnormal{fin}}(y)=\frac{|\\{i\in[n]|x_{i}=y\\}|}{n}$. When
$\boldsymbol{d}(p,q)=\frac{1}{2}\|p-q\|_{1}$ is the total variation distance,
the above is equivalent to the form given in eq. 2 as shown in the following
lemma.

######  Lemma 6.

For any $\epsilon>0$ and $x_{1},\ldots,x_{n}\in\mathcal{X}$,

$\displaystyle\inf_{\begin{subarray}{c}q\in{\Delta}_{\mathcal{X}}\\\
\operatorname{supp}(q)=\hat{\mathcal{X}}_{n}\\\
\frac{1}{2}\|q-\hat{p}_{\textnormal{fin}}\|_{1}\leq\epsilon\end{subarray}}\sum_{x\in\hat{\mathcal{X}}_{n}}q(x)\log\frac{q(x)}{p_{\theta}(x)}\
=\ \inf_{\begin{subarray}{c}w\in{\Delta}_{n}\\\
\frac{1}{2}\|w-o\|_{1}\leq\epsilon\end{subarray}}\sum_{i=1}^{n}w_{i}\log\frac{w_{i}n\hat{p}_{\textnormal{fin}}(x_{i})}{p_{\theta}(x_{i})}.$

where $o=(1/n,\ldots,1/n)\in\Delta_{n}$.

###### Proof.

For convenience, let $n_{i}=n\hat{p}_{\textnormal{fin}}(x_{i})$ and let
$n(x)=n\hat{p}_{\textnormal{fin}}(x)$. For any $q\in{\Delta}_{\mathcal{X}}$
satisfying $\operatorname{supp}(q)=\hat{\mathcal{X}}_{n}$, let
$w_{q}\in\Delta_{n}$ satisfy $w_{q,i}=q(x_{i})/n_{i}$. Then we have

$\displaystyle\|w_{q}-o\|_{1}=\sum_{i=1}^{n}\left|\frac{q(x_{i})}{n_{i}}-\frac{1}{n}\right|=\sum_{x\in\hat{\mathcal{X}}_{n}}n(x)\left|\frac{q(x)}{n(x)}-\frac{1}{n}\right|=\|q-\hat{p}_{\textnormal{fin}}\|_{1}\text{
and }$
$\displaystyle\sum_{i=1}^{n}w_{q,i}\log\frac{w_{q,i}n_{i}}{p_{\theta}(x_{i})}=\sum_{i=1}^{n}\frac{q(x_{i})}{n_{i}}\log\frac{q(x_{i})}{p_{\theta}(x_{i})}=\sum_{x\in\hat{\mathcal{X}}_{n}}q(x)\log\frac{q(x)}{p_{\theta}(x)}.$

The above two equalities imply that

$\displaystyle\inf_{\begin{subarray}{c}q\in{\Delta}_{\mathcal{X}}\\\
\operatorname{supp}(q)=\hat{\mathcal{X}}_{n}\\\
\frac{1}{2}\|q-\hat{p}_{\textnormal{fin}}\|_{1}\leq\epsilon\end{subarray}}\sum_{x\in\hat{\mathcal{X}}_{n}}q(x)\log\frac{q(x)}{p_{\theta}(x)}\
\geq\ \inf_{\begin{subarray}{c}w\in{\Delta}_{n}\\\
\frac{1}{2}\|w-o\|_{1}\leq\epsilon\end{subarray}}\sum_{i=1}^{n}w_{i}\log\frac{w_{i}n\hat{p}_{\textnormal{fin}}(x_{i})}{p_{\theta}(x_{i})}.$

Now for any $w\in\Delta_{n}$, let $q_{w}\in{\Delta}_{\mathcal{X}}$ satisfy
$q_{w}(x)=\sum_{i:x_{i}=x}w_{i}$. Note that we trivially must have
$\operatorname{supp}(q_{w})=\hat{\mathcal{X}}_{n}$. Moreover, we have

$\displaystyle\|q_{w}-\hat{p}_{\textnormal{fin}}\|_{1}=\sum_{x\in\hat{\mathcal{X}}_{n}}\left|\left(\sum_{i:x_{i}=x}w_{i}\right)-\frac{n(x)}{n}\right|\leq\sum_{x\in\hat{\mathcal{X}}_{n}}\sum_{i:x_{i}=x}\left|w_{i}-\frac{1}{n}\right|=\|w-o\|_{1}\text{
and }$
$\displaystyle\sum_{x\in\hat{\mathcal{X}}_{n}}q_{w}(x)\log\frac{q_{w}(x)}{p_{\theta}(x)}=\sum_{x\in\hat{\mathcal{X}}_{n}}\left(\sum_{i:x_{i}=x}w_{i}\right)\log\frac{\left(\sum_{i:x_{i}=x}w_{i}\right)}{p_{\theta}(x)}\leq\sum_{i=1}^{n}w_{i}\log\frac{w_{i}n_{i}}{p_{\theta}(x_{i})},$

where the first inequality is the triangle inequality and the second
inequality is the log sum inequality [Cover and Thomas, 2006, Theorem 2.7.1].
Together, the above implies that

$\displaystyle\inf_{\begin{subarray}{c}q\in{\Delta}_{\mathcal{X}}\\\
\operatorname{supp}(q)=\hat{\mathcal{X}}_{n}\\\
\frac{1}{2}\|q-\hat{p}_{\textnormal{fin}}\|_{1}\leq\epsilon\end{subarray}}\sum_{x\in\hat{\mathcal{X}}_{n}}q(x)\log\frac{q(x)}{p_{\theta}(x)}\
\leq\ \inf_{\begin{subarray}{c}w\in{\Delta}_{n}\\\
\frac{1}{2}\|w-o\|_{1}\leq\epsilon\end{subarray}}\sum_{i=1}^{n}w_{i}\log\frac{w_{i}n\hat{p}_{\textnormal{fin}}(x_{i})}{p_{\theta}(x_{i})}.\
\ \ \qed$

To prove convergence of the estimator in eq. 13, we will make the following
assumptions on the space $\mathcal{X}$ and distance $\boldsymbol{d}$.

######  Assumption B.1.

$\mathcal{X}$ is a finite set, $\boldsymbol{d}$ is a metric, $\boldsymbol{d}$
is jointly convex in its arguments, and there exists a constant $C\geq 1$ for
which $\boldsymbol{d}(p,q)\leq C\|p-q\|_{1}$ for all
$p,q\in\Delta_{\mathcal{X}}$.

Observe that Assumption B.1 fulfills the conditions of Lemma 2, implying that
$I_{\epsilon}(\theta)$ is continuous in $\epsilon$. To get quantitative
bounds, we make the following assumption.

######  Assumption B.2.

There exist constants $V,\epsilon_{0}>0$ such that
$I_{\epsilon_{0}}(\theta)\leq V$.

Finally, we will also require some conditions on the support of $p_{\theta}$
and $p_{0}$.

######  Assumption B.3.

There exists a set $S\subseteq\mathcal{X}$ and constant $\gamma_{0}>0$ such
that $\operatorname{supp}(p_{\theta})=S\subseteq\operatorname{supp}(p_{0})$
and $p_{0}(x)\geq\gamma_{0}$ for all $x\in S$.

Given the above assumptions, we have the following convergence result for
$\hat{I}_{\epsilon,\textnormal{fin}}(\theta)$.

######  Theorem 5.

Pick $\epsilon>\epsilon_{0}$ and let
$n\geq\max\left\\{\frac{1}{\gamma_{0}}\log\frac{2|S|}{\delta},\frac{1}{2}\left(\frac{C|S|}{\epsilon-\epsilon_{0}}\right)^{2}\log\frac{4|S|}{\delta}\right\\}$,
and suppose Assumptions B.1, B.3 and B.2 hold. If
$x_{1},\ldots,x_{n}\overset{i.i.d.}{\sim}p_{0}$, then with probability at
least $1-\delta$,

$|I_{\epsilon}(\theta)-\hat{I}_{\epsilon,\textnormal{fin}}(\theta)|\leq\frac{CV|S|}{\epsilon-\epsilon_{0}}\sqrt{\frac{1}{2n}\log\frac{2|S|}{\delta}}.$

###### Proof.

If $n\geq\frac{1}{\gamma_{0}}\log\frac{2|S|}{\delta}$, then with probability
$1-\delta/2$, we have $S\subseteq\hat{\mathcal{X}}_{n}$. Moreover, an
application of Hoeffding’s inequality tells us that with probability at least
$1-\delta/2$, we have

$\|\hat{p}_{\textnormal{fin}}-p_{0}\|_{1}\leq|S|\sqrt{\frac{1}{2n}\log\frac{4|S|}{\delta}}.$

By a union bound, both of these events occur with probability at least
$1-\delta$. Condition on these two events occurring.

Now observe that any $q\in\Delta_{\mathcal{X}}$ that achieves
$\operatorname{KL}_{\mathcal{X}}(q|p^{\theta})<\infty$ must satisfy $q(x)=0$
for all $x\not\in S$. Thus, we may rewrite the OKL and our finite estimator as

$\displaystyle I_{\epsilon}(\theta)$
$\displaystyle=\inf_{\begin{subarray}{c}q\in\Delta_{\mathcal{X}}\\\
\operatorname{supp}(q)\subseteq S\\\
\boldsymbol{d}(q,p_{0})\leq\epsilon\end{subarray}}\operatorname{KL}(q|p_{\theta})$
$\displaystyle\hat{I}_{\epsilon,\textnormal{fin}}(\theta)$
$\displaystyle=\inf_{\begin{subarray}{c}q\in\Delta_{\mathcal{X}}\\\
\operatorname{supp}(q)\subseteq\hat{\mathcal{X}}_{n}\cap S\\\
\boldsymbol{d}(q,\hat{p}_{\textnormal{fin}})\leq\epsilon\end{subarray}}\operatorname{KL}(q|p_{\theta})=\inf_{\begin{subarray}{c}q\in\Delta_{\mathcal{X}}\\\
\operatorname{supp}(q)\subseteq S\\\
\boldsymbol{d}(q,\hat{p}_{\textnormal{fin}})\leq\epsilon\end{subarray}}\operatorname{KL}(q|p_{\theta}),$

where we have used the fact that we are conditioning on
$S\subseteq\hat{\mathcal{X}}_{n}$.

Moreover, by Assumption B.1 and our bound on
$\|\hat{p}_{\textnormal{fin}}-p_{0}\|_{1}$, we have:

$\boldsymbol{d}(q,\hat{p}_{\textnormal{fin}})\leq\boldsymbol{d}(q,p_{0})+\boldsymbol{d}(\hat{p}_{\textnormal{fin}},p_{0})\leq\boldsymbol{d}(q,p_{0})+C\|\hat{p}_{\textnormal{fin}}-p_{0}\|_{1}\leq\boldsymbol{d}(q,p_{0})+\alpha_{n},$

where $\alpha_{n}=C|S|\sqrt{\frac{1}{2n}\log\frac{2|S|}{\delta}}$. Similarly,
we also can conclude
$\boldsymbol{d}(q,\hat{p}_{\textnormal{fin}})\geq\boldsymbol{d}(q,p_{0})-\alpha_{n}.$

Applying Lemma 2, we have

$\displaystyle\hat{I}_{\epsilon,\textnormal{fin}}(\theta)$
$\displaystyle=\inf_{\begin{subarray}{c}q\in\Delta_{\mathcal{X}}\\\
\operatorname{supp}(q)\subseteq S\\\
\boldsymbol{d}(q,\hat{p}_{\textnormal{fin}})\leq\epsilon\end{subarray}}\operatorname{KL}(q|p_{\theta})\geq\inf_{\begin{subarray}{c}q\in\Delta_{\mathcal{X}}\\\
\operatorname{supp}(q)\subseteq S\\\
\boldsymbol{d}(q,p_{0})\leq\epsilon+\alpha\end{subarray}}\operatorname{KL}(q|p_{\theta})$
$\displaystyle=I_{\epsilon+\alpha_{n}}(\theta)\geq
I_{\epsilon}(\theta)-\frac{\alpha_{n}}{\epsilon-\epsilon_{0}+\alpha_{n}}V.$

On the other hand, if
$n\geq\frac{1}{2}\left(\frac{C|S|}{\epsilon-\epsilon_{0}}\right)^{2}\log\frac{4|S|}{\delta}$,
then $\alpha_{n}\leq\epsilon-\epsilon_{0}$, and we can again apply Lemma 2 to
see that

$\displaystyle\hat{I}_{\epsilon,\textnormal{fin}}(\theta)$
$\displaystyle=\inf_{\begin{subarray}{c}q\in\Delta_{\mathcal{X}}\\\
\operatorname{supp}(q)\subseteq S\\\
\boldsymbol{d}(q,\hat{p}_{\textnormal{fin}})\leq\epsilon\end{subarray}}\operatorname{KL}(q|p_{\theta})\leq\inf_{\begin{subarray}{c}q\in\Delta_{\mathcal{X}}\\\
\operatorname{supp}(q)\subseteq S\\\
\boldsymbol{d}(q,p_{0})\leq\epsilon-\alpha\end{subarray}}\operatorname{KL}(q|p_{\theta})$
$\displaystyle=I_{\epsilon-\alpha_{n}}(\theta)\leq
I_{\epsilon}(\theta)+\frac{\alpha_{n}}{\epsilon-\epsilon_{0}}V.$

Rearranging the above inequalities gives us the lemma statement. ∎

##  Appendix C Convergence of OKL estimator in Euclidean spaces

In this section, we show consistency (and convergence rates) for the OKL
estimator when $\mathcal{X}=\mathbb{R}^{d}$ is the Euclidean space. To avoid
technical complications with tail estimation, we will restrict our analysis to
the case when both the data and the model family are supported on a compact
set $S\subseteq\mathcal{X}$. The results and notation in this section are
self-contained, and can be read independently of other sections.

###  C.1 Introduction

Consider the data space $\mathcal{X}=\mathbb{R}^{d}$ equipped with the
Euclidean norm $\|\cdot\|$ and its Borel sigma algebra $\mathcal{B}$. We will
let $\mathscr{D}(\mathcal{X})=\\{f:\mathcal{X}\to[0,\infty)\mid\int
f(x)dx=1,f\text{ is $\mathcal{B}$-measurable}\\}$ denote the set of densities
on $\mathcal{X}$ with respect to the Lebesgue measure $\lambda$. Given the
data density $p_{0}\in\mathscr{D}(\mathcal{X})$, model family
$\\{p_{\theta}\\}_{\theta\in\Theta}\subseteq\mathscr{D}(\mathcal{X})$ and
coarsening radius $\epsilon>0$, the central object of interest in this section
is the OKL function defined as

$I_{\epsilon}(\theta)=\inf_{\begin{subarray}{c}q\in\mathscr{D}(\mathcal{X})\\\
\text{d}_{\text{TV}}(q,p_{0})\leq\epsilon\end{subarray}}\operatorname{KL}(q|p_{\theta}),$
(14)

where, given two densities $p,q\in\mathscr{D}(\mathcal{X})$, the total
variation distance between them is
$\text{d}_{\text{TV}}(q,p)=\frac{1}{2}\int|q(x)-p(x)|dx$, and the KL-
divergence is $\operatorname{KL}(p|q)=\int p(x)\log\frac{p(x)}{q(x)}dx$ if the
absolute continuity condition $\int p(x)I\\{q(x)=0\\}dx=0$ is satisfied,
otherwise $\operatorname{KL}(p|q)=\infty$.

Given samples $x_{1},\ldots,x_{n}\in\mathcal{X}$ drawn i.i.d. from the
distribution with density $p_{0}$, and a suitable kernel
$K_{h}:\mathcal{X}\times\mathcal{X}\to\mathbb{R}$, we will approximate
$I_{\epsilon}(\theta)$ with the value of a finite-dimensional optimization
problem given by

$\hat{I}_{\epsilon}(\theta)=\inf_{\begin{subarray}{c}w\in\hat{\Delta}_{n}\\\
\frac{1}{2}\|w-o\|_{1}\leq\epsilon\end{subarray}}\sum_{i=1}^{n}w_{i}\log\frac{nw_{i}\hat{p}(x_{i})}{p_{\theta}(x_{i})},$
(15)

where $\hat{p}$ is a suitable density estimator for $p_{0}$,
$\Delta_{n}=\\{(v_{1},\ldots,v_{n})|\sum_{i=1}^{n}v_{i}=1,v_{i}\geq 0\\}$ is
the $n$-dimensional probability simplex, $o=(1/n,\ldots,1/n)\in\Delta_{n}$ is
the constant probability vector, $A$ is an $n\times n$ matrix with entries
$A_{ij}=\frac{K_{h}(x_{i},x_{j})}{n\hat{p}(x_{i})}$,
$\hat{\Delta}_{n}=A\Delta_{n}$ is the image of the set
$\Delta_{n}\subseteq\mathbb{R}^{n}_{+}$ under the linear operator $A$, and
$\|(x_{1},\ldots,x_{d})\|_{1}=\sum_{i=1}^{d}|x_{i}|$ is the $\ell_{1}$ norm of
the vector.

####  C.1.1 Assumptions and statement of the result

To describe the formal statement quantifying the approximation between eq. 14
and eq. 15, we will introduce a series of assumptions. Our result will handle
the case when densities $p_{0}$ and $p_{\theta}$ are smooth densities
supported on a bounded set $S\subseteq\mathcal{X}$ whose boundary has measure
zero, i.e. $\lambda(S\setminus S^{\circ})=0$, where $S^{\circ}$ denotes the
interior of $S$. We fix a value $\theta\in\Theta$ throughout this section.

######  Assumption C.1.

Suppose $S\subseteq\mathcal{X}$ is a subset of the closed unit ball
$\bar{B}(0,R)$ of radius $R$, with finite Lebesgue measure
$V_{S}=\lambda(S)\geq 1$, and has a boundary measure functional
$\phi(r)=\frac{\lambda(S\setminus S_{-r})}{\lambda(S)}$ that satisfies
$\lim_{r\rightarrow 0}\phi(r)=0$.

Here $S_{-r}=\\{x\in S:B(x,r)\subseteq S\\}$ denotes the set of points for
which the unit ball of radius $B(x,r)=\\{y\in\mathcal{X}|\|x-y\|\leq r\\}$ is
also contained inside $S$. For example, when $S=B(x_{0},r_{0})$ is the unit
ball of radius $r_{0}$ centered at the point $x_{0}$, the boundary measure
functional is given by

$\phi(r)=1-\frac{\lambda(B(x,r_{0}-r))}{\lambda(B(x,r_{0}))}=1-\left(1-\frac{r}{r_{0}}\right)^{d}$

since $S_{-r}=B(x_{0},r_{0}-r)$.

Next we have the following smoothness and support condition on densities
$p_{0},p_{\theta}\in\mathscr{D}(\mathcal{X})$. Here the support of a density
$p\in\mathscr{D}(\mathcal{X})$ is defined as
$\operatorname{supp}(p)=\\{x\in\mathcal{X}:p(x)>0\\}$.

######  Assumption C.2.

The supports satisfy
$\operatorname{supp}(p_{0})=\operatorname{supp}(p_{\theta})=S$, and there
exists $\gamma\in(0,1]$ such that $p_{0}(x),p_{\theta}(x)\in[\gamma,1/\gamma]$
for all $x\in S$.

######  Assumption C.3.

$p_{0}$ and $\log p_{\theta}$ are $\alpha$-Hölder smooth on $S$. More
precisely, there are constants $\alpha,C_{\alpha}>0$ such that
$|p_{0}(x)-p_{0}(y)|,|\log p_{\theta}(x)-\log p_{\theta}(y)|\leq
C_{\alpha}\|x-y\|^{\alpha}$ for all $x,y\in S$.

Finally, we will require the following assumption on the kernel
$K_{h}:\mathcal{X}\times\mathcal{X}\to\mathbb{R}$.

######  Assumption C.4.

The kernel satisfies
$K_{h}(x,y)=\frac{1}{h^{d}}\kappa\left(\frac{\|x-y\|_{2}}{h}\right)$ for a
non-increasing continuous function
$\kappa:\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$ satisfying (i)
$\int_{\mathbb{R}^{d}}\kappa(\|x\|_{2})\,dx=1$, (ii) $\kappa(0)\leq c_{0}$ for
some fixed constant $c_{0}>0$, and (iii) there exist constants
$t_{0},C_{\rho},\rho$ such that $\rho\leq 1$ and $t_{0}\geq 1$ so that for all
$t>t_{0}$, $k(t)\leq C_{\rho}\exp(-t^{\rho})$. Further, suppose that (iv) for
every $h>0$, the kernel $K_{h}$ is a positive semi-definite kernel, i.e. the
$m\times m$ matrix $(K_{h}(y_{i},y_{j}))_{i,j\in[m]}$ for any
$y_{1},\ldots,y_{m}\in\mathbb{R}^{d}$ and $m\geq 1$ is positive semi-definite.

Parts (i)-(iii) in Assumption C.4 are standard assumptions in the kernel
density estimation literature (see, e.g. Jiang [2017]), while part (iv) allows
us to use techniques from reproducing kernel Hilbert spaces. By Shoenberg’s
theorem (see e.g. Ressel [1976]) part (iv) of Assumption C.4 is satisfied
whenever $\kappa$ is a completely monotone function (see e.g. Merkle [2014]).
In particular, note that Assumption C.4 is satisfied by the Gaussian kernel
given as $\kappa(t)=\frac{1}{(2\pi)^{d/2}}\exp(-t^{2})$.

######  Definition C.1.

Suppose Assumption C.4 holds and observations
$x_{1},\ldots,x_{n}\overset{i.i.d.}{\sim}p_{0}$ are given. Define a mapping
$L:\Delta_{n}\mapsto\mathscr{D}(\mathcal{X})$ from the $n$-dimensional
probability simplex $\Delta_{n}$ to the space of densities
$\mathscr{D}(\mathcal{X})$ given by $L(w)=\hat{q}_{w}$, where

$\hat{q}_{w}(\cdot)=\sum_{i=1}^{n}w_{i}K_{h}(\cdot,x_{i}).$

For the probability density estimator $\hat{p}$ in the Monte Carlo estimate of
the objective in eq. 14, we use the kernel density estimate
$\hat{p}=\hat{q}_{o}$, where $o=(1/n,\ldots,1/n)\in\Delta_{n}$.

Using the parameterization $w=Av$ for $v\in\Delta_{n}$, one can rewrite eq. 15
using the above notation as:

$\hat{I}_{\epsilon}(\theta)=\inf_{\begin{subarray}{c}v\in\Delta_{n}\\\
\frac{1}{2n}\sum_{i=1}^{n}\left|\frac{\hat{q}_{v}(x_{i})}{\hat{p}(x_{i})}-1\right|\leq\epsilon\end{subarray}}\frac{1}{n}\sum_{i=1}^{n}\frac{\hat{q}_{v}(x_{i})}{\hat{p}(x_{i})}\log\frac{\hat{q}_{v}(x_{i})}{p_{\theta}(x_{i})}.$

In order to ensure stability of the optimization objective in eq. 15 and
guarantee regularity in the optimal weights, we will restrict the optimization
over weights that do not deviate too far from uniformity and replace $\hat{p}$
by the ‘clipped’ version of our estimator:
$\hat{p}_{\gamma}(x)=\min(\max(\hat{p}(x),\gamma),1/\gamma)$. To that end,
define $\Delta_{n}^{r}=\\{v\in\Delta_{n}:n\cdot v_{i}\in[r,1/r]\text{ for all
}i\\}$ for $r\leq 1$. Then for our theoretical result, we will consider a
version of the estimator

$\displaystyle\hat{I}_{\epsilon}(\theta)=\inf_{\begin{subarray}{c}v\in\Delta_{n}^{\gamma^{2}/4}\\\
\frac{1}{2n}\sum_{i=1}^{n}\left|\frac{\hat{q}_{v}(x_{i})}{\hat{p}_{\gamma}(x_{i})}-1\right|\leq\epsilon\end{subarray}}\frac{1}{n}\sum_{i=1}^{n}\frac{\hat{q}_{v}(x_{i})}{\hat{p}_{\gamma}(x_{i})}\log\frac{\hat{q}_{v}(x_{i})}{p_{\theta}(x_{i})},$
(16)

where $\gamma$ is the value from Assumption C.2.

Under the above assumptions, we have the following result:

######  Theorem 6.

Suppose Assumptions C.1, C.2, C.3 and C.4 hold and $n\geq
n_{0},h\leq\bar{h},and\frac{\log n}{\sqrt{n}h^{d}}\leq\bar{\eta}$ for suitable
constants $\bar{h},n_{0},\bar{\eta}>0$ that depend on the quantities in the
assumptions. Fix a $\beta>0$, and suppose we obtain an i.i.d. sample
$x_{1},\ldots,x_{n}$ of size $n$ from density $p_{0}$. Then with probability
at least $1-e^{-(\log n)^{2\beta}}$,

$\left|\hat{I}_{\epsilon}(\theta)-I_{\epsilon}(\theta)\right|\leq
O\left(\frac{\log
n}{\sqrt{n}h^{d}}+h^{\min(\alpha/2,1)}\log\frac{1}{h}+\phi(\sqrt{h})\log\frac{1}{\phi(\sqrt{h})}\right),$

where the $O(\cdot)$ hides constant factors depending on the quantities in
Assumptions C.1-C.4, and on the choice of $\epsilon,\beta>0$.

When $S=B(0,R)$ is a Euclidean ball of radius $R$, Taylor expansion shows that
$\phi(\sqrt{h})=\frac{\sqrt{h}d}{R}+O(h)$. Suppose, for simplicity that
$\alpha\geq 1$, then taking $h=n^{-\frac{1}{2d+1}}$ and $\beta=1$, we see that
$|\hat{I}_{\epsilon}(\theta)-I_{\epsilon}(\theta)|=\tilde{O}(n^{-\frac{1}{4d+2}})$
upto a logarithmic factor in $n$, with probability at least $1-1/n$.

Note that the choice of bandwidth parameter $h=o(n^{-\frac{1}{2d}})$ required
to shrink our error terms to zero decreases more slowly with $n$ than the
optimal rate $h=o(n^{-1/d})$ for density estimation [Rigollet and Vert, 2009].
This suggests that our error bounds can potentially be improved. Note also
that the above result holds for any fixed value of $\theta\in\Theta$;
extensions to uniform convergence over all $\theta\in\Theta$ may be possible
with further assumptions on the complexity of the class $\Theta$ and
continuity of the map $\theta\mapsto\log p_{\theta}(\cdot)$, but we do not
pursue this direction here.

###### Proof outline of Theorem 6.

We sketch the proof here.

Section C.3.1

First, Lemma 12 shows that with high probability for large $n$, the estimators
of KL divergence and total variation in eq. 16 are close to their population
counterparts $\operatorname{KL}(\hat{q}_{v}|p_{\theta})$ and
$\text{d}_{\text{TV}}(\hat{q}_{v},p_{0})$ for any $v\in\Delta_{n}$ such that
$\hat{q}_{v}$ is suitably bounded. See Corollary 3 for the most useful version
of this statement.

Section C.3.2

Next, Lemma 17 shows that for any density $q$ over $S$ satisfying Assumption
C.2, with high probability for large $n$, there exists a
$v\in\Delta_{n}^{\gamma}$ such that $\hat{q}_{v}$ is a pointwise accurate
estimator of $K_{h}\star q$, where $K_{h}\star q$ denotes the convolution of
the density $q$ with the probability kernel $K_{h}$. Combined with Lemma 5,
which establishes the boundedness of the minimizer $q^{*}_{\epsilon}$ in eq.
14, we have that there exists a pointwise accurate estimator $\hat{q}_{v^{*}}$
of $K_{h}\star q^{*}_{\epsilon}$ for some $v^{*}\in\Delta_{n}^{\gamma^{2}/4}$.

Section C.3.3

Lemma 18 shows that under Assumption C.3, $\operatorname{KL}(K_{h}\star
q|p_{\theta})$ and $\text{d}_{\text{TV}}(K_{h}\star q,p_{0})$ must not be much
greater than $\operatorname{KL}(q|p_{\theta})$ and
$\text{d}_{\text{TV}}(q,p_{0})$, respectively, when $h$ is sufficiently small.

We combine the above arguments (see Section C.4), to show that the optimal
objective value in eq. 14 corresponding to the minimizer $q^{*}_{\epsilon}$,
must be close to the optimal objective value in eq. 16, thus showing that
$\hat{I}_{\epsilon}(\theta)$ can well approximate $I_{\epsilon}(\theta)$ when
$h$ is small, and $n$ is large. ∎

While Section C.3 covers the main steps of proof, there are useful results in
Section C.2 that provide upper bounds on the tail probability and second
moment of the kernel $K_{h}$ based on Assumption C.4. These results are used
in Section C.3.3 and Section C.4.

##### Additional notation

For $p\in\mathscr{D}(\mathcal{X})$ and $A\subseteq\mathcal{X}$, we will use
the shorthand $p(A)$ to denote the quantity $\int_{A}p(x)dx$. For a
probability density kernel $K_{h}$, let

$\widetilde{p}_{h}(\cdot)=(K_{h}\star p)(\cdot)=\int
p(y)K_{h}(\cdot,y)dy\in\mathscr{D}(\mathcal{X})$

denote the kernel-smoothed version of a density
$p\in\mathscr{D}(\mathcal{X})$. Similarly, for a measure $\mu$ on
$\mathcal{X}$, we can define $(K_{h}\star\mu)(x)=\int K_{h}(x,y)\mu(dy)$. For
a set $S\subseteq\mathbb{R}^{d}$ and $p,q\in\mathscr{D}(\mathcal{X})$, let
$\operatorname{KL}_{S}(q|p)=\int_{S}q(x)\log\frac{p(x)}{q(x)}\,dx$. The
constant $v_{d}$ will denote the volume of the Euclidean ball in
$\mathbb{R}^{d}$. The notation $\|f\|_{1}=\int|f(x)|dx$ and
$\|f\|_{\infty}=\sup_{x\in\mathcal{X}}|f(x)|$ will denote the $L_{1}$ and
$L_{\infty}$ norm of the function $f$. For $p,q\in\mathscr{D}(\mathcal{X})$,
recall that $\text{d}_{\text{TV}}(p,q)=\frac{1}{2}\|p-q\|_{1}.$

###  C.2 Kernel tail bounds

In this sub-section, we derive tail bounds for a class of probability kernels
$K_{h}(x,y)=\frac{1}{h^{d}}\kappa(\|x-y\|/h)$ on $\mathbb{R}^{d}$ indexed by
parameter $h>0$ used for density estimation, when the function
$\kappa:[0,\infty)\to[0,\infty)$ has exponentially decaying tails (see parts
(i)-(iii) of Assumption C.4). The following two lemmas bound the tail
distribution and the variance of the random variable $Z$ having density
$x\mapsto\kappa(\|x\|)$. These results will then be used to obtain tails
bounds for the kernel $K_{h}$.

######  Lemma 7.

Suppose Assumption C.4 holds. If $Z$ is an $\mathbb{R}^{d}$ valued random
vector with probability density $x\mapsto\kappa(\|x\|)$, then

$\mathbb{P}(\|Z\|\geq t)=\int_{\|x\|\geq t}\kappa(\|x\|)dx\leq
C_{1}t^{d+1-\rho}e^{-t^{\rho}}$ (17)

for each $t\geq t_{1}=\max(\Gamma(a+1)^{1/{\rho(a-1)}},t_{0})\geq 1$ where
$\Gamma$ is the Gamma function, $a=\frac{d+1}{\rho}$, and $C_{1}>0$ is a
constant depending on constants $t_{0},C_{\rho},\rho>0$ in Assumption C.4 and
dimension $d$. Explicitly, $C_{1}=\rho^{-1}C_{\rho}v_{d}2^{a-1}$, where
$v_{d}=\frac{\pi^{d/2}}{\Gamma(d/2+1)}$ is the volume of the unit ball in
$\mathbb{R}^{d}$.

###### Proof.

Using [Jiang, 2017, Lemma 4] and the upper bound on tails of $\kappa$ since
$s\geq t\geq t_{0}$,

$\displaystyle\int_{\|x\|\geq
t}\kappa(\|x\|)dx=v_{d}\int_{t}^{\infty}\kappa(r)r^{d}dr\leq
C_{\rho}v_{d}\int_{t}^{\infty}e^{-r^{\rho}}r^{d}dr.$

Using the substitution $s=r^{\rho}$, we obtain

$\int_{t}^{\infty}e^{-r^{\rho}}r^{d}dr=\frac{1}{\rho}\int_{t^{\rho}}^{\infty}e^{-s}s^{\frac{d+1}{\rho}-1}ds=\frac{1}{\rho}\Gamma\left(a,t^{\rho}\right)$

where $\Gamma(a,y)=\int_{y}^{\infty}e^{-x}x^{a-1}dx$ is the incomplete Gamma
function and $a=\frac{d+1}{\rho}\geq 2$. Taking $b_{a}=\Gamma(a+1)^{1/(a-1)}$,
we have the following bound on the incomplete Gamma function [Pinelis, 2020,
Theorem 1.1] for $a\geq 2$:

$\Gamma(a,y)\leq\frac{((b_{a}+y)^{a}-y^{a})e^{-y}}{ab_{a}}=\frac{e^{-y}\int_{0}^{b_{a}}a(x+y)^{a-1}dx}{ab_{a}}\leq(b_{a}+y)^{a-1}e^{-y}.$

Since $t^{\rho}\geq b_{a}$, the proof can be completed by combining the above
displays along with the bound

$\Gamma(a,t^{\rho})\leq
2^{a-1}t^{\rho(a-1)}e^{-t^{\rho}}=2^{a-1}t^{d+1-\rho}e^{-t^{\rho}}.$

∎

######  Lemma 8.

Suppose Assumption C.4 holds. If $Z$ is an $\mathbb{R}^{d}$ valued random
vector with probability density $x\mapsto\kappa(\|x\|)$, then

$\mathbb{E}_{Z}[\|Z\|_{2}^{2}]\leq
v_{d}\left(c_{0}t_{0}^{d+3}+\frac{C_{\rho}}{\rho}\Gamma\left(\frac{d+3}{\rho}\right)\right),$

where $v_{d}$ is the volume of the unit ball in $d$-dimensions and
$\Gamma(\cdot)$ is the Gamma function.

###### Proof.

We can write

$\displaystyle\mathbb{E}_{Z}[\|Z\|_{2}^{2}]=\int_{\mathbb{R}^{d}}\|z\|_{2}^{2}\kappa(\|z\|_{2})\,dz=v_{d}\int_{0}^{\infty}\kappa(t)t^{d+2}\,du,$

where the second equality follows from [Jiang, 2017, Lemma 4]. Taking
$c_{0},t_{0},\rho,C_{\rho}$ as the constants from Assumption C.4, we have

$\displaystyle\int_{0}^{\infty}\kappa(t)t^{d+2}\,du$
$\displaystyle=\int_{0}^{t_{0}}\kappa(t)t^{d+2}\,du+\int_{t_{0}}^{\infty}\kappa(t)t^{d+2}\,du$
$\displaystyle\leq
c_{0}t_{0}^{d+3}+C_{\rho}\int_{t_{0}}^{\infty}\exp(-t^{\rho})t^{d+2}\,du$
$\displaystyle\leq
c_{0}t_{0}^{d+3}+\frac{C_{\rho}}{\rho}\int_{0}^{\infty}\exp(-u)u^{\frac{d+3}{\rho}-1}\,du$
$\displaystyle=c_{0}t_{0}^{d+3}+\frac{C_{\rho}}{\rho}\Gamma\left(\frac{d+3}{\rho}\right),$

where we have used the substitution $u=t^{\rho}$ in the second inequality as
well as the fact that the integrands are non-negative from 0 to $\infty$, and
the last line follows from the definition of the Gamma function. ∎

We now use the above lemmas to prove properties about the kernel $K_{h}$.

######  Lemma 9.

Suppose that Assumption C.4 holds. For any $x\in\mathbb{R}^{d}$,

$\int_{B(x,r)}K_{h}(x,y)\,dy\geq 1-\frac{C_{1}k!}{(r/h)^{4}}$

whenever $r\geq t_{1}h$, where $B(x,r)$ denotes the open ball of radius $r$
around $x$, constants $C_{1},t_{1}>0$ are as defined in Lemma 7, and
$k=\lceil\frac{5+d}{\rho}\rceil-1$. In particular, for any bounded set
$S\subset\mathbb{R}^{d}$ and any $x\in S$, we have

$\int_{S}K_{h}(x,y)\,dy\geq 1-\frac{C_{1}k!}{(r_{x}/h)^{4}}$

whenever $r_{x}\geq t_{1}h$, where $r_{x}=\inf_{y\in S^{c}}\|x-y\|_{2}$. If
$0<h\leq h_{0}=\min(\frac{1}{C_{1}k!},\frac{1}{t_{1}^{2}})$, we can always
take $r=\sqrt{h}$, and the bound on the right hand side simplifies to
$1-\frac{C_{1}k!}{(r/h)^{4}}\geq 1-h$.

###### Proof.

Let $Z$ be an $\mathbb{R}^{d}$-valued random vector with probability density
$z\mapsto\kappa(\|z\|_{2})$, then

$\displaystyle 1-\int_{B(x,r)}K_{h}(x,y)\,dy$ $\displaystyle=\Pr(x+hZ\notin
B(x,r))$ $\displaystyle=\Pr\left(\|Z\|_{2}\geq\frac{r}{h}\right)\leq
C_{1}(r/h)^{(d+1-\rho)}e^{-(r/h)^{\rho}}$
$\displaystyle\leq\frac{C_{1}k!}{(r/h)^{k\rho-(d+1-\rho)}}\leq\frac{C_{1}k!}{(r/h)^{4}}.$

where the inequality in the second line follows from Lemma 7 whenever $r\geq
t_{1}h$, and the inequality on the last line follows by using
$e^{y}\geq\frac{y^{k}}{k!}$ and $k\rho-(d+1-\rho)\geq 4$. To get the statement
for set $S$, we observe that $1-\int_{S}K_{h}(x,y)\,dy\geq
1-\int_{B(x,r_{x})}K_{h}(x,y)\,dy$.

∎

For any probability measure $\mu$ on $\mathcal{X}$, we define the density
$f_{h,\mu}(y)=\int K_{h}(y,x)\mu(dx)\in\mathscr{D}(\mathcal{X})$ obtained by
convolving $\mu$ with the kernel $K_{h}$. The next result bounds the TV-
distance $\text{d}_{\text{TV}}(f_{h,\mu},f_{h,\nu})$ in terms of the supremum
norm $\|f_{h,\mu}-f_{h,\nu}\|_{\infty}$ when measures $\mu$ and $\nu$ are
supported on $S$.

######  Corollary 1.

Suppose Assumptions C.2 and C.4 hold and $\mu$ and $\nu$ are two probability
measures supported on $S$. Then whenever $h\leq 1/t_{1}$,

$\text{d}_{\text{TV}}(f_{h,\mu},f_{h,\nu})\leq\frac{v_{d}(R+1)^{d}}{2}\|f_{h,\mu}-f_{h,\nu}\|_{\infty}+C_{1}h^{d+1-\rho}{e^{-h^{-1/\rho}}}$

where $v_{d}$ is the volume of the unit ball in $\mathbb{R}^{d}$, and $t_{1}$
is as defined in Lemma 7.

###### Proof.

We first claim that

$\displaystyle\int_{\|y\|\geq R+1}f_{h,\mu}(y)dy\leq
C_{1}(1/h)^{d+1-\rho}e^{-(1/h)^{\rho}}\text{ for any $h\leq 1/t_{1}$}.$ (18)

To see this, we note that $f_{h,\mu}(y)=\int_{S}K_{h}(x,y)\mu(dx)$, since
$\mu$ is supported on $S$ and $K_{h}$ is symmetric. Thus by Fubini’s theorem

$\int_{\|y\|\geq R+r}f_{h,\mu}(y)dy=\int_{S}\left(\int_{\|y\|\geq
R+r}K_{h}(x,y)dy\right)\mu(dx).$

Next, note that the proof of Lemma 9 shows that

$\int_{\|y\|\geq R+1}K_{h}(x,y)dy\leq 1-\int_{B(x,1)}K_{h}(x,y)dy\leq
C_{1}(1/h)^{d+1-\rho}e^{-(1/h)^{\rho}}$

for any $x\in S$ since $B(x,1)\subseteq B(0,R+1)$ whenever $x\in S\subseteq
B(0,R)$, proving eq. 18.

To finish the proof of the lemma, observe that

$\displaystyle\text{d}_{\text{TV}}(f_{h,\mu},f_{h,\nu})$
$\displaystyle=\frac{1}{2}\int_{B(0,R+1)}|f_{h,\mu}(x)-f_{h,\nu}(x)|dx+\frac{1}{2}\int_{\|x\|\geq
R+1}|f_{h,\mu}(x)-f_{h,\nu}(x)|dx$
$\displaystyle\leq\frac{v_{d}}{2}(R+1)^{d}\|f_{h,\mu}-f_{h,\nu}\|_{\infty}+C_{1}h^{d+1-\rho}{e^{-h^{-1/\rho}}}$

where the bound on the second term follows from eq. 18. ∎

Next, we can see how well the convolved density $\widetilde{q}_{h}=(K_{h}\star
q)\in\mathscr{D}(\mathcal{X})$ approximates the density
$q\in\mathscr{D}(\mathcal{X})$. For instance, if the density $q$ is supported
on a bounded set $S\subseteq\mathbb{R}^{d}$ with non-zero Lebesgue measure
$V_{S}$, with boundary functional $\phi(r)=\frac{\lambda(S\setminus
S_{-r})}{\lambda(S)}$ (see Assumption C.1), then the following Lemma provides
an upper bound on the mass placed by the convolved density $\widetilde{q}_{h}$
outside the set $S$.

######  Lemma 10.

Suppose that Assumption C.1 and Assumption C.4 hold. For any probability
density $q\in\mathscr{D}(\mathcal{X})$ and density bounded above by $1/\gamma$
and supported on the set $S$,

$\widetilde{q}_{h}(S^{c})\doteq\int_{S^{c}}\widetilde{q}_{h}(x)dx\leq
h+\frac{V_{S}}{\gamma}\phi(\sqrt{h})$

whenever $h\leq h_{0}$, where $h_{0}$ is as given in Lemma 9.

###### Proof.

We use the following chain of arguments:

$\displaystyle\widetilde{q}_{h}(S^{c})$
$\displaystyle=\int_{S^{c}}\widetilde{q}_{h}(x)dx=\int_{S^{c}}\int_{S}q(y)K_{h}(x,y)dydx$
$\displaystyle=\int_{S}q(y)\int_{S^{c}}K_{h}(x,y)\,dx\,dy$
$\displaystyle=\int_{S_{-\sqrt{h}}}q(y)\int_{S^{c}}K_{h}(x,y)\,dx\,dy+\int_{S\setminus
S_{-\sqrt{h}}}q(y)\int_{S^{c}}K_{h}(x,y)\,dx\,dy$ $\displaystyle\leq
h+\int_{S\setminus S_{-\sqrt{h}}}q(y)\,dy\leq
h+\frac{V_{S}}{\gamma}\phi(\sqrt{h}),$

where the first inequality uses
$\int_{S^{c}}K_{h}(x,y)dx=1-\int_{S}K_{h}(y,x)dx$ is bounded above by $h$ if
$y\in S_{-\sqrt{h}}$ (Lemma 9) or by one if $y\in S\setminus S_{-\sqrt{h}}$,
and the second inequality holds from the definition of boundary functional
$\phi$ and the upper bound on the density $q$. ∎

For a set $S\subseteq\mathbb{R}^{d}$, let
$\operatorname{KL}_{S}(q|p)=\int_{S}q(x)\log\frac{p(x)}{q(x)}\,dx$. The
following lemma provides a useful trick to translate between
$\operatorname{KL}$ and $\text{d}_{\text{TV}}$ expressions for densities that
are not supported on $S$ to densities that are supported on $S$.

######  Lemma 11.

Suppose $q\in\mathscr{D}(\mathcal{X})$ is a density that may not be supported
on $S$. Then there is a density $\bar{q}$ supported on $S$ such that

$\operatorname{KL}_{S}(q|p_{\theta})=(1-q(S^{c}))(\operatorname{KL}(\bar{q}|p_{\theta})+\log(1-q(S^{c})))$

and
$\text{d}_{\text{TV}}(\bar{q},p_{0})\leq\text{d}_{\text{TV}}(q,p_{0})+q(S^{c}).$

###### Proof.

We will take $\bar{q}(x)=\frac{q(x)}{q(S)}I\\{x\in S\\}$ to be the restriction
of the density $q$ to $S$. It is straightforward to see that the equality for
the KL terms hold. The TV bound follows from the triangle inequality, noting
that
$\text{d}_{\text{TV}}(\bar{q},q)=\frac{1}{2}\int_{\mathbb{R}^{d}}\lvert\bar{q}(x)-q(x)\rvert
dx=q(S^{c})$. ∎

###  C.3 Proof of Theorem 1

####  C.3.1 Uniform convergence of KL and TV estimators

The main result of this subsection is the following.

######  Lemma 12.

There exists an absolute constant $c_{1}>0$ such that the following holds.
Suppose observations $x_{1},\ldots,x_{n}$ are drawn i.i.d. from $p_{0}$, and
that Assumption C.2 and Assumption C.4 hold. Let $\hat{q}_{w}$ be as defined
in Definition C.1. Let $\hat{p}=\hat{q}_{o}$, where
$o=(1/n,\ldots,1/n)\in\Delta_{n}$, be the kernel-density estimator for $p_{0}$
based on observations $x_{1},\ldots x_{n}$, and let
$\hat{p}_{\gamma}(\cdot)=\min(\max(\hat{p}(\cdot),\gamma),1/\gamma)$ be its
truncated version. With probability at least $1-\delta$, we have

$\displaystyle\left|\left(\|\hat{q}_{w}-p_{0}\|_{1}-\hat{q}_{w}(S^{c})\right)-\frac{1}{n}\sum_{i=1}^{n}\left|\frac{\hat{q}_{w}(x_{i})}{\hat{p}_{\gamma}(x_{i})}-1\right|\right|$
$\displaystyle\leq\frac{c_{1}u}{\gamma^{3}}\left(\frac{c_{0}}{\sqrt{n}h^{d}}+\sqrt{\frac{2}{n}\log\frac{6}{\delta}}+\text{d}_{\text{TV}}(\hat{p},p_{0})\right)\hskip
10.00002pt\text{ and }$
$\displaystyle\left|\operatorname{KL}_{S}(\hat{q}_{w}|p_{\theta})-\frac{1}{n}\sum_{i=1}^{n}\frac{\hat{q}_{w}(x_{i})}{\hat{p}_{\gamma}(x_{i})}\log\frac{\hat{q}_{w}(x_{i})}{p_{\theta}(x_{i})}\right|$
$\displaystyle\leq\left(\frac{c_{1}u}{\gamma^{3}}\log\frac{u}{\ell\gamma}\right)\left(\frac{c_{0}}{\sqrt{n}h^{d}}+\sqrt{\frac{2}{n}\log\frac{6}{\delta}}+\text{d}_{\text{TV}}(\hat{p},p_{0})\right).$

uniformly over all
$w\in\mathcal{W}_{\ell,u}=\\{w\in\Delta_{n}\,:\,\hat{q}_{w}(x_{i})\in[\ell,u]\text{
for all }i\in[n]\\}$, where thresholds $u,l$ are chosen so that
$u\geq\max(1,\gamma e)\geq 1\geq\ell$ and $\|f\|_{1}=\int|f(x)|dx$.

To establish this result, we will use techniques from uniform law of large
numbers over a class of functions
$\mathscr{F}\subseteq\\{f:S\rightarrow\mathbb{R}\\}$. For a fixed class
$\mathscr{F}$, given i.i.d. samples $x_{1},\ldots,x_{n}$ from density $p_{0}$
supported on $S\subseteq\mathcal{X}$, we consider the empirical Rademacher
complexity (e.g. Boucheron et al. [2005]) of the function class $\mathscr{F}$
defined as:

$\mathcal{R}_{n}(\mathscr{F})=\mathbb{E}_{\epsilon}\left[\sup_{f\in\mathscr{F}}\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}f(x_{i})\right|\right]$
(19)

where the expectation is over Rademacher random variables
$\epsilon_{1},\ldots\epsilon_{n}\overset{i.i.d.}{\sim}\operatorname{Uniform}(\\{-1,1\\})$.
The Rademacher complexity is a measure of richness of a function class that
can be used to obtain a uniform law of large numbers result like the following
standard result.

######  Lemma 13 (c.f. Theorem 3.2 of [Boucheron et al., 2005]).

Let $\mathscr{F}\subset\\{f:S\rightarrow[-a,a]\\}$ be a fixed class of bounded
functions and suppose $\delta>0$. If $x_{1},\ldots,x_{n}\sim p_{0}$, then with
probability at least $1-\delta$

$\sup_{f\in\mathscr{F}}\left|\frac{1}{n}\sum_{i=1}^{n}f(x_{i})-\int
f(x)p_{0}(x)dx\right|\leq
2\mathcal{R}_{n}(\mathscr{F})+a\sqrt{\frac{2}{n}\log\frac{2}{\delta}}.$

Thus a typical task to obtain uniform laws of large numbers is to obtain upper
bounds on $\mathcal{R}_{n}(\mathscr{F})$ for various function classes
$\mathscr{F}$. To this end, the following results will be useful:

######  Lemma 14 (c.f. Theorem 3.3 of [Boucheron et al., 2005]).

Suppose $g:S\rightarrow\mathbb{R}$ is a bounded function,
$\mathscr{F}\subset\\{f:S\rightarrow\mathbb{R}\\}$, and
$\psi:\mathbb{R}\rightarrow\mathbb{R}$ is a function with Lipschitz constant
$L$. Then

$\displaystyle\mathcal{R}_{n}(\\{x\mapsto g(x)f(x):f\in\mathscr{F}\\})$
$\displaystyle\leq\mathcal{R}_{n}(\mathscr{F})\sup_{x\in S}|g(x)|$
$\displaystyle\mathcal{R}_{n}(\\{x\mapsto\psi(f(x)):f\in\mathscr{F}\\})$
$\displaystyle\leq L\mathcal{R}_{n}(\mathscr{F})+\frac{|\psi(0)|}{\sqrt{n}}.$

###### Proof.

The above statements with $\psi(0)=0$ follow from Theorem 3.3 of [Boucheron et
al., 2005]. To handle the case $\psi(0)\neq 0$, define
$\tilde{\psi}=\psi-\psi(0)\boldsymbol{1}$ where $\boldsymbol{1}$ denotes the
function taking the constant value one, and note that

$\displaystyle\mathcal{R}_{n}(\\{\psi\circ f:f\in\mathscr{F}\\})$
$\displaystyle=\mathcal{R}_{n}(\\{\tilde{\psi}\circ
f+\psi(0)\boldsymbol{1}:f\in\mathscr{F}\\})$
$\displaystyle=\mathcal{R}_{n}(\\{\tilde{\psi}\circ
f:f\in\mathscr{F}\\})+\mathcal{R}_{n}(\\{\psi(0)\boldsymbol{1}\\})$
$\displaystyle\leq
L\mathcal{R}_{n}(\mathscr{F})+|\psi(0)|\mathcal{R}_{n}(\boldsymbol{1})$

where we have used that
$\mathcal{R}_{n}(\\{\boldsymbol{1}\\})\leq\mathbb{E}_{\epsilon}\lvert\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\rvert\leq\sqrt{\mathbb{E}_{\epsilon}\left(\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\right)^{2}}=n^{-1/2}.$
∎

######  Lemma 15 (Lemma 22 of [Bartlett and Mendelson, 2002]).

Let $k:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}$ be a positive
definite kernel satisfying $k(x,x)\leq c$ for all $x\in\mathcal{X}$. Then, for
the function class

$\mathscr{F}_{a}=\bigg{\\{}\cdot\mapsto\sum_{i=1}^{m}w_{i}k(\cdot,y_{i})\,:\,m\geq
1,y_{i}\in\mathcal{X},w_{i}\in\mathbb{R},\text{ and
}\sum_{i,j}w_{i}w_{j}k(y_{i},y_{j})\leq a^{2}\bigg{\\}},$

we have $\mathcal{R}_{n}(\mathscr{F}_{a})\leq 2a\sqrt{\frac{c}{n}}$.

We will now use the above results to bound the Monte Carlo estimation error
uniformly over functions generated from a data-dependent function family
$\\{\hat{q}_{w}:w\in\Delta_{n}\\}$.

######  Lemma 16.

Suppose bounded functions $\alpha,\beta,\eta:S\to\mathbb{R}$ and a Lipschitz
function $\Phi:\mathbb{R}\to[-M,M]$ with Lipschitz constant $L$ are given, and
suppose that Assumption C.4 holds. Given a function $q:S\to\mathbb{R}$, denote
$\psi(q,x)=\eta(x)\Phi(\alpha(x)q(x)+\beta(x))$. Then for any
$\delta\in(0,2/e)$, with probability $1-\delta$ it holds that:

$\sup_{w\in\Delta_{n}}\left\lvert\frac{1}{n}\sum_{i=1}^{n}\psi(\hat{q}_{w},x_{i})-\int\psi(\hat{q}_{w},x)p_{0}(x)dx\right\rvert\leq\frac{C_{1}}{h^{d}\sqrt{n}}+C_{2}\sqrt{\frac{2}{n}\log\frac{2}{\delta}}$

where $\hat{q}_{w}$ is as in Definition C.1,
$C_{1}=4\|\eta\|_{\infty}\|\alpha\|_{\infty}Lc_{0}$, and
$C_{2}=\sqrt{2}\|\eta\|_{\infty}(L\|\beta\|_{\infty}+|\Phi(0)|)+\|\eta\|_{\infty}M$.

###### Proof.

Using $\hat{\mathcal{Q}}$ to denote the data dependent class of functions
$\\{\hat{q}_{w}\mid w\in\Delta_{n}\\}$, and taking $\kappa=K_{h}$,
$c=c_{0}/h^{d}$, and $a=\sqrt{c}$ in Lemma 15, let us first note that
$\hat{\mathcal{Q}}\subseteq\mathscr{F}_{a}$. Indeed, this holds since for any
$w=(w_{1},\ldots,w_{n})\in\Delta_{n}$ we have
$\hat{q}_{w}(\cdot)=\sum_{i=1}^{n}K_{h}(\cdot,x_{i})w_{i}$ and

$\sum_{i,j=1}^{n}w_{i}w_{j}K_{h}(x_{i},x_{j})\leq
c\sum_{i=1}^{n}\sum_{j=1}^{n}w_{i}w_{j}=c,$

where the inequality follows from the Cauchy Schwarz bound
$K_{h}(x,y)\leq\sqrt{K_{h}(x,x)K_{h}(y,y)}$ using the positive definiteness of
the kernel $K_{h}$, and the bound $K_{h}(x,x)\leq c_{0}/h^{d}=c$ from
Assumption C.4. Further, note by Lemma 15 that
$\mathcal{R}_{n}(\mathscr{F}_{a})\leq\frac{2c_{0}}{h^{d}\sqrt{n}}$.

Next, let $\mathscr{G}$ denote the fixed function class
$\\{x\mapsto\psi(f,x)|f\in\mathscr{F}_{a}\\}$. Repeated application of Lemma
14 shows:

$\displaystyle\mathcal{R}_{n}(\mathscr{G})$
$\displaystyle\leq\|\eta\|_{\infty}\|\alpha\|_{\infty}L\mathcal{R}_{n}(\mathscr{F}_{a})+\frac{\|\eta\|_{\infty}(L\|\beta\|_{\infty}+|\Phi(0)|)}{\sqrt{n}}$
$\displaystyle\leq\frac{2\|\eta\|_{\infty}\|\alpha\|_{\infty}Lc_{0}}{h^{d}\sqrt{n}}+\frac{\|\eta\|_{\infty}(L\|\beta\|_{\infty}+|\Phi(0)|)}{\sqrt{n}}.$

Thus we can complete the proof by an application of Lemma 13 for the bounded
class of functions $\mathscr{F}=\mathscr{G}$, and noting the inclusion
$\hat{\mathcal{Q}}\subseteq\mathscr{F}_{a}$. ∎

With these uniform convergence results in place, now we can prove the main
result of this section:

###### Proof of Lemma 12.

By assumption

$\frac{1}{n}\sum_{i=1}^{n}\left|\frac{1}{p_{0}(x_{i})}-\frac{1}{\hat{p}_{\gamma}(x_{i})}\right|\leq\frac{1}{\gamma^{2}n}\sum_{i=1}^{n}\left|p_{0}(x_{i})-\hat{p}_{\gamma}(x_{i})\right|\leq\frac{1}{\gamma^{2}n}\sum_{i=1}^{n}(\left|p_{0}(x_{i})-\hat{p}(x_{i})\right|\wedge\gamma^{-1}),$

where the last inequality uses the fact that $\lvert
p_{0}(\cdot)-\hat{p}_{\gamma}(\cdot)\rvert\leq\min(1/\gamma,\lvert
p_{0}(\cdot)-\hat{p}(\cdot)\rvert)$ since
$p_{0}(\cdot),\hat{p}_{\gamma}(\cdot)\in[1/\gamma,\gamma]$. Recall
$\hat{p}=\hat{q}_{o}$, and hence we may apply Lemma 16 with
$\Phi(x)=|x|\wedge\gamma^{-1}$, $\beta=p_{0}$, $\alpha(\cdot)=\eta(\cdot)=1$,
and $w=o$, to show with probability $1-\delta/3$:

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\left|p_{0}(x_{i})-\hat{p}(x_{i})\right|\wedge\gamma^{-1}$
$\displaystyle\leq\int(\gamma^{-1}\wedge|p_{0}(x)-\hat{p}(x)|)p_{0}(x)dx+\left(\frac{4c_{0}}{h^{d}\sqrt{n}}+\frac{3}{\gamma}\sqrt{\frac{2}{n}\log\frac{6}{\delta}}\right)$
$\displaystyle\leq\frac{2}{\gamma}\text{d}_{\text{TV}}(\hat{p},p_{0})+\left(\frac{4c_{0}}{h^{d}\sqrt{n}}+\frac{3}{\gamma}\sqrt{\frac{2}{n}\log\frac{6}{\delta}}\right)=\frac{\nu}{\gamma},$

where $\nu=2\text{d}_{\text{TV}}(\hat{p},p_{0})+\frac{4\gamma
c_{0}}{h^{d}\sqrt{n}}+3\sqrt{\frac{2}{n}\log\frac{6}{\delta}}$.

Turning to the $\ell_{1}$-bound, for any $w\in\mathcal{W}_{\gamma}$, we have

$\displaystyle\left|\frac{1}{n}\sum_{i=1}^{n}\left|\frac{\hat{q}_{w}(x_{i})}{\hat{p}_{\gamma}(x_{i})}-1\right|-\frac{1}{n}\sum_{i=1}^{n}\left|\frac{\hat{q}_{w}(x_{i})}{{p}_{0}(x_{i})}-1\right|\right|$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\left|\left|\frac{\hat{q}_{w}(x_{i})}{\hat{p}_{\gamma}(x_{i})}-1\right|-\left|\frac{\hat{q}_{w}(x_{i})}{{p}_{0}(x_{i})}-1\right|\right|$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\left|\frac{\hat{q}_{w}(x_{i})}{\hat{p}_{\gamma}(x_{i})}-\frac{\hat{q}_{w}(x_{i})}{{p}_{0}(x_{i})}\right|\leq\frac{\nu
u}{\gamma^{3}}.$

Here the first inequality follows from the triangle inequality, the second
follows from the reverse triangle inequality, and the last follows from the
upper bound on $\hat{q}_{w}$ and the bounds at the beginning of the proof.
Observe that $\int\lvert\frac{q(x)}{{p_{0}}(x)}-1\rvert
p_{0}(x)dx=\|q-p_{0}\|_{1}-q(S^{c})$ for any density
$q\in\mathscr{D}(\mathcal{X})$. Next, we apply Lemma 16 with
$\Phi(x)=|x|\wedge M$, $M=u/\gamma$, $\alpha=1/p_{0}$, $\beta=-1$, $\eta=1$,
noting that:

$\psi(\hat{q}_{w},\cdot)=\left\lvert\frac{\hat{q}_{w}(\cdot)}{p_{0}(\cdot)}-1\right\rvert\wedge
M=\left\lvert\frac{\hat{q}_{w}(\cdot)}{p_{0}(\cdot)}-1\right\rvert$

for each $w\in\mathcal{W}_{\ell,u}$. Thus we have

$\displaystyle\left|\frac{1}{n}\sum_{i=1}^{n}\left|\frac{\hat{q}_{w}(x_{i})}{{p_{0}}(x_{i})}-1\right|-\|\hat{q}_{w}-p_{0}\|_{1}-\hat{q}_{w}(S^{c})\right|\leq\frac{4c_{0}}{\gamma\sqrt{n}h^{d}}+\left(3+\frac{u}{\gamma}\right)\sqrt{\frac{2}{n}\log\frac{6}{\delta}},$

with probability at least $1-\delta/3$ for all $w\in\mathcal{W}_{\ell,u}$
simultaneously.

Turning to the KL-bound, a similar chain of reasoning gives us

$\displaystyle\left|\frac{1}{n}\sum_{i=1}^{n}\frac{q_{w}(x_{i})}{\hat{p}(x_{i})}\log\frac{q_{w}(x_{i})}{p_{\theta}(x_{i})}-\frac{1}{n}\sum_{i=1}^{n}\frac{q_{w}(x_{i})}{p_{0}(x_{i})}\log\frac{q_{w}(x_{i})}{p_{\theta}(x_{i})}\right|\leq\frac{\nu
u}{\gamma^{3}}\log\frac{u}{\gamma},$

where we have additionally used the lower bound
$p_{\theta}(\cdot)\in[\gamma,1/\gamma]$. Next, we will invoke Lemma 16 with
$\alpha=1/p_{\theta},\beta=0,\eta=p_{\theta}/p_{0}$ and $\Phi(x)=k(x)\log
k(x)$ where $k(x)=\min(\max(x,u/\gamma),l\gamma)$, noting that the function
$\Phi$ is bounded within radius $M=\frac{u}{\gamma}\log\frac{u}{\gamma}$ and
is a Lipschitz function with Lipschitz constant bounded by
$L=\sup_{x\in[l\gamma,u/\gamma]}|1+\log x|\leq 2\log\frac{u}{l\gamma}$. Then,
using the bounds
$C_{1}\leq\tilde{C}_{1}=\frac{8c_{0}}{\gamma^{3}}\log\frac{u}{l\gamma}$ and
$C_{2}\leq\tilde{C}_{2}=\frac{3u}{\gamma^{3}}\log\frac{u}{\gamma}$, Lemma 16
shows that with probability $1-\delta/3$,

$\left\lvert\frac{1}{n}\sum_{i=1}^{n}\frac{\hat{q}_{w}(x_{i})}{p_{0}(x_{i})}\log\frac{\hat{q}_{w}(x_{i})}{p_{\theta}(x_{i})}-\operatorname{KL}_{S}(\hat{q}_{w}|p_{\theta})\right\rvert\leq\frac{\tilde{C_{1}}}{\sqrt{n}h^{d}}+\tilde{C_{2}}\sqrt{\frac{2}{n}\log\frac{6}{\delta}}$

for each $w\in\mathcal{W}_{\ell,u}$ simultaneously, since
$\psi(\hat{q}_{w},\cdot)=\frac{\hat{q}_{w}(\cdot)}{p_{0}(\cdot)}\log\frac{\hat{q}_{w}(\cdot)}{p_{\theta}(\cdot)}$
and $\operatorname{KL}_{S}(\hat{q}_{w}|p_{\theta})=$
$\int\psi(\hat{q}_{w},x)p_{0}(x)dx$ whenever $w\in\mathcal{W}_{\ell,u}$.
Finally, we obtain the lemma statement by using the union bound and putting
all the display equations together, noting that $u/\gamma\geq e$ and
$\gamma\leq 1$. ∎

####  C.3.2 Sup-norm approximation of kernel density estimates

Recall our notation for the truncated probability simplex
$\Delta_{n}^{\beta}=\\{(w_{1},\ldots,w_{n})\in\Delta_{n}:\frac{\beta}{n}\leq
w_{i}\leq\frac{1}{n\beta}\\}$. The next lemma provides approximation results
for the subset of densities
$\\{\hat{q}_{w}:w\in\Delta_{n}^{\gamma^{2}/4}\\}\subseteq\mathscr{D}(\mathcal{X})$
that hold with arbitrary high probability when $n$ is large enough. In
particular, Item 1 shows that $\hat{p}$ approximates well the convolved
density $K_{h}\star p_{0}$, Item 2 provides upper and lower bounds on the
density $\hat{q}_{w}$, Item 3 bounds the mass of $\hat{q}_{w}$ outside the set
$S$, and Item 4 shows that any convolved density of the form $K_{h}\star q$
can be approximated well by a density of the form $\hat{q}_{w}$, whenever
$q(\cdot)\in[\gamma,1/\gamma]$ is a density supported on $S$.

######  Lemma 17.

Suppose that Assumption C.2 and Assumption C.4 hold and $\delta\in(0,1)$ is
such that $n\geq\frac{2}{\gamma^{4}}\log\frac{12}{\delta}$. Further suppose
that $q\in\mathscr{D}(\mathcal{X})$ is a density supported on $S$ satisfying
$\gamma\leq q(x)\leq 1/\gamma$ for each $x\in S$. If $x_{1},\ldots,x_{n}\sim
p_{0}$, with probability $1-\delta$, the following items hold:

  1. 1.

$\|\hat{p}-K_{h}\star
p_{0}\|_{\infty}\leq\frac{6c_{0}}{\sqrt{n}h^{d}}\sqrt{\log\frac{6}{\delta}}$.

  2. 2.

$\frac{\gamma^{2}}{4}\left(\gamma-\frac{6c_{0}}{\sqrt{n}h^{d}}\sqrt{\log\frac{2}{\delta}}\right)\leq\hat{q}_{w}(x)\leq\frac{4}{\gamma^{2}}\left(\gamma^{-1}+\frac{6c_{0}}{\sqrt{n}h^{d}}\sqrt{\log\frac{2}{\delta}}\right)$
uniformly over $w\in\Delta_{n}^{\gamma^{2}/2}$ and $x\in\mathbb{R}^{d}$.

  3. 3.

$\hat{q}_{w}(S^{c})\leq\frac{4}{\gamma^{2}}\left(h+\frac{V_{S}}{\gamma}\phi(\sqrt{h})+\sqrt{\frac{1}{2n}\log\frac{3}{\delta}}\right)$
uniformly over $w\in\Delta_{n}^{\gamma^{2}/2}$, whenever $h\leq h_{0}$, where
$h_{0}$ is as defined in Lemma 9.

  4. 4.

Denote $\widetilde{q}_{h}=K_{h}\star q$. There is a
$w\in\Delta_{n}^{\gamma^{2}/2}$ such that
$\|\hat{q}_{w}-\widetilde{q}_{h}\|_{\infty}\leq\frac{8c_{0}}{\gamma^{4}h^{d}}\sqrt{\frac{1}{n}\log\frac{12}{\delta}}$.
In particular,

$\lvert\operatorname{KL}_{S}(\hat{q}_{w}|p_{\theta})-\operatorname{KL}_{S}(\widetilde{q}_{h}|p_{\theta})\rvert\leq\frac{C}{h^{d}\sqrt{n}}\sqrt{\log\frac{12}{\delta}}$

where $C=\frac{8c_{0}}{\gamma^{4}}V_{S}(1+\log(\frac{u}{\gamma l}))$ and $u$
and $l$ are the upper and lower bounds on $\hat{q}_{w}$ in Item 2. We take
$C=\infty$ if $l\leq 0.$

###### Proof of Lemma 17.

Combining Lemma 13 with Lemma 15 shows that with probability $1-\delta/3$:

$\displaystyle\left|\frac{1}{n}\sum_{i=1}^{n}K_{h}(x_{i},x)-\int
K_{h}(y,x)p_{0}(y)dy\right|$
$\displaystyle\leq\frac{4c_{0}}{\sqrt{n}h^{d}}+\frac{c_{0}}{\sqrt{n}h^{d}}\sqrt{2\log\frac{6}{\delta}}\leq\frac{6c_{0}}{\sqrt{n}h^{d}}\sqrt{\log\frac{6}{\delta}}.$

for all $x\in\mathbb{R}^{d}$ simultaneously. Noting that
$\hat{p}(x)=\frac{1}{n}\sum_{i}K_{h}(x_{i},x)$ and $(K_{h}\star p_{0})(x)=\int
K_{h}(y,x)p_{0}(y)dy$, the uniform bound in Item 1 follows.

To show Item 2, note for each $w\in\Delta_{n}^{\gamma^{2}/4}$ that

$\frac{\gamma^{2}\hat{p}(x)}{4}\leq\hat{q}_{w}(x)=\sum_{i=1}^{n}w_{i}K_{h}(x_{i},x)\leq\frac{4\hat{p}(x)}{\gamma^{2}}\quad\text{for
each }x\in\mathbb{R}^{d}.$

Item 2 now follows from the bound in Item 1 and as $(K_{h}\star
p_{0})(\cdot)\in[\gamma,1/\gamma]$, since $\int K_{h}(y,x)dy=1$ and
$p_{0}(\cdot)\in[\gamma,1/\gamma]$.

Now we will show Item 3. For arbitrary $w\in\Delta_{n}^{\gamma^{2}/4}$ observe
that

$\hat{q}_{w}(S^{c})\leq\frac{4\hat{p}(S^{c})}{\gamma^{2}}.$

An application of Hoeffding’s inequality to the function
$f(\cdot)=\int_{S^{c}}K_{h}(\cdot,x)dx\in[0,1]$ implies that with probability
$1-\delta/3$,

$\displaystyle\hat{p}(S^{c})=\frac{1}{n}\sum_{i=1}^{n}f(x_{i})\,dx$
$\displaystyle\leq\int
f(y)p_{0}(y)dydx+\sqrt{\frac{1}{2n}\log\frac{3}{\delta}}$
$\displaystyle=\int_{S^{c}}\int
K_{h}(y,x)p_{0}(y)dydx+\sqrt{\frac{1}{2n}\log\frac{3}{\delta}}$
$\displaystyle\leq
h+\frac{V_{S}}{\gamma}\phi(\sqrt{h})+\sqrt{\frac{1}{2n}\log\frac{3}{\delta}},$

where, the second inequality follows by invoking Lemma 10 with the choice
$q=p_{0}$ whenever $h\leq h_{0}$.

Finally to show Item 4, we choose the weights
$w_{i}=\frac{q(x_{i})}{Zp_{0}(x_{i})}$ for $i=1,\ldots,n$, where
$Z=\sum_{i=1}^{n}\frac{q(x_{i})}{p_{0}(x_{i})}$. By Hoeffding’s inequality, we
have that with probability at least $1-\delta/6$,

$|Z-n|=|Z-\mathbb{E}[Z]|\leq\frac{1}{\gamma^{2}}\sqrt{\frac{n}{2}\log\frac{12}{\delta}}.$

In the event that this holds, if
$n\geq\frac{2}{\gamma^{4}}\log\frac{12}{\delta}$, then $Z\in[n/2,3n/2]$ and we
have that $w\in\Delta_{n}^{\gamma^{2}/4}$. Moreover, it implies that for any
$x\in\mathbb{R}^{d}$,

$\displaystyle\left|\hat{q}_{w}(x)-\frac{1}{n}\sum_{i=1}^{n}\frac{q(x_{i})}{p_{0}(x_{i})}K_{h}(x_{i},x)\right|$
$\displaystyle=\left|\sum_{i=1}^{n}w_{i}K_{h}(x_{i},x)-\frac{1}{n}\sum_{i=1}^{n}\frac{q(x_{i})}{p_{0}(x_{i})}K_{h}(x_{i},x)\right|$
$\displaystyle\leq\left|\frac{n-Z}{Z}\right|\max_{i\in[n]}\frac{q(x_{i})}{p_{0}(x_{i})}K_{h}(x_{i},x)$
$\displaystyle\leq\frac{2}{n}|n-Z|\frac{c_{0}}{\gamma^{2}h^{d}}\leq\frac{2c_{0}}{\gamma^{4}h^{d}}\sqrt{\frac{1}{n}\log\frac{12}{\delta}}.$

Next, observe that Lemma 14 and Lemma 15 imply that the Rademacher complexity
$\mathcal{R}_{n}$ of the function class
$\\{\cdot\mapsto\frac{q(\cdot)}{p_{0}(\cdot)}K_{h}(\cdot,x)\,:\,x\in\mathbb{R}^{d}\\}$
on domain $S$ is bounded above by $\frac{2c_{0}}{\gamma^{2}h^{d}\sqrt{n}}$.
Therefore by Lemma 13, with probability $1-\delta/6$, we have

$\displaystyle\sup_{x\in\mathbb{R}^{d}}\left|\frac{1}{n}\sum_{i=1}^{n}\frac{q(x_{i})}{p_{0}(x_{i})}K_{h}(x_{i},x)-\int_{S}\frac{q(y)}{p_{0}(y)}K_{h}(y,x)\,p_{0}(y)dy\right|\leq\frac{c_{0}}{\gamma^{2}h^{d}\sqrt{n}}\left(4+\sqrt{2\log\frac{12}{\delta}}\right).$

Since $p_{0},q$ are both supported on $S$ with $\inf_{x\in S}p_{0}(x)>0$, we
have $(K_{h}\star
q)(x)=\int_{S}q(y)K_{h}(x,y)\,dy=\int_{S}\frac{q(y)}{p_{0}(y)}K_{h}(x,y)p_{0}(y)dy$.
Hence combining the previous two display equations and using the union bound,
the uniform bound in Item 4 between $\hat{q}_{w}$ and $\widetilde{q}_{h}$ is
seen to hold with probability $1-\delta/3$. Finally to bound the differences
between the KL terms, note that

$\displaystyle\lvert\operatorname{KL}_{S}(\hat{q}_{w}|p_{\theta})-\operatorname{KL}_{S}(\widetilde{q}_{h}|p_{\theta})\rvert$
$\displaystyle\leq\int_{S}|\hat{q}_{w}(x)\log\hat{q}_{w}(x)-\widetilde{q}_{h}(x)\log\widetilde{q}_{h}(x)|dx$
$\displaystyle\quad+\int_{S}|\log
p_{\theta}(x)||\hat{q}_{w}(x)-\widetilde{q}_{h}(x)|dx$
$\displaystyle\leq\|\hat{q}_{w}-\widetilde{q}_{h}\|_{\infty}V_{S}(1+\log\frac{u}{\gamma
l}),$

where the last inequality follows by using the Lipschitz continuity of the map
$\Phi(x)=x\log x$ on the interval $[l,u]$, with Lipschitz constants
$1+\log(u/l)$, and using the upper bound $|\log
p_{\theta}(\cdot)|\leq\log(1/\gamma)$.

A final application of the union bound shows that Items 1 through 4 can be
simultaneously satisfied with probability $1-\delta$. ∎

####  C.3.3 KL and TV approximation by kernel smoothed densities

In this section we show that the terms $\operatorname{KL}(q|p_{\theta})$ and
$\text{d}_{\text{TV}}(q,p_{0})$ do not increase by much when a density
$q\in\mathscr{D}(\mathcal{X})$ is replaced by its kernel-smoothed version
$\widetilde{q}_{h}=K_{h}\star q$ for a suitably small bandwidth parameter
$h>0$.

######  Lemma 18.

Suppose Assumptions C.1, C.2, C.3 and C.4 hold. There exists a constant
$\tilde{c}>0$ and $\tilde{h}>0$ depending only on the constants in the above
assumption, such that the following statement holds. Suppose that
$q\in\mathscr{D}(\mathcal{X})$ is supported on $S$ and bounded above by
$1/\gamma$ and $h\leq\tilde{h}$ then

  * •

$\text{d}_{\text{TV}}(\widetilde{q}_{h},p_{0})\leq\text{d}_{\text{TV}}(q,p_{0})+\tilde{c}\left(h^{\alpha/2}+h+\phi(\sqrt{h})\right)$

  * •

$\operatorname{KL}_{S}(\widetilde{q}_{h}|p_{\theta})\leq\operatorname{KL}(q|p_{\theta})+\tilde{c}\left(h^{\alpha/2}+h\log\frac{1}{h}+\phi(\sqrt{h})\log\frac{1}{\phi(\sqrt{h})}\right)$.

We will prove the TV and KL statements separately. We start with the TV
statement.

######  Lemma 19.

Suppose that $q\in\mathscr{D}(\mathcal{X})$ is supported on $S$ and suppose
that Assumptions C.1, C.2, C.3 and C.4 hold. Then

$\text{d}_{\text{TV}}(\widetilde{q}_{h},p_{0})\leq\text{d}_{\text{TV}}(q,p_{0})+V_{S}\left(C_{\alpha}h^{\alpha/2}+h+\frac{\phi(\sqrt{h})}{\gamma}\right)$

whenever $h\in(0,h_{0})$.

###### Proof.

We first observe that for any densities $p,q\in\mathscr{D}(\mathcal{X})$, we
have

$\displaystyle\text{d}_{\text{TV}}(\widetilde{p}_{h},\widetilde{q}_{h})$
$\displaystyle=\frac{1}{2}\int_{\mathbb{R}^{d}}|\mathbb{E}_{Z\sim
K}[q(x-hZ)-p(x-hZ)]|\,dx$ $\displaystyle\leq\frac{1}{2}\mathbb{E}_{Z\sim
K}\int_{\mathbb{R}^{d}}|q(x-hZ)-p(x-hZ)|\,dx$
$\displaystyle=\frac{1}{2}\int_{\mathbb{R}^{d}}|q(x)-p(x)|\,dx=\text{d}_{\text{TV}}(p,q),$

where $Z$ is an $\mathbb{R}^{d}$-valued random vector with probability density
$x\mapsto\kappa(\|x\|_{2})$, and the inequality follows from Jensen’s
inequality and Fubini’s theorem. By the triangle inequality, we then have

$\displaystyle\text{d}_{\text{TV}}(\widetilde{q}_{h},p_{0})\leq\text{d}_{\text{TV}}(\widetilde{q}_{h},K_{h}\star
p_{0})+\text{d}_{\text{TV}}(K_{h}\star
p_{0},p_{0})\leq\text{d}_{\text{TV}}(q,p_{0})+\text{d}_{\text{TV}}(K_{h}\star
p_{0},p_{0}).$

Next, note that for any $x\in S_{-\sqrt{h}}$ we have

$\displaystyle\left|p_{0}(x)-K_{h}\star p_{0}(x)\right|$
$\displaystyle=\left|\int_{\mathbb{R}^{d}}p_{0}(x)K_{h}(x,y)\,dy-\int_{\mathbb{R}^{d}}p_{0}(y)K_{h}(x,y)\,dy\right|$
$\displaystyle\leq\int_{\mathbb{R}^{d}}\left|p_{0}(x)-p_{0}(y)\right|K_{h}(x,y)\,dy$
$\displaystyle=\int_{B(x,\sqrt{h})}\left|p_{0}(x)-p_{0}(y)\right|K_{h}(x,y)\,dy+\int_{B(x,\sqrt{h})^{c}}\left|p_{0}(x)-p_{0}(y)\right|K_{h}(x,y)\,dy$
$\displaystyle\leq C_{\alpha}h^{\alpha/2}+h,$

where the first inequality follows from Jensen’s inequality, and the second
follows from Assumption C.3 and Lemma 9, using the upper bound on the density
$p_{0}(\cdot)\leq 1/\gamma$.

Thus we have

$\displaystyle\text{d}_{\text{TV}}(K_{h}\star p_{0},p_{0})$
$\displaystyle=\frac{1}{2}\int_{\mathbb{R}^{d}}\left|p_{0}(x)-K_{h}\star
p_{0}(x)\right|\,dx$
$\displaystyle=\frac{1}{2}\int_{S_{-\sqrt{h}}}\left|p_{0}(x)-K_{h}\star
p_{0}(x)\right|\,dx+\frac{1}{2}\int_{\mathbb{R}^{d}\setminus
S_{-\sqrt{h}}}\left|p_{0}(x)-K_{h}\star p_{0}(x)\right|\,dx$
$\displaystyle\leq\frac{\lambda(S_{-\sqrt{h}})}{2}\left(C_{\alpha}h^{\alpha/2}+h\right)+\frac{1}{2}\int_{S\setminus
S_{-\sqrt{h}}}\left|p_{0}(x)-(K_{h}\star
p_{0})(x)\right|\,dx+\frac{1}{2}(K_{h}\star p_{0})(S^{c})$ $\displaystyle\leq
V_{S}(C_{\alpha}h^{\alpha/2}+h+\gamma^{-1}\phi(\sqrt{h})).$

where the first inequality follows from the last display equation and using
the fact that $p_{0}(x)=0$ whenever $x\in S^{c}$, and the second inequality
follows by using that $|p_{0}(\cdot)-(K_{h}\star p_{0})(\cdot)|\leq 1/\gamma$
and $\lambda(S\setminus S_{-r})=V_{S}\phi(r)$, along with the bound
$(K_{h}\star p_{0})(S^{c})\leq h+\frac{V_{S}}{\gamma}\phi(\sqrt{h})$ from
Lemma 10. ∎

We now turn to proving the KL bound. To do so, we will use the decomposition
of the KL into negative entropy and cross-entropy and bound each term
separately.

######  Lemma 20.

Suppose Assumptions C.1 and C.4 hold, $q\in\mathscr{D}(\mathcal{X})$ has
support $S$ and is bounded above by $1/\gamma$. Then

$\int_{S}\widetilde{q}_{h}(x)\log\widetilde{q}_{h}(x)dx\leq\int_{S}q(x)\log
q(x)dx+D(h)\left[\frac{d}{2}\log(2\pi
eM)+\left(\frac{d}{2}+1\right)\log\frac{1}{D(h)}\right],$

where
$M=2R^{2}+2v_{d}\left(c_{0}t_{0}^{d+3}+\frac{C_{\rho}}{\rho}\Gamma\left(\frac{d+3}{\rho}\right)\right)$
and $D(h)=h+\frac{V_{S}}{\gamma}\phi(\sqrt{h})$, whenever
$h\leq\min(h_{0},h_{1})$ where $h_{1}=\inf\\{h>0:D(h)>1/e\\}.$

###### Proof.

First let us note that the integrals $\int_{\mathbb{R}^{d}}q(x)\log q(x)dx$
and $\int_{\mathbb{R}^{d}}\widetilde{q}_{h}(x)\log\widetilde{q}_{h}(x)dx$ are
well-defined. Indeed, the first integral is well defined since $q$ is bounded
above by $1/\gamma$ on a set $S$ with finite Lebesgue measure. Although,
$\widetilde{q}_{h}$ can also be shown to be bounded above by $1/\gamma$, its
support is unbounded if the kernel $K_{h}$ also has unbounded support.
Instead, for the existence of the second integral, it suffices to show that
the second moment of $\widetilde{q}_{h}$ is finite (e.g. see Ghourchian et al.
[2017]). To show the latter, we will use the property a random variable $Y$
with density $\widetilde{q}_{h}$, has the same distribution as $X+hZ$, where
$X$ is random variable with density $q$, and let $Z$ be a random variable with
density $x\mapsto\kappa(\|x\|_{2})$ independent of $X$. Hence

$\mathbb{E}_{Y\sim\widetilde{q}_{h}}[\|Y\|_{2}^{2}]=\mathbb{E}_{Z,X}[\|X+hZ\|^{2}]\leq
2R^{2}+2h^{2}v_{d}\left(c_{0}t_{0}^{d+3}+\frac{C_{\rho}}{\rho}\Gamma\left(\frac{d+3}{\rho}\right)\right)=M$
(20)

where we have used the inequality $\|x+z\|_{2}^{2}\leq
2\|x\|_{2}^{2}+2\|z\|_{2}^{2}$ along with the bound on $\mathbb{E}\|Z\|^{2}$
from Lemma 8 and the bound $\mathbb{E}\|X\|^{2}\leq R^{2}$.

Next, let us use the convexity of the function $\Phi:\mathbb{R}_{\geq
0}\to\mathbb{R}$ given by $\Phi(x)=x\log x$ to conclude that

$\displaystyle\int_{\mathbb{R}^{d}}\widetilde{q}_{h}(y)\log\widetilde{q}_{h}(y)dy$
$\displaystyle=\int_{\mathbb{R}^{d}}\Phi(\mathbb{E}_{Z\sim
K}[q(y-hZ)])dy\overset{(i)}{\leq}\int\mathbb{E}_{Z\sim K}[\Phi(q(y-hZ))]dy$
$\displaystyle\overset{(ii)}{=}\mathbb{E}_{Z\sim
K}\int_{\mathbb{R}^{d}}\Phi(q(y-hZ))dy\overset{(iii)}{=}\int_{S}\Phi(q(u))du=\int_{S}q(u)\log
q(u)du$

where we have used Jensen’s inequality in Step (i) and Fubini’s theorem in
Step (ii). In Step (iii) we used the change of variables $u=y-hZ$ as well as
the convention that $\Phi(0)=0$.

Now observe that we can decompose the negative entropy of $\widetilde{q}_{h}$
as

$\displaystyle\int_{S}\widetilde{q}_{h}(y)\log\widetilde{q}_{h}(y)dy$
$\displaystyle=\int_{\mathbb{R}^{d}}\widetilde{q}_{h}(y)\log\widetilde{q}_{h}(y)dy+\int_{S^{c}}\widetilde{q}_{h}(y)\log\frac{1}{\widetilde{q}_{h}(y)}dy.$

Now define the conditional probability density
$\bar{q}(x)=\frac{\widetilde{q}_{h}(x)I\\{x\in
S^{c}\\}}{\widetilde{q}_{h}(S^{c})}$. Then we have the identity

$\displaystyle\int_{S^{c}}\widetilde{q}_{h}(y)\log\frac{1}{\widetilde{q}_{h}(y)}dy=\widetilde{q}_{h}(S^{c})\log\frac{1}{\widetilde{q}_{h}(S^{c})}+\widetilde{q}_{h}(S^{c})\int_{\mathbb{R}^{d}}\bar{q}(y)\log\frac{1}{\bar{q}(y)}dy.$

We now claim that $\bar{q}$ has bounded second moment. To see this, observe
that we can write

$\mathbb{E}_{y\sim\widetilde{q}_{h}}[\|y\|^{2}]=\widetilde{q}_{h}(S)\mathbb{E}_{y\sim\widetilde{q}_{h}}[\|y\|^{2}|y\in
S]+\widetilde{q}_{h}(S^{c})\mathbb{E}_{y\sim\widetilde{q}_{h}}[\|y\|^{2}|y\in
S^{c}].$

Thus,
$\mathbb{E}_{y\sim\bar{q}}[\|y\|^{2}]=\mathbb{E}_{y\sim\widetilde{q}_{h}}[\|y\|^{2}|y\in
S^{c}]\leq M/\widetilde{q}_{h}(S^{c})$ by eq. 20.

Now in order to bound the negative entropy of $\bar{q}$, let
$\mu=\mathbb{E}_{y\sim\bar{q}}[y]$ and
$\sigma^{2}=\mathbb{E}_{y\sim\bar{y}}[\|y-\mu\|^{2}]\leq
M/\widetilde{q}_{h}(S^{c})$ denote the mean and mean squared error of
$\bar{q}$, and let
$g(x)=\frac{1}{(2\pi\sigma^{2})^{d/2}}e^{-\frac{\|x-\mu\|^{2}}{2\sigma^{2}}}$
be the probability density function of the the multivariate normal
distribution with the same first two moments. Examining the property
$\operatorname{KL}(\bar{q}|g)\geq 0$, we obtain

$\int_{\mathbb{R}^{d}}\bar{q}(y)\log\frac{1}{\bar{q}(y)}dy\leq\frac{1}{2}+\frac{d}{2}\log(2\pi\sigma^{2})\leq\frac{d}{2}\log(2\pi
eM\widetilde{q}_{h}(S^{c})^{-1}).$

Finally, by Lemma 10, $\widetilde{q}_{h}(S^{c})\leq
h+\frac{V_{S}}{\gamma}\phi(\sqrt{h})$. Putting it all together and noting that
the function $x\mapsto x\log\frac{1}{x}$ is monotonically increasing on
$x\in(0,1/e]$, gives the lemma statement. ∎

######  Lemma 21.

Suppose that $q\in\mathscr{D}(\mathcal{X})$ is supported on $S$ and bounded
above by $1/\gamma$. Further suppose that Assumptions C.1, C.2, C.3 and C.4
hold. Then

$\left|\int_{S}\widetilde{q}_{h}(x)\log p_{\theta}(x)dx-\int_{S}q(x)\log
p_{\theta}(x)dx\right|\leq
C_{\alpha}h^{\alpha/2}+2h\log\frac{1}{\gamma}+\frac{V_{S}\phi(\sqrt{h})}{\gamma}\log\frac{1}{\gamma}$

whenever $h\leq h_{0}$.

###### Proof.

Using Fubini’s theorem, we obtain

$\int_{S}\widetilde{q}_{h}(x)\log
p_{\theta}(x)dx=\int_{\mathbb{R}^{d}}q(y)l(y)dy=\int_{S}q(y)l(y)dy$

where $l(y)=\int_{S}K_{h}(x,y)\log p_{\theta}(x)dx$ and last equality follows
since $q$ is supported on $S$. For any $y\in S_{-\sqrt{h}}$ (recall this means
that $B(y,\sqrt{h})\subseteq S$) and hence we have:

$\displaystyle\lvert\log p_{\theta}(y)-l(y)\rvert$
$\displaystyle=\left\lvert\int_{\mathbb{R}^{d}}\log
p_{\theta}(y)K_{h}(x,y)dx-\int_{S}\log p_{\theta}(x)K_{h}(x,y)dx\right\rvert$
$\displaystyle\leq\int_{B(y,\sqrt{h})}K_{h}(x,y)|\log p_{\theta}(y)-\log
p_{\theta}(x)|\,dx$
$\displaystyle+\int_{B(y,\sqrt{h})^{c}}K_{h}(x,y)\left(|\log
p_{\theta}(y)|+|\log p_{\theta}(x)|\right)\,dx$ $\displaystyle\leq
C_{\alpha}h^{\alpha/2}+2h\log\frac{1}{\gamma},$

where we have used Assumptions C.2 and C.3 and Lemma 9 in the last step.

Thus we have

$\displaystyle\left|\int_{S}q(y)l(y)\,dy-\int_{S}q(y)\log
p_{\theta}(y)\,dy\right|$ $\displaystyle\leq\int_{S}q(y)\left|l(y)-\log
p_{\theta}(y)\right|\,dy$
$\displaystyle=\int_{S_{-\sqrt{h}}}q(y)\left|l(y)-\log
p_{\theta}(y)\right|\,dy$ $\displaystyle+\int_{S\setminus
S_{-\sqrt{h}}}q(y)\left|l(y)-\log p_{\theta}(y)\right|\,dy$ $\displaystyle\leq
C_{\alpha}h^{\alpha/2}+2h\log\frac{1}{\gamma}+\frac{V_{S}\phi(\sqrt{h})}{\gamma}\log\frac{1}{\gamma}.\qed$

###### Proof of Lemma 18.

The TV statement follows immediately from Lemma 19. To see the KL statement,
we first observe that

$\operatorname{KL}_{S}(\widetilde{q}_{h},p_{\theta})=\int_{S}\widetilde{q}_{h}(x)\log\frac{\widetilde{q}_{h}(x)}{p_{\theta}(x)}\,dx=\int_{S}\widetilde{q}_{h}(x)\log\widetilde{q}_{h}(x)\,dx-\int_{S}\widetilde{q}_{h}(x)\log
p_{\theta}(x)\,dx.$

Plugging in Lemma 20 for the first term and Lemma 21 for the second term
completes the proof. ∎

###  C.4 Proof of Theorem 6

We now put all of the above together to prove Theorem 6. We suppose
Assumptions C.2, C.1, C.4 and C.3 hold and thus obtain the following
corollaries of Lemmas 12, 17 and 18 when we take $\delta_{n}=e^{-(\log
n)^{2\beta}}$ and $\eta_{n,h}=\frac{(\log n)^{\beta}}{\sqrt{n}h^{d}}$ for a
fixed constant $\beta>0$ (e.g. take $\beta=1$). In the following,
$n_{0},\bar{h},\bar{\eta}>0$ are constant quantities that can depend on any of
the terms used in the assumptions and on $\beta>0$, but are independent of $n$
and $h$. Given two expressions $f$ and $g$, the notation $f=O(g)$ will be used
to denote that $|f|\leq c|g|$ holds for a similar constant $c$. We will delay
instantiating a concrete value of $\epsilon^{\prime}$ in Corollary 2 until we
start the final proof, but note for now that the constants
$c,n_{0},\bar{h},\bar{\eta}$ do not depend on the choice of
$\epsilon^{\prime}$ in any way.

######  Corollary 2.

Suppose a fixed value $\epsilon^{\prime}>0$ is given. Then whenever $n\geq
n_{0},h\leq\bar{h}$ and $\eta_{n,h}\leq\bar{\eta}$, the following holds with
probability at least $1-\delta_{n}$:

  1. 1.

$\text{d}_{\text{TV}}(\hat{p},p_{0})=O\left(\eta_{n,h}+h^{\min(\frac{\alpha}{2},1)}+\phi(\sqrt{h})\right)$.

  2. 2.

$\Delta_{n}^{\gamma^{2}/4}\subseteq\mathcal{W}_{\frac{\gamma^{3}}{8},\frac{8}{\gamma^{3}}}$,
where $\mathcal{W}_{\ell,u}$ is as defined in Lemma 12.

  3. 3.

$\sup_{w\in\Delta_{n}^{\gamma^{2}/2}}\hat{q}_{w}(S^{c})=O(h+\phi(\sqrt{h}))$.

  4. 4.

There is $w^{\epsilon^{\prime}}\in\Delta_{n}^{\gamma^{2}/4}$ such that

$\operatorname{KL}_{S}(\hat{q}_{w^{\epsilon^{\prime}}}|p_{\theta})\leq
I_{\epsilon^{\prime}}(\theta)+O\left(\eta_{n,h}+h^{\frac{\alpha}{2}}+h\log\frac{1}{h}+\phi(\sqrt{h})\log\frac{1}{\phi(\sqrt{h})}\right)$

and

$\text{d}_{\text{TV}}(\hat{q}_{w^{\epsilon^{\prime}}},p_{0})\leq{\epsilon^{\prime}}+O\left(\eta_{n,h}+h^{\min(\frac{\alpha}{2},1)}+\phi(\sqrt{h})\right).$

###### Proof.

Observe by Lemma 5 that the information projection $q^{*}_{\epsilon^{\prime}}$
is sandwiched between $p_{0}$ and $p_{\theta}$; in particular,
$q^{*}_{\epsilon^{\prime}}$ has support $S$ and is bounded between values
$\gamma$ and $1/\gamma$ on $S$. Thus we will invoke Lemma 17 with
$q=q^{*}_{\epsilon^{\prime}}$ and $\delta=\delta_{n}$, noting that the
condition $n\geq\frac{2}{\gamma^{2}}\log\frac{12}{\delta}$ is satisfied when
$n_{0}$ is suitably large. Hence we may now prove the respective items.

We show Item 1 as follows:

$\text{d}_{\text{TV}}(\hat{p},p_{0})\leq\text{d}_{\text{TV}}(\hat{p},K_{h}\star
p_{0})+\text{d}_{\text{TV}}(K_{h}\star
p_{0},p_{0})=O(\eta_{n,h}+h)+O(h^{\min(\frac{\alpha}{2},1)}+\phi(\sqrt{h})),$

where the term $\text{d}_{\text{TV}}(\hat{p},K_{h}\star p_{0})$ was bounded by
combining Item 1 of Lemma 17 with Corollary 1, and the term
$\text{d}_{\text{TV}}(K_{h}\star p_{0},p_{0})$ was bounded by using Lemma 18
with $q=p_{0}$ (assuming suitable choice of constants $\bar{h}$ and $c$).

Next, Item 2 follows from Item 2 of Lemma 17 as long as
$\frac{6c_{0}}{\sqrt{n}h^{d}}\sqrt{\log\frac{4}{\delta_{n}}}=O(\eta_{n,h})\leq\gamma/2$
is satisfied, which holds when $\bar{\eta}$ is a suitably small constant.

Next, Item 3 follows from Item 3 of Lemma 17 noting that
$\sqrt{\frac{1}{2n}\log\frac{6}{\delta_{n}}}=O(\eta_{n,h}h^{d})=O(\bar{\eta}h)$.

Finally to show Item 4, we will invoke Item 4 from Lemma 17 for the choice
$q=q^{*}_{\epsilon^{\prime}}$. Hence we obtain a
$w^{\epsilon^{\prime}}\in\Delta_{n}^{\gamma^{2}/4}$ such that
$\|\hat{q}_{w^{\epsilon^{\prime}}}-q^{*}_{\epsilon^{\prime}}\|_{\infty}=O(\eta_{n,h})$
and

$|\operatorname{KL}_{S}(\hat{q}_{w^{\epsilon^{\prime}}}|p_{\theta})-\operatorname{KL}_{S}(K_{h}\star
q^{*}_{\epsilon^{\prime}}|p_{\theta})|=O(\eta_{n,h}).$

Further, Corollary 1 shows

$\text{d}_{\text{TV}}(\hat{q}_{w^{\epsilon^{\prime}}},K_{h}\star
q^{*}_{\epsilon^{\prime}})\leq O(\eta_{n,h}+h)$

since $\mu=\sum_{i=1}^{n}w^{\epsilon^{\prime}}_{i}\delta_{x_{i}}$ and the
measure $\nu$ given by density $q^{*}_{\epsilon^{\prime}}$, are both supported
on $S$. The bounds in Item 4 now follow using Lemma 18 with
$q=q^{*}_{\epsilon^{\prime}}$ and the triangle inequality, noting that
$\operatorname{KL}(q^{*}_{\epsilon^{\prime}}|p_{\theta})=I_{\epsilon^{\prime}}(\theta)$
and
$\text{d}_{\text{TV}}(q^{*}_{\epsilon^{\prime}},p_{0})\leq\epsilon^{\prime}$.
∎

Since our goal is to approximate $I_{\epsilon}(\theta)$ by
$\hat{I}_{\epsilon}(\theta)$, let us rewrite eq. 16 as

$\hat{I}_{\epsilon}(\theta)=\inf_{\begin{subarray}{c}w\in\Delta_{n}^{\gamma^{2}/4}\\\
\hat{d}_{\text{TV}}(\hat{q}_{w},p_{0})\leq\epsilon\end{subarray}}\widehat{\operatorname{KL}}_{S}(\hat{q}_{w}|p_{\theta})$

where, given $q\in\mathscr{D}(\mathcal{X})$,

$\widehat{\operatorname{KL}}_{S}(q|p_{\theta})=\frac{1}{n}\sum_{i=1}^{n}\frac{q(x_{i})}{\hat{p}_{\gamma}(x_{i})}\log\frac{q(x_{i})}{p_{\theta}(x_{i})}$

and

$\hat{d}_{\text{TV}}(q,p_{0})=\frac{1}{2n}\sum_{i=1}^{n}\left\lvert\frac{q(x_{i})}{\hat{p}_{\gamma}(x_{i})}-1\right\rvert.$

Next, the following corollary of Lemma 12 shows that, with high probability,
the estimators $\widehat{\operatorname{KL}}_{S}(\hat{q}_{w}|p_{\theta})$ and
$\hat{d}_{\text{TV}}(\hat{q}_{w},p_{0})$ are close to their population level
targets $\operatorname{KL}_{S}(\hat{q}_{w}|p_{\theta})$ and
$\text{d}_{\text{TV}}(\hat{q}_{w},p_{0})$, uniformly over all
$w\in\Delta_{n}^{\gamma^{2}/4}$.

######  Corollary 3.

Suppose $n\geq n_{0}$, $h\leq\bar{h}$ and $\eta_{n,h}\leq\bar{\eta}$, then
with probability at least $1-2\delta_{n}$ the event in Corollary 2 holds, and
further uniformly over all $w\in\Delta_{n}^{\gamma^{2}/4}$ it holds that

$\left\lvert\widehat{\operatorname{KL}}_{S}(\hat{q}_{w}|p_{\theta})-\operatorname{KL}_{S}(\hat{q}_{w}|p_{\theta})\right\rvert\leq\psi_{n,h}\quad\text{and
}\left\lvert\hat{d}_{\text{TV}}(\hat{q}_{w},p_{0})-\text{d}_{\text{TV}}(\hat{q}_{w},p_{0})\right\rvert\leq\psi_{n,h}$

for a deterministic quantity $\psi_{n,h}$ that satisfies
$\psi_{n,h}=O\left(\eta_{n,h}+h^{\min(\frac{\alpha}{2},1)}+\phi(\sqrt{h})\right)$.

###### Proof.

Let $E_{1}$ denote the event in Corollary 2, and let $E_{2}$ denote the event
in Lemma 12 with the choices $\delta=\delta_{n}$, $l=\frac{\gamma^{3}}{8}$,
$u=\frac{8}{\gamma^{2}}$. We will assume that both events $E_{1}$ and $E_{2}$
hold simultaneously, which happens with probability at least $1-2\delta_{n}$.

Recall that on the event $E_{1}$, we have
$\Delta_{n}^{\gamma^{2}/4}\subseteq\mathcal{W}_{\ell,u}$,
$\sup_{w\in\Delta_{n}^{\gamma^{2}/4}}\hat{q}_{w}(S^{c})=O(h+\phi(\sqrt{h}))$,
are
$\text{d}_{\text{TV}}(\hat{p},p_{0})=O\left(\eta_{n,h}+h^{\min(\frac{\alpha}{2},1)}+\phi(\sqrt{h})\right)$.
The proof can be completed by combining the above with the bounds from Lemma
12 under the event $E_{2}$. ∎

For a suitable constant $c$, the term
$\xi_{n,h}=c\left(\eta_{n,h}+h^{\frac{\alpha}{2}}+h\log\frac{1}{h}+\phi(\sqrt{h})\log\frac{1}{\phi(\sqrt{h})}\right)$
dominates all the error terms (i.e. the terms of the form $O(\cdot)$) in the
statement of Corollary 2 and Corollary 3. Using this term, we are ready to
finish the proof of Theorem 6.

###### Proof of Theorem 6.

We will invoke Corollary 3 with the choice
$\epsilon^{\prime}=\epsilon-2\xi_{n,h}$ (see Corollary 2). We first claim that
the following holds:

$\displaystyle
I_{\epsilon+2\xi_{n,h}}(\theta)-O(\xi_{n,h})\leq\hat{I}_{\epsilon}(\theta)\leq
I_{\epsilon-2\xi_{n,h}}(\theta)+O(\xi_{n,h})$ (21)

with probability at least $1-2\delta_{n}$.

For the upper bound, let $w^{\epsilon^{\prime}}\in\Delta_{n}^{\gamma^{2}/4}$
be the vector from Corollaries 2 and 3 and note that

$\hat{d}_{\text{TV}}(\hat{q}_{w},p_{0})\leq\text{d}_{\text{TV}}(\hat{q}_{w},p_{0})+\xi_{n,h}\leq\epsilon^{\prime}+2\xi_{n,h}\leq\epsilon,$

and hence

$\hat{I}_{\epsilon}(\theta)\leq\widehat{\operatorname{KL}}_{S}(\hat{q}_{w}|p_{\theta})\leq\operatorname{KL}_{S}(\hat{q}_{w}|p_{\theta})+\xi_{n,h}\leq
I_{\epsilon^{\prime}}(\theta)+2\xi_{n,h}.$

To lower bound $\hat{I}_{\epsilon}(\theta)$, let
$w\in\Delta_{n}^{\gamma^{2}/4}$ be such that
$\hat{d}_{\text{TV}}(\hat{q}_{w},p_{0})\leq\epsilon$. Then by Corollary 2,
Corollary 3, and Lemma 11, there is a $\bar{q}_{w}$ that is supported on $S$
such that

$\text{d}_{\text{TV}}(\bar{q}_{w},p_{0})\leq\text{d}_{\text{TV}}(\hat{q}_{w},p_{0})+\hat{q}_{w}(S^{c})\leq\hat{d}_{\text{TV}}(\hat{q}_{w},p_{0})+2\xi_{n,h}\leq\epsilon+2\xi_{n,h}$

and

$\displaystyle\widehat{\operatorname{KL}}_{S}(\hat{q}_{w}|p_{\theta})$
$\displaystyle\geq\operatorname{KL}_{S}(\hat{q}_{w}|p_{\theta})-\xi_{n,h}$
$\displaystyle=(1-\hat{q}_{w}(S^{c}))\operatorname{KL}(\bar{q}_{w}|p_{\theta})+(1-\hat{q}_{w}(S^{c}))\log(1-\hat{q}_{w}(S^{c}))-\xi_{n,h}$
$\displaystyle\geq(1-\xi_{n,h})I_{\epsilon+2\xi_{n,h}}(\theta)-2\xi_{n,h}$

where we have used that $\hat{q}_{w}(S^{c})\leq\xi_{n,h}$,
$h(x)=(1-x)\log(1-x)\geq-x$ by the convexity of $h$, and
$\operatorname{KL}(\bar{q}_{w}|p_{\theta})\geq
I_{\epsilon+2\xi_{n,h}}(\theta)$ since
$\text{d}_{\text{TV}}(\bar{q}_{w},p_{0})\leq\epsilon+2\xi_{n,h}$. Since the
right hand side of the previous display doesn’t depend on the choice of $w$,
by considering the infimum over all $w\in\Delta_{n}^{\gamma^{2}/4}$ such that
$\hat{d}_{\text{TV}}(\hat{q}_{w},p_{0})\leq\epsilon$ we see

$\displaystyle\hat{I}_{\epsilon}(\theta)$ $\displaystyle\geq
I_{\epsilon+2\xi_{n,h}}(\theta)-\xi_{n,h}(1+I_{\epsilon+2\xi_{n,h}}(\theta))\geq
I_{\epsilon+2\xi_{n,h}}(\theta)-\xi_{n,h}(1+\operatorname{KL}(p_{0}|p_{\theta})).$

Note that $\operatorname{KL}(p_{0}|p_{\theta})\leq 2\log(1/\gamma)$ by
Hölder’s inequality, and we have thus shown the lower bound and established
eq. 21.

Finally, we appeal to the continuity of the OKL function with respect to the
coarsening radius (i.e., Lemma 2) to see that

$I_{\epsilon-2\xi_{n,h}}(\theta)\leq
I_{\epsilon}(\theta)+\frac{2\xi_{n,h}}{\epsilon}\operatorname{KL}(p_{0}|p_{\theta})\leq
I_{\epsilon}(\theta)+\frac{4\xi_{n,h}}{\epsilon}\log(1/\gamma)=I_{\epsilon}(\theta)+O(\xi_{n,h})$

and

$I_{\epsilon+2\xi_{n,h}}(\theta)\geq
I_{\epsilon}(\theta)-\frac{2\xi_{n,h}}{\epsilon+2\xi_{n,h}}\operatorname{KL}(p_{0}|p_{\theta})\leq
I_{\epsilon}(\theta)-\frac{4\xi_{n,h}}{\epsilon}\log(1/\gamma)=I_{\epsilon}(\theta)-O(\xi_{n,h}),$

where we have used Assumption C.2 and Hölder’s inequality to establish
$\operatorname{KL}(p_{0}|p_{\theta})\leq 2\log(1/\gamma)$. Combining the above
two inequalities with Equation 21 completes the proof. ∎

##  Appendix D Asymptotics of the coarsened likelihood

In this section, we will show the asymptotic convergence of the coarsened
likelihood to the OKL function.

###  D.1 Asymptotics for finite spaces

Suppose $\mathcal{X}$ is a finite space. We will use the notation from Section
4.1; in particular, recall the probability simplex
$\Delta_{\mathcal{X}}=\\{q\in[0,1]^{\mathcal{X}}|\sum_{x\in X}q(x)=1\\}$ and
the OKL function $I_{\epsilon}(\theta)$ in terms of a general distance
$\boldsymbol{d}$ on $\Delta_{\mathcal{X}}$ as in eq. 11. We begin by showing
an elementary rounding lemma, which will be useful when applying Sanov’s
theorem in Lemma 23.

######  Lemma 22.

Let $p,p_{\theta}\in\Delta_{\mathcal{X}}$ such that
$\operatorname{KL}(p|p_{\theta})<\infty$. For any integer $n>|\mathcal{X}|$,
there exists a $q_{n}\in\Delta_{\mathcal{X}}$ such that $nq_{n}(x)$ is
integral for all $x\in\mathcal{X}$,
$\|q_{n}-p\|_{1}\leq\frac{2|\mathcal{X}|}{n}$, and

$\operatorname{KL}(q_{n}|p_{\theta})\leq\left(1+\frac{|\mathcal{X}|^{2}}{n}\right)\operatorname{KL}(p|p_{\theta})+\frac{|\mathcal{X}|}{n}\left(2\log\frac{n}{2}+\log|\mathcal{X}|+\frac{|\mathcal{X}|}{e}\right).$

###### Proof.

Choose an arbitrary
$x^{\star}=\operatorname*{arg\,max}_{x\in\mathcal{X}}p(x)$, choosing
arbitrarily if there are ties. Then we define $q_{n}\in\Delta_{\mathcal{X}}$
as follows. For all $x\neq x^{\star}$, let $q_{n}(x)=\frac{1}{n}\lfloor
nq_{n}(x)\rfloor$, and let $q_{n}(x^{\star})=1-\sum_{x\neq
x^{\star}}q_{n}(x)$. As $p\in\Delta_{\mathcal{X}}$, we have
$q_{n}\in\Delta_{\mathcal{X}}$. Moreover, by construction we also have that
$nq_{n}(x)$ is integral for all $x\in\mathcal{X}$.

Observe that for all $x\neq x^{\star}$, we have $0\leq p(x)-q_{n}(x)\leq 1/n$.
This implies that

$0\leq q_{n}(x^{\star})-p(x^{\star})=\left(1-\sum_{x\neq
x^{\star}}q_{n}(x)\right)-\left(1-\sum_{x\neq
x^{\star}}p(x)\right)\leq\frac{|\mathcal{X}|}{n}.$

Together, these statements give us that
$\|p-q_{n}\|_{1}\leq\frac{2|\mathcal{X}|}{n}$. Further since
$\operatorname{KL}(p|p_{\theta})<\infty$, we must also have
$\operatorname{KL}(q_{n}|p_{\theta})<\infty$ since
$\operatorname{supp}(q_{n})\subseteq\operatorname{supp}(p)\subseteq\operatorname{supp}(p_{\theta})$.

To prove the more detailed KL bound, we first observe that by known bounds on
the entropy function [Cover and Thomas, 2006, c.f. Theorem 17.3.3], we have

$\displaystyle\sum_{x}q_{n}(x)\log q_{n}(x)$
$\displaystyle\leq\sum_{x}p(x)\log
p(x)+\|p-q_{n}\|_{1}\log\frac{|\mathcal{X}|}{\|p-q_{n}\|_{1}}$
$\displaystyle\leq\sum_{x}p(x)\log
p(x)+\frac{2|\mathcal{X}|}{n}\log\frac{n}{2}.$

Next observe that we can bound the cross-entropy between $q_{n}$ and
$p_{\theta}$ as follows.

$\displaystyle\sum_{x}q_{n}(x)\log\frac{1}{p_{\theta}(x)}$
$\displaystyle=\sum_{x\neq
x^{\star}}q_{n}(x)\log\frac{1}{p_{\theta}(x)}+q_{n}(x^{\star})\log\frac{1}{p_{\theta}(x^{\star})}$
$\displaystyle\leq\sum_{x\neq
x^{\star}}p(x)\log\frac{1}{p_{\theta}(x)}+(p(x^{\star})+q_{n}(x^{\star})-p(x^{\star}))\log\frac{1}{p_{\theta}(x^{\star})}$
$\displaystyle\leq\sum_{x}p(x)\log\frac{1}{p_{\theta}(x)}+\frac{|\mathcal{X}|}{n}\log\frac{1}{p_{\theta}(x^{\star})}.$

Now observe that $p(x^{\star})\geq 1/|\mathcal{X}|$. This implies that
$\log\frac{1}{p_{\theta}(x^{\star})}\leq|\mathcal{X}|(\operatorname{KL}(p|p_{\theta})+1/e)+\log|\mathcal{X}|$.
To see this, first note that if $p_{\theta}(x^{\star})\geq 1/|\mathcal{X}|$,
then the claim is trivial. Thus, we may assume
$p_{\theta}(x^{\star})<1/|\mathcal{X}|\leq p(x^{\star})$. The log-sum
inequality implies that

$\displaystyle\operatorname{KL}(p|p_{\theta})$ $\displaystyle\geq
p(x^{\star})\log\frac{p(x^{\star})}{p_{\theta}(x^{\star})}+(1-p(x^{\star}))\log\frac{1-p(x^{\star})}{1-p_{\theta}(x^{\star})}$
$\displaystyle\geq
p(x^{\star})\log\frac{p(x^{\star})}{p_{\theta}(x^{\star})}-(1-p(x^{\star}))\log\frac{1}{1-p(x^{\star})}$
$\displaystyle\geq
p(x^{\star})\log\frac{p(x^{\star})}{p_{\theta}(x^{\star})}-\frac{1}{e}\geq\frac{1}{|\mathcal{X}|}\log\frac{1}{|\mathcal{X}|p_{\theta}(x^{\star})}-\frac{1}{e}.$

Here, the last inequality follows from our bound on $p(x^{\star})$ combined
with the fact that $a\log\frac{a}{b}$ is an increasing function in $a$ for
$a\geq b$. Rearranging the above gives us the claim. ∎

Our analysis of the coarsened likelihood will rely heavily on the following
result, which is essentially a consequence of Sanov’s theorem.

######  Lemma 23.

Suppose Assumptions B.1 and B.2 hold, and let $r>\epsilon_{0}$ and
$n\geq\frac{4C|\mathcal{X}|}{r-\epsilon_{0}}$. Then

$\left|\frac{1}{n}\log\mathbb{P}_{\theta}\left(\boldsymbol{d}(\hat{P}_{Z_{1:n}},p_{0})\leq
r\right)+I_{r}(\theta)\right|\leq\frac{|\mathcal{X}|}{n}\left(3\log(n+1)+\log|\mathcal{X}|+|\mathcal{X}|\left(V+\frac{1}{e}\right)+\frac{2C}{r-\epsilon_{0}}\right)$

where the probability operation $\mathbb{P}_{\theta}$ is taken over random
points $Z_{1},\ldots,Z_{n}\in\mathcal{X}$ drawn from the distribution
$p_{\theta}\in\Delta_{\mathcal{X}}$, and
$\hat{P}_{Z_{1:n}}\in\Delta_{\mathcal{X}}$ is the empirical distribution of
the data points $Z_{1},\ldots,Z_{n}$.

###### Proof.

Observe that $I_{r}(\theta)\leq V<\infty$ for all $r>\epsilon_{0}$. Sanov’s
theorem [Cover and Thomas, 2006, Theorem 11.4.1] implies that

$\frac{1}{n}\log\mathbb{P}_{\theta}\left(\boldsymbol{d}(\hat{P}_{Z_{1:n}},p_{0})\leq
r\right)\leq-I_{r}(\theta)+\frac{|\mathcal{X}|}{n}\log(n+1).$

Thus, we only need to show the lower bound for
$\frac{1}{n}\log\mathbb{P}_{\theta}\left(\boldsymbol{d}(\hat{P}_{Z_{1:n}},p_{0})\leq
r\right)+I_{r}(\theta)$. Pick $\delta>0$ and for any $t>0$, let
$q_{t}\in\Delta_{\mathcal{X}}$ satisfy $\boldsymbol{d}(q_{t},p_{0})\leq t$ and

$\operatorname{KL}(q_{t}|p_{\theta})\leq I_{t}(\theta)+\delta.$

Now let $\alpha_{n}=\frac{2C|\mathcal{X}|}{n}$ and observe that for
$n>\frac{2C|\mathcal{X}|}{r-\epsilon_{0}}$, such a
$q_{r-\alpha_{n}}\in\Delta_{\mathcal{X}}$ exists. Letting
$q^{(n)}_{r-\alpha_{n}}\in\Delta_{\mathcal{X}}$ be the discretization promised
by Lemma 22 and utilizing Assumption B.1, we have

$\displaystyle\boldsymbol{d}(q^{(n)}_{r-\alpha_{n}},p_{0})\leq\boldsymbol{d}(q^{(n)}_{r-\alpha_{n}},q_{r-\alpha_{n}})+\boldsymbol{d}(q_{r-\alpha_{n}},p_{0})\leq
C\|q^{(n)}_{r-\alpha_{n}}-q_{r-\alpha_{n}}\|_{1}+r-\alpha_{n}\leq r.$

Thus we have

$\displaystyle\frac{1}{n}\log\mathbb{P}_{\theta}\left(\boldsymbol{d}(\hat{P}_{Z_{1:n}},p_{0})\leq
r\right)\geq\frac{1}{n}\log\mathbb{P}_{\theta}\left(\hat{P}_{Z_{1:n}}=q_{r-\alpha_{n}}^{(n)}\right)$
$\displaystyle\geq-\frac{|\mathcal{X}|}{n}\log(n+1)-\operatorname{KL}(q^{(n)}_{r-\alpha_{n}}|p_{\theta})$
$\displaystyle\geq-\left(1+\frac{|\mathcal{X}|^{2}}{n}\right)(I_{r-\alpha_{n}}(\theta)+\delta)-\frac{|\mathcal{X}|}{n}\left(3\log(n+1)+\log|\mathcal{X}|+\frac{|\mathcal{X}|}{e}\right)$
$\displaystyle\geq-
I_{r-\alpha_{n}}(\theta)-\delta-\frac{|\mathcal{X}|}{n}\left(3\log(n+1)+\log|\mathcal{X}|+|\mathcal{X}|\left(V+\frac{1}{e}+\delta\right)\right)$
$\displaystyle\geq-
I_{r}(\theta)-\delta-\frac{\alpha_{n}V}{r-\epsilon_{0}}-\frac{|\mathcal{X}|}{n}\left(3\log(n+1)+\log|\mathcal{X}|+|\mathcal{X}|\left(V+\frac{1}{e}+\delta\right)\right),$

where the second line follows from [Cover and Thomas, 2006, Theorem 11.1.4],
the third line follows from Lemma 22, and the last line follows from Lemma 2.
Rearranging the above and utilizing the fact that $\delta>0$ was arbitrary
gives us the lemma statement. ∎

With Lemma 23 in hand, we can prove the following convergence result for the
coarsened likelihood.

######  Theorem 7.

Suppose Assumptions B.1 and B.2 hold, and let $\epsilon>\epsilon_{0}$. If
$x_{1},\ldots,x_{n}\sim p_{0}$, then with probability at least $1-\delta$,

$\displaystyle\left|\frac{1}{n}\log
L_{\epsilon}(\theta|x_{1:n})+I_{\epsilon}(\theta)\right|$
$\displaystyle\leq\frac{CV|\mathcal{X}|}{\epsilon-\epsilon_{0}}\sqrt{\frac{2}{n}\log\frac{2|\mathcal{X}|}{\delta}}$
$\displaystyle\hskip
30.00005pt+\frac{3|\mathcal{X}|}{n}\left(3\log(n+1)+\log|\mathcal{X}|+|\mathcal{X}|\left(V+\frac{1}{e}\right)+\frac{4C}{\epsilon-\epsilon_{0}}\right).$

whenever
$n>\max\left\\{2\left(\frac{C|\mathcal{X}|}{\epsilon-\epsilon_{0}}\right)^{2}\log\frac{2|\mathcal{X}|}{\delta},\frac{8C|\mathcal{X}|}{\epsilon-\epsilon_{0}}\right\\}$.

###### Proof.

For $r>0$, define
$M_{n,r}(\theta)=\mathbb{P}_{\theta}\left(\boldsymbol{d}(\hat{P}_{Z_{1:n}},p^{0})\leq
r\right)$. By Lemma 23,

$\left|\frac{1}{n}\log
M_{n,r}(\theta)+I_{r}(\theta)\right|\leq\frac{|\mathcal{X}|}{n}\left(3\log(n+1)+\log|\mathcal{X}|+|\mathcal{X}|\left(V+\frac{1}{e}\right)+\frac{2C}{r-\epsilon_{0}}\right)$
(22)

for all $r>\epsilon_{0}$ satisfying that
$n\geq\frac{4C|\mathcal{X}|}{r-\epsilon_{0}}$.

Now suppose that $x_{1},\ldots,x_{n}\sim p_{0}$. Then Hoeffding’s inequality
combined with Assumption B.1 implies that with probability at least
$1-\delta$,

$\boldsymbol{d}(\hat{P}_{x_{1:n}},p_{0})\leq
C\|\hat{P}_{x_{1:n}}-p_{0}\|_{1}\leq
C|\mathcal{X}|\sqrt{\frac{1}{2n}\log\frac{2|\mathcal{X}|}{\delta}}=:\alpha_{n}.$

Let us condition on this event occurring. For
$n>2\left(\frac{C|\mathcal{X}|}{\epsilon-\epsilon_{0}}\right)^{2}\log\frac{2|\mathcal{X}|}{\delta}$,
we have $\alpha_{n}<(\epsilon-\epsilon_{0})/2$. Thus, we may write

$\displaystyle\left|\log M_{n,\epsilon}(\theta)-\log
L_{\epsilon}(\theta|x_{1:n})\right|$
$\displaystyle=\left|\log\mathbb{P}_{\theta}\left(\boldsymbol{d}(\hat{P}_{Z_{1:n}},p_{0})\leq\epsilon\right)-\log\mathbb{P}_{\theta}\left(\boldsymbol{d}(\hat{P}_{Z_{1:n}},\hat{P}_{x_{1:n}})\leq\epsilon\right)\right|$
$\displaystyle=\log\max\left\\{\frac{\mathbb{P}_{\theta}\left(\boldsymbol{d}(\hat{P}_{Z_{1:n}},p_{0})\leq\epsilon\right)}{\mathbb{P}_{\theta}\left(\boldsymbol{d}(\hat{P}_{Z_{1:n}},\hat{P}_{x_{1:n}})\leq\epsilon\right)},\frac{\mathbb{P}_{\theta}\left(\boldsymbol{d}(\hat{P}_{Z_{1:n}},\hat{P}_{x_{1:n}})\leq\epsilon\right)}{\mathbb{P}_{\theta}\left(\boldsymbol{d}(\hat{P}_{Z_{1:n}},p_{0})\leq\epsilon\right)}\right\\}$
$\displaystyle\leq\log\max\left\\{\frac{\mathbb{P}_{\theta}\left(\boldsymbol{d}(\hat{P}_{Z_{1:n}},p_{0})\leq\epsilon\right)}{\mathbb{P}_{\theta}\left(\boldsymbol{d}(\hat{P}_{Z_{1:n}},p_{0})\leq\epsilon-\alpha_{n}\right)},\frac{\mathbb{P}_{\theta}\left(\boldsymbol{d}(\hat{P}_{Z_{1:n}},p_{0})\leq\epsilon+\alpha_{n}\right)}{\mathbb{P}_{\theta}\left(\boldsymbol{d}(\hat{P}_{Z_{1:n}},p_{0})\leq\epsilon\right)}\right\\}$
$\displaystyle=\log\max\left\\{\frac{M_{n,\epsilon}(\theta)}{M_{n,\epsilon-\alpha_{n}}(\theta)},\frac{M_{n,\epsilon+\alpha_{n}}(\theta)}{M_{n,\epsilon}(\theta)}\right\\}$

By eq. 22 and Lemma 2, we have

$\displaystyle\frac{1}{n}\log\frac{M_{n,\epsilon}(\theta)}{M_{n,\epsilon-\alpha_{n}}(\theta)}$
$\displaystyle\leq
I_{\epsilon}(\theta)-I_{\epsilon-\alpha_{n}}(\theta)+\frac{2|\mathcal{X}|}{n}\left(3\log(n+1)+\log|\mathcal{X}|+|\mathcal{X}|\left(V+\frac{1}{e}\right)+\frac{2C}{\epsilon-\alpha_{n}-\epsilon_{0}}\right)$
$\displaystyle\leq\frac{2\alpha_{n}}{\epsilon-\epsilon_{0}}V+\frac{2|\mathcal{X}|}{n}\left(3\log(n+1)+\log|\mathcal{X}|+|\mathcal{X}|\left(V+\frac{1}{e}\right)+\frac{4C}{\epsilon-\epsilon_{0}}\right).$

Similarly, we also have

$\displaystyle\frac{1}{n}\log\frac{M_{n,\epsilon+\alpha_{n}}(\theta)}{M_{n,\epsilon}(\theta)}$
$\displaystyle\leq
I_{\epsilon+\alpha_{n}}(\theta)-I_{\epsilon}(\theta)+\frac{2|\mathcal{X}|}{n}\left(3\log(n+1)+\log|\mathcal{X}|+|\mathcal{X}|\left(V+\frac{1}{e}\right)+\frac{2C}{\epsilon+\alpha_{n}-\epsilon_{0}}\right)$
$\displaystyle\leq\frac{\alpha_{n}}{\epsilon-\epsilon_{0}+\alpha_{n}}V+\frac{2|\mathcal{X}|}{n}\left(3\log(n+1)+\log|\mathcal{X}|+|\mathcal{X}|\left(V+\frac{1}{e}\right)+\frac{4C}{\epsilon-\epsilon_{0}}\right).$

Putting it all together gives us the theorem statement. ∎

###  D.2 Asymptotics for continuous spaces

In this section, we will show that the coarsened likelihood continues to
converge in probability to the OKL when $\mathcal{X}$ is a metric space. More
precisely, let $\mathcal{X}$ be a Polish space (i.e. a complete and separable
metric space) equipped with its Borel sigma algebra
$\mathcal{B}(\mathcal{X})$. Then $\mathcal{P}(\mathcal{X})$, the set of
(Borel) probability measures on $\mathcal{X}$, can be equipped with the
topology of weak-convergence [Billingsley, 2013]. In more detail, we say that
a sequence of measures
$\\{\mathcal{P}_{n}\\}_{n\in\mathbb{N}}\subseteq\mathcal{P}(\mathcal{X})$
weakly converges to a measure $P$, denoted as $P_{n}\Rightarrow P$, if
$\lim_{n\to\infty}\int fdP_{n}=\int fdP$ for each continuous and bounded
function $f:\mathcal{X}\to\mathbb{R}$. The space $\mathcal{P}(\mathcal{X})$ is
also a Polish space under this topology [Billingsley, 2013].

Recall the definition of the OKL for a general distance $\boldsymbol{d}$ over
$\mathcal{P}(\mathcal{X})$ from eq. 11:

$I_{\epsilon}(\theta)=\inf_{\begin{subarray}{c}Q\in\mathcal{P}(\mathcal{X})\\\
\boldsymbol{d}(Q,P_{0})\leq\epsilon\end{subarray}}\operatorname{KL}(Q|P_{\theta}).$

To establish an asymptotic connection between the coarsened likelihood and the
OKL, we will make the following assumption on $\boldsymbol{d}$.

######  Assumption D.1.

For any $P,Q,R\in\mathcal{P}(\mathcal{X})$ and $\lambda\in(0,1)$, the
following holds:

  1. (a)

$\boldsymbol{d}(P,P)=0$.

  2. (b)

$\boldsymbol{d}(P,Q)=\boldsymbol{d}(Q,P)$.

  3. (c)

$\boldsymbol{d}(P,Q)\leq\boldsymbol{d}(P,R)+\boldsymbol{d}(R,Q)$.

  4. (d)

$\boldsymbol{d}$ is convex in its arguments:
$\boldsymbol{d}(P,(1-\lambda)Q+\lambda
R)\leq\lambda\boldsymbol{d}(P,Q)+(1-\lambda)\boldsymbol{d}(P,R)$.

  5. (e)

For any sequence of probability measures $P_{n}\Rightarrow P$,
$\boldsymbol{d}(P_{n},Q)\to\boldsymbol{d}(P,Q)$ as $n\to\infty$.

Conditions (a)-(c) simply require that $\boldsymbol{d}$ is a pseudometric,
i.e. it satisfies all the requirements of a metric except for the requirement
that $\boldsymbol{d}(P,Q)>0$ whenever $P\neq Q$. Condition (d) (combined with
condition (a)) allows us to apply Lemma 2, and condition (e) ensures that
$\boldsymbol{d}$ is continuous with respect to the topology of weak
convergence.

Given this assumption on $\boldsymbol{d}$, we can demonstrate the following
asymptotic convergence.

######  Theorem 8.

Suppose that Assumption D.1 holds and that $I_{\epsilon_{0}}(\theta)<\infty$
for some $\epsilon_{0}\geq 0$. For any $\epsilon>\epsilon_{0}$, if
$x_{1},\ldots,x_{n}\overset{i.i.d.}{\sim}P_{0}$, then

$\frac{1}{n}\log
L_{\epsilon}(\theta|x_{1:n})\xrightarrow{P}-I_{\epsilon}(\theta)$

as $n\to\infty$.

####  D.2.1 Proof of Theorem 8

Similar to the setting in Section D.1, we will study asymptotics of the
coarsened likelihood $L_{\epsilon}(\theta|x_{1:n})$ by first studying the
asymptotics of its population level analog

$M_{n,\epsilon}(\theta)=\mathbb{P}_{\theta}(\boldsymbol{d}(\hat{P}_{Z_{1:n}},P_{0})\leq\epsilon)$
(23)

obtained by replacing the empirical distribution of the data
$\hat{P}_{x_{1:n}}$ by the population level quantity $P_{0}$.

Next, to study the asymptotics of $M_{n,\epsilon}(\theta)$, we will invoke
Sanov’s theorem from Large Deviation theory which says that the law of the
empirical distribution $\hat{P}_{Z_{1:n}}$ satisfies a Large Deviation
principle in the space $\mathcal{P}(\mathcal{X})$ with rate function
$\mu\mapsto\operatorname{KL}(\mu|P_{\theta})$, when
$Z_{1},\ldots,Z_{n}\overset{i.i.d.}{\sim}P_{\theta}$. More precisely, we will
show that the error term

$r_{n}(\epsilon)=\left|\frac{1}{n}\log
M_{n,\epsilon}(\theta)+I_{\epsilon}(\theta)\right|$ (24)

converges to zero as $n\to\infty$.

######  Lemma 24.

If Assumption D.1 holds and $I_{\epsilon_{0}}(\theta)<\infty$ for some
$\epsilon_{0}\geq 0$, then for any $\epsilon>\epsilon_{0}$,
$\lim\limits_{n\to\infty}r_{n}(\epsilon)=0$.

###### Proof.

Assume $Z_{1},\ldots,Z_{n}\overset{i.i.d.}{\sim}P_{\theta}$. Then Sanov’s
theorem [Dembo and Zeitouni, 2010, Theorem 6.2.10] shows that for any Borel
measurable subset $\Gamma\subseteq\mathcal{P}(\mathcal{X})$,

$\displaystyle-\inf_{Q\in\Gamma^{\circ}}\operatorname{KL}(Q|P_{\theta})$
$\displaystyle\leq\liminf_{n\to\infty}\frac{1}{n}\log\mathbb{P}_{\theta}(\hat{P}_{Z_{1:n}}\in\Gamma)$
(25)
$\displaystyle\leq\limsup_{n\to\infty}\frac{1}{n}\log\mathbb{P}_{\theta}(\hat{P}_{Z_{1:n}}\in\Gamma)\leq-\inf_{Q\in\bar{\Gamma}}\operatorname{KL}(Q|P_{\theta}),$

where $\Gamma^{\circ}$ and $\bar{\Gamma}$ refer to the interior and closure of
$\Gamma$ under the weak-topology on $\mathcal{P}(\mathcal{X})$.

Now consider the set
$\Gamma_{t}=\\{Q\in\mathcal{P}(\mathcal{X})|\boldsymbol{d}(Q,P_{0})\leq t\\}$
indexed by the parameter $t\geq 0$. By the assumed continuity of
$\boldsymbol{d}$ under the topology of weak-convergence (Assumption D.1(e)),
the set $\Gamma_{\epsilon}$ is closed while the set
$\Gamma_{\epsilon^{-}}=\\{Q\in\mathcal{P}(\mathcal{X})\mid\boldsymbol{d}(Q,P_{0})<\epsilon\\}$
is an open set. Thus using $\bar{\Gamma}_{\epsilon}=\Gamma_{\epsilon}$ and
$\cup_{r<\epsilon}\Gamma_{r}=\Gamma_{\epsilon^{-}}\subseteq\Gamma_{\epsilon}^{\circ}$,
we see

$\displaystyle
I_{\epsilon}(\theta)=\inf_{Q\in\bar{\Gamma}_{\epsilon}}\operatorname{KL}(Q|P_{\theta})\leq\inf_{Q\in\Gamma^{\circ}_{\epsilon}}\operatorname{KL}(Q|P_{\theta})\leq\inf_{Q\in\Gamma_{\epsilon^{-}}}\operatorname{KL}(Q|P_{\theta})\leq
I_{r}(\theta)$

for each $0<r<\epsilon$. Next by the condition
$I_{\epsilon_{0}}(\theta)<\infty$, we may apply Lemma 2 to conclude that the
map $t\mapsto I_{t}(\theta)$ is continuous at $t=\epsilon$, i.e.
$\lim_{t\to\epsilon}I_{t}(\theta)=I_{\epsilon}(\theta)$. Hence letting $r$
increase to $\epsilon$ in the above display, we find that

$\inf_{Q\in\bar{\Gamma}_{\epsilon}}\operatorname{KL}(Q|P_{\theta})=\inf_{Q\in\Gamma^{\circ}_{\epsilon}}\operatorname{KL}(Q|P_{\theta})=I_{\epsilon}(\theta).$

Thus taking $\Gamma=\Gamma_{\epsilon}$ in eq. 25 shows that the limit

$\frac{1}{n}\log\mathbb{P}_{\theta}(\boldsymbol{d}(\hat{P}_{Z_{1:n}},P_{0})\leq\epsilon)=\frac{1}{n}\log\mathbb{P}_{\theta}(\hat{P}_{Z_{1:n}}\in\Gamma_{\epsilon})\to-
I_{\epsilon}(\theta)$

holds as $n\to\infty$. Recalling the definition of $M_{n,\epsilon}(\theta)$ in
eq. 23, we see that the asymptotic error term $r_{n}(\epsilon)$ in eq. 24 is
converging to zero as $n\to\infty$.

∎

Now we can prove Theorem 8 by carefully accounting for the error between the
coarsened likelihood $L_{\epsilon}(\theta|x_{1:n})$ and its population-level
analog $M_{n,\epsilon}(\theta)$ from Equation 23.

###### Proof of Theorem 8.

Let $x_{1},\ldots,x_{n}\overset{i.i.d.}{\sim}P_{0}$ and pick
$0<t<\epsilon-\epsilon_{0}$. Define $E_{n,t}$ as the event that
$\boldsymbol{d}(\hat{P}_{x_{1:n}},P_{0})\leq t$. Since $\boldsymbol{d}$ is
continuous with respect to weak convergence and $\hat{P}_{x_{1:n}}\Rightarrow
P_{0}$ as $n\to\infty$ by the weak law of large numbers, we have
$\lim_{n\to\infty}\mathbb{P}(E_{n,t})=1$ for any $t>0$. By Assumption D.1(c)
we have
$|\boldsymbol{d}(\hat{P}_{Z_{1:n}},P_{0})-\boldsymbol{d}(\hat{P}_{Z_{1:n}},\hat{P}_{x_{1:n}})|\leq\boldsymbol{d}(P_{0},\hat{P}_{x_{1:n}})$,
implying that on the event $E_{n,t}$ we have

$M_{n,\epsilon-t}(\theta)\leq L_{\epsilon}(\theta|x_{1:n})\leq
M_{n,\epsilon+t}(\theta).$ (26)

Thus on the event $E_{n,t}$, we can bound

$\displaystyle\left\lvert\frac{1}{n}\log
L_{\epsilon}(\theta|x_{1:n})+I_{\epsilon}(\theta)\right\rvert$
$\displaystyle\leq\left\lvert\frac{1}{n}\log
M_{n,\epsilon+t}(\theta)+I_{\epsilon}(\theta)\right\rvert+\left\lvert\frac{1}{n}\log
M_{n,\epsilon-t}(\theta)+I_{\epsilon}(\theta)\right\rvert$ $\displaystyle\leq
r_{n}(\epsilon+t)+r_{n}(\epsilon-t)+\lvert
I_{\epsilon+t}(\theta)-I_{\epsilon}(\theta)\rvert+\lvert
I_{\epsilon-t}(\theta)-I_{\epsilon}(\theta)\rvert$ $\displaystyle\leq
r_{n}(\epsilon+t)+r_{n}(\epsilon-t)+\frac{2t}{\epsilon-\epsilon_{0}}I_{\epsilon_{0}}(\theta)$

where the first inequality uses eq. 26, the second uses eq. 24, and the last
uses Lemma 2. Hence given any $\delta>0$ and $t\in(0,\epsilon-\epsilon_{0})$
such that $tI_{\epsilon_{0}}(\theta)<(\epsilon-\epsilon_{0})\delta/4$, we have

$\displaystyle\mathbb{P}\left(\left\lvert\frac{1}{n}\log
L_{\epsilon}(\theta|x_{1:n})+I_{\epsilon}(\theta)\right\rvert>\delta\right)\leq\mathbb{P}(E_{n,t}^{c})+I\\{r_{n}(\epsilon-t)+r_{n}(\epsilon+t)>\delta/2\\}.$

Hence using Lemma 24 and the fact that $\mathbb{P}(E_{n,t})\to 1$ as
$n\to\infty$, we now see that

$\lim_{n\to\infty}\mathbb{P}\left(\left\lvert\frac{1}{n}\log
L_{\epsilon}(\theta|x_{1:n})-I_{\epsilon}(\theta)\right\rvert>\delta\right)=0.$

Since $\delta>0$ was arbitrary, this completes the proof. ∎

####  D.2.2 Smoothed total variation distance satisfies Assumption D.1

Suppose $\kappa:\mathcal{X}\times\mathcal{X}\to[0,\infty)$ is a probability
kernel with respect to measure $\lambda$. That is, assume
$\int\kappa(x,y)d\lambda(x)=1$ for each $y\in\mathcal{X}$. Given a measure
$\mu\in\mathcal{P}(\mathcal{X})$, this allows us to define a smoothed
probability measure $\kappa\star\mu\in\mathcal{P}(\mathcal{X})$ that has
density

$\frac{d(\kappa\star\mu)}{d\lambda}(x)=f_{\kappa,\mu}(x)=\int\kappa(x,y)d\mu(y)$

with respect to $\lambda$.

Recall the definition of the total variation distance on
$\mathcal{P}(\mathcal{X})$,

$\text{d}_{\text{TV}}(\mu,\nu)=\sup_{B\in\mathcal{B}(\mathcal{X})}|\mu(B)-\nu(B)|=\sup_{g:\mathcal{X}\to[-1,1]}\left\lvert\int
gd\mu-\int gd\nu\right\rvert.$ (27)

When $\mu$ and $\nu$ have densities $f_{\mu}$ and $f_{\nu}$ with respect to a
common measure $\lambda$, one can additionally show
$\text{d}_{\text{TV}}(\mu,\nu)=\frac{1}{2}\int\lvert f_{\mu}-f_{\nu}\rvert
d\lambda$.

Although $\text{d}_{\text{TV}}$ is not closed with respect to weak
convergence, we can show that the following kernel-smoothed version of TV
distance is.

######  Definition D.1.

Given a probability density kernel $\kappa$, the smoothed total-variation
distance is given by

$\text{d}_{\text{TV,}\kappa}(\mu,\nu)=\text{d}_{\text{TV}}(\kappa\star\mu,\kappa\star\nu)=\frac{1}{2}\int\lvert
f_{\kappa,\mu}(x)-f_{\kappa,\nu}(x)\rvert d\lambda(x)$

Now we will show that $\text{d}_{\text{TV,}\kappa}$ satisfies Assumption D.1
when $\kappa$ is a bounded and continuous kernel.

######  Proposition 3.

If $\kappa$ is a bounded and continuous kernel, then
$\text{d}_{\text{TV,}\kappa}$ satisfies Assumption D.1.

###### Proof.

First observe that the smoothed TV distance is just an ordinary TV distance
between smoothed densities. Since the ordinary TV distance is a metric, this
immediately implies that the smoothed TV satisfies the identity, symmetry, and
triangle inequality properties.

To establish convexity of $\text{d}_{\text{TV,}\kappa}$, note that for
measures $\mu,\nu\in\mathcal{P}(\mathcal{X})$ and $v\in[0,1]$, we have

$f_{\kappa,(1-v)\mu+v\nu}(x)=(1-v)\int\kappa(x,y)d\mu(y)+v\int\kappa(x,y)d\nu(y)=(1-v)f_{\kappa,\mu}(x)+vf_{\kappa,\nu}(x).$

Thus, for $\mu,\nu,\pi\in\mathcal{P}(\mathcal{X})$, we have

$\displaystyle\text{d}_{\text{TV,}\kappa}(\pi,(1-v)\mu+v\nu)$
$\displaystyle=\frac{1}{2}\int\lvert
f_{\kappa,\pi}(x)-f_{\kappa,(1-v)\mu+v\nu}(x)\rvert d\lambda(x)$
$\displaystyle=\frac{1}{2}\int\lvert
f_{\kappa,\pi}(x)-((1-v)f_{\kappa,\mu}(x)+vf_{\kappa,\nu}(x))\rvert
d\lambda(x)$ $\displaystyle\leq(1-v)\frac{1}{2}\int\lvert
f_{\kappa,\pi}(x)-f_{\kappa,\mu}(x)\rvert d\lambda(x)+v\frac{1}{2}\int\lvert
f_{\kappa,\pi}(x)-f_{\kappa,\nu}(x)\rvert d\lambda(x)$
$\displaystyle=(1-v)\text{d}_{\text{TV,}\kappa}(\pi,\mu)+v\text{d}_{\text{TV,}\kappa}(\pi,\nu),$

where the inequality follows from the convexity of the absolute value
function. Thus, $\text{d}_{\text{TV,}\kappa}$ is convex in its arguments.

To establish the continuity of $\text{d}_{\text{TV,}\kappa}$ under the
topology of weak-convergence, suppose $\mu_{n}\Rightarrow\mu$ in
$\mathcal{P}(\mathcal{X})$. Then since $y\mapsto\kappa(x,y)$ is a continuous
and bounded function, the convergence

$f_{\kappa,\mu_{n}}(x)\to f_{\kappa,\mu}(x)$

follows for each $x\in\mathcal{X}$ as $n\to\infty$. Since $f_{\kappa,\nu}$ for
any $\nu\in\mathcal{P}(\mathcal{X})$ is a density with respect to $\lambda$,
Scheffé’s lemma shows that

$\text{d}_{\text{TV,}\kappa}(\mu_{n},\mu)=\frac{1}{2}\int\lvert
f_{\kappa,\mu_{n}}(x)-f_{\kappa,\mu}(x)\rvert d\lambda(x)\to 0\ \ \text{ as
}n\to\infty.$

Finally, by the triangle inequality,
$\lvert\text{d}_{\text{TV,}\kappa}(\mu_{n},\nu)-\text{d}_{\text{TV,}\kappa}(\mu,\nu)\rvert\leq\text{d}_{\text{TV,}\kappa}(\mu_{n},\mu)$.
∎

##  Appendix E Auxiliary lemmas

In the following lemma, we would like to understand the conditions under which
two distributions $P_{0}$ and $P_{1}$ can be written as an
$\epsilon$-contamination of one another.

######  Lemma 25.

Suppose $\epsilon\in[0,1)$ and two probability measures $P_{0},P_{1}$ are
given. Then there is a probability measure $Q$ such that
$P_{0}=(1-\epsilon)P_{1}+\epsilon Q$ if and only if the Radon Nikodym
derivative $h=\frac{dP_{1}}{dP_{0}}$ exists and is bounded above by
$\frac{1}{1-\epsilon}$ almost surely $P_{0}$.

###### Proof.

First we note the “only if” direction. Suppose indeed that
$P_{0}=(1-\epsilon)P_{1}+\epsilon Q$. Then the absolute continuity condition
$P_{1}\ll P_{0}$ follows since $\epsilon<1$. Thus by the Radon Nikodym theorem
$h=\frac{dP_{1}}{dP_{0}}$ exists. Since $Q$ is a probability measure, for any
non-negative bounded (measurable) function $f$ we have

$P_{0}(f)-(1-\epsilon)P_{1}(f)=\epsilon Q(f)\geq 0,$

where we use the notation $\mu(f)\doteq\int fd\mu$. Noting
$P_{1}(f)=P_{0}(hf)$, we thus obtain that

$\int fdP_{0}\geq(1-\epsilon)\int fhdP_{0}\qquad\text{ for each bounded }f\geq
0.$ (28)

This shows that $h$ is bounded above by $\frac{1}{1-\epsilon}$ almost surely.

Now let us show the “if” condition. Suppose $h=\frac{dP_{1}}{dP_{0}}$ exists
and is bounded above by $\frac{1}{1-\epsilon}$. Then equation (28) is seen to
be satisfied. Let us assume $\epsilon>0$, since $\epsilon=0$ means that
$P_{1}=P_{0}$ and there is nothing to show. This allows us to define the
signed measure $Q$ given by

$Q(f)\doteq\frac{P_{0}(f)-(1-\epsilon)P_{1}(f)}{\epsilon}$

for every bounded $f$. Since $Q(f)\geq 0$ for each $f\geq 0$, this implies
that $Q$ is indeed a non-negative measure. It is indeed a probability measure
since $Q(1)=\frac{P_{0}(1)-(1-\epsilon)P_{1}(1)}{\epsilon}=1$. Finally, the
result that $P_{0}=(1-\epsilon)P_{1}+\epsilon Q$ holds by the way $Q$ was
defined. ∎

##  Appendix F Simulations with random corruptions

In this section, we present the simulation results for the setting in which
the data points to be corrupted are chosen entirely at random. For each of the
problem settings, all of the details remain exactly the same as in the max-
likelihood corruption simulations, with the only change coming from which data
points are chosen to be corrupted.

Figure 11: Gaussian results for random corruptions. Dashed black line denotes
average performance of MLE on full uncorrupted dataset. Shaded regions denote
95% confidence intervals over 50 random seeds.

Figure 11 presents the random corruption results for estimating a multivariate
normal distribution. In contrast with the max-likelihood corruption setting,
we see that OWL without kernelization outperforms OWL with kernelization in
higher dimensions. It is possible that this is due to the difficulty of
density estimation in higher dimensions.

Figure 12: Linear regression results for random corruptions. Dashed black line
denotes average performance of MLE on full uncorrupted training set. Shaded
regions denote 95% confidence intervals over 50 random seeds.

Figure 12 presents the random corruption results for linear regression. The
results here are qualitatively similar to those for the max-likelihood
corruption setting, with all three robust methods performing well in the
simulated data setting but with RANSAC performing notably worse with QSAR
data.

Figure 13: Logistic regression results for random corruptions. Dashed black
line denotes average performance of MLE on full uncorrupted training set.
Shaded regions denote 95% confidence intervals over 50 random seeds.

Figure 13 presents the random corruption results for logistic regression. As
in the max-likelihood corruption case, we see that OWL outperforms the other
methods across all three datasets. Moreover, we see that on the Enron spam
dataset, OWL even outperforms the uncorrupted MLE baseline, which is entirely
possible if the logistic regression model is mis-specified.

Figure 14: Mixture model results for random corruptions. Dashed black line
denotes average performance of MLE on full uncorrupted training set. Shaded
regions denote 95% confidence intervals over 50 random seeds.

Figure 14 presents the random corruption results for the mixture model
settings. The results here are qualitatively similar to those for the max-
likelihood corruption setting.

##  Appendix G More details of the micro-credit study

This section contains additional details of our analysis in Section 7.

Figure 15 shows a scatter-plot for the data and the presence of outliers.

Figure 16 shows the 90% OS-bootstrap confidence bands for the AIT estimates,
with the $x$-axis scaled to emphasize the uncertainty for small values of
$\epsilon$.

Figure 17 plots minimum-OKL estimate for various values $\epsilon$, along with
the associated 90% bootstrap confidence bands.

Figure 18 shows the distribution of profit values for points that were
declared as outliers by the OWL procedure at the parameter value
$\epsilon_{0}$.

Figure 15: Scatter-plot of the household profit values across treated and non-
treated households. Even after removing the household with the extreme profit
of -40000 USD PPP, there are still households with extreme profit values that
cause brittleness in estimating the average treatment effect. Figure 16: The
plot from the left panel of Figure 10, plotted on a re-scaled $x$-axis to
emphasize the uncertainty in the AIT estimates for small values of $\epsilon$.
The confidence bands become narrow roughly at the tuned value of
$\epsilon_{0}=0.005$ (Section 2.2.3), suggesting that the outliers that cause
brittleness may have been down-weighted by OWL for $\epsilon=\epsilon_{0}$.
Figure 17: The minimum OKL estimate (i.e.
$\hat{R}(\epsilon)=\min_{\theta\in\Theta}\hat{I}_{\epsilon}(\theta)$) versus
$\epsilon$ plot for the micro-credit example. Using the notion of curvature in
Section 2.2.3, the value $\epsilon_{0}=0.005$ was identified as the point at
which this graph has its prominent kink. The $90\%$ confidence bands under
$m=50$ OS-bootstrap iterations are also shown. Figure 18: The profit
distribution for households that were declared to be inliers
($\\{i:w_{i}<1\\}$) versus outliers ($\\{i:w_{i}\leq 1\\}$) by the OWL
procedure at parameter $\epsilon_{0}$. For clarity, we omitted an outlying
household with a profit value of less that $-40K$ USD PPP.