On the Strong Convexity of Negative Entropy and Kullback-Leibler Divergence.

Author: Tran Thu Le
Date: 15/02/2023

Abstract. In this post, we investigate the locally strong convexity of the negative entropy and its Bregman divergence called Kullback-Leibler Divergence.

---

For $u\in \mathbb R^m_+$, let
$$\log(u) \triangleq [\log(u_1), .... ,\log(u_m)]^T \in \mathbb R^m.$$

We say that $u$ is a probability if, in addition, $\langle 1_m, u\rangle = \sum_{i=1}^n u_i=1$.

The negative entropy function of $u$ is denoted by
$$h(u) = \langle u, \log(u)\rangle.$$
with gradient
$$\nabla h(u) = 1_m+ \log(u)$$
and Hessian
$$\nabla^2 h (u) = diag(u^{-1}).$$

Note. Here note that $I(u) = -\log(u) = 1-\nabla h(u)$ is called the information of $u$.

The following theorem summarizes some of basic results of $h$ when $u$ is bounded by a box.

Theorem. If $u\in [0, \frac{1}{\alpha}]^m$, then

1. $\nabla^2 h(u) - \alpha I_m$ is positively semidefinite $$\nabla^2 h(u) - \alpha I_m\geq 0$$
2. $\nabla h$ satisfies $$||\nabla h(u) - \nabla h(r)||\geq \alpha ||u-r||$$
   for all $u, r\in \mathbb R^m$.
3. $h$ is $\alpha$-strongly convex
   $$Breg_h(u, r) \triangleq h(u) - h(r) - \langle \nabla h(r), u-r\rangle\geq \frac{\alpha}{2}||u-r||^2$$
   for all $u, r\in \mathbb R^m$.

Here $Breg_h$ is called Bregman divergence of $h$. By this theorem we see that

The negative entropy is $\alpha$-strongly convex on $[0, \frac{1}{\alpha}]^m$.

We call the Bregman divergence of negative entropy Kullback Leibler divergence and denote it as $$KL(u, r)\triangleq Breg_h(u, r).$$ It has the following formula

Theorem. Let $u, r$ be probabilities, then the Kullback Leibler divergence has the formula
$$KL(u, r) = \langle u, \log(u/r)\rangle - \langle 1_m, u\rangle + \langle 1_m, r\rangle$$
In particular, if $u, r$ are probabilities, we have
$$KL(u, r) = \langle u, \log(u/r)\rangle$$

Proof. We have
$$\begin{aligned} & h(u)-h(r) - \langle \nabla h(r), u-r\rangle\\ = & \langle u, \log(u)\rangle - \langle r, \log(r)\rangle - \langle 1_m+\log(r), u-r\rangle \\ = & \langle u, \log(u/r)\rangle - \langle 1_m, u\rangle + \langle 1_m, r\rangle \end{aligned}$$
If $u, r$ are probabilities, on obtains the desired equality since $\langle 1_m, u\rangle = \langle 1_m, r\rangle=1$. $\square$

In general, the Bregman divergence is always strongly convex for the first argument if $h$ is.

Theorem. If $h$ is $\alpha$-strongly convex, then so is $Breg_h(\cdot, r_0)$ for any fixed $r_0\in \mathbb R^m$.

Proof. This is clear since $Breg_h(\cdot, r_0)$ is the sum of a strongly convex function $h$ and an affine function.$\square$

In general, the Bregman divergence is not strongly convex for the second argument. Hoever, for the Kullback-Leibler divergence, it is locally strongly convex.

Theorem. For $u_0$ fixed on $\mathbb R^m$, we have

• $KL(u_0, \cdot)$ is strongly convex on $[0, 1/\alpha]^m$
• $KL(u_0, \cdot)$ is strongly smooth on $[1/\beta, +\infty)$

Proof. Indeed, we have $$\nabla_r KL(u_0, r) =-\frac{u_0}{r} + 1_m$$
and $$\nabla^2_r KL(u_0, r) =diag( \frac{u_0}{r^2}) \geq \frac{u_0}{\alpha^2} I_m.$$
for $r\leq 1/\alpha$. Note that the RHS is positively defnite since $u_0\geq 0$.
And that $$\nabla^2_r KL(u_0, r) \leq \frac{u_0}{\beta^2} I_m.$$
for $r\geq 1/\beta$.
$\square$

References

[1]: MSE - How to show 1D negative entropy function is strongly convex?
[2]: MSE - How to show nD negative entropy function is strongly convex?