#  Risk Bounds for Mixture Density Estimation on Compact Domains via the
$h$-Lifted Kullback–Leibler Divergence

Mark Chiu Chong<EMAIL_ADDRESS>
School of Mathematics and Physics
The University of Queensland
St Lucia, QLD 4072, Australia Hien Duy Nguyen<EMAIL_ADDRESS>
Institute of Mathematics for Industry
Kyushu University
Nishi Ward, Fukuoka 819-0395, Japan;
School of Computing, Engineering,
and Mathematical Sciences
La Trobe University
Bundoora, VIC 3086, Australia; TrungTin Nguyen<EMAIL_ADDRESS>
School of Mathematics and Physics
The University of Queensland
St Lucia, QLD 4072, Australia

###### Abstract

We consider the problem of estimating probability density functions based on
sample data, using a finite mixture of densities from some component class. To
this end, we introduce the $h$-lifted Kullback–Leibler (KL) divergence as a
generalization of the standard KL divergence and a criterion for conducting
risk minimization. Under a compact support assumption, we prove an
$\mathcal{O}(1/{\sqrt{n}})$ bound on the expected estimation error when using
the $h$-lifted KL divergence, which extends the results of Rakhlin et al.
(2005, ESAIM: Probability and Statistics, Vol. 9) and Li and Barron (1999,
Advances in Neural Information Processing Systems, Vol. 12) to permit the risk
bounding of density functions that are not strictly positive. We develop a
procedure for the computation of the corresponding maximum $h$-lifted
likelihood estimators ($h$-MLLEs) using the Majorization-Maximization
framework and provide experimental results in support of our theoretical
bounds.

Keywords: Kullback–Leibler divergence, mixture density estimation, maximum
likelihood, convergence rates, learning theory.

##  1 Introduction

Let $\left(\Omega,\mathfrak{A},{\mathrm{\mathbf{P}}}\right)$ be an abstract
probability space and let $X:\Omega\to\mathcal{X}$ be a random variable taking
values in the measurable space $\left(\mathcal{X},\mathfrak{F}\right)$, where
$\mathcal{X}$ is a compact metric space equipped with its Borel
$\sigma$-algebra $\mathfrak{F}$. Suppose that we observe an independent and
identically distributed (i.i.d.) sample of random variables
$\mathbf{X}_{n}=\left(X_{i}\right)_{i\in\left[n\right]}$, where
$\left[n\right]=\left\\{1,\ldots,n\right\\}$, and that each $X_{i}$ arises
from the same data generating process as $X$, characterized by the probability
measure $F\ll\mu$ on $\left(\mathcal{X},\mathfrak{F}\right)$, with density
function $f=\mathrm{d}F/\mathrm{d}\mu$, for some $\sigma$-finite $\mu$.

In this work, we are concerned with the estimating $f$ via a data dependent
double-index sequence of estimators $\left(f_{k,n}\right)_{k,n\in\mathbb{N}}$,
where

$\displaystyle f_{k,n}\in\mathcal{C}_{k}$
$\displaystyle=\mathrm{co}_{k}\left(\mathcal{P}\right)$
$\displaystyle=\left\\{f_{k}\left(\cdot;\psi_{k}\right)=\sum_{j=1}^{k}\pi_{j}\varphi\left(\cdot;\theta_{j}\right)\mid\varphi\left(\cdot;\theta_{j}\right)\in\mathcal{P},\,\pi_{j}\geq
0,\,j\in\left[k\right],\,\sum_{j=1}^{k}\pi_{j}=1\right\\},$

for each $k,n\in\mathbb{N}$, and where

$\mathcal{P}=\left\\{\varphi\left(\cdot;\theta\right):\mathcal{X}\rightarrow\mathbb{R}_{\geq
0}\mid\theta\in\Theta\subset\mathbb{R}^{d}\right\\},$

$\psi_{k}=\left(\pi_{1},\dots,\pi_{k},\theta_{1},\dots,\theta_{k}\right)$, and
$d\in\mathbb{N}$. To ensure the measurability and existence of various optima,
we shall assume that $\varphi$ is Caratheodory in the sense that
$\varphi\left(\cdot;\theta\right)$ is
$\left(\mathcal{X},\mathfrak{F}\right)$-measurable, for each
$\theta\in\Theta$, and $\varphi\left(X;\cdot\right)$ is continuous for each
$X\in\mathcal{X}$.

In the definition above, we can identify the set
$\mathcal{C}_{k}=\mathrm{co}_{k}\left(\mathcal{P}\right)$ as the set of
density functions that can be written as a convex combination of $k$ elements
of $\mathcal{P}$, where $\mathcal{P}$ is often called the space of component
density functions. We then interpret $\mathcal{C}_{k}$ as the class of
$k$-component finite mixtures of densities of class $\mathcal{P}$, as studied,
for example, by McLachlan and Peel (2004); Nguyen et al. (2020, 2022b).

###  1.1 Risk bounds for mixture density estimation

We are particularly interested in oracle bounds of the form

${\mathrm{\mathbf{E}}}\left\\{\ell\left(f,f_{k,n}\right)\right\\}-\ell\left(f,\mathcal{C}\right)\leq\rho\left(k,n\right),$
(1)

where $\left(p,q\right)\mapsto\ell\left(p,q\right)\in\mathbb{R}_{\geq 0}$ is a
loss function on pairs of density functions. We also define the density-to-
class loss

$\ell\left(f,\mathcal{C}\right)=\inf_{q\in\mathcal{C}}\ell\left(f,q\right),\
\mathcal{C}=\mathrm{cl}\left(\bigcup_{k\in\mathbb{N}}\mathrm{co}_{k}\left(\mathcal{P}\right)\right),$

where $\mathrm{cl}(\cdot)$ is the closure. Here, we identify
$\left(k,n\right)\mapsto\rho\left(k,n\right)$ as a characterization of the
rate at which the left-hand side of (1) converges to zero as $k$ and $n$
increase. Our present work follows the research of Li and Barron (1999),
Rakhlin et al. (2005) and Klemelä (2007) (see also Klemelä 2009, Ch. 19). In
Li and Barron (1999) and Rakhlin et al. (2005), the authors consider the case
where $\ell\left(p,q\right)$ is taken to be the Kullback–Leibler (KL)
divergence

$\mathrm{KL}\left(p\,||\,q\right)=\int p\log\frac{p}{q}\mathrm{d}\mu,$

and $f_{k,n}=f_{k}\left(\cdot;{\psi}_{k,n}\right)$ is a maximum likelihood
estimator (MLE), where

${\psi}_{k,n}\in\underset{\psi_{k}\in\mathcal{S}_{k}\times\Theta^{k}}{\operatorname*{arg\,max\,}}\frac{1}{n}\sum_{i=1}^{n}\log
f_{k}\left(X_{i};\psi_{k}\right),$

is a function of $\mathbf{X}_{n}$, with $\mathcal{S}_{k}$ denoting the
probability simplex in $\mathbb{R}^{k}$.

Under the assumption that $f,f_{k}\geq a$, for some $a>0$ and each
$k\in\left[n\right]$ (i.e., strict positivity), Li and Barron (1999) obtained
the bound

${\mathrm{\mathbf{E}}}\left\\{\mathrm{KL}\left(f\,||\,f_{k,n}\right)\right\\}-\mathrm{KL}\left(f\,||\,\mathcal{C}\right)\leq
c_{1}\frac{1}{k}+c_{2}\frac{k\log\left(c_{3}n\right)}{n},$

for constants $c_{1},c_{2},c_{3}>0$, which was then improved by Rakhlin et al.
(2005) who obtain the bound

${\mathrm{\mathbf{E}}}\left\\{\mathrm{KL}\left(f\,||\,f_{k,n}\right)\right\\}-\mathrm{KL}\left(f\,||\,\mathcal{C}\right)\leq
c_{1}\frac{1}{k}+c_{2}\frac{1}{\sqrt{n}},$

for constants $c_{1},c_{2}>0$ (constants $(c_{j})_{j\in\mathbb{N}}$ are
typically different between expressions).

Alternatively, Klemelä (2007) takes $\ell\left(p,q\right)$ to be the squared
$L_{2}\left(\mu\right)$ norm distance (i.e., the least-squares loss):

$\ell\left(p,q\right)=\lVert p-q\rVert_{2,\mu}^{2},$

where $\lVert p\rVert_{2,\mu}^{2}=\int_{\mathcal{X}}\lvert
p\rvert^{2}\mathrm{d}\mu$, for each $p\in L_{2}\left(\mu\right)$, and choose
$f_{k,n}$ as minimizers of the $L_{2}\left(\mu\right)$ empirical risk: i.e.,
$f_{k,n}=f_{k}\left(\cdot;{\psi}_{k,n}\right)$, where

$\psi_{k,n}\in\underset{\psi_{k}\in\mathcal{S}_{k}\times\Theta^{k}}{\operatorname*{arg\,min\,}}-\frac{2}{n}\sum_{i=1}^{n}f_{k}\left(\cdot;\psi_{k}\right)+\left\|f_{k}\left(\cdot;\psi_{k}\right)\right\|_{2,\mu}^{2}.$
(2)

Here, Klemelä (2007) establish the bound

${\mathrm{\mathbf{E}}}\left\|f-{f}_{k,n}\right\|_{2,\mu}^{2}-\inf_{q\in\mathcal{C}}\left\|f-q\right\|_{2,\mu}^{2}\leq
c_{1}\frac{1}{k}+c_{2}\frac{1}{\sqrt{n}},$

$c_{1},c_{2}>0$, without the lower bound assumption on $f,f_{k}$ above, even
permitting $\mathcal{X}$ to be unbounded. Via the main results of Naito and
Eguchi (2013), the bound above can be generalized to the $U$-divergences,
which includes the special $L_{2}(\mu)$ norm distance as a special case.

On the one hand, the sequence of MLEs required for the results of Li and
Barron (1999) and Rakhlin et al. (2005) are typically computable, for example,
via the usual expectation–maximization approach (cf. McLachlan and Peel 2004,
Ch. 2). This contrasts with the computation of least-squares density
estimators of form (2), which requires evaluations of the typically
intractable integral expressions:
$\left\|f_{k}\left(\cdot;\psi_{k}\right)\right\|_{2}^{2}$. However, the least-
squares approach of Klemelä (2007) permits the analysis using families
$\mathcal{P}$ of usual interest, such as normal distributions and beta
distributions, the latter of which being compactly supported but having
densities that cannot be bounded away from zero without restrictions, and thus
do not satisfy the regularity conditions of Li and Barron (1999) and Rakhlin
et al. (2005).

###  1.2 Main contributions

We propose the following $h$-lifted KL divergence, as a generalization of the
standard KL divergence to address the computationally tractable estimation of
density functions which do not satisfy the regularity conditions of Li and
Barron (1999) and Rakhlin et al. (2005). The use of the $h$-lifted KL
divergence has the possibility to advance theories based on the standard KL
divergence in statistical machine learning. To this end, let
$h:\mathcal{X}\rightarrow\mathbb{R}_{\geq 0}$ be a function in $L_{1}(\mu)$,
and define the $h$-lifted KL divergence by:

$\mathrm{KL}_{h}\left(p\,||\,q\right)=\int_{\mathcal{X}}\left\\{p+h\right\\}\log\frac{p+h}{q+h}\mathrm{d}\mu.$
(3)

In the sequel, we shall show that $\mathrm{KL}_{h}$ is a Bregman divergence on
the space of probability density functions, as per Csiszár (1995).

Assume that $h$ is a probability density function, and let
$\mathbf{Y}_{n}=\left(Y_{i}\right)_{i\in\left[n\right]}$ be a an i.i.d.
sample, independent of $\mathbf{X}_{n}$, where each
$Y_{i}:\Omega\rightarrow\mathcal{X}$ is a random variable with probability
measure on $(\mathcal{X},\mathfrak{F})$, characterized by the density $h$ with
respect to $\mu$. Then, for each $k$ and $n$, let $f_{k,n}$ be defined via the
maximum $h$-lifted likelihood estimator ($h$-MLLE):
$f_{k,n}=f_{k}\left(\cdot;{\psi}_{k,n}\right)$, where

${\psi}_{k,n}\in\underset{\psi_{k}\in\mathcal{S}_{k}\times\Theta^{k}}{\operatorname*{arg\,max\,}}~{}\frac{1}{n}\sum_{i=1}^{n}\left(\log\left\\{f_{k}\left(X_{i};\psi_{k}\right)+h\left(X_{i}\right)\right\\}+\log\left\\{f_{k}\left(Y_{i};\psi_{k}\right)+h\left(Y_{i}\right)\right\\}\right).$
(4)

The primary aim of this work is to show that

${\mathrm{\mathbf{E}}}\left\\{\mathrm{KL}_{h}\left(f\,||\,f_{k,n}\right)\right\\}-\mathrm{KL}_{h}\left(f\,||\,\mathcal{C}\right)\leq
c_{1}\frac{1}{k}+c_{2}\frac{1}{\sqrt{n}}$ (5)

for some constants $c_{1},c_{2}>0$, without requiring the strict positivity
assumption that $f,f_{k}\geq a>0$.

This result is a compromise between the works of Li and Barron (1999) and
Rakhlin et al. (2005), and Klemelä (2007), as it applies to a broader space of
component densities $\mathcal{P}$, and because the required $h$-MLLEs, (4),
can be efficiently computed via minorization–maximization (MM) algorithms
(see, e.g., Lange 2016). We shall discuss this assertion in Section 6.

###  1.3 Relevant literature

Our work largely follows the approach of Li and Barron (1999), which have was
extended upon by Rakhlin et al. (2005) and Klemelä (2007). All three texts use
approaches based on the availability of greedy algorithms for maximizing
convex functions with convex functional domains. In this work, we shall make
use of the proof techniques of Zhang (2003). Related results in this direction
can be found in DeVore and Temlyakov (2016) and Temlyakov (2016). Making the
same boundedness assumption as Rakhlin et al. (2005), Dalalyan and Sebbar
(2018) obtain refined oracle inequalities under the additional assumption that
the class $\mathcal{P}$ is finite. Numerical implementations of greedy
algorithms for estimating finite mixtures of Gaussian densities were studied
by Vlassis and Likas (2002) and Verbeek et al. (2003).

