PaperlayerView exact revision on arXiv

Source-linked AI summary

Rényi Divergence and Kullback-Leibler Divergence

Tim van Erven, Peter Harremoës

arXiv:1206.2459v2cs.ITmath.STstat.ML

TL;DR

The paper addresses the scattered and often finite-alphabet treatment of Rényi divergence by systematically developing its definitions and properties across general spaces and orders. It derives results on convexity, continuity, asymptotic distribution relations, hypothesis testing, and minimax identities, including the equivalence of channel capacity and minimax redundancy for continuous channel inputs.

  • Problem

    Properties of Rényi divergence are scattered in the literature and have often been established only for finite alphabets, motivating a general reference treatment.

  • Method

    The paper extends Rényi divergence to continuous spaces and derives its convexity, continuity, asymptotic, testing, and minimax properties across orders.

  • Results

    The paper generalizes the Pythagorean inequality beyond order 1, relates order 0 to absolute continuity and mutual singularity, and extends channel-capacity/minimax-redundancy equivalence to continuous channel inputs for all orders.

  • Takeaways & Limitations

    Rényi divergence provides a unified framework connecting information measures, convergence and continuity properties, hypothesis testing, and channel minimax identities.

Abstract

from arXiv · show

Rényi divergence is related to Rényi entropy much like Kullback-Leibler divergence is related to Shannon's entropy, and comes up in many settings. It was introduced by Rényi as a measure of information that satisfies almost the same axioms as Kullback-Leibler divergence, and depends on a parameter that is called its order. In particular, the Rényi divergence of order 1 equals the Kullback-Leibler divergence. We review and extend the most important properties of Rényi divergence and Kullback-Leibler divergence, including convexity, continuity, limits of $σ$-algebras and the relation of the special order 0 to the Gaussian dichotomy and contiguity. We also show how to generalize the Pythagorean inequality to orders different from 1, and we extend the known equivalence between channel capacity and minimax redundancy to continuous channel inputs (for all orders) and present several other minimax results.

I. INTRODUCTION

The paper develops Rényi divergence as a general information-theoretic quantity related to Kullback–Leibler divergence, and consolidates its properties across general spaces and orders. It also extends results on convexity, continuity, hypothesis testing, product distributions, and channel capacity.

  • Motivation and information measures: Rényi divergence is a principal generalization of Shannon entropy and Kullback–Leibler divergence, with applications including coding, estimation, hypothesis testing, and Markov-chain convergence.Its order-1 case is Kullback–Leibler divergence, while order 0 relates to absolute continuity and contiguity and order ∞ to worst-case coding regret.
  • Definition and orders: The paper extends Rényi divergence from finite alphabets to continuous spaces through integral and discretization definitions, showing that the two definitions agree.The development also treats extended orders 0, 1, and ∞ and studies divergence as a function of its order.
  • Sequences and asymptotic relations: For α ∈ (0, 1), Rényi divergence characterizes absolute continuity and mutual singularity through order 0 and extends these relations to contiguity and entire separation.The paper also derives additivity and limiting results for product distributions and sequences.
  • Minimax identities: The paper links Rényi divergence to Chernoff information in hypothesis testing and establishes equality between channel capacity and minimax redundancy for all orders.The channel-capacity equivalence includes results for continuous channel inputs, while the outline also gives optimizer properties for finite input spaces.

II. DEFINITION OF R´ENYI DIVERGENCE

The paper defines Rényi divergence on measurable spaces using densities and distinguishes simple orders from extended orders. It also specifies conventions, measure-independence, and links to Hellinger integrals and familiar special cases.

  • Orders: Simple orders are finite α satisfying α > 0 and α ≠ 1, while 0, 1, and ∞ are extended orders.
  • Definition: Rényi divergence is defined on a measurable space using densities p and q with respect to a dominating measure µ.The Hellinger-integral form uses p^αq^(1−α), and the definition does not depend on the choice of µ.
  • Definition: The conventions 0/0 = 0 and x/0 = ∞ for x > 0 determine how zero densities enter the divergence.
  • Connections: The Hellinger integral underlying Rényi divergence is an f-divergence and connects the definition to squared Hellinger and χ2 distances.
  • Definition: For α > 1, P not absolutely continuous with respect to Q implies Dα(P∥Q) = ∞, even when the Q-integral may be finite.This follows from the paper’s conventions for the continuous-space definition.

B. Definition via Discretization for Simple Orders

