∎

11institutetext: M. Hayashi 22institutetext: School of Data Science, The
Chinese University of Hong Kong, Shenzhen, Longgang District, Shenzhen,
518172, China, International Quantum Academy (SIQA), Futian District, Shenzhen
518048, China, and Graduate School of Mathematics, Nagoya University, Chikusa-
ku, Nagoya 464-8602, Japan.
22email: e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
# Iterative minimization algorithm on mixture family

Masahito Hayashi

(Received: date / Accepted: date)

###### Abstract

Iterative minimization algorithms appear in various areas including machine
learning, neural network, and information theory. The em algorithm is one of
the famous iterative minimization algorithms in the former area, and Arimoto-
Blahut algorithm is a typical iterative algorithm in the latter area. However,
these two topics had been separately studied for a long time. In this paper,
we generalize an algorithm that was recently proposed in the context of
Arimoto-Blahut algorithm. Then, we show various convergence theorems, one of
which covers the case when each iterative step is done approximately. Also, we
apply this algorithm to the target problem in em algorithm, and propose its
improvement. In addition, we apply it to other various problems in information
theory.

###### Keywords:

minimization em algorithm mixture family channel capacity divergence

##  1 Introduction

Optimization over distributions is an important topic in various areas. For
example, the minimum divergence between a mixture family and an exponential
family has been studied by em algorithm in the areas of machine learning and
neural network Amari ; Fujimoto ; Allassonniere . The em algorithm is an
iterative algorithm to calculate the above minimization and it is rooted in
the study of Boltzmann machine Bol . In particular, the paper Fujimoto
formulated em algorithm the framework with Bregman divergence Amari-Nagaoka ;
Amari-Bregman . This topic has been mainly studied in the community of machine
learning, neural network, and information geometry. As another iterative
algorithm, Arimoto-Blahut algorithm is known as an algorithm to maximize the
mutual information by changing the distribution on the input system Arimoto ;
Blahut . This maximization is needed to calculate the channel capacity Shannon
. This algorithm has been generalized to various settings including the rate
distortion theory Blahut ; Csiszar ; Cheng ; YSM , the capacity of a wire-tap
channel Yasui , and their quantum extensions Nagaoka ; Dupuis ; Sutter ; Li ;
RISB . In particular, the two papers YSM ; RISB  made very useful
generalizations to cover various topics in information theory. This topic has
been mainly studied in the community of information theory.

However, only a limited number of studies have discussed the relation between
the two topics, em algorithm and Arimoto-Blahut algorithm as follows. The
papers Tusnady ; Sullivan  pointed out that Arimoto-Blahut algorithm can be
considered as an alternating algorithm in a similar way to EM and em
algorithms. Recently, the paper Shoji  pointed out that the maximization of
the mutual information can be considered the maximization of the projected
divergence to an exponential family by changing an element of a mixture
family. The paper reverse  generalized this maximization to the framework with
Bregman divergence Amari-Nagaoka ; Amari-Bregman  and applied this setting to
various problems in information theory. Also, the recent paper Bregman-em
applied em algorithm to the rate distortion theory, which is a key topic in
information theory.

In this paper, we focus on a generalized problem setting proposed in RISB ,
which is given as an optimization over the set of input quantum states. As the
difference from the former algorithm, their algorithm RISB  has an
acceleration parameter. Changing this parameter, we can enhance the
convergence speed under a certain condition. To obtain wider applicability, we
extend their problem setting to the minimization over a general mixture
family. Although they discussed the convergence speed only when there is no
local minimizer, our analysis covers the convergence speed to a local
minimizer even when there exist several local minimizers. Further, since our
setting covers a general mixture family as the set of input variables, our
method can be applied to the minimum divergence between a mixture family and
an exponential family, which is the objective problem in em algorithm. That
is, this paper presents a general algorithm including em algorithm as well as
Arimoto-Blahut algorithm. This type of relation between em algorithm and
Arimoto-Blahut algorithm is different from the relation pointed by the papers
Tusnady ; Sullivan .

There is a possibility that each iteration can be calculated only
approximately. To cover such an approximated case, we evaluate the error of
our algorithm with approximated iterations. Since em algorithm has local
minimizers in general, it is essential to cover the convergence to a local
minimizer. Since our algorithm has the acceleration parameter, our application
to the minimum divergence gives a generalization of em algorithm. Also, our
algorithm can be applied to the maximization of the projected divergence to an
exponential family by changing an element of a mixture family.

In addition, our algorithm has various applications that were not discussed in
the preceding study RISB . In channel coding, the decoding block error
probability goes to zero exponentially under the proper random coding when the
transmission rate is smaller than the capacity Gallager . Also, the
probability of correct decoding goes to zero exponentially when the
transmission rate is greater than the capacity Arimoto2 . These exponential
rates are written with the optimization of the so-called Gallager function.
Recently, the paper H15  showed that the Gallager function can be written as
the minimization of Rényi divergence. Using this fact, we apply our method to
these optimizations. Further, we apply our algorithm to the capacity of a
wiretap channel. In addition, since our problem setting allows a general
mixture family as the range of input, we apply the channel capacity with cost
constraint. Also, we point out that the calculation of the commitment capacity
is given as the minimization of the divergence between a mixture family and an
exponential family. Hence, we discuss this application as well.

The remaining part of this paper is organized as follows. Section 2 formulates
our minimization problem for a general mixture family. Then, we proposed
several algorithms to solve the minimization problem. We derive various
convergence theorems including the case with approximated iterations. Section
3 applies our algorithm to various information theoretical problems Then,
Section 4 applies our algorithm to the minimum divergence between a mixture
family and an exponential family Section 5 applies our algorithm to the
commitment capacity. Section 6 applies our algorithm to the maximization of
the projected divergence to an exponential family by changing an element of a
mixture family. Section 7 applies our algorithm to information bottleneck,
which is a powerful method for machine learning. Appendices are devoted to the
proofs of the theorems presented in Section 2.

##  2 General setting

###  2.1 Algorithm with exact iteration

We consider a finite sample space ${\cal X}$ and focus on the set ${\cal
P}({\cal X})$ of distributions whose support is ${\cal X}$. Using $k$ linearly
independent functions $f_{1},\ldots,f_{k}$ on ${\cal X}$ and constants
$a=(a_{1},\ldots,a_{k})$, we define the mixture family ${\cal M}_{a}$ as
follows

$\displaystyle{\cal M}_{a}:=\\{P\in{\cal P}({\cal X})|P[f_{i}]=a_{i}\hbox{ for
}i=1,\ldots,k\\},$ (1)

where $P[f]:=\sum_{x\in{\cal X}}P(x)f(x)$. We add additional $l-k$ linearly
independent functions $f_{k+1},\ldots f_{l}$ and $|{\cal X}|=l+1$ such that
the $l$ functions $f_{1},\ldots,f_{l}$ are linearly independent. Then, the
distribution $P$ can be parameterized by the mixture parameter
$\eta=(\eta_{1},\ldots,\eta_{l})$ as $\eta_{i}=P[f_{i}]$. That is, the above
distribution is denoted by $P_{\eta}$. Then, we denote the $m$-projection of
$P$ to ${\cal M}_{a}$ by $\Gamma^{(m)}_{{\cal M}_{a}}[P]$. That is,
$\Gamma^{(m)}_{{\cal M}_{a}}[P]$ is defined as follows.

$\displaystyle\Gamma^{(m)}_{{\cal M}_{a}}[P]:=\mathop{\rm
argmin}\limits_{Q\in{\cal M}_{a}}D(Q\|P),$ (2)

where the Kullback-Leibler divergence $D(Q\|P)$ is defined as

$\displaystyle D(Q\|P):=\sum_{x\in{\cal X}}Q(x)(\log Q(x)-\log P(x)).$ (3)

Using the $m$-projection, we have the following equation for an element of
$Q\in{\cal M}_{a}$, which is often called Pythagorean theorem.

$\displaystyle D(Q\|P)=D(Q\|\Gamma^{(m)}_{{\cal
M}_{a}}[P])+D(\Gamma^{(m)}_{{\cal M}_{a}}[P]\|P).$ (4)

Given a continuous function $\Psi$ from ${\cal M}_{a}$ to the set of functions
on ${\cal X}$, we consider the minimization $\min_{P\in{\cal M}_{a}}{\cal
G}(P)$;

$\displaystyle{\cal G}(P):=\sum_{x\in{\cal X}}P(x)\Psi[P](x).$ (5)

The aim of this paper is to find

$\displaystyle\overline{{\cal G}}(a):=\min_{P\in{\cal M}_{a}}{\cal G}(P),\quad
P_{*,a}:=\mathop{\rm argmin}\limits_{P\in{\cal M}_{a}}{\cal G}(P).$ (6)

For this aim, we propose an interative algorithm based on a positive real
number $\gamma>0$. Since the above formulation (5) is very general, we can
choose the function $\Psi$ dependently of our objective function. That is,
different choices of $\Psi$ lead to different objective functions.

For a distribution $Q\in{\cal P}({\cal X})$, we define the distribution ${\cal
F}_{3}[Q]$ as ${\cal
F}_{3}[Q](x):=\frac{1}{\kappa[Q]}Q(x)\exp(-\frac{1}{\gamma}\Psi[Q](x))$, where
$\kappa[Q]$ is the normalization factor $\sum_{x\in{\cal
X}}Q(x)\exp(-\frac{1}{\gamma}\Psi[Q](x))$. Then, generalizing the algorithm by
RISB , depending on $\gamma>0$, we propose Algorithm 1. When the calculation
of $\Psi[P]$ and the $m$-projection is feasible, Algorithm 1 is feasible.

Algorithm 1 Minimization of ${\cal G}(P)$

As inputs, we prepare the function $\Psi$, $l$ linearly independent functions
$f_{1},\ldots,f_{l}$, constraints $a_{1},\ldots,a_{k}$, a positive number
$\gamma>0$, and the initial value $P^{(1)}\in\mathcal{M}_{a}$;

repeat

Calculate $P^{(t+1)}:=\Gamma^{(m)}_{{\cal M}_{a}}[{\cal F}_{3}[P^{(t)}]]$;

until convergence. We denote the convergent by $P^{(\infty)}$.

Output $P^{(\infty)}$.

Indeed, Algorithm 1 is characterized as the iterative minimization of the
following two-variable function, i.e., the extended objective function;

$\displaystyle J_{\gamma}(P,Q):=\gamma D(P\|Q)+\sum_{x\in{\cal
X}}P(x)\Psi[Q](x).$ (7)

To see this fact, we define

$\displaystyle{\cal F}_{1}[P]:=\mathop{\rm argmin}\limits_{Q\in{\cal
M}_{a}}J_{\gamma}(P,Q),\quad{\cal F}_{2}[Q]:=\mathop{\rm
argmin}\limits_{P\in{\cal M}_{a}}J_{\gamma}(P,Q).$ (8)

Then, as a generalization of a part of (RISB, , Lemma 3.2), ${\cal F}_{2}[Q]$
is calculated as follows.

###### Lemma 1

Under the above definitions, we have ${\cal F}_{2}[Q]=\Gamma^{(m)}_{{\cal
M}_{a}}[{\cal F}_{3}[Q]]$, i.e.,

$\displaystyle\min_{P\in{\cal M}_{a}}J_{\gamma}(P,Q)$
$\displaystyle=J_{\gamma}(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal F}_{3}[Q]],Q)$
$\displaystyle=\gamma D(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal F}_{3}[Q]]\|{\cal
F}_{3}[Q])-\gamma\log\kappa[Q],$ (9) $\displaystyle J_{\gamma}(P,Q)$
$\displaystyle=\min_{P^{\prime}\in{\cal M}_{a}}J_{\gamma}(P^{\prime},Q)+\gamma
D(P\|\Gamma^{(m)}_{{\cal M}_{a}}[{\cal F}_{3}[Q]])$ (10)
$\displaystyle=J_{\gamma}(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[Q]],Q)+\gamma D(P\|\Gamma^{(m)}_{{\cal M}_{a}}[{\cal F}_{3}[Q]]).$ (11)

###### Proof

We have the following relations.

$\displaystyle J_{\gamma}(P,Q)=\gamma\sum_{x\in{\cal X}}P(x)(\log P(x)-\log
Q(x)+\frac{1}{\gamma}\Psi[Q](x))$ $\displaystyle=$
$\displaystyle\gamma\sum_{x\in{\cal X}}P(x)(\log P(x)-\log{\cal
F}_{3}[Q](x)-\log\kappa[Q])$ $\displaystyle=$ $\displaystyle\gamma D(P\|{\cal
F}_{3}[Q])-\gamma\log\kappa[Q]$ $\displaystyle=$ $\displaystyle\gamma
D(P\|\Gamma^{(m)}_{{\cal M}_{a}}[{\cal F}_{3}[Q]])+\gamma
D(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal F}_{3}[Q]]\|{\cal
F}_{3}[Q])-\gamma\log\kappa[Q],$ (12)

where the final equation follows from (4). Then, the minimum is given as (9),
and it is realized with $\Gamma^{(m)}_{{\cal M}_{a}}[{\cal F}_{3}[Q]]$.

Applying (9) to the final line of (12), we obtain (10). Since the minimum in
(10) is realized when $P^{\prime}=\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[Q]]$, we obtain (11).

As a generalization of another part of (RISB, , Lemma 3.2), we calculate
${\cal F}_{1}[Q]$. For this aim, we define

$\displaystyle D_{\Psi}(P\|Q):=\sum_{x\in{\cal
X}}P(x)(\Psi[P](x)-\Psi[Q](x)).$ (13)

###### Lemma 2

Assume that two distributions $P,Q\in{\cal M}_{a}$ satisfy the following
condition,

$\displaystyle D_{\Psi}(P\|Q)\leq\gamma D(P\|Q).$ (14)

Then, we have ${\cal F}_{1}[P]=P$, i.e.,

$\displaystyle J_{\gamma}(P,Q)\geq J_{\gamma}(P,P).$ (15)

###### Proof

Eq. (14) guarantees that

$\displaystyle J_{\gamma}(P,Q)-J_{\gamma}(P,P)$ $\displaystyle=$
$\displaystyle\gamma D(P\|Q)-\sum_{x\in{\cal
X}}P(x)(\Psi[P](x)-\Psi[Q](x))\geq 0.$ (16)

Therefore, when all pairs $(P^{(t+1)},P^{(t)})$ satisfy (14), the relations

$\displaystyle{\cal G}(P^{(t)})=J_{\gamma}(P^{(t)},P^{(t)})\geq
J_{\gamma}(P^{(t+1)},P^{(t)})\geq J_{\gamma}(P^{(t+1)},P^{(t+1)})={\cal
G}(P^{(t+1)})$ (17)

hold under Algorithm 1. In addition, we have the following theorem.

###### Theorem 2.1

When all pairs $(P^{(t+1)},P^{(t)})$ satisfy (14), i.e., the positive number
$\gamma$ is sufficiently large, Algorithm 1 converges to a local minimum.

###### Proof

Since $\\{{\cal G}(P^{(t)})\\}$ is monotonically decreasing for $t$, we have

$\displaystyle\lim_{n\to\infty}{\cal G}(P^{(t)})-{\cal G}(P^{(t+1)})=0.$ (18)

Using (11), we have

$\displaystyle{\cal G}(P^{(t)})=J_{\gamma}(P^{(t)},P^{(t)})$ $\displaystyle=$
$\displaystyle\gamma D(P^{(t)}\|P^{(t+1)})+J_{\gamma}(P^{(t+1)},P^{(t)})$
$\displaystyle\geq$ $\displaystyle\gamma D(P^{(t)}\|P^{(t+1)})+{\cal
G}(P^{(t+1)})$ (19)

Thus, we have

$\displaystyle\gamma D(P^{(t)}\|P^{(t+1)})\leq{\cal G}(P^{(t)})-{\cal
G}(P^{(t+1)}).$ (20)

Since due to (18) and (20), the sequence $\\{{\cal G}(P^{(t)})\\}$ is a Cauchy
sequence, it converges.

To discuss the detail of Algorithm 1, we focus on the $\delta$-neighborhood
$U(P^{0},\delta)$ of $P^{0}$ defined as

$\displaystyle U(P^{0},\delta):=\\{P\in{\cal M}_{a}|D(P^{0}\|P)\leq\delta\\}.$
(21)

In particular, we denote ${\cal M}_{a}$ by $U(P^{0},\infty)$. Then, we address
the following conditions for the $\delta$-neighborhood $U(P^{0},\delta)$ of
$P^{0}$;

(A0)

Any distribution $Q\in U(P^{0},\delta)$ satisfies the inequality

$\displaystyle{\cal G}({\cal F}_{2}[Q])\geq{\cal G}(P^{0}).$ (22)

(A1)

Any distribution $Q\in U(P^{0},\delta)$ satisfy

$\displaystyle D_{\Psi}({\cal F}_{2}[Q]\|Q)\leq\gamma D({\cal F}_{2}[Q]\|Q).$
(23)

(A2)

Any distribution $Q\in U(P^{0},\delta)$ satisfies

$\displaystyle D_{\Psi}(P^{0}\|Q)\geq 0.$ (24)

(A3)

There exists a positive number $\beta>0$ such that any distribution $Q\in
U(P^{0},\delta)$ satisfies