The $h$-MLLE as an optimization objective can be compared to other similar
modified likelihood estimators, such as the $L_{q}$ likelihood of Ferrari and
Yang (2010) and Qin and Priebe (2013), the $\beta$-likelihood of Basu et al.
(1998) and Fujisawa and Eguchi (2006), penalized likelihood estimators, such
as maximum a posteriori estimators of Bayesian models, or $f$-separable
Bregman distortion measures of Kobayashi and Watanabe (2024, 2021).

The practical computation of the $h$-MLLEs, (4), is made possible via the MM
algorithm framework of Lange (2016), see also Hunter and Lange (2004), Wu and
Lange (2010), and Nguyen (2017) for further details. Such algorithms have
well-studied global convergence properties and can be modified for mini-batch
and stochastic settings (see, e.g., Razaviyayn et al., 2013 and Nguyen et al.,
2022a).

A related and popular setting of investigations is that of model selection,
where the objects of interest are single-index sequences
$\left(f_{k_{n},n}\right)_{n\in\mathbb{N}}$, and where the aim is to obtain
finite-sample bounds for losses of the form $\ell\left(f_{k_{n},n},f\right)$,
where each $k_{n}\in\mathbb{N}$ is a data dependent function, often obtained
by optimizing some penalized loss criterion, as described in Massart (2007),
Koltchinskii (2011, Ch. 6), and Giraud (2021, Ch. 2). In the context of finite
mixtures, examples of such analyses can be found in the works of Maugis and
Michel (2011) and Maugis-Rabusseau and Michel (2013). A comprehensive
bibliography of model selection results for finite mixtures and related
statistical models can be found in Nguyen et al. (2022c).

###  1.4 Organization of paper

The manuscript proceeds as follows. In the following section we formally
characterize the $h$-lifted KL divergence as a Bregman divergence, and
establish some of its properties. In Section 4, we prove new risk bounds of
the form (1) in terms of the $h$-lifted KL divergence. We discuss the
computation of the $h$-lifted likelihood estimator of form (4) in Section 6,
followed by the presentation of some empirical results regarding the
convergence of (1) in terms of both $k$ and $n$. Additional technical results
are also included in the Appendices.

##  2 The $h$-lifted KL divergence and its properties

In this section we formally define the $h$-lifted KL divergence on the space
of density functions and establish some of its properties.

######  Definition 1 ($h$-lifted KL divergence).

Let $f,g$, and $h$ be probability density functions on the space
$\mathcal{X}$, where $h>0$. The $h$-lifted _KL_ divergence from $g$ to $f$ is
defined as follows:

$\mathrm{KL}_{h}\left(f\,||\,g\right)=\int_{\mathcal{X}}\left\\{f+h\right\\}\log\frac{f+h}{g+h}\mathrm{d}\mu={\operatorname*{{\mathrm{\mathbf{E}}}}}_{f}\left\\{\log\frac{f+h}{g+h}\right\\}+{\operatorname*{{\mathrm{\mathbf{E}}}}}_{h}\left\\{\log\frac{f+h}{g+h}\right\\}.$

###  2.1 $\textrm{KL}_{h}$ as a Bregman divergence

Let $\phi:\mathcal{I}\to\operatorname*{\mathbb{R}}$, $\mathcal{I}=(0,\infty)$
be a strictly convex function that is continuously differentiable. The Bregman
divergence between scalars
$d_{\phi}:\mathcal{I}\times\mathcal{I}\to\mathbb{R}_{\geq 0}$ generated by the
function $\phi$ is given by:

$d_{\phi}(p,q)=\phi(p)-\phi(q)-\phi^{\prime}(q)(p-q),$

where $\phi^{\prime}(q)$ denotes the derivative of $\phi$ at $q$.

Bregman divergences possess several useful properties, including the following
list:

  1. 1.

Non-negativity: $d_{\phi}(p,q)\geq 0$ for all $p,q\in\mathcal{I}$ with
equality if and only if $p=q$;

  2. 2.

Asymmetry: $d_{\phi}(p,q)\neq d_{\phi}(q,p)$ in general;

  3. 3.

Convexity: $d_{\phi}(p,q)$ is convex in $p$ for every fixed $q\in\mathcal{I}$.

  4. 4.

Linearity:
$d_{c_{1}\phi_{1}+c_{2}\phi_{2}}(p,q)=c_{1}\,d_{\phi_{1}}(p,q)+c_{2}\,d_{\phi_{2}}(p,q)$
for $c_{1},c_{2}\geq 0$.

The properties for Bregman divergences between scalars can be extended to
density functions and other functional spaces, as established in Frigyik et
al. (2008) and Stummer and Vajda (2012), for example. We also direct the
interested reader to the works of Pardo (2006), Basu et al. (2011), and Amari
(2016).

The class of $h$-lifted KL divergences constitute a generalization of the
usual KL divergence and are a subset of the Bregman divergences over the space
of density functions that are considered by Csiszár (1995). Namely, let
$\mathcal{P}$ be a convex set of probability densities with respect to the
measure $\mu$ on $\mathcal{X}$. The Bregman divergence
$D_{\phi}:\mathcal{P}\times\mathcal{P}\to[0,\infty)$ between densities
$p,q\in\mathcal{P}$ can be constructed as follows:

$D_{\phi}(p\,||\,q)=\int_{\mathcal{X}}d_{\phi}\left(p(x),q(x)\right)\mathrm{d}\mu(x).$

The $h$-lifted KL divergence $\mathrm{KL}_{h}$ as a Bregman divergence is
generated by the function $\phi(u)=(u+h)\log(u+h)-(u+h)+1$. This assertion is
demonstrated in Appendix A.

###  2.2 Advantages of the $h$-lifted KL divergence

When the standard KL divergence is employed in the density estimation problem,
it is common to restrict consideration of density functions to those bounded
away from zero by some positive constant. That is, one typically considers the
smaller class of so-called admissible target densities
$\mathcal{P}_{\alpha}\subset\mathcal{P}$ (cf. Meir and Zeevi, 1997), where

$\mathcal{P}_{\alpha}=\left\\{\varphi(\cdot;\theta)\in\mathcal{P}\mid\varphi(\cdot;\theta)\geq\alpha>0\right\\}.$

Without this restriction, the standard KL divergence can be unbounded, even
for functions with bounded $L_{1}$ norms. For example, let $p$ and $q$ be
densities of beta distributions on the support $\mathcal{X}=\left[0,1\right]$.
That is, suppose that $p,q\in\mathcal{P}_{\mathrm{beta}}$, respectively
characterized by parameters $\theta_{p}=\left(a_{p},b_{p}\right)$ and
$\theta_{q}=\left(a_{q},b_{q}\right)$, where

$\mathcal{P}_{\mathrm{beta}}=\left\\{x\mapsto\beta\left(x;\theta\right)=\frac{\Gamma\left(a+b\right)}{\Gamma\left(a\right)\Gamma\left(b\right)}x^{a-1}\left(1-x\right)^{b-1},\theta=\left(a,b\right)\in\mathbb{R}_{>0}^{2}\right\\}.$
(6)

Then, from Gil et al. (2013), the KL divergence between $p$ and $q$ is given
by:

$\mathrm{KL}\left(p\,||\,q\right)=\log\left\\{\frac{\Gamma\left(a_{q}\right)\Gamma\left(b_{q}\right)}{\Gamma\left(a_{q}+b_{q}\right)}\right\\}-\log\left\\{\frac{\Gamma\left(a_{p}\right)\Gamma\left(b_{p}\right)}{\Gamma\left(a_{p}+b_{p}\right)}\right\\}\\\
+\left(a_{p}-a_{q}\right)\left\\{\psi\left(a_{p}\right)-\psi\left(a_{p}+b_{p}\right)\right\\}+\left(b_{p}-b_{q}\right)\left\\{\psi\left(b_{p}\right)-\psi\left(a_{p}+b_{p}\right)\right\\},$

where $\psi:\mathbb{R}_{>0}\rightarrow\mathbb{R}$ is the digamma function.
Next, suppose that $a_{p}=b_{q}$ and $a_{q}=b_{p}=1$, which leads to the
simplification

$\mathrm{KL}\left(p\,||\,q\right)=\left(a_{p}-1\right)\left\\{\psi\left(a_{p}\right)-\psi(1)\right\\}.$

Since $\psi$ is strictly increasing, we observe that the right-hand side
diverges as $a_{p}\to\infty$. Thus, the KL divergence between beta
distributions is unbounded. The $h$-lifted KL divergence in contrast does not
suffer from this problem, and does not require the restriction to
$\mathcal{P}_{\alpha}$. This allows us to consider cases where
$p,q\in\mathcal{P}$ are not bounded away from $0$.

######  Proposition 2.

$\mathrm{KL}_{h}\left(p\,||\,q\right)$ is bounded for all continuous densities
$p,q\in\mathcal{P}$.

Proof.  Let $\tilde{p}=p+h$ and $\tilde{q}=q+h$. Since $h$ is positive, there
exists some $\tilde{q}_{*}$ such that
$\tilde{q}_{*}=\inf_{x\in\mathcal{X}}\left\\{q(x)+h(x)\right\\}>0$. Similarly,
since $\mathcal{X}$ is compact, there exists some positive $\tilde{p}^{*}$
such that
$0<\tilde{p}^{*}=\sup_{x\in\mathcal{X}}\left\\{p(x)+h(x)\right\\}<\infty$.
Define $M=\sup_{x\in\mathcal{X}}\log\\{\tilde{p}(x)/\tilde{q}(x)\\}$. Then
$M<\infty$, and

$\mathrm{KL}_{h}\left(p\,||\,q\right)=\int_{\mathcal{X}}\tilde{p}\log\frac{\tilde{p}}{\tilde{q}}\mathrm{d}\mu\leq\sup_{x\in\mathcal{X}}\log\frac{\tilde{p}}{\tilde{q}}\int_{\mathcal{X}}\tilde{p}\mathrm{d}\mu=2M<\infty.$

Let $L_{p}(f,g)$ denote the standard $L_{p}$ norm,

$L_{p}(f,g)=\left\\{\int_{\mathcal{X}}\left\lvert
f(x)-g(x)\right\rvert^{p}\mathrm{d}\mu(x)\right\\}^{1/p}.$

As remarked previously, Klemelä (2007) established empirical risk bounds in
terms of the $L_{2}$ norm distance. Following results from Meir and Zeevi
(1997), characterizing the relationship between the KL divergence in terms of
the $L_{2}$ norm distance, we establish the corresponding relationship between
the $h$-lifted KL divergence and the $L_{2}$ norm distance.

######  Proposition 3.

For probability density functions $f,g$, and $h$, where $h$ is such that
$h(x)\geq\gamma>0$ for all $x\in\mathcal{X}$, the following inequality holds:

$\mathrm{KL}_{h}\left(f\,||\,g\right)\leq\gamma^{-1}L_{2}^{2}(f,g).$

Proof.  Defining $\tilde{f}$ and $\tilde{g}$ as above, we have

$\mathrm{KL}_{h}\left(f\,||\,g\right)=\int_{\mathcal{X}}\tilde{f}\log\frac{\tilde{f}}{\tilde{g}}\mathrm{d}\mu\leq\int_{\mathcal{X}}\tilde{f}\left(\frac{\tilde{f}}{\tilde{g}}-1\right)\mathrm{d}\mu=\int_{\mathcal{X}}\frac{(f-g)^{2}}{\tilde{g}}\mathrm{d}\mu\leq\gamma^{-1}L_{2}^{2}(f,g),$

The following section is devoted to establishing some technical definitions
and instrumental results which will be utilized in later sections.

##  3 Preliminaries

Recall that we are interested in bounds of the form (1). Note that
$\mathcal{P}$ is a subset of the linear space

$\mathcal{V}=\text{cl}\left(\bigcup_{k\in\mathbb{N}}\left\\{\sum_{j=1}^{k}\varpi_{j}\varphi\left(\cdot;\theta_{j}\right)\mid\varphi\left(\cdot;\theta_{j}\right)\in\mathcal{P},\varpi_{j}\in\mathbb{R},j\in\left[k\right]\right\\}\right),$

and hence we can apply the following result, paraphrased from Zhang (2003,
Thm. II.1).

######  Lemma 4.

Let $\kappa$ be a differentiable and convex function on $\mathcal{V}$, and let
$\left(\bar{f}_{k}\right)_{k\in\mathbb{N}}$ be a sequence of functions
obtained by Algorithm 1. If

$\sup_{p,q\in\mathcal{C},\pi\in\left(0,1\right)}\frac{\mathrm{d}^{2}}{\mathrm{d}\pi^{2}}\kappa\left(\left(1-\pi\right)p+\pi
q\right)\leq\mathfrak{M}<\infty,$

then, for each $k\in\mathbb{N}$,

$\kappa\left(\bar{f}_{k}\right)-\inf_{p\in\mathcal{C}}\kappa\left(p\right)\leq\frac{2\mathfrak{M}}{k+2}.$

Algorithm 1 Algorithm for computing a greedy approximation sequence.

1: Input: $\bar{f}_{0}\in\mathcal{P}$

2: for $k\in\mathbb{N}$ do

3: Compute
$\left(\bar{\pi}_{k},\bar{\theta}_{k}\right)=\operatorname*{arg\,min\,}\limits_{\left(\pi,\theta\right)\in[0,1]\times\Theta}\kappa\left(\left(1-\pi\right)\bar{f}_{k-1}+\pi\varphi\left(\cdot;\theta\right)\right)$

4: Define
$\bar{f}_{k}=\left(1-\bar{\pi}_{k}\right)\bar{f}_{k-1}+\bar{\pi}_{k}\varphi\left(\cdot;\bar{\theta}_{k}\right)$

5: end for

We are interested in two choices for $\kappa$:

$\kappa\left(p\right)=\mathrm{KL}_{h}\left(f\,||\,p\right)$ (7)

and its sample counterpart,

$\kappa_{n}\left(p\right)=\frac{1}{n}\sum_{i=1}^{n}\log\frac{f\left(X_{i}\right)+h\left(X_{i}\right)}{p\left(X_{i}\right)+h\left(X_{i}\right)}+\frac{1}{n}\sum_{i=1}^{n}\log\frac{f\left(Y_{i}\right)+h\left(Y_{i}\right)}{p\left(Y_{i}\right)+h\left(Y_{i}\right)},$
(8)

where $(X_{i})_{i\in[n]}$ and $(Y_{i})_{i\in[n]}$ are realisations of $X$ and
$Y$, respectively. For choice (7), by the dominated convergence theorem, we
observe that

