2
$\begingroup$

Let $P$ be a probability distribution and let $A$ and $B$ be some events, and suppose that we want to minimise an $f$-divergence between $P$ and the set of all distributions $Q$ that satisfy that constraint that $Q(B|A) = q$ for some fixed $q \geq P(B|A)$. Let $P_{f}$ denote the result of minimising a given $f$-divergence with this constraint. Is it always true, for any $f$, that $P_{f}(A) \leq P(A)$? I know that this holds for several examples (Kullback Leibler divergence, Hellinger distance, Inverse Kullback Leibler divergence), but is it true in general?

$\endgroup$
1
$\begingroup$

After having some trouble understanding this question, I have come to interpret it as follows: Let $P$ be a probability measure on a measurable space $(S,\Sigma)$. Suppose that $A$ and $B$ are in $\Sigma$, and $P(A)>0$. Fix any $q\in[P(B|A),1]$. Let $f\colon[0,\infty]\to(-\infty,\infty]$ be a function that is convex and continuous on $[0,\infty]$ and finite on $(0,\infty)$. Let $Q_f$ be a minimizer of the $f$-divergence $$D_f:=D_f(P||Q):=\int_S f\Big(\frac{dP}{dQ}\Big)\,dQ$$ over the set of all probability measures $Q$ on $(S,\Sigma)$ such that $Q(B|A)=q$. Is it then necessarily true that $Q_f(A)\le P(A)$?

The answer to this question is no. Indeed, let $S=\{1,2,3\}$, $A=\{1,2\}$, $B=\{2,3\}$, $P(\{i\})=p_i$ where $(p_1,p_2,p_3)=(1,1,2)/4$, $q=4/5$, and $f(x)=(4-3x)_++(1-2x)_+$, where $u_+:=\max(0,u)$.

Introducing now $k_i:=Q(\{i\})/P(\{i\})$, rewrite the conditions that $Q(B|A)=q$ and that $Q$ is a probability measure as $\frac{k_2}{k_1+k_2}=\frac45$ and $\frac14\,(k_1+k_2)+\frac12\,k_3=1$, which can be further rewritten as $k_1=\frac45\,(1-k_3/2)$ and $k_2=\frac{16}5\,(1-k_3/2)$, with the restriction $0\le k_3\le2$ to ensure that $k_1,k_2,k_3$ are all nonnegative. So, we can write \begin{equation} D_f(P||Q)=F(k_3):=\sum_1^3 f(1/k_i)k_i p_i = \begin{cases} \frac{2}{5} (7-6 k_3) & \text{if } k_3\le\tfrac18, \\ \frac{11}{4}-2 k_3 & \text{if } \frac{1}{8}\leq k_3\leq \frac{3}{4} \\ \frac{1}{20} (8 k_3+19) & \text{if } \frac{3}{4}\le k_3\le\frac{49}{32}, \\ 2 k_3-\frac{3}{2} & \text{if } \frac{49}{32}\le k_3. \end{cases} \end{equation} Thus, the minimization of $D_f(P||Q)$ in $Q$ such that $Q(B|A)=q$ here reduces to the minimization of the (convex) function $F$ on the interval $[0,2]$. It is obvious that the unique minimizer here is $k_3=\frac34$, which then leads to $k_1=\frac12$, $k_2=2$, and $Q_f(A)=k_1p_1+k_2p_2=\frac18+\frac12>\frac12=P(A)$. So, the inequality $Q_f(A)\le P(A)$ fails to hold.


Remark. It may be of interest how the above counterexample was obtained; that was based on a few not so straightforward observations. The difficulty here is that the convex function $f$ and the measures $P$ and $Q$ are, in general, infinite-dimensional objects. We minimize $D_f(P||Q)$ in $Q$ subject to the restriction $Q(B|A)=q$, which can be rewritten as $Q(A\cap B)=qQ(A)$. Note that this restriction is (i) linear in $Q$ and (ii) depends on $Q$ only through its restriction to the small sigma algebra $\Sigma_0$ generated by the partition $(A\setminus B,A\cap B,S\setminus A)$ of $S$.