$\displaystyle D_{\Psi}(P^{0}\|Q)=\sum_{x\in{\cal
X}}P^{0}(x)(\Psi[P^{0}](x)-\Psi[Q](x))\geq\beta D(P^{0}\|Q).$ (25)

The condition (A3) is a stronger version of (A2).

However, the convergence to the global minimum is not guaranteed. As a
generalization of (RISB, , Theorem 3.3), the following theorem discusses the
convergence to the global minimum and the convergence speed.

###### Theorem 2.2

Assume that the $\delta$-neighborhood $U(P^{0},\delta)$ of $P^{0}$ satisfies
the conditions (A1) and (A2) with $\gamma$, and $P^{(1)}\in U(P^{0},\delta)$.
Then, Algorithm 1 with $t_{0}$ iterations has one of the following two
behaviors.

(i)

There exists an integer $t_{1}\leq t_{0}+1$ such that

$\displaystyle{\cal G}(P^{(t_{1})})<{\cal G}(P^{0}).$ (26)

(ii)

Algorithm 1 satisfies the conditions $\\{P^{(t)}\\}_{t=1}^{t_{0}+1}\subset
U(P^{0},\delta)$ and

$\displaystyle{\cal G}(P^{(t_{0}+1)})-{\cal G}(P^{0})\leq\frac{\gamma
D(P^{0}\|P^{(1)})}{t_{0}}.$ (27)

When the condition (A0) holds additionally, Algorithm 1 with $t_{0}$
iterations satisfies (ii).

The above theorem is shown in Appendix B. Now, we choose an element
$P^{*}\in{\cal M}_{a}$ to satisfy ${\cal G}(P^{*})=\min_{P\in{\cal
M}_{a}}{\cal G}(P)$. Then, $U(P^{*},\infty)={\cal M}_{a}$ with $P^{*}$
satisfies the condition (A0). When $U(P^{*},\infty)={\cal M}_{a}$ with $P^{*}$
satisfies the conditions (A1) and (A2), Theorem 2.2 guarantees the convergence
to the minimizer $P^{*}$ in Algorithm 1. Although we consider the conditions
(A1) and (A2), the condition (A2) is essential. When we choose $\gamma>0$ to
be sufficiently large and $\delta\neq\infty$, the $\delta$-neighborhood
$U(P^{*},\delta)$ of $P^{*}$ satisfies the condition (A1) with $\gamma$
because $U(P^{*},\delta)$ is a compact set. Hence, Theorem 2.2 guarantees the
convergence of Algorithm 1. That is, it is essential to check the condition
(A2).

However, as seen in (27), a larger $\gamma$ makes the convergence speed
slower. Therefore, it is important to choose $\gamma$ to be small under the
condition (A1). Practically, it is better to change $\gamma$ to be smaller
when the point $P^{(t)}$ is closer to the minimizer $P^{*}$. In fact, as a
generalization of (RISB, , Proposition 3.6), we have the following exponential
convergence under a stronger condition dependently of $\gamma$. In this sense,
the parameter is called an acceleration parameter (RISB, , Remark 3.4).

###### Theorem 2.3

Assume that the $\delta$-neighborhood $U(P^{0},\delta)$ of $P^{0}$ satisfies
the conditions (A1) and (A3) with $\gamma$, and $P^{(1)}\in U(P^{0},\delta)$.
Then, Algorithm 1 with $t_{0}$ iterations has one of the following two
behaviors.

(i)

There exists an integer $t_{1}\leq t_{0}+1$ such that

$\displaystyle{\cal G}(P^{(t_{1})})<{\cal G}(P^{0}).$ (28)

(ii)

Algorithm 1 satisfies the conditions $\\{P^{(t)}\\}_{t=1}^{t_{0}+1}\subset
U(P^{0},\delta)$ and

$\displaystyle{\cal G}(P^{(t_{0}+1)})-{\cal
G}(P^{0})\leq(1-\frac{\beta}{\gamma})^{t_{0}}D(P^{0}\|P^{(1)}).$ (29)

When the condition (A0) holds additionally, Algorithm 1 with $t_{0}$
iterations satisfies (ii).

The above theorem is shown in Appendix C. Next, we consider the case when
there are several local minimizers $P^{*}_{1},\ldots,P^{*}_{n}\in{\cal M}_{a}$
while the true minimizer is $P^{*}$. These local minimizers are characterized
by the following corollary, which is shown in Appendix B as a corollary of
Theorem 2.2.

###### Corollary 1

$\displaystyle D_{\Psi}(P^{*}\|P^{*}_{i})=\sum_{x\in{\cal
X}}P^{*}(x)(\Psi[P^{*}](x)-\Psi[P^{*}_{i}](x))={\cal G}(P^{*})-{\cal
G}(P^{*}_{i})<0.$ (30)

Hence, if there exist local minimizers, $U(P^{*},\infty)={\cal M}_{a}$ with
$P^{*}$ does not satisfy the condition (A2). In this case, when the
$\delta$-neighborhood $U(P^{*}_{i},\delta)$ of $P^{*}_{i}$ satisfies the
conditions (A0), (A1), and (A2), Algorithm 1 converges to the local minimizer
$P^{*}_{i}$ with the speed (27) except for the case (i). Since $P^{*}_{i}$ is
a local minimizer, the $\delta$-neighborhood $U(P^{*}_{i},\delta)$ of
$P^{*}_{i}$ satisfies the conditions (A0) and (A1) with sufficiently small
$\delta>0$. When the following condition (A4) holds, as shown below, the
$\delta$-neighborhood $U(P^{*}_{i},\delta)$ of $P^{*}_{i}$ satisfies the
condition (A2) with sufficiently small $\delta>0$. That is, when the initial
point belongs to the $\delta$-neighborhood $U(P^{*}_{i},\delta)$, Algorithm 1
converges to $P^{*}_{i}$.

(A4)

The function $\eta\mapsto\Psi[P_{\eta}](x)$ is differentiable, and the
relation

$\displaystyle\sum_{x\in{\cal
X}}P_{\eta}(x)\Big{(}\frac{\partial}{\partial\eta_{i}}\Psi[P_{\eta}](x)\Big{)}=0$
(31)

holds for $i=k+1,\ldots,l$ and $P_{\eta}\in{\cal M}_{a}$.

###### Lemma 3

We consider the following two conditions for a convex subset ${\cal
K}\subset{\cal M}_{a}$.

(B1)

The relation

$\displaystyle\sum_{x\in{\cal X}}P(x)(\Psi[P](x)-\Psi[Q](x))\geq 0$ (32)

holds for $P,Q\in{\cal K}$.

(B2)

${\cal G}(P)$ is convex for the mixture parameter in ${\cal K}$.

The condition (B1) implies the condition (B2). In addition, when the condition
(A4) holds, the condition (B2) implies the condition (B1).

When the function $\eta\mapsto\Psi[P_{\eta}](x)$ is twice-differentiable, and
the Hessian of ${\cal G}(P_{\eta})$ is strictly positive semi-definite at a
local minimizer $P^{*}_{i}$, this function is convex in the
$\delta$-neighborhood $U(P^{*}_{i},\delta)$ of $P^{*}_{i}$ with a sufficiently
small $\delta>0$ because the Hessian of ${\cal G}(P_{\eta})$ is strictly
positive semi-definite in the neighborhood. Then, Lemma 3 guarantees the
condition (A2) for the $\delta$-neighborhood $U(P^{*}_{i},\delta)$. Algorithm
1 converges to the local minimizer $P^{*}_{i}$ with the speed (27) except for
the case (i).

Proof of Lemma 3:  Assume the condition (B1). Then, for $\lambda\in[0,1]$, we
have

$\displaystyle\varphi(\lambda):=$ $\displaystyle\lambda{\cal
G}(P)+(1-\lambda){\cal G}(Q)-\lambda{\cal G}(\lambda P+(1-\lambda)Q)$
$\displaystyle=$ $\displaystyle\lambda\sum_{x\in{\cal
X}}P(x)(\Psi[P](x)-\Psi[\lambda P+(1-\lambda)Q](x))$
$\displaystyle+(1-\lambda)\sum_{x\in{\cal X}}Q(x)(\Psi[Q](x)-\Psi[\lambda
P+(1-\lambda)Q](x))$ $\displaystyle\geq$ $\displaystyle 0,$ (33)

which implies (B2).

Assume the conditions (A4) and (B2). Since $\varphi(\lambda)\geq 0$ for
$\lambda\in[0,1]$, we have

$\displaystyle 0\leq$
$\displaystyle\frac{d\varphi(\lambda)}{d\lambda}|_{\lambda=0}$
$\displaystyle=$ $\displaystyle{\cal G}(P)-{\cal G}(Q)-\sum_{x\in{\cal
X}}(P(x)-Q(x))\Psi[Q](x)$ $\displaystyle-\sum_{x\in{\cal
X}}Q(x)\frac{d\Psi[\lambda P+(1-\lambda)Q](x)}{d\lambda}|_{\lambda=0}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}$ $\displaystyle{\cal
G}(P)-{\cal G}(Q)-\sum_{x\in{\cal X}}(P(x)-Q(x))\Psi[Q](x),$ (34)

which implies (B1), where $(a)$ follows from the condition (A4). ∎

###### Remark 1

The reference RISB  considers the same problem setting with the quantum case.
Their case covers the case when ${\cal M}_{a}$ is given as ${\cal P}({\cal
X})$, and does not cover the case with a general mixture family ${\cal
M}_{a}$, To address the case with cost constraint, this extension is
essential. The ideas of Theorems 2.2 and 2.3 are quite similar to (RISB, ,
Theorem 3.3 and Proposition 3.6). However, these preceding studies consider
the case when $P^{0}$ and $U(P^{0},\delta)$ are $P^{*}$ and ${\cal P}({\cal
X})$, respectively. That is, they do not cover the case with local minimizers.

###  2.2 Algorithm with approximated iteration

In general, it is not so easy to calculate the $m$-projection
$\Gamma^{m}_{{\cal M}_{a}}({\cal F}_{3}[Q])$. We consider the case when it is
approximately calculated. There are two methods to calculate the
$m$-projection. One is the method based on the minimization in the given
mixture family, and the other is the method based on the minimization in the
exponential family orthogonal to the mixture family. In the first method, the
$m$-projection $\Gamma^{m}_{{\cal M}_{a}}({\cal F}_{3}[Q])$ is the minimizer
of the following minimization;

$\displaystyle\min_{P\in{\cal M}_{a}}D(P\|{\cal F}_{3}[Q]).$ (35)

To describe the second method, we define the exponential family

$\displaystyle Q_{\theta}(x):={\cal
F}_{3}[Q](x)e^{\sum_{j=1}^{k}\theta^{j}f_{j}(x)-\phi[Q](\theta)},$ (36)

where

$\displaystyle\phi[Q](\theta):=\log\sum_{x\in{\cal X}}{\cal
F}_{3}[Q](x)e^{\sum_{j=1}^{k}\theta^{j}f_{j}(x)}.$ (37)

The projected element $\Gamma^{(m)}_{{\cal M}_{a}}[{\cal F}_{3}[Q]]$ is the
unique element of the intersection $\\{Q_{\theta}\\}\cap{\cal M}_{a}$. Then,
the $m$-projection $\Gamma^{m}_{{\cal M}_{a}}({\cal F}_{3}[Q])$ is given as
the solution of the following equation;

$\displaystyle\frac{\partial\phi[Q]}{\partial\theta^{j}}(\theta)=\sum_{x\in{\cal
X}}Q_{\theta}(x)f_{j}(x)=a_{j}$ (38)

for $j=1,\ldots,k$. The solution of (38) is given as the minimizer of the
following minimization;

$\displaystyle\min_{\theta\in\mathbb{R}^{k}}\phi[Q](\theta)-\sum_{j=1}^{k}\theta^{j}a_{j}.$
(39)

We discuss the precision of our algorithm when each step has a certain error
in the above minimization.

However, the first method requires the minimization with the same number of
parameters as the original minimization $\min_{P\in{\cal M}_{a}}{\cal G}(P)$.
Hence, it is better to employ the second method. In fact, when ${\cal M}_{a}$
is given as a subset of ${\cal P}({\cal X})$ with one linear constraint, the
minimization (39) is written as a one-parameter convex minimization. Since any
one-parameter convex minimization is performed by the bisection method, which
needs $O(-\log\epsilon)$ iterations BV  to achieve a smaller error of the
minimum of the objective function than $\epsilon$, the cost of this
minimization is much smaller than that of the original minimization
$\min_{P\in{\cal M}_{a}}{\cal G}(P)$. To consider an algorithm based on the
minimization (39), we assume that $\Psi$ is defined in ${\cal P}({\cal X})$.
In the multi-parameter case, we can use the gradient method and the
accelerated proximal gradient method BT ; AT ; Nesterov ; Nesterov2 ;
Nesterov3 ; Teboulle .

Algorithm 2 Minimization of ${\cal G}(P)$ with an error in (35)

As inputs, we prepare the function $\Psi$, $l$ linearly independent functions
$f_{1},\ldots,f_{l}$, constraints $a_{1},\ldots,a_{k}$, a positive number
$\gamma,\epsilon_{1},\epsilon_{2}>0$, and the initial value
$P^{(1)}\in\mathcal{M}_{a}$;

repeat

Calculate the pair of $P^{(t+1)}\in{\cal M}_{a}$ and
$\bar{P}^{(t+1)}=Q_{\theta}$ with $Q=P^{(t)}$ to satisfy
$\displaystyle\phi[\bar{P}^{(t)}](\theta)-\sum_{j=1}^{k}\theta^{j}a_{j}$
$\displaystyle\leq\min_{\theta^{\prime}\in\mathbb{R}^{k}}\phi[\bar{P}^{(t)}](\theta^{\prime})-\sum_{j=1}^{k}{\theta^{\prime}}^{j}a_{j}+\epsilon_{1}$
(40) $\displaystyle D(\bar{P}^{(t+1)}\|P^{(t+1)})$
$\displaystyle\leq\epsilon_{2}.$ (41)

until $t=t_{1}-1$.

final step: We output the final estimate
$P_{f}^{(t_{1})}:=P^{(t_{2})}\in\mathcal{M}$ by using $t_{2}:=\mathop{\rm
argmin}\limits_{t=2,\ldots,t_{1}}{\cal G}(P^{(t)})-\gamma
D(P^{(t)}\|\bar{P}^{(t)})$.

To consider the convergence of Algorithm 2, we extend the conditions (A1) and
(A2). For this aim, we focus on the $\delta$-neighborhood
$\bar{U}(P^{0},\delta)$ of $P^{0}\in{\cal M}_{a}$ defined as

$\displaystyle\bar{U}(P^{0},\delta):=\\{P\in{\cal P}({\cal
X})|D(P^{0}\|P)\leq\delta\\}.$ (42)

Then, we introduce the following conditions for the $\delta$-neighborhood
$\bar{U}(P^{0},\delta)$ of $P^{0}$ as follows.

(A1+)

A distribution $Q\in\bar{U}(P^{0},\delta)\cap{\cal M}_{a}={U}(P^{0},\delta)$
satisfies the following condition with a positive real number
$\epsilon_{2}>0$. When a distribution $P\in{\cal M}_{a}$ satisfies $D(P\|{\cal
F}_{2}[Q])\leq\epsilon_{2}$, we have

$\displaystyle\sum_{x\in{\cal X}}P(x)(\Psi[P](x)-\Psi[Q](x))\leq\gamma
D(P\|Q).$ (43)

(A2+)

A distribution $Q\in\bar{U}(P^{0},\delta)$ satisfies (24).

The convergence of Algorithm 2 is guaranteed in the following theorem.

###### Theorem 2.4

Assume that the $\delta$-neighborhood $\bar{U}(P^{0},\delta)$ of $P^{0}$
satisfies the conditions (A1+) and (A2+) with two positive real numbers
$\gamma>0$, $\epsilon_{2}>0$, and $P^{(1)}\in U(P^{0},\delta)$. Then, for a
positive real number $\epsilon_{1}>0$, Algorithm 2 satisfies the conditions

$\displaystyle D(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[\bar{P}^{(t)}]]\|\bar{P}^{(t+1)})$ $\displaystyle\leq\epsilon_{1}$ (44)
$\displaystyle{\cal G}(P_{f}^{(t_{1})})-{\cal G}(P^{*})$
$\displaystyle\leq\frac{\gamma
D(P^{*}\|P^{(1)})}{t_{1}-1}+\epsilon_{1}+\gamma\epsilon_{2}.$ (45)

The above theorem is shown in Appendix D. We discussed the convergences of
Algorithms 1 and 2 under several conditions. When these conditions do not
hold, we cannot guarantee its global convergence but, the algorithms achieve a
local minimum. Hence, we need to repeat these algorithms by changing the
initial value.

###### Remark 2

To address the minimization with a cost constraint, the paper YSM  added a
linear penalty term to the objective function. However, this method does not
guarantee that the obtained result satisfies the required cost constraint. Our
method can be applied to any mixture family including the distribution family
with cost constraint(s). Hence, our method directly can be applied without the
above modification while we need to calculate the m-projection. As explained
in this subsection, this m-projection can be obtained with the convex
minimization whose number of variables is the number of the constraint to
define the mixture family. If the number of the constraint is not so large,
still the m-projection is feasible.

