The duo Bregman and Fenchel-Young divergences
Frank Nielsen
cs.IT
2022-02-22
Duo Fenchel-Young/Bregman divergences compute KL across nested exponential families; truncated normals, exponential-vs-Laplace, and Poisson-vs-geometric get closed forms.
KL between two densities in the same exponential family is a Bregman divergence, and equally a Fenchel-Young divergence. Amari wrote that identity for dually flat spaces; Azoury and Warmuth used the dual-Bregman form for online density estimation in 2001. The identity breaks as soon as the two measures live in different families: a half-line exponential against a two-sided Laplace, a truncated Gaussian against a full Gaussian. Different supports mean different log-partition functions, so the single-generator formula KL = BF(θ2:θ1) no longer applies.
Frank Nielsen (Sony CSL) packages the gap as a pair of convex generators. If two strictly convex functions satisfy F1 ≥ F2 on the common domain, a duo Fenchel-Young divergence is well-defined and non-negative, and nested-family KL equals that divergence. The journal version is Entropy 2022, 24(3), 421.
Ordinary Fenchel-Young is Y{F,F}(θ,η') = F(θ)+F(η')−θᵀη', non-negative by the Fenchel-Young inequality, with equality iff η'=∇F(θ). The duo version splits the generators:
Y{F1,F2}(θ,η') = F1(θ) + F2(η') − θᵀη'
Non-negativity needs F1(θ)≥F2(θ) everywhere on the overlap. The Legendre-Fenchel transform reverses dominance: a larger F1 yields a smaller conjugate F1, so the duo gap is at least the ordinary Fenchel-Young gap.
In primal coordinates this is the duo Bregman divergence
B{F1,F2}(θ:θ') = F1(θ) − F2(θ') − (θ−θ')ᵀ∇F2(θ')
Graphically it is the taller curve minus the tangent to the shorter curve at θ'. When F1=F2 it collapses to ordinary Bregman. The quadratic pair F1=(a/2)θ², F2=(1/2)θ² is non-negative only for a≥1; a=1 recovers half squared Euclidean distance, and a=1/2 dips below zero.
Nested exponential families are the main application. Family E2 lives on a large support X2; family E1 is the truncation to X1⊂X2, sharing sufficient statistics and natural parameters. The log-partition functions then satisfy F2≥F1 because the integral domain is larger, while the natural parameter spaces nest the other way, Θ2⊆Θ1. Theorem 1:
DKL[p{θ1}:q{θ2}] = B{F2,F1}(θ2:θ1) = Y{F2,F1}(θ2:η1)
Parameter order is swapped. Reverse KL is infinite: the larger-support density is not absolutely continuous with respect to the truncated one.
The α-skewed Bhattacharyya distance follows the same pattern and becomes a duo Jensen divergence (Theorem 2):
J{F1,F2,α}(θ1:θ2) = α F1(θ1) + (1−α) F2(θ2) − F1(αθ1+(1−α)θ2)
Dividing by 1−α and sending α→1 recovers the KL above, in parallel with the classical Jensen-to-Bregman limit inside a single family.
Drop the F1≥F2 constraint and the duo Bregman can go negative; the paper calls that a signed pseudo-divergence. The DCA / CCCP iteration of difference-of-convex programming is exactly minimization of that signed gap with the right argument held fixed.
No neural leaderboard. The usable output is a handful of closed forms.
| Pair | KL | Versus same-family KL |
| Exponential λ1 vs Laplace λ2 | log(λ1/λ2)+λ2/λ1+log 2−1 | Extra log 2; the rest is Itakura-Saito DIS[λ2:λ1] |
| Half-normal σ1 vs normal σ2 | ½(log(σ2²/σ1²)+σ1²/σ2²+log 4−1) | Extra log 2, since ½ log 4 = log 2 |
| Truncated normals with [a1,b1]⊆[a2,b2] | log-partition written with Φ, minus a moment inner product | +∞ if supports do not nest; full-line supports recover the textbook univariate Gaussian KL |
| Poisson λ vs geometric p | −log p + λ log(λ/(1-p)) − λ − Eλ[log x!] | The factorial term has no simpler closed form |
Truncated-normal mean and second moment use the usual mills-ratio corrections with φ and Φ. On the full line this collapses to ½(log(s2²/s1²)+s1²/s2²+(m2−m1)²/s2²−1). A Java implementation is linked.
Centroids: the left-sided duo Bregman centroid is θL=(∇F1)^{−1}((1/n)Σ ∇F2(θi)); the right-sided centroid is always the arithmetic mean. The second fact extends Banerjee et al. 2005 from ordinary Bregman clustering to two generators.
Truncated Gaussians, half-normals, and exponential-versus-Laplace pairs show up whenever a model shares sufficient statistics but not support. The usual options were numerical integration or a one-off derivation. If the partition function is available, this paper folds those KLs into one duo Bregman expression.
As a training loss this is an incremental extension. Blondel et al. already made ordinary Fenchel-Young losses a standard tool for structured prediction; the duo variant only lets the two convex generators differ. Khan and Swaroop used duo Fenchel-Young as a change regularizer in knowledge-adaptation priors for continual learning. This paper cites that work and does not run its own downstream experiments.
The DC-programming remark gives CCCP a geometric reading. It does not improve known convergence rates.
Nielsen notes that nested exponential families are rarely studied on their own, and uses of duo divergences beyond nested statistical distances remain thin. When F1 strictly majorizes F2, the duo gap stays strictly positive even at matching natural parameters, so it is a pseudo-divergence: not a metric, and not a drop-in replacement for Bregman clustering losses.
Truncated exponential families can fail to be steep. Del Castillo's singly truncated normal is the textbook case; the moment map need not cover the mean space, and dual-coordinate conversion can stall. Reverse KL is infinite unless supports nest, so any implementation has to check support inclusion first.
There is no numerical check of closed form against Monte Carlo KL. The Φ(β)−Φ(α) term in the truncated-normal formula underflows in the tails; numerical stability is left unaddressed.