12
$\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$
  • $\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$ – Aryeh Kontorovich Jul 28 '18 at 22:10
  • $\begingroup$ Which result in this paper are you referring to? $\endgroup$ – Maziar Sanjabi Jul 28 '18 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$ – Maziar Sanjabi Jul 29 '18 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$ – Maziar Sanjabi Jul 29 '18 at 8:07
  • $\begingroup$ See Theorem 11 in the paper I linked. $\endgroup$ – Aryeh Kontorovich Jul 29 '18 at 8:51
6
+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$
  • $\begingroup$ I have added a remark on the optimality of the lower bound. $\endgroup$ – Iosif Pinelis Jul 31 '18 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$ – Maziar Sanjabi Jul 31 '18 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$ – Maziar Sanjabi Jul 31 '18 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$ – Iosif Pinelis Aug 1 '18 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$ – Iosif Pinelis Aug 1 '18 at 3:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.