###  2.3 Combination of gradient method and Algorithm 1

Although we can use the gradient method to calculate (39) for a general
mixture family ${\cal M}_{a}$, in order to calculate $\overline{{\cal
G}}(a):=\min_{P\in{\cal M}_{a}}{\cal G}(P)$ with $a\in\mathbb{R}^{k}$, we
propose another algorithm to combine the gradient method and Algorithm 1. This
algorithm avoids the calculation of the $m$-projection $\Gamma^{(m)}_{{\cal
M}_{a}}$. For simplicity, we calculate $\overline{{\cal G}}(0)$ and assume
that the function $\overline{{\cal G}}(a)$ is convex. In the following, we
denote the expectation of the function $f$ under the distribution $P$ by
$P[f]$.

Then, we consider the following functions by using Legendre transform; For
$b=(b^{1},\ldots,b^{k})\in\mathbb{R}^{k}$ and
$c=(c^{1},\ldots,c^{l-k})\in\mathbb{R}^{l-k}$, we define

$\displaystyle{\cal G}_{*}(b,c):=$ $\displaystyle\sup_{P\in{\cal P}({\cal
X})}\sum_{i=1}^{k}b^{i}P[f_{i}]+\sum_{j=1}^{l-k}c^{i}P[f_{k+i}]-{\cal G}(P),$
(46)

and

$\displaystyle\overline{{\cal G}}_{*}(b):=$ $\displaystyle{\cal
G}_{*}(b,0)=\sup_{P\in{\cal P}({\cal X})}\sum_{i=1}^{k}b^{i}P[f_{i}]-{\cal
G}(P)=\sup_{a\in\mathbb{R}^{k}}\sum_{i=1}^{k}b^{i}a_{i}-\overline{{\cal
G}}(a).$ (47)

In the following, we consider the calculation of $\overline{{\cal G}}(0)$ by
assuming that the function $\eta\mapsto{\cal G}(P_{\eta})$ is
$C^{2}$-continuous and convex. Since Legendre transform of $\overline{{\cal
G}}_{*}(b)$ is $\overline{{\cal G}}_{(}a)$ due to the convexity of
$\overline{{\cal G}}_{(}a)$, we have
$\sup_{b\in\mathbb{R}^{k}}\sum_{i=1}^{k}b^{i}a_{i}-\overline{{\cal
G}}_{*}(b)=\overline{{\cal G}}(a)$. As a special case, we have

$\displaystyle-\inf_{b\in\mathbb{R}^{k}}\overline{{\cal
G}}_{*}(b)=\overline{{\cal G}}(0).$ (48)

That is, when we find the minimizer $b_{*}:=\mathop{\rm
argmin}\limits_{a\in\mathbb{R}^{k}}\overline{{\cal G}}_{*}(b)$, we can
calculate $\overline{{\cal G}}(0)$ as $\overline{{\cal G}}(0)=-\sup_{P\in{\cal
P}({\cal X})}\sum_{i=1}^{k}b_{*}^{i}P[f_{i}]-{\cal G}(P)=\inf_{P\in{\cal
P}({\cal X})}{\cal G}(P)-\sum_{i=1}^{k}b_{*}^{i}P[f_{i}]$.

To find it, we denote the gradient vector of a function $f$ on
$\mathbb{R}^{k}$ by $\nabla f$. That is, $\nabla f$ is the vector
$(\frac{\partial}{\partial x^{1}}f,\ldots,\frac{\partial}{\partial x^{k}}f)$.
Then, we choose a real number $L$ that is larger than the matrix norm of the
Hessian of $\overline{{\cal G}}_{*}$, which implies the uniform Lipschitz
condition;

$\displaystyle\|\nabla\overline{{\cal G}}_{*}(b)-\nabla\overline{{\cal
G}}_{*}(b^{\prime})\|\leq L\|b-b^{\prime}\|.$ (49)

Then, we apply the following update rule for the minimization of
$\overline{{\cal G}}_{*}(b)$;

$\displaystyle b_{t+1}:=b_{t}-\frac{1}{L}\nabla\overline{{\cal
G}}_{*}(b_{t}).$ (50)

The following precision is guaranteed (Beck, , Chapter 10) BT ; Nesterov ;

$\displaystyle|\overline{{\cal G}}_{*}(b_{k})-\overline{{\cal
G}}_{*}(b_{*})|\leq\frac{L}{2k}\|b_{*}-b_{0}\|^{2}.$ (51)

However, since the calculation of (53) requires a large calculation amount.
Hence, replacing it by a one-step iteration in Algorithm 1, we propose another
algorithm. For this aim, we notice that

$\displaystyle\nabla\overline{{\cal G}}_{*}(b)=\mathop{\rm
argmax}\limits_{a\in\mathbb{R}^{k}}\sum_{i=1}^{k}b^{i}a_{i}-\overline{{\cal
G}}(a)=(Q_{b}[f_{i}])_{i=1}^{k},$ (52)

where

$\displaystyle Q_{b}:=\mathop{\rm argmax}\limits_{P\in{\cal P}({\cal
X})}\sum_{i=1}^{k}b^{i}P[f_{i}]-{\cal G}(P)=\mathop{\rm
argmin}\limits_{P\in{\cal P}({\cal X})}\sum_{x\in{\cal
X}}P(x)\Big{(}\Psi[P](x)-\sum_{i=1}^{k}b^{i}f_{i}(x)\Big{)}.$ (53)