$\displaystyle\frac{\mathrm{d}^{2}}{\mathrm{d}\pi^{2}}\kappa\left(\left(1-\pi\right)p+\pi
q\right)$
$\displaystyle\qquad\quad={\operatorname*{{\mathrm{\mathbf{E}}}}}_{f}\left\\{\frac{\mathrm{d}^{2}}{\mathrm{d}\pi^{2}}\log\frac{f+h}{\left(1-\pi\right)p+\pi
q+h}\right\\}+{\operatorname*{{\mathrm{\mathbf{E}}}}}_{h}\left\\{\frac{\mathrm{d}^{2}}{\mathrm{d}\pi^{2}}\log\frac{f+h}{\left(1-\pi\right)p+\pi
q+h}\right\\}$
$\displaystyle\qquad\quad={\operatorname*{{\mathrm{\mathbf{E}}}}}_{f}\left\\{\frac{\left(p-q\right)^{2}}{\left[\left(1-\pi\right)p+\pi
q+h\right]^{2}}\right\\}+{\operatorname*{{\mathrm{\mathbf{E}}}}}_{h}\left\\{\frac{\left(p-q\right)^{2}}{\left[\left(1-\pi\right)p+\pi
q+h\right]^{2}}\right\\}.$

Suppose that each $\varphi\left(\cdot;\theta\right)\in\mathcal{P}$ is bounded
from above by $c<\infty$. Then, since $p,q\in\mathcal{C}$ are non-negative
functions, we have the fact that $\left(p-q\right)^{2}\leq c^{2}$. If we
further have $a\leq h$ for some $a>0$, then $\left[\left(1-\pi\right)p+\pi
q+h\right]^{2}\geq a^{2}$, which implies that

$\frac{\mathrm{d}^{2}}{\mathrm{d}\pi^{2}}\kappa\left(\left(1-\pi\right)p+\pi
q\right)\leq 2\times\frac{c^{2}}{a^{2}}$

for every $p,q\in\mathcal{C}$ and $\pi\in\left(0,1\right)$, and thus

$\sup_{p,q\in\mathcal{C},\pi\in\left(0,1\right)}\frac{\mathrm{d}^{2}}{\mathrm{d}\pi^{2}}\kappa\left(\left(1-\pi\right)p+\pi
q\right)\leq\frac{2c^{2}}{a^{2}}<\infty.$

Similarly, for case (8), we have

$\frac{\mathrm{d}^{2}}{\mathrm{d}\pi^{2}}\kappa_{n}\left(\left(1-\pi\right)p+\pi
q\right)=\frac{1}{n}\sum_{i=1}^{n}\frac{\mathrm{d}^{2}}{\mathrm{d}\pi^{2}}\log\frac{f\left(x_{i}\right)+h\left(x_{i}\right)}{\left(1-\pi\right)p\left(x_{i}\right)+\pi
q\left(x_{i}\right)+h\left(x_{i}\right)}\\\
+\frac{1}{n}\sum_{i=1}^{n}\frac{\mathrm{d}^{2}}{\mathrm{d}\pi^{2}}\log\frac{f\left(y_{i}\right)+h\left(y_{i}\right)}{\left(1-\pi\right)p\left(y_{i}\right)+\pi
q\left(y_{i}\right)+h\left(y_{i}\right)}\\\
=\frac{1}{n}\sum_{i=1}^{n}\frac{\left(p\left(x_{i}\right)-q\left(x_{i}\right)\right)^{2}}{\left[\left(1-\pi\right)p\left(x_{i}\right)+\pi
q\left(x_{i}\right)+h\left(x_{i}\right)\right]^{2}}+\frac{1}{n}\sum_{i=1}^{n}\frac{\left(p\left(y_{i}\right)-q\left(y_{i}\right)\right)^{2}}{\left[\left(1-\pi\right)p\left(y_{i}\right)+\pi
q\left(y_{i}\right)+h\left(y_{i}\right)\right]^{2}}.$

By the same argument, as for $\kappa$, we have the fact that
$\left(p\left(x\right)-q\left(x\right)\right)^{2}\leq c^{2}$, for every
$p,q\in\mathcal{C}$ and every $x\in\mathcal{X}$, and furthermore
$\left[\left(1-\pi\right)p\left(x\right)+\pi
q\left(x\right)+h\left(x\right)\right]^{2}\geq a^{2}$, for any
$\pi\in\left(0,1\right)$. Thus,

$\sup_{p,q\in\mathcal{C},\pi\in\left(0,1\right)}\frac{\mathrm{d}^{2}}{\mathrm{d}\pi^{2}}\kappa\left(\left(1-\pi\right)p+\pi
q\right)\leq\frac{2c^{2}}{a^{2}}<\infty,$

as required. We therefore obtain the following result.

######  Proposition 5.

Let $\square$ denote either $\kappa$, the $\textrm{KL}_{h}$ divergence (7), or
$\kappa_{n}$, the sample $\textrm{KL}_{h}$ divergence (8), and assume that
$h\geq a$ and $\varphi\left(\cdot;\theta\right)\leq c$, for each
$\theta\in\Theta$. Then,

$\square\left(\bar{f}_{k}\right)-\inf_{p\in\mathcal{C}}\square\left(p\right)\leq\frac{4a^{-2}c^{2}}{k+2},$

for each $k\in\mathbb{N}$, where $\left(\bar{f}_{k}\right)_{k\in\mathbb{N}}$
is obtained as per Algorithm 1.

Notice that sequences $\left(\bar{f}_{k}\right)_{k\in\mathbb{N}}$ obtained via
Lemma 4 are greedy approximation sequences, and that
$\bar{f}_{k}\in\mathcal{C}_{k}$, for each $k\in\mathbb{N}$. Let
$\left(f_{k}\right)_{k\in\mathbb{N}}$ be the sequence of minimizers defined by

$f_{k}=\underset{\psi_{k}\in\mathcal{S}_{k}\times\Theta^{k}}{\operatorname*{arg\,min\,}}\mathrm{KL}_{h}\left(f\,||\,f_{k}\left(\cdot;\psi_{k}\right)\right),$
(9)

and let $\left(f_{k,n}\right)_{k\in\mathbb{N}}$ be the sequence of $h$-MLLEs,
as per (4). Then, by definition, we have the fact that
$\kappa\left(f_{k}\right)\leq\kappa\left(\bar{f}_{k}\right)$ and
$\kappa\left(f_{k,n}\right)\leq\kappa\left(\bar{f}_{k}\right)$, for $\kappa$
set as (7) or (8), respectively. Thus, we have the following result.

######  Proposition 6.

For the $\textrm{KL}_{h}$ divergence (7), under the assumption that $h\geq a$
and $\varphi\left(\cdot;\theta\right)\leq c$, for each $\theta\in\Theta$, we
have

$\kappa\left(f_{k}\right)-\inf_{p\in\mathcal{C}}\kappa\left(p\right)\leq\frac{4a^{-2}c^{2}}{k+2}$
(10)

for each $k\in\mathbb{N}$, where $\left(f_{k}\right)_{k\in\mathbb{N}}$ is the
sequence of minimizers defined via (9). Furthermore, for the sample
$\textrm{KL}_{h}$ divergence (8), under the same assumptions as above, we have

$\kappa_{n}\left(f_{k,n}\right)-\inf_{p\in\mathcal{C}}\kappa_{n}\left(p\right)\leq\frac{4a^{-2}c^{2}}{k+2},$
(11)

for each $k\in\mathbb{N}$, where $\left(f_{k,n}\right)_{k\in\mathbb{N}}$ are
$h$-MLLEs defined via (4).

As is common in many statistical learning/uniform convergence results (e.g.,
Bartlett and Mendelson, 2002, Koltchinskii and Panchenko, 2004), we employ the
use of Rademacher processes and associated bounds. Let
$(\varepsilon_{i})_{i\in[n]}$ be i.i.d. Rademacher random variables, that is
$\mathrm{\mathbf{P}}(\varepsilon_{i}=-1)=\mathrm{\mathbf{P}}(\varepsilon_{i}=1)=\nicefrac{{1}}{{2}}$,
that are independent of $(X_{i})_{i\in[n]}$. The Rademacher process, indexed
by a class of real measurable functions $\mathcal{S}$, is defined as the
quantity

$R_{n}(s)=\frac{1}{n}\sum_{i=1}^{n}s(X_{i})\varepsilon_{i},$

for $s\in\mathcal{S}$. The Rademacher complexity of the class $\mathcal{S}$ is
given by
$\mathcal{R}_{n}(\mathcal{S})=\operatorname*{{\mathrm{\mathbf{E}}}}\sup_{s\in\mathcal{S}}\lvert
R_{n}(s)\rvert$.

In the subsequent section, we make use of the following result regarding the
supremum of convex functions:

######  Lemma 7 (Rockafellar, 1997, Thm. 32.2).

Let $\eta$ be a convex function on a linear space $\mathcal{T}$, and let
$\mathcal{S}\subset\mathcal{T}$ be an arbitrary subset. Then,

$\sup_{p\in\mathcal{S}}\eta\left(p\right)=\sup_{p\in\mathrm{co}\left(\mathcal{S}\right)}\eta\left(p\right).$

In particular, we use the fact that since a linear functional of convex
combinations achieves its maximum value at vertices, the Rademacher complexity
of $\mathcal{S}$ is equal to the Rademacher complexity of
$\textrm{co}(\mathcal{S})$ (see Lemma 19). We consequently obtain the
following result.

######  Lemma 8.

Let $(\varepsilon_{i})_{i\in[n]}$ be i.i.d. Rademacher random variables,
independent of $(X_{i})_{i\in[n]}$ and $\mathcal{P}$ be defined as above. The
sets $\mathcal{C}$ and $\mathcal{P}$ will have equal complexity,
$\mathcal{R}_{n}(\mathcal{C})=\mathcal{R}_{n}(\mathcal{P})$, and the supremum
of the Rademacher process indexed by $\mathcal{C}$ is equal to the supremum on
the basis functions of $\mathcal{P}$:

${\operatorname*{{\mathrm{\mathbf{E}}}}}_{\varepsilon}\sup_{g\in\mathcal{C}}\left\lvert\frac{1}{n}\sum_{i=1}^{n}g(X_{i})\varepsilon_{i}\right\rvert={\operatorname*{{\mathrm{\mathbf{E}}}}}_{\varepsilon}\sup_{\theta\in\Theta}\left\lvert\frac{1}{n}\sum_{i=1}^{n}\varphi(X_{i};\theta)\varepsilon_{i}\right\rvert.$

Proof.  Follows immediately from Lemma 7.

##  4 Main results

Here we provide explicit statements regarding the convergence rates claimed in
(5). We assume that $f$ is bounded above by some constant $c$ and that the
lifting function $h$ is bounded above and below by constants $a$ and $b$,
respectively.

######  Theorem 9.

Let $h$ be a positive density satisfying $0<a\leq h(x)\leq b$, for all
$x\in\mathcal{X}$. For any target density $f$ satisfying $0\leq f(x)\leq c$,
for all $x\in\mathcal{X}$ and where $f_{k,n}$ is the minimizer of
$\mathrm{KL}_{h}$ over $k$-component mixtures, the following inequality holds:

$\operatorname*{{\mathrm{\mathbf{E}}}}\left\\{\mathrm{KL}_{h}\left(f\,||\,f_{k,n}\right)\right\\}-\mathrm{KL}_{h}\left(f\,||\,\mathcal{C}\right)\leq\frac{u_{1}}{k+2}+\frac{u_{2}}{\sqrt{n}}\int_{0}^{c}\log^{1/2}N(\mathcal{P},\varepsilon/2,{\operatorname*{\lVert\,\cdot\,\rVert}}_{\infty})\mathrm{d}\varepsilon+\frac{u_{3}}{\sqrt{n}},$

where $u_{1}$, $u_{2}$, and $u_{3}$ are positive constants that depend on some
or all of $a$, $b$, and $c$.

######  Corollary 10.

Let $\mathcal{X}$ and $\Theta$ be compact and assume the following Lipschitz
condition holds: for each $x\in\mathcal{X}$, and for each
$\theta,\tau\in\Theta$,

$\left|\varphi\left(x;\theta\right)-\varphi\left(x;\tau\right)\right|\leq\varPhi\left(x\right)\left\|\theta-\tau\right\|_{1},$
(12)

for some function $\varPhi:\mathcal{X}\rightarrow\mathbb{R}_{\geq 0}$, where
$\lVert\varPhi\rVert_{\infty}=\sup_{x\in\mathcal{X}}\lvert\varPhi(x)\rvert<\infty$.
Then the bound in Theorem 9 becomes

$\operatorname*{{\mathrm{\mathbf{E}}}}\left\\{\mathrm{KL}_{h}\left(f\,||\,f_{k,n}\right)\right\\}-\mathrm{KL}_{h}\left(f\,||\,\mathcal{C}\right)\leq\frac{c_{1}}{k+2}+\frac{c_{2}}{\sqrt{n}},$

where $c_{1}$ and $c_{2}$ are positive constants.

##  5 Proofs

We first present a result establishing a uniform concentration bound for the
$h$-lifted log-likelihood ratios, which is instrumental in the proof of
Theorem 9. Our proofs broadly follow the structure of Rakhlin et al. (2005),
modified as needed for the use of $\textrm{KL}_{h}$.

Assume that $0\leq\varphi(\cdot;\theta)<{c}$ for some
$c\in\operatorname*{\mathbb{R}}_{>0}$. For brevity, we adopt the notation:
$\left\lVert T(g)\right\rVert_{\mathcal{C}}=\sup_{g\in\mathcal{C}}\lvert
T(g)\rvert$.

######  Theorem 11.

Let $X_{1},\ldots,X_{n}$ be an i.i.d. sample of size $n$ drawn from a fixed
density $f$ such that $0\leq f(x)\leq c$ for all $x\in\mathcal{X}$, and let
$h$ be a positive density with $0<a\leq h(x)\leq b$ for all $x\in\mathcal{X}$.
Then with probability at least $1-\mathrm{e}^{-t}$,

$\left\lVert\frac{1}{n}\sum_{i=1}^{n}\log\frac{g(X_{i})+h(X_{i})}{f(X_{i})+h(X_{i})}-{\operatorname*{{\mathrm{\mathbf{E}}}}}_{f}\log\frac{g+h}{f+h}\right\rVert_{\mathcal{C}}\leq\frac{w_{1}}{\sqrt{n}}\operatorname*{{\mathrm{\mathbf{E}}}}\int_{0}^{c}\log^{1/2}N(\mathcal{P},\varepsilon,d_{n,x})\mathrm{d}\varepsilon+\frac{w_{2}}{\sqrt{n}}+w_{3}\sqrt{\frac{t}{n}},$

