lemmaindex lemma propositionindex proposition corollaryindex corollary
definitionindex definition remarkindex remark

# Mixture weights optimisation for Alpha-Divergence Variational Inference

Kamélia Daudel
LTCI, Télécom Paris
Institut Polytechnique de Paris, France
<EMAIL_ADDRESS>
&Randal Douc
SAMOVAR, Télécom SudParis
Institut Polytechnique de Paris, France
<EMAIL_ADDRESS>
# Mixture weights optimisation for Alpha-Divergence Variational Inference

Kamélia Daudel
LTCI, Télécom Paris
Institut Polytechnique de Paris, France
<EMAIL_ADDRESS>
&Randal Douc
SAMOVAR, Télécom SudParis
Institut Polytechnique de Paris, France
<EMAIL_ADDRESS>
###### Abstract

This paper focuses on gradient-based Variational Inference for
$\alpha$-divergence minimisation. More precisely, we are interested in
studying algorithms making it possible to optimise the mixture weights of any
given mixture model, without any information on the underlying distribution of
its mixture components parameters. The Power Descent is one such algorithm and
we establish in our work its convergence towards the optimal mixture weights
when $\alpha<1$ under alleviated assumptions. We also investigate the link
between Power Descent and Entropic Mirror Descent: this allows us to introduce
the Renyi Descent, for which we prove an $O(1/N)$ convergence rate. We then
provide some numerical experiments to illustrate the behavior of these two
algorithms in practice.

##  1 Introduction

Bayesian Inference involves being able to compute or sample from the posterior
density. For many useful models, the posterior density can only be evaluated
up to a normalisation constant and we must resort to approximation methods.

One major category of approximation methods is Variational Inference, a wide
class of optimisation methods which introduce a simpler density family
$\mathcal{Q}$ and use it to approximate the posterior density (see for example
Variational Bayes [1, 2] and Stochastic Variational Inference [3]). The crux
of these methods consists in being able to find the best approximation of the
posterior density among the family $\mathcal{Q}$ in the sense of a certain
divergence, most typically the Kullback-Leibler divergence. However, The
Kullback-Leibler divergence is known to have some undesirable properties (e.g
posterior overestimation/underestimation [4]) and as a consequence, the
$\alpha$-divergence [5, 6] and Renyi’s $\alpha$-divergence [7, 8] have gained
a lot of attention recently as a more general alternative [9, 10, 11, 12, 13,
14, 15, 16, 17, 18, 19].

Noticeably, [17] introduced the $(\alpha,\Gamma)$-descent, a general family of
gradient-based algorithms that are able to optimise the mixture weights of
mixture models by $\alpha$-divergence minimisation, without any information on
the underlying distribution of its mixture components parameters. The benefit
of these types of algorithms is that they allow, in an Sequential Monte Carlo
fashion [20], to select the mixture components according to their overall
importance in the set of component parameters. From there, one is able to
optimise the weights and the components parameters alternatively [17]. The
$(\alpha,\Gamma)$-descent framework recovers the Entropic Mirror Descent
algorithm (corresponding to $\Gamma(v)=e^{-\eta v}$ with $\eta>0$) and
includes the Power Descent, an algorithm defined for all
$\alpha\in\mathbb{R}\setminus\left\\{1\right\\}$ and all $\eta>0$ that sets
$\Gamma(v)=[(\alpha-1)v+1]^{\eta/(1-\alpha)}$. Although these two algorithms
are linked to one another from a theoretical perspective through the
$(\alpha,\Gamma)$-descent framework, numerical experiments in [17] showed that
the Power Descent outperforms the Entropic Mirror Descent when $\alpha<1$ as
the dimension increases.

Nonetheless, the global convergence of the Power Descent algorithm when
$\alpha<1$, as stated in [17], is subjected to the condition that the limit
exists. Furthermore, even though the convergence towards the global optimum is
derived, there is no convergence rate available for the Power Descent when
$\alpha<1$. While there is no general rule yet on how to select the value of
$\alpha$ in practice, the case $\alpha<1$ has the advantage that it enforces a
mass-covering property, as opposed to the mode-seeking property exhibited when
$\alpha\geqslant 1$ ([4] and [17]) and which often may lead to posterior
variance underestimation. We are thus interested in studying Variational
Inference methods for optimising the mixture weights of mixture models when
$\alpha<1$. After recalling the basics of the Power Descent algorithm in
Section 2, we make the following contributions in the paper:

  * $\bullet$

In Section 3, we derive the full convergence proof of the Power Descent
algorithm towards the optimal mixture weights when $\alpha<1$ (2).

  * $\bullet$

Since the $\alpha$-divergence becomes the traditional forward Kullback-Leibler
when $\alpha\to 1$, we first bridge in Section 4 the gap between the cases
$\alpha<1$ and $\alpha>1$ of the Power Descent: we obtain that the Power
Descent recovers an Entropic Mirror Descent performing forward Kullback-
Leibler minimisation (Section 4). We then keep on investigating the
connections between the Power Descent and the Entropic Mirror Descent by
considering first-order approximations. In doing so, we are able to go beyond
the $(\alpha,\Gamma)$-descent framework and to introduce an algorithm closely-
related to the Power Descent that we call the Renyi Descent and that is proved
in 3 to converge at an $O(1/N)$ rate towards its optimum for all
$\alpha\in\mathbb{R}$.

  * $\bullet$

Finally, we run some numerical experiments in Section 5 to compare the
behavior of the Power Descent and the Renyi Descent altogether, before
discussing the potential benefits of one approach over the other.

##  2 Background

We start by introducing some notation. Let $(\mathsf{Y},\mathcal{Y},\nu)$ be a
measured space, where $\nu$ is a $\sigma$-finite measure on
$(\mathsf{Y},\mathcal{Y})$. Assume that we have access to some observed
variables $\mathscr{D}$ generated from a probabilistic model
$p(\mathscr{D}|y)$ parameterised by a hidden random variable $y\in\mathsf{Y}$
that is drawn from a certain prior $p_{0}(y)$. The posterior density of the
latent variable $y$ given the data $\mathscr{D}$ is then given by:

$p(y|\mathscr{D})=\frac{p(y,\mathscr{D})}{p(\mathscr{D})}=\frac{p_{0}(y)p(\mathscr{D}|y)}{p(\mathscr{D})}\;,$

where the normalisation constant
$p(\mathscr{D})=\int_{\mathsf{Y}}p_{0}(y)p(\mathscr{D}|y)\nu(\mathrm{d}y)$ is
called the marginal likelihood or model evidence and is oftentimes unknown.

To approximate the posterior density, the Power Descent considers a
variational family $\mathcal{Q}$ that is large enough to contain mixture
models and that we redefine now: letting $({\mathsf{T}},\mathcal{T})$ be a
measurable space, $K:(\theta,A)\mapsto\int_{A}k(\theta,y)\nu(\mathrm{d}y)$ be
a Markov transition kernel on ${\mathsf{T}}\times\mathcal{Y}$ with kernel
density $k$ defined on ${\mathsf{T}}\times\mathsf{Y}$, the Power Descent
considers the following approximating family

$\left\\{y\mapsto\int_{\mathsf{T}}\mu(\mathrm{d}\theta)k(\theta,y)\;:\;\mu\in\mathsf{M}\right\\}\;,$

where $\mathsf{M}$ is a convenient subset of $\mathrm{M}_{1}({\mathsf{T}})$,
the set of probability measures on $({\mathsf{T}},\mathcal{T})$. This choice
of approximating family extends the typical parametric family commonly-used in
Variational Inference since it amounts to putting a prior over the parameter
$\theta$ (in the form of a measure) and does describe the class of mixture
models when $\mu$ is a weighted sum of Dirac measures.

##### Problem statement

Denote by $\mathbb{P}$ the probability measure on $(\mathsf{Y},\mathcal{Y})$
with corresponding density $p(\cdot|\mathscr{D})$ with respect to $\nu$ and
for all $\mu\in\mathrm{M}_{1}({\mathsf{T}})$, for all $y\in\mathsf{Y}$, denote
$\mu k(y)=\int_{\mathsf{T}}\mu(\mathrm{d}\theta)k(\theta,y)$. Furthermore,
given $\alpha\in\mathbb{R}$, let $f_{\alpha}$ be the convex function on
$(0,+\infty)$ defined by $f_{0}(u)=u-1-\log(u)$, $f_{1}(u)=1-u+u\log(u)$ and
$f_{\alpha}(u)=\frac{1}{\alpha(\alpha-1)}\left[u^{\alpha}-1-\alpha(u-1)\right]$
for all $\alpha\in\mathbb{R}\setminus\left\\{0,1\right\\}$. Then, the
$\alpha$-divergence between $\mu K$ and $\mathbb{P}$ (extended by continuity
to the cases $\alpha=0$ and $\alpha=1$ as for example done in [21]) is given
by

$\displaystyle D_{\alpha}(\mu
K||\mathbb{P})=\int_{\mathsf{Y}}f_{\alpha}\left(\frac{\mu
k(y)}{p(y|\mathscr{D})}\right)p(y|\mathscr{D})\nu(\mathrm{d}y)\;,$

and the goal of the Power Descent is to find

$\displaystyle\mathrm{arginf}_{\mu\in\mathsf{M}}D_{\alpha}(\mu
K||\mathbb{P})\;.$ (1)

More generally, letting $p$ be any measurable positive function on
$(\mathsf{Y},\mathcal{Y})$, the Power Descent aims at solving

$\displaystyle\mathrm{arginf}_{\mu\in\mathsf{M}}\Psi_{\alpha}(\mu;p)\;,$ (2)

where for all $\mu\in\mathrm{M}_{1}({\mathsf{T}})$,
$\Psi_{\alpha}(\mu;p)=\int_{\mathsf{Y}}f_{\alpha}\left(\mu
k(y)/p(y)\right)p(y)\nu(\mathrm{d}y)$. The Variational Inference optimisation
problem (1) can then be seen as an instance of (2) that is equivalent to
optimising $\Psi_{\alpha}(\mu;p)$ with $p(y)=p(y,\mathscr{D})$ (see Section
A.1). In the following, the dependency on $p$ in $\Psi_{\alpha}$ may be
dropped throughout the paper for notational ease when no ambiguity occurs and
we now present the Power Descent algorithm.

##### The Power Descent algorithm.

The optimisation problem (2) can be solved for all
$\alpha\in\mathbb{R}\setminus\left\\{1\right\\}$ by using the Power Descent
algorithm introduced in [17] : given an initial measure
$\mu_{1}\in\mathrm{M}_{1}({\mathsf{T}})$ such that
$\Psi_{\alpha}(\mu_{1})<\infty$,
$\alpha\in\mathbb{R}\setminus\left\\{1\right\\}$, $\eta>0$ and $\kappa$ such
that $(\alpha-1)\kappa\geqslant 0$, the Power descent algorithm is an
iterative scheme which builds the sequence of probability measures
$(\mu_{n})_{n\in\mathbb{N}^{\star}}$

$\mu_{n+1}=\mathcal{I}_{\alpha}(\mu_{n})\;,\qquad n\in\mathbb{N}^{\star}\;,$
(3)

where for all $\mu\in\mathrm{M}_{1}({\mathsf{T}})$, the one-step transition
$\mu\mapsto\mathcal{I}_{\alpha}(\mu)$ is given by Algorithm 1 and where for
all $v\in\mathrm{Dom}_{\alpha}$, $\Gamma(v)=[(\alpha-1)v+1]^{\eta/(1-\alpha)}$
[and $\mathrm{Dom}_{\alpha}$ denotes an interval of $\mathbb{R}$ such that for
all $\theta\in{\mathsf{T}}$, all $\mu\in\mathrm{M}_{1}({\mathsf{T}})$,
${b_{\mu,\alpha}}(\theta)+\kappa$ and
$\mu({b_{\mu,\alpha}})+\kappa\in\mathrm{Dom}_{\alpha}$].

  1. 1.

Expectation step :
${b_{\mu,\alpha}}(\theta)={\int_{\mathsf{Y}}}k(\theta,y)f_{\alpha}^{\prime}\left(\dfrac{\mu
k(y)}{p(y)}\right)\nu(\mathrm{d}y)$

  2. 2.

Iteration step :
$\mathcal{I}_{\alpha}(\mu)(\mathrm{d}\theta)=\dfrac{\mu(\mathrm{d}\theta)\cdot\Gamma({b_{\mu,\alpha}}(\theta)+\kappa)}{\mu(\Gamma({b_{\mu,\alpha}}+\kappa))}$

Algorithm 1 Power descent one-step transition
$(\Gamma(v)=[(\alpha-1)v+1]^{\eta/(1-\alpha)})$

In this algorithm, ${b_{\mu,\alpha}}$ can be understood as the gradient of
$\Psi_{\alpha}$. Algorithm 1 then consists in applying the transform function
$\Gamma$ to the translated gradient ${b_{\mu,\alpha}}+\kappa$ and projecting
back onto the space of probability measures.

A remarkable property of the Power Descent algorithm, which has been proven in
[17] (it is a special case of [17, Theorem 1] with
$\Gamma(v)=[(\alpha-1)v+1]^{\eta/(1-\alpha)}$), is that under (A1) as defined
below

  1. (A1)

The density kernel $k$ on ${\mathsf{T}}\times\mathsf{Y}$, the function $p$ on
$\mathsf{Y}$ and the $\sigma$-finite measure $\nu$ on
$(\mathsf{Y},\mathcal{Y})$ satisfy, for all
$(\theta,y)\in{\mathsf{T}}\times\mathsf{Y}$, $k(\theta,y)>0$, $p(y)>0$ and
$\int_{\mathsf{Y}}p(y)\nu(\mathrm{d}y)<\infty$.

the Power Descent ensures a monotonic decrease in the $\alpha$-divergence at
each step for all $\eta\in(0,1]$ (this result is recalled in 4 of Section A.2
for the sake of completeness). Under the additional assumptions that
$\kappa>0$ and

$\displaystyle\sup_{\theta\in{\mathsf{T}},\mu\in\mathrm{M}_{1}({\mathsf{T}})}|{b_{\mu,\alpha}}|<\infty\quad\mbox{and}\quad\Psi_{\alpha}(\mu_{1})<\infty\;,$
(4)

the Power Descent is also known to converge towards its optimal value at an
$O(1/N)$ rate when $\alpha>1$ [17, Theorem 3]. On the other hand, when
$\alpha<1$, the convergence towards the optimum as written in [17] holds under
different assumptions including

  1. (A2)

    1. (i)

${\mathsf{T}}$ is a compact metric space and $\mathcal{T}$ is the associated
Borel $\sigma$-field;

    2. (ii)

for all $y\in\mathsf{Y}$, $\theta\mapsto k(\theta,y)$ is continuous;

    3. (iii)

we have
$\int_{\mathsf{Y}}{\sup_{\theta\in{\mathsf{T}}}k(\theta,y)}\times\sup_{\theta^{\prime}\in{\mathsf{T}}}\left(\frac{k(\theta^{\prime},y)}{p(y)}\right)^{\alpha-1}\nu(\mathrm{d}y)<\infty$.

If $\alpha=0$, assume in addition that
$\int_{\mathsf{Y}}{\sup_{\theta\in{\mathsf{T}}}\left|\log\left(\frac{k(\theta,y)}{p(y)}\right)\right|}p(y)\nu(\mathrm{d}y)<\infty$.

so that [17, Theorem 4], that is recalled below under the form of 1, states
the convergence of the Power Descent algorithm towards the global optimum.

######  Theorem 1 ([17, Theorem 4]).