Using ${\cal
F}_{3}^{b}[Q](x):=\frac{1}{\kappa}Q(x)\exp(-\frac{1}{\gamma}\Big{(}\Psi[P](x)-\sum_{i=1}^{k}b^{i}f_{i}(x)\Big{)}$
with the normalizing constant $\kappa$, we propose Algorithm 3.

Algorithm 3 Minimization of ${\cal G}(P)$

As inputs, we prepare the function $\Psi$, $l$ linearly independent functions
$f_{1},\ldots,f_{l}$, a positive number $\gamma>0$, and the initial values
$P^{(1)}\in\mathcal{M}_{0}$, $b_{1}\in\mathbb{R}^{k}$;

repeat

Calculate $P^{(t+1)}:={\cal F}_{3}^{b_{t}}[P^{(t)}]$ and
$b_{t+1}:=b_{t}-\frac{1}{L}(P^{(t+1)}[f_{i}])_{i=1}^{k}$;

until convergence. We denote the convergent by $(P^{(\infty)},b_{\infty})$.

Output $P^{(\infty)}$ and ${\cal G}(P^{(\infty)})$.

It is not so easy to evaluate the convergence speed of Algorithm 3. But, when
it converges, the convergent point is the true minimizer.

###### Theorem 2.5

When the pair $(b,P)$ is a convergence point, we have $b=b_{*}$ and $P=P_{*}$.

###### Proof

Since the pair $(b,P)$ is a convergence point, we have $P={\cal
F}_{3}^{b}[P]$, which implies

$\displaystyle\sum_{i=1}^{k}b^{i}P[f_{i}]-{\cal G}(P)=\sup_{P^{\prime}\in{\cal
P}({\cal X})}\sum_{i=1}^{k}b^{i}P^{\prime}[f_{i}]-{\cal
G}(P^{\prime})=\overline{{\cal G}}_{*}(b).$ (54)

Since the pair $(b,P)$ is a convergence point, we have $P[f_{i}]=0$ for
$i=1,\ldots,k$, i.e., the distribution $P$ satisfies the required condition in
(1). the relation (52) implies $\nabla\overline{{\cal G}}_{*}(b)=0$. Hence,
(48) yields $\overline{{\cal G}}_{*}(b)=\overline{{\cal G}}(0)$, which implies
$b=b_{*}$. Therefore, the relation (54) is rewritten as ${\cal
G}(P)=\overline{{\cal G}}(0)$, which implies $P=P_{*}$.

###### Remark 3

We compare our algorithm with the general algorithm proposed in YSM . The
input of the objective function in YSM  forms a mixture family. The function
$f$ given in (YSM, , (6)) satisfies the condition of ${\cal G}$ by considering
the second line of (YSM, , (6)) as $\Psi$. Their algorithm is the same as
Algorithm 1 with $\gamma=1$ when there is no constraint because their extended
objective function $g$ defined in (YSM, , (16)) can be considered as
$D(P\|Q)+\sum_{x\in{\cal X}}P(x)\Psi[Q](x)$, where the choice of $q$ in YSM
corresponds to the choice of $P$ and the choice of $Q_{1},\ldots,Q_{K}$ in YSM
does to the choice of $Q$.

Also, we can show that the function $f$ given in (YSM, , (6)) satisfies the
condition (A4). Since the condition (A4) holds, the convexity of $f$ is
equivalent to the condition (B1). This equivalence in this case was shown as
(YSM, , Proposition 4.1). They showed the convergence of their algorithm as
(YSM, , Theorem 4.1), which can be considered as a special case of our Theorem
2.2.

However, our treatment for the constraint is different from theirs. They
consider the minimization $\min_{P\in{\cal P}({\cal X})}{\cal
G}(P)-\sum_{i=1}^{k}b^{i}P[f_{i}]$ without updating the parameter $b$. Hence,
their algorithm cannot achieve the minimum with the desired constraint while
Algorithms 1, 2, and 3 achieve the minimum with the desired constraint.
Although their algorithm is similar to Algorithm 3, Algorithm 3 updates the
parameter $b$ to achieve the minimum with the desired constraint.

##  3 Application to information theoretical problems

###  3.1 Channel capacity

According to the reference RISB , we apply our problem setting to the channel
coding. A channel is given as a conditional distributions $W_{Y|X=x}$ on the
sample space ${\cal Y}$ with conditions the sample space ${\cal X}$, where
${\cal Y}$ is a general sample space with a measure $\mu$ and ${\cal X}$ is a
finite sample space. For two absolutely continuous distributions $P_{Y}$ and
$Q_{Y}$ with respect to $\mu$ on ${\cal Y}$, the Kullback-Leibler divergence
$D(P_{Y}\|Q_{Y})$ is given as

$\displaystyle D(P_{Y}\|Q_{Y}):=\int_{{\cal Y}}p_{Y}(y)(\log p_{Y}(y)-\log
q_{Y}(y))\mu(dy),$ (55)

where $p_{Y}$ and $q_{Y}$ are the probability density functions of $P_{Y}$ and
$Q_{Y}$ with respect to $\mu$. This quantity is generalized to the Renyi
divergence with order $\alpha>0$ as

$\displaystyle D_{\alpha}(P_{Y}\|Q_{Y}):=\frac{1}{\alpha-1}\log\int_{{\cal
Y}}\Big{(}\frac{p_{Y}(y)}{q_{Y}(y)}\Big{)}^{\alpha-1}p_{Y}(y)\mu(dy).$ (56)

The channel capacity $C(W_{Y|X})$ is given as the maximization of the mutual
information $I(P_{X},W_{Y|X})$ as Shannon

$\displaystyle C(W_{Y|X})$ $\displaystyle:=\max_{P_{X}}I(P_{X},W_{Y|X})$ (57)
$\displaystyle I(P_{X},W_{Y|X})$ $\displaystyle:=\sum_{x\in{\cal
X}}P_{X}(x)D(W_{Y|X=x}\|W_{Y|X}\cdot P_{X})$ $\displaystyle=D(P_{Y|X}\times
P_{X}\|(W_{Y|X}\cdot P_{X})\times P_{X}),$ (58)

where $W_{Y|X}\cdot P_{X}$ and $W_{Y|X}\times P_{X}$ are defined as the
following probability density functions $w_{Y|X}\cdot P_{X}$ and
$w_{Y|X}\times P_{X}$;

$\displaystyle(w_{Y|X}\cdot P_{X})(y)$ $\displaystyle:=\sum_{x\in{\cal
X}}P_{X}(x)w_{Y|X=x}(y)$ (59) $\displaystyle(w_{Y|X}\times P_{X})(x,y)$
$\displaystyle:=P_{X}(x)w_{Y|X=x}(y).$ (60)

However, the mutual information $I(P_{X},W_{Y|X})$ has another form as

$\displaystyle I(P_{X},W_{Y|X})=\min_{Q_{Y}}\sum_{x\in{\cal
X}}P_{X}(x)D(W_{Y|X=x}\|Q_{Y}).$ (61)

When we choose ${\cal M}_{a}$ and $\Psi$ as ${\cal P}({\cal X})$ and

$\displaystyle\Psi_{W_{Y|X}}[P_{X}](x):=-D(W_{Y|X=x}\|W_{Y|X}\cdot P_{X}),$
(62)

$-I(P_{X},W_{Y|X})$ coincides with ${\cal G}(P_{X})$ RISB . Since

$\displaystyle\sum_{x\in{\cal
X}}P_{X}(x)(\Psi[P_{X}](x)-\Psi[Q_{X}](x))=D(W_{Y|X}\cdot P_{X}\|W_{Y|X}\cdot
Q_{X})\geq 0,$ (63)

the condition (A2) holds with ${\cal P}({\cal X})$. In addition, since the
information processing inequality guarantees that

$\displaystyle D(W_{Y|X}\cdot P_{X}\|W_{Y|X}\cdot Q_{X})\leq D(P_{X}\|Q_{X}),$
(64)

the condition (A1) holds with $\gamma=1$ and ${\cal P}({\cal X})$. In this
case, ${\cal F}_{3}$ is given as

$\displaystyle{\cal
F}_{3}[Q_{X}](x)=\frac{1}{\kappa_{W_{Y|X}}[Q_{X}]}Q_{X}(x)\exp(\frac{1}{\gamma}D(W_{Y|X=x}\|W_{Y|X}\cdot
Q_{X})),$ (65)

where the normalizing constant $\kappa_{W_{Y|X}}[Q_{X}]$ is given as

$\displaystyle\kappa_{W_{Y|X}}[Q_{X}]=\sum_{x\in{\cal
X}}Q_{X}(x)\exp(\frac{1}{\gamma}D(W_{Y|X=x}\|W_{Y|X}\cdot Q_{X})).$ (66)

When $\gamma=1$, it coincides with Arimoto-Blahut algorithm Arimoto ; Blahut .
Since ${\cal F}_{3}[Q_{X}]\in{\cal P}({\cal X})$, $P_{X}^{(t+1)}$ is given as
${\cal F}_{3}[P_{X}^{(t)}]$.

###### Remark 4

Since the reference RISB  covers the case when ${\cal M}_{a}$ is given as
${\cal P}({\cal X})$, the algorithms presented in this section are presented
by including the case when $Y$ is a quantum system. Also, they proposed an
adaptive choice of $\gamma$ in this case (RISB, , (22)). In addition, they
numerically compared their adaptive choice with the case of $\gamma=1$ (RISB,
, Figs. 1,…, 6). These comparisons show a significant improvement by their
adaptive choice.

###  3.2 Reliability function in channel coding

In channel coding, we consider the reliability function, which was originally
introduced by Gallager Gallager  and expresses the exponential decreasing rate
of an upper bound of the decoding block error probability under the random
coding. To achieve this aim, for $\alpha>0$, we define

$\displaystyle
I_{\alpha}(P_{X},W_{Y|X}):=\frac{\alpha}{\alpha-1}\log\Big{(}\int_{{\cal
Y}}\Big{(}\sum_{x\in{\cal
X}}P_{X}(x)w_{Y|X=x}(y)^{\alpha}\Big{)}^{\frac{1}{\alpha}}\mu(dy)\Big{)}$ (67)

while this parameterization is different from the original parameterization by
Gallager . Then, when the code is generated with the random coding based on
the distribution $P_{X}$, the decoding block error probability with coding
rate $R$ is upper bounded by the following quantity;

$\displaystyle e^{n\min_{\rho\in[0,1]}\rho R-\rho
I_{\frac{1}{1+\rho}}(P_{X},W_{Y|X})}$ (68)

when we use the channel $W_{Y|X}$ with $n$ times. Notice that $e^{-\rho
I_{\frac{1}{1+\rho}}(P_{X},W_{Y|X})}=\int_{{\cal Y}}\Big{(}\sum_{x\in{\cal
X}}P_{X}(x)w_{Y|X=x}(y)^{\frac{1}{1+\rho}}\Big{)}^{1+\rho}\mu(dy)$. Taking the
minimum for the choice of $P_{X}$, we have

$\displaystyle\min_{P_{X}}e^{\min_{\rho\in[0,1]}\rho R-\rho
I_{\frac{1}{1+\rho}}(P_{X},W_{Y|X})}=\min_{\alpha\in[1/2,1]}\Big{(}e^{-\frac{\alpha-1}{\alpha}R}\min_{P_{X}}e^{\frac{\alpha-1}{\alpha}I_{\alpha}(P_{X},W_{Y|X})}\Big{)}$
(69)

with $\alpha=\frac{1}{1-\rho}\in[1/2,1]$. Therefore, we consider the following
minimization;

$\displaystyle\min_{P_{X}}e^{\frac{\alpha-1}{\alpha}I_{\alpha}(P_{X},W_{Y|X})}=\min_{P_{X}}\int_{{\cal
Y}}\Big{(}\sum_{x\in{\cal
X}}P_{X}(x)w_{Y|X=x}(y)^{\alpha}\Big{)}^{\frac{1}{\alpha}}\mu(dy).$ (70)

In the following, we discuss the RHS of (70) with $\alpha\in[1/2,1]$.

To apply our method, as a generalization of (61), we consider another
expression of $I_{\alpha}(P_{X},W_{Y|X})$;

$\displaystyle I_{\alpha}(P_{X},W_{Y|X})=\min_{Q_{Y}}D_{\alpha}(W_{Y|X}\times
P_{X}\|Q_{Y}\times P_{X}),$ (71)

which was shown in (H15, , Lemma 2). Using

$\displaystyle Q_{Y|\alpha,P_{X}}:=$ $\displaystyle\mathop{\rm
argmin}\limits_{Q_{Y}}D_{\alpha}(W_{Y|X}\times P_{X}\|Q_{Y}\times P_{X})$
$\displaystyle=$ $\displaystyle\mathop{\rm
argmax}\limits_{Q_{Y}}\sum_{x\in{\cal
X}}P_{X}(x)e^{(\alpha-1)D_{\alpha}(W_{Y|X=x}\|Q_{Y})},$ (72)

we have

$\displaystyle\Big{(}\min_{P_{X}}e^{\frac{\alpha-1}{\alpha}I_{\alpha}(P_{X},W_{Y|X})}\Big{)}^{\alpha}=\min_{P_{X}}\sum_{x\in{\cal
X}}P_{X}(x)e^{(\alpha-1)D_{\alpha}(W_{Y|X=x}\|Q_{Y|\alpha,P_{X}})}.$ (73)

The probability density function $q_{Y|\alpha,P_{X}}$ of the minimizer
$Q_{Y|\alpha,P_{X}}$ is calculated as

$\displaystyle q_{Y|\alpha,P_{X}}(y)=C\Big{(}\sum_{x\in{\cal
X}}P_{X}(x)w_{Y|X=x}(y)^{\alpha}\Big{)}^{\frac{1}{\alpha}},$ (74)

where $C$ is the normalized constant (H15, , Lemma 2).

To solve the minimization (73), we apply our method to the case when we choose
${\cal M}_{a}$ and $\Psi$ as ${\cal P}({\cal X})$ and

$\displaystyle\Psi_{\alpha,W_{Y|X}}[P_{X}](x):=e^{(\alpha-1)D_{\alpha}(W_{Y|X=x}\|Q_{Y|\alpha,P_{X}})}.$
(75)

Since (72) guarantees that

$\displaystyle\sum_{x\in{\cal
X}}P_{X}(x)(\Psi_{\alpha,W_{Y|X}}[P_{X}](x)-\Psi_{\alpha,W_{Y|X}}[Q_{X}](x))$
$\displaystyle=$ $\displaystyle\sum_{x\in{\cal
X}}P_{X}(x)\Big{(}e^{(\alpha-1)D_{\alpha}(W_{Y|X=x}\|Q_{Y|\alpha,P_{X}})}-e^{(\alpha-1)D_{\alpha}(W_{Y|X=x}\|Q_{Y|\alpha,Q_{X}})}\Big{)}\geq
0,$ (76)

the condition (A2) holds with ${\cal P}({\cal X})$. The condition (A1) can be
satisfied with sufficiently large $\gamma$. In this case, ${\cal F}_{3}$ is
given as

$\displaystyle{\cal
F}_{3,\alpha}[Q_{X}](x)=\frac{1}{\kappa_{\alpha,W_{Y|X}}[Q_{X}]}Q_{X}(x)\exp(-\frac{1}{\gamma}e^{(\alpha-1)D_{\alpha}(W_{Y|X=x}\|Q_{Y|\alpha,P_{X}})}),$
(77)

where the normalizing constant $\kappa_{\alpha,W_{Y|X}}[Q_{X}]$ is given as
$\kappa_{\alpha,W_{Y|X}}[Q_{X}]=$

$\sum_{x\in{\cal
X}}Q_{X}(x)\exp(-\frac{1}{\gamma}e^{(\alpha-1)D_{\alpha}(W_{Y|X=x}\|Q_{Y|\alpha,P_{X}})})$.
Since ${\cal F}_{3,\alpha}[Q_{X}]\in{\cal M}_{a}$, $P_{X}^{(t+1)}$ is given as
${\cal F}_{3,\alpha}[P_{X}^{(t)}]$.

###  3.3 Strong converse exponent in channel coding

In channel coding, we discuss an upper bound of the probability of correct
decoding. This probability is upper bounded by the following quantity;

$\displaystyle\max_{P_{X}}e^{n\min_{\rho\in[0,1]}\Big{(}-\rho R+\rho
I_{\frac{1}{1-\rho}}(P_{X},W_{Y|X})\Big{)}}$ (78)

when we use the channel $P_{Y|X}$ with $n$ times and the coding rate is $R$
Arimoto2 . Therefore, we consider the following maximization;

$\displaystyle\max_{P_{X}}e^{\rho
I_{\frac{1}{1-\rho}}(P_{X},W_{Y|X})}=\max_{P_{X}}e^{\frac{\alpha-1}{\alpha}I_{\alpha}(P_{X},W_{Y|X})}$
(79)

with $\alpha=\frac{1}{1-\rho}>1$. In the following, we discuss the RHS of (79)
with $\alpha>1$.

To apply our method, we consider another expression (71) of
$I_{\alpha}(P_{X},W_{Y|X})$. Using (72), we have

$\displaystyle\Big{(}\max_{P_{X}}e^{\frac{\alpha-1}{\alpha}I_{\alpha}(P_{X},W_{Y|X})}\Big{)}^{\alpha}=\max_{P_{X}}\sum_{x\in{\cal
X}}P_{X}(x)e^{(\alpha-1)D_{\alpha}(W_{Y|X=x}\|Q_{Y|\alpha,P_{X}})}.$ (80)

The maximization (80) can be solved by choosing ${\cal M}_{a}$ and $\Psi$ as
${\cal P}({\cal X})$ and

$\displaystyle\Psi_{\alpha,W_{Y|X}}[P_{X}](x):=-e^{(\alpha-1)D_{\alpha}(W_{Y|X=x}\|Q_{Y|\alpha,P_{X}})}.$
(81)

Since (72) guarantees that

$\displaystyle\sum_{x\in{\cal
X}}P_{X}(x)(\Psi_{\alpha,W_{Y|X}}[P_{X}](x)-\Psi_{\alpha,W_{Y|X}}[Q_{X}](x))$
$\displaystyle=$ $\displaystyle\sum_{x\in{\cal
X}}P_{X}(x)\Big{(}-e^{(\alpha-1)D_{\alpha}(W_{Y|X=x}\|Q_{Y|\alpha,P_{X}})}+e^{(\alpha-1)D_{\alpha}(W_{Y|X=x}\|Q_{Y|\alpha,Q_{X}})}\Big{)}\geq
0,$ (82)

the condition (A2) holds with ${\cal P}({\cal X})$. Similarly, the condition
(A1) can be satisfied with sufficiently large $\gamma$. In this case, ${\cal
F}_{3}$ is given as

$\displaystyle{\cal
F}_{3,\alpha}[Q_{X}](x)=\frac{1}{\kappa_{\alpha,W_{Y|X}}[Q_{X}]}Q_{X}(x)\exp(\frac{1}{\gamma}e^{(\alpha-1)D_{\alpha}(W_{Y|X=x}\|Q_{Y|\alpha,P_{X}})}),$
(83)

where the normalizing constant $\kappa_{\alpha,W_{Y|X}}[Q_{X}]$ is given as
$\kappa_{\alpha,W_{Y|X}}[Q_{X}]=$

$\sum_{x\in{\cal
X}}Q_{X}(x)\exp(\frac{1}{\gamma}e^{(\alpha-1)D_{\alpha}(W_{Y|X=x}\|Q_{Y|\alpha,P_{X}})})$.
Since ${\cal F}_{3,\alpha}[Q_{X}]\in{\cal M}_{a}$, $P_{X}^{(t+1)}$ is given as
${\cal F}_{3,\alpha}[P_{X}^{(t)}]$.

###  3.4 Wiretap channel capacity

####  3.4.1 General case

Given a pair of a channel $W_{Y|X}$ from ${\cal X}$ to a legitimate user
${\cal Y}$ and a channel $W_{Z|X}$ from ${\cal X}$ to a malicious user ${\cal
Z}$, the wiretap channel capacity is given as Wyner ; CK79

$\displaystyle C(W_{Y|X},W_{Z|X}):=\max_{P_{VX}}I(P_{V},W_{Y|X}\cdot
P_{X|V})-I(P_{V},W_{Z|X}\cdot P_{X|V})$ (84)

with a sufficiently large discrete set ${\cal V}$. The recent papers showed
that the above rate can be achieved even with strong security Csisz ; H06 ;
H11  and the semantic security BTV ; HM16 . Furthermore, the paper (HM16, ,
Appendix D) showed the above even when the output systems are general
continuous systems including Gaussian channels. The wiretap capacity (84) can
be calculated via the minimization;

$\displaystyle\min_{P_{VX}}-I(P_{V},W_{Y|X}\cdot P_{X|V})+I(P_{V},W_{Z|X}\cdot
P_{X|V}).$ (85)

Here, ${\cal V}$ is an additional discrete sample space. When we choose ${\cal
M}_{a}$ and $\Psi$ as ${\cal P}({\cal X}\times{\cal V})$ and

$\displaystyle\Psi_{W_{Y|X},W_{Z|X}}[P_{VX}](v,x)$ $\displaystyle:=$
$\displaystyle D(W_{Z|X}\cdot P_{X|V=v}\|W_{Z|X}\cdot P_{X})-D(W_{Y|X}\cdot
P_{X|V=v}\|W_{Y|X}\cdot P_{X}),$ (86)

$-I(P_{V},W_{Y|X}\cdot P_{X|V})+I(P_{V},W_{Z|X}\cdot P_{X|V})$ coincides with
${\cal G}(P_{VX})$. Hence, the general theory in Section 2 can be used for the
minimization (85). In this case, it is difficult to clarify whether the
conditions (A1) and (A2) hold in general. ${\cal F}_{3}$ is given as

$\displaystyle{\cal F}_{3}[Q_{VX}](v,x)$ $\displaystyle=$
$\displaystyle\frac{1}{\kappa_{W_{Y|X},W_{Z|X}}[Q_{VX}]}Q_{VX}(v,x)\exp\Big{(}\frac{1}{\gamma}\Big{(}D(W_{Y|X}\cdot
P_{X|V=v}\|W_{Y|X}\cdot P_{X})$ $\displaystyle-D(W_{Z|X}\cdot
P_{X|V=v}\|W_{Z|X}\cdot P_{X})\Big{)}\Big{)},$ (87)

where $\kappa_{W_{Y|X},W_{Z|X}}[Q_{VX}]$ is the normalizing constant. Since
${\cal F}_{3}[Q_{X}]\in{\cal M}_{a}$, $P_{X}^{(t+1)}$ is given as ${\cal
F}_{3}[P_{X}^{(t)}]$.

####  3.4.2 Degraded case

However, when there exists a channel $W_{Z|Y}$ from ${\cal Y}$ to ${\cal Z}$
such that $W_{Z|Y}\cdot W_{Y|X}=W_{Z|X}$, i.e., the channel $W_{Z|X}$ is a
degraded channel of $W_{Y|X}$, we can define the joint channel $W_{YZ|X}$ with
the following conditional probability density function

$\displaystyle w_{YZ|X}(yz|x):=w_{Z|Y}(z|y)w_{Y|X}(y|x).$ (88)

Then, the maximization (84) is simplified as

$\displaystyle C(W_{YZ|X}):=\max_{P_{X}}I(X;Y|Z)[P_{X},W_{YZ|X}]$ (89)

where the conditional mutual information is given as

$\displaystyle
I(X;Y|Z)[P_{X},W_{YZ|X}]:=\sum_{x,z}P_{XZ}(x,z)D(P_{Y|X=x,Z=z}\|P_{Y|Z=z}),$
(90)

where the conditional distributions $P_{Y|XZ}$ and $P_{Y|Z}$ are defined from
the joint distribution $W_{YZ|X}\times P_{X}$. To consider (89), we consider
the following minimization with a general two-output channel $W_{YZ|X}$;

$\displaystyle\min_{P_{X}}-I(X;Y|Z)[P_{X},W_{YZ|X}].$ (91)

When we choose ${\cal M}_{a}$ and $\Psi$ as ${\cal P}({\cal X})$ and

$\displaystyle\Psi_{W_{YZ|X}}[P_{X}](x):=-\sum_{z}P_{Z|X=x}(z)D(P_{Y|X=x,Z=z}\|P_{Y|Z=z}).$
(92)

$-I(X;Y|Z)[P_{X},W_{YZ|X}]$ coincides with ${\cal G}(P_{X})$. Hence, the
general theory in Section 2 can be used for the minimization (85). In this
case, as shown in Subsection 6.2, the conditions (A1) with $\gamma=1$ and (A2)
hold. ${\cal F}_{3}$ is given as

$\displaystyle{\cal F}_{3}[Q_{X}](x)$ $\displaystyle=$
$\displaystyle\frac{1}{\kappa_{W_{YZ|X}}[Q_{X}]}Q_{X}(x)\exp\Big{(}\frac{1}{\gamma}\Big{(}\sum_{z}P_{Z|X=x}(z)D(P_{Y|X=x,Z=z}\|P_{Y|Z=z})\Big{)}\Big{)},$
(93)

where $\kappa_{W_{YZ|X}}[Q_{X}]$ is the normalizing constant. Since ${\cal
F}_{3}[Q_{X}]\in{\cal M}_{a}$, $P_{X}^{(t+1)}$ is given as ${\cal
F}_{3}[P_{X}^{(t)}]$. The above algorithm with $\gamma=1$ coincides with that
by Yasui .

###  3.5 Capacities with cost constraint

Next, we consider the case when a cost constraint is imposed. Consider a
function $f$ on ${\cal X}$ and the following constraint for a distribution
$P_{X}\in{\cal X}$;

$\displaystyle P_{X}[f]=a.$ (94)

We define ${\cal M}_{a}$ by imposing the condition (94). The capacity under
the cost constraint is given as $\max_{P_{X}\in{\cal M}_{a}}I(P_{X},W_{Y|X})$.
That is, we need to solve the minimization $\min_{P_{X}\in{\cal
M}_{a}}-I(P_{X},W_{Y|X})$. In this case, the $t+1$-th distribution $P^{(t+1)}$
is given as $\Gamma_{{\cal M}_{a}}^{m}[{\cal F}_{3}[P_{X}^{(t)}]]$. Since
$\Gamma_{{\cal M}_{a}}^{m}[{\cal F}_{3}[P_{X}^{(t)}]]$ cannot be calculated
analytically, we can use Algorithm 2 instead of Algorithm 1. Since conditions
(A1) with $\gamma=1$ and (A2) hold, Theorem 2.4 guarantees the global
convergence to the minimum in Algorithm 2.

We can consider the cost constraint (94) for the problems (73) and (80). In
these cases, we have a similar modification by considering $\Gamma_{{\cal
M}_{a}}^{m}[{\cal F}_{3}[P_{X}^{(t)}]]$.

##  4 em problem

We apply our algorithm to the problem setting with em algorithm Amari ;
Fujimoto ; Allassonniere , which is a generalization of Boltzmann machines Bol
. The em algorithm is implemented by iterative applications of the projection
to an exponential family (the $e$-projection) and the projection to a mixture
family (the $m$-projection). Hence, this algorithm is called em algorithm. In
contrast, EM algorithm is implemented by iterative applications of expectation
and maximization. They are different algorithms. In particular, the
expectation in EM algorithm, which is often called E-step, corresponds to the
projection to a mixture family, which is often called $m$-step in em
algorithm. Also, the maximization in EM algorithm, which is often called
M-step, corresponds to the projection to an exponential family, which is often
called $e$-step in em algorithm.

For this aim, we consider a pair of an exponential family ${\cal E}$ and a
mixture family ${\cal M}_{a}$ on ${\cal X}$. We denote the $e$-projection to
${\cal E}$ of $P$ by $\Gamma_{\cal E}^{e}[P]$, which is defined as

$\displaystyle\Gamma_{\cal E}^{e}[P]:=\mathop{\rm argmin}\limits_{Q\in{\cal
E}}D(P\|Q).$ (95)

We consider the following minimization;

$\displaystyle\min_{P\in{\cal M}_{a}}\min_{Q\in{\cal
E}}D(P\|Q)=\min_{P\in{\cal M}_{a}}D(P\|\Gamma_{\cal E}^{e}[P])$
$\displaystyle=$ $\displaystyle\min_{P\in{\cal M}_{a}}\sum_{x\in{\cal
X}}P(x)(\log P(x)-\log\Gamma_{\cal E}^{e}[P](x)).$ (96)

We choose the function $\Psi$ as

$\displaystyle\Psi_{\rm{em}}[P](x):=(\log P(x)-\log\Gamma_{\cal
E}^{e}[P](x)),$ (97)

and apply the discussion in Section 2. Then, we have

$\displaystyle\sum_{x\in{\cal
X}}P^{0}(x)(\Psi_{\rm{em}}[P^{0}](x)-\Psi_{\rm{em}}[Q](x))$ $\displaystyle=$
$\displaystyle\sum_{x\in{\cal X}}P^{0}(x)\Big{(}(\log
P^{0}(x)-\log\Gamma_{\cal E}^{e}[P^{0}](x))-(\log Q(x)-\log\Gamma_{\cal
E}^{e}[Q](x))\Big{)}$ $\displaystyle=$ $\displaystyle\sum_{x\in{\cal
X}}P^{0}(x)(\log P^{0}(x)-\log Q(x))$ $\displaystyle+\sum_{x\in{\cal
X}}P^{0}(x)\Big{(}\log\Gamma_{\cal E}^{e}[Q](x))-\log\Gamma_{\cal
E}^{e}[P^{0}](x))\Big{)}$ $\displaystyle=$ $\displaystyle
D(P^{0}\|Q)+D(P^{0}\|\Gamma_{\cal E}^{e}[P^{0}])-D(P^{0}\|\Gamma_{\cal
E}^{e}[Q])$ $\displaystyle=$ $\displaystyle D(P^{0}\|Q)-D(\Gamma_{\cal
E}^{e}[P^{0}]\|\Gamma_{\cal E}^{e}[Q]),$ (98)