where $w_{1}$, $w_{2}$, and $w_{3}$ are constants that each depend on some or
all of $a$, $b$, and $c$, and $N(\mathcal{P},\varepsilon,d_{n,x})$ is the
$\varepsilon$-covering number of $\mathcal{P}$ with respect to the following
empirical $L_{2}$ metric

$d_{n,x}^{2}(\varphi_{1},\varphi_{2})=\frac{1}{n}\sum_{i=1}^{n}(\varphi_{1}(X_{i})-\varphi_{2}(X_{i}))^{2}.$

######  Remark 12.

The bound on the term

$\left\lVert\frac{1}{n}\sum_{i=1}^{n}\log\frac{g(Y_{i})+h(Y_{i})}{f(Y_{i})+h(Y_{i})}-{\operatorname*{{\mathrm{\mathbf{E}}}}}_{h}\log\frac{g+h}{f+h}\right\rVert_{\mathcal{C}}$

is the same as the above, except where the empirical distance $d_{n,x}$ is
replaced by $d_{n,y}$, defined in the same way as $d_{n,x}$ but with $Y_{i}$
replacing $X_{i}$.

Proof. [of Theorem 11]. Fix $h$ and define the following quantities:
$\tilde{g}=g+h$, $\tilde{f}=f+h$, $\tilde{\mathcal{C}}=\mathcal{C}+h$,

$m_{i}=\log\frac{\tilde{g}(X_{i})}{\tilde{f}(X_{i})},\quad
m_{i}^{\prime}=\log\frac{\tilde{g}(X_{i}^{\prime})}{\tilde{f}(X_{i}^{\prime})},\quad
Z(x_{1},\ldots,x_{n})=\left\lVert\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{g}(X_{i})}{\tilde{f}(X_{i})}-\operatorname*{{\mathrm{\mathbf{E}}}}\log\frac{\tilde{g}}{\tilde{f}}\right\rVert_{\tilde{\mathcal{C}}}.$

We first apply McDiarmid’s inequality (Lemma 21) to the random variable $Z$.
The bound on the martingale difference is given by

$\displaystyle\left\lvert
Z(X_{1},\ldots,X_{i},\ldots,X_{n})-Z(X_{1},\ldots,X_{i}^{\prime},\ldots,X_{n})\right\rvert$
$\displaystyle=\left\lvert\left\lVert\operatorname*{{\mathrm{\mathbf{E}}}}\log\frac{\tilde{g}}{\tilde{f}}-\frac{1}{n}(m_{1}+\\!...\\!+m_{i}+\\!...\\!+m_{n})\right\rVert_{\tilde{\mathcal{C}}}\right.$
$\displaystyle-\left.\left\lVert\operatorname*{{\mathrm{\mathbf{E}}}}\log\frac{\tilde{g}}{\tilde{f}}-\frac{1}{n}(m_{1}+\\!...\\!+m_{i}^{\prime}+\\!...\\!+m_{n})\right\rVert_{\tilde{\mathcal{C}}}\right\rvert$
$\displaystyle\leq\frac{1}{n}\left\lVert\log\frac{\tilde{g}(X_{i}^{\prime})}{\tilde{f}(X_{i}^{\prime})}-\log\frac{\tilde{g}(X_{i})}{\tilde{f}(X_{i})}\right\rVert_{\tilde{\mathcal{C}}}$
$\displaystyle\leq\frac{1}{n}\left(\log\frac{c+b}{a}-\log\frac{a}{c+b}\right)$
$\displaystyle=\frac{1}{n}2\log\frac{c+b}{a}=c_{i}.$

The chain of inequalities holds because of the triangle inequality and the
properties of the supremum. By Lemma 21, we have

${\mathrm{\mathbf{P}}}(Z-\operatorname*{{\mathrm{\mathbf{E}}}}Z>\varepsilon)\leq\exp\left\\{-\frac{n\varepsilon^{2}}{(\sqrt{2}\log\frac{c+b}{a})^{2}}\right\\},$

so

${\mathrm{\mathbf{P}}}(Z\leq\varepsilon+\operatorname*{{\mathrm{\mathbf{E}}}}Z)\geq
1-\exp\left\\{-\frac{n\varepsilon^{2}}{(\sqrt{2}\log\frac{c+b}{a})^{2}}\right\\},$

where it follows from $t=n\varepsilon^{2}/(\sqrt{2}\log\frac{c+b}{a})^{2}$
that $\varepsilon=\sqrt{2}\log\left(\frac{c+b}{a}\right)\sqrt{\frac{t}{n}}$.
Therefore with probability at least $1-\mathrm{e}^{-t}$,

$\left\lVert\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{g}(X_{i})}{\tilde{f}(X_{i})}-{\operatorname*{{\mathrm{\mathbf{E}}}}}_{f}\log\frac{\tilde{g}}{\tilde{f}}\right\rVert_{\tilde{\mathcal{C}}}\leq\operatorname*{{\mathrm{\mathbf{E}}}}\left\lVert\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{g}(X_{i})}{\tilde{f}(X_{i})}-{\operatorname*{{\mathrm{\mathbf{E}}}}}_{f}\log\frac{\tilde{g}}{\tilde{f}}\right\rVert_{\tilde{\mathcal{C}}}+\sqrt{2}\log\left(\frac{c+b}{a}\right)\sqrt{\frac{t}{n}}.$

Let $(\varepsilon_{i})_{i\in[n]}$ be i.i.d. Rademacher random variables,
independent of $(X_{i})_{i\in[n]}$. By Lemma 22,

$\operatorname*{{\mathrm{\mathbf{E}}}}\left\lVert\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{g}(X_{i})}{\tilde{f}(X_{i})}-{\operatorname*{{\mathrm{\mathbf{E}}}}}_{f}\log\frac{\tilde{g}}{\tilde{f}}\right\rVert_{\tilde{\mathcal{C}}}\leq
2\operatorname*{{\mathrm{\mathbf{E}}}}\left\lVert\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{g}(X_{i})}{\tilde{f}(X_{i})}\varepsilon_{i}\right\rVert_{\tilde{\mathcal{C}}}.$

By combining the results above, the following inequality holds with
probability at least $1-\mathrm{e}^{-t}$

$\left\lVert\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{g}(X_{i})}{\tilde{f}(X_{i})}-{\operatorname*{{\mathrm{\mathbf{E}}}}}_{f}\log\frac{\tilde{g}}{\tilde{f}}\right\rVert_{\tilde{\mathcal{C}}}\leq
2\operatorname*{{\mathrm{\mathbf{E}}}}\left\lVert\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{g}(X_{i})}{\tilde{f}(X_{i})}\varepsilon_{i}\right\rVert_{\tilde{\mathcal{C}}}+\sqrt{2}\log\left(\frac{c+b}{a}\right)\sqrt{\frac{t}{n}}.$

Now let $p_{i}=\frac{\tilde{g}(X_{i})}{\tilde{f}(X_{i})}-1$, such that
$\frac{a}{c+b}\leq p_{i}+1\leq\frac{c+b}{a}$ holds for all $i\in[n]$.
Additionally, let $\eta(p)=\log(p+1)$ so that $\eta(0)=0$ and note that for
$p\in\left[\frac{a}{c+b}-1,\frac{c+b}{a}-1\right]$, the derivative of
$\eta(p)$ is maximal at $p^{*}=\frac{a}{c+b}-1$, and equal to
$\eta^{{{}^{\prime}}}(p^{*})=(c+b)/a$. Therefore, $\frac{a}{b+c}\log(p+1)$ is
$1$-Lipschitz. By Lemma 20 applied to $\eta(p)$,

$\displaystyle
2\operatorname*{{\mathrm{\mathbf{E}}}}\left\lVert\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{g}(X_{i})}{\tilde{f}(X_{i})}\varepsilon_{i}\right\rVert_{\tilde{\mathcal{C}}}$
$\displaystyle=2\operatorname*{{\mathrm{\mathbf{E}}}}\left\lVert\frac{1}{n}\sum_{i=1}^{n}\eta(p_{i})\varepsilon_{i}\right\rVert_{\tilde{\mathcal{C}}}$
$\displaystyle\leq\frac{4(c+b)}{a}\operatorname*{{\mathrm{\mathbf{E}}}}\left\lVert\frac{1}{n}\sum_{i=1}^{n}\frac{\tilde{g}(X_{i})}{\tilde{f}(X_{i})}\varepsilon_{i}-\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\right\rVert_{\tilde{\mathcal{C}}}$
$\displaystyle\leq\frac{4(c+b)}{a}\operatorname*{{\mathrm{\mathbf{E}}}}\left\lVert\frac{1}{n}\sum_{i=1}^{n}\frac{\tilde{g}(X_{i})}{\tilde{f}(X_{i})}\varepsilon_{i}\right\rVert_{\tilde{\mathcal{C}}}+\frac{4(c+b)}{a}{\operatorname*{{\mathrm{\mathbf{E}}}}}_{\varepsilon}\left\lvert\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\right\rvert$
$\displaystyle\leq\frac{4(c+b)}{a}\operatorname*{{\mathrm{\mathbf{E}}}}\left\lVert\frac{1}{n}\sum_{i=1}^{n}\frac{\tilde{g}(X_{i})}{\tilde{f}(X_{i})}\varepsilon_{i}\right\rVert_{\tilde{\mathcal{C}}}+\frac{4(c+b)}{a}\frac{1}{\sqrt{n}},$

where the final inequality follows from the following result, proved in
Haagerup (1981):

${\operatorname*{{\mathrm{\mathbf{E}}}}}_{\varepsilon}\left\lvert\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\right\rvert\leq\left({\operatorname*{{\mathrm{\mathbf{E}}}}}_{\varepsilon}\left\\{\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\right\\}^{2}\right)^{1/2}=\frac{1}{\sqrt{n}}.$

Now, let $\xi_{i}(\tilde{g}_{i})=a\cdot{\tilde{g}(X_{i})}/{\tilde{f}(X_{i})}$,
and note that

$\lvert\xi_{i}(u_{i})-\xi_{i}(v_{i})\rvert=\frac{a}{\lvert\tilde{f}(X_{i})\rvert}\lvert
u(X_{i})-v(X_{i})\rvert\leq\lvert u(X_{i})-v(X_{i})\rvert.$

By again applying Lemma 20, we have

$\displaystyle\frac{4(c+b)}{a}\operatorname*{{\mathrm{\mathbf{E}}}}\left\lVert\frac{1}{n}\sum_{i=1}^{n}\frac{\tilde{g}(X_{i})}{\tilde{f}(X_{i})}\varepsilon_{i}\right\rVert_{\tilde{\mathcal{C}}}$
$\displaystyle\leq\frac{8(c+b)}{a^{2}}\operatorname*{{\mathrm{\mathbf{E}}}}\left\lVert\frac{1}{n}\sum_{i=1}^{n}\tilde{g}(X_{i})\varepsilon_{i}\right\rVert_{\tilde{\mathcal{C}}}$
$\displaystyle\leq\frac{8(c+b)}{a^{2}}\operatorname*{{\mathrm{\mathbf{E}}}}\left\lVert\frac{1}{n}\sum_{i=1}^{n}g(X_{i})\varepsilon_{i}\right\rVert_{\mathcal{C}}+\frac{8(c+b)}{a^{2}}\operatorname*{{\mathrm{\mathbf{E}}}}\left\lvert\frac{1}{n}\sum_{i=1}^{n}h(X_{i})\varepsilon_{i}\right\rvert$
$\displaystyle\leq\frac{8(c+b)}{a^{2}}\operatorname*{{\mathrm{\mathbf{E}}}}\left\lVert\frac{1}{n}\sum_{i=1}^{n}g(X_{i})\varepsilon_{i}\right\rVert_{\mathcal{C}}+\frac{8(c+b)}{a^{2}}\frac{b}{\sqrt{n}}.$

Applying Lemmas 8 and 23, the following inequality holds for some constant
$K>0$:

${\operatorname*{{\mathrm{\mathbf{E}}}}}_{\varepsilon}\sup_{g\in\mathcal{C}}\left\lvert\frac{1}{n}\sum_{i=1}^{n}g(X_{i})\varepsilon_{i}\right\rvert={\operatorname*{{\mathrm{\mathbf{E}}}}}_{\varepsilon}\sup_{\theta\in\Theta}\left\lvert\frac{1}{n}\sum_{i=1}^{n}\varphi(X_{i};\theta)\varepsilon_{i}\right\rvert\leq\frac{K}{\sqrt{n}}\operatorname*{{\mathrm{\mathbf{E}}}}\int_{0}^{c}\log^{1/2}N(\mathcal{P},\varepsilon,d_{n,x})\mathrm{d}\varepsilon,$
(13)

and combining the results together, the following inequality holds with
probability at least $1-\mathrm{e}^{-t}$:

$\displaystyle\left\lVert\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{g}(X_{i})}{\tilde{f}(X_{i})}-{\operatorname*{{\mathrm{\mathbf{E}}}}}_{f}\log\frac{\tilde{g}}{\tilde{f}}\right\rVert$
$\displaystyle\qquad\leq\frac{8(c+b)K}{a^{2}\sqrt{n}}\operatorname*{{\mathrm{\mathbf{E}}}}\int_{0}^{c}\log^{1/2}N(\mathcal{P},\varepsilon,d_{n,x})\mathrm{d}\varepsilon+\frac{(8b+4a)(c+b)}{a^{2}\sqrt{n}}+\sqrt{2}\log\left(\frac{c+b}{a}\right)\sqrt{\frac{t}{n}},$
$\displaystyle\qquad=\frac{w_{1}}{\sqrt{n}}\operatorname*{{\mathrm{\mathbf{E}}}}\int_{0}^{c}\log^{1/2}N(\mathcal{P},\varepsilon,d_{n,x})\mathrm{d}\varepsilon+\frac{w_{2}}{\sqrt{n}}+w_{3}\sqrt{\frac{t}{n}},$

where $w_{1}$, $w_{2}$, and $w_{3}$ are constants that each depend on some or
all of $a$, $b$, and $c$.

######  Remark 13.

From Lemma 23 we have that
$\sigma^{2}_{n}\coloneqq\sup_{f\in\mathscr{F}}P_{n}f^{2}$. To make explicit
why $2\sigma_{n}=\left(\sup_{g\in\mathcal{C}}P_{n}g^{2}\right)^{1/2}=2c$, let
$\mathscr{F}=\mathcal{C}$ and observe