Assume (A1) and (A2). Let $\alpha<1$ and let $\kappa\leqslant 0$. Then, for
all $\mu\in\mathrm{M}_{1}({\mathsf{T}})$, $\Psi_{\alpha}(\mu)<\infty$ and any
$\eta>0$ satisfies $0<\mu(\Gamma({b_{\mu,\alpha}}+\kappa))<\infty$. Further
assume that $\eta\in(0,1]$ and that there exist
$\mu_{1},{\mu^{\star}}\in\mathrm{M}_{1}({\mathsf{T}})$ such that the (well-
defined) sequence $(\mu_{n})_{n\in\mathbb{N}^{\star}}$ defined by (3) weakly
converges to ${\mu^{\star}}$ as $n\to\infty$. Finally, denote by
$\mathrm{M}_{1,\mu_{1}}({\mathsf{T}})$ the set of probability measures
dominated by $\mu_{1}$. Then the following assertions hold

  1. (i)

$(\Psi_{\alpha}(\mu_{n}))_{n\in\mathbb{N}^{\star}}$ is nonincreasing,

  2. (ii)

${\mu^{\star}}$ is a fixed point of $\mathcal{I}_{\alpha}$,

  3. (iii)

$\Psi_{\alpha}({\mu^{\star}})=\inf_{\zeta\in\mathrm{M}_{1,\mu_{1}}({\mathsf{T}})}\Psi_{\alpha}(\zeta)$.

The above result assumes there must exist
$\mu_{1},{\mu^{\star}}\in\mathrm{M}_{1}({\mathsf{T}})$ such that the sequence
$(\mu_{n})_{n\in\mathbb{N}^{\star}}$ defined by (3) weakly converges to
${\mu^{\star}}$ as $n\to\infty$, that is it assumes the limit already exists.
Our first contribution consists in showing that this assumption can be
alleviated when $\mu$ is chosen a weighted sum of Dirac measures, that is when
we seek to perform mixture weights optimisation by $\alpha$-divergence
minimisation.

##  3 Convergence of the Power Descent algorithm in the mixture case

Before we state our convergence result, let us first make two comments on the
assumptions from 1 that shall be retained in our upcoming convergence result.

A first comment is that (A1) is mild since the assumption that $p(y)>0$ for
all $y\in\mathsf{Y}$ can be discarded and is kept for convenience [17, Remark
4]. A second comment is that (A2) is also mild and covers (4) as it amounts to
assuming that ${b_{\mu,\alpha}}(\theta)$ and $\Psi_{\alpha}(\mu)$ are
uniformly bounded with respect to $\mu$ and $\theta$. To see this, we give
below an example for which (A2) is satisfied.

######  Example 1.

Consider the case $\mathsf{Y}=\mathbb{R}^{d}$ with $\alpha\in[0,1)$. Let $r>0$
and let ${\mathsf{T}}=\mathcal{B}(0,r)\subset\mathbb{R}^{d}$. Furtheremore,
let $K_{h}$ be a Gaussian transition kernel with bandwidth $h$ and denote by
$k_{h}$ its associated kernel density. Finally, let $p$ be a mixture density
of two $d$-dimensional Gaussian distributions multiplied by a positive
constant $c$ such that
$p(y)=c\times\left[0.5\mathcal{N}(y;\theta^{\star}_{1},\boldsymbol{I_{d}})+0.5\mathcal{N}(y;\theta^{\star}_{2},\boldsymbol{I_{d}})\right]$
for all $y\in\mathsf{Y}$ where
$\theta_{1}^{\star},\theta_{2}^{\star}\in{\mathsf{T}}$ and
$\boldsymbol{I_{d}}$ is the identity matrix. Then, (A2) holds (see Section
B.1).

Next, we introduce some notation that are specific to the case of mixture
models we aim at studying in this section. Given $J\in\mathbb{N}^{\star}$, we
introduce the simplex of $\mathbb{R}^{J}$:

$\mathcal{S}_{J}=\left\\{{\boldsymbol{\lambda}}=(\lambda_{1},\ldots,\lambda_{J})\in\mathbb{R}^{J}\;:\;\forall
j\in\left\\{1,\ldots,J\right\\},\;\lambda_{j}\geqslant
0\;\mbox{and}\;\sum_{j=1}^{J}\lambda_{j}=1\right\\}\;$

and we also define
$\mathcal{S}_{J}^{+}=\left\\{{\boldsymbol{\lambda}}\in\mathcal{S}_{J}\;:\;\forall
j\in\left\\{1,\ldots,J\right\\},\;\lambda_{j}>0\right\\}$. We let
$\Theta=(\theta_{1},\ldots,\theta_{J})\in{\mathsf{T}}^{J}$ be fixed and for
all ${\boldsymbol{\lambda}}\in\mathcal{S}_{J}$, we define
${\mu_{{\boldsymbol{\lambda}},\Theta}}\in\mathrm{M}_{1}({\mathsf{T}})$ by
${\mu_{{\boldsymbol{\lambda}},\Theta}}=\sum_{j=1}^{J}\lambda_{j}\delta_{\theta_{j}}$.

Consequently,
${\mu_{{\boldsymbol{\lambda}},\Theta}}k(y)=\sum_{j=1}^{J}\lambda_{j}k(\theta_{j},y)$
corresponds to a mixture model and if we let
$(\mu_{n})_{n\in\mathbb{N}^{\star}}$ be defined by
$\mu_{1}={\mu_{{\boldsymbol{\lambda}},\Theta}}$ and (3), an immediate
induction yields that for every $n\in\mathbb{N}^{\star}$, $\mu_{n}$ can be
expressed as $\mu_{n}=\sum_{j=1}^{J}\lambda_{j,n}\delta_{\theta_{j}}$ where
${\boldsymbol{\lambda}_{n}}=(\lambda_{1,n},\ldots,\lambda_{J,n})\in\mathcal{S}_{J}$
satisfies the initialisation
${\boldsymbol{\lambda}_{1}}={\boldsymbol{\lambda}}$ and the update formula:

$\displaystyle{\boldsymbol{\lambda}_{n+1}}=\mathcal{I}_{\alpha}^{\mathrm{mixt}}({\boldsymbol{\lambda}_{n}})\;,\;n\in\mathbb{N}^{\star}\;,$
(5)

where for all ${\boldsymbol{\lambda}}\in\mathcal{S}_{J}$,

$\mathcal{I}_{\alpha}^{\mathrm{mixt}}({\boldsymbol{\lambda}}):=\left(\dfrac{\lambda_{j}\Gamma({b_{{\mu_{{\boldsymbol{\lambda}},\Theta}},\alpha}}(\theta_{j})+\kappa)}{\sum_{\ell=1}^{J}\lambda_{\ell}\Gamma({b_{{\mu_{{\boldsymbol{\lambda}},\Theta}},\alpha}}(\theta_{\ell})+\kappa)}\right)_{1\leqslant
j\leqslant J}$

with $\Gamma(v)=[(\alpha-1)v+1]^{\frac{\eta}{1-\alpha}}$ for all
$v\in\mathrm{Dom}_{\alpha}$. Finally, let us rewrite (A2) in the simplified
case where $\mu$ is a sum of Dirac measures, which gives (A3) below.

  1. (A3)

    1. (i)

For all $y\in\mathsf{Y}$, $\theta\mapsto k(\theta,y)$ is continuous;

    2. (ii)

we have $\int_{\mathsf{Y}}\max\limits_{1\leqslant j\leqslant
J}k(\theta_{j},y)\times\max\limits_{1\leqslant j^{\prime}\leqslant
J}\left(\frac{k(\theta_{j^{\prime}},y)}{p(y)}\right)^{\alpha-1}\nu(\mathrm{d}y)<\infty$.

If $\alpha=0$, we assume in addition that
$\int_{\mathsf{Y}}\max\limits_{1\leqslant j\leqslant
J}\left|\log\left(\frac{k(\theta_{j},y)}{p(y)}\right)\right|p(y)\nu(\mathrm{d}y)<\infty$.

We then have the following theorem, which establishes the full proof of the
global convergence towards the optimum for the mixture weights when
$\alpha<1$.

######  Theorem 2.

Assume (A1) and (A3). Let $\alpha<1$, let
$\Theta=(\theta_{1},\ldots,\theta_{J})\in{\mathsf{T}}^{J}$ be fixed and let
$\kappa$ be such that $\kappa\leqslant 0$. Then for all
${\boldsymbol{\lambda}}\in\mathcal{S}_{J}$,
$\Psi_{\alpha}({\mu_{{\boldsymbol{\lambda}},\Theta}})<\infty$ and for any
$\eta>0$ the sequence $({\boldsymbol{\lambda}_{n}})_{n\in\mathbb{N}^{\star}}$
defined by ${\boldsymbol{\lambda}_{1}}\in\mathcal{S}_{J}$ and (5) is well-
defined. If in addition
$({\boldsymbol{\lambda}_{1}},\eta)\in\mathcal{S}_{J}^{+}\times(0,1]$ and
$\left\\{K(\theta_{1},\cdot),\ldots,K(\theta_{J},\cdot)\right\\}$ are linearly
independent, then

  1. (i)

$(\Psi_{\alpha}({\mu_{{\boldsymbol{\lambda}_{n}},\Theta}}))_{n\in\mathbb{N}^{\star}}$
is nonincreasing,

  2. (ii)

the sequence $({\boldsymbol{\lambda}_{n}})_{n\in\mathbb{N}^{\star}}$ converges
to some ${\boldsymbol{\lambda}_{\star}}\in\mathcal{S}_{J}$ which is a fixed
point of $\mathcal{I}_{\alpha}^{\mathrm{mixt}}$,

  3. (iii)

$\Psi_{\alpha}({\mu_{{\boldsymbol{\lambda}_{\star}},\Theta}})=\inf_{{\boldsymbol{\lambda}}^{\prime}\in\mathcal{S}_{J}}\Psi_{\alpha}({\mu_{{\boldsymbol{\lambda}}^{\prime},\Theta}})$.

The proof of this result builds on 1 and 4 and is deferred to Section B.2.
Notice that since $\Psi_{\alpha}$ depends on ${\boldsymbol{\lambda}}$ through
${\mu_{{\boldsymbol{\lambda}},\Theta}}{}K$ in 2, an identifiably condition was
to be expected in order to achieve the convergence of the sequence
$({\boldsymbol{\lambda}_{n}})_{n\in\mathbb{N}^{\star}}$. Following 1, this
identifiably condition notably holds for $J\leqslant d$ under the assumption
that the $\theta_{1},...,\theta_{J}$ are full-rank.

We thus have the convergence of the Power Descent under less stringent
conditions when $\alpha<1$ and when we consider the particular case of mixture
models. This algorithm can easily become feasible for any choice of kernel $K$
by resorting to an unbiased estimator of
$({b_{{\mu_{{\boldsymbol{\lambda}_{n}},\Theta}},\alpha}}(\theta_{j}))_{1\leqslant
j\leqslant J}$ in the update formula (5) (see Algorithm 3 of Section B.3).

Nevertheless, contrary to the case $\alpha>1$ we still do not have a
convergence rate for the Power Descent when $\alpha<1$. Furthermore, the
important case $\alpha\to 1$, which corresponds to performing forward
Kullback-Leibler minimisation, is not covered by the Power Descent algorithm.
In the next section, we extend the Power Descent to the case $\alpha=1$. As we
shall see, this will lead us to investigate the connections between the Power
Descent and the Entropic Mirror Descent beyond the $(\alpha,\Gamma)$-descent
framework. As a result, we will introduce a novel algorithm closely-related to
the Power Descent that yields an $O(1/N)$ convergence rate when
$\mu={\mu_{{\boldsymbol{\lambda}},\Theta}}{}$ and $\alpha<1$ (and more
generally when $\mu\in\mathrm{M}_{1}({\mathsf{T}})$ and
$\alpha\in\mathbb{R}$).

##  4 Power Descent and Entropic Mirror Descent

Recall from Section 2 that the Power Descent is defined for all
$\alpha\in\mathbb{R}\setminus\left\\{1\right\\}$. In this section, we first
establish in Section 4 that the Power Descent can be extended to the case
$\alpha=1$ and that we recover an Entropic Mirror Descent, showing that a
deeper connection runs between the two approaches beyond the one identified by
the $(\alpha,\Gamma)$-descent framework. This result relies on typical
convergence and differentiability assumptions summarised in (D1) and which are
deferred to Section C.1, alongside with the proof of Section 4.

######  Proposition  (Limiting case $\alpha\to 1$).

Assume (A1) and (D1). Then, for all continuous and bounded real-valued
functions $h$ on ${\mathsf{T}}$, we have that

$\lim_{\alpha\to
1}[\mathcal{I}_{\alpha}(\mu)](h)=[\mathcal{I}_{1}(\mu)](h)\;,$

where for all $\mu\in\mathrm{M}_{1}({\mathsf{T}})$ and all
$\theta\in{\mathsf{T}}$, we have set

$\displaystyle\mathcal{I}_{1}(\mu)(\mathrm{d}\theta)=\frac{\mu(\mathrm{d}\theta)e^{-\eta{b_{\mu,1}}(\theta)}}{\mu\left(e^{-\eta{b_{\mu,1}}}\right)}\quad\mbox{and}\quad{b_{\mu,1}}(\theta)=\int_{\mathsf{Y}}k(\theta,y)\log\left(\frac{\mu
k(y)}{p(y)}\right)\nu(\mathrm{d}y)\;.$ (6)

Here, we recognise the one-step transition associated to the Entropic Mirror
Descent applied to $\Psi_{1}$. This algorithm is a special case of [17] with
$\Gamma(v)=e^{-\eta v}$ and $\alpha=1$ and as such, it is known to lead to a
systematic decrease in the forward Kullback-Leibler divergence and to enjoy an
$O(1/N)$ convergence rate under the assumptions that (4) holds and
$\eta\in(0,1)$ [17, Theorem 3].

We have thus obtained that the Power Descent coincides exactly with the
Entropic Mirror Descent applied to $\Psi_{1}$ when $\alpha=1$ and we now focus
on understanding the links between Power Descent and Entropic Mirror Descent
when $\alpha\in\mathbb{R}\setminus\left\\{1\right\\}$. For this purpose, let
$\kappa$ be such that $(\alpha-1)\kappa\geqslant 0$ and let us study first-
order approximations of the Power Descent and the Entropic Mirror Descent
applied to $\Psi_{\alpha}$ when
${b_{\mu_{n},\alpha}}(\theta)\approx\mu_{n}({b_{\mu_{n},\alpha}})$ for all
$\theta\in{\mathsf{T}}$.

Letting $\eta>0$, we have that the update formula for the Power Descent is
given by

$\mu_{n+1}(\mathrm{d}\theta)=\frac{\mu_{n}(\mathrm{d}\theta)\left[(\alpha-1)({b_{\mu_{n},\alpha}}(\theta)+\kappa)+1\right]^{\frac{\eta}{1-\alpha}}}{\mu_{n}(\left[(\alpha-1)({b_{\mu_{n},\alpha}}+\kappa)+1\right]^{\frac{\eta}{1-\alpha}})}\;,\quad
n\in\mathbb{N}^{\star}\;.$

Now using the first order approximation $u^{\frac{\eta}{1-\alpha}}\approx
v^{\frac{\eta}{1-\alpha}}-\frac{\eta}{\alpha-1}v^{\frac{\eta}{1-\alpha}-1}(u-v)$
with
$u=\frac{(\alpha-1)({b_{\mu_{n},\alpha}}(\theta)+\kappa)+1}{(\alpha-1)(\mu({b_{\mu_{n},\alpha}})+\kappa)+1}$
and $v=1$, we can deduce the following approximated update formula

$\mu_{n+1}(\mathrm{d}\theta)=\mu_{n}(\mathrm{d}\theta)\left[1-\frac{\eta}{\alpha-1}\frac{{b_{\mu_{n},\alpha}}(\theta)-\mu_{n}({b_{\mu_{n},\alpha}})}{\mu_{n}({b_{\mu_{n},\alpha}})+\kappa+1/(\alpha-1)}\right]\;,\quad
n\in\mathbb{N}^{\star}\;.$