where the final equation follows from (4). The condition (A1) holds with
$U(P^{0},\infty)={\cal M}_{a}$ and $\gamma=1$. There is a possibility that the
condition (A1) holds with a smaller $\gamma$. Thefore, with $\gamma=1$,
Theorem 2.1 guarantees that Algorithm 1 converges to a local minimum. In
addition, when the relation

$\displaystyle D(P^{0}\|Q)\geq D(\Gamma_{\cal E}^{e}[P^{0}]\|\Gamma_{\cal
E}^{e}[Q])$ (99)

holds for $Q\in U(P^{0},\delta)$, the condition (A2) holds with
$U(P^{0},\delta)$. That is, if the condition (99) holds, Algorithm 1 has the
global convergence to the minimizer. The condition (99) is a similar condition
to the condition given in Bregman-em .

In this case, ${\cal F}_{3}$ is given as

$\displaystyle{\cal F}_{3}[Q](x)=$
$\displaystyle\frac{1}{\kappa_{\rm{em}}[Q]}Q(x)\exp\Big{(}-\frac{1}{\gamma}(\log
Q(x)-\log\Gamma_{\cal E}^{e}[Q](x))\Big{)}$ $\displaystyle=$
$\displaystyle\frac{1}{\kappa_{\rm{em}}[Q]}Q(x)^{\frac{\gamma-1}{\gamma}}\Gamma_{\cal
E}^{e}[Q](x)^{\frac{1}{\gamma}},$ (100)

where the normalizing constant $\kappa_{\rm{em}}[Q_{X}]$ is given as
$\kappa_{\rm{em}}[Q_{X}]=\sum_{x\in{\cal
X}}Q(x)^{\frac{\gamma-1}{\gamma}}\Gamma_{\cal
E}^{e}[Q](x)^{\frac{1}{\gamma}}$. Since ${\cal F}_{3}[Q]\in{\cal M}_{a}$,
$P^{(t+1)}$ is given as $\Gamma_{{\cal M}_{a}}^{m}[{\cal F}_{3}[P^{(t)}]]$.
When $\gamma=1$, it coincides with the conventional em-algorithm Amari ;
Fujimoto ; Allassonniere  because ${\cal F}_{3}[P^{(t)}]=\Gamma_{\cal
E}^{e}[P^{(t)}]$. The above analysis suggests the choice of $\gamma$ as a
smaller value than $1$. That is, there is a possibility that a smaller
$\gamma$ improves the conventional em-algorithm. In addition, we may use
Algorithm 2 instead of Algorithm 1 when the calculation of m-projection is
difficult.

###### Lemma 4

When $\Psi_{\rm{em}}$ is given as (97), the condition (A4) holds.

Therefore, by combining Lemmas 3 and 4, the assumption of Theorem 2.2 holds in
the $\delta$ neighborhood of a local minimizer with sufficiently small
$\delta>0$. That is, the convergence speed can be evaluated by Theorem 2.2.

###### Proof

Pythagorean theorem guarantees

$\displaystyle\sum_{x\in{\cal X}}P(x)\big{(}\log\Gamma_{\cal
E}^{e}[Q](x)-\log\Gamma_{\cal E}^{e}[P](x)\big{)}$ $\displaystyle=$
$\displaystyle D(P\|\Gamma_{\cal E}^{e}[P])-D(P\|\Gamma_{\cal
E}^{e}[Q])=D(\Gamma_{\cal E}^{e}[P]\|\Gamma_{\cal E}^{e}[Q]).$ (101)

We make the parameterization $P_{\eta}\in{\cal M}_{a}$ with mixture parameter
$\eta$. We denote
$\eta(h,i):=(\eta(0)_{1},\ldots,\eta(0)_{i-1},\eta(0)_{i}+h,\eta(0)_{i+1},\ldots,\eta(0)_{k})$.

$\displaystyle\sum_{x\in{\cal
X}}P_{\eta(0)}(x)\Big{(}\frac{\partial}{\partial\eta_{i}}\Psi[P_{\eta}](x)|_{\eta=\eta(0)}\Big{)}$
$\displaystyle=$ $\displaystyle\sum_{x\in{\cal
X}}P_{\eta(0)}(x)\Big{(}\lim_{h\to
0}\frac{\Psi[P_{\eta(h,i)}](x)-\Psi[P_{\eta(0)}](x)}{h}\Big{)}$
$\displaystyle=$ $\displaystyle\sum_{x\in{\cal
X}}P_{\eta(0)}(x)\Big{(}\lim_{h\to 0}\frac{\log P_{\eta(h,i)}(x)-\log
P_{\eta(0)}(x)}{h}$ $\displaystyle-\lim_{h\to 0}\frac{\log\Gamma_{\cal
E}^{e}[P_{\eta(h,i)}](x)-\log\Gamma_{\cal E}^{e}[P_{\eta(0)}](x)}{h}\Big{)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}$ $\displaystyle\sum_{x\in{\cal
X}}P_{\eta(0)}(x)\Big{(}\lim_{h\to 0}\frac{\log P_{\eta(h,i)}(x)-\log
P_{\eta(0)}(x)}{h}\Big{)}$ $\displaystyle-\sum_{x\in{\cal X}}\Gamma_{\cal
E}^{e}[P_{\eta(0)}](x)\Big{(}\lim_{h\to 0}\frac{\log\Gamma_{\cal
E}^{e}[P_{\eta(h,i)}](x)-\log\Gamma_{\cal E}^{e}[P_{\eta(0)}](x)}{h}\Big{)}$
$\displaystyle=$ $\displaystyle\sum_{x\in{\cal
X}}\frac{\partial}{\partial\eta_{i}}P_{\eta}(x)|_{\eta=\eta(0)}-\sum_{x\in{\cal
X}}\frac{\partial}{\partial\eta_{i}}\Gamma_{\cal
E}^{e}[P_{\eta}](x)|_{\eta=\eta(0)}=0,$ (102)

which implies the condition (A4). Here, $(a)$ follows from (101).

##  5 Commitment capacity

Using the same notations as Section 3, we address the bit commitment via a
noisy channel $W_{Y|X}$. This problem setting has several versions. To achieve
the bit commitment, the papers BC1 ; CCDM ; W-Protocols  considered
interactive protocols with multiple rounds, where each round has one use of
the given noisy channel $W_{Y|X}$ and free noiseless communications in both
directions. Then, it derived the commitment capacity, which is explained
later. The proof is basically composed of two parts. One is the achievability
part, which is often called the direct part and shows the existence of the
code to achieve the capacity. The other is the impossibility part, which is
often called the converse part and shows the non-existence of the code to
exceed the capacity. As the achievability part, they showed that the
commitment capacity can be achieved with non-interactive protocol, which has
no free noiseless communication during multiple uses of the given noisy
channel $W_{Y|X}$. However, as explained in HW22 , their proof of the
impossibility part skips so many steps that it cannot be followed. Later, the
paper BC3  showed the impossibility part only for non-interactive protocols by
applying the wiretap channel. Recently, the paper H21  constructed a code to
achieve the commitment capacity by using a specific type of list decoding.
Further, the paper showed that the achievability of the commitment capacity
even in the quantum setting. In addition, the paper HW22  showed the
impossibility part for interactive protocols by completing the proof by HW22 .
The proof in HW22  covers the impossibility part for a certain class even in
the quantum setting.

Given a distribution $P_{X}$, the Shannon entropy is given as

$\displaystyle H(X)_{P_{X}}:=-\sum_{x\in{\cal X}}P_{X}(x)\log P_{X}(x).$ (103)

Given a joint distribution $P_{XY}$, the conditional entropy is defined as

$\displaystyle H(X|Y)_{P_{XY}}:=\int_{{\cal
Y}}H(X)_{W_{X|Y=y}}p_{Y}(y)\mu(dy).$ (104)

The commitment capacity is given as

$\displaystyle C_{c}(W_{Y|X}):=\max_{P_{X}}H(X|Y)_{W_{Y|X}\times P_{X}}.$
(105)

###  5.1 Use of em-algorithm problem

To calculate the commitment capacity, we consider the following mixture and
exponential families;

$\displaystyle{\cal M}_{a}$ $\displaystyle:=\\{W_{Y|X}\times
P_{X}|P_{X}\in{\cal P}({\cal X})\\}$ (106) $\displaystyle{\cal E}$
$\displaystyle:=\\{Q_{Y}\times P_{X,Uni}|Q_{Y}\in{\cal P}({\cal Y})\\},$ (107)

where $P_{X,Uni}$ is the uniform distribution on ${\cal X}$. Since
$\Gamma_{\cal E}^{e}[W_{Y|X}\times P_{X}]=(W_{Y|X}\cdot P_{X})\times
P_{X,Uni}$, the commitment capacity is rewritten as

$\displaystyle\log|{\cal X}|-C_{c}(W_{Y|X})=$
$\displaystyle\min_{P_{X}}H(X)_{P_{X,Uni}}+H(X)_{W_{Y|X}\cdot
P_{X}}-H(XY)_{W_{Y|X}\times P_{X}}$ $\displaystyle=$
$\displaystyle\min_{P_{X}}D(W_{Y|X}\times P_{X}\|(W_{Y|X}\cdot P_{X})\times
P_{X,Uni})$ $\displaystyle=$ $\displaystyle\min_{P_{X}}D(W_{Y|X}\times
P_{X}\|\Gamma_{\cal E}^{e}[W_{Y|X}\times P_{X}]).$ (108)

Hence, the minimization (108) is a special case of the minimization (96).
Since $\Gamma_{\cal E}^{e}[W_{Y|X}\times Q_{X}](x,y)=(W_{Y|X}\cdot
Q_{X})\times P_{X,Uni}$,

$\displaystyle D(\Gamma_{\cal E}^{e}[P^{*}]\|\Gamma_{\cal
E}^{e}[Q_{X}])=D(W_{Y|X}\cdot P_{X}\|W_{Y|X}\cdot Q_{X})\leq D(P^{*}\|Q_{X}),$
(109)

which yields the condition (99). Hence, the global convergence is guaranteed.

By applying (100), ${\cal F}_{3}$ is calculated as

$\displaystyle{\cal F}_{3}[W_{Y|X}\times Q_{X}](x,y)$ $\displaystyle=$
$\displaystyle\frac{1}{\kappa_{W_{Y|X}}^{1}[Q_{X}]}w_{Y|X}(y|x)^{\frac{\gamma-1}{\gamma}}Q_{X}(x)^{\frac{\gamma-1}{\gamma}}(w_{Y|X}\cdot
Q_{X})(y)^{\frac{1}{\gamma}}P_{X,Uni}(x)^{\frac{1}{\gamma}},$ (110)

where $\kappa_{W_{Y|X}}^{1}[Q_{X}]$ is the normalizer. Then, after a
complicated calculation, the marginal distribution of its projection to ${\cal
M}_{a}$ is given as

$\displaystyle\int_{{\cal Y}}\Gamma_{{\cal M}_{a}}^{m}[{\cal
F}_{3}[W_{Y|X}\times Q_{X}]](x,y)\mu(dy)$ $\displaystyle=$
$\displaystyle\frac{1}{\kappa_{W_{Y|X}}^{2}[Q_{X}]}Q_{X}(x)^{1-\frac{1}{\gamma}}\exp(-\frac{1}{\gamma}D(W_{Y|X=x}\|W_{Y|X}\cdot
Q_{X})),$ (111)

where $\kappa_{W_{Y|X}}^{2}[Q_{X}]$ is the normalizer. In the algorithm, we
update $P_{X}^{(t+1)}$ as $P_{X}^{(t+1)}(x):=\int_{{\cal Y}}\Gamma_{{\cal
M}_{a}}^{m}[{\cal F}_{3}[W_{Y|X}\times P_{X}^{(t)}]](x,y)\mu(dy)$.

###  5.2 Direct Application

The update formula (111) requires a complicated calculation, we can derive the
same update rule by a simpler derivation as follows. The commitment capacity
is rewritten as

$\displaystyle-C_{c}(W_{Y|X})=$
$\displaystyle\min_{P_{X}}I(P_{X},W_{Y|X})-H(X)_{P_{X}}$ $\displaystyle=$
$\displaystyle\min_{P_{X}}\sum_{x\in{\cal
X}}P_{X}(x)(D(W_{Y|X=x}\|W_{Y|X}\cdot P_{X})+\log P_{X}(x)).$ (112)

We choose ${\cal M}_{a}$ and $\Psi$ as ${\cal P}({\cal X})$ and

$\displaystyle\Psi_{c,W_{Y|X}}[P_{X}](x):=D(W_{Y|X=x}\|W_{Y|X}\cdot
P_{X})+\log P_{X}(x).$ (113)

Then, we have

$\displaystyle\sum_{x\in{\cal X}}P_{X}(x)(\Psi[P_{X}](x)-\Psi[Q_{X}](x))$
$\displaystyle=$ $\displaystyle D(P_{X}\|Q_{X})-D(W_{Y|X}\cdot
P_{X}\|W_{Y|X}\cdot Q_{X})\geq 0$ (114)

and

$\displaystyle D(P_{X}\|Q_{X})\geq D(P_{X}\|Q_{X})-D(W_{Y|X}\cdot
P_{X}\|W_{Y|X}\cdot Q_{X}).$ (115)

Since the condition (A1) with $\gamma=1$ and the condition (A2) hold,
Algorithm 1 has the convergence with $\gamma=1$. In this case, ${\cal F}_{3}$
is given as

$\displaystyle{\cal F}_{3}[Q_{X}](x)$
$\displaystyle=\frac{1}{\kappa_{W_{Y|X}}^{3}[Q_{X}]}Q_{X}(x)\exp(-\frac{1}{\gamma}(\log
Q_{X}(x)+D(W_{Y|X=x}\|W_{Y|X}\cdot Q_{X})))$
$\displaystyle=\frac{1}{\kappa_{W_{Y|X}}^{3}[Q_{X}]}Q_{X}(x)^{1-\frac{1}{\gamma}}\exp(-\frac{1}{\gamma}D(W_{Y|X=x}\|W_{Y|X}\cdot
Q_{X})),$ (116)

where the normalizing constant $\kappa_{W_{Y|X}}^{3}[Q_{X}]$ is given as
$\kappa_{W_{Y|X}}^{3}[Q_{X}]:=$

$\sum_{x\in{\cal
X}}Q_{X}(x)^{1-\frac{1}{\gamma}}\exp(-\frac{1}{\gamma}D(W_{Y|X=x}\|W_{Y|X}\cdot
Q_{X}))$. Since ${\cal F}_{3}[Q_{X}]\in{\cal M}_{a}$, $P_{X}^{(t+1)}$ is given
as ${\cal F}_{3}[P_{X}^{(t)}]$.

To consider the effect of the acceleration parameter $\gamma$, we made
numerical comparison when the channel with ${\cal X}=\\{1,2,3,4\\}$ and ${\cal
Y}=\\{1,2,3,4\\}$ is given as follows.

$\displaystyle
W_{Y|X}(1,1)=0.6,W_{Y|X}(2,1)=0.2,W_{Y|X}(3,1)=0.1,W_{Y|X}(4,1)=0.1,$
$\displaystyle
W_{Y|X}(1,2)=0.1,W_{Y|X}(2,2)=0.2,W_{Y|X}(3,2)=0.1,W_{Y|X}(4,2)=0.6,$
$\displaystyle
W_{Y|X}(1,3)=0.1,W_{Y|X}(2,3)=0.2,W_{Y|X}(3,3)=0.15,W_{Y|X}(4,3)=0.55,$
$\displaystyle
W_{Y|X}(1,4)=0.05,W_{Y|X}(2,4)=0.85,W_{Y|X}(3,4)=0.05,W_{Y|X}(4,4)=0.05.$
(117)

We choose $\gamma$ to be $1$, $0.95$, and $0.9$. Fig. 1 shows the numerical
result for the iteration of our algorithm when the channel input is limited
into $\\{1,2,3\\}$. In this case, a smaller $\gamma$ does not improve the
convergence. Fig. 2 shows the same numerical result when all elements of
$\\{1,2,3,4\\}$ are allowed as the channel input. In this case, a smaller
$\gamma$ improves the convergence.

Figure 1:  Calculation of commitment capacity for the channel given in (117)
with ${\cal X}=\\{1,2,3\\}$. The right plot shows an enlarged plot of the left
plot. The horizontal axis shows the number of iteration. The vertical axis
shows the conditional entropy. Red points show the case with $\gamma=1$. Green
points show the case with $\gamma=0.95$. Blue points show the case with
$\gamma=0.9$. For $t=3,\ldots,10$, these cases have almost the same value.
Hence, these plots cannot be distinguished for $t=5,6,7,8,9,10$. In this case,
a smaller $\gamma$ does not improve the convergence.

Figure 2:  Calculation of commitment capacity for the channel given in (117)
with ${\cal X}=\\{1,2,3,4\\}$. The roles of color is the same as Fig. 1. In
this case, a smaller $\gamma$ improves the convergence.

##  6 Reverse em problem

###  6.1 General problem description

In this section, given a pair of an exponential family ${\cal E}$ and a
mixture family ${\cal M}_{a}$ on ${\cal X}$, we consider the following
maximization;

$\displaystyle\max_{P\in{\cal M}_{a}}\min_{Q\in{\cal
E}}D(P\|Q)=\min_{P\in{\cal M}_{a}}D(P\|\Gamma_{\cal E}^{e}[P])$
$\displaystyle=$ $\displaystyle\max_{P\in{\cal M}_{a}}\sum_{x\in{\cal
X}}P(x)(\log P(x)-\log\Gamma_{\cal E}^{e}[P](x))$ (118)

while Section 4 considers the minimization of the same value. When ${\cal
M}_{a}$ is given as (106) and ${\cal E}$ is given as ${\cal P}({\cal
X})\times{\cal P}({\cal Y})$, this problem coincides with the channel capacity
(57). This problem was firstly studied for the channel capacity in Shoji , and
was discussed with a general form in reverse . To discuss this problem, we
choose the function $\Psi$ as $\Psi_{\rm{rem}}:=-\Psi_{\rm{em}}$, and apply
the discussion in Section 2. Due to (98), (23) in the condition (A1) is
written as

$\displaystyle(\gamma+1)D(P^{0}\|Q)\geq D(\Gamma_{\cal
E}^{e}[P^{0}]\|\Gamma_{\cal E}^{e}[Q]),$ (119)

and (24) in the condition (A2) is written as

$\displaystyle D(\Gamma_{\cal E}^{e}[P^{0}]\|\Gamma_{\cal E}^{e}[Q])\geq
D(P^{0}\|Q).$ (120)

Further, due to Lemma 4, the condition (A4) holds.

###  6.2 Application to wiretap channel

Now, we apply this problem setting to wiretap channel with the degraded case
discussed in Subsection 3.4.2. We choose ${\cal M}_{a}$ as $\\{W_{YZ|X}\times
P_{X}|P_{X}\in{\cal P}({\cal X})\\}$ and ${\cal E}$ as the set of
distributions with the Markov chain condition $X-Z-Y$ Toyota . Then, the
conditional mutual information $I(X;Y|Z)[P_{X},W_{YZ|X}]$ is given as
$D(W_{YZ|X}\times P_{X}\|\Gamma_{{\cal E}}^{e}(W_{YZ|X}\times P_{X}))$. In
this application, we have

$\displaystyle D_{\Psi_{\rm{rem}}}(W_{YZ|X}\times P_{X}\|W_{YZ|X}\times
Q_{X})$ $\displaystyle=D_{\Psi_{W_{YZ|X}}}D(P_{X}\|Q_{X})$ (121)
$\displaystyle D(W_{YZ|X}\times P_{X}\|W_{YZ|X}\times Q_{X})$
$\displaystyle=D(P_{X}\|Q_{X}).$ (122)

To check the conditions (A1) and (A2) for $\Psi_{W_{YZ|X}}$, it is sufficient
to check them for $\Psi_{\rm{rem}}$ in this application. Since we have

$\displaystyle D(\Gamma_{{\cal E}}^{e}(W_{YZ|X}\times P_{X})\|\Gamma_{{\cal
E}}^{e}(W_{YZ|X}\times Q_{X}))$ $\displaystyle=$ $\displaystyle
D(W_{Z|X}\times P_{X}\|Q_{XZ})+D(W_{YZ|X}\cdot P_{X}\|W_{YZ|X}\cdot Q_{X})$
$\displaystyle-D(W_{Z|X}\cdot P_{X}\|W_{Z|X}\cdot Q_{X})$ $\displaystyle=$
$\displaystyle D(P_{X}\|Q_{X})+D(W_{YZ|X}\cdot P_{X}\|W_{YZ|X}\cdot
Q_{X})-D(W_{Z|X}\cdot P_{X}\|W_{Z|X}\cdot Q_{X})$ $\displaystyle\leq$
$\displaystyle 2D(P_{X}\|Q_{X}),$ (123)

LHS of (23) in the condition (A1) is written as

$\displaystyle\gamma D(P_{X}^{0}\|Q_{X})-D(W_{YZ|X}\cdot P_{X}\|W_{YZ|X}\cdot
Q_{X})+D(W_{Z|X}\cdot P_{X}\|W_{Z|X}\cdot Q_{X})$ $\displaystyle\geq$
$\displaystyle\gamma D(P^{0}\|Q)-D(P_{X}^{0}\|Q_{X}).$ (124)

It is not negative when $\gamma\geq 1$. Also, RHS of (24) in the condition
(A2) is written as

$\displaystyle D(W_{YZ|X}\cdot P_{X}\|W_{YZ|X}\cdot Q_{X})-D(W_{Z|X}\cdot
P_{X}\|W_{Z|X}\cdot Q_{X})\geq 0.$ (125)

Hence, the conditions (A1) and (A2) hold with $\gamma\geq 1$.

##  7 Information bottleneck

As a method for information-theoretical machine learning, we often consider
information bottleneck Tishby . Consider two correlated systems ${\cal X}$ and
${\cal Y}$ and a joint distribution $P_{XY}$ over ${\cal X}\times{\cal Y}$.
The task is to extract an essential information from the space ${\cal X}$ to
${\cal T}$ with respect to ${\cal Y}$. For this information extraction, given
parameters $\alpha\in[0,1]$ and $\beta\geq\alpha$, we choose a conditional
distribution $P_{T|X}^{*}$ as

$\displaystyle P_{T|X}^{*}:=\mathop{\rm argmin}\limits_{P_{T|X}}\alpha
I(T;X)+(1-\alpha)H(T)-\beta I(T;Y).$ (126)

This method is called information bottleneck. To apply our method to this
problem, we choose ${\cal M}_{a}$ ${\cal P}({\cal X})$, and define

$\displaystyle{\Psi}_{\alpha,\beta}[P_{TX}](t,x):=$ $\displaystyle\alpha\log
P_{TX}(t,x)-\alpha\log P_{X}(x)+(\beta-1)\log P_{T}(t)$
$\displaystyle+\beta\sum_{y\in{\cal Y}}P_{Y|X}(y|x)(\log P_{Y}(y)-\log
P_{TY}(t,y)).$ (127)

Then, when the joint distribution $P_{TX}$ is chosen to be $P_{T|X}\times
P_{X}$, the objective function is written as

$\displaystyle{\cal G}_{\alpha,\beta}(P_{TX}):=\sum_{t\in{\cal T},x\in{\cal
X}}P_{TX}(t,x){\Psi}_{\alpha,\beta}[P_{TX}](t,x).$ (128)

That is, our problem is reduced to the minimization

$\displaystyle\min_{P_{TX}\in{\cal M}(P_{X})}{\cal G}_{\alpha,\beta}(P_{TX}),$
(129)

where ${\cal M}(P_{X})$ is the set of joint distributions on ${\cal
X}\times{\cal Y}$ whose marginal distribution on ${\cal X}$ is $P_{X}$. The
$m$-projection $\Gamma^{(m)}_{{\cal M}(P_{X})}$ to ${\cal M}(P_{X})$ is
written as

$\displaystyle\Gamma^{(m)}_{{\cal M}(P_{X})}[Q_{TX}]=Q_{T|X}\times P_{X}$
(130)

because the relation
$D(P_{TX}\|Q_{TX})=D(P_{X}\|Q_{X})+D(P_{TX}\|Q_{T|X}\times P_{X})$ holds for a
distribution $P_{TX}\in{\cal M}(P_{X})$.

When Algorithm 1 is applied to this problem, due to (130), the update rule for
the conditional distribution is given as

$\displaystyle P_{T|X}^{(t)}\mapsto
P_{T|X}^{(t+1)}(t|x):=\kappa_{x}P_{T|X}^{(t)}(t|x)\exp(-\frac{1}{\gamma}\Psi_{\alpha,\beta}[P_{T|X}^{(t)}\times
P_{X}](t,x))$ (131)

with a normalized constant $\kappa_{x}$. This update rule is the same as the
update rule proposed in Section 3 of HY  when the states $\\{\rho_{Y|x}\\}$
are given as diagonal density matrices, i.e., a conditional distribution
$P_{Y|X}$. Also, as shown in (HY, , (22)), we have the relation

$\displaystyle D_{\Psi_{\alpha,\beta}}(P_{TX}\|Q_{TX})\leq\alpha
D(P_{TX}\|Q_{TX})$ (132)

for $P_{TX},Q_{TX}\in{\cal M}(P_{X})$ as follows. First, we have

$\displaystyle D(P_{T|X}\cdot P_{XY}\|Q_{T|X}\cdot P_{XY})\geq
D(P_{T}\|Q_{T}),$ (133)

where $P_{T|X}\cdot P_{XY}(t,y):=\sum_{x\in{\cal X}}P_{T|X}(t|x)P_{XY}(x,y)$.
Then, we have

$\displaystyle D_{\Psi_{\alpha,\beta}}(P_{TX}\|Q_{TX})$ $\displaystyle=$
$\displaystyle(\beta-1)D(P_{T}\|Q_{T})+\alpha\sum_{x\in{\cal
X}}P_{X}(x)D(P_{T|X=x}\|Q_{T|X=x})$ $\displaystyle-\beta D(P_{T|X}\cdot
P_{XY}\|Q_{T|X}\cdot P_{XY})$ $\displaystyle\leq$
$\displaystyle-D(P_{T}\|Q_{T})+\alpha\sum_{x\in{\cal
X}}P_{X}(x)D(P_{T|X=x}\|Q_{T|X=x})$ $\displaystyle\leq$
$\displaystyle\alpha\sum_{x\in{\cal X}}P_{X}(x)D(P_{T|X=x}\|Q_{T|X=x})=\alpha
D(P_{TX}\|Q_{TX}).$ (134)

That is, the condition (A1) holds with $\gamma=\alpha$. Thefore, with
$\gamma=\alpha$, Theorem 2.1 guarantees that Algorithm 1 converges to a local
minimum, which was shown as (HY, , Theorem 3). This fact shows the importance
of the choice of $\gamma$ dependently of the problem setting. That is, it
shows the necessity of our problem setting with a general positive real number
$\gamma>0$.

The paper HY  also discussed the case when ${\cal Y}$ and ${\cal T}$ are
quantum systems. It numerically compared these algorithms depending on
$\gamma$ (HY, , Fig. 2). This numerical calculation indicates the following
behavior. When $\gamma$ is larger than a certain threshold, a smaller $\gamma$
realizes faster convergence. But, when $\gamma$ is smaller than a certain
threshold, the algorithm does not converge.

##  8 Conclusion

We have proposed iterative algorithms with an acceleration parameter for a
general minimization problem over a mixture family. For these algorithms, we
have shown its convergence theorems in various forms, one of which covers the
case with approximated iterations. Then, we have applied our algorithms to
various problem settings including em algorithm and several information
theoretical problem settings.

There are two existing studies to numerically evaluate the effect of the
acceleration parameter $\gamma$ RISB ; HY . They reported improvement of the
convergence by modifying the acceleration parameter $\gamma$. For example, in
the numerical calculation for information bottleneck in (HY, , Fig. 2), the
case with $\gamma=0.55$ improves the convergence. Our numerical calculation
for commitment capacity, has two cases. In one case, the choices with
$\gamma=0.95,0.9$ do not improve the convergence. In another case, the choices
with $\gamma=0.95,0.9$ improves the convergence. These facts show that the
effect of the acceleration parameter $\gamma$ depends on the parameters of the
problem setting. The commitment capacity is considered as a special case of
the divergence between a mixture family and an exponential family, Therefore,
it is useful to characterize the case when the acceleration parameter $\gamma$
improves the conventional em algorithm for the minimization of the divergence
between a mixture family and an exponential family in the problem setting of
em algorithm.

The second direction is the evaluation of the convergence speed of Algorithm 3
because we could not derive its evaluation. The third direction is to find
various applications of our methods. Although this paper studied several
examples, it is needed to more useful examples for our algorithm. The third
direction is the extensions of our results. A typical extension is the
extension to the quantum setting Holevo ; SW ; hayashi . As a further
extension, it is an interesting topic to extend our result to the setting with
Bregman divergence. Recently, Bregman proximal gradient algorithm has been
studied for the minimization of a convex function CT93 ; T97 ; ZYS . Since
this algorithm uses Bregman divergence, it might have an interesting relation
with the above extended algorithm. Therefore, it is interesting study to
investigate this relation.

## Acknowledgments

The author was supported in part by the National Natural Science Foundation of
China (Grant No. 62171212) and Guangdong Provincial Key Laboratory (Grant No.
2019B121203002). The author is very grateful to Mr. Shoji Toyota for helpful
discussions. In addition, he pointed out that the secrecy capacity can be
written as the reverse em algorithm in a similar way as the channel capacity
Toyota  under the degraded condition.

## Data availability

Data sharing is not applicable to this article as no datasets were generated
or analyzed during the current study.

## Conflict of interest

There are no competing interests.

##  Appendix A Useful lemma

To show various theorems, we prepare the following lemma.

###### Lemma 5

For any distribution $Q\in{\cal M}_{a}$, we have

$\displaystyle D(P^{0}\|Q)-D(P^{0}\|Q_{\theta})$ $\displaystyle=$
$\displaystyle\frac{1}{\gamma}J_{\gamma}(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[Q]],Q)-\frac{1}{\gamma}{\cal G}(P^{0})+\frac{1}{\gamma}\sum_{x\in{\cal
X}}P^{0}(x)\Big{(}\Psi[P^{0}](x)-\Psi[Q](x)\Big{)}$
$\displaystyle-D(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal F}_{3}[Q]]\|Q_{\theta})$
(135) $\displaystyle=$ $\displaystyle\frac{1}{\gamma}{\cal
G}(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal F}_{3}[Q]])-\frac{1}{\gamma}{\cal
G}(P^{0})$ $\displaystyle+D(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[Q]]\|Q)-\frac{1}{\gamma}\sum_{x\in{\cal X}}\Gamma^{(m)}_{{\cal
M}_{a}}[{\cal F}_{3}[Q]](x)(\Psi[\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[Q]]](x)-\Psi[Q](x))$ $\displaystyle+\frac{1}{\gamma}\sum_{x\in{\cal
X}}P^{0}(x)\Big{(}\Psi[P^{0}](x)-\Psi[Q](x)\Big{)}-D(\Gamma^{(m)}_{{\cal
M}_{a}}[{\cal F}_{3}[Q]]\|Q_{\theta}).$ (136)

In addition, when $\Psi$ is defined for any distribution in ${\cal P}({\cal
X})$, the above relations holds for any distribution $Q\in{\cal P}({\cal X})$.

###### Proof

We have

$\displaystyle{\cal G}(P^{0})=$ $\displaystyle\sum_{x\in{\cal
X}}P^{0}(x)\Psi[P^{0}](x)=J_{\gamma}(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[P^{0}]],P^{0})$ $\displaystyle=$ $\displaystyle\gamma
D(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal F}_{3}[P^{0}]]\|{\cal
F}_{3}[P^{0}])-\log\kappa[P^{0}]).$ (137)

Using (137), we have

$\displaystyle D(P^{0}\|Q)-D(P^{0}\|Q_{\theta})=\sum_{x\in{\cal
X}}P^{0}(x)(\log Q_{\theta}(x)-\log Q(x))$ $\displaystyle=$
$\displaystyle\sum_{x\in{\cal X}}P^{0}(x)\Big{(}\log Q_{\theta}(x)-\log{\cal
F}_{3}[Q](x)+\log{\cal F}_{3}[Q](x)-\log Q(x)\Big{)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}$ $\displaystyle D(P^{0}\|{\cal
F}_{3}[Q])-D(P^{0}\|Q_{\theta})+\sum_{x\in{\cal
X}}P^{0}(x)\Big{(}-\frac{1}{\gamma}\Psi[Q](x)-\log\kappa[Q]\Big{)}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}$ $\displaystyle
D(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal F}_{3}[Q]]\|{\cal
F}_{3}[Q])-D(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal F}_{3}[Q]]\|Q_{\theta})$
$\displaystyle-\log\kappa[Q]-\frac{1}{\gamma}\sum_{x\in{\cal
X}}P^{0}(x)\Psi[Q](x)$ $\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}$
$\displaystyle\frac{1}{\gamma}J_{\gamma}(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[Q]],Q)-\frac{1}{\gamma}{\cal G}(P^{0})+\frac{1}{\gamma}\sum_{x\in{\cal
X}}P^{0}(x)\Big{(}\Psi[P^{0}](x)-\Psi[Q](x)\Big{)}$
$\displaystyle-D(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal F}_{3}[Q]]\|Q_{\theta})$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}$
$\displaystyle\frac{1}{\gamma}{\cal G}(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[Q]])-\frac{1}{\gamma}{\cal G}(P^{0})$
$\displaystyle+D(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[Q]]\|Q)-\frac{1}{\gamma}\sum_{x\in{\cal X}}\Gamma^{(m)}_{{\cal
M}_{a}}[{\cal F}_{3}[Q]](x)(\Psi[\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[Q]]](x)-\Psi[Q](x))$ $\displaystyle+\frac{1}{\gamma}\sum_{x\in{\cal
X}}P^{0}(x)\Big{(}\Psi[P^{0}](x)-\Psi[Q](x)\Big{)}-D(\Gamma^{(m)}_{{\cal
M}_{a}}[{\cal F}_{3}[Q]]\|Q_{\theta}),$ (138)

where each step is shown as follows. $(a)$ follows from the definition of
${\cal F}_{3}(Q)$. $(c)$ follows from (9) and (137). $(d)$ follows from (16).
$(b)$ follows from the relations

$\displaystyle D(P^{0}\|{\cal F}_{3}[Q])$
$\displaystyle=D(P^{0}\|\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[Q]])+D(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal F}_{3}[Q]]\|{\cal F}_{3}[Q])$
(139) $\displaystyle D(P^{0}\|Q_{\theta})$
$\displaystyle=D(P^{0}\|\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[Q]])+D(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal F}_{3}[Q]]\|Q_{\theta}),$
(140)

which are shown by Phythagorean equation.

##  Appendix B Proof of Theorem 2.2 and Corollary 1

Step 1: The aim of this step is to show the following inequalities by assuming
that item (i) does not hold and the conditions (A1) and (A2) hold.

$\displaystyle D(P^{0}\|P^{(t+1)})\leq\delta$ (141) $\displaystyle
D(P^{0}\|P^{(t)})-D(P^{0}\|P^{(t+1)})\geq\frac{1}{\gamma}{\cal
G}(P^{(t+1)})-\frac{1}{\gamma}{\cal G}(P^{0})$ (142)

for $t=1,\ldots,t_{0}-1$. We show these relations by induction.

For any $t$, by using the relation $\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[{P}^{(t)}]]=P^{(t+1)}$, the application of (136) of Lemma 5 to the case
with $Q=P^{(t)}$ and $Q_{\theta}=P^{(t+1)}$ yields

$\displaystyle D(P^{0}\|P^{(t)})-D(P^{0}\|P^{(t+1)})$ $\displaystyle=$
$\displaystyle\frac{1}{\gamma}{\cal G}(P^{(t+1)})-\frac{1}{\gamma}{\cal
G}(P^{0})+D(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal F}_{3}[P^{(t)}]]\|P^{(t)})$
$\displaystyle-\frac{1}{\gamma}\sum_{x\in{\cal X}}\Gamma^{(m)}_{{\cal
M}_{a}}[{\cal F}_{3}[P^{(t)}]](x)(\Psi[\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[P^{(t)}]](x)-\Psi[P^{(t)}](x))$
$\displaystyle+\frac{1}{\gamma}\sum_{x\in{\cal
X}}P^{0}(x)\Big{(}\Psi[P^{0}](x)-\Psi[P^{(t)}](x)\Big{)}.$ (143)

First, we show the relations (141) and (142) with $t=1$. Since
$D(P^{0}\|P^{(1)})\leq\delta$, the conditions (A1) and (A2) guarantees the
following inequality with $t=1$;

$\displaystyle\hbox{\rm(RHS of \eqref{XME2})}\geq\frac{1}{\gamma}{\cal
G}(P^{(t+1)})-\frac{1}{\gamma}{\cal G}(P^{0}).$ (144)

The combination of (143) and (144) implies (142). Since item (i) does not
hold, we have

$\displaystyle\frac{1}{\gamma}{\cal G}(P^{(t+1)})-\frac{1}{\gamma}{\cal
G}(P^{0})\geq 0.$ (145)

The combination of (143), (144), and (145) implies (141).

Next, we show the relations (141) and (142) with $t=t^{\prime}$ by assuming
the relations (141) and (142) with $t=t^{\prime}-1$. Since the assumption
guarantees $D(P^{0}\|P^{(t^{\prime})})\leq\delta$, the conditions (A1) and
(A2) guarantees (144) with $t=t^{\prime}$. We obtain (141) and (142) in the
same way as $t=1$.

Step 2: The aim of this step is to show (27) by assuming that item (i) does
not hold and the conditions (A1) and (A2) hold. Due to (141), the condition
(A1) and Lemmas 1 and 2 guarantee that

$\displaystyle{\cal G}(P^{(t+1)})\leq{\cal G}(P^{(t)}).$ (146)

We have

$\displaystyle\frac{t_{0}}{\gamma}\Big{(}{\cal G}(P^{(t_{0}+1)})-{\cal
G}(P^{0})\Big{)}\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{1}{\gamma}\sum_{t=1}^{t_{0}}{\cal
G}(P^{(t+1)})-{\cal G}(P^{0})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}$
$\displaystyle\sum_{t=1}^{t_{0}}D(P^{0}\|P^{(t)})-D(P^{0}\|P^{(t+1)})=D(P^{0}\|P^{(1)})-D(P^{0}\|P^{(t_{0}+1)})\leq
D(P^{0}\|P^{(1)}),$ (147)

where $(a)$ and $(b)$ follow from (146) and (142), respectively.

Step 3: The aim of this step is to show item (ii) by assuming the conditions
(A0) as well as (A1) and (A2). In the discussion of Step 1, since
$D(P^{0}\|P^{(t)})\leq\delta$, the condition (A0) guarantees (145). We can
show item (ii) with assuming that item (i) does not hold. Hence, we obtain
Theorem 2.2.

Step 4: To show Corollary 1, we apply (143) to the case when $P^{0}=P^{*}$ and
$P^{(t)}=P^{*}_{i}$. Then, we have

$\displaystyle 0={\cal G}(P^{*}_{i})-{\cal G}(P^{*})+\sum_{x\in{\cal
X}}P^{*}(x)(\Psi[P^{*}](x)-\Psi[P^{*}_{i}](x)),$ (148)

which implies (30).

##  Appendix C Proof of Theorem 2.3

We have already shown that $\\{P^{(t)}\\}_{t=1}^{t_{0}+1}\subset
U(P^{0},\delta)$ when item (i) does not hold. Hence, in the following, we show
only (29) by using (A1), (A3), and $\\{P^{(t)}\\}_{t=1}^{t_{0}+1}\subset
U(P^{0},\delta)$ when item (i) does not hold.

We have

$\displaystyle J_{\gamma}(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[P^{(t)}]],P^{(t)})-{\cal G}(P^{0})$ (149)
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}$ $\displaystyle{\cal
G}(P^{(t+1)})-{\cal G}(P^{0})+\gamma D(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[P^{(t)}]]\|P^{(t)})$ $\displaystyle-\sum_{x\in{\cal
X}}\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[P^{(t)}]](x)(\Psi[\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[P^{(t)}]](x)-\Psi[P^{(t)}](x))$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\geq}}$ $\displaystyle{\cal
G}(P^{(t+1)})-{\cal G}(P^{0})\stackrel{{\scriptstyle(c)}}{{\geq}}0,$ (150)

where $(a)$ follows from Lemma 2, $(b)$ follows from the condition (A1) and
$P^{(t)}\in U(P^{0},\delta)$, and $(c)$ holds because item (i) does not hold.

Since $\Gamma^{(m)}_{{\cal M}_{a}}[{\cal F}_{3}[{P}^{(t)}]]=P^{(t+1)}$, the
application of (135) of Lemma 5 to the case with $Q=P^{(t)}$ and
$Q_{\theta}=P^{(t+1)}$ yields

$\displaystyle D(P^{0}\|P^{(t)})-D(P^{0}\|P^{(t+1)})$ $\displaystyle=$
$\displaystyle\frac{1}{\gamma}J_{\gamma}(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[P^{(t)}]],P^{(t)})-\frac{1}{\gamma}{\cal
G}(P^{0})+\frac{1}{\gamma}\sum_{x\in{\cal
X}}P^{0}(x)\Big{(}\Psi[P^{0}](x)-\Psi[P^{(t)}](x)\Big{)}$ (151)
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}$
$\displaystyle\frac{1}{\gamma}\sum_{x\in{\cal
X}}P^{0}(x)\Big{(}\Psi[P^{0}](x)-\Psi[P^{(t)}](x)\Big{)}\stackrel{{\scriptstyle(b)}}{{\geq}}\frac{\beta}{\gamma}D(P^{0}\|P^{(t)}),$
(152)

where $(a)$ follows from (150), and $(b)$ follows from (25) in the condition
(A3) and $P^{(t)}\in U(P^{0},\delta)$. Hence, we have

$\displaystyle
D(P^{0}\|P^{(t+1)})\leq(1-\frac{\beta}{\gamma})D(P^{0}\|P^{(t)}).$ (153)

Using the above relations, we have

$\displaystyle{\cal G}(P^{(t+1)})-{\cal
G}(P^{0})\stackrel{{\scriptstyle(a)}}{{\leq}}J_{\gamma}(\Gamma^{(m)}_{{\cal
M}_{a}}[{\cal F}_{3}[P^{(t)}]],P^{(t)})-{\cal G}(P^{0})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}$ $\displaystyle
D(P^{0}\|P^{(t)})-D(P^{0}\|P^{(t+1)})-\frac{1}{\gamma}\sum_{x\in{\cal
X}}P^{0}(x)\Big{(}\Psi[P^{0}](x)-\Psi[P^{(t)}](x)\Big{)}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}$ $\displaystyle
D(P^{0}\|P^{(t)})-D(P^{0}\|P^{(t+1)})-\frac{\beta}{\gamma}D(P^{0}\|P^{(t)})$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}$
$\displaystyle(1-\frac{\beta}{\gamma})D(P^{0}\|P^{(t)})\stackrel{{\scriptstyle(e)}}{{\leq}}(1-\frac{\beta}{\gamma})^{t}D(P^{0}\|P^{(1)}),$
(154)

where each step is derived as follows. Step $(a)$ follows from (150). Step
$(b)$ follows from (151). Step $(c)$ follows from (25) in the condition (A3)
and $P^{(t)}\in U(P^{0},\delta)$. Step $(d)$ follows from (152). Step $(e)$
follows from (153). Hence, we obtain (29). Therefore, we have shown item (ii)
under the conditions (A1) and (A3) when item (i) does not hold.

When (A0) holds in addition to (A1) and (A3), as shown in Step 1 of the proof
of Theorem 2.2, the relation $\\{P^{(t)}\\}_{t=1}^{t_{0}+1}\subset
U(P^{0},\delta)$ holds. Hence, item (ii) holds.

##  Appendix D Proof of Theorem 2.4

In this proof, we choose $\bar{P}^{(1)}$ to be ${P}^{(1)}$.

Step 1: The aim of this step is to show the inequality (44). We denote the
maximizer in (40) by $\theta^{\prime}$. The condition (40) implies that

$\displaystyle\phi[\bar{P}^{(t)}](\theta)-\sum_{j=1}^{k}\theta^{j}a_{j}\leq\phi[\bar{P}^{(t)}](\theta^{\prime})-\sum_{j=1}^{k}{\theta^{\prime}}^{j}a_{j}+\epsilon_{1}.$
(155)

Since the divergence in the exponential family $\\{Q_{\theta}\\}$ can be
considered as the Bregmann divergence of the potential function
$\phi[\bar{P}^{(t)}](\theta)$, we have

$\displaystyle D(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[\bar{P}^{(t)}]]\|\bar{P}^{(t+1)})=$
$\displaystyle\phi[\bar{P}^{(t)}](\theta)-\sum_{j=1}^{k}\theta^{j}a_{j}-\Big{(}\phi[\bar{P}^{(t)}](\theta^{\prime})-\sum_{j=1}^{k}{\theta^{\prime}}^{j}a_{j}\Big{)}\leq\epsilon_{1}.$
(156)

Step 2: The aim of this step is to show Eq. (45) when the following inequality

$\displaystyle{\cal G}({P}^{(t_{2})})-\gamma
D(P^{(t_{2})}\|\bar{P}^{(t_{2})}){\leq}\frac{\gamma}{t_{1}-1}D^{F}(\theta_{*}\|\theta_{(1)})+\epsilon_{1}+{\cal
G}(P^{0})$ (157)

holds. Eq. (45) is shown as follows;

$\displaystyle{\cal G}({P}_{f}^{(t_{1})})-{\cal
G}(P^{0})\stackrel{{\scriptstyle(a)}}{{=}}{\cal G}({P}^{(t_{2})})-{\cal
G}(P^{0})\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{\gamma}{t_{1}-1}D(P^{0}\|\bar{P}^{(1)})+\gamma
D(P^{(t_{2})}\|\bar{P}^{(t_{2})})+\epsilon_{1}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}$
$\displaystyle\frac{\gamma}{t_{1}-1}D(P^{0}\|\bar{P}^{(1)})+\gamma\epsilon_{2}+\epsilon_{1},$
(158)

where Steps $(a)$, $(b)$, and $(c)$ follow from the definition of
${P}_{f}^{(t_{1})}$, (157), and (41), respectively. Therefore, the remaining
task is the proof of (157).

Step 3: We choose $t_{4}\in[1,t_{1}-1]$ as the minimum integer
$t\in[1,t_{1}-1]$ to satisfy the following inequality

$\displaystyle\frac{1}{\gamma}J_{\gamma}(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[\bar{P}^{(t)}]],\bar{P}^{(t)})\leq\frac{1}{\gamma}{\cal
G}(P^{0})+\epsilon_{1}.$ (159)

If no integer $t\in[1,t_{1}-1]$ satisfies (159), we set $t_{4}$ to be $t_{1}$.
The aim of this step is to show the following two facts for
$t=1,\ldots,t_{4}-1$. (i) $D(P^{0}\|\bar{P}^{(t+1)})\leq\delta$. (ii) The
inequality

$\displaystyle
D(P^{0}\|\bar{P}^{(t)})-D(P^{0}\|\bar{P}^{(t+1)}){\geq}\frac{1}{\gamma}J_{\gamma}(\Gamma^{(m)}_{{\cal
M}_{a}}[{\cal F}_{3}[\bar{P}^{(t)}]],\bar{P}^{(t)})-\frac{1}{\gamma}{\cal
G}(P^{0})-\epsilon_{1}$ (160)

holds. The above two items are shown by induction for $t$ as follows. It is
sufficient to show the case when $t_{4}\geq 2$.

We show items (i) and (ii) for $t=1$ as follows. The application of Lemma 5 to
the case with $Q=\bar{P}^{(1)}$ and $Q_{\theta}=\bar{P}^{(2)}$ yields

$\displaystyle D(P^{0}\|\bar{P}^{(1)})-D(P^{0}\|\bar{P}^{(2)})$
$\displaystyle=$ $\displaystyle\frac{1}{\gamma}J_{\gamma}(\Gamma^{(m)}_{{\cal
M}_{a}}[{\cal F}_{3}[\bar{P}^{(1)}]],\bar{P}^{(1)})-\frac{1}{\gamma}{\cal
G}(P^{0})$ $\displaystyle+\frac{1}{\gamma}\sum_{x\in{\cal
X}}P^{0}(x)\Big{(}\Psi[P^{0}](x)-\Psi[\bar{P}^{(1)}](x)\Big{)}-D(\Gamma^{(m)}_{{\cal
M}_{a}}[{\cal F}_{3}[\bar{P}^{(1)}]]\|\bar{P}^{(2)})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}$
$\displaystyle\frac{1}{\gamma}J_{\gamma}(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[\bar{P}^{(1)}]],\bar{P}^{(1)})-\frac{1}{\gamma}{\cal
G}(P^{0})-\epsilon_{1}\stackrel{{\scriptstyle(b)}}{{\geq}}0,$ (161)

where $(a)$ follows from (A2+) and (44) because the relation
$D(P^{0}\|\bar{P}^{(1)})\leq\delta$ follows from the assumption of this
theorem. $(b)$ follows from the fact that $t=1$ does not satisfy the condition
(159). Hence, $D(P^{0}\|\bar{P}^{(2)})\leq D(P^{0}\|\bar{P}^{(1)})\leq\delta$.

Assume that items (i) and (ii) hold with $t=t^{\prime}-1$. Then, the
application of Lemma 5 to the case with $Q=\bar{P}^{(t)}$ and
$Q_{\theta}=\bar{P}^{(t+1)}$ yields

$\displaystyle
D(P^{0}\|\bar{P}^{(t^{\prime})})-D(P^{0}\|\bar{P}^{(t^{\prime}+1)})$
$\displaystyle=$ $\displaystyle\frac{1}{\gamma}J_{\gamma}(\Gamma^{(m)}_{{\cal
M}_{a}}[{\cal
F}_{3}[\bar{P}^{(t^{\prime})}]],\bar{P}^{(t^{\prime})})-\frac{1}{\gamma}{\cal
G}(P^{0})$ $\displaystyle+\frac{1}{\gamma}\sum_{x\in{\cal
X}}P^{0}(x)\Big{(}\Psi[P^{0}](x)-\Psi[\bar{P}^{(t)}](x)\Big{)}-D(\Gamma^{(m)}_{{\cal
M}_{a}}[{\cal F}_{3}[\bar{P}^{(t^{\prime})}]]\|\bar{P}^{(t^{\prime}+1)})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}$
$\displaystyle\frac{1}{\gamma}J_{\gamma}(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[\bar{P}^{(t^{\prime})}]],\bar{P}^{(t^{\prime})})-\frac{1}{\gamma}{\cal
G}(P^{0})-\epsilon_{1}\stackrel{{\scriptstyle(b)}}{{\geq}}0,$ (162)