The paper extends Rényi divergence from finite spaces to continuous spaces through finite-partition approximations and defines extended orders by continuity. It establishes monotonicity and continuity in the order under explicit conditions, including the relationship at α = 1.

  • Data Processing: The data processing inequality states that restricting distributions to a sub-σ-algebra cannot increase Rényi divergence.For a Markov processing from X to Y, the joint divergence is preserved before marginalization, while the induced divergence for Y is no larger.
  • Definition via Discretization for Simple Orders: Rényi divergence on continuous spaces can be arbitrarily well approximated by divergences on finite partitions.The relevant representation uses a supremum over finite partitions and also supports an equivalent construction by discretization.
  • Extended Orders: Varying the Order: At α = 1, the limiting Rényi divergence equals Kullback–Leibler divergence, with infinite value when P is not absolutely continuous with respect to Q.
  • Extended Orders: Varying the Order: Rényi divergence is nondecreasing in its order α, and it is constant across the admissible order range exactly for conditional distributions of Q on an event.
  • Extended Orders: Varying the Order: Continuity at α = 1 can fail from above when D(P∥Q) is finite but Dα(P∥Q) is infinite for every α > 1.The paper therefore defines D1 using the limit from below so it always equals Kullback–Leibler divergence.
  • Extended Orders: Varying the Order: Dα(P∥Q) is continuous in α on the set of orders where 0 ≤ α ≤ 1 or Dα(P∥Q) is finite.

III. FIXED NONNEGATIVE ORDERS

For fixed order α, the paper studies Rényi divergence as the distributions vary, covering positivity, data processing, finite-partition representations, convexity, a generalized Pythagorean inequality, and continuity.

  • III. FIXED NONNEGATIVE ORDERS: For fixed α, the paper analyzes Rényi divergence as P and Q vary across several structural properties.
  • III. FIXED NONNEGATIVE ORDERS: The section includes positivity, data processing, finite-partition representations, convexity, a generalized Pythagorean inequality, and continuity.
  • III. FIXED NONNEGATIVE ORDERS: The analysis treats the order α as fixed while varying the two distributions.

A. Positivity, Data Processing and Finite Partitions

The paper establishes positivity and data processing for Rényi divergence, including extended orders, and characterizes its convexity across orders. It also represents divergence through finite partitions and identifies order-dependent convexity limits.

  • Positivity: For α > 0, Dα(P∥Q) = 0 exactly when P = Q, whereas for α = 0 it vanishes exactly when Q ≪ P.
  • Data Processing: The data processing inequality holds for every order α ∈ [0, ∞] and every sub-σ-algebra G ⊆ F.The result extends the simple-order theorem to the extended orders.
  • Convexity: Rényi divergence is jointly convex in (P, Q) for α ∈ [0, 1], but joint convexity fails for α > 1.
  • Convexity: Rényi divergence is convex in its second argument for every order α ∈ [0, ∞] and jointly quasi-convex in both arguments for all such orders.

C. A Generalized Pythagorean Inequality

The paper generalizes the Kullback-Leibler Pythagorean inequality to Rényi divergence by replacing ordinary convexity with α-convexity and ordinary mixtures with (α, λ)-mixtures.

  • Motivation: If distributions in the convex set approach the minimum divergence to Q, the ordinary Pythagorean result implies convergence to the minimizing projection in divergence.This motivates extending the inequality beyond order 1.
  • Generalization: For α ≠ 1, Rényi divergence does not satisfy the ordinary Pythagorean inequality, motivating an alternative convexity notion.The paper defines α-convexity through closure under (α, λ)-mixtures.
  • Generalization: An α-convex set is closed under (α, λ)-mixtures, which reduce to ordinary mixtures when α = 1.The normalizing constant in the mixture definition is well defined and bounded.
  • Generalized inequality: Theorem 14 establishes Dα(P∥Q) ≥ Dα(P∥P ∗) + Dα(P ∗∥Q) for every P in an α-convex set when the α-information projection exists.At α = 1, this specializes to the standard Kullback-Leibler Pythagorean inequality.
  • Proof strategy: The proof minimizes divergence along an (α, λ)-mixture of the projection P ∗ and an arbitrary P, using convexity or concavity according to α.For α in (0, 1), the relevant inequalities reverse relative to α in (1, ∞) when taking logarithms and dividing by α − 1.

D. Continuity

