PaperlayerView exact revision on arXiv

Source-linked AI summary

$f$-divergence Inequalities

Igal Sason, Sergio Verdú

arXiv:1508.00335v7cs.ITmath.PR

TL;DR

The paper addresses how to derive systematic inequalities among f-divergences for arbitrary pairs of probability measures. It combines functional domination, bounded-relative-information arguments, and integral representations, obtaining bounds involving total variation, Eγ divergence, and Rényi divergence.

  • Problem

    The paper studies systematic relationships and bounds among f-divergences, including cases where total variation does not generally control relative entropy.

  • Method

    It uses functional domination, bounded relative-information techniques, and integral representations involving Eγ divergence and the relative information spectrum.

  • Results

    The paper obtains bounds on total variation, relative entropy, Eγ divergence, and Rényi divergence, with Eγ pairs uniquely determining relative entropy and twice-differentiable f-divergences.

  • Takeaways & Limitations

    The resulting representations and inequalities transfer bounds among important f-divergences and extend Pinsker-type relationships to Eγ divergence and the relative information spectrum.

Abstract

from arXiv · show

This paper develops systematic approaches to obtain $f$-divergence inequalities, dealing with pairs of probability measures defined on arbitrary alphabets. Functional domination is one such approach, where special emphasis is placed on finding the best possible constant upper bounding a ratio of $f$-divergences. Another approach used for the derivation of bounds among $f$-divergences relies on moment inequalities and the logarithmic-convexity property, which results in tight bounds on the relative entropy and Bhattacharyya distance in terms of $χ^2$ divergences. A rich variety of bounds are shown to hold under boundedness assumptions on the relative information. Special attention is devoted to the total variation distance and its relation to the relative information and relative entropy, including "reverse Pinsker inequalities," as well as on the $E_γ$ divergence, which generalizes the total variation distance. Pinsker's inequality is extended for this type of $f$-divergence, a result which leads to an inequality linking the relative entropy and relative information spectrum. Integral expressions of the Rényi divergence in terms of the relative information spectrum are derived, leading to bounds on the Rényi divergence in terms of either the variational distance or relative entropy.

I. INTRODUCTION

The paper develops systematic inequalities among f-divergences for probability measures, using functional domination, bounded relative information, and integral representations. It emphasizes optimal constants, total variation, reverse Pinsker inequalities, Eγ divergence, and Rényi divergence.

  • Functional domination: Functional domination derives bounds among f-divergences and, under mild regularity conditions, establishes optimality of their constants.The paper also gives cases where optimality holds without regularity conditions.
  • Functional domination: The approach yields relationships among relative entropy, Hellinger divergence, and total variation distance, including maximal ratios relative to total variation.It also strengthens and provides an alternative proof of Samson’s inequality.
  • Bounded relative information: With relative information bounded almost surely, the paper bounds ratios of f-divergences and derives strengthened Jensen-type inequalities and a reverse Samson inequality.Examples include ratios involving relative entropy and the non-negative difference between forward and reverse relative entropies.
  • Total variation and reverse Pinsker inequalities: The paper derives identities linking total variation to the relative information spectrum, producing bounds that can be tighter than Pinsker’s inequality in some parameter ranges.It also gives refined bounds on relative entropy using χ^2-divergences and total variation.
  • Total variation and reverse Pinsker inequalities: Reverse Pinsker inequalities lower-bound total variation as a function of relative entropy under bounded relative information, Lipschitz, or minimum-probability conditions.The introduction motivates these constraints because total variation alone cannot generally upper-bound relative entropy.
  • Eγ and Rényi divergence: Integral representations express f-divergences through Eγ divergence and Rényi divergence through the relative information spectrum, yielding bounds in terms of variational distance or relative entropy.The pair of Eγ divergences uniquely determines relative entropy, Rényi divergence, and twice-differentiable f-divergences.

C. R´enyi Divergence