where $(a)$ follows from (A2+) and (44) because the relation
$D(P^{0}\|\bar{P}^{(t^{\prime})})\leq\delta$ follows from the assumption of
induction. $(b)$ follows from the fact that $t=t^{\prime}$ does not satisfy
the condition (159). Hence, $D(P^{0}\|\bar{P}^{(t^{\prime}+1)})\leq
D(P^{0}\|\bar{P}^{(t^{\prime})})\leq\delta$.

Step 4: The aim of this step is to show the inequality (157) when $t_{4}\leq
t_{1}-1$, i.e., there exists an integer $t\in[1,t_{1}-1]$ to satisfy (159).

Pythagorean theorem guarantees

$\displaystyle D({P}^{(t_{4}+1)}\|\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[\bar{P}^{(t_{4})}]])$ $\displaystyle\leq$ $\displaystyle
D({P}^{(t_{4}+1)}\|\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[\bar{P}^{(t_{4})}]])+D(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[\bar{P}^{(t_{4})}]]\|\bar{P}^{(t_{4}+1)})$ $\displaystyle=$
$\displaystyle D(P^{(t_{4}+1)}\|\bar{P}^{(t_{4}+1)})\leq\epsilon_{2}.$ (163)

Then, we have

$\displaystyle{\cal G}({P}^{(t_{2})})-\gamma
D(P^{(t_{2})}\|\bar{P}^{(t_{2})})\stackrel{{\scriptstyle(a)}}{{\leq}}{\cal
G}({P}^{(t_{4}+1)})-\gamma D(P^{(t_{4}+1)}\|\bar{P}^{(t_{4}+1)})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}$ $\displaystyle
J_{\gamma}({P}^{(t_{4}+1)},\bar{P}^{(t_{4})})-\gamma
D(P^{(t_{4}+1)}\|\bar{P}^{(t_{4}+1)})$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}$ $\displaystyle
J_{\gamma}(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[\bar{P}^{(t_{4})}]],\bar{P}^{(t_{4})})+\gamma
D({P}^{(t_{4}+1)}\|\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[\bar{P}^{(t_{4})}]])-\gamma D(P^{(t_{4}+1)}\|\bar{P}^{(t_{4}+1)})$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}$ $\displaystyle
J_{\gamma}(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[\bar{P}^{(t_{4})}]],\bar{P}^{(t_{4})}),$ (164)

where each step is derived as follows. Step $(a)$ follows from the relation
$t_{2}=$

$\mathop{\rm
argmin}\limits_{t=2,\ldots,t_{1}}D^{F}(\theta^{(t)}\|\theta_{(t-1)})-D^{F}(\theta^{(t)}\|\bar{\theta}^{(t)})$.
Step $(b)$ follows from Lemma 2 and the condition (A1+) because (163) holds,
and the relation $D(P^{0}\|\bar{P}^{(t_{4})})\leq\delta$ follows from item (i)
with $t=t_{4}-1$ shown in Step 3. Step $(c)$ follows from (11). Step $(d)$
follows from the equation (163).

Combining (164) and (159), we have

$\displaystyle{\cal G}({P}^{(t_{2})})-\gamma
D(P^{(t_{2})}\|\bar{P}^{(t_{2})})\leq\epsilon_{1}+{\cal G}(P^{0}),$ (165)

which implies (157).

Step 5: The aim of this step is to show

$\displaystyle J_{\gamma}(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[\bar{P}^{(t_{3})}]],\bar{P}^{(t_{3})})-{\cal
G}(P^{0})-\epsilon_{1}\leq\frac{\gamma}{t_{1}-1}D(P^{0}\|\bar{P}^{(1)})$ (166)

under the choice of $t_{3}:=\mathop{\rm argmin}\limits_{1\leq t\leq
t_{1}-1}J_{\gamma}(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[\bar{P}^{(t)}]],\bar{P}^{(t)})$ when $t_{4}=t_{1}$, i.e., there exists
no integer $t\in[1,t_{1}-1]$ to satisfy (159).

Using (160), we have

$\displaystyle\frac{1}{\gamma}J_{\gamma}(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[\bar{P}^{(t_{3})}]],\bar{P}^{(t_{3})})-\frac{1}{\gamma}{\cal
G}(P^{0})-\epsilon_{1}\leq$ $\displaystyle
D(P^{0}\|\bar{P}^{(t)})-D(P^{0}\|\bar{P}^{(t+1)})$ (167)

for $t\leq t_{1}-1$. Taking the sum for (167), we have

$\displaystyle\frac{1}{\gamma}J_{\gamma}(\Gamma^{(m)}_{{\cal M}_{a}}[{\cal
F}_{3}[\bar{P}^{(t_{3})}]],\bar{P}^{(t_{3})})-\frac{1}{\gamma}{\cal
G}(P^{0})-\epsilon_{1}$ $\displaystyle\leq$
$\displaystyle\frac{1}{t_{1}-1}\sum_{t=1}^{t=t_{1}-1}D(P^{0}\|\bar{P}^{(t)})-D(P^{0}\|\bar{P}^{(t+1)})$
$\displaystyle=$
$\displaystyle\frac{1}{t_{1}-1}(D(P^{0}\|\bar{P}^{(1)})-D(P^{0}\|\bar{P}^{(t_{1})}))\leq\frac{1}{t_{1}-1}D(P^{0}\|\bar{P}^{(1)}).$
(168)

Therefore, we obtain (166).

Step 6: The aim of this step is to show the inequality (157) when
$t_{4}=t_{1}$, i.e., there exists no integer $t\in[1,t_{1}-1]$ to satisfy
(159). We obtain the following inequality

$\displaystyle{\cal G}({P}^{(t_{2})})-\gamma
D(P^{(t_{2})}\|\bar{P}^{(t_{2})})\leq J_{\gamma}(\Gamma^{(m)}_{{\cal
M}_{a}}[{\cal F}_{3}[\bar{P}^{(t_{3})}]],\bar{P}^{(t_{3})})$ (169)

in the same way as (164) in Step 4 by changing $t_{4}$ by $t_{3}$. Combining
(169) and (166), we obtain (157).

## References

  * (1) S. Amari, “Information geometry of the EM and em algorithms for neural networks,” Neural Networks 8(9): 1379 – 1408 (1995).
  * (2) Y. Fujimoto and N. Murata, “A modified EM algorithm for mixture models based on Bregman divergence,” Annals of the Institute of Statistical Mathematics, vol. 59, 3 – 25 (2007).
  * (3) S. Allassonnière and J. Chevallier, “A New Class of EM Algorithms. Escaping Local Minima and Handling Intractable Sampling,”. Computational Statistics & Data Analysis, Elsevier, vol. 159(C), (2019).
  * (4) S. Amari, K. Kurata and H. Nagaoka, “Information geometry of Boltzmann machines,” IEEE Transactions on Neural Networks, vol. 3, no. 2, pp. 260 – 271, (1992).
  * (5) S. Amari and H. Nagaoka, Methods of Information Geometry (AMS and Oxford, 2000).
  * (6) S. Amari, “$\alpha$-Divergence Is Unique, Belonging to Both f-Divergence and Bregman Divergence Classes,” IEEE Trans. Inform. Theory, vol. 55, 4925 – 4931 (2009).
  * (7) S. Arimoto, “An algorithm for computing the capacity of arbitrary discrete memoryless channels,” IEEE Trans. Inform. Theory, vol. 18, no. 1, 14 – 20 (1972).
  * (8) R. Blahut, “Computation of channel capacity and rate-distortion functions,” IEEE Trans. Inform. Theory, vol. 18, no. 4, 460 – 473 (1972).
  * (9) C. E. Shannon,“A Mathematical Theory of Communication,” Bell System Technical Journal, vol.27, 379–423 and 623–656 (1948).
  * (10) I. Csiszár, “On the computation of rate-distortion functions,” IEEE Trans. Inform. Theory, vol. 20, no. 1, 122 – 124 (1974).
  * (11) S. Cheng, V. Stankovic, and Z. Xiong, “Computing the channel capacity and rate-distortion function with two-sided state information,” IEEE Trans. Inform. Theory, vol. 51, no. 12, 4418 – 4425 (2005).
  * (12) K. Yasui, T. Suko, and T. Matsushima, “On the Global Convergence Property of Extended Arimoto-Blahut Algorithm,” EICE Trans. Fundamentals, vol.J91-A, no.9, pp.846-860, (2008). (In Japanese)
  * (13) K. Yasui, T. Suko, and T. Matsushima, “An Algorithm for Computing the Secrecy Capacity of Broadcast Channels with Confidential Messages,” Proc. 2007 IEEE Int. Symp. Information Theory (ISIT 2007), Nice, France, 24-29 June 2007, pp. 936 – 940.
  * (14) H. Nagaoka, “Algorithms of Arimoto-Blahut type for computing quantum channel capacity,” Proc. 1998 IEEE Int. Symp. Information Theory (ISIT 1998), Cambridge, MA, USA, 16-21 Aug. 1998, pp. 354.
  * (15) F. Dupuis, W. Yu, and F. Willems, “Blahut-Arimoto algorithms for computing channel capacity and rate-distortion with side information,” Proc. 2014 IEEE Int. Symp. Information Theory (ISIT 2014), Chicago, IL, USA, 27 June-2 July 2004, pp. 179.
  * (16) D. Sutter, T. Sutter, P. M. Esfahani, and R. Renner, “Efficient approximation of quantum channel capacities,” IEEE Trans. Inform. Theory, vol. 62, 578 – 598 (2016).
  * (17) H. Li and N. Cai, “A Blahut-Arimoto Type Algorithm for Computing Classical-Quantum Channel Capacity,” Proc. 2019 IEEE Int. Symp. Information Theory (ISIT 2019), Paris, France, 7-12 July 2019, pp. 255–259.
  * (18) N. Ramakrishnan, R. Iten. V. B. Scholz, and M. Berta, “Computing Quantum Channel Capacities,” IEEE Trans. Inform. Theory, vol. 67, 946 – 960 (2021).
  * (19) S. Toyota,“Geometry of Arimoto algorithm,” Information Geometry, vol. 3, 183 – 198 (2020).
  * (20) M. Hayashi, “Reverse em-problem based on Bregman divergence and its application to classical and quantum information theory,” In preparation.
  * (21) M. Hayashi, “Bregman divergence based em algorithm and its application to classical and quantum rate distortion theory,” IEEE Trans. Inform. Theory, (In press). DOI: 10.1109/TIT.2023.3239955.
  * (22) I. Csiszár and G. Tusnády, “Information geometry and alternating minimization procedures,” Statistics and Decisions, Supplemental Issue no. 1, 205–2377 (1984)
  * (23) J. A. O’Sullivan, “Alternating minimization algorithms: From Blahut-Arimoto to expectation-maximization,” in Codes, Curves, and Signals, A. Vardy, Ed. Norwell, MA: Kluwer Academic, 1998, pp. 173-192.
  * (24) R. G. Gallager, Information Theory and Reliable Communication. New York, NY, USA: Wiley, 1968.
  * (25) S. Arimoto, “On the converse to the coding theorem for discrete memoryless channels,” IEEE Trans. Inform. Theory, vol. 19, pp. 357–359, 1973.
  * (26) M. Hayashi, “Quantum wiretap channel with non-uniform random number and its exponent and equivocation rate of leaked information,” IEEE Trans. Inform. Theory, vol. 61, no. 10, 5595 – 5622 (2015).
  * (27) A. D. Wyner, “The wire-tap channel,” Bell. Sys. Tech. Jour., 54 1355 – 1387 (1975).
  * (28) I. Csiszár and J. Körner, “Broadcast channels with confidential messages,” IEEE Trans. Inform. Theory, vol. 24, no. 3, 339 – 348 (1978).
  * (29) I. Csiszár, “Almost independence and secrecy capacity,” Problems Inf. Transmiss., vol. 32, no. 1, pp. 40–47, 1996.
  * (30) M. Hayashi, “General nonasymptotic and asymptotic formulas in channel resolvability and identification capacity and their application to the wiretap channel,” IEEE Trans. Inform. Theory, vol. 52, no. 4, pp. 1562–1575, Apr. 2006.
  * (31) M. Hayashi, “Exponential decreasing rate of leaked information in universal random privacy amplification,” IEEE Trans. Inform. Theory, vol. 57, no. 6, pp. 3989–4001, Jun. 2011.
  * (32) M. Bellare, S. Tessaro, and A. Vardy, “Semantic security for the wiretap channel,” in Proc. 32nd Annu. Cryptol. Conf., vol. 7417. 2012, pp. 294–311.
  * (33) M. Hayashi and R. Matsumoto, “Secure Multiplex Coding with Dependent and Non-Uniform Multiple Messages,” IEEE Trans. Inform. Theory, vol. 62, no. 5, 2355 – 2409 (2016).
  * (34) S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press (2004)
  * (35) A. Winter, A. C. A. Nascimento, and H. Imai, “Commitment Capacity of Discrete Memoryless Channels,” Proc. 9th IMA International Conferenece on Cryptography and Coding (Cirencester 16-18 December 2003), pp. 35-51, 2003.
  * (36) H. Imai, K. Morozov, A. C. A. Nascimento and A. Winter, “Commitment Capacity of Discrete Memoryless Channels,” https: arXiv:cs/0304014.
  * (37) H. Imai, K. Morozov, A. C. A. Nascimento and A. Winter, “Efficient protocols achieving the commitment capacity of noisy correlations,” Proc. IEEE International Symposium on Information Theory (ISIT2006), Seattle, Washington, USA July 9 – 14, 2006, pp. 1432-1436.
  * (38) M. Hayashi and N. Warsi, “Commitment capacity of classical-quantum channels,” Proc. 2022 IEEE Int. Symp. Information Theory (ISIT), Aalto University in Espoo, Finland, June 26 – July 1, 2022 (In Press); arXiv: 2201.06333 (2022).
  * (39) H. Yamamoto and D. Isami, “Multiplex Coding of Bit Commitment Based on a Discrete Memoryless Channel,” Proc. IEEE ISIT 2007, pp. 721-725, June 24-29, 2007.
  * (40) M. Hayashi, “Secure list decoding and its application to bit-string commitment,” IEEE Trans. Inform. Theory (In Press); arXiv: 2103.11548.
  * (41) S. Toyota, Private communication (2019).
  * (42) N. Tishby, F. C. Pereira, and W. Bialek. “The information bottleneck method,” In The 37th annual Allerton Conference on Communication, Control, and Computing, pages 368 – 377. Univ. Illinois Press, 1999. DOI: 10.48550/arXiv.physics/0004057.
  * (43) M. Hayashi and Y. Yang, “Efficient algorithms for quantum information bottleneck,” Quantum, 7, 936 (2023).
  * (44) A.S. Holevo, “The capacity of the quantum channel with general signal states,” IEEE Trans. Inform. Theory, vol. 44, 269 (1998).
  * (45) B. Schumacher, and M.D. Westmoreland, “Sending classical information via noisy quantum channelsm” Phys. Rev. A vol. 56, 131 (1997).
  * (46) M. Hayashi, Quantum Information Theory: Mathematical Foundation, Graduate Texts in Physics, Springer-Verlag, (2017).
  * (47) G. Chen and M. Teboulle, “Convergence analysis of a proximal-like minimization algorithm using Bregman functions,” SIAM Journal on Optimization, 3(3):538 – 543 (1993).
  * (48) M. Teboulle, “Convergence of proximal-like algorithms,” SIAM Journal on Optimization, 7(4): 1069 – 1083 (1997).
  * (49) Y. Zhou, Y. Liang, and L. Shen, “A simple convergence analysis of Bregman proximal gradient algorithm,” Computational Optimization and Applications, vol 73, no. 3, 903 – 912 (2019).
  * (50) A. Beck, First-Order Methods in Optimization, MOS-SIAM Series on Optimization. SIAM, 2017\.
  * (51) A. Beck and M. Teboulle, “A fast iterative shrinkage-thresholding algorithm for linear inverse problems,” SIAM Journal on Imaging Sciences, 2(1), 183 – 202 (2009).
  * (52) Y. Nesterov, “Gradient methods for minimizing composite functions,” Mathematical Programming, Ser. B, 140, 125–161 (2013).
  * (53) A. Auslender and M. Teboulle, “Interior gradient and proximal methods for convex and conic optimization”, SIAM Journal on Optimization, 16(3), 697–725 (2006).
  * (54) Y. Nesterov, “A method for solving a convex programming problem with convergence rate $O(1/k^{2})$,” Soviet Mathematics - Doklady, 27(2), 372 – 376 (1983).
  * (55) Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Kluwer, Boston, 2004.
  * (56) M. Teboulle, “A simplified view of first order methods for optimization,”. Mathematical Programming, Ser. B, 170, 67–96 (2018).