The paper characterizes Rényi divergence’s continuity by order, topology, and sample-space assumptions. Positive orders are generally lower semi-continuous, while stronger continuity holds under specific conditions.

  • Continuity by order: For α > 1, Rényi divergence is lower semi-continuous, including in the topology of setwise convergence.Lower semi-continuity also extends to the extended orders 1 and ∞.
  • Continuity by order: For α ∈ (0, 1), Rényi divergence is continuous and, in total variation topology, uniformly continuous.The result applies jointly to (P, Q).
  • Relations to metrics: For α ∈ (0, 1), convergence of Dα(Pn∥Q) to zero is equivalent to convergence of Pn to Q in Hellinger distance and total variation.This connects divergence convergence with two standard distributional topologies or metrics.
  • Boundary orders: The order-zero divergence is upper semi-continuous in total variation topology, providing only a partial extension of the positive-order continuity result.The paper separately notes continuity in Q for finite sample spaces.
  • Sample-space assumptions: On a finite sample space, Dα(P∥Q) is continuous in Q under setwise convergence for every α ∈ [0, ∞].The statement holds for any fixed P.
  • Sample-space assumptions: On a Polish space, Dα(P∥Q) is lower semi-continuous jointly in (P, Q) under weak convergence for α ∈ (0, ∞].Weak-topology results depend on the topology of the sample space, so the Polish-space assumption is explicit.

E. Limits of σ-Algebras

The paper studies Rényi divergence under increasing and decreasing limits of σ-algebras. Increasing restrictions converge for all orders, while decreasing restrictions require order- and finiteness-related conditions.

  • Increasing σ-algebras: For an increasing family of σ-algebras generating F∞, Rényi divergence of the restrictions converges for every order α ∈ (0, ∞].The result applies to increasingly informative σ-algebras and their generated limit.
  • Increasing σ-algebras: The increasing-limit result does not hold for α = 0.A counterexample is given after Example 3.
  • Proof strategy: The proofs use conditional expectations, convergence theorems, lower semi-continuity, data processing, and uniform integrability.Uniform integrability is established separately for the relevant sequences of conditional expectations.
  • Decreasing σ-algebras: For a decreasing family with limit F∞, the divergence limit holds for α ∈ [0, 1) or when some restricted divergence at a finite stage is finite.The stated conditions cover the special order zero and positive orders under a finiteness assumption.
  • Decreasing σ-algebras: The decreasing-limit theorem cannot be extended to α = ∞.This is stated as an explicit scope limitation of the theorem.

F. Absolute Continuity and Mutual Singularity

At order 0, Rényi divergence characterizes absolute continuity and mutual singularity, while corresponding sequence results characterize contiguity and entire separation.

  • Order zero: D0(P∥Q) = 0 exactly when Q is absolutely continuous with respect to P, and D0(P∥Q) = ∞ exactly when P and Q are mutually singular.These properties follow from the support relation encoded by order-zero divergence.
  • Mutual singularity: P ⊥ Q is equivalent to Dα(P∥Q) = ∞ for some α ∈ [0, 1), and also to divergence infinity for all α ∈ [0, ∞].The paper states equivalent support-based conditions involving Q(p > 0).
  • Asymptotic analogues: For constant sequences Pn = P and Qn = Q, entire separation is equivalent to mutual singularity P ⊥ Q.This connects asymptotic separation with the corresponding static property.
  • Asymptotic analogues: Theorems 25 and 26 give equivalent divergence-based conditions for contiguity and entire separation of distribution sequences.These are presented as asymptotic analogues of the absolute-continuity and singularity characterizations.
  • Asymptotic analogues: The sequence equivalences continue to hold for restrictions to increasing sub-σ-algebras that generate the full σ-algebra.This follows by relating the sequence theorems to the increasing σ-algebra limit theorem.

G. Distributions on Sequences

For consistent finite-dimensional distributions, Rényi divergence converges to the divergence of the corresponding infinite product distributions for α > 0. Product additivity yields a Gaussian dichotomy and Kakutani’s generalization, while α = 0 is exceptional.

  • Consistent Distributions: Consistent finite-dimensional distributions admit an infinite-dimensional distribution with the prescribed marginals.
  • Consistent Distributions: For α > 0, Rényi divergence of consistent finite-dimensional distributions converges to the divergence of their infinite-dimensional limits.
  • Additivity: Finite additivity of Rényi divergence extends to countable additivity for product distributions at the covered orders.
  • Exceptional Order 0: At α = 0, countable additivity can fail, with product divergences remaining zero while the infinite-product divergence is infinite.
  • Gaussian Dichotomy: The Gaussian dichotomy states that two infinite Gaussian product distributions are either equivalent or mutually singular.
  • Kakutani’s Dichotomy: For α ∈ (0, 1), Kakutani’s dichotomy generalizes this result to arbitrary product distributions whose coordinate distributions are pairwise equivalent.