Letting $\eta^{\prime}>0$, the update formula for the Entropic Mirror Descent
applied to $\Psi_{\alpha}$ can be written as

$\displaystyle\mu_{n+1}(\mathrm{d}\theta)=\frac{\mu_{n}(\mathrm{d}\theta)\exp\left[-\eta^{\prime}({b_{\mu_{n},\alpha}}(\theta)+\kappa)\right]}{\mu_{n}(\exp\left[-\eta^{\prime}({b_{\mu_{n},\alpha}}+\kappa)\right])}\;,\quad
n\in\mathbb{N}^{\star}\;,$ (7)

and we obtain in a similar fashion that an approximated version of this
iterative scheme is

$\mu_{n+1}(\mathrm{d}\theta)=\mu_{n}(\mathrm{d}\theta)\left[1-\eta^{\prime}\left({b_{\mu_{n},\alpha}}(\theta)-\mu_{n}({b_{\mu_{n},\alpha}})\right)\right]\;,\quad
n\in\mathbb{N}^{\star}\;.$

Thus, for the two approximated formulas above to coincide, we need to set
$\eta^{\prime}=\eta\left[(\alpha-1)(\mu_{n}({b_{\mu_{n},\alpha}})+\kappa)+1\right]^{-1}$.
Now coming back to (7), we see that this leads us to consider the update
formula given by

$\displaystyle\mu_{n+1}(\mathrm{d}\theta)=\frac{\mu_{n}(\mathrm{d}\theta)\exp\left[-\eta\frac{{b_{\mu_{n},\alpha}}(\theta)}{(\alpha-1)(\mu_{n}({b_{\mu_{n},\alpha}})+\kappa)+1}\right]}{\mu_{n}\left(\exp\left[-\eta\frac{{b_{\mu_{n},\alpha}}}{(\alpha-1)(\mu_{n}({b_{\mu_{n},\alpha}})+\kappa)+1}\right]\right)}\;,\quad
n\in\mathbb{N}^{\star}\;.$ (8)

Observe then that (8) can again be seen as an Entropic Mirror Descent, but
applied this time to the objective function defined for all
$\alpha\in\mathbb{R}\setminus\left\\{0,1\right\\}$ by

$\displaystyle\Psi_{\alpha}^{AR}(\mu)$
$\displaystyle:=\frac{1}{\alpha(\alpha-1)}\log\left(\int_{\mathsf{Y}}\mu
k(y)^{\alpha}p(y)^{1-\alpha}\nu(\mathrm{d}y)+(\alpha-1)\kappa\right)\;,$

meaning we have applied the monotonic transformation

$u\mapsto\frac{1}{\alpha(\alpha-1)}\log\left(\alpha(\alpha-1)u+\alpha+(1-\alpha)\int_{\mathsf{Y}}p(y)\nu(\mathrm{d}y)+(\alpha-1)\kappa\right)$

to the initial objective function $\Psi_{\alpha}$ (see Section C.2 for the
derivation of (8) based on the objective function $\Psi_{\alpha}^{AR}$).
Hence, in the spirit of Renyi’s $\alpha$-divergence gradient-based methods for
Variational Inference (e.g [9, 10]), we can motivate the iterative scheme (8)
by observing that we recover the Variational Renyi bound introduced in [10] up
to a constant $-\alpha^{-1}$ when we let $p=p(\cdot,\mathscr{D})$, $\kappa=0$
and $\alpha>0$ in $\Psi_{\alpha}^{AR}$. For this reason we call the algorithm
given by (8) the Renyi Descent thereafter.

Contrary to the Entropic Mirror Descent applied to $\Psi_{\alpha}$, the Renyi
Descent now shares the same first-order approximation as the Power Descent.
This might explain why the behavior of the Entropic Mirror Descent applied to
$\Psi_{\alpha}$ and of the Power Descent differed greatly when $\alpha<1$ in
the numerical experiments from [17] despite their theoretical connection
through the $(\alpha,\Gamma)$-descent framework (the former performing poorly
numerically compared to the later as the dimension increased).

Strikingly, we can prove an $O(1/N)$ convergence rate towards the global
optimum for the Renyi Descent. Letting $\kappa^{\prime}\in\mathbb{R}$,
denoting by $\mathrm{Dom}_{\alpha}^{AR}$ an interval of $\mathbb{R}$ such that
for all $\theta\in{\mathsf{T}}$ and all $\mu\in\mathrm{M}_{1}({\mathsf{T}})$,

$\frac{{b_{\mu,\alpha}}(\theta)+1/(\alpha-1)}{(\alpha-1)(\mu({b_{\mu,\alpha}})+\kappa)+1}+\kappa^{\prime}\quad\mbox{and}\quad\frac{\mu({b_{\mu,\alpha}})+1/(\alpha-1)}{(\alpha-1)(\mu({b_{\mu,\alpha}})+\kappa)+1}+\kappa^{\prime}\in\mathrm{Dom}_{\alpha}^{AR}$

and introducing the assumption on $\eta$

  1. (A4)

For all $v\in\mathrm{Dom}_{\alpha}^{AR}$,
$1-\eta(\alpha-1)(v-\kappa^{\prime})\geqslant 0$.

we indeed have the following convergence result.

######  Theorem 3.

Assume (A1) and (A4). Let $\alpha\in\mathbb{R}\setminus\left\\{1\right\\}$ and
let $\kappa$ be such that $(\alpha-1)\kappa>0$. Define
$|B|_{\infty,\alpha}:=\sup_{\theta\in{\mathsf{T}},\mu\in\mathrm{M}_{1}({\mathsf{T}})}|{b_{\mu,\alpha}}(\theta)+1/(\alpha-1)|$
and assume that $|B|_{\infty,\alpha}<\infty$. Moreover, let
$\mu_{1}\in\mathrm{M}_{1}({\mathsf{T}})$ be such that
$\Psi_{\alpha}(\mu_{1})<\infty$. Then, the following assertions hold.

  1. (i)

The sequence $(\mu_{n})_{n\in\mathbb{N}^{\star}}$ defined by (8) is well-
defined and the sequence $(\Psi_{\alpha}(\mu_{n}))_{n\in\mathbb{N}^{\star}}$
is non-increasing.

  2. (ii)

For all $N\in\mathbb{N}^{\star}$, we have

$\displaystyle\Psi_{\alpha}(\mu_{N})-\Psi_{\alpha}(\mu^{\star})\leqslant\frac{L_{\alpha,2}}{N}\left[KL(\mu^{\star}||\mu_{1})+L\frac{L_{\alpha,3}}{L_{\alpha,1}(\alpha-1)\kappa}\Delta_{1}\right]\;,$
(9)

where $\mu^{\star}$ is such that
$\Psi_{\alpha}(\mu^{\star})=\inf_{\zeta\in\mathrm{M}_{1,\mu_{1}}({\mathsf{T}})}\Psi_{\alpha}(\zeta)$,
$\mathrm{M}_{1,\mu_{1}}({\mathsf{T}})$ denotes the set of probability measures
dominated by $\mu_{1}$,
$KL(\mu^{\star}||\mu_{1})=\int_{\mathsf{T}}\log\left(\mathrm{d}\mu^{\star}/\mathrm{d}\mu_{1}\right)\mathrm{d}\mu^{\star}$,
$\Delta_{1}=\Psi_{\alpha}(\mu_{1})-\Psi_{\alpha}(\mu^{\star})$ and
$L_{\alpha,2}$, $L$, $L_{\alpha,3}$, $L_{\alpha,1}$ are finite constants
defined in (C.3).

The proof of this result is deferred to Section C.3 and we present in the next
example an application of this theorem to the particular case of mixture
models.

######  Example 2.

Let $\alpha\in\mathbb{R}\setminus\left\\{1\right\\}$, let
$J\in\mathbb{N}^{\star}$, let
$\Theta=(\theta_{1},\ldots,\theta_{J})\in{\mathsf{T}}^{J}$, let
$\mu_{1}=J^{-1}\sum_{j=1}^{J}\delta_{\theta_{j}}$ and let
$\mathrm{Dom}_{\alpha}^{AR}=[-\frac{|B|_{\infty,\alpha}}{(\alpha-1)\kappa}+\kappa^{\prime},\frac{|B|_{\infty,\alpha}}{(\alpha-1)\kappa}+\kappa^{\prime}]$
with $\kappa^{\prime}\in\mathbb{R}$. In addition, assume that
$1-\eta|\kappa|^{-1}|B|_{\infty,\alpha}>0$. Then, taking
$\kappa^{\prime}=-3\frac{|B|_{\infty,\alpha}}{(\alpha-1)\kappa}$, we obtain

$\Psi_{\alpha}(\mu_{N})-\Psi_{\alpha}(\mu^{\star})\leqslant\frac{|\alpha-1|(|B|_{\infty,\alpha}+|\kappa|)}{N}\left[\frac{\log
J}{\eta}+\frac{\sqrt{2\log(J)}|B|_{\infty,\alpha}}{(\alpha-1)\kappa(1-\eta|\kappa|^{-1}|B|_{\infty,\alpha})}\right]\;,$

where we have used that $KL(\mu^{\star}||\mu_{1})\leqslant\log J$,
$\Delta_{1}\leqslant\sqrt{2\log J}|B|_{\infty,\alpha}$ and that the constants
defined in (C.3) satisfy
$L_{\alpha,2}=\eta^{-1}|\alpha-1|(|B|_{\infty,\alpha}+|\kappa|)$,
$L=\eta^{2}e^{\eta\frac{|B|_{\infty,\alpha}}{(\alpha-1)\kappa}-\eta\kappa^{\prime}}$,
$L_{\alpha,3}=e^{\eta\frac{|B|_{\infty,\alpha}}{(\alpha-1)\kappa}+\eta\kappa^{\prime}}$
and $L_{\alpha,1}=(1-\eta|\kappa|^{-1}|B|_{\infty,\alpha})\eta
e^{-\eta\frac{|B|_{\infty,\alpha}}{(\alpha-1)\kappa}-\eta\kappa^{\prime}}$.

To put things into perspective, notice that the Renyi Descent enjoys an
$O(1/\sqrt{N})$ convergence rate as a Entropic Mirror Descent algorithm for
the sequence
$(\Psi_{\alpha}(N^{-1}\sum_{n=1}^{N}\mu_{n}))_{N\in\mathbb{N}^{\star}}$ under
our assumptions when $\eta$ is proportional to $1/\sqrt{N}$, $N$ being fixed
(see [22] or [23, Theorem 4.2.]).

The improvement thus lies in the fact that deriving an $O(1/N)$ convergence
rate usually requires stronger smoothness assumptions on $\Psi_{\alpha}$ [23,
Theorem 6.2] that we do not assume in 3. Furthermore, due to the monotonicity
property, our result only involves the measure $\mu_{N}$ at time $N$ while
typical Entropic Mirror Result are expressed in terms of the average
$N^{-1}\sum_{n=1}^{N}\mu_{n}$.

Finally, observe that the Renyi Descent becomes feasible in practice for any
choice of kernel $K$ by letting $\mu$ be a weighted sum of Dirac measures i.e
$\mu={\mu_{{\boldsymbol{\lambda}},\Theta}}{}$ and by resorting to an unbiased
estimate of $({b_{\mu,\alpha}}(\theta_{j}))_{1\leqslant j\leqslant J}$ (see
Algorithm 4 of Section C.4).

The theoretical results we have obtained are summarised in Table 1 and we next
move on to numerical experiments.

Table 1: Summary of the theoretical results obtained in this paper compared to [17] | Power Descent | Renyi Descent
---|---|---
[17] |  $\alpha<1$: convergence under restrictive assumptions; | not covered
|  $\alpha>1$: $O(1/N)$ convergence rate |
This paper |  $\alpha<1$: full proof of convergence for mixture weights; | $O(1/N)$
| extension to $\alpha=1$ with $O(1/N)$ convergence rate | convergence rate

##  5 Simulation study

Let the target $p$ be a mixture density of two $d$-dimensional Gaussian
distributions multiplied by a positive constant $c$ such that
$p(y)=c\times\left[0.5\mathcal{N}(\boldsymbol{y};-s\boldsymbol{u_{d}},\boldsymbol{I_{d}})+0.5\mathcal{N}(\boldsymbol{y};s\boldsymbol{u_{d}},\boldsymbol{I_{d}})\right]$,
where $\boldsymbol{u_{d}}$ is the $d$-dimensional vector whose coordinates are
all equal to $1$, $s=2$, $c=2$ and $\boldsymbol{I_{d}}$ is the identity
matrix. Given $J\in\mathbb{N}^{\star}$, the approximating family is described
by

$\left\\{y\mapsto\mu_{{\boldsymbol{\lambda}}}k_{h}(y)=\sum_{j=1}^{J}\lambda_{j}k_{h}(y-\theta_{j})\;:\;{\boldsymbol{\lambda}}\in\mathcal{S}_{J},\theta_{1},\ldots,\theta_{J}\in{\mathsf{T}}\right\\}\;,$

where $K_{h}$ is a Gaussian transition kernel with bandwidth $h$ and $k_{h}$
denotes its associated kernel density.

Since the Power Descent and the Renyi Descent operate only on the mixture
weights ${\boldsymbol{\lambda}}$ of $\mu_{{\boldsymbol{\lambda}}}k_{h}$ during
the optimisation, a fully adaptive algorithm can be obtained by alternating
$T$ times between an Exploitation step where the mixture weights are optimised
and an Exploration step where the $\theta_{1},\ldots,\theta_{J}$ are updated,
as written in Algorithm 2.

Input: $p$: measurable positive function, $\alpha$: $\alpha$-divergence
parameter, $q_{0}$: initial sampler, $K_{h}$: Gaussian transition kernel, $T$:
total number of iterations, $J$: dimension of the parameter set.

Output: Optimised weights ${\boldsymbol{\lambda}}$ and parameter set $\Theta$.

Draw $\theta_{1,1},\ldots,\theta_{J,1}$ from $q_{0}$.

for  _$t=1\ldots T$_ do

  1. Exploitation step : Set $\Theta=\\{\theta_{1,t},\ldots,\theta_{J,t}\\}$. Perform the Power Descent or Renyi Descent and obtain the optimised mixture weights ${\boldsymbol{\lambda}}$.

  2. Exploration step : Perform any exploration step of our choice and obtain $\theta_{1,t+1},\ldots,\theta_{J,t+1}$.

Algorithm 2 Complete Exploitation-Exploration Algorithm

Many choices of Exploration step can be envisioned in Algorithm 2 since there
is no constraint on $\left\\{\theta_{1},\ldots,\theta_{J}\right\\}$. Here, we
consider the same Exploration step as the one they used in [17]: $h$ is set to
be proportional to $J^{-1/(4+d)}$ and the particles are updated by i.i.d
sampling according to ${\mu_{{\boldsymbol{\lambda}},\Theta}}{}k_{h}$ (and we
refer to Section C.5 for some details about alternative possible choices of
Exploration step).

As for the Power Descent and Renyi Descent, we perform $N$ transitions of
these algorithms at each time $t=1\ldots T$ according to Algorithm 3 and 4, in
which the initial weights are set to be $[1/J,\ldots,1/J]$,
$\eta=\eta_{0}/\sqrt{N}$ with $\eta_{0}>0$ and $M$ samples are used in the
estimation of
$({b_{{\mu_{{\boldsymbol{\lambda}},\Theta}}{},\alpha}}(\theta_{j,t}))_{1\leqslant
J}$ at each iteration $n=1\ldots N$. We take $J=100$,
$M\in\left\\{100,1000,2000\right\\}$, $\alpha=0.5$, $\kappa=0$, $\eta_{0}=0.3$
and the initial particles $\theta_{1},\ldots,\theta_{J}$ are sampled from a
centered normal distribution $q_{0}$ with covariance matrix
$5\boldsymbol{I_{d}}$. We let $T=10$, $N=20$ and we replicate the experiment
100 times independently in dimension $d=16$ for each algorithm. The
convergence is assessed using a Monte Carlo estimate of the Variational Renyi
bound introduced in [10] (which requires next to none additional
computations).

