26.4 Legendre functions 295Example26.10.Letf(x) =∑
ixilog(xi)−xibe the unnormalized negentropy,
which we met in Example 26.5. Similarly to the previous example,dom(f) =
[0,∞)d,int(dom(f)) = (0,∞)d and∂int(dom(f)) = {x ∈[0,∞)d : xi =
0 for somei∈[d]}. The gradient is∇f(x) =log(x) and thus‖∇f(x)‖→∞as
x→∂int(dom(f)). Strict convexity also holds, hencefis Legendre. You already
met the Bregman divergenceDf(x,y), which turned out to be the relative entropy
whenx,ybelong to the simplex. Exercise 26.8 asks you to calculate the dual of
f(can you guess what this function will be?), the Bregman divergence induced
byf∗and to verify Theorem 26.6.
The Taylor series of the Bregman divergence is often a useful approximation.
Letg(y) =Df(x,y), which fory=xhas∇g(y) = 0 and∇^2 g(y) =∇^2 f(x). A
second order Taylor expansion suggests that
Df(x,y) =g(y)≈g(x) +〈∇g(x),y−x〉+1
2
‖y−x‖^2 ∇ (^2) f(x)=
1
2
‖y−x‖^2 ∇ (^2) f(x).
This approximation can be very poor ifxandyare far apart. Even whenxandy
are close the lower order terms are occasionally problematic, but nevertheless the
approximation can guide intuition. The next theorem, which is based on Taylor’s
theorem, gives an exact result.
Theorem26.11.Iffis convex and twice differentiable inA=int(dom(f))and
x,y∈A, then there exists anα∈[0,1]andz=αx+ (1−α)ysuch that
Df(x,y) =
1
2
‖x−y‖^2 ∇ (^2) f(z).
The next result will be useful.
Theorem 26.12. Letη > 0 andf be Legendre and twice differentiable in
A=int(dom(f)),x,y∈Aand letz∈[x,y]be the point such thatDf(x,y) =
1
2 ‖x−y‖
(^2) ∇ (^2) g(z). Then for al lu∈Rd,
〈x−y,u〉−
Df(x,y)
η
≤
η
2‖u‖^2 (∇ (^2) f(z))− 1.
Although the Bregman divergence is not symmetric, the right hand side does
not depend on the order ofxandyin the Bregman divergence except that
z∈[x,y] may be different.
Proof Strict convexity offensures thatH=∇^2 f(z) is invertible. Applying
Cauchy-Schwarz,
〈x−y,u〉≤‖x−y‖H‖u‖H− 1 =‖u‖H− 1
√
2 Df(x,y).Therefore
〈x−y,u〉−Df(x,y)
η≤‖u‖H− 1√
2 Df(x,y)−Df(x,y)
η≤
η
2‖u‖^2 H− 1 ,