Source-linked AI summary
Information Measures: the Curious Case of the Binary Alphabet
Jiantao Jiao, Thomas Courtade, Albert No, Kartik Venkat, Tsachy Weissman
TL;DR
The paper examines whether several characterizations of divergence measures extend across finite alphabet sizes. It analyzes four questions about data processing, sufficiency, and membership in divergence classes. The answers differ for binary alphabets, while KL divergence remains the unique Bregman divergence that is also an f-divergence for any alphabet size.
Problem
The paper asks whether four uniqueness characterizations for divergence measures hold across finite alphabet sizes, given that larger-alphabet results may not extend to binary alphabets.
Source: §I · pp. 1–2Method
The paper analyzes the four characterization questions and uses convex analysis and functional equations for its result on Bregman divergences invariant under sufficient transformations.
Source: §I · p. 2Results
Only the Bregman-and-f-divergence uniqueness question has an affirmative answer for every alphabet size; all four questions have affirmative answers for n ≥3, while counterexamples arise at n = 2.
Source: §I · p. 1, D. QUESTION 4: Is KL divergence the… · p. 5, E. Review · p. 5Takeaways & Limitations
For binary alphabets, decomposable divergences satisfying data processing need not be f-divergences, whereas KL divergence is the unique Bregman divergence that is also an f-divergence for any alphabet size.
Source: §III · p. 4, D. QUESTION 4: Is KL divergence the… · p. 5, E. Review · p. 5
Abstract
from arXiv · showhide
Four problems related to information divergence measures defined on finite alphabets are considered. In three of the cases we consider, we illustrate a contrast which arises between the binary-alphabet and larger-alphabet settings. This is surprising in some instances, since characterizations for the larger-alphabet settings do not generalize their binary-alphabet counterparts. Specifically, we show that $f$-divergences are not the unique decomposable divergences on binary alphabets that satisfy the data processing inequality, thereby clarifying claims that have previously appeared in the literature. We also show that KL divergence is the unique Bregman divergence which is also an $f$-divergence for any alphabet size. We show that KL divergence is the unique Bregman divergence which is invariant to statistically sufficient transformations of the data, even when non-decomposable divergences are considered. Like some of the problems we consider, this result holds only when the alphabet size is at least three.
I. INTRODUCTION
The paper asks four uniqueness questions about divergence measures and finds that the answers depend on alphabet size. Only the question of whether KL divergence is the unique Bregman divergence that is also an f-divergence has an affirmative answer for every alphabet size.
I. INTRODUCTION
- Only the Bregman–f-divergence uniqueness question has an affirmative answer for every alphabet size; for n ≥3, all four questions have affirmative answers, while counterexamples arise at n = 2.The four questions concern decomposable divergences with data processing, KL-type f-distance measures with data processing, Bregman divergences satisfying sufficiency, and divergences that are both Bregman and f-divergences.Source: §I · p. 1
- The binary setting admits a richer class of divergence measures satisfying data processing than the larger-alphabet setting, contrary to the expectation that the simpler alphabet would be less rich.The paper connects this contrast to earlier results distinguishing binary from larger alphabets.Source: §I · p. 1
- The paper is motivated by the binary-versus-larger-alphabet contrast and investigates whether established characterizations extend to binary alphabets.It also highlights the result that KL divergence is the unique Bregman divergence invariant to statistically sufficient transformations for alphabet sizes of at least three, without requiring decomposability.Source: §I · p. 2
II. PRELIMINARIES: DIVERGENCES, DATA PROCESSING, AND SUFFICIENCY PROPERTIES
The preliminaries define divergence measures on finite alphabets and set out the data processing, sufficiency, and decomposability properties used in the paper. Sufficiency is a restricted form of data processing, applying to transformations that preserve a sufficient statistic.
II. PRELIMINARIES: DIVERGENCES, DATA PROCESSING, AND SUFFICIENCY PROPERTIES
- The paper considers nonnegative divergence functions between probability distributions on finite alphabets and focuses on data processing and sufficiency.The alphabet has size n, and transformations are Markov kernels with source and target equal to the alphabet.Source: §II · p. 2
- Data processing requires divergence not to increase under a transformation, while sufficiency imposes this requirement only for transformations preserving a sufficient statistic.The paper notes that sufficiency is weaker than data processing; for sufficient transformations, the defining inequality can equivalently be stated as equality.Source: §II · p. 2
- The preliminaries also introduce decomposability and identify Bregman, f-, and KL-type divergences as the classes examined in the paper.The supplied passage identifies decomposability through a bivariate function but does not provide its full formula.Source: §II · p. 3
A. Bregman Divergences
The paper reviews Bregman, f-, and KL-type f-distance divergences as the three classes central to its questions. Their definitions and basic properties set up the comparisons developed in the results.
A. Bregman Divergences
- A Bregman divergence is generated by a convex function differentiable on the relative interior of the probability simplex and is nonnegative.When its generating function has the specified coordinatewise form, the Bregman divergence is decomposable.Source: A. Bregman Divergences · p. 3
B. f-Divergences
- An f-divergence is generated by a convex function f with f(1) = 0, is nonnegative, and is decomposable.Examples include KL divergence, Hellinger distance, χ2-divergence, and total variation distance.Source: B. f-Divergences · p. 3
C. Kullback-Leibler-type f-distance measures
- For n ≥3, every KL-type f-distance measure is proportional to standard KL divergence.KL-type f-distance measures are decomposable by definition.Source: C. Kullback-Leibler-type f-distance… · p. 3
III. MAIN RESULTS
The first main-results question asks whether f-divergences are the only decomposable divergences satisfying data processing. The paper shows that this characterization fails for binary alphabets, where such counterexamples are abundant.
III. MAIN RESULTS
- The cited characterization that decomposable divergences satisfying data processing must be f-divergences applies for n ≥3, but its cited proofs do not establish it for n = 2.The paper notes that a similar proof in another cited source also fails in the binary case.Source: §III · pp. 3–4
- On binary alphabets, decomposable divergences satisfying data processing need not be f-divergences.The paper states that counterexamples are abundant and gives a binary example based on f(x) = |x − 1|.Source: §III · p. 4
- For binary alphabets, combining two f-divergences with a nonnegative function nondecreasing in each argument gives another divergence satisfying data processing.The paper describes this family as decomposable on the binary alphabet.Source: §III · p. 4
B. QUESTION 2: Is KL divergence the only KL-type f-distance measure which satisfies DATA PROCESSING?
The data-processing characterization of KL-type f-distances differs sharply by alphabet size: KL is unique up to scale for n ≥3, but binary alphabets admit broader families. For Bregman divergences satisfying sufficiency, the same size contrast holds, even without assuming decomposability.
B. QUESTION 2: Is KL divergence the only KL-type f-distance measure which satisfies DATA PROCESSING?
- For n=2, continuously differentiable generators permit a family parameterized by nonnegative, nondecreasing continuous h, with G symmetric; for n≥3, only KL up to scale remains.The theorem’s binary characterization also requires G(x) = G(1 − x) for x ∈ [1/2, 1).Source: B. QUESTION 2: Is KL divergence the… · p. 4
- A binary KL-type f-distance can satisfy data processing without being KL up to scale, so it need not be an f-divergence.The example demonstrates that even the stronger KL-type f-distance condition plus data processing does not force an f-divergence in the binary setting.Source: B. QUESTION 2: Is KL divergence the… · p. 4
C. QUESTION 3: Is KL divergence the unique Bregman divergence which satisfies SUFFICIENCY?
- For Bregman divergences satisfying sufficiency, n≥3 forces KL up to a nonnegative factor, whereas n=2 permits any divergence generated by a symmetric bivariate convex function on Γ2.The binary characterization corresponds precisely to the set of such symmetric bivariate convex functions.Source: C. QUESTION 3: Is KL divergence the… · p. 5
- The n≥3 uniqueness result assumes no decomposability, and the authors provide its first complete proof.A similar claim had appeared informally, but no proof was previously known.Source: C. QUESTION 3: Is KL divergence the… · p. 5
- On binary alphabets, a bijection between Bregman divergences and KL-type f-distances links the two theorems’ broad non-KL characterizations.The bijection follows from the Savage representation; Theorem 3 characterizes binary Bregman divergences satisfying data processing, while Theorem 4 characterizes those satisfying sufficiency.Source: C. QUESTION 3: Is KL divergence the… · p. 5
D. QUESTION 4: Is KL divergence the unique Bregman divergence which is also an f-divergence?
The paper establishes that KL divergence, up to a nonnegative factor, is the only divergence that is both Bregman and an f-divergence for every alphabet size. Its broader review contrasts several divergence characterizations for binary and larger alphabets.
D. QUESTION 4: Is KL divergence the unique Bregman divergence which is also an f-divergence?
- For every n ≥2, a divergence that is both Bregman and an f-divergence equals KL divergence up to a nonnegative multiplicative factor.This completes results previously established only for n ≥3 or in different settings.Source: D. QUESTION 4: Is KL divergence the… · p. 5
E. Review
- For n ≥3, any Bregman divergence satisfying SUFFICIENCY is KL, even without assuming decomposability.The review contrasts this with the binary case, where such Bregman divergences need not be KL.Source: E. Review · p. 5
- For binary alphabets, decomposable divergences satisfying DATA PROCESSING need not be f-divergences, and the other two characterized classes need not be KL.The review states that KL-type f-distances satisfying DATA PROCESSING and Bregman divergences satisfying SUFFICIENCY are each completely characterized in the binary case.Source: E. Review · p. 5
IV. CONCLUDING REMARKS
- The paper reports a binary-versus-larger-alphabet contrast for three questions, while the Bregman–f-divergence intersection has KL as its unique member at every alphabet size.For the sufficiency question, the larger-alphabet result applies when n > 2, but does not hold for binary alphabets.Source: §IV · pp. 5–6
APPENDIX A PROOF OF LEMMA 1
The proof studies a binary-alphabet divergence through a two-variable function and its behavior under exchanging the two alphabet elements. It concludes that the divergence is decomposable.
APPENDIX A PROOF OF LEMMA 1
- The proof represents an arbitrary binary-alphabet divergence as h(p, q) = D((p, 1 −p); (q, 1 −q)).This parametrization turns the divergence into a function of the probabilities assigned to one alphabet element.Source: Appendix A · p. 6
- Exchanging the two alphabet elements in both distributions corresponds to replacing (p, q) with (1 −p, 1 −q) in h.The proof examines whether this exchange leaves the divergence unchanged.Source: Appendix A · p. 6
- The proof concludes that the binary-alphabet divergence is decomposable.Source: Appendix A · p. 6
APPENDIX B PROOF OF THEOREM 3
The proof reduces the KL-type f-distance data-processing question to binary alphabets, then derives and characterizes a condition on the generating function’s derivative. The converse verifies that the characterized functions satisfy data processing.
APPENDIX B PROOF OF THEOREM 3
- When n ≥3, Theorem 1 reduces the proof to the binary-alphabet case.Source: Appendix B · p. 6
- For a binary channel, data processing imposes an inequality on the generating function and its derivative across input and output distributions.The proof parameterizes the channel by α and β and differentiates the inequality with respect to q.Source: Appendix B · p. 6
- The data-processing condition requires the derivative of f to have the stated representation, with h nonnegative and nondecreasing.The proof further specifies that h is continuous on (0, 1/2].Source: Appendix B · p. 7
- Conversely, any f with the characterized derivative representation generates a divergence satisfying DATA PROCESSING.Source: Appendix B · p. 7
APPENDIX C PROOF OF THEOREM 4
The proof characterizes Bregman divergences satisfying SUFFICIENCY by examining their convex generators. For n ≥3, the generator reduces to a constant multiple of negative entropy up to an additive constant, yielding KL divergence up to a nonnegative factor.
APPENDIX C PROOF OF THEOREM 4
- A Bregman divergence satisfying SUFFICIENCY can be generated by a symmetric convex function without changing the divergence.Source: Appendix C · p. 7
- For n = 2, SUFFICIENCY restricts transformations to permutations, so the proof focuses on n ≥3.Source: Appendix C · p. 7
- For n ≥3, the proof first represents a symmetric convex generator using a coefficient-weighted sum of p_i ln p_i terms and a symmetric remainder.The coefficient and remainder depend symmetrically on the remaining probability coordinates.Source: Appendix C · p. 8
- Convexity forces the generator to be a nonnegative multiple of Σ_i p_i ln p_i plus a constant, so its Bregman divergence is a nonnegative multiple of KL.Source: Appendix C · p. 9
APPENDIX D PROOF OF THEOREM 5
The proof restricts the divergence to a binary support and uses convexity to characterize f on either side of 1; equation (93) forces the two branch coefficients to agree.
APPENDIX D PROOF OF THEOREM 5
- For x ≥ 1, convexity and the derivative relation yield f(x) = a+ · (x ln x − x + 1) + f′(1)(x − 1).Source: Appendix D · p. 10
- For x < 1, the corresponding form is f(x) = a− · (x ln x − x + 1) + f′(1)(x − 1).Source: Appendix D · p. 10
- Substituting these forms into equation (93) gives a+ = a−, after which the proof substitutes the common form into the definition of an f-divergence.Source: Appendix D · p. 10