The results for the Power Descent and the Renyi Descent are displayed on
Figure 1 below and we add the Entropic Mirror Descent applied to
$\Psi_{\alpha}$ as a reference.

Figure 1: Plotted is the average Variational Renyi bound for the Power Descent (PD), the Renyi Descent (RD) and the Entropic Mirror Descent applied to $\Psi_{\alpha}$ (EMD) in dimension $d=16$ computed over 100 replicates with $\eta_{0}=0.3$ and $\alpha=0.5$ and an increasing number of samples $M$. |  |
---|---|---

We then observe that the Renyi Descent is indeed better-behaved compared to
the Entropic Mirror Descent applied to $\Psi_{\alpha}$, which fails in
dimension $16$. Furthermore, it matches the performances of the Power Descent
as $M$ increases in our numerical experiment, which illustrates the link
between the two algorithms we have established in the previous section.

##### Discussion

From a theoretical standpoint, no convergence rate is yet available for the
Power Descent algorithm when $\alpha<1$. An advantage of the novel Renyi
Descent algorithm is then that while being close to the Power Descent, it also
benefits from the Entropic Mirror Descent optimisation literature and as such
$O(1/\sqrt{N})$ convergence rates hold, which we have been able to improve to
$O(1/N)$ convergence rates.

A practical use of the Power Descent and of the Renyi Descent algorithms
requires approximations to handle intractable integrals appearing in the
update formulas so that the Power Descent applies the function
$\Gamma(v)=[(\alpha-1)v+1]^{\eta/(1-\alpha)}$ to an unbiased estimator of the
translated gradient ${b_{\mu,\alpha}}(\theta)+\kappa$ before renormalising,
while the the Renyi Descent applies the Entropic Mirror Descent function
$\Gamma(v)=e^{-\eta v}$ to a biased estimator of
${b_{\mu_{n},\alpha}}(\theta)/(\mu_{n}({b_{\mu_{n},\alpha}})+\kappa+1/(\alpha-1))$
before renormalising.

Finding which approach is most suitable between biased and unbiased
$\alpha$-divergence minimisation is still an open issue in the literature,
both theoretically and empirically [15, 16, 19]. Due to the exponentiation,
considering the $\alpha$-divergence instead of Renyi’s $\alpha$-divergence has
for example been said to lead to high-variance gradients [11, 10] and low
Signal-to-Noise ratio when $\alpha\neq 0$ [16] during the stochastic gradient
descent optimization.

In that regard, our work sheds light on additional links between unbiased and
biased $\alpha$-divergence methods beyond the framework of stochastic gradient
descent algorithms, as both the unbiased Power Descent and the biased Renyi
Descent share the same first order approximation.

##  6 Conclusion

We investigated algorithms that can be used to perform mixture weights
optimisation for $\alpha$-divergence minimisation regardless of how the
mixture parameters are obtained. We have established the full proof of the
convergence of the Power Descent algorithm in the case $\alpha<1$ when we
consider mixture models and bridged the gap with the case $\alpha=1$. We also
introduced a closely-related algorithm called the Renyi Descent. We proved it
enjoys an $O(1/N)$ convergence rate and illustrated in practice the proximity
between these two algorithms when the number of samples $M$ increases.

Further work could include establishing theoretical results regarding the
stochastic version of these two algorithms, as well as providing complementary
empirical results comparing the performances of the unbiased
$\alpha$-divergence-based Power Descent algorithm to those of the biased
Renyi’s $\alpha$-divergence-based Renyi Descent.

## References

  * [1] Michael I. Jordan, Zoubin Ghahramani, Tommi S. Jaakkola, and Lawrence K. Saul.  An introduction to variational methods for graphical models.  Machine Learning, 37(2):183–233, 1999.
  * [2] Matthew James. Beal.  Variational algorithms for approximate bayesian inference.  PhD thesis, 01 2003.
  * [3] Matthew D. Hoffman, David M. Blei, Chong Wang, and John Paisley.  Stochastic variational inference.  Journal of Machine Learning Research, 14(4):1303–1347, 2013.
  * [4] Tom Minka.  Divergence measures and message passing.  Technical Report MSR-TR-2005-173, January 2005.
  * [5] Huaiyu Zhu and Richard Rohwer.  Information geometric measurements of generalisation.  Technical Report NCRG/4350, Aug 1995.
  * [6] Huaiyu Zhu and Richard Rohwer.  Bayesian invariant measurements of generalization.  Neural Processing Letters, 2:28–31, December 1995.
  * [7] Alfréd Rényi.  On measures of entropy and information.  In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, pages 547–561, Berkeley, Calif., 1961. University of California Press.
  * [8] Tim van Erven and Peter Harremoes.  Rényi divergence and kullback-leibler divergence.  IEEE Transactions on Information Theory, 60(7):3797–3820, Jul 2014\.
  * [9] Jose Hernandez-Lobato, Yingzhen Li, Mark Rowland, Thang Bui, Daniel Hernandez-Lobato, and Richard Turner.  Black-box alpha divergence minimization.  In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 1511–1520, New York, New York, USA, 20–22 Jun 2016. PMLR.
  * [10] Yingzhen Li and Richard E Turner.  Rényi divergence variational inference.  In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29, pages 1073–1081. Curran Associates, Inc., 2016.
  * [11] Adji Bousso Dieng, Dustin Tran, Rajesh Ranganath, John Paisley, and David Blei.  Variational inference via \chi upper bound minimization.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 2732–2741. Curran Associates, Inc., 2017.
  * [12] Volodymyr Kuleshov and Stefano Ermon.  Neural variational inference and learning in undirected graphical models.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
  * [13] Robert Bamler, Cheng Zhang, Manfred Opper, and Stephan Mandt.  Perturbative black box variational inference.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 5079–5088. Curran Associates, Inc., 2017.
  * [14] Dilin Wang, Hao Liu, and Qiang Liu.  Variational inference with tail-adaptive f-divergence.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 5737–5747. Curran Associates, Inc., 2018.
  * [15] Tomas Geffner and Justin Domke.  Empirical evaluation of biased methods for alpha divergence minimization.  In 3rd Symposium on Advances in Approximate Bayesian Inference, pages 1–12, 2020.
  * [16] Tomas Geffner and Justin Domke.  On the difficulty of unbiased alpha divergence minimization.  arXiv preprint arXiv:2010.09541, 2020.
  * [17] Kamélia Daudel, Randal Douc, and François Portier.  Infinite-dimensional gradient-based descent for alpha-divergence minimisation.  To appear in the Annals of Statistics, 2021.
  * [18] Kamélia Daudel, Randal Douc, and François Roueff.  Monotonic alpha-divergence minimisation.  arXiv preprint arxiv:2103.05684, 2021.
  * [19] Akash Kumar Dhaka, Alejandro Catalina, Manushi Welandawe, Michael Riis Andersen, Jonathan Huggins, and Aki Vehtari.  Challenges and opportunities in high-dimensional variational inference.  arxiv preprint arxiv:2103.01085, 2021.
  * [20] Arnaud Doucet, Nando Freitas, Kevin Murphy, and Stuart Russell.  Sequential monte carlo methods in practice.  01 2013.
  * [21] Andrzej Cichocki and Shun-ichi Amari.  Families of alpha- beta- and gamma- divergences: Flexible and robust measures of similarities.  Entropy, 12(6):1532–1568, Jun 2010.
  * [22] Amir Beck and Marc Teboulle.  Mirror descent and nonlinear projected subgradient methods for convex optimization.  Operations Research Letters, 31(3):167 – 175, 2003.
  * [23] Sébastien Bubeck.  Convex optimization: Algorithms and complexity.  Foundations and Trends® in Machine Learning, 8(3-4):231–357, 01 2015.

## Appendix A

###  A.1 Equivalence between (1) and (2) with $p(y)=p(y,\mathscr{D})$

  * •

Case $\alpha=1$ with $f_{1}(u)=1-u+u\log(u)$ for all $u>0$. Then,

$\displaystyle D_{1}(\mu K||\mathbb{P})$
$\displaystyle=\int_{\mathsf{Y}}f_{1}\left(\frac{\mu
k(y)}{p(y|\mathscr{D})}\right)p(y|\mathscr{D})\nu(\mathrm{d}y)$
$\displaystyle=\int_{\mathsf{Y}}\mu k(y)\log\left(\frac{\mu
k(y)}{p(y|\mathscr{D})}\right)\nu(\mathrm{d}y)+0$
$\displaystyle=\int_{\mathsf{Y}}\mu k(y)\log\left(\frac{\mu
k(y)}{p(y,\mathscr{D})}\right)\nu(\mathrm{d}y)+\log p(\mathscr{D})$
$\displaystyle=\int_{\mathsf{Y}}f_{1}\left(\frac{\mu
k(y)}{p(y,\mathscr{D})}\right)p(y,\mathscr{D})\nu(\mathrm{d}y)+1-p(\mathscr{D})+\log
p(\mathscr{D})$

Thus,

$\mathrm{arginf}_{\mu\in\mathsf{M}}D_{1}(\mu
K||\mathbb{P})=\mathrm{arginf}_{\mu\in\mathsf{M}}\Psi_{1}(\mu;p)\quad\mbox{with}\quad
p(y)=p(y,\mathscr{D})$

  * •

Case $\alpha=0$ with $f_{0}(u)=u-1-\log(u)$ for all $u>0$.

$\displaystyle D_{0}(\mu K||\mathbb{P})$
$\displaystyle=\int_{\mathsf{Y}}f_{0}\left(\frac{\mu
k(y)}{p(y|\mathscr{D})}\right)p(y|\mathscr{D})\nu(\mathrm{d}y)$
$\displaystyle=\int_{\mathsf{Y}}-\log\left(\frac{\mu
k(y)}{p(y|\mathscr{D})}\right)p(y|\mathscr{D})\nu(\mathrm{d}y)$
$\displaystyle=\int_{\mathsf{Y}}-\log\left(\frac{\mu
k(y)}{p(y,\mathscr{D})}\right)p(y|\mathscr{D})\nu(\mathrm{d}y)-\log
p(\mathscr{D})$
$\displaystyle=\frac{1}{p(\mathscr{D})}\left[\int_{\mathsf{Y}}f_{1}\left(\frac{\mu
k(y)}{p(y,\mathscr{D})}\right)p(y,\mathscr{D})\nu(\mathrm{d}y)+p(\mathscr{D})-1-p(\mathscr{D})\log
p(\mathscr{D})\right]$

Thus

$\mathrm{arginf}_{\mu\in\mathsf{M}}D_{0}(\mu
K||\mathbb{P})=\mathrm{arginf}_{\mu\in\mathsf{M}}\Psi_{0}(\mu;p)\quad\mbox{with}\quad
p(y)=p(y,\mathscr{D})$

  * •

Case $\alpha\in\mathbb{R}\setminus\left\\{1\right\\}$ with
$f_{\alpha}(u)=\frac{1}{\alpha(\alpha-1)}\left[u^{\alpha}-1-\alpha(u-1)\right]$
for all $u>0$.

$\displaystyle D_{\alpha}(\mu K||\mathbb{P})$
$\displaystyle=\int_{\mathsf{Y}}f_{\alpha}\left(\frac{\mu
k(y)}{p(y|\mathscr{D})}\right)p(y|\mathscr{D})\nu(\mathrm{d}y)$
$\displaystyle=\int_{\mathsf{Y}}\frac{1}{\alpha(\alpha-1)}\left[\left(\frac{\mu
k(y)}{p(y|\mathscr{D})}\right)^{\alpha}-1\right]p(y|\mathscr{D})\nu(\mathrm{d}y)$
$\displaystyle=p(\mathscr{D})^{\alpha-1}\int_{\mathsf{Y}}\frac{1}{\alpha(\alpha-1)}\left[\left(\frac{\mu
k(y)}{p(y,\mathscr{D})}\right)^{\alpha}-1\right]p(y,\mathscr{D})\nu(\mathrm{d}y)+\frac{p(\mathscr{D})^{\alpha}-1}{\alpha(\alpha-1)}$
$\displaystyle=p(\mathscr{D})^{\alpha-1}\int_{\mathsf{Y}}f_{\alpha}\left(\frac{\mu
k(y)}{p(y,\mathscr{D})}\right)p(y,\mathscr{D})\nu(\mathrm{d}y)+\frac{\alpha
p(\mathscr{D})^{\alpha-1}+(1-\alpha)p(\mathscr{D})^{\alpha}-1}{\alpha(\alpha-1)}$
(10)

Thus,

$\mathrm{arginf}_{\mu\in\mathsf{M}}D_{\alpha}(\mu
K||\mathbb{P})=\mathrm{arginf}_{\mu\in\mathsf{M}}\Psi_{\alpha}(\mu;p)\quad\mbox{with}\quad
p(y)=p(y,\mathscr{D})$

###  A.2 [17, Theorem 1] with $\Gamma(v)=[(\alpha-1)v+1]^{\eta/(1-\alpha)}$

######  Theorem 4 ([17, Theorem 1] with
$\Gamma(v)=[(\alpha-1)v+1]^{\eta/(1-\alpha)}$).

Assume that $p$ and $k$ are as in (A1). Let
$\alpha\in\mathbb{R}\setminus\left\\{1\right\\}$, let $\kappa$ be such that
$(\alpha-1)\kappa\geqslant 0$, let $\mu\in\mathrm{M}_{1}({\mathsf{T}})$ and
let $\eta\in(0,1]$ be such that

$\displaystyle 0<\mu(\Gamma({b_{\mu,\alpha}}+\kappa))<\infty\;$ (11)

holds and $\Psi_{\alpha}(\mu)<\infty$. Then, the two following assertions
hold.

  1. (i)

We have
$\Psi_{\alpha}\circ\mathcal{I}_{\alpha}(\mu)\leqslant\Psi_{\alpha}(\mu)$.

  2. (ii)

We have $\Psi_{\alpha}\circ\mathcal{I}_{\alpha}(\mu)=\Psi_{\alpha}(\mu)$ if
and only if $\mu=\mathcal{I}_{\alpha}(\mu)$.

## Appendix B

###  B.1 Proof that (A2) is satisfied in 1

###### Proof that (A2) is satisfied in 1.

We have $k_{h}(\theta,y)=\frac{e^{-\|y-\theta\|^{2}/(2h^{2})}}{(2\pi
h^{2})^{d/2}}$ and
$p(y)=c\times\left[0.5\frac{e^{-\|y-\theta^{\star}_{1}\|^{2}/2}}{(2\pi)^{d/2}}+0.5\frac{e^{-\|y-\theta^{\star}_{2}\|^{2}/2}}{(2\pi)^{d/2}}\right]$
for all $\theta\in{\mathsf{T}}$ and all $y\in\mathsf{Y}$. Recall that by
assumption ${\mathsf{T}}=\mathcal{B}(0,r)\subset\mathbb{R}^{d}$ with $r>0$.
Then, for all $\alpha\in[0,1)$, we are interested in proving

$\displaystyle\int_{\mathsf{Y}}{\sup_{\theta\in{\mathsf{T}}}k(\theta,y)}\times\sup_{\theta^{\prime}\in{\mathsf{T}}}\left(\frac{k(\theta^{\prime},y)}{p(y)}\right)^{\alpha-1}\nu(\mathrm{d}y)<\infty$
(12)