The section defines Rényi divergence and relates it to Hellinger divergence, while developing functional-domination tools for tight f-divergence inequalities under differentiability conditions.

  • Definition and basic properties: Rényi divergence of order α≥0 is defined for P≪Q, with a separate convention at α=0 based on the limit α↓0.The paper notes that this convention differs from Rényi’s original definition at order zero.
  • Definition and basic properties: For α∈(0,1)∪(1,∞), Rényi divergence is a one-to-one transformation of the Hellinger divergence of the same order.The transformation is given explicitly by D_α(P∥Q) = 1/(α−1) log(1 + (α−1)H_α(P∥Q)).
  • Definition and basic properties: Monotonicity of Rényi divergence in its order yields several stated bounds, including the order-2 specialization of the Hellinger relation.The section also identifies the order-2 case as a useful particularization.
  • Functional domination: Functional domination bounds one f-divergence by another when f(t)≤αg(t) for all t>0, with the best ratio controlled by the supremum of f(t)/g(t).The construction uses parametric probability measures to show sharpness of the ratio bound.
  • Functional domination: The general domination result requires differentiability at t=1, although one-sided derivative conditions can suffice when the ratio supremum lies on one side of 1.Without the relevant derivative condition, the bound need not hold.

B. Relationships Among D(P∥Q), χ2(P∥Q) and |P −Q|

The section derives relationships among relative entropy, χ^2 divergences, total variation, and related distances, emphasizing explicit and often optimal constants.

  • χ^2 and total variation: χ2(P∥Q)+χ2(Q∥P)≥2|P−Q|^2, with the same small-distance behavior as a stronger stated inequality.The paper also discusses sharpenings and bounds involving relative entropy under boundedness assumptions.
  • Vincze-Le Cam distance: The Vincze-Le Cam distance admits three upper bounds in terms of relative entropy, and the constant in one bound is optimal.For one displayed bound, the optimal constant is c2=0.0374250, attained at t⋆=0.122463.
  • Constant trade-offs: The allowable constant pairs for combining relative entropy and total variation form a convex region symmetric about c1=c2, with boundary nearly a line of slope −1.The section identifies boundary points including (1.11591,0) and (0,1.11591).
  • Relative entropy and distance bounds: 2(P,Q)+d2^2(Q,P)≤2 log e D(P∥Q), and the constant 2 log e is optimal.The supremum of the ratio is 2 log e over distinct mutually absolutely continuous probability measures.
  • Relative entropy and distance bounds: Under bounded relative information, a reverse inequality to the preceding bound can also be derived.The passage states this as a consequence of adapting the proof, but does not display the complete reverse bound.
  • f-divergence and total variation: For f-divergences relative to total variation, explicit bounds are available for |P−Q|<1, and the associated constant is explicit and best possible.The range result is attainable by suitable probability measures, while the sharper bound supersedes a general endpoint expression when |P−Q|<1.

IV. BOUNDED RELATIVE INFORMATION

The section derives f-divergence bounds under upper and/or lower bounds on relative information, emphasizing optimal constants and applications to entropy-related divergences. It also extends these results to Rényi and Hellinger divergences.

  • Relative entropy: Bounds on the ratio of relative entropies follow as an application of Theorem 6.Theorem 7 specializes the framework to mutually absolutely continuous, distinct measures with (β1, β2) ∈ (0, 1)2.
  • Refined bounds: Theorem 10 refines upper bounds involving total variation, Jensen–Shannon, and triangular discrimination divergences.Its upper bounds are sharper than earlier bounds when β1 > 0, while the β1 = 0 case corresponds to unbounded relative information.
  • General alphabets: Theorem 11 extends Hellinger-divergence bounds to arbitrary alphabets and arbitrary orders α ∈ (0, ∞), while improving prior bounds in specified cases.The section also notes that the constants from Theorem 6 remain best possible under the stated parameterization.

G. Local Behavior of f-Divergences

This section characterizes the local behavior of f-divergences as probability measures approach one another under a strong convergence condition. It shows that several divergences vanish together and that their ratios have controlled limiting behavior.

  • G. Local Behavior of f-Divergences: Local behavior of f-divergences differs by only a constant under the section’s convergence condition.The result compares divergences through their behavior near the reference measure.
  • G. Local Behavior of f-Divergences: The convergence condition requires Pn ≪ Q for all sufficiently large n and a strong approach of Pn to Q.For finite alphabets, it is equivalent to total variation convergence when Q has positive mass everywhere.
  • G. Local Behavior of f-Divergences: Relative entropy in both directions vanishes when Pn converges to Q in the sense of (206).This is stated for D(Pn∥Q) and D(Q∥Pn).
  • G. Local Behavior of f-Divergences: Both χ2(Pn∥Q) and D(Pn∥Q) vanish under the same convergence condition.The result is presented as a separate corollary for these two divergences.

H. Strengthened Jensen’s inequality

The section strengthens Jensen’s inequality using a random transformation and applies the resulting lemma to f-divergence and relative-information identities. It then derives exact and tight bounds for total variation through the relative information spectrum.

  • H. Strengthened Jensen’s inequality: Lemma 1 provides a strengthened Jensen inequality for P1 ≪ P0 and an arbitrary random transformation.The proof reduces boundary cases to Jensen’s inequality or the trivial equality P0 = P1.
  • H. Strengthened Jensen’s inequality: Theorem 13 applies the lemma to convex functions with f(1) = 0, yielding f-divergence inequalities.Choosing f(t) = −log t sharpens a prior inequality under bounded relative information.
  • Total variation and relative information: Theorem 15 gives several exact expressions for total variation distance in terms of the relative information spectrum.For P ≪ Q, the supremum defining total variation is attained as a maximum.
  • Upper bounds: Theorem 18 supplies two upper bounds on total variation that are attainable by suitable binary-alphabet probability measures.The bounds use spectrum probabilities and are parameterized by β0 ∈ [β1, 1].
  • Lower bounds: Theorem 21 provides a lower bound on total variation from the distribution of relative information, with equality under binary-alphabet conditions.The result is presented as a strengthened counterpart to earlier lower bounds.

D. Relative Entropy and Bhattacharyya Distance

This section develops moment-inequality and log-convexity bounds for relative entropy and Bhattacharyya distance. The bounds can be tight under convergence conditions and extend across general alphabets and divergence orders.

  • D. Relative Entropy and Bhattacharyya Distance: Moment inequalities refine bounds on relative entropy in terms of χ2(P∥Q).The refined upper-bound ratio tends to 1, whereas the ratio for the looser bound in (5) tends to 2.
  • D. Relative Entropy and Bhattacharyya Distance: The paper uses log-convexity of λα in α to derive bounds on the Bhattacharyya distance from χ2 divergences and relative entropy.The resulting bounds are stated in Theorem 25.
  • D. Relative Entropy and Bhattacharyya Distance: Both upper bounds in (292) and (304) are tight under the same convergence condition, while (292) depends only on χ2-divergences.The paper distinguishes this tightness statement from the lower-bound result in (307).
  • D. Relative Entropy and Bhattacharyya Distance: The lower relative-entropy bound in (307) is asymptotically tight when Pn converges to Q in the sense of (206).The ratio of D(Pn∥Q) to this lower bound tends to 1, strengthening the sufficient tightness condition from earlier work.

VI. REVERSE PINSKER INEQUALITIES

The section develops reverse Pinsker inequalities that upper-bound relative entropy using total variation or related information about the pair of measures. The bounds require additional structure, such as bounded relative information or density constraints.

  • Motivation: Arbitrarily small total variation can coexist with arbitrarily large finite relative entropy, so D(P∥Q) alone cannot lower-bound |P−Q|.Consequently, the section’s bounds incorporate another feature of (P,Q).
  • Method: Bounds on relative entropy are obtained using bounded relative information and properties of an auxiliary function ϕ.The proof uses monotonicity, non-negativity, concavity, and differentiability of ϕ in successive refinements.
  • Results: The refined bounds improve earlier inequalities, including a reverse Pinsker inequality that is stronger by at least a factor of 2.The section also notes improvements involving the coefficient of |P−Q| and tightened bounds derived from additional properties of ϕ.
  • Results: The resulting inequalities include upper bounds on D(P∥Q) in terms of total variation under suitable boundedness or Lipschitz conditions.Theorem 27 extends an earlier bound to the non-discrete setting for continuous convex f satisfying the stated regularity conditions.

C. Finite Alphabet

For finite alphabets, the paper derives strengthened reverse Pinsker and entropy–variation bounds, then characterizes the exact feasible region relating entropy to distance from uniformity. It also connects these results to typicality and prior bounds.

  • Reverse Pinsker bounds: Finite-alphabet reverse Pinsker bounds assume a common finite alphabet and exploit positivity or lower bounds on Q’s probabilities.Several refinements depend on Q_min or mutual absolute continuity.
  • Reverse Pinsker bounds: The strengthened bounds improve earlier results by at least a factor of 2 and yield corresponding improvements for a strong data processing inequality constant.The comparison is stated for finite-alphabet bounds and their downstream application.
  • Entropy and uniformity: Theorem 29 determines the exact locus of (H(P), |P−U|) for probability measures on a finite alphabet and compares it with analytic upper and lower bounds.Here U is the equiprobable distribution, and Figure 2 illustrates the locus and bounds for alphabet sizes 4 and 256.
  • Typicality: Sanov’s theorem identifies relative entropy as the exponential decay exponent for empirical distributions that are not strongly δ-typical.The typicality set consists of distributions δ-close to Q in total variation.

A. Basic Properties

The paper studies the E_γ divergence as a generalized total variation measure, establishes its relations to statistical information and other f-divergences, and derives an optimized Pinsker-type bound. The bound’s constant decreases with γ and has stated limitations.

  • Basic properties: E_γ divergence generalizes total variation but, for γ>1, E_γ(P∥Q)=0 does not imply P=Q.This follows because the defining function is not strictly convex at t=1.
  • Basic properties: The E_γ divergence is monotone in γ and admits representations involving likelihood ratios and DeGroot statistical information.The representation uses the Neyman–Pearson lemma, and γ=1 recovers total variation-related identities.
  • Integral representations: A twice-differentiable convex f-divergence is represented through an integral involving the E_γ family, so E_γ bounds transfer to other f-divergences.The representation uniquely determines relative entropy, Hellinger, Rényi, and other twice-differentiable f-divergences.
  • Limitation: No general lower bound on E_γ(P∥Q) in terms of relative entropy exists for γ>1.The paper points to a binary example demonstrating this impossibility.
  • Extended Pinsker inequality: c_γ decreases with γ, while c_γ diverges as γ approaches 1 from above; this is consistent with the distinct behavior of E_γ and total variation.At γ=1, the bound reduces to Pinsker’s inequality with no tighter constant.
  • Extended Pinsker inequality: Theorem 33 replaces a prior coefficient with the universal constant c_γ, yielding a tighter upper bound on E_γ(P∥Q) in terms of relative entropy.The constant is optimal, can be approximated with relative error below 1% for γ>1, and is below the earlier comparison coefficient.

VIII. R´ENYI DIVERGENCE

The Rényi-divergence section derives integral representations through the relative information spectrum and uses them to bound Rényi and Hellinger divergences. It also exploits logarithmic convexity and total variation constraints.

  • Spectrum representations: Integral expressions represent Rényi divergence in terms of the relative information spectrum, under boundedness assumptions on relative information.These expressions are then used to derive bounds involving variational distance or relative entropy.
  • Spectrum representations: The paper derives corresponding integral representations for Hellinger divergence from the relationship between Rényi and Hellinger divergences.The resulting corollary covers α∈(0,1)∪(1,∞) when the lower relative-information bound is positive.
  • Order properties: The normalized Hellinger divergence is log-convex in its order, alongside monotonicity properties established for Hellinger divergence.The proof invokes moment inequalities for non-negative random variables.
  • Bounds from total variation: The resulting Rényi bounds recover the relative-entropy bound as α approaches 1 and are asymptotically tight in stated limits.The paper also notes coincidence or asymptotic agreement among alternative bounds for α approaching 0 or infinity.

C. Bounds as a Function of the Relative Entropy

The section develops upper and lower bounds on Rényi divergence for arbitrary orders, characterizes their tightness, and situates them within systematic approaches to f-divergence inequalities.

  • C. Bounds as a Function of the Relative Entropy: The constants uα(β1) and uα(β2) in the bounds are best possible among probability measures with the specified (β1, β2).The subsequent remarks address tightness of the relevant bounds.
  • C. Bounds as a Function of the Relative Entropy: As ε →0, the ratio of the upper to lower bounds in Parts a) and b) converges to 1.This establishes asymptotic tightness for the binary constructions considered in the remarks.
  • C. Bounds as a Function of the Relative Entropy: For α ∈(0, 1), the limiting ratio of Dα(P∥Q) to the left side of (512) is α log2(2/(2−α)), lying between 1 and loge(4).The ratio approaches 1 as α →1 and loge(4) as α →0.
  • C. Bounds as a Function of the Relative Entropy: For α ∈(1, ∞), the ratio of Dα(P∥Q) to the right side of (515) tends to 1 as ε →0.The proof assembles the relevant limiting relations for α > 1.
  • C. Bounds as a Function of the Relative Entropy: Theorem 38 provides bounds for Dα(P∥Q): (513) for α ∈(0, 1), (515) for α ∈[1, 2.57], and (516) for α > 2.57.These bounds use parameters β1, β2 and the function uα.
  • C. Bounds as a Function of the Relative Entropy: The paper proposes systematic approaches including functional domination, moment inequalities, logarithmic convexity, bounded relative information, and Lipschitz constraints.It also derives inequalities through Eγ representations, an Eγ extension of Pinsker’s inequality, relative-information relations, and Rényi-spectrum expressions.

APPENDIX A

The appendix completes technical proofs by establishing monotonicity properties of auxiliary functions and deriving related identities through calculus, continuity, change of measure, and integral representations.

  • APPENDIX A: The function κ is a continuous extension with κ(1) = 1 and is strictly monotonically increasing.The proof reduces this property to positivity of an auxiliary expression after substituting t = exp(x).
  • APPENDIX A: The function κα is monotonically increasing on [0, ∞] for α ∈(0, 1) and monotonically decreasing for α ∈(1, ∞).The proof establishes corresponding monotonicity of φα on intervals below and above 1.
  • APPENDIX A: Additional proofs derive relations involving relative information and total variation by change of measure, symmetry, anti-symmetry, and complementary cumulative distribution functions.The arguments assume absolute continuity where required and use nonnegative random-variable expectations as integrals.

APPENDIX E

The appendix derives tightened relative-entropy bounds, characterizes their small-η scaling, and analyzes entropy extrema under total-variation constraints.

  • APPENDIX E: When β2 is replaced by zero, inequalities (332) and (344) coincide.The parameter β2 represents information about the infimum of the relative density.
  • APPENDIX E: For small η, the tightened upper bound in (616) scales like η^2, while the bound in (617) scales like η.The η^2 scaling is stated to be tight according to Pinsker’s inequality.
  • APPENDIX E: The upper and lower bounds in (616) and (622) have ratio 2 and both provide the true quadratic scaling in η for η ≈0.The weaker upper bound in (617) remains linear in η in this regime.
  • APPENDIX E: The tighter relative-entropy bound results from combining a concavity-based improvement for ϕ(Z) with existing bounds.This improves the upper bound compared with (332).
  • APPENDIX E: The appendix uses entropy concavity and H(P) = log |A| − D(P∥U) to characterize the solution for the entropy optimization.The minimizing measure is related to a general result for fixed-distribution total-variation constraints.
  • APPENDIX E: Maximizing entropy at a fixed positive total variation distance from the equiprobable distribution reduces to distributions with two distinct mass values.The remaining optimization determines the number of masses taking the larger value.
Loading 1508.00335v7…