14
$\begingroup$

By KL divergence I mean $D(P||Q) = \int dP \log(\frac{dP}{dQ})$. I am looking for the conditions under which this strong convexity is true and possible references. I could not find an answer for infinite dimensions. I am specifically interested in the case where the dimension is uncountable.

Note that this strong convexity is equivalent to the strong convexity of negative entropy function $H(P) = \int dP \log(dP)$.

$\endgroup$
18
  • $\begingroup$ See the proofs here -- arxiv.org/pdf/1206.2459.pdf -- they hold in infinite dimensions (though the paper formally deals with finite dimensions). $\endgroup$ Commented Jul 28, 2018 at 22:10
  • $\begingroup$ Which result in this paper are you referring to? $\endgroup$ Commented Jul 28, 2018 at 22:21
  • $\begingroup$ It suffices to prove the statement for the negative entropy $H(P) = \int dP log(dP)$. It seems that for $P$ and $Q$ with bounded negative entropy, $H(P)-H(Q)-\langle H'(Q), P-Q\rangle = KL(P||Q)$ (I am not sure if this equality could be proved for general $P$ and $Q$). With this equality, one can use Pinsker's inequality to derive the lower bound $H(P)-H(Q)-\langle H'(Q), P-Q\rangle \geq \frac{1}{2}\|P-Q\|_1^2$. But this does not prove the strong convexity unless one knows that on the space of possible $P$ and $Q$'s there is a fixed lower bound on the H. No fixed upper bound on $H$ is needed. $\endgroup$ Commented Jul 29, 2018 at 8:02
  • $\begingroup$ In the problem that I was working on, the set of $P$'s comes from transport plans between two marginal distributions $p$ and $q$ with bounded entropy. Thus, the lower bound is obvious and the set of bounded entropy $P$'s could be convex. So, it seems that above argument could be used to prove strong convexity of negative entropy on the convex set of tranports with bounded H. $\endgroup$ Commented Jul 29, 2018 at 8:07
  • $\begingroup$ See Theorem 11 in the paper I linked. $\endgroup$ Commented Jul 29, 2018 at 8:51

1 Answer 1

9
+50
$\begingroup$

$\newcommand{\de}{\delta} \newcommand{\De}{\Delta} \newcommand{\ep}{\varepsilon}$

Take any probability measures $P_0,P_1$ absolutely continuous with respect (w.r.) to $Q$. We shall prove the following:

Theorem 1. For any $t\in(0,1)$, \begin{align*} \De:=(1-t)H(P_0)+tH(P_1)-H(P_t) \ge\frac{(1-t)t}2\,\|P_1-P_0\|^2, \end{align*} where $\|P_1-P_0\|:=\int|dP_1-dP_0|$ is the total variation norm of $P_1-P_0$, \begin{equation*} H(P):=D(P||Q)=\int \ln\frac{dP}{dQ}\,dP, \end{equation*} and, for any elements $C_0,C_1$ of a linear space, $C_t:=(1-t)C_0+tC_1$. Thus, by "A third definition[8] for a strongly convex function", indeed $D(P||Q)$ is strongly convex in $P$ w.r. to the total variation norm.

We see that the lower bound on $\De$ does not depend on $Q$.