and

$\displaystyle\int_{\mathsf{Y}}\sup_{\theta\in{\mathsf{T}}}\left|\log\left(\frac{k_{h}(\theta,y)}{p(y)}\right)\right|p(y)\nu(\mathrm{d}y)<\infty\;.$
(13)

  1. (i)

We start by proving (12). First note that for all
$\theta,\theta^{\prime}\in{\mathsf{T}}$ and for all $y\in\mathsf{Y}$ we can
write

$\displaystyle\frac{k_{h}(\theta,y)}{k_{h}(\theta^{\prime},y)}$
$\displaystyle=e^{\frac{-\|y-\theta\|^{2}+\|y-\theta^{\prime}\|^{2}}{2h^{2}}}=e^{\frac{2<y,\theta-\theta^{\prime}>-\|\theta\|^{2}+\|\theta^{\prime}\|^{2}}{2h^{2}}}$
$\displaystyle\leqslant
e^{\frac{2|<y,\theta-\theta^{\prime}>|+\|\theta\|^{2}+\|\theta^{\prime}\|^{2}}{2h^{2}}}\leqslant
e^{\frac{\|y\|\|\theta-\theta^{\prime}\|+r^{2}}{h^{2}}}\;.$

from which we deduce that for all $\theta,\theta^{\prime}\in{\mathsf{T}}$ and
for all $y\in\mathsf{Y}$,

$\displaystyle\frac{k_{h}(\theta,y)}{k_{h}(\theta^{\prime},y)}\leqslant
e^{\frac{\|y\|2r+r^{2}}{h^{2}}}\;$ (14)

and that

$\int_{\mathsf{Y}}{\sup_{\theta\in{\mathsf{T}}}k(\theta,y)}\times\sup_{\theta^{\prime}\in{\mathsf{T}}}\left(\frac{k(\theta^{\prime},y)}{p(y)}\right)^{\alpha-1}\nu(\mathrm{d}y)\leqslant\int_{\mathsf{Y}}k(\theta,y)e^{\frac{\|y\|2r+r^{2}}{h^{2}}}\sup_{\theta^{\prime}\in{\mathsf{T}}}\left(\frac{k(\theta^{\prime},y)}{p(y)}\right)^{\alpha-1}\nu(\mathrm{d}y).$

Additionally, Jensen’s inequality applied to the concave function $u\mapsto
u^{1-\alpha}$ implies

$\displaystyle\int_{\mathsf{Y}}k(\theta,y)e^{\frac{\|y\|2r+r^{2}}{h^{2}}}\sup_{\theta^{\prime}\in{\mathsf{T}}}\left(\frac{k(\theta^{\prime},y)}{p(y)}\right)^{\alpha-1}\nu(\mathrm{d}y)$
$\displaystyle\leqslant\left(\int_{\mathsf{Y}}k(\theta,y)e^{\frac{\|y\|2r+r^{2}}{(1-\alpha)h^{2}}}\sup_{\theta^{\prime}\in{\mathsf{T}}}\frac{p(y)}{k(\theta^{\prime},y)}\nu(\mathrm{d}y)\right)^{1-\alpha}$
$\displaystyle\leqslant\left(\int_{\mathsf{Y}}\sup_{\theta,\theta^{\prime}\in{\mathsf{T}}}\frac{k_{h}(\theta,y)}{k_{h}(\theta^{\prime},y)}e^{\frac{\|y\|2r+r^{2}}{(1-\alpha)h^{2}}}p(y)\nu(\mathrm{d}y)\right)^{1-\alpha}$

Now using (14), we can deduce

$\int_{\mathsf{Y}}\sup_{\theta,\theta^{\prime}\in{\mathsf{T}}}\frac{k_{h}(\theta,y)}{k_{h}(\theta^{\prime},y)}e^{\frac{\|y\|2r+r^{2}}{(1-\alpha)h^{2}}}p(y)\nu(\mathrm{d}y)\leqslant\int_{\mathsf{Y}}e^{\frac{\|y\|2r+r^{2}}{h^{2}}(1+\frac{1}{1-\alpha})}p(y)\nu(\mathrm{d}y)<\infty\;,$

which yields the desired result.

  2. (ii)

We now prove (13). For all $y\in\mathsf{Y}$ and all $\theta\in{\mathsf{T}}$,
we have

$\displaystyle
e^{-\sup_{\theta\in{\mathsf{T}}}\frac{\|y-\theta\|^{2}}{2h^{2}}}\leqslant(2\pi
h^{2})^{d/2}k_{h}(\theta,y)\leqslant 1$ $\displaystyle
e^{-\max_{i\in\left\\{1,2\right\\}}\frac{\|y-\theta_{i}^{\star}\|^{2}}{2}}\leqslant
c^{-1}(2\pi)^{d/2}p(y)\leqslant 1$

and we can deduce for all $y\in\mathsf{Y}$ and all $\theta\in{\mathsf{T}}$

$\displaystyle\left|\log\left(\frac{k_{h}(\theta,y)}{p(y)}\right)\right|$
$\displaystyle\leqslant\sup_{\theta\in{\mathsf{T}}}\frac{\|y-\theta\|^{2}}{2h^{2}}+\max_{i\in\left\\{1,2\right\\}}\frac{\|y-\theta_{i}^{\star}\|^{2}}{2}+d|\log
h|+|\log c|$
$\displaystyle\leqslant\frac{(\|y\|+r)^{2}}{2}\left[\frac{1}{h^{2}}+1\right]+d|\log
h|+|\log c|\;.$ (15)

Since we have

$\int_{\mathsf{Y}}\left(\frac{(\|y\|+r)^{2}}{2}\left[\frac{1}{h^{2}}+1\right]+d|\log
h|+|\log c|\right)p(y)\nu(\mathrm{d}y)<\infty$

we deduce that (13) holds.

∎

###  B.2 Proof of 2

We start with some preliminary results. Let
$\zeta,\zeta^{\prime}\in\mathrm{M}_{1}({\mathsf{T}})$. Recall that we say that
$\zeta\mathcal{R}\zeta^{\prime}$ if and only if $\zeta K=\zeta^{\prime}K$ and
that $\mathrm{M}_{1,\zeta}({\mathsf{T}})$ denotes the set of probability
measures dominated by $\zeta$.

######  Lemma .

Assume (A1). Let $\mathsf{M}$ be a convex subset of
$\mathrm{M}_{1}({\mathsf{T}})$ and let
$\zeta_{1},\zeta_{2}\in\mathrm{M}_{1}({\mathsf{T}})$ be such that

$\Psi_{\alpha}(\zeta_{1})=\Psi_{\alpha}(\zeta_{2})=\inf_{\zeta\in\mathsf{M}}\Psi_{\alpha}(\zeta).$

Then, we have $\zeta_{1}\mathcal{R}\zeta_{2}$.

###### Proof.

For all $y\in\mathsf{Y}$, set $u_{y}=\zeta_{1}k(y)/p(y)$ and
$v_{y}=\zeta_{2}k(y)/p(y)$. Then, for all $y\in\mathsf{Y}$ and for all
$t\in(0,1)$, $f_{\alpha}(tu_{y}+(1-t)v_{y})\leqslant
tf_{\alpha}(u_{y})+(1-t)f_{\alpha}(v_{y})$ by convexity of $f_{\alpha}$ and we
obtain

$\displaystyle\Psi_{\alpha}(t\zeta_{1}+(1-t)\zeta_{2})\leqslant
t\Psi_{\alpha}(\zeta_{1})+(1-t)\Psi_{\alpha}(\zeta_{2})=\inf_{\zeta\in\mathsf{M}}\Psi_{\alpha}(\zeta)\;.$
(16)

Furthermore, $t\zeta_{1}+(1-t)\zeta_{2}\in\mathsf{M}$ which implies that we
have equality in (16).

Consequently, for all $t\in(0,1)$ :

$\int_{\mathsf{Y}}\underbrace{\left[tf_{\alpha}(u_{y})+(1-t)f_{\alpha}(v_{y})-f_{\alpha}(tu_{y}+(1-t)v_{y})\right]}_{\geqslant
0}p(y)\nu(\mathrm{d}y)=0\;.$

Now using that $f_{\alpha}$ is strictly convex, we deduce that for $p$-almost
all $y\in\mathsf{Y}$, $\zeta_{1}k(y)=\zeta_{2}k(y)$ that is
$\zeta_{1}\mathcal{R}\zeta$. ∎

######  Lemma .

Assume (A1). Let $\alpha\in\mathbb{R}\setminus\left\\{1\right\\}$, let
$\kappa$ be such that $(\alpha-1)\kappa\geqslant 0$ and let
${\mu^{\star}}\in\mathrm{M}_{1}({\mathsf{T}})$ be a fixed point of
$\mathcal{I}_{\alpha}$. Then,

$\Psi_{\alpha}({\mu^{\star}})=\inf_{\zeta\in\mathrm{M}_{1,{\mu^{\star}}}({\mathsf{T}})}\Psi_{\alpha}(\zeta)\;.$
(17)

Furthermore, for all $\zeta\in\mathrm{M}_{1,{\mu^{\star}}}({\mathsf{T}})$,
$\Psi_{\alpha}({\mu^{\star}})=\Psi_{\alpha}(\zeta)$ implies that
${\mu^{\star}}\mathcal{R}\zeta$.

###### Proof.

Let $\zeta\in\mathrm{M}_{1,{\mu^{\star}}}({\mathsf{T}})$ be such that
$\Psi_{\alpha}(\zeta)\leqslant\Psi_{\alpha}({\mu^{\star}})$. We have that

$\displaystyle\zeta\left({b_{{\mu^{\star}},\alpha}}-{\mu^{\star}}({b_{{\mu^{\star}},\alpha}})\right)\leqslant\Psi_{\alpha}(\zeta)-\Psi_{\alpha}({\mu^{\star}})\leqslant
0\;.$ (18)

Furthermore, since ${\mu^{\star}}$ is a fixed point of $\mathcal{I}_{\alpha}$,
$\Gamma({b_{{\mu^{\star}},\alpha}}+\kappa)$, hence
$|{b_{{\mu^{\star}},\alpha}}+\kappa+1/(\alpha-1)|$ is ${\mu^{\star}}$-almost
all constant. In addition, ${b_{{\mu^{\star}},\alpha}}+\kappa+1/(\alpha-1)$ is
of constant sign by assumption on $\kappa$. Since $\zeta\preceq{\mu^{\star}}$,
we thus deduce that

$\displaystyle\zeta\left({b_{{\mu^{\star}},\alpha}}-{\mu^{\star}}({b_{{\mu^{\star}},\alpha}})\right)=0\;.$

Combining this result with (18) yields
$\Psi_{\alpha}(\zeta)=\Psi_{\alpha}({\mu^{\star}})$ and we recover (17).

Finally, assume there exists
$\zeta\in\mathrm{M}_{1,{\mu^{\star}}}({\mathsf{T}})$ such that
$\Psi_{\alpha}({\mu^{\star}})=\Psi_{\alpha}(\zeta)$. Then, since
$\mathrm{M}_{1,{\mu^{\star}}}({\mathsf{T}})$ is a convex set, we have by
Section B.2 that ${\mu^{\star}}\mathcal{R}\zeta$. ∎

We now move on to the proof of 2.

###### Proof of 2.

For convenience, we define the notation
$\Psi_{\alpha,\Theta}({\boldsymbol{\lambda}}):=\Psi_{\alpha}\left({\mu_{{\boldsymbol{\lambda}},\Theta}}\right)$
for all ${\boldsymbol{\lambda}}\in\mathcal{S}_{J}$. In this proof, we will use
the equivalence relation $\mathcal{R}$ defined by:
$\zeta\mathcal{R}\zeta^{\prime}$ if and only if $\zeta K=\zeta^{\prime}K$ and
we write $\mathrm{M}_{1,\zeta}({\mathsf{T}})$ the set of probability measures
dominated by $\zeta$.

  1. (i)

Any possible limit of convergent subsequence of
$({\boldsymbol{\lambda}_{n}})_{n\in\mathbb{N}^{\star}}$ is a fixed point of
$\mathcal{I}_{\alpha}^{\mathrm{mixt}}$.

First note that by (A3), we have that
$|\Psi_{\alpha,\Theta}({\boldsymbol{\lambda}})|<\infty$ and that (11) is
satisfied for all ${\mu_{{\boldsymbol{\lambda}},\Theta}}$ such that
${\boldsymbol{\lambda}}\in\mathcal{S}_{J}$. This means that the sequence
$({\boldsymbol{\lambda}_{n}})_{n\in\mathbb{N}^{\star}}$ defined by (5) is
well-defined, that the sequence
$(\Psi_{\alpha,\Theta}({\boldsymbol{\lambda}_{n}}))_{n\in\mathbb{N}^{\star}}$
is lower-bounded and that $\Psi_{\alpha,\Theta}({\boldsymbol{\lambda}_{n}})$
is finite for all $n\in\mathbb{N}^{\star}$. As
$(\Psi_{\alpha,\Theta}({\boldsymbol{\lambda}_{n}}))_{n\in\mathbb{N}^{\star}}$
is nonincreasing by 4-(i), it converges in $\mathbb{R}$ and in particular we
have

$\lim\limits_{n\to\infty}\Psi_{\alpha,\Theta}\circ\mathcal{I}_{\alpha}^{\mathrm{mixt}}({\boldsymbol{\lambda}_{n}})-\Psi_{\alpha,\Theta}({\boldsymbol{\lambda}_{n}})=0\;.$

Let $({\boldsymbol{\lambda}_{\varphi(n)}})_{n\in\mathbb{N}^{\star}}$ be a
convergent subsequence of
$({\boldsymbol{\lambda}_{n}})_{n\in\mathbb{N}^{\star}}$ and denote by
$\bar{{\boldsymbol{\lambda}}}$ its limit. Since the function
${\boldsymbol{\lambda}}\mapsto\Psi_{\alpha,\Theta}\circ\mathcal{I}_{\alpha}^{\mathrm{mixt}}({\boldsymbol{\lambda}})-\Psi_{\alpha,\Theta}({\boldsymbol{\lambda}})$
is continuous we obtain that
$\Psi_{\alpha,\Theta}\circ\mathcal{I}_{\alpha}^{\mathrm{mixt}}(\bar{{\boldsymbol{\lambda}}})=\Psi_{\alpha,\Theta}(\bar{{\boldsymbol{\lambda}}})$
and hence by 4-(ii), $\bar{{\boldsymbol{\lambda}}}$ is a fixed point of
$\mathcal{I}_{\alpha}^{\mathrm{mixt}}$.

  2. (ii)

The set
$F=\left\\{{\boldsymbol{\lambda}}\in\mathcal{S}_{J}\;:\;{\boldsymbol{\lambda}}=\mathcal{I}_{\alpha}^{\mathrm{mixt}}({\boldsymbol{\lambda}})\right\\}$
of fixed points of $\mathcal{I}_{\alpha}^{\mathrm{mixt}}$ is finite.

For any subset $R\subset\left\\{1,\ldots,J\right\\}$, define

$\displaystyle\mathcal{S}_{J,R}$
$\displaystyle=\left\\{{\boldsymbol{\lambda}}\in\mathcal{S}_{J}\;:\;\forall
i\in R^{c},\lambda_{i}=0,\forall j\in R^{c},\lambda_{j}\neq 0\right\\}\;,$
$\displaystyle\tilde{\mathcal{S}}_{J,R}$
$\displaystyle=\left\\{{\boldsymbol{\lambda}}\in\mathcal{S}_{J}\;:\;\forall
i\in R^{c},\lambda_{i}=0\right\\}\;,$

and write

$F=\bigcup\limits_{R\subset\\{1,\ldots,J\\}}(S_{J,R}\cap F)\;.$