On the other hand, $D_f(P||Q)=\int_S g(K)\,dP$, where $K:=\frac{dQ}{dP}$ and \begin{equation*} g(k):=k\,f(\tfrac1k),\quad\text{with }g(0):=g(0+),\ g(\infty):=g(\infty-). \tag{1} \end{equation*} The latter formula defines a map of the set of all functions $f\colon[0,\infty]\to(-\infty,\infty]$ that are convex and continuous on $[0,\infty]$ and finite on $(0,\infty)$ onto the same set (in fact, this map is an involution and hence bijective). So, by Jensen's inequality, \begin{equation*} D_f(P||Q)=E_P g(K)=E_P\,E_P(g(K)|\Sigma_0)\ge E_P g(K_0),\quad\text{where } K_0:=E_P(K|\Sigma_0) \end{equation*} and $E_P$ denotes the expectation with respect to the measure $P$. So, without loss of generality (wlog) $K$ is $\Sigma_0$-measurable and hence takes constant values, say $k_1,k_2,k_3$, on the sets $A\setminus B,A\cap B,S\setminus A$. That is, wlog $S=\{1,2,3\}$, as in the above counterexample. Thus, the measures $P$ and $Q$ are no longer infinite-dimensional objects; they are now completely represented by their values on the sets $A\setminus B,A\cap B,S\setminus A$: say $p_1,p_2,p_3$ for $P$ and hence $k_1p_1,k_2p_2,k_3p_3$ for $Q$. Accordingly, now we can write \begin{equation*} D_f(P||Q)=\sum_1^3 g(k_i)p_i. \end{equation*} We need to minimize this in $k_1,k_2,k_3\ge0$ subject to the linear restrictions $k_1p_1+k_2p_2+k_3p_3=1$ and $k_2p_2=q(k_1p_1+k_2p_2)$, the latter restriction representing $Q(A\cap B)=qQ(A)$. The condition $q \geq P(B|A)$ can now be rewritten as $vp_2=q(p_1+p_2)$ for some $v\ge1$. Writing the Lagrange multipliers system, we see that the dependence on the convex function $g$, an infinite-dimensional object, is reduced to the dependence on just the three numbers $h_i:=g'(k_i)$, such that the function $k_i\mapsto h_i$ is nondecreasing, that is, $(h_i-h_j)(k_i-k_j)\ge0$ for all $i,j$ in $\{1,2,3\}$.

The inequality $Q_f(A)\le P(A)$ in question in the (now justified) reduced setting can be rewritten as $k_1p_1+k_2p_2\le p_1+p_2$. Thus, it remains to check whether the latter inequality is implied by the system of algebraic equations and inequalities described above, involving the 10 real variables $p_1,p_2,p_3,k_1,k_2,k_3,v,h_1,h_2,h_3$. With the help of a computer algebra package, we find the above counterexample showing that the implication in question fails to hold in general. (Given the numbers $h_i$ such that $(h_i-h_j)(k_i-k_j)\ge0$ for all $i,j$, we can find any number of convex functions $g$ such that $h_i=g'(k_i)$ for $i=1,2,3$; I took one of such functions $g$ and then obtained $f$ from $g$ using the involution formula (1).)

$\endgroup$
  • $\begingroup$ I have added a remark about how the above counterexample was obtained. $\endgroup$ – Iosif Pinelis Feb 18 '18 at 5:42
  • $\begingroup$ Thanks a lot for the very helpful answer (and sorry if the question wasn't clearly phrased). I just have one more question. Isn't it normally assumed that f(1) = 0 for any f-divergence? This doesn't seem to be satisfied by the counterexample? $\endgroup$ – King Kong Feb 19 '18 at 11:26
  • 1
    $\begingroup$ @BenEva : You can always replace $f$ by $\tilde f:=f-c$, where $c$ is any constant; in particular, you can take $c=f(1)$, thus making $\tilde f(1)=0$, if desired. Then $D_f(P||Q)$ will get replaced by $D_{f-c}(P||Q)=D_f(P||Q)-c$, which clearly will not affect the minimizing $Q$ at all. $\endgroup$ – Iosif Pinelis Feb 19 '18 at 12:17

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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