$\sigma^{2}_{n}=\sup_{g\in\mathcal{C}}P_{n}g^{2}=\sup_{g\in\mathcal{C}}\frac{1}{n}\sum_{i=1}^{n}g(X_{i})^{2}\leq\frac{1}{n}\sum_{i=1}^{n}c^{2}=c^{2}.$

Since our basis functions $\varphi(\cdot,\theta)$ are bounded by $c$,
everything greater than $c$ will have value $0$ and hence the change from $2c$
to $c$ is inconsequential. However, it can also be motivated by the fact that
$\varphi(\cdot,\theta)$ are positive functions.

As highlighted in Remark 12, the full result of Theorem 11 relies on the
empirical $L_{2}$ distances $d_{n,x}$ and $d_{n,y}$. In the result of Theorem
9, we make use of the following result to bound $d_{n,x}$ and $d_{n,y}$.

######  Proposition 14.

By combining Lemmas 16 and 17, the following inequality holds:

$\log N(\mathcal{P},\varepsilon,\operatorname*{\lVert\,\cdot\,\rVert})\leq\log
N_{[]}(\mathcal{P},\varepsilon,\operatorname*{\lVert\,\cdot\,\rVert})\leq\log
N(\mathcal{P},\varepsilon/2,{\operatorname*{\lVert\,\cdot\,\rVert}}_{\infty}),$

where $N_{[]}(\mathcal{P},\varepsilon,\operatorname*{\lVert\,\cdot\,\rVert})$
is the $\varepsilon$-bracketing number of $\mathcal{P}$. Therefore, we have
that

$\log N(\mathcal{P},\varepsilon,d_{n,x})\leq\log
N(\mathcal{P},\varepsilon/2,{\operatorname*{\lVert\,\cdot\,\rVert}}_{\infty}),$

and

$\log N(\mathcal{P},\varepsilon,d_{n,y})\leq\log
N(\mathcal{P},\varepsilon/2,{\operatorname*{\lVert\,\cdot\,\rVert}}_{\infty}).$

With this result, we can now prove Theorem 9.

Proof. [of Theorem 9] The notation is the same as in the proof of Theorem 11.
The values of the constants may change from line to line.

$\displaystyle\mathrm{KL}_{h}\left(f\,||\,f_{k,n}\right)-\mathrm{KL}_{h}\left(f\,||\,f_{k}\right)$
$\displaystyle\quad={\operatorname*{{\mathrm{\mathbf{E}}}}}_{f}\log\frac{\tilde{f}}{\tilde{f}_{k,n}}+{\operatorname*{{\mathrm{\mathbf{E}}}}}_{h}\log\frac{\tilde{f}}{\tilde{f}_{k,n}}-{\operatorname*{{\mathrm{\mathbf{E}}}}}_{f}\log\frac{\tilde{f}}{\tilde{f}_{k}}-{\operatorname*{{\mathrm{\mathbf{E}}}}}_{h}\log\frac{\tilde{f}}{\tilde{f}_{k}}$
$\displaystyle\quad={\operatorname*{{\mathrm{\mathbf{E}}}}}_{f}\log\frac{\tilde{f}}{\tilde{f}_{k,n}}-\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}(X_{i})}{\tilde{f}_{k,n}(X_{i})}+\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}(X_{i})}{\tilde{f}_{k,n}(X_{i})}$
$\displaystyle\quad\qquad+{\operatorname*{{\mathrm{\mathbf{E}}}}}_{h}\log\frac{\tilde{f}}{\tilde{f}_{k,n}}-\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}(Y_{i})}{\tilde{f}_{k,n}(Y_{i})}+\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}(Y_{i})}{\tilde{f}_{k,n}(Y_{i})}$
$\displaystyle\quad\qquad-{\operatorname*{{\mathrm{\mathbf{E}}}}}_{f}\log\frac{\tilde{f}}{\tilde{f}_{k}}+\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}(X_{i})}{\tilde{f}_{k}(X_{i})}-\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}(X_{i})}{\tilde{f}_{k}(X_{i})}$
$\displaystyle\quad\qquad-{\operatorname*{{\mathrm{\mathbf{E}}}}}_{h}\log\frac{\tilde{f}}{\tilde{f}_{k}}+\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}(Y_{i})}{\tilde{f}_{k}(Y_{i})}-\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}(Y_{i})}{\tilde{f}_{k}(Y_{i})}$
$\displaystyle\quad=\left({\operatorname*{{\mathrm{\mathbf{E}}}}}_{f}\log\frac{\tilde{f}}{\tilde{f}_{k,n}}-\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}(X_{i})}{\tilde{f}_{k,n}(X_{i})}\right)+\left({\operatorname*{{\mathrm{\mathbf{E}}}}}_{h}\log\frac{\tilde{f}}{\tilde{f}_{k,n}}-\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}(Y_{i})}{\tilde{f}_{k,n}(Y_{i})}\right)$
$\displaystyle\quad\quad+\left(\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}(X_{i})}{\tilde{f}_{k}(X_{i})}-{\operatorname*{{\mathrm{\mathbf{E}}}}}_{f}\log\frac{\tilde{f}}{\tilde{f}_{k}}\right)+\left(\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}(Y_{i})}{\tilde{f}_{k}(Y_{i})}-{\operatorname*{{\mathrm{\mathbf{E}}}}}_{h}\log\frac{\tilde{f}}{\tilde{f}_{k}}\right)$
$\displaystyle\quad\quad+\left(\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}(X_{i})}{\tilde{f}_{k,n}(X_{i})}-\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}(X_{i})}{\tilde{f}_{k}(X_{i})}\right)+\left(\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}(Y_{i})}{\tilde{f}_{k,n}(Y_{i})}-\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}(Y_{i})}{\tilde{f}_{k}(Y_{i})}\right)$
$\displaystyle\quad\leq
2\sup_{\tilde{g}\in\tilde{\mathcal{C}}}\left\lvert\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{g}(X_{i})}{\tilde{f}(X_{i})}-{\operatorname*{{\mathrm{\mathbf{E}}}}}_{f}\log\frac{\tilde{g}}{\tilde{f}}\right\rvert+2\sup_{\tilde{g}\in\tilde{\mathcal{C}}}\left\lvert\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{g}(Y_{i})}{\tilde{f}(Y_{i})}-{\operatorname*{{\mathrm{\mathbf{E}}}}}_{h}\log\frac{\tilde{g}}{\tilde{f}}\right\rvert$
$\displaystyle\quad\quad+\left(\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}(X_{i})}{\tilde{f}_{k,n}(X_{i})}-\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}(X_{i})}{\tilde{f}_{k}(X_{i})}\right)+\left(\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}(Y_{i})}{\tilde{f}_{k,n}(Y_{i})}-\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}(Y_{i})}{\tilde{f}_{k}(Y_{i})}\right)$
$\displaystyle\quad\leq
2\operatorname*{{\mathrm{\mathbf{E}}}}\left\\{\frac{w^{x}_{1}}{\sqrt{n}}\int_{0}^{c}\log^{1/2}N(\mathcal{P},\varepsilon,d_{n,x})\mathrm{d}\varepsilon\right\\}+\frac{w^{x}_{2}}{\sqrt{n}}+w^{x}_{3}\sqrt{\frac{t}{n}}+\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}_{k}(X_{i})}{\tilde{f}_{k,n}(X_{i})}$
$\displaystyle\quad\qquad+2\operatorname*{{\mathrm{\mathbf{E}}}}\left\\{\frac{w^{y}_{1}}{\sqrt{n}}\int_{0}^{c}\log^{1/2}N(\mathcal{P},\varepsilon,d_{n,y})\mathrm{d}\varepsilon\right\\}+\frac{w^{y}_{2}}{\sqrt{n}}+w^{y}_{3}\sqrt{\frac{t}{n}}+\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}_{k}(Y_{i})}{\tilde{f}_{k,n}(Y_{i})}$
$\displaystyle\quad\leq\frac{w_{1}}{\sqrt{n}}\int_{0}^{c}\log^{1/2}N(\mathcal{P},\varepsilon/2,{\operatorname*{\lVert\,\cdot\,\rVert}}_{\infty})\mathrm{d}\varepsilon+\frac{w_{2}}{\sqrt{n}}+w_{3}\sqrt{\frac{t}{n}}$
$\displaystyle\quad\qquad+\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}_{k}(X_{i})}{\tilde{f}_{k,n}(X_{i})}+\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}_{k}(Y_{i})}{\tilde{f}_{k,n}(Y_{i})},$

with probability at least $1-\mathrm{e}^{-t}$, by Theorem 11. Now, we can use
(11) from Proposition 6 applied to the target density $f_{k}$, obtaining the
following:

$\displaystyle\mathrm{KL}_{h}\left(f_{k}\,||\,f_{k,n}\right)$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}_{k}(X_{i})}{\tilde{f}_{k,n}(X_{i})}+\frac{1}{n}\sum_{i=1}^{n}\log\frac{\tilde{f}_{k}(Y_{i})}{\tilde{f}_{k,n}(Y_{i})}$
$\displaystyle\leq\frac{4a^{-2}c^{2}}{k+2}+\inf_{p\in\mathcal{C}}\mathrm{KL}_{h}\left(f_{k}\,||\,p\right).$

Since by definition we have that $f_{k}\in\mathcal{C}$,
$\inf_{p\in\mathcal{C}}\mathrm{KL}_{h}\left(f_{k}\,||\,p\right)=0$, and so
with probability at least $1-\mathrm{e}^{-t}$ we have:

$\displaystyle\mathrm{KL}_{h}\left(f\,||\,f_{k,n}\right)$
$\displaystyle-\mathrm{KL}_{h}\left(f\,||\,f_{k}\right)$
$\displaystyle\quad\leq\frac{w_{1}}{\sqrt{n}}\int_{0}^{c}\log^{1/2}N(\mathcal{P},\varepsilon/2,{\operatorname*{\lVert\,\cdot\,\rVert}}_{\infty})\mathrm{d}\varepsilon+\frac{w_{2}}{\sqrt{n}}+w_{3}\sqrt{\frac{t}{n}}+\frac{w_{4}}{k+2}.$
(14)

We can write the overall error as the sum of the approximation and estimation
errors as follows. The former is bounded by (10), and the latter is bounded as
above in (14). Therefore, with probability at least $1-\mathrm{e}^{-t}$,

$\displaystyle\mathrm{KL}_{h}\left(f\,||\,f_{k,n}\right)-\mathrm{KL}_{h}\left(f\,||\,\mathcal{C}\right)$
$\displaystyle=[\mathrm{KL}_{h}\left(f\,||\,f_{k}\right)-\mathrm{KL}_{h}\left(f\,||\,\mathcal{C}\right)]+[\mathrm{KL}_{h}\left(f\,||\,f_{k,n}\right)-\mathrm{KL}_{h}\left(f\,||\,f_{k}\right)]$
$\displaystyle\leq\frac{w_{4}}{k+2}+\frac{w_{1}}{\sqrt{n}}\int_{0}^{c}\log^{1/2}N(\mathcal{P},\varepsilon/2,{\operatorname*{\lVert\,\cdot\,\rVert}}_{\infty})\mathrm{d}\varepsilon+\frac{w_{2}}{\sqrt{n}}+w_{3}\sqrt{\frac{t}{n}}.$

As in Rakhlin et al. (2005), we rewrite the above probabilistic statement as a
statement in terms of expectations. To this end, let

$\mathcal{A}\coloneqq\frac{w_{4}}{k+2}+\frac{w_{1}}{\sqrt{n}}\int_{0}^{c}\log^{1/2}N(\mathcal{P},\varepsilon/2,{\operatorname*{\lVert\,\cdot\,\rVert}}_{\infty})\mathrm{d}\varepsilon+\frac{w_{2}}{\sqrt{n}},$

and
$\mathcal{Z}\coloneqq\mathrm{KL}_{h}\left(f\,||\,f_{k,n}\right)-\mathrm{KL}_{h}\left(f\,||\,\mathcal{C}\right)$.
We have shown
${\mathrm{\mathbf{P}}}\left(\mathcal{Z}\geq\mathcal{A}+w_{3}\sqrt{\frac{t}{n}}\right)\leq\mathrm{e}^{-t}$.
Since $\mathcal{Z}\geq 0$,

$\operatorname*{{\mathrm{\mathbf{E}}}}\\{\mathcal{Z}\\}=\int^{\mathcal{A}}_{0}{\mathrm{\mathbf{P}}}(\mathcal{Z}>s)\mathrm{d}s+\int^{\infty}_{\mathcal{A}}{\mathrm{\mathbf{P}}}(\mathcal{Z}>s)\mathrm{d}s\leq\mathcal{A}+\int_{0}^{\infty}{\mathrm{\mathbf{P}}}(\mathcal{Z}>\mathcal{A}+s)\mathrm{d}s.$

Setting $s=w_{3}\sqrt{\frac{t}{n}}$, we have $t=w_{5}ns^{2}$ and
$\operatorname*{{\mathrm{\mathbf{E}}}}\\{\mathcal{Z}\\}\leq\mathcal{A}+\int_{0}^{\infty}e^{-w_{5}ns^{2}}\mathrm{d}s\leq\mathcal{A}+\frac{w}{\sqrt{n}}$.
Hence,

${\operatorname*{{\mathrm{\mathbf{E}}}}}\left\\{\mathrm{KL}_{h}\left(f\,||\,f_{k,n}\right)\right\\}-\mathrm{KL}_{h}\left(f\,||\,\mathcal{C}\right)\leq\frac{c_{1}}{k+2}+\frac{c_{2}}{\sqrt{n}}\int_{0}^{c}\log^{1/2}N\left(\mathcal{P},\varepsilon/2,{\operatorname*{\lVert\,\cdot\,\rVert}}_{\infty}\right)\mathrm{d}\varepsilon+\frac{c_{3}}{\sqrt{n}},$

where $c_{1}$, $c_{2}$, and $c_{3}$ are constants that depend on some or all
of $a$, $b$, and $c$.

######  Remark 15.

The approximation error characterises the suitability of the class
$\mathcal{C}$, i.e., how well functions in $\mathcal{C}$ are able to estimate
a target $f$ which does not necessarily lie in $\mathcal{C}$. The estimation
error characterises the error arising from the estimation of the target $f$ on
the basis of the finite sample of size $n$.

Proof. [of Corollary 10] Let $\mathcal{X}$ and $\Theta$ be compact and assume
the Lipshitz condition given in (12). If $\varphi(x;\cdot)$ is continuously
differentiable, then