In order to show that $F$ is finite, we prove by contradiction that for any
$R\subset\\{1,\ldots,J\\}$, $S_{J,R}\cap F$ contains at most one element.
Assume indeed the existence of two distinct elements
${\boldsymbol{\lambda}}\neq{\boldsymbol{\lambda^{\prime}}}$ belonging to
$S_{J,R}\cap F$. Since
$\mathrm{M}_{1,{\mu_{{\boldsymbol{\lambda}},\Theta}}}({\mathsf{T}})=\mathrm{M}_{1,{\mu_{{\boldsymbol{\lambda^{\prime}}},\Theta}}}({\mathsf{T}})=\left\\{{\mu_{{\boldsymbol{\lambda^{\prime\prime}}},\Theta}}\;:{\boldsymbol{\lambda^{\prime\prime}}}\in\tilde{\mathcal{S}}_{J,R}\right\\}$,
Section B.2 implies that

$\Psi_{\alpha,\Theta}({\boldsymbol{\lambda}})=\inf_{{\boldsymbol{\lambda^{\prime\prime}}}\in\tilde{\mathcal{S}}_{J,R}}\Psi_{\alpha,\Theta}\left({\boldsymbol{\lambda^{\prime\prime}}}\right)=\Psi_{\alpha,\Theta}({\boldsymbol{\lambda^{\prime}}})\;.$

Applying again Section B.2, we get
${\mu_{{\boldsymbol{\lambda}},\Theta}}\mathcal{R}{\mu_{{\boldsymbol{\lambda^{\prime}}},\Theta}}$,
that is,
${\mu_{{\boldsymbol{\lambda}},\Theta}}K={\mu_{{\boldsymbol{\lambda^{\prime}}},\Theta}}K$.
This means that
$\sum_{j=1}^{J}(\lambda_{j}-\lambda^{\prime}_{j})K(\theta_{j},\cdot)$ is the
null measure, which in turns implies the identity
${\boldsymbol{\lambda}}={\boldsymbol{\lambda^{\prime}}}$ since the family of
measures $\left\\{K(\theta_{1},\cdot),\ldots,K(\theta_{J},\cdot)\right\\}$ is
assumed to be linearly independent.

  3. (iii)

Conclusion.

According to Section B.2 applied to the convex subset of measures
$\mathsf{M}=\mathcal{S}_{J}$, the function $\Psi_{\alpha,\Theta}$ attains its
global infimum at a unique ${\boldsymbol{\lambda}_{\star}}\in\mathcal{S}_{J}$.
The uniqueness of ${\boldsymbol{\lambda}_{\star}}$ actually follows from the
fact that, as shown above,
${\mu_{{\boldsymbol{\lambda}},\Theta}}\mathcal{R}{\mu_{{\boldsymbol{\lambda^{\prime}}},\Theta}}$
if and only if ${\boldsymbol{\lambda}}={\boldsymbol{\lambda^{\prime}}}$. Then,
by 4-(i) and by definition of ${\boldsymbol{\lambda}_{\star}}$

$\Psi_{\alpha,\Theta}\circ\mathcal{I}_{\alpha}^{\mathrm{mixt}}({{\boldsymbol{\lambda}_{\star}}})\leqslant\Psi_{\alpha,\Theta}({{\boldsymbol{\lambda}_{\star}}})=\inf_{{\boldsymbol{\lambda}}^{\prime}\in\mathcal{S}_{J}}\Psi_{\alpha,\Theta}({\boldsymbol{\lambda}}^{\prime})\leqslant\Psi_{\alpha,\Theta}\circ\mathcal{I}_{\alpha}^{\mathrm{mixt}}({{\boldsymbol{\lambda}_{\star}}})\;,$

and hence,
$\Psi_{\alpha,\Theta}\circ\mathcal{I}_{\alpha}^{\mathrm{mixt}}({{\boldsymbol{\lambda}_{\star}}})=\Psi_{\alpha,\Theta}({{\boldsymbol{\lambda}_{\star}}})$,
showing that ${\boldsymbol{\lambda}_{\star}}\in F$ by 4-(ii). Since by (ii),
$F$ is finite, there exists $L\geqslant 1$ such that
$F=\left\\{{\boldsymbol{\lambda}}^{\ell}\;:1\leqslant\ell\leqslant
L\right\\}$, where for $i\neq j$,
${\boldsymbol{\lambda}}^{i}\neq{\boldsymbol{\lambda}}^{j}$. Without any loss
of generality, we set
${\boldsymbol{\lambda}}^{1}={\boldsymbol{\lambda}_{\star}}$ to simplify the
notation.

We now introduce a sequence $(W_{\ell})_{1\leqslant{\ell}\leqslant L}$ of
disjoint open neighborhoods of
$({\boldsymbol{\lambda}}^{\ell})_{1\leqslant\ell\leqslant L}$ such that for
any $\ell\in\\{1,\ldots,L\\}$,

$\mathcal{I}_{\alpha}^{\mathrm{mixt}}(W_{\ell})\cap\left(\bigcup_{j\neq\ell}W_{j}\right)=\emptyset$
(19)

This is possible since
$\mathcal{I}_{\alpha}^{\mathrm{mixt}}({\boldsymbol{\lambda}}^{\ell})={\boldsymbol{\lambda}}^{\ell}$
and
${\boldsymbol{\lambda}}\mapsto\mathcal{I}_{\alpha}^{\mathrm{mixt}}({\boldsymbol{\lambda}})$
is continuous.

By (i) , the set $F$ contains all the possible limits of any subsequence of
$({\boldsymbol{\lambda}_{n}})_{n\in\mathbb{N}^{\star}}$. As a consequence,
there exists $N>0$ such that for all $n\geqslant N$,
${\boldsymbol{\lambda}_{n}}\in\bigcup_{1\leqslant{\ell}\leqslant L}W_{\ell}$.
Combining with (19), there exists $\ell\in\\{1,\ldots,L\\}$ such that for all
$n\geqslant N$, ${\boldsymbol{\lambda}_{n}}\in W_{\ell}$. Therefore
${\boldsymbol{\lambda}}^{\ell}$ is the only possible limit of any convergent
subsequence of $({\boldsymbol{\lambda}_{n}})_{n\in\mathbb{N}^{\star}}$ and as
a consequence,
$\lim_{n\to\infty}{\boldsymbol{\lambda}_{n}}={\boldsymbol{\lambda}}^{\ell}$.

Thus, the sequence
$(\mu_{{\boldsymbol{\lambda}_{n}},\Theta})_{n\in\mathbb{N}^{\star}}$ weakly
converges to $\mu_{{\boldsymbol{\lambda}}^{\ell},\Theta}$ as $n\to\infty$ and
1 can be applied. Since ${\boldsymbol{\lambda}_{1}}\in\mathcal{S}_{J}^{+}$, we
have
$\mathrm{M}_{1,\mu_{{\boldsymbol{\lambda}_{1}},\Theta}}({\mathsf{T}})=\left\\{\mu_{{\boldsymbol{\lambda^{\prime}}},\Theta}\;:{\boldsymbol{\lambda^{\prime}}}\in\mathcal{S}_{J}\right\\}$
and 1-(iii) then shows that $\mu_{{\boldsymbol{\lambda}}^{\ell},\Theta}$ is
the global arginf of $\Psi_{\alpha}$ over all
$\left\\{\mu_{{\boldsymbol{\lambda^{\prime}}},\Theta}\;:{\boldsymbol{\lambda^{\prime}}}\in\mathcal{S}_{J}\right\\}$.
Therefore, $\ell=1$, i.e.,
${\boldsymbol{\lambda}}^{\ell}={\boldsymbol{\lambda}}^{1}={\boldsymbol{\lambda}_{\star}}$
and

$\Psi_{\alpha,\Theta}({\boldsymbol{\lambda}_{\star}})=\inf_{{\boldsymbol{\lambda}}^{\prime}\in\mathcal{S}_{J}}\Psi_{\alpha,\Theta}({\boldsymbol{\lambda}}^{\prime})\;.$

∎

###  B.3 The Power Descent for mixture models: practical version

The algorithm below provides one possible approximated version of the Power
Descent algorithm, where we have set
$\Gamma(v)=[(\alpha-1)v+1]^{\frac{\eta}{1-\alpha}}$ with $\eta\in(0,1]$.

Input: $p$: measurable positive function, $K$: Markov transition kernel, $M$:
number of samples,
$\Theta=\\{\theta_{1},\ldots,\theta_{J}\\}\subset{\mathsf{T}}$: parameter set,
$\Gamma(v)=[(\alpha-1)v+1]^{\frac{\eta}{1-\alpha}}$ with $\eta\in(0,1]$, $N$:
total number of iterations.

Output: Optimised weights ${\boldsymbol{\lambda}}$.

Set ${\boldsymbol{\lambda}}=[\lambda_{1,1},\ldots,\lambda_{J,1}]$.

for  _$n=1\ldots N$_ do

  1. Sampling step : Draw independently $M$ samples $Y_{1},\ldots,Y_{M}$ from ${\mu_{{\boldsymbol{\lambda}},\Theta}}k$.

  2. Expectation step : Compute $\boldsymbol{B}_{{\boldsymbol{\lambda}}}=(b_{j})_{1\leqslant j\leqslant J}$ where for all $j=1\ldots J$

$\displaystyle
b_{j}=\dfrac{1}{M}\sum\limits_{m=1}^{M}\frac{k(\theta_{j},Y_{m})}{{\mu_{{\boldsymbol{\lambda}},\Theta}}k(Y_{m})}f_{\alpha}^{\prime}\left(\frac{{\mu_{{\boldsymbol{\lambda}},\Theta}}k(Y_{m})}{p(Y_{m})}\right)$

and deduce
$\boldsymbol{W}_{{\boldsymbol{\lambda}}}=(\lambda_{j}\Gamma(b_{j}+\kappa))_{1\leqslant
j\leqslant J}$ and
$w_{{\boldsymbol{\lambda}}}=\sum_{j=1}^{J}\lambda_{j}\Gamma(b_{j}+\kappa)$.

  3. Iteration step : Set

$\displaystyle{\boldsymbol{\lambda}}\leftarrow\frac{1}{w_{{\boldsymbol{\lambda}}}}\boldsymbol{W}_{{\boldsymbol{\lambda}}}$

Algorithm 3 Practical version of the Power Descent for mixture models

## Appendix C

###  C.1 Proof of Section 4

We first state (D1), which summarises the necessary convergence and
differentiability assumptions needed in the proof of section 4.

  1. (D1)

    1. (i)

we have
$\int_{\mathsf{Y}}\sup\limits_{\theta\in{\mathsf{T}}}k(\theta,y)\times\sup\limits_{\theta^{\prime}\in{\mathsf{T}}}\left(\frac{k(\theta^{\prime},y)}{p(y)}\right)^{\alpha-1}\nu(\mathrm{d}y)<\infty$;

    2. (ii)

we have
$\int_{\mathsf{Y}}\sup\limits_{\theta\in{\mathsf{T}}}k(\theta,y)\times\sup\limits_{\theta^{\prime}\in{\mathsf{T}}}\left|\log\left(\frac{k(\theta^{\prime},y)}{p(y)}\right)\right|\times\sup\limits_{\theta^{\prime\prime}\in{\mathsf{T}}}\left(\frac{k(\theta^{\prime\prime},y)}{p(y)}\right)^{\alpha-1}\nu(\mathrm{d}y)<\infty$;

    3. (iii)

we have
$\int_{\mathsf{Y}}\inf\limits_{\theta\in{\mathsf{T}}}k(\theta,y)\times\inf\limits_{\theta^{\prime}\in{\mathsf{T}}}\left(\frac{k(\theta^{\prime},y)}{p(y)}\right)^{\alpha-1}\nu(\mathrm{d}y)>0$.

Note that these assumptions are mild if we assume that ${\mathsf{T}}$ is a
compact metric space, which is generally the case. Assumption (D1)-(D1)(iii)
is only required when $\alpha>1$ to ensure that the quantity
$[(\alpha-1)({b_{\mu,\alpha}}+\kappa)+1]^{\frac{\eta}{1-\alpha}}$ is bounded
from above. This assumption could also be replaced by the assumption that
$\kappa$ is such that $(\alpha-1)\kappa>0$.

###### Proof of section 4.

For all $\theta\in{\mathsf{T}}$, the Dominated Convergence Theorem and
(D1)-(D1)(i) yield

$\lim_{\alpha\to
1}(\alpha-1)({b_{\mu,\alpha}}(\theta)+\kappa)+1=\lim_{\alpha\to
1}\int_{\mathsf{Y}}k(\theta,y)\left(\frac{\mu
k(y)}{p(y)}\right)^{\alpha-1}\nu(\mathrm{d}y)+0=1\;.$

Then, using (D1)-(D1)(ii) we have that for all $\theta\in{\mathsf{T}}$,

$\displaystyle\lim_{\alpha\to
1}\left[(\alpha-1)({b_{\mu,\alpha}}(\theta)+\kappa)+1\right]^{\frac{\eta}{1-\alpha}}$
$\displaystyle=\exp\left(\lim_{\alpha\to
1}-\eta\frac{\log\left[(\alpha-1)({b_{\mu,\alpha}}(\theta)+\kappa)+1\right]}{\alpha-1}\right)$
$\displaystyle=\exp\left(\lim_{\alpha\to
1}-\eta\frac{\int_{\mathsf{Y}}k(\theta,y)\left(\frac{\mu
k(y)}{p(y)}\right)^{\alpha-1}\log\left(\frac{\mu
k(y)}{p(y)}\right)\nu(\mathrm{d}y)+\kappa}{\int_{\mathsf{Y}}k(\theta,y)\left(\frac{\mu
k(y)}{p(y)}\right)^{\alpha-1}\nu(\mathrm{d}y)+(\alpha-1)\kappa}\right)$
$\displaystyle=\exp\left[-\eta\int_{\mathsf{Y}}k(\theta,y)\log\left(\frac{\mu
k(y)}{p(y)}\right)\nu(\mathrm{d}y)\right]\exp\left(-\eta\kappa\right)$

In addition, by the Dominated Convergence Theorem (and (D1)-(D1)(iii) when
$\alpha>1$), we have

$\lim_{\alpha\to
1}\mu\left([(\alpha-1)({b_{\mu,\alpha}}+\kappa)+1]^{\frac{\eta}{1-\alpha}}\right)=\mu\left(\exp\left[-\eta\int_{\mathsf{Y}}k(\cdot,y)\log\left(\frac{\mu
k(y)}{p(y)}\right)\nu(\mathrm{d}y)\right]\right)\exp\left(-\eta\kappa\right)\;.$

Thus,

$\lim_{\alpha\to
1}[\mathcal{I}_{\alpha}(\mu)](h)=\int_{\mathsf{T}}\frac{\mu(\mathrm{d}\theta)h(\theta)e^{-\eta\int_{\mathsf{Y}}k(\theta,y)\log\left(\frac{\mu
k(y)}{p(y)}\right)\nu(\mathrm{d}y)}}{\mu\left(e^{-\eta\int_{\mathsf{Y}}k(\cdot,y)\log\left(\frac{\mu
k(y)}{p(y)}\right)\nu(\mathrm{d}y)}\right)}=[\mathcal{I}_{1}(\mu)](h)\;.$

∎

###  C.2 Derivation of the update formula for the Renyi Descent

For all $\alpha\in\mathbb{R}\setminus\left\\{0,1\right\\}$ and $\kappa$ such
that $(\alpha-1)\kappa\geqslant 0$, we are interested applying the Entropic
Mirror Descent algorithm to the following objective function

$\displaystyle\Psi_{\alpha}^{AR}(\mu)$
$\displaystyle:=\frac{1}{\alpha(\alpha-1)}\log\left(\int_{\mathsf{Y}}\mu
k(y)^{\alpha}p(y)^{1-\alpha}\nu(\mathrm{d}y)+(\alpha-1)\kappa\right)$

######  Lemma .

Assume (A1). The gradient of $\Psi_{\alpha}^{AR}(\mu)$ is given by
$\theta\mapsto\frac{{b_{\mu,\alpha}}(\theta)+1/(\alpha-1)}{(\alpha-1)(\mu({b_{\mu,\alpha}})+\kappa)+1}$.

###### Proof.

Let $\varepsilon>0$ be small and let
$\mu,\mu^{\prime}\in\mathrm{M}_{1}({\mathsf{T}})$. Then,

$\displaystyle\Psi_{\alpha}^{AR}(\mu+\varepsilon\mu^{\prime})$
$\displaystyle=\frac{1}{\alpha(\alpha-1)}\log\left(\int_{\mathsf{Y}}[(\mu+\varepsilon\mu^{\prime})k(y)]^{\alpha}p(y)^{1-\alpha}\nu(\mathrm{d}y)+(\alpha-1)\kappa\right)$
$\displaystyle=\frac{1}{\alpha(\alpha-1)}\log\left(\int_{\mathsf{Y}}\mu
k(y)^{\alpha}\left[1+\alpha\varepsilon\frac{\mu^{\prime}k(y)}{\mu
k(y)}\right]p(y)^{1-\alpha}\nu(\mathrm{d}y)+(\alpha-1)\kappa+o(\varepsilon)\right)$

where we used that $(1+u)^{\alpha}=1+\alpha u+o(u)$ as $u\to 0$. Thus,

$\displaystyle\Psi_{\alpha}^{AR}(\mu+\varepsilon\mu^{\prime})$
$\displaystyle=\Psi_{\alpha}^{AR}(\mu)+\frac{1}{\alpha(\alpha-1)}\log\left(1+\alpha\varepsilon\frac{\int_{\mathsf{Y}}\mu^{\prime}k(y)\left(\frac{\mu
k(y)}{p(y)}\right)^{\alpha-1}\nu(\mathrm{d}y)}{\int_{\mathsf{Y}}\mu
k(y)^{\alpha}p(y)^{1-\alpha}\nu(\mathrm{d}y)+(\alpha-1)\kappa}+o(\varepsilon)\right)$
$\displaystyle=\Psi_{\alpha}^{AR}(\mu)+\varepsilon\frac{1}{\alpha-1}\frac{\int_{\mathsf{Y}}\mu^{\prime}k(y)\left(\frac{\mu
k(y)}{p(y)}\right)^{\alpha-1}\nu(\mathrm{d}y)}{\int_{\mathsf{Y}}\mu
k(y)^{\alpha}p(y)^{1-\alpha}\nu(\mathrm{d}y)+(\alpha-1)\kappa}+o(\varepsilon)$
$\displaystyle=\Psi_{\alpha}^{AR}(\mu)+\varepsilon\int_{\mathsf{T}}\mu^{\prime}(\mathrm{d}\theta)\frac{1}{\alpha-1}\frac{{b_{\mu,\alpha}}(\theta)+1/(\alpha-1)}{\mu({b_{\mu,\alpha}})+\kappa+1/(\alpha-1)}+o(\varepsilon)$

using that $\log(1+u)=u+o(u)$ as $u\to 0$. ∎

Consequently, the iterative update formula for the Entropic Mirror Descent
applied to the objective function $\Psi_{\alpha}^{AR}$ is given by

$\displaystyle\mu_{n+1}(\mathrm{d}\theta)=\mu_{n}(\mathrm{d}\theta)\frac{e^{-\frac{\eta}{\alpha-1}\frac{{b_{\mu_{n},\alpha}}(\theta)}{\mu_{n}({b_{\mu_{n},\alpha}})+\kappa+1/(\alpha-1)}}}{\mu_{n}(e^{-\frac{\eta}{\alpha-1}\frac{{b_{\mu_{n},\alpha}}}{\mu_{n}({b_{\mu_{n},\alpha}})+\kappa+1/(\alpha-1)}})}\;,\quad
n\in\mathbb{N}^{\star}\;.$

###  C.3 Proof of 3

As we shall see, the proof can be adapted from the proof of [17, Theorem 2].
For all $\mu\in\mathrm{M}_{1}({\mathsf{T}})$, we will use the notation

$\mathcal{I}_{\alpha}^{AR}(\mu)(\mathrm{d}\theta)=\frac{\mu(\mathrm{d}\theta)\exp\left[-\eta\frac{{b_{\mu,\alpha}}(\theta)}{(\alpha-1)(\mu({b_{\mu,\alpha}})+\kappa)+1}\right]}{\mu\left(\exp\left[-\eta\frac{{b_{\mu,\alpha}}}{(\alpha-1)(\mu_{n}({b_{\mu,\alpha}})+\kappa)+1}\right]\right)}\;$

to designate the one-step transition of the Renyi Descent algorithm. Note in
passing that for all $\kappa^{\prime}\in\mathbb{R}$, this definition can also
be rewritten under the form

$\mathcal{I}_{\alpha}^{AR}(\mu)(\mathrm{d}\theta)=\frac{\mu(\mathrm{d}\theta)\exp\left[-\eta\frac{{b_{\mu,\alpha}}(\theta)}{(\alpha-1)(\mu({b_{\mu,\alpha}})+\kappa)+1}+\kappa^{\prime}\right]}{\mu\left(\exp\left[-\eta\frac{{b_{\mu,\alpha}}}{(\alpha-1)(\mu_{n}({b_{\mu,\alpha}})+\kappa)+1}+\kappa^{\prime}\right]\right)}\;.$

We also define

$\displaystyle
L_{\alpha,2}=\eta^{-1}\sup_{\theta\in{\mathsf{T}},\mu\in\mathrm{M}_{1}({\mathsf{T}})}[(\alpha-1)({b_{\mu,\alpha}}(\theta)+\kappa)+1]$
$\displaystyle L=\eta^{2}\sup_{v\in\mathrm{Dom}_{\alpha}^{AR}}e^{-\eta v}$
$\displaystyle L_{\alpha,3}=\sup_{v\in\mathrm{Dom}_{\alpha}^{AR}}e^{\eta v}$
$\displaystyle
L_{\alpha,1}=\inf_{v\in\mathrm{Dom}_{\alpha}^{AR}}\left\\{1-\eta(\alpha-1)(v-\kappa^{\prime})\right\\}\times\eta\inf_{v\in\mathrm{Dom}_{\alpha}^{AR}}e^{-\eta
v}\;.$ (20)

####  C.3.1 Recalling [17, Lemma 5]

Let $(\zeta,\mu)$ be a couple of probability measures where $\zeta$ is
dominated by $\mu$ which we denote by $\zeta\preceq\mu$ and define

$\displaystyle
A_{\alpha}:=\int_{\mathsf{Y}}\nu(\mathrm{d}y)\int_{\mathsf{T}}\mu(\mathrm{d}\theta)k(\theta,y)f_{\alpha}^{\prime}\left(\frac{g(\theta)\mu
k(y)}{p(y)}\right)\left[1-g(\theta)\right]\;,$ (21)

where $g$ is the density of $\zeta$ w.r.t $\mu$, i.e.
$\zeta(\mathrm{d}\theta)=\mu(\mathrm{d}\theta)g(\theta)$. We recall [17, Lemma
5] in Section C.3.1 below.

######  Lemma .

[17, Lemma 5] Assume (A1). Then, for all
$\mu,\zeta\in\mathrm{M}_{1}({\mathsf{T}})$ such that $\zeta\preceq\mu$ and
$\Psi_{\alpha}(\mu)<\infty$, we have

$A_{\alpha}\leqslant\Psi_{\alpha}(\mu)-\Psi_{\alpha}(\zeta)\;.$ (22)

Moreover, equality holds in (22) if and only if $\zeta=\mu$.

####  C.3.2 Adaptation of [17, Theorem 1]

######  Lemma .

Assume (A1) and (A4). Let $\alpha\in\mathbb{R}\setminus\left\\{1\right\\}$,
let $\kappa$ be such that $(\alpha-1)\kappa\geqslant 0$ and let
$\mu\in\mathrm{M}_{1}({\mathsf{T}})$ be such that

$\displaystyle
0<\mu\left\\{\exp\left(-\eta\frac{{b_{\mu,\alpha}}+1/(\alpha-1)}{(\alpha-1)(\mu({b_{\mu,\alpha}})+\kappa)+1}\right)\right\\}<\infty\;$
(23)

holds and $\Psi_{\alpha}(\mu)<\infty$. Then, the two following assertions
hold.

  1. (i)

We have
$\Psi_{\alpha}\circ\mathcal{I}_{\alpha}^{AR}(\mu)\leqslant\Psi_{\alpha}(\mu)$.

  2. (ii)

We have $\Psi_{\alpha}\circ\mathcal{I}_{\alpha}^{AR}(\mu)=\Psi_{\alpha}(\mu)$
if and only if $\mu=\mathcal{I}_{\alpha}^{AR}(\mu)$.

###### Proof.

The proof builds on the proof of [17, Theorem 1] in the particular case
$\alpha\in\mathbb{R}\setminus\left\\{1\right\\}$. Indeed, in this case,

$\displaystyle A_{\alpha}$
$\displaystyle=\int_{\mathsf{Y}}\nu(\mathrm{d}y)\int_{\mathsf{T}}\mu(\mathrm{d}\theta)k(\theta,y)\frac{1}{\alpha-1}\left[\left(\frac{g(\theta)\mu
k(y)}{p(y)}\right)^{\alpha-1}-1\right]\left[1-g(\theta)\right]$
$\displaystyle=\int_{\mathsf{Y}}\nu(\mathrm{d}y)\int_{\mathsf{T}}\mu(\mathrm{d}\theta)k(\theta,y)\frac{1}{\alpha-1}\left(\frac{\mu
k(y)}{p(y)}\right)^{\alpha-1}g(\theta)^{\alpha-1}\left[1-g(\theta)\right]$
$\displaystyle=\int_{\mathsf{T}}\mu(\mathrm{d}\theta)\left[{b_{\mu,\alpha}}(\theta)+\frac{1}{\alpha-1}\right]g(\theta)^{\alpha-1}\left[1-g(\theta)\right]\;.$

so that

$\displaystyle A_{\alpha}$
$\displaystyle=[(\alpha-1)(\mu({b_{\mu,\alpha}})+\kappa)+1]\times\int_{\mathsf{T}}\mu(\mathrm{d}\theta)\frac{{b_{\mu,\alpha}}(\theta)+\frac{1}{\alpha-1}}{(\alpha-1)(\mu({b_{\mu,\alpha}})+\kappa)+1}g(\theta)^{\alpha-1}\left[1-g(\theta)\right]$

where $(\alpha-1)(\mu({b_{\mu,\alpha}})+\kappa)+1>0$ under (A1). Set

$g={\tilde{\Gamma}}\circ\left(\frac{{b_{\mu,\alpha}}+1/(\alpha-1)}{(\alpha-1)(\mu({b_{\mu,\alpha}})+\kappa)+1}\right)$

where for all $v\in\mathrm{Dom}_{\alpha}^{AR}$,

${\tilde{\Gamma}}(v)=\frac{e^{-\eta
v}}{\mu\left\\{\exp\left(-\eta\frac{{b_{\mu,\alpha}}+1/(\alpha-1)}{(\alpha-1)(\mu({b_{\mu,\alpha}})+\kappa)+1}-\eta\kappa^{\prime}\right)\right\\}}\;.$

Finally, let us consider the probability space
$({\mathsf{T}},\mathcal{T},\mu)$ and let $V$ be the random variable

$V(\theta)=\frac{{b_{\mu,\alpha}}(\theta)+1/(\alpha-1)}{(\alpha-1)(\mu({b_{\mu,\alpha}})+\kappa)+1}+\kappa^{\prime}\;.$

Then, we have $\mathbb{E}[1-{\tilde{\Gamma}}(V)]=0$ and we can write

$\displaystyle A_{\alpha}$
$\displaystyle=[(\alpha-1)(\mu({b_{\mu,\alpha}})+\kappa)+1]\times\mathbb{E}[(V-\kappa^{\prime}){\tilde{\Gamma}}^{\alpha-1}(V)(1-{\tilde{\Gamma}}(V))]$
$\displaystyle=[(\alpha-1)(\mu({b_{\mu,\alpha}})+\kappa)+1]\times\mathbb{C}\mathrm{ov}((V-\kappa^{\prime}){\tilde{\Gamma}}^{\alpha-1}(V),1-{\tilde{\Gamma}}(V))\;.$
(24)

Under (A4) with $\alpha\in\mathbb{R}\setminus\left\\{1\right\\}$,
$v\mapsto(v-\kappa^{\prime}){\tilde{\Gamma}}^{\alpha-1}(v)$ and $v\mapsto
1-{\tilde{\Gamma}}(v)$ are increasing on $\mathrm{Dom}_{\alpha}^{AR}$ which
implies
$\mathbb{C}\mathrm{ov}(V{\tilde{\Gamma}}^{\alpha-1}(V),1-{\tilde{\Gamma}}(V))\geqslant
0$ and thus $A_{\alpha}\geqslant 0$ since
$(\alpha-1)(\mu({b_{\mu,\alpha}})+\kappa)+1>0$. ∎

####  C.3.3 Adaptation of [17, Lemma 6]

Consider the probability space $({\mathsf{T}},\mathcal{T},\mu)$ and denote by
$\mathbb{V}\mathrm{ar}_{\mu}$ the associated variance operator.

######  Lemma .

Assume (A1) and (A4). Let $\alpha\in\mathbb{R}\setminus\left\\{1\right\\}$,
let $\kappa$ be such that $(\alpha-1)\kappa>0$, and let
$\mu\in\mathrm{M}_{1}({\mathsf{T}})$ be such that (23) holds and
$\Psi_{\alpha}(\mu)<\infty$. Then,

$\displaystyle\frac{(\alpha-1)\kappa
L_{\alpha,1}}{2}\mathbb{V}\mathrm{ar}_{\mu}\left(\frac{{b_{\mu,\alpha}}+1/(\alpha-1)}{(\alpha-1)(\mu({b_{\mu,\alpha}})+\kappa)+1}\right)\leqslant\Psi_{\alpha}(\mu)-\Psi_{\alpha}\circ\mathcal{I}_{\alpha}^{AR}(\mu)\;,$
(25)

where

$L_{\alpha,1}:=\inf_{v\in\mathrm{Dom}_{\alpha}^{AR}}\left\\{1-\eta(\alpha-1)(v-\kappa^{\prime})\right\\}\times\inf_{v\in\mathrm{Dom}_{\alpha}^{AR}}\eta
e^{-\eta v}\;.$

###### Proof.

The proof of Section C.3.3 builds on the proof of [17, Lemma 6], which can be
found in the supplementary material of [17]. Using (24) combined with the fact
that under (A1),
$(\alpha-1)(\mu({b_{\mu,\alpha}})+\kappa)+1>(\alpha-1)\kappa>0$

$\displaystyle A_{\alpha}$
$\displaystyle=[(\alpha-1)(\mu({b_{\mu,\alpha}})+\kappa)+1]\times\mathbb{C}\mathrm{ov}((V-\kappa^{\prime}){\tilde{\Gamma}}^{\alpha-1}(V),1-{\tilde{\Gamma}}(V))$
$\displaystyle>(\alpha-1)\kappa\times\mathbb{C}\mathrm{ov}((V-\kappa^{\prime}){\tilde{\Gamma}}^{\alpha-1}(V),1-{\tilde{\Gamma}}(V))$

Furthermore,

$\displaystyle\mathbb{C}\mathrm{ov}((V-\kappa^{\prime})$
$\displaystyle{\tilde{\Gamma}}^{\alpha-1}(V),1-{\tilde{\Gamma}}(V))$
$\displaystyle=\frac{1}{2}\mathbb{E}\left[((U-\kappa^{\prime}){\tilde{\Gamma}}^{\alpha-1}(U)-(V-\kappa^{\prime}){\tilde{\Gamma}}^{\alpha-1}(V))(-{\tilde{\Gamma}}(U)+{\tilde{\Gamma}}(V))\right]$
$\displaystyle=\frac{1}{2}\mathbb{E}\left[\frac{(U-\kappa^{\prime}){\tilde{\Gamma}}^{\alpha-1}(U)-(V-\kappa^{\prime}){\tilde{\Gamma}}^{\alpha-1}(V)}{U-V}\frac{-{\tilde{\Gamma}}(U)+{\tilde{\Gamma}}(V)}{U-V}(U-V)^{2}\right]$
$\displaystyle\geqslant\frac{L_{\alpha,1}}{2}\mathbb{V}\mathrm{ar}_{\mu}\left(\frac{{b_{\mu,\alpha}}+1/(\alpha-1)}{(\alpha-1)(\mu({b_{\mu,\alpha}})+\kappa)+1}\right)$

and we thus obtain (25). ∎

####  C.3.4 Adaptation of the proof of [17, Theorem 2] to obtain 3

###### Proof of 3.

The proof of 3 builds on the proof of [17, Theorem 2], which can be found in
the supplementary material of [17]. We prove the assertions successively.

  1. (i)

The proof of (i) simply consists in verifying that we can apply Section C.3.2.
For all $\mu\in\mathrm{M}_{1}({\mathsf{T}})$, (23) with $\mu=\mu_{n}$ holds
for all $n\in\mathbb{N}^{\star}$ by assumption on $|B|_{\infty,\alpha}$ and
since at each step $n\in\mathbb{N}^{\star}$, Section C.3.2 combined with
$\Psi_{\alpha}(\mu_{n})<\infty$ implies that
$\Psi_{\alpha}(\mu_{n+1})\leqslant\Psi_{\alpha}(\mu_{n})<\infty$, we obtain by
induction that $(\Psi_{\alpha}(\mu_{n}))_{n\in\mathbb{N}^{\star}}$ is non-
increasing.

  2. (ii)

Let $n\in\mathbb{N}^{\star}$, set
$\Delta_{n}=\Psi_{\alpha}(\mu_{n})-\Psi_{\alpha}(\mu^{\star})$ and for all
$\theta\in{\mathsf{T}}$,
$V_{n}(\theta)=\frac{{b_{\mu_{n},\alpha}}(\theta)+\frac{1}{\alpha-1}}{(\alpha-1)(\mu_{n}({b_{\mu_{n},\alpha}})+\kappa)+1}+\kappa^{\prime}$,
such that $\mathrm{d}\mu_{n+1}\propto e^{-\eta V_{n}}\mathrm{d}\mu_{n}$.

We first show that

$\displaystyle\Delta_{n}\leqslant
L_{\alpha,2}\left[\int_{\mathsf{T}}\log\left(\frac{\mathrm{d}\mu_{n+1}}{\mathrm{d}\mu_{n}}\right)\mathrm{d}\mu^{\star}+\frac{L}{2}\mathbb{V}\mathrm{ar}_{\mu_{n}}(V_{n})L_{\alpha,3}\right]\;.$
(26)

The convexity of $f_{\alpha}$ implies that

$\displaystyle\Delta_{n}$
$\displaystyle\leqslant\int_{\mathsf{T}}{b_{\mu_{n},\alpha}}(\mathrm{d}\mu_{n}-\mathrm{d}\mu^{\star})$
(27)
$\displaystyle=\int_{\mathsf{T}}\left({b_{\mu_{n},\alpha}}+\frac{1}{\alpha-1}\right)(\mathrm{d}\mu_{n}-\mathrm{d}\mu^{\star})$
$\displaystyle=\frac{(\alpha-1)(\mu_{n}({b_{\mu_{n},\alpha}})+\kappa)+1}{\eta}\int_{\mathsf{T}}(\mu_{n}(\eta
V_{n})-\eta V_{n})\mathrm{d}\mu^{\star}\;.$ (28)

Then, noting that

$-\eta V_{n}=\log\mu_{n}\left(e^{-\eta
V_{n}}\right)+\log\left(\frac{\mathrm{d}\mu_{n+1}}{\mathrm{d}\mu_{n}}\right)$

we deduce

$\displaystyle\Delta_{n}$ $\displaystyle\leqslant
L_{\alpha,2}\int_{\mathsf{T}}\left[\mu_{n}(\eta
V_{n})+\log\mu_{n}\left(e^{-\eta
V_{n}}\right)+\log\left(\frac{\mathrm{d}\mu_{n+1}}{\mathrm{d}\mu_{n}}\right)\right]\mathrm{d}\mu^{\star}\;.$
(29)

Since $v\mapsto e^{-\eta v}$ is $L$-smooth on $\mathrm{Dom}_{\alpha}^{AR}$,
for all $\theta\in{\mathsf{T}}$ and for all $n\in\mathbb{N}^{\star}$ we can
write

$\displaystyle e^{-\eta V_{n}(\theta)}\leqslant e^{-\eta\mu_{n}(V_{n})}+\eta
e^{-\eta\mu_{n}(V_{n})}(V_{n}(\theta)-\mu_{n}(V_{n}))+\frac{L}{2}\left(V_{n}(\theta)-\mu_{n}(V_{n})\right)^{2}$

which in turn implies

$\mu_{n}(e^{-\eta V_{n}})\leqslant
e^{-\eta\mu_{n}(V_{n})}+\frac{L}{2}\mathbb{V}\mathrm{ar}_{\mu_{n}}\left(V_{n}\right)\;.$

Finally, we obtain

$\log\mu_{n}(e^{-\eta V_{n}})\leqslant\log
e^{-\eta\mu_{n}(V_{n})}+\log\left(1+\frac{L}{2}\frac{\mathbb{V}\mathrm{ar}_{\mu_{n}}(V_{n})}{e^{-\eta\mu_{n}(V_{n})}}\right)\;.$

Using that $\log(1+u)\leqslant u$ when $u\geqslant 0$ and by definition of
$L_{\alpha,3}$, we deduce

$\log\mu_{n}(e^{-\eta
V_{n}})\leqslant-\eta\mu_{n}(V_{n})+\frac{L}{2}\mathbb{V}\mathrm{ar}_{\mu_{n}}(V_{n})L_{\alpha,3}\;,$

which combined with (29) implies (26). To conclude, we apply Section C.3.3 to
$g=\frac{\mathrm{d}\mu_{n+1}}{\mathrm{d}\mu_{n}}$ and combining with (26), we
obtain

$\Delta_{n}\leqslant
L_{\alpha,2}\left[\int_{\mathsf{T}}\log\left(\frac{\mathrm{d}\mu_{n+1}}{\mathrm{d}\mu_{n}}\right)\mathrm{d}\mu^{\star}+\frac{LL_{\alpha,3}}{L_{\alpha,1}(\alpha-1)\kappa}\left(\Delta_{n}-\Delta_{n+1}\right)\right]\;,$

where by assumption $L_{\alpha,1}$, $L_{\alpha,2}$ and $L_{\alpha,3}>0$. As
the r.h.s involves two telescopic sums, we deduce

$\displaystyle\frac{1}{N}\sum_{n=1}^{N}\Psi_{\alpha}(\mu_{n})-\Psi_{\alpha}(\mu^{\star})\leqslant\frac{L_{\alpha,2}}{N}\left[KL(\mu^{\star}||\mu_{1})-KL(\mu^{\star}||\mu_{N+1})+L\frac{L_{\alpha,3}}{L_{\alpha,1}(\alpha-1)\kappa}(\Delta_{1}-\Delta_{N+1})\right]$

and we recover (9) using (i), that $KL(\mu^{\star}||\mu_{N+1})\geqslant 0$ and
that $\Delta_{N+1}\geqslant 0$.

∎

###  C.4 The Renyi Descent for mixture models: practical version

The algorithm below provides one possible approximated version of the Renyi
Descent algorithm, where we have set $\Gamma(v)=e^{-\eta v}$ with $\eta>0$.

Input: $p$: measurable positive function, $K$: Markov transition kernel, $M$:
number of samples,
$\Theta=\\{\theta_{1},\ldots,\theta_{J}\\}\subset{\mathsf{T}}$: parameter set,
$\Gamma(v)=e^{-\eta v}$ with $\eta>0$, $N$: total number of iterations.

Output: Optimised weights ${\boldsymbol{\lambda}}$.

Set ${\boldsymbol{\lambda}}=[\lambda_{1,1},\ldots,\lambda_{J,1}]$.

for  _$n=1\ldots N$_ do

  1. Sampling step : Draw independently $M$ samples $Y_{1},\ldots,Y_{M}$ from ${\mu_{{\boldsymbol{\lambda}},\Theta}}k$.

  2. Expectation step : Compute $\boldsymbol{B}_{{\boldsymbol{\lambda}}}=(b^{\prime}_{j})_{1\leqslant j\leqslant J}$ where for all $j=1\ldots J$

$\displaystyle
b_{j}=\dfrac{1}{M}\sum\limits_{m=1}^{M}\frac{k(\theta_{j},Y_{m})}{{\mu_{{\boldsymbol{\lambda}},\Theta}}k(Y_{m})}f_{\alpha}^{\prime}\left(\frac{{\mu_{{\boldsymbol{\lambda}},\Theta}}k(Y_{m})}{p(Y_{m})}\right)$

and for all $j=1\ldots J$

$b^{\prime}_{j}=\frac{b_{j}}{(\alpha-1)(\sum_{\ell=1}^{J}b_{\ell}+\kappa)+1}\;$

and deduce
$\boldsymbol{W}_{{\boldsymbol{\lambda}}}=(\lambda_{j}\Gamma(b^{\prime}_{j}+\kappa^{\prime}))_{1\leqslant
j\leqslant J}$ and
$w_{{\boldsymbol{\lambda}}}=\sum_{j=1}^{J}\lambda_{j}\Gamma(b^{\prime}_{j}+\kappa^{\prime})$.

  3. Iteration step : Set

$\displaystyle{\boldsymbol{\lambda}}\leftarrow\frac{1}{w_{{\boldsymbol{\lambda}}}}\boldsymbol{W}_{{\boldsymbol{\lambda}}}$

Algorithm 4 Practical version of the Renyi Descent for mixture models

###  C.5 Alternative Exploration step in Algorithm 2

We present here several possible alternative choices of Exploration step in
Algorithm 2, beyond the one we have made in Section 5 and that is based on
[18]. Our goal here is not to discriminate between all of them, but to
illustrate the generality of our approach.

Gradient Descent. One could use a Gradient Descent approach to optimise the
mixture components parameters
$\left\\{\theta_{1,t+1},\ldots,\theta_{J,t+1}\right\\}$ in the spirit of
Renyi’s $\alpha$-divergence gradient-based methods (e.g [9, 10]) or
$\alpha$-divergence gradient-based methods (e.g [11, 12]).

The particular case $\alpha\in[0,1)$. Following [18], if we consider the
specific case $\alpha\in[0,1)$ another possibility would be to set at time
$t$: for all $j=1\ldots J$

$\displaystyle\theta_{j,t+1}=\mathrm{argmax}_{\theta_{j}\in{\mathsf{T}}}\int_{\mathsf{Y}}\gamma_{j,\alpha}^{t}(y)\log(k(\theta_{j},y))\nu(\mathrm{d}y)$
(30)

where for all $y\in\mathsf{Y}$,

$\displaystyle\gamma_{j,\alpha}^{t}(y)=k(\theta_{j,t},y)\left(\frac{{\mu_{{\boldsymbol{\lambda}},\Theta}}{}k(y)}{p(y)}\right)^{\alpha-1}\;.$

Indeed, [18] showed that the above update formulas for
$\left\\{\theta_{1,t+1},\ldots,\theta_{J,t+1}\right\\}$ ensure a systematic
decrease in the $\alpha$-divergence and they notably explained how these
update formulas could even outperform typical Renyi’s $\alpha$ /
$\alpha$-divergence gradient-based approaches (we refer to [18] for details).

Furthermore, in the particular case of $d$-dimensional Gaussian kernels with
$k(\theta_{j,t},y)=\mathcal{N}(y;m_{j,t},\Sigma_{j,t})$ and where
$\theta_{j,t}=(m_{j,t},\Sigma_{j,t})\in{\mathsf{T}}$ denotes the mean and
covariance matrix of the $j$-th Gaussian component density, they obtained that
the maximisation procedure (30) amounts to setting

$\displaystyle\forall j=1\ldots J,\quad m_{j,t+1}$
$\displaystyle=\frac{\int_{\mathsf{Y}}\gamma_{j,\alpha}^{t}(y)y\leavevmode\nobreak\
\nu(\mathrm{d}y)}{\int_{\mathsf{Y}}\gamma_{j,\alpha}^{t}(y)\nu(\mathrm{d}y)}$
$\displaystyle\Sigma_{j,t+1}$
$\displaystyle=\frac{\int_{\mathsf{Y}}\gamma_{j,\alpha}^{t}(y)(y-m_{j,t})(y-m_{j,t})^{T}\nu(\mathrm{d}y)}{\int_{\mathsf{Y}}\gamma_{j,\alpha}^{t}(y)\nu(\mathrm{d}y)}\;.$

These update formulas can then always be made feasible by resorting to Monte
Carlo approximations and can be used as a valid Exploration step. If we were
to focus on solely updating the means $(m_{j,t+1})_{1\leqslant j\leqslant J}$,
we could for example consider the Exploration step given by:

$\displaystyle\forall j=1\ldots J,\quad\theta_{j,t+1}=m_{j,t+1}$
$\displaystyle=\frac{\sum_{m=1}^{M}\hat{\gamma}_{j}^{(t)}(Y^{\prime}_{m};{\boldsymbol{\lambda}})\cdot
Y^{\prime}_{m}}{\sum_{m=1}^{M}\hat{\gamma}_{j}^{(t)}(Y^{\prime}_{m};{\boldsymbol{\lambda}})}$

where the $M$ samples $(Y^{\prime}_{m})_{1\leqslant m\leqslant M}$ have been
drawn independently from the proposal $\mu_{{\boldsymbol{\lambda}},\Theta}$
and where we have set

$\hat{\gamma}_{j}^{(t)}(y;{\boldsymbol{\lambda}})=\frac{k(\theta_{j,t},y)}{\mu_{{\boldsymbol{\lambda}},\Theta}k(y)}\left(\frac{\mu_{{\boldsymbol{\lambda}},\Theta}k(y)}{p(y)}\right)^{\alpha-1}\;.$

We ran Algorithm 2 over 100 replicates for this choice of Exploration step
with $M\in\left\\{100,500\right\\}$ (and keeping the same target $p$, initial
sampler $q_{0}$, and hyperparameters $N=20$, $T=10$, $\eta=\eta_{0}/\sqrt{N}$
with $\eta_{0}=0.3$, $\alpha=0.5$, $J=100$, $\kappa=0.$ and $d=16$ as those
chosen in Section 5). The results when using the Power and the Renyi Descent
as Exploitation steps can be visualised in the figure below.

Figure 2: Plotted is the average Variational Renyi bound for the Power Descent (PD) and the Renyi Descent (RD) in dimension $d=16$ computed over 100 replicates with $\eta_{0}=0.3$ and $\alpha=0.5$ and an increasing number of samples $M$. |
---|---

We then observe a similar behavior for the Power and the Renyi Descent, which
illustrates the closeness between both algorithms, irrespective of the choice
of the Exploration step.