H. Taylor Approximation for Parametric Models

This section connects Rényi divergence to local parametric behavior, hypothesis testing, and minimax identities. It establishes concavity and Pinsker-type bounds, and interprets Rényi divergence through weighted Kullback-Leibler divergences.

  • Taylor Approximation: For regular parametric models, a second-order expansion of Kullback-Leibler divergence around θ relates local behavior to Fisher information.
  • Taylor Approximation: The corresponding generalization is stated for all α ∈ (0, ∞), although the exact parametrization conditions are not specified.
  • Hypothesis Testing: Rényi divergence appears in hypothesis-testing error bounds because (1 − α)Dα(P∥Q) is a cumulant generating function under Q.
  • Variational Representation: Rényi divergence admits a variational representation as a trade-off between two Kullback-Leibler divergences, uniquely optimized by Pα under stated finiteness conditions.
  • Concavity: The function (1 − α)Dα(P∥Q) is concave in α on [0, ∞], with conventions covering α = 1 and α = ∞.
  • Pinsker’s Inequality: Pinsker’s inequality extends from α = 1 to every α ∈ (0, 1], relating Rényi divergence to total variation distance.
  • Minimax Results: Under D(P∥Q) < ∞, a minimax identity holds, and an α∗ satisfying equal divergences to P and Q yields a saddle point.
  • Minimax Results: The minimax value is the Chernoff information, which gives an asymptotically tight bound on both type 1 and type 2 testing errors.

B. Channel Capacity and Minimax Redundancy

For finite sample spaces, the paper extends the equality between channel capacity and minimax redundancy to every Rényi order. It also characterizes redundancy-achieving distributions and relates the order-∞ case to normalized maximum likelihood.

  • For finite X, channel capacity equals minimax redundancy for every α ∈[0, ∞].
  • A redundancy-achieving distribution Qopt exists on finite sample spaces because Q ↦ supθ Dα(Pθ∥Q) is continuous and convex and attains a minimum.
  • When a capacity-achieving input πopt exists, Dα(Pθ∥Qopt) = Rα almost surely under πopt.
  • For countable X with finite R∞, the redundancy-achieving distribution is the Shtarkov distribution, provided its normalizing sum is finite.
  • The paper conjectures a unique redundancy-achieving distribution and a one-sided inequality for positive orders, but notes that Sion’s theorem generally cannot prove it because quasi-convexity may fail.
  • For α = ∞ and finite X, a maximum-likelihood selector induces a capacity-achieving input distribution from Qopt.

V. NEGATIVE ORDERS

The paper extends Rényi divergence to negative orders, where several sign, curvature, continuity, and data-processing properties reverse. Nonetheless, divergence remains nondecreasing in order and is continuous on a specified domain.

  • Skew symmetry relates negative orders to positive orders, allowing negative-order properties to be connected to orders greater than one.
  • For negative orders, Rényi divergence is nonpositive, concave in its first argument, and upper semi-continuous under setwise convergence.
  • For negative orders, the data processing inequality reverses, and the relevant supremum becomes an infimum.
  • Rényi divergence is nondecreasing in α across the full order range α ∈[−∞, ∞].
  • Dα(P∥Q) is continuous in α when 0 ≤ α ≤ 1 or |Dα(P∥Q)| < ∞.

VI. COUNTEREXAMPLES

The paper gives counterexamples showing that Rényi divergence lacks several familiar properties: continuity under setwise convergence, convexity in its first argument, and metric structure.

  • For α ∈(1, ∞), Rényi divergence is not convex in its first argument.
  • For α ∈(0, 1), Rényi divergence is not generally continuous under setwise convergence.The constructed distributions converge to the uniform distribution while their divergences remain positive rather than converging to zero.
  • Except at α = 1/2, Rényi divergence is generally asymmetric and cannot be a metric.
  • At α = 1/2, the square root of Rényi divergence still violates the triangle inequality, so the divergence is not the square of a metric.For the example distributions, D1/2(P∥Q) = ln 2, D1/2(Q∥R) = ln 2, and D1/2(P∥R) = ∞.
  • The paper’s broader conclusions include convexity and continuity results, a generalized Pythagorean inequality, and minimax identities for Rényi and Kullback-Leibler divergence.
Loading 1206.2459v2…