Proof of Theorem 1. Take indeed any $t\in(0,1)$. Let $f_j:=\frac{dP_j}{dQ}$ for $j=0,1$, so that $f_t=\frac{dP_t}{dQ}$. By Taylor's theorem with the integral form of the remainder, for $h(x):=x\ln x$ and $j=0,1$ we have \begin{equation*} h(f_j)=h(f_t)+h'(f_t)(f_j-f_t)+(f_j-f_t)^2\int_0^1 h''((1-s)f_t+sf_j)(1-s)\,ds, \end{equation*} whence \begin{align*} \de&:=(1-t)h(f_0)+th(f_1)-h(f_t) \\ &=(1-t)t\,(f_1-f_0)^2\, \int_0^1\Big(\frac t{(1-s)f_t+sf_0}+\frac{1-t}{(1-s)f_t+sf_1}\Big)(1-s)\,ds \\ &=(1-t)t\,(f_1-f_0)^2\, \int_0^1\Big(\frac t{f_{u_0(t,s)}}+\frac{1-t}{f_{u_1(t,s)}}\Big)(1-s)\,ds, \end{align*} where $$u_j(t,s):=(1-s)t+js.$$ So, \begin{equation} \De=\int\de\,dQ=(1-t)t\,\int_0^1(1-s)\,ds\,[tI(u_0(t,s))+(1-t)I(u_1(t,s))], \tag{1} \end{equation} where \begin{equation*} I(u):=\int\frac{(f_1-f_0)^2}{f_u}\,dQ. \end{equation*} Next, take any $u\in(0,1)$. Then $P_1$ is absolutely continuous w.r. to $P_u$. Introducing
$g_u:=\dfrac{dP_1}{dP_u}=\dfrac{f_1}{f_u}$, we have \begin{multline*} I(u)=\frac1{(1-u)^2}\,\int\frac{(f_1-f_u)^2}{f_u}\,dQ =\frac1{(1-u)^2}\,\int(g_u-1)^2\,dP_u \\ \ge\frac1{(1-u)^2}\,\Big(\int|g_u-1|\,dP_u\Big)^2 =\frac1{(1-u)^2}\,\|P_1-P_u\|^2=\|P_1-P_0\|^2. \tag{2} \end{multline*} Note also that for any $t\in(0,1)$ and $s\in(0,1)$ we have $u_0(t,s)\in(0,1)$ and $u_1(t,s)\in(0,1)$ and hence, by (2), $I(u_j(t,s))\ge\|P_1-P_0\|^2$ for $j=0,1$. Now Theorem 1 follows by (1).

Remark. The constant factor $\frac12$ in the lower bound in Theorem 1 is the best possible one. Indeed, assuming that $P_1$ is absolutely continuous w.r. to $P_0$ and introducing $f:=\frac{dP_1}{dP_0}$, after some rather straightforward manipulations we get \begin{equation} \De=\int k(t,f)\,dP_0, \tag{*} \end{equation} where $\De$ is as before and \begin{equation} k(t,f):=t f \ln f-(1-t+t f)\ln(1-t+t f). \end{equation} Take now any $h\in(0,1)$ and let $f$ take values $1-h,1+h$ each on a set of $P_0$-measure $1/2$, so that $\|P_1-P_0\|=h$. Then, in view of (*), for each $t\in(0,1)$, \begin{equation} \De=\frac12\,k(t,1-h)+\frac12\,k(t,1+h)\sim \frac{(1-t)t}2\,h^2=\frac{(1-t)t}2\,\|P_1-P_0\|^2 \end{equation} as $h\downarrow0$, which confirms the optimality claim.

$\endgroup$
14
  • $\begingroup$ I have added a remark on the optimality of the lower bound. $\endgroup$ Commented Jul 31, 2018 at 20:22
  • $\begingroup$ So the absolute continuity of $dP_1$ and $dP_2$ w.r. to each other seems to be absolutely necessary for the proof (without it the Taylor expansion would fail, right?). In the problem that motivated my question on this, $dP_1$ and $dP_2$ are optimal solutions to the following optimization (assuming everything is well behaved): $P_i = \arg\min_{P} \int (C_i~dP) + \lambda KL(P||Q)$ (subject to some other constraints on the marginals of $P$). And I am not sure if it would be possible to make sure the $P_1$ and $P_2$ would be absolutely continuous w.r.t each other. $\endgroup$ Commented Jul 31, 2018 at 20:25
  • $\begingroup$ And also why is this inequality true: $u(t):=\frac1{f_{2t/3}}+\frac1{f_{(2t+1)/3}}\ge(1-t)u(0)+tu(1)$ $\endgroup$ Commented Jul 31, 2018 at 20:27
  • $\begingroup$ The inequality for $u(t)$ went the wrong way. Now this is fixed, albeit the new lower bound is slightly worse, and the proof is now more complicated. As for the mutual absolute continuity condition for $P_0$ and $P_1$, I believe it can be rather easily removed by approximation, say by adding small positive constants to the densities $f_0$ and $f_1$ and then renormalizing to keep the condition $\int f_j\,dQ=1$. $\endgroup$ Commented Aug 1, 2018 at 1:25
  • $\begingroup$ The previous, better (and optimal) bound is now restored. The proof is greatly simplified; computer algebra is no longer needed. Also, the mutual absolute continuity condition for $P_0$ and $P_1$ is no longer needed or used. $\endgroup$ Commented Aug 1, 2018 at 3:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .