Negative Entropy

Negative entropy, its properties, and applications in machine learning.

• Background
• Strongly convex property
• Applications
  • Differentiable dynamic programming
  • Smoothed Wasserstain distance

Background

Notation: Denoting standard simplex in ${\mathbb{R}}^n$ as ${\mathrm{△}}_n\triangleq \{\mathit{\lambda }\in {\mathbb{R}}_{+}^n:⟨\mathbf{1},\mathit{\lambda }⟩=1\}$.

Strongly convex property

We consider the negative entropy defined as

$$\eta (\mathbf{x})=⟨\mathbf{x},\ln \mathbf{x}⟩,\mathbf{x}\in {\mathrm{△}}_n.$$

Theorem 1. The negative entropy is a strongly convex on ${\mathrm{△}}_n$ in the ${\ell }_1$-norm with convexity parameter 1, i.e., for any $\mathbf{h}\in {\mathbb{R}}^n$, the following inequality holds

$$⟨{\mathrm{\nabla }}^2\eta (\mathbf{x})\mathbf{h},\mathbf{h}⟩\le \Vert \mathbf{h}{\Vert }_1^2.$$

Proof. First note that $\mathrm{\nabla }\eta (\mathbf{x})=\mathbf{1}+\ln \mathbf{x}$ and ${\mathrm{\nabla }}^2\eta (\mathbf{x})=\mathrm{diag}(1/\mathbf{x})$, and thus

$$\begin{array}{r}⟨{\mathrm{\nabla }}^2\eta (\mathbf{x})\mathbf{h},\mathbf{h}⟩=⟨\mathbf{h},\frac{\mathbf{h}}{\mathbf{x}}⟩=\sum _{i=1}^n\frac{h_i^2}{x_i}.\end{array}$$

Now we shall find

$$minf(\mathbf{x})\triangleq ⟨\mathbf{h},\frac{\mathbf{h}}{\mathbf{x}}⟩\mathrm{s}.\mathrm{t}.⟨\mathbf{1},\mathbf{x}⟩=1.$$

According to the Proposition 1 the optimal ${\mathbf{x}}^{\ast }$ and optimal dual multiplier ${\lambda }^{\ast }$ satisfy

$$\mathrm{\nabla }f({\mathbf{x}}^{\ast })=-{\left(\frac{\mathbf{h}}{{\mathbf{x}}^{\ast }}\right)}^2=\mathbf{1}{\lambda }^{\ast }\Rightarrow {\left(\frac{h_i}{x_i^{\ast }}\right)}^2={\lambda }^{\ast }\Rightarrow x_i^{\ast }=\frac{|h_i|}{\sqrt{{\lambda }^{\ast }}}$$

in the first step, we have absorbed the minus operator into ${\lambda }^{\ast }$ since it is a free variable; the second step follows the fact that $h_i\in \mathbb{R}$ and $x_i^{\ast }\in {\mathbb{R}}_{+}$.

Taking $x_i^{\ast }=\frac{|h_i|}{\sqrt{{\lambda }^{\ast }}}$ along with $\sum _{i=1}^n{x}_i^{\ast }=1$, we get

$$f({\mathbf{x}}^{\ast })={\left(\sum _i^n|h_i|\right)}^2=\Vert \mathbf{h}{\Vert }_1^2.$$

Proposition 1. Let ${\mathbf{x}}^{\ast }$ be a local minimum of a differentiable function $f$ subject to the linear equality constraints

$$\mathbf{x}\in \mathcal{E}=\{\mathbf{x}\in {\mathbb{R}}^n|A\mathbf{x}=\mathbf{b}\}\ne \mathrm{\varnothing },$$

where $A$ is an $m\times n$-matrix with full row rank, and $m<n$. Then there exists a vector of multipliers ${\mathit{\lambda }}^{\ast }$ such that

$$\mathrm{\nabla }f({\mathbf{x}}^{\ast })=A^{\mathrm{\top }}{\mathit{\lambda }}^{\ast }.$$

Proof. Let ${\mathbf{u}}_i\in {\mathbb{R}}^n,i=1\dots k$ be the basis of the null space of $A$ and $g(\mathbf{v})\triangleq {\mathbf{x}}^{\ast }+U\mathbf{v}$ where $\mathbf{v}\in {\mathbb{R}}^k$, $U=[{\mathbf{u}}_1,\dots ,{\mathbf{u}}_k]$. We observe that $g(\mathbf{v})\in \mathcal{E}$ for any $\mathbf{v}\in {\mathbb{R}}^k$, and let $\varphi (\mathbf{v})=f(g(\mathbf{v}))$. Since $\varphi (0)$ is a local minimum of $\varphi$ then

$$\mathrm{\nabla }\varphi (\mathbf{v}){|}_{\mathbf{v}=0}=U^{\mathrm{\top }}\mathrm{\nabla }f({\mathbf{x}}^{\ast })=0,$$

i.e., $\mathrm{\nabla }f({\mathbf{x}}^{\ast })$ is orthogonal to the null space of $A$, hence $\mathrm{\nabla }f({\mathbf{x}}^{\ast })$ must stay in the row space of $A$ which completes the proof.

Remark: $\mathrm{d}\varphi (\mathbf{v})=\mathrm{d}f(g(\mathbf{v}))=⟨\mathrm{\nabla }f,\mathrm{d}g(\mathbf{v})⟩=⟨\mathrm{\nabla }f,U\mathrm{d}\mathbf{v}⟩=⟨U^{\mathrm{\top }}\mathrm{\nabla }f,\mathrm{d}\mathbf{v}⟩$.

Applications

Differentiable dynamic programming

The $max$ operator can be formulated as

$$max(\mathbf{x})=\underset{\mathbf{q}\in {\mathrm{△}}_{+}}{sup}⟨\mathbf{q},\mathbf{x}⟩$$

However, it is not a smooth operator w.r.t $\mathbf{x}$ and we can smooth it with negative entropy to yield

$${\max }_{\eta }(\mathbf{x})=\underset{\mathbf{q}\in {\mathrm{△}}_{+}}{sup}⟨\mathbf{q},\mathbf{x}⟩-\eta (\mathbf{q})$$

where the r.h.s is a strongly concave function w.r.t $\mathbf{q}$, more details is available in the paper.

Smoothed Wasserstain distance

Recall the Wasserstain distance between two measure $\mathbf{a},\mathbf{b}$: ${\mathrm{L}}_C(\mathbf{a},\mathbf{b})\triangleq \underset{P\in U(\mathbf{a},\mathbf{b})}{min}⟨P,C⟩$ the r.h.s is a convex function w.r.t $P$ and we can transform it to a $ϵ$-strongly convex function with negative entropy ${\mathrm{L}}_C^{ϵ}(\mathbf{a},\mathbf{b})\triangleq \underset{P\in U(\mathbf{a},\mathbf{b})}{min}⟨P,C⟩+ϵ\eta (P).$