$\displaystyle\left|\varphi\left(x;\theta\right)-\varphi\left(x;\tau\right)\right|$
$\displaystyle\leq\sum_{k=1}^{d}\left|\frac{\partial\varphi\left(x;\cdot\right)}{\partial\theta_{k}}\left(\theta_{k}^{*}\right)\right|\left|\theta_{k}-\tau_{k}\right|$
$\displaystyle\leq\sup_{\theta^{*}\in\Theta}\left\|\frac{\partial\varphi\left(x;\cdot\right)}{\partial\theta}\left(\theta^{*}\right)\right\|_{1}\left\|\theta-\tau\right\|_{1}.$

Setting

$\varPhi\left(x\right)=\sup_{\theta^{*}\in\Theta}\left\|\frac{\partial\varphi\left(x;\cdot\right)}{\partial\theta}\left(\theta^{*}\right)\right\|_{1},$

we have $\lVert\varPhi\rVert_{\infty}<\infty$. From Lemma 18, we obtain the
fact that

$\log
N_{[]}\left(\mathcal{P},2\varepsilon\lVert\varPhi\rVert_{\infty},{\operatorname*{\lVert\,\cdot\,\rVert}}_{\infty}\right)\leq\log
N\left(\Theta,\varepsilon,{\operatorname*{\lVert\,\cdot\,\rVert}}_{\infty}\right),$

which by the change of variable
$\delta=2\varepsilon\lVert\varPhi\rVert_{\infty}\implies\varepsilon=\delta/2\lVert\varPhi\rVert_{\infty}$
implies

$\log
N_{[]}\left(\mathcal{P},\varepsilon/2,{\operatorname*{\lVert\,\cdot\,\rVert}}_{\infty}\right)\leq\log
N\left(\Theta,\frac{\varepsilon}{4\lVert\varPhi\rVert_{\infty}},{\operatorname*{\lVert\,\cdot\,\rVert}}_{1}\right).$

Since $\Theta\subset\mathbb{R}^{d}$, using the fact that a Euclidean set of
radius $r$ has covering number

$N\left(r,\varepsilon\right)\leq\left(\frac{3r}{\varepsilon}\right)^{d},$

we have

$\log
N\left(\Theta,\frac{\varepsilon}{4\lVert\varPhi\rVert_{\infty}},{\operatorname*{\lVert\,\cdot\,\rVert}}_{1}\right)\leq
d\log\left[\frac{12\lVert\varPhi\rVert_{\infty}\mathrm{diam}\left(\Theta\right)}{\varepsilon}\right].$

So

$\int_{0}^{c}\sqrt{\log
N\left(\Theta,\frac{\varepsilon}{4\lVert\varPhi\rVert_{\infty}},{\operatorname*{\lVert\,\cdot\,\rVert}}_{1}\right)}\mathrm{d}\varepsilon\leq\int_{0}^{c}\sqrt{d\log\left[\frac{12\lVert\varPhi\rVert_{\infty}\mathrm{diam}\left(\Theta\right)}{\varepsilon}\right]}\mathrm{d}\varepsilon,$

and since $c<\infty$, the integral is finite, as required.

##  6 Numerical experiments

In this section, we discuss the computability and computation of
$\textrm{KL}_{h}$ estimation problems and provide empirical evidence towards
the rates obtained in Theorem 9. Namely, we seek to develop a methodology for
computing $h$-MLLEs, and to use numerical experiments to demonstrate that the
sequence of expected $h$-lifted KL divergences between some density $f$ and a
sequence of $k$-component mixture densities from a suitable class
$\mathcal{P}$, estimated using $n$ observations does indeed decrease at rates
proportional to $1/k$ and $1/\sqrt{n}$, as $k$ and $n$ increase.

###  6.1 Minorization–Maximization algorithm

One solution for computing problems of kind (4) is to employ an MM algorithm.
To do so, we first write the objective of (4) as

$L_{h,n}\left(\psi_{k}\right)=\frac{1}{n}\sum_{i=1}^{n}\left(\log\left\\{\sum_{j=1}^{k}\pi_{j}\varphi\left(X_{i};\theta_{j}\right)+h\left(X_{i}\right)\right\\}+\log\left\\{\sum_{j=1}^{k}\pi_{j}\varphi\left(Y_{i};\theta_{j}\right)+h\left(Y_{i}\right)\right\\}\right),$

where $\psi_{k}\in\Psi_{k}=\mathcal{S}_{k}\times\Theta^{k}$. We then require
the definition of a minorizer $Q_{n}$ for $L_{h,n}$ on the space $\Psi_{k}$,
where $Q_{n}:\Psi_{k}\times\Psi_{k}\rightarrow\mathbb{R}$ is a function with
the properties:

  1. (i)

$Q_{n}\left(\psi_{k},\psi_{k}\right)=L_{h,n}\left(\psi_{k}\right)$, and

  2. (ii)

$Q_{n}\left(\psi_{k},\chi_{k}\right)\leq L_{h,n}\left(\psi_{k}\right)$,

for each $\psi_{k},\chi_{k}\in\Psi_{k}$. In this context, given a fixed
$\chi_{k}$, the minorizer $Q_{n}\left(\cdot,\chi_{k}\right)$ should possess
properties that simplify it compared to the original objective $L_{h,n}$.
These properties should make the minorizer more tractable and might include
features such as parametric separability, differentiability, convexity, among
others.

In order to build an appropriate minorizer for $L_{h,n}$, we make use of the
so-called Jensen’s inequality minorizer, as detailed in Lange (2016, Sec.
4.3), applied to the logarithm function. This construction results in a
minorizer of the form

$\displaystyle Q_{n}\left(\psi_{k},\chi_{k}\right)$ $\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{k}\left\\{\tau_{j}\left(X_{i};\chi_{k}\right)\log\pi_{j}+\tau_{j}\left(X_{i};\chi_{k}\right)\log\varphi\left(X_{i};\theta_{j}\right)\right\\}$
$\displaystyle+\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{k}\left\\{\tau_{j}\left(Y_{i};\chi_{k}\right)\log\pi_{j}+\tau_{j}\left(Y_{i};\chi_{k}\right)\log\varphi\left(Y_{i};\theta_{j}\right)\right\\}$
$\displaystyle+\frac{1}{n}\sum_{i=1}^{n}\left\\{\gamma\left(X_{i};\chi_{k}\right)\log
h\left(X_{i}\right)+\gamma\left(Y_{i};\chi_{k}\right)\log
h\left(Y_{i}\right)\right\\}$
$\displaystyle-\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{k}\left\\{\tau_{j}\left(X_{i};\chi_{k}\right)\log\tau_{j}\left(X_{i};\chi_{k}\right)+\tau_{j}\left(Y_{i};\chi_{k}\right)\log\tau_{j}\left(Y_{i};\chi_{k}\right)\right\\}$
$\displaystyle-\frac{1}{n}\sum_{i=1}^{n}\left\\{\gamma\left(X_{i};\chi_{k}\right)\log\gamma\left(X_{i};\chi_{k}\right)+\gamma\left(Y_{i};\chi_{k}\right)\log\gamma\left(Y_{i};\chi_{k}\right)\right\\}$

where

$\gamma\left(X_{i};\psi_{k}\right)=h\left(X_{i}\right)/\left\\{\sum_{j=1}^{k}\pi_{j}\varphi\left(X_{i};\theta_{j}\right)+h\left(X_{i}\right)\right\\}$

and

$\tau_{j}\left(X_{i};\psi_{k}\right)=\pi_{j}\varphi\left(X_{i};\theta_{j}\right)/\left\\{\sum_{j=1}^{k}\pi_{j}\varphi\left(X_{i};\theta_{j}\right)+h\left(X_{i}\right)\right\\}.$

Observe that $Q_{n}\left(\cdot,\chi_{k}\right)$ now takes the form of a sum-
of-logarithms, as opposed to the more challenging log-of-sum form of
$L_{h,n}$. This change produces a functional separation of the elements of
$\psi_{k}$.

Using $Q_{n}$, we then define the MM algorithm via the parameter sequence
$\left(\psi_{k}^{\left(s\right)}\right)_{s\in\mathbb{N}}$, where

$\psi_{k}^{\left(s\right)}=\underset{\psi_{k}\in\Psi_{k}}{\operatorname*{arg\,max\,}}~{}Q_{n}\left(\psi_{k},\psi_{k}^{\left(s-1\right)}\right),$
(15)

for each $s>0$, and where $\psi_{k}^{\left(0\right)}$ is user chosen and is
typically referred to as the initialization of the algorithm. Notice that for
each $s$, (15) is a simpler optimization problem than (4). Writing
$\psi_{k}^{\left(s\right)}=\left(\pi_{1}^{\left(s\right)},\dots,\pi_{k}^{\left(s\right)},\theta_{1}^{\left(s\right)},\dots,\theta_{k}^{\left(s\right)}\right)$,
we observe that (15) simplifies to the separated expressions:

$\pi_{j}^{\left(s\right)}=\frac{\sum_{i=1}^{n}\left\\{\tau_{j}\left(X_{i};\psi_{k}^{\left(s-1\right)}\right)+\tau_{j}\left(Y_{i};\psi_{k}^{\left(s-1\right)}\right)\right\\}}{\sum_{i=1}^{n}\sum_{l=1}^{k}\left\\{\tau_{l}\left(X_{i};\psi_{k}^{\left(s-1\right)}\right)+\tau_{l}\left(Y_{i};\psi_{k}^{\left(s-1\right)}\right)\right\\}}$

and

$\theta_{j}^{\left(s\right)}=\underset{\theta_{j}\in\Theta}{\operatorname*{arg\,max\,}}\frac{1}{n}\sum_{i=1}^{n}\left\\{\tau_{j}\left(X_{i};\psi_{k}^{\left(s-1\right)}\right)\log\varphi\left(X_{i};\theta_{j}\right)+\tau_{j}\left(Y_{i};\psi_{k}^{\left(s-1\right)}\right)\log\varphi\left(Y_{i};\theta_{j}\right)\right\\},$

for each $j\in\left[k\right]$.

A noteworthy property of the MM sequence
$\left(\psi_{k}^{\left(s\right)}\right)_{s\in\mathbb{N}}$ is that it generates
an increasing sequence of objective values, due to the chain of inequalities

$L_{h,n}\left(\psi_{k}^{\left(s-1\right)}\right)=Q_{n}\left(\psi_{k}^{\left(s-1\right)},\psi_{k}^{\left(s-1\right)}\right)\leq
Q_{n}\left(\psi_{k}^{\left(s\right)},\psi_{k}^{\left(s-1\right)}\right)\leq
L_{h,n}\left(\psi_{k}^{\left(s\right)}\right),$

where the equality is due to property (i) of $Q_{n}$, the first in equality is
due to the definition of $\psi_{k}^{\left(s\right)}$, and the second
inequality is due to property (ii) of $Q_{n}$. This provides a kind of
stability and regularity to the sequence
$\left(L_{h,n}\left(\psi_{k}^{\left(s\right)}\right)\right)_{s\in\mathbb{N}}$.

Of course, we can provide stronger guarantees under additional assumptions.
Namely, assume that (iii) $\Psi_{k}\subset\varPsi_{k}$, where $\varPsi_{k}$ is
an open set in a finite dimensional Euclidean space on which $L_{h,n}$ and
$Q_{n}\left(\cdot,\chi_{k}\right)$ is differentiable, for each
$\chi_{k}\in\Psi_{k}$. Then, under assumptions (i)–(iii) regarding $L_{h,n}$
and $Q_{n}$, and due to the compactness of $\Psi_{k}$ and the continuity of
$Q_{n}$ on $\Psi_{k}\times\Psi_{k}$, Razaviyayn et al. (2013, Cor. 1) implies
that $\left(\psi_{k}^{\left(s\right)}\right)_{s\in\mathbb{N}}$ converges to
the set of stationary points of $L_{h,n}$ in the sense that

$\lim_{s\rightarrow\infty}\inf_{\psi_{k}^{*}\in\Psi_{k}^{*}}\left\|\psi_{k}^{\left(s\right)}-\psi_{k}^{*}\right\|_{2}=0$

where,

$\Psi_{k}^{*}=\left\\{\psi_{k}^{*}\in\Psi_{k}:\left.\frac{\partial
L_{h,n}}{\partial\psi_{k}}\right|_{\psi_{k}=\psi_{k}^{*}}=0\right\\}.$

More concisely, we say that the sequence
$\left(\psi_{k}^{\left(s\right)}\right)_{s\in\mathbb{N}}$ globally converges
to the set of stationary points $\Psi_{k}^{*}$.

###  6.2 Experimental setup

Towards the task of demonstrating empirical evidence of the rates in Theorem
9, we consider the family of beta distributions on the unit interval
$\mathcal{X}=\left[0,1\right]$ as our base class (i.e., (6)) to estimate a
pair of target densities

$f_{1}\left(x\right)=\frac{1}{2}\chi_{\left[0,2/5\right]}\left(x\right)+\frac{1}{2}\chi_{\left[3/5,1\right]}\left(x\right),$

and

$f_{2}\left(x\right)=\chi_{\left[0,1\right]}\left(x\right)\begin{cases}2-4x&\text{if
}x\leq 1/2,\\\ -2+4x&\text{if }x>1/2,\end{cases}$

where $\chi_{\mathcal{A}}$ is the characteristic function that takes value $1$
if $x\in\mathcal{A}$ and $0$, otherwise. Note that neither $f_{1}$ nor $f_{2}$
are in $\mathcal{C}$. In particular, $f_{1}\left(x\right)=0$ when
$x\in\left(\nicefrac{{2}}{{5}},\nicefrac{{3}}{{5}}\right)$, and $f_{2}(x)=0$
when $x=1/2$, and hence neither densities are bounded away from 0, on
$\mathcal{X}$. Thus, the theory of Rakhlin et al. (2005) cannot be applied to
provide bounds for the expected KL divergence between MLEs of beta mixtures
and the pair of targets. We visualize $f_{1}$ and $f_{2}$ in Figure 1.

Figure 1: Simulation target densities $f_{1}$ (solid line) and $f_{2}$ (dashed
line).

To observe the rate of decrease of the $h$-lifted KL divergence between the
targets and respective sequences of $h$-MLLEs, we conduct two experiments E1
and E2. In E1, our target density is set to $f_{1}$ and
$h_{1}=\beta\left(\cdot;1/2,1/2\right)$. For each
$n\in\left\\{2^{10},\dots,2^{15}\right\\}$ and
$k\in\left\\{2,\dots,8\right\\}$, we independently simulate $\mathbf{X}_{n}$
and $\mathbf{Y}_{n}$ with each $X_{i}$ and $Y_{i}$ ($i\in\left[n\right]$),
i.i.d., from the distributions characterized by $f_{1}$ and $h_{1}$,
respectively. In E2, we target $f_{2}$ with $h$-MLLEs over the same ranges of
$k$ and $n$, but with $h_{2}=\beta\left(\cdot;1,1\right)$–the density of the
uniform distribution. For each $k$ and $n$, we simulate $\mathbf{X}_{n}$ and
$\mathbf{Y}_{n}$ respectively from distributions characterized by $f_{2}$ and
$h_{2}$.

In both experiments, we simulate $r=50$ replicates of each
$\left(k,n\right)$-scenario and compute the corresponding $h$-MLLEs,
$\left(f_{k,n,l}\right)_{l\in[r]}$, using the previously described MM
algorithm. For each $l\in\left[r\right]$, we compute the corresponding
negative log $h$-lifted likelihood between the target $f$ and $f_{k,n,l}$:

$K_{k,n,l}=-\int_{\mathcal{X}}\left(f+h\right)\log\left(f_{k,n,l}+h\right)\mathrm{d}\mu$

to assess the rates, and note that

$\mathrm{KL}_{h}\left(f\,||\,f_{k,n,l}\right)=\int_{\mathcal{X}}\left(f+h\right)\log\left(f+h\right)\mathrm{d}\mu+K_{k,n,l},$

where the prior term is a constant with respect to $k$ and $n$.

To analyze the sample of $7\times 6\times 50=2100$ observations of
relationship between the values $\left(K_{k,n,l}\right)_{l\in\left[r\right]}$
and the corresponding values of $k$ and $n$, we use non-linear least squares
(Amemiya, 1985, Sec. 4.3) to fit the regression relationship:

$\operatorname*{{\mathrm{\mathbf{E}}}}\left[K_{k,n,l}\right]=a_{0}+\frac{a_{1}}{\left(k+2\right)^{b_{1}}}+\frac{a_{2}}{n^{b_{2}}}.$
(16)

We obtain $95\%$ asymptotic confidence intervals for the estimates of the
regression parameters $a_{0},a_{1},a_{2},b_{1},b_{2}\in\mathbb{R}$, under the
assumption of potential mis-specification of (16), by using the sandwich
estimator for the asymptotic covariance matrix (cf. White 1982). We include
the code for these experiments in Appendix B.

###  6.3 Results

We report the estimates along with $95\%$ asymptotic confidence intervals for
the parameters of (16) for E1 and E2 in Table 1. Plots of the average negative
log $h$-lifted likelihood values by sample sizes $n$ and numbers of components
$k$ are provided in Figure 2.

Table 1:  Estimates of parameters for fitted relationships (with $95\%$ confidence intervals) between negative log $h$-lifted likelihood values, sample size and number of mixture components for experiments E1 and E2. E1 | $a_{0}$ | $a_{1}$ | $a_{2}$ | $b_{1}$ | $b_{2}$
---|---|---|---|---|---
Est. | $-1.68$ | $0.73$ | $6.80$ | $1.87$ | $0.99$
95% CI | $\left(-1.68,-1.67\right)$ | $\left(0.68,0.78\right)$ | $\left(1.24,12.36\right)$ | $\left(1.81,1.93\right)$ | $\left(0.87,1.11\right)$
E2 | $a_{0}$ | $a_{1}$ | $a_{2}$ | $b_{1}$ | $b_{2}$
Est. | $-1.47$ | $1.49$ | $6.75$ | $4.36$ | $1.07$
95% CI | $\left(-1.48,-1.47\right)$ | $\left(0.58,2.41\right)$ | $\left(2.17,11.32\right)$ | $\left(3.91,4.81\right)$ | $\left(0.97,1.16\right)$
Figure 2: Average negative log $h$-lifted likelihood values by sample sizes
$n$ and numbers of components $k$ for experiments E1 and E2.

From Table 1, we observe that
$\operatorname*{{\mathrm{\mathbf{E}}}}\left[K_{k,n,l}\right]$ decreases with
both $n$ and $k$ in both simulations, and that the rates at which the averages
decrease are faster than anticipated by Theorem 9, with respect to both $n$
and $k$. We can visually confirm the decreases in the estimate of
$\operatorname*{{\mathrm{\mathbf{E}}}}\left[K_{k,n,l}\right]$ via Figure 2. In
both E1 and E2, the rate of decrease over the assessed range of $n$ is
approximately proportional to $1/n$, as opposed to the anticipated rate of
$1/\sqrt{n}$, whereas the rate of decrease in $k$ is far larger, at
approximately $1/k^{1.87}$ for E1 and $1/k^{4.36}$ for E2.

These observations provide empirical evidence towards the fact that the rate
of decrease of $\operatorname*{{\mathrm{\mathbf{E}}}}\left[K_{k,n,l}\right]$
is at least $1/k$ and $1/\sqrt{n}$, respectively, for $k$ and $n$, at least
over the simulation scenarios. These fast rates of fit over small values of
$n$ and $k$ may be indicative of a diminishing returns of fit phenomenon, as
discussed in Cadez and Smyth (2000) or the so-called elbow phenomenon (see,
e.g., Ritter 2014, Sec. 4.2), whereupon the rate of decrease in average loss
for small values of $k$ is fast and becomes slower as $k$ increases,
converging to some asymptotic rate. This is also the reason why we do not
include the outcomes when $k=1$, as the drop in
$\operatorname*{{\mathrm{\mathbf{E}}}}\left[K_{k,n,l}\right]$ between $k=1$
and $k=2$ is so dramatic that it makes our simulated data ill-fitted by any
model of form (16). As such, we do not view Theorem 9 as being pessimistic in
light of these phenomena, as it applies uniformly over all values of $k$ and
$n$.

##  7 Conclusion

The estimation of probability densities using finite mixtures from some base
class $\mathcal{P}$ appears often in machine learning and statistical
inference as a natural method for modeling underlying data generating
processes. In this work, we sought to provide novel generalization bounds for
such mixture estimators. To this end, we introduce the family of $h$-lifted KL
divergences for densities on compact supports, within the family of Bregman
divergences, which correspond to risk functions that can be bounded, even when
densities in the class $\mathcal{P}$ are not bounded away from zero, unlike
the standard KL divergence. Unlike the least-squares loss, the corresponding
maximum $h$-likelihood estimation problem can be computed via an MM algorithm,
mirroring the availability of EM algorithms for the maximum likelihood problem
corresponding to the KL divergence. Along with our derivations of
generalization bounds that achieve the same rates as the best-known bounds for
the KL divergence and least square loss, we also provide numerical evidence
towards the correctness of these bounds in the case when $\mathcal{P}$
corresponds to beta distribution densities.

Aside from beta distributions, mixture densities on compact supports that can
be analysed under our framework appear frequently in the literature. For
supports on compact Euclidean subset, examples include mixtures of Dirichlet
distributions (Fan et al., 2012) and bivariate binomial distributions
(Papageorgiou and David, 1994). Alternatively, one can consider distributions
on compact Euclidean manifolds, such as mixtures of Kent (Peel et al., 2001)
distributions and von Mises–Fisher distributions (Banerjee et al., 2005, Ng
and Kwong, 2022). We defer investigating the practical performance of the
maximum $h$-lifted likelihood estimators and accompanying theory for such
models to future work.

##  Appendix A The $h$-lifted KL divergence as a Bregman divergence

Let $\tilde{u}=u+h$, so that $\phi(u)=\tilde{u}\log(\tilde{u})-\tilde{u}+1$.
Then $\phi^{\prime}(u)=\log(\tilde{u})$, and

$\displaystyle D_{\phi}(p\,||\,q)$
$\displaystyle=\int_{X}\\{\tilde{p}\log(\tilde{p})-\tilde{p}-1\\}-\\{\tilde{q}\log(\tilde{q})-\tilde{q}-1\\}-\log(\tilde{q})(p-q)\mathrm{d}\mu$
$\displaystyle=\int_{\mathcal{X}}\tilde{p}\log(\tilde{p})-\tilde{q}\log(\tilde{q})-p\log(\tilde{q})+q\log(\tilde{q})\mathrm{d}\mu$
$\displaystyle=\int_{\mathcal{X}}\\{p+h\\}\log(\tilde{p})-\\{q+h\\}\log(\tilde{q})-p\log(\tilde{q})+q\log(\tilde{q})\mathrm{d}\mu$
$\displaystyle=\int_{\mathcal{X}}\\{p+h\\}\log{\frac{p+h}{q+h}}\mathrm{d}\mu=\mathrm{KL}_{h}\left(p\,||\,q\right).$

##  Appendix B Experimental results

The code for all simulations and analyses of Experiment 1 and 2 is available
in both the R and Python programming languages. The experiments and analyses
presented were conducted in R. The figures were created in Python. The code
repository is available here: https://github.com/hiendn/LiftedLikelihood.

##  Appendix C Technical results

Here we collect some technical results that are required in our proofs but
appear elsewhere in the literature. In some places, notation may be modified
from the original text to keep with the established conventions herein.

######  Lemma 16 (Kosorok, 2007. Lem 9.18).

Let $N(\mathscr{F},\varepsilon,\operatorname*{\lVert\,\cdot\,\rVert})$ denote
the $\varepsilon$-covering number of $\mathscr{F}$, and
$N_{[]}(\mathscr{F},\varepsilon,\operatorname*{\lVert\,\cdot\,\rVert})$ the
$\varepsilon$-bracketing number of $\mathscr{F}$. Let
$\operatorname*{\lVert\,\cdot\,\rVert}$ be any norm on $\mathscr{F}$. Then

$N(\mathscr{F},\varepsilon,\operatorname*{\lVert\,\cdot\,\rVert})\leq
N_{[]}(\mathscr{F},\varepsilon,\operatorname*{\lVert\,\cdot\,\rVert})$

for all $\varepsilon>0$.

######  Lemma 17 (Kosorok, 2007. Lem 9.22).

For any norm $\operatorname*{\lVert\,\cdot\,\rVert}$ dominated by
${\operatorname*{\lVert\,\cdot\,\rVert}}_{\infty}$ and any class of functions
$\mathscr{F}$,

$\log
N_{[]}(\mathscr{F},2\varepsilon,\operatorname*{\lVert\,\cdot\,\rVert})\leq\log
N(\mathscr{F},\varepsilon,{\operatorname*{\lVert\,\cdot\,\rVert}}_{\infty}),$

for all $\varepsilon>0$.

######  Lemma 18 (Kosorok, 2007. Thm 9.23).

Let $\mathscr{F}=\\{f_{t}:t\in T\\}$ be a function class satisfying

$\lvert f_{s}(x)-f_{t}(x)\rvert\leq d(s,t)F(x),$

for some metric $d$ on $T$, some fixed function $F$ on $\mathcal{X}$, and for
all $x\in\mathcal{X}$ and $s,t\in T$. Then, for any norm
$\operatorname*{\lVert\,\cdot\,\rVert}$,

$N_{[]}(\mathscr{F},2\varepsilon\lVert
F\rVert,\operatorname*{\lVert\,\cdot\,\rVert})\leq N(T,\varepsilon,d).$

######  Lemma 19 (Shalev-Shwartz and Ben-David (2014), Lem 26.7).

Let $A$ be a subset of $\mathbb{R}^{m}$ and let

$A^{\prime}=\left\\{\sum_{j=1}^{n}\alpha_{j}\mathbf{a}_{j}\mid
n\in\operatorname*{\mathbb{N}},\mathbf{a}_{j}\in A,\alpha_{j}\geq
0,\lVert\mathbf{\alpha}\rVert_{1}=1\right\\}.$

Then, $\mathcal{R}_{n}(A^{\prime})=\mathcal{R}_{n}(A)$, i.e., both $A$ and
$A^{\prime}$ have the same Rademacher complexity.

######  Lemma 20 (van de Geer, 2016, Thm. 16.2).

Let $(X_{i})_{i\in[n]}$ be non-random elements of $\mathcal{X}$ and let
$\mathscr{F}$ be a class of real-valued functions on $\mathcal{X}$. If
$\varphi_{i}:\operatorname*{\mathbb{R}}\to\operatorname*{\mathbb{R}}$,
$i\in[n]$, are functions vanishing at zero that satisfy for all
$u,v\in\operatorname*{\mathbb{R}}$,

$\lvert\varphi_{i}(u)-\varphi_{i}(v)\rvert\leq\lvert u-v\rvert,$

then we have

${\mathrm{\mathbf{E}}}\left\\{\left\lVert\sum_{i=1}^{n}\varphi_{i}(f(X_{i}))\varepsilon_{i}\right\rVert_{\mathscr{F}}\right\\}\leq
2{\mathrm{\mathbf{E}}}\left\\{\left\lVert\sum_{i=1}^{n}f(X_{i})\varepsilon_{i}\right\rVert_{\mathscr{F}}\right\\}.$

######  Lemma 21 (McDiarmid, 1998, Thm. 3.1 or McDiarmid, 1989).

Suppose $(X_{i})_{i\in[n]}$ are independent random variables and let
$Z=g(X_{1},\ldots,X_{n})$, for some function $g$. If $g$ satisfies the bounded
difference condition, that is there exists constant $c_{j}$ such that for all
$j\in[n]$ and all $x_{1},\ldots,x_{j},x_{j}^{\prime},\ldots,x_{n}$,

$\lvert
g(x_{1},\ldots,x_{j-1},x_{j},x_{j+1},\ldots,x_{n})-g(x_{1},\ldots,x_{j-1},x_{j}^{\prime},x_{j+1},\ldots,x_{n})\rvert\leq
c_{j},$

then

${\mathrm{\mathbf{P}}}(Z-{\mathrm{\mathbf{E}}}Z\geq
t)\leq\exp\left\\{\frac{-2t^{2}}{\sum_{j=1}^{n}c_{j}^{2}}\right\\}.$

######  Lemma 22 (van der Vaart and Wellner, 1996, Lem. 2.3.1).

Let $\mathfrak{R}(f)=\mathrm{\mathbf{E}}f$ and
$\mathfrak{R}_{n}(f)=n^{-1}\sum_{i=1}^{n}f(X_{i})$. If
$\varPhi:\mathbb{R}_{>0}\to\mathbb{R}_{>0}$ is a convex function, then the
following inequality holds for any class of measurable functions
$\mathscr{F}$:

