8 Chain Rule Optimal Transport
211
Taking the integral over the support we find that
A i j ≤ exp
F
θ i + θ j − ¯
θ
− F(θ i ) − F(θ j ) +
k
l=1
w
l F(θ
l )
.
Overall, we get the upper bound:
KL(m : m
) ≤
⎛
⎝
i, j
w i w j exp
⎛
⎝ F
θ i + θ j − ¯
θ
− F(θ i ) − F(θ j ) +
k
l=1
w
l F(θ
l )
⎞
⎠
⎞
⎠ − 1.
(8.17)
In general, we have the following upper bound for f -divergences [14]:
Property 8.10 ( f -divergence upper bound) The f -divergence between two densities p and q with respect to μ is upper bounded as follows: I f ( p : q) ≤
(q(x) −
p(x)) f
q(x)
p(x)
dμ(x).
Proof Let us use the non-negative property of scalar Bregman divergences:
B F (a : b) = F(a) − F(b) − (a − b)F
(b) ≥ 0.
Let F(x) = f (x) (with F(1) = f (1) = 0), and a = 1 and b =
q
p
. It follows that
B F
1 :
q
p
= − f
q
p
−
1 −
q
p
f
q
p
≥ 0.
That is,
p f
q
p
≤ p
q
p
− 1
f
q
p
.
Taking the integral over the support, we get
I f ( p : q) ≤
(q − p) f
q
p
dμ.
For example, when f (u) = − log u (with f
(u) = −
1
u
), we recover the former
upper bound:
KL( p : q) ≤
( p − q)
p
q
dμ =
p
2
q
dμ − 1.
Notice that
p
2
q
dμ − 1 is a f -divergence for the generator f (u) =
1
u
− 1.