${\mathrm{\mathbf{E}}}\varPhi\left(\left\lVert\mathfrak{R}(f)-\mathfrak{R}_{n}(f)\right\rVert_{\mathscr{F}}\right)\leq{\mathrm{\mathbf{E}}}\varPhi\left(2\left\lVert
R_{n}(f)\right\rVert_{\mathscr{F}}\right),$

where $R_{n}(f)$ is the Rademacher process indexed by $\mathscr{F}$. In
particular, since the identity map is convex,

${\mathrm{\mathbf{E}}}\left\\{\lVert\mathfrak{R}(f)-\mathfrak{R}_{n}(f)\rVert_{\mathscr{F}}\right\\}\leq
2{\mathrm{\mathbf{E}}}\left\\{\lVert R_{n}(f)\rVert_{\mathscr{F}}\right\\}.$

######  Lemma 23 (Koltchinskii, 2011, Thm. 3.11).

Let $d_{n}$ be the empirical distance

$d_{n}^{2}(f_{1},f_{2})=\frac{1}{n}\sum_{i=1}^{n}(f_{1}(X_{i})-f_{2}(X_{i}))^{2}$

and denote by $N(\mathscr{F},\varepsilon,d_{n})$ the $\varepsilon$-covering
number of $\mathscr{F}$. Let
$\sigma_{n}^{2}\coloneqq\sup_{f\in\mathscr{F}}P_{n}f^{2}$. Then the following
inequality holds

${\mathrm{\mathbf{E}}}\left\\{\lVert
R_{n}(f)\rVert_{\mathscr{F}}\right\\}\leq\frac{K}{\sqrt{n}}\mathrm{\mathbf{E}}\int_{0}^{2\sigma_{n}}\log^{1/2}N(\mathscr{F},\varepsilon,d_{n})\mathrm{d}\varepsilon$

for some constant $K>0$.

## References

  * Amari (2016) Shun-ichi Amari.  _Information Geometry and Its Applications_ , volume 194.  Springer, New York, 2016.
  * Amemiya (1985) Takeshi Amemiya.  _Advanced econometrics_.  Harvard university press, 1985.
  * Banerjee et al. (2005) Arindam Banerjee, Inderjit S Dhillon, Joydeep Ghosh, Suvrit Sra, and Greg Ridgeway.  Clustering on the unit hypersphere using von mises-fisher distributions.  _Journal of Machine Learning Research_ , 6(9), 2005.
  * Bartlett and Mendelson (2002) Peter L Bartlett and Shahar Mendelson.  Rademacher and gaussian complexities: Risk bounds and structural results.  _Journal of Machine Learning Research_ , 3(Nov):463–482, 2002.
  * Basu et al. (1998) Ayanendranath Basu, Ian R Harris, Nils L Hjort, and MC Jones.  Robust and efficient estimation by minimising a density power divergence.  _Biometrika_ , 85(3):549–559, 1998.
  * Basu et al. (2011) Ayanendranath Basu, Hiroyuki Shioya, and Chanseok Park.  _Statistical Inference: The Minimum Distance Approach_.  CRC press, Boca Raton, 2011.
  * Cadez and Smyth (2000) Igor Cadez and Padhraic Smyth.  Model complexity, goodness of fit and diminishing returns.  _Advances in Neural Information Processing Systems_ , 13, 2000.
  * Csiszár (1995) Imre Csiszár.  Generalized projections for non-negative functions.  In _Proceedings of 1995 IEEE International Symposium on Information Theory_ , page 6. IEEE, 1995.
  * Dalalyan and Sebbar (2018) Arnak S Dalalyan and Mehdi Sebbar.  Optimal kullback–leibler aggregation in mixture density estimation by maximum likelihood.  _Mathematical Statistics and Learning_ , 1(1):1–35, 2018.
  * DeVore and Temlyakov (2016) Ronald A DeVore and Vladimir N Temlyakov.  Convex optimization on banach spaces.  _Foundations of Computational Mathematics_ , 16(2):369–394, 2016.
  * Fan et al. (2012) Wentao Fan, Nizar Bouguila, and Djemel Ziou.  Variational learning for finite dirichlet mixture models and applications.  _IEEE transactions on neural networks and learning systems_ , 23:762–774, 2012.
  * Ferrari and Yang (2010) Davide Ferrari and Yuhong Yang.  Maximum lq-likelihood method.  _Annals of Statistics_ , 38:573–583, 2010.
  * Frigyik et al. (2008) Béla A Frigyik, Santosh Srivastava, and Maya R Gupta.  Functional bregman divergence and bayesian estimation of distributions.  _IEEE Transactions on Information Theory_ , 54(11):5130–5139, 2008.
  * Fujisawa and Eguchi (2006) Hironori Fujisawa and Shinto Eguchi.  Robust estimation in the normal mixture model.  _Journal of Statistical Planning and Inference_ , 136(11):3989–4011, 2006.
  * Gil et al. (2013) Manuel Gil, Fady Alajaji, and Tamas Linder.  Rényi divergence measures for commonly used univariate continuous distributions.  _Information Sciences_ , 249:124–131, 2013.
  * Giraud (2021) Christophe Giraud.  _Introduction to high-dimensional statistics_.  CRC Press, 2021.
  * Haagerup (1981) Uffe Haagerup.  The best constants in the khintchine inequality.  _Studia Mathematica_ , 70(3):231–283, 1981.
  * Hunter and Lange (2004) David R Hunter and Kenneth Lange.  A tutorial on mm algorithms.  _The American Statistician_ , 58(1):30–37, 2004.
  * Klemelä (2007) Jussi S Klemelä.  Density estimation with stagewise optimization of the empirical risk.  _Machine Learning_ , 67:169–195, 2007.
  * Klemelä (2009) Jussi S Klemelä.  _Smoothing of multivariate data: density estimation and visualization_.  John Wiley & Sons, 2009.
  * Kobayashi and Watanabe (2021) Masahiro Kobayashi and Kazuho Watanabe.  Generalized Dirichlet-process-means for f-separable distortion measures.  _Neurocomputing_ , 458:667–689, 2021.  ISSN 0925-2312.
  * Kobayashi and Watanabe (2024) Masahiro Kobayashi and Kazuho Watanabe.  Unbiased Estimating Equation and Latent Bias under f-Separable Bregman Distortion Measures.  _IEEE Transactions on Information Theory_ , 2024.
  * Koltchinskii (2011) Vladimir Koltchinskii.  _Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems: École D’Été de Probabilités de Saint-Flour XXXVIII-2008_.  Lecture Notes in Mathematics. Springer, 2011.  ISBN 9783642221460.
  * Koltchinskii and Panchenko (2004) Vladimir Koltchinskii and Dmitry Panchenko.  Rademacher processes and bounding the risk of function learning.  _arXiv: Probability_ , pages 443–457, 2004.
  * Kosorok (2007) Michael R. Kosorok.  _Introduction to Empirical Processes and Semiparametric Inference_.  Springer Series in Statistics. Springer New York, 2007.  ISBN 9780387749785.
  * Lange (2016) Kenneth Lange.  _MM optimization algorithms_.  SIAM, 2016.
  * Li and Barron (1999) Jonathan Li and Andrew Barron.  Mixture Density Estimation.  In S. Solla, T. Leen, and K. Müller, editors, _Advances in Neural Information Processing Systems_ , volume 12. MIT Press, 1999.
  * Massart (2007) Pascal Massart.  _Concentration inequalities and model selection: Ecole d’Eté de Probabilités de Saint-Flour XXXIII-2003_.  Springer, 2007.
  * Maugis and Michel (2011) Cathy Maugis and Bertrand Michel.  A non asymptotic penalized criterion for gaussian mixture model selection.  _ESAIM: Probability and Statistics_ , 15:41–68, 2011.
  * Maugis-Rabusseau and Michel (2013) Cathy Maugis-Rabusseau and Bertrand Michel.  Adaptive density estimation for clustering with gaussian mixtures.  _ESAIM: Probability and Statistics_ , 17:698–724, 2013.
  * McDiarmid (1989) Colin McDiarmid.  On the method of bounded differences.  In J.Editor Siemons, editor, _Surveys in Combinatorics, 1989: Invited Papers at the Twelfth British Combinatorial Conference_ , London Mathematical Society Lecture Note Series, pages 148–188. Cambridge University Press, 1989.
  * McDiarmid (1998) Colin McDiarmid.  Concentration.  In Michel Habib, Colin McDiarmid, Jorge Ramirez-Alfonsin, and Bruce Reed, editors, _Probabilistic Methods for Algorithmic Discrete Mathematics_ , pages 195–248. Springer Berlin Heidelberg, Berlin, Heidelberg, 1998.  ISBN 978-3-662-12788-9.
  * McLachlan and Peel (2004) Geoffrey J McLachlan and David Peel.  _Finite Mixture Models_.  John Wiley & Sons, 2004.
  * Meir and Zeevi (1997) Ronny Meir and Assaf Zeevi.  Density estimation through convex combinations of densities: Approximation and estimation bounds.  _Neural Networks_ , 10:99–109, 02 1997.
  * Naito and Eguchi (2013) Kanta Naito and Shinto Eguchi.  Density estimation with minimization of U-divergence.  _Machine Learning_ , 90(1):29–57, January 2013.
  * Ng and Kwong (2022) Tin Lok James Ng and Kwok-Kun Kwong.  Universal approximation on the hypersphere.  _Communications in Statistics-Theory and Methods_ , 51:8694–8704, 2022.
  * Nguyen (2017) Hien D Nguyen.  An introduction to majorization-minimization algorithms for machine learning and statistical estimation.  _Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery_ , 7(2):e1198, 2017.
  * Nguyen et al. (2022a) Hien D Nguyen, Florence Forbes, Gersende Fort, and Olivier Cappé.  An online minorization-maximization algorithm.  In _17th Conference of the International Federation of Classification Societies_ , 2022a.
  * Nguyen et al. (2020) TrungTin Nguyen, Hien D Nguyen, Faicel Chamroukhi, and Geoffrey J McLachlan.  Approximation by finite mixtures of continuous density functions that vanish at infinity.  _Cogent Mathematics & Statistics_, 7:1750861, 2020.
  * Nguyen et al. (2022b) TrungTin Nguyen, Faicel Chamroukhi, Hien D Nguyen, and Geoffrey J McLachlan.  Approximation of probability density functions via location-scale finite mixtures in Lebesgue spaces.  _Communications in Statistics - Theory and Methods_ , pages 1–12, 2022b.
  * Nguyen et al. (2022c) TrungTin Nguyen, Hien D Nguyen, Faicel Chamroukhi, and Florence Forbes.  A non-asymptotic approach for model selection via penalization in high-dimensional mixture of experts models.  _Electronic Journal of Statistics_ , 16(2):4742–4822, 2022c.
  * Papageorgiou and David (1994) H Papageorgiou and Katerina M David.  On countable mixtures of bivariate binomial distributions.  _Biometrical journal_ , 36(5):581–601, 1994.
  * Pardo (2006) Leandro Pardo.  _Statistical Inference Based on Divergence Measures_.  CRC Press, Boca Raton, 2006.
  * Peel et al. (2001) David Peel, William J Whiten, and Geoffrey J McLachlan.  Fitting mixtures of kent distributions to aid in joint set identification.  _Journal of the American Statistical Association_ , 96:56–63, 2001.
  * Qin and Priebe (2013) Yichen Qin and Carey E Priebe.  Maximum $L_{q}$-likelihood estimation via the expectation-maximization algorithm: a robust estimation of mixture models.  _Journal of the American Statistical Association_ , 108(503):914–928, 2013.
  * Rakhlin et al. (2005) Alexander Rakhlin, Dmitry Panchenko, and Sayan Mukherjee.  Risk bounds for mixture density estimation.  _ESAIM: PS_ , 9:220–229, 2005.
  * Razaviyayn et al. (2013) Meisam Razaviyayn, Mingyi Hong, and Zhi-Quan Luo.  A unified convergence analysis of block successive minimization methods for nonsmooth optimization.  _SIAM Journal on Optimization_ , 23(2):1126–1153, 2013.
  * Ritter (2014) Gunter Ritter.  _Robust cluster analysis and variable selection_.  CRC Press, 2014.
  * Rockafellar (1997) Ralph Tyrrell Rockafellar.  _Convex analysis_ , volume 11.  Princeton university press, 1997.
  * Shalev-Shwartz and Ben-David (2014) Shai Shalev-Shwartz and Shai Ben-David.  _Understanding machine learning: From theory to algorithms_.  Cambridge university press, 2014.
  * Stummer and Vajda (2012) Wolfgang Stummer and Igor Vajda.  On bregman distances and divergences of probability measures.  _IEEE Transactions on Information Theory_ , 58(3):1277–1288, 2012.
  * Temlyakov (2016) Vladimir N Temlyakov.  Convergence and rate of convergence of some greedy algorithms in convex optimization.  _Proceedings of the Steklov Institute of Mathematics_ , 293:325–337, 2016.
  * van de Geer (2016) Sara van de Geer.  _Estimation and Testing Under Sparsity: École d’Été de Probabilités de Saint-Flour XLV – 2015_.  Lecture Notes in Mathematics. Springer International Publishing, 2016.  ISBN 9783319327747.
  * van der Vaart and Wellner (1996) Aad W van der Vaart and Jon A Wellner.  _Weak Convergence and Empirical Processes: With Applications to Statistics_.  Springer Series in Statistics. Springer, 1996.  ISBN 9780387946405.
  * Verbeek et al. (2003) Jakob J Verbeek, Nikos Vlassis, and Ben Kröse.  Efficient greedy learning of gaussian mixture models.  _Neural computation_ , 15(2):469–485, 2003.
  * Vlassis and Likas (2002) Nikos Vlassis and Aristidis Likas.  A greedy em algorithm for gaussian mixture learning.  _Neural processing letters_ , 15:77–87, 2002.
  * White (1982) Halbert White.  Maximum likelihood estimation of misspecified models.  _Econometrica_ , pages 1–25, 1982.
  * Wu and Lange (2010) Tong Tong Wu and Kenneth Lange.  The mm alternative to em.  _Statistical Science_ , 25(4):492–505, 2010.
  * Zhang (2003) Tong Zhang.  Sequential greedy approximation for certain convex optimization problems.  _IEEE Transactions on Information Theory_ , 49(3):682–691, 2003.