Rényi Divergence and Kullback-Leibler Divergence

Tim van ErvenPeter Harremoës

article2012IEEE Transactions on Information Theory1,586 citations

Develops a rigorous foundation for Rényi divergence by establishing its essential analytic properties, generalizing the Pythagorean inequality to arbitrary orders, and extending channel capacity and minimax redundancy equivalences to continuous inputs.

Listen

Modern data science, statistical modeling, and communications engineering rely heavily on measuring how much probability distributions differ from one another. While standard tools like Shannon entropy and Kullback-Leibler divergence are widely used, many advanced applications—such as data compression, hypothesis testing, machine learning convergence proofs, and image ranking—require more flexible information measures. The family of Rényi divergences provides this flexibility via an adjustable order parameter, but its mathematical properties have historically been scattered across literature and largely restricted to simple, finite settings.

The article systematically evaluates and extends the mathematical properties of Rényi divergence across general continuous spaces and all parameter orders, unifying it with classical Kullback-Leibler divergence. The authors conduct a rigorous theoretical analysis using measure-theoretic probability, continuous approximations, and minimax optimization principles to establish a single, comprehensive reference.

The analysis establishes several foundational findings. First, Rényi divergence on continuous spaces can be fully recovered by taking approximations over increasingly fine finite partitions, and it increases monotonically and continuously with its order parameter. Second, while classical joint convexity holds for orders between 0 and 1, it breaks down for orders greater than 1; however, convexity in the second argument and joint quasi-convexity hold across all orders. Third, the article generalizes the fundamental Pythagorean inequality to arbitrary positive orders by introducing a modified concept of distribution mixing. Fourth, the authors prove that channel capacity strictly equals minimax redundancy for all orders on finite alphabets, even when channel inputs are continuous. Finally, the work links the extreme order of zero to probability singularity and the Gaussian dichotomy, while establishing that negative orders invert many standard mathematical properties.

These findings provide immediate practical clarity for researchers and technical leaders designing statistical estimators, robust communications channels, and compression algorithms. By mapping out exactly where convexity, continuity, and geometric projections hold or fail, the article defines the precise operational boundaries for using Rényi measures. It prevents practitioner errors—such as assuming convexity or metric distance properties where they do not exist—and strengthens the theoretical backing for convergence proofs in statistical machine learning.

Organizations and research teams working on information-theoretic modeling should update their algorithmic frameworks to leverage the generalized Pythagorean inequality and unified minimax identities established in the article. For operational decisions involving minimax redundancy, practitioners can confidently use the proven equivalence to channel capacity. Because the general version of the redundancy conjecture remains open for positive orders, teams requiring guaranteed bounds should treat that specific result as a conjecture until formal verification is complete, while relying safely on the proven countable and finite cases.

Copenhagen Business College Université Paris-Sud channel capacity gaussians mutual informations Rényi divergence Kullback-Leibler divergence relative entropy

arXiv: 1206.2459

Paper: Clustering with Bregman Divergences, Arindam Banerjee et al. (2005). It provides essential foundational background on statistical divergences, information geometry properties, and the role of Kullback-Leibler divergence in convex optimization and rate-distortion theory.
Paper: Algorithms for Non-negative Matrix Factorization, Daniel D. Lee et al. (2000). It introduces standard convex formulations and optimization procedures under the generalized Kullback-Leibler divergence.
Paper: The information bottleneck method, Naftali Tishby et al. (2000). It establishes key information-theoretic foundations connecting Kullback-Leibler divergence, mutual information, and variational optimization.

Paper: f-GAN: Training Generative Neural Samplers using Variational Divergence Minimization, Sebastian Nowozin et al. (2016). It generalizes generative adversarial network objectives to arbitrary statistical divergences, directly applying the properties of f-divergences and Kullback-Leibler divergence studied in the source.
Paper: Learning deep representations by mutual information estimation and maximization, R. Devon Hjelm et al. (2018). It uses variational estimators of divergence and mutual information to optimize deep representation learning architectures.
Paper: Fixing a Broken ELBO, Alexander A. Alemi et al. (2018). It analyzes variational lower bounds in latent variable models through the lens of mutual information and divergence-based rate-distortion trade-offs.
Paper: Variational Inference with Normalizing Flows, Danilo Jimenez Rezende et al. (2015). It leverages flexible density transformations to minimize Kullback-Leibler divergence in variational inference.
Paper: Normalizing Flows for Probabilistic Modeling and Inference, George Papamakarios et al. (2019). It provides a comprehensive treatment of probability transformations and continuous change-of-variables optimized via divergence minimization.
Paper: Contrastive Representation Distillation, Yonglong Tian et al. (2020). It evaluates the limitations of classical Kullback-Leibler divergence minimization in representation distillation and proposes contrastive alternatives.
Paper: Computational Optimal Transport, Gabriel Peyré et al. (2018). It explores computational probability metrics and entropic regularization, connecting statistical divergences to optimal transport geometry.

Cover for Rényi Divergence and Kullback-Leibler Divergence

Abstract

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 $\sigma$ -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.

Topics

channel capacity gaussians mutual informations

Keywords

Rényi divergence Kullback-Leibler divergence relative entropy power divergences total variation distance Fisher information channel capacity mutual information minimax theorem

I Introduction
I-A Rényi’s Information Measures
I-B Special Orders
I-C Outline
II Definition of Rényi divergence
II-A Definition by Formula for Simple Orders
II-B Definition via Discretization for Simple Orders
II-C Extended Orders: Varying the Order
III Fixed Nonnegative Orders
III-A Positivity, Data Processing and Finite Partitions
III-B Convexity
III-C A Generalized Pythagorean Inequality
III-D Continuity
III-E Limits of σ\sigma-Algebras
III-F Absolute Continuity and Mutual Singularity
III-G Distributions on Sequences
III-H Taylor Approximation for Parametric Models
IV Minimax results
IV-A Hypothesis Testing and Chernoff Information
IV-B Channel Capacity and Minimax Redundancy
V Negative Orders
VI Counterexamples
VI-A Convexity in PP does not hold for α>1\alpha>1
VI-B Rényi divergence is not continuous
VI-C Not a metric
VII Summary
References

Knowls

Knowl 1 — Generalized Pythagorean Inequality for alpha-Convex Sets
theoretical result
Let $\alpha \in (0, \infty)$ . A set of probability distributions $\mathcal{P}$ on a measurable space $(\mathcal{X}, \mathcal{F})$ is called $\alpha$ -convex if for every pair $P_1, P_2 \in \mathcal{P}$ and any mixture parameter $\lambda = (\lambda_1, \lambda_2)$ with $\lambda_1, \lambda_2 \ge 0, \lambda_1 + \lambda_2 = 1$ , the $(\alpha, \lambda)$ -mixture $P_\lambda$ defined by the density

$p_\lambda = \frac{(\lambda_1 p_1^\alpha + \lambda_2 p_2^\alpha)^{1/\alpha}}{\int_\mathcal{X} (\lambda_1 p_1^\alpha + \lambda_2 p_2^\alpha)^{1/\alpha} \, d\mu}$

also belongs to $\mathcal{P}$ (where $\mu$ is any common dominating $\sigma$ -finite measure).

Let $Q$ be an arbitrary probability distribution on $(\mathcal{X}, \mathcal{F})$ . If the $\alpha$ -information projection

$P^* = \arg\min_{P \in \mathcal{P}} D_\alpha(P \parallel Q)$

exists, then for all distributions $P \in \mathcal{P}$ , the generalized Pythagorean inequality holds:

$D_\alpha(P \parallel Q) \ge D_\alpha(P \parallel P^*) + D_\alpha(P^* \parallel Q).$
Knowl 2 — Variational Representation of Renyi Divergence via Kullback-Leibler Divergence
theoretical result
For any simple order $\alpha \in (0, 1) \cup (1, \infty)$ and probability distributions $P, Q$ on a measurable space $(\mathcal{X}, \mathcal{F})$ , the Rényi divergence $D_\alpha(P \parallel Q)$ satisfies the variational identity

$(1 - \alpha) D_\alpha(P \parallel Q) = \inf_R \{ \alpha D(R \parallel P) + (1 - \alpha) D(R \parallel Q) \},$

where the infimum is taken over all probability distributions $R$ on $(\mathcal{X}, \mathcal{F})$ , and $D(\cdot \parallel \cdot)$ denotes the Kullback-Leibler divergence (with the convention that $\alpha D(R \parallel P) + (1 - \alpha) D(R \parallel Q) = \infty$ if undefined).

Furthermore, if the tilted distribution $P_\alpha$ with density

$p_\alpha = \frac{p^\alpha q^{1-\alpha}}{\int_\mathcal{X} p^\alpha q^{1-\alpha} \, d\mu}$

is well defined (i.e., $0 < \int p^\alpha q^{1-\alpha} \, d\mu < \infty$ ) and either $\alpha \in (0, 1)$ or $D(P_\alpha \parallel P) < \infty$ , then the infimum over $R$ is uniquely attained by $R = P_\alpha$ .
Knowl 3 — Minimax Characterization of Chernoff Information
theoretical result
Let $P$ and $Q$ be probability distributions on $(\mathcal{X}, \mathcal{F})$ such that $D(P \parallel Q) < \infty$ . The Chernoff information satisfies the minimax identity:

$\sup_{\alpha \in (0, \infty)} \inf_R \{ \alpha D(R \parallel P) + (1 - \alpha) D(R \parallel Q) \} = \inf_R \sup_{\alpha \in (0, \infty)} \{ \alpha D(R \parallel P) + (1 - \alpha) D(R \parallel Q) \},$

where $R$ ranges over all probability distributions on $(\mathcal{X}, \mathcal{F})$ . The equality remains valid if the left-hand supremum over $\alpha$ is restricted to the open interval $(0, 1)$ .

If there exists an order $\alpha^* \in (0, 1)$ such that $D(P_{\alpha^*} \parallel P) = D(P_{\alpha^*} \parallel Q)$ , where $P_{\alpha^*}$ has density proportional to $p^{\alpha^*} q^{1-\alpha^*}$ , then $(\alpha^*, P_{\alpha^*})$ is a saddle-point, and both sides of the minimax identity equal:

$(1 - \alpha^*) D_{\alpha^*}(P \parallel Q) = \sup_{\alpha \in (0, 1)} (1 - \alpha) D_\alpha(P \parallel Q) = D(P_{\alpha^*} \parallel P) = D(P_{\alpha^*} \parallel Q).$
Knowl 4 — Equivalence of Generalized Channel Capacity and Minimax Redundancy
theoretical result
Let $\{P_\theta \mid \theta \in \Theta\}$ be a non-empty family of probability distributions on a finite sample space $\mathcal{X}$ . For any order $\alpha \in [0, \infty]$ , the generalized channel capacity $C_\alpha$ equals the minimax redundancy $R_\alpha$ :

$C_\alpha \equiv \sup_\pi \inf_Q \int_\Theta D_\alpha(P_\theta \parallel Q) \, d\pi(\theta) = \inf_Q \sup_{\theta \in \Theta} D_\alpha(P_\theta \parallel Q) \equiv R_\alpha,$

where $\pi$ ranges over Borel probability measures on the parameter space $\Theta$ , and $Q$ ranges over probability distributions on $\mathcal{X}$ .

Key properties include:
- If $\mathcal{X}$ has $n$ elements, then $C_\alpha = R_\alpha \le \ln n$ for all $\alpha \in [0, \infty]$ .
- There always exists a redundancy-achieving output distribution $Q_{\text{opt}}$ satisfying $\sup_{\theta} D_\alpha(P_\theta \parallel Q_{\text{opt}}) = R_\alpha$ .
- If there exists a capacity-achieving input distribution $\pi_{\text{opt}}$ satisfying $\inf_Q \int D_\alpha(P_\theta \parallel Q) \, d\pi_{\text{opt}}(\theta) = C_\alpha$ , then the integral $\int D_\alpha(P_\theta \parallel Q) \, d\pi_{\text{opt}}(\theta)$ is minimized at $Q = Q_{\text{opt}}$ , and $D_\alpha(P_\theta \parallel Q_{\text{opt}}) = R_\alpha$ holds almost surely for $\theta \sim \pi_{\text{opt}}$ .
Knowl 5 — Definition of Renyi Divergence on General Measurable Spaces
definition
Let $P$ and $Q$ be probability distributions on a measurable space $(\mathcal{X}, \mathcal{F})$ with Radon-Nikodym densities $p = dP/d\mu$ and $q = dQ/d\mu$ with respect to an arbitrary dominating $\sigma$ -finite measure $\mu$ .
- For simple orders $\alpha \in (0, 1) \cup (1, \infty)$ , the Rényi divergence of order $\alpha$ of $P$ from $Q$ is defined as:
$D_\alpha(P \parallel Q) = \frac{1}{\alpha - 1} \ln \int_\mathcal{X} p^\alpha q^{1-\alpha} \, d\mu,$

with conventions for $\alpha > 1$ that $p^\alpha q^{1-\alpha} = p^\alpha / q^{\alpha-1}$ , $0/0 = 0$ , and $x/0 = \infty$ for $x > 0$ .
- For extended orders $\alpha \in \{0, 1, \infty\}$ , defined by continuity limits:
  - Order $0$ : $D_0(P \parallel Q) = \lim_{\alpha \downarrow 0} D_\alpha(P \parallel Q) = -\ln Q(\{x \in \mathcal{X} \mid p(x) > 0\})$ .
  - Order $1$ : $D_1(P \parallel Q) = \lim_{\alpha \uparrow 1} D_\alpha(P \parallel Q) = D(P \parallel Q) = \int_\mathcal{X} p \ln(p/q) \, d\mu$ (Kullback-Leibler divergence).
  - Order $\infty$ : $D_\infty(P \parallel Q) = \lim_{\alpha \uparrow \infty} D_\alpha(P \parallel Q) = \ln \left(\operatorname{ess\,sup}_P \frac{p}{q}\right) = \ln \sup_{A \in \mathcal{F}} \frac{P(A)}{Q(A)}$ .
- For negative orders $\alpha \in (-\infty, 0)$ , $D_\alpha(P \parallel Q) = \frac{1}{\alpha - 1} \ln \int_\mathcal{X} q^{1-\alpha} p^{-\alpha} \, d\mu$ , and for $\alpha = -\infty$ , $D_{-\infty}(P \parallel Q) = \lim_{\alpha \to -\infty} D_\alpha(P \parallel Q) = \ln \operatorname{ess\,inf}_Q (p/q)$ .
Knowl 6 — Convexity and Quasi-Convexity of Renyi Divergence
theoretical result
Let $P_0, P_1, Q_0, Q_1$ be probability distributions on $(\mathcal{X}, \mathcal{F})$ , and $\lambda \in (0, 1)$ . The convexity properties of $D_\alpha(P \parallel Q)$ depend on the order $\alpha$ :
- Joint Convexity: For $\alpha \in [0, 1]$ , Rényi divergence is jointly convex in its arguments:
$D_\alpha((1 - \lambda)P_0 + \lambda P_1 \parallel (1 - \lambda)Q_0 + \lambda Q_1) \le (1 - \lambda) D_\alpha(P_0 \parallel Q_0) + \lambda D_\alpha(P_1 \parallel Q_1).$

Joint convexity does not hold for any $\alpha > 1$ .
- Convexity in the Second Argument: For all $\alpha \in [0, \infty]$ , Rényi divergence is convex in its second argument:
$D_\alpha(P \parallel (1 - \lambda)Q_0 + \lambda Q_1) \le (1 - \lambda) D_\alpha(P \parallel Q_0) + \lambda D_\alpha(P \parallel Q_1).$
- Joint Quasi-Convexity: For all $\alpha \in [0, \infty]$ , Rényi divergence is jointly quasi-convex in its arguments:
$D_\alpha((1 - \lambda)P_0 + \lambda P_1 \parallel (1 - \lambda)Q_0 + \lambda Q_1) \le \max\{ D_\alpha(P_0 \parallel Q_0), D_\alpha(P_1 \parallel Q_1) \}.$
Knowl 7 — Monotonicity, Continuity, and Concavity of Renyi Divergence in Its Order
theoretical result
For fixed probability distributions $P$ and $Q$ on $(\mathcal{X}, \mathcal{F})$ :
- Monotonicity: The function $\alpha \mapsto D_\alpha(P \parallel Q)$ is nondecreasing on $[-\infty, \infty]$ . On the subset $\{\alpha \in [0, \infty] \mid 0 \le \alpha \le 1 \text{ or } D_\alpha(P \parallel Q) < \infty\}$ , it is strictly increasing unless $P = Q(\cdot \mid A)$ for some event $A \in \mathcal{F}$ .
- Continuity in Order: $D_\alpha(P \parallel Q)$ is continuous in $\alpha$ on $[0, 1] \cup \{\alpha \in [-\infty, \infty] \mid |D_\alpha(P \parallel Q)| < \infty\}$ .
- Concavity: The function $\alpha \mapsto (1 - \alpha) D_\alpha(P \parallel Q)$ is concave in $\alpha$ on $[0, \infty]$ (with the conventions that it is $0$ at $\alpha = 1$ , and $0$ at $\alpha = \infty$ if $P = Q$ ).
- Skew Symmetry: For any $\alpha \in (-\infty, \infty) \setminus \{0, 1\}$ ,
$D_\alpha(P \parallel Q) = \frac{\alpha}{1 - \alpha} D_{1-\alpha}(Q \parallel P),$

which implies symmetry $D_{1/2}(P \parallel Q) = D_{1/2}(Q \parallel P)$ for order $\alpha = 1/2$ , and $D_{-\infty}(P \parallel Q) = -D_\infty(Q \parallel P)$ .
Knowl 8 — Approximation via Partitions and Limits of sigma-Algebras
theoretical result
Let $P$ and $Q$ be probability distributions on $(\mathcal{X}, \mathcal{F})$ :
- Finite Partition Approximation: For any order $\alpha \in [0, \infty]$ ,
$D_\alpha(P \parallel Q) = \sup_{\mathcal{P}} D_\alpha(P|_\mathcal{P} \parallel Q|_\mathcal{P}),$

where the supremum is taken over all finite partitions $\mathcal{P} \subseteq \mathcal{F}$ , and $P|_\mathcal{P}, Q|_\mathcal{P}$ denote restrictions to the sub- $\sigma$ -algebra $\sigma(\mathcal{P})$ .
- Increasing Sequences of $\sigma$ -Algebras: If $\mathcal{F}_1 \subseteq \mathcal{F}_2 \subseteq \dots \subseteq \mathcal{F}$ is an increasing filtration and $\mathcal{F}_\infty = \sigma(\bigcup_{n=1}^\infty \mathcal{F}_n)$ , then for all $\alpha \in (0, \infty]$ ,
$\lim_{n \to \infty} D_\alpha(P|_{\mathcal{F}_n} \parallel Q|_{\mathcal{F}_n}) = D_\alpha(P|_{\mathcal{F}_\infty} \parallel Q|_{\mathcal{F}_\infty}).$

(This limit property fails in general for $\alpha = 0$ .)
- Decreasing Sequences of $\sigma$ -Algebras: If $\mathcal{F} \supseteq \mathcal{F}_1 \supseteq \mathcal{F}_2 \supseteq \dots$ and $\mathcal{F}_\infty = \bigcap_{n=1}^\infty \mathcal{F}_n$ , then for all $\alpha \in [0, 1)$ , and for $\alpha \in [1, \infty)$ whenever $D_\alpha(P|_{\mathcal{F}_m} \parallel Q|_{\mathcal{F}_m}) < \infty$ for some $m$ ,
$\lim_{n \to \infty} D_\alpha(P|_{\mathcal{F}_n} \parallel Q|_{\mathcal{F}_n}) = D_\alpha(P|_{\mathcal{F}_\infty} \parallel Q|_{\mathcal{F}_\infty}).$
Knowl 9 — Kakutani Dichotomy and Countable Additivity on Product Measures
theoretical result
Let $(P_n, Q_n)_{n=1}^\infty$ be pairs of probability distributions on measurable spaces $(\mathcal{X}_n, \mathcal{F}_n)$ . Let $P = \prod_{n=1}^\infty P_n$ and $Q = \prod_{n=1}^\infty Q_n$ on the infinite product space.
- Countable Additivity: For all $\alpha \in (0, \infty]$ , Rényi divergence is countably additive on product distributions:
$D_\alpha(P \parallel Q) = \sum_{n=1}^\infty D_\alpha(P_n \parallel Q_n).$

(Countable additivity fails for $\alpha = 0$ .)
- Kakutani's Dichotomy: Suppose $P_n \sim Q_n$ (mutually absolutely continuous) for all $n$ . Then for any fixed $\alpha \in (0, 1)$ , the infinite product distributions $P$ and $Q$ are either equivalent ( $P \sim Q$ ) or mutually singular ( $P \perp Q$ ):
$P \sim Q \iff \sum_{n=1}^\infty D_\alpha(P_n \parallel Q_n) < \infty,$

$P \perp Q \iff \sum_{n=1}^\infty D_\alpha(P_n \parallel Q_n) = \infty.$
Knowl 10 — Generalized Pinsker Inequality and Relations to Statistical Distances
theoretical result
Let $P$ and $Q$ be probability distributions on $(\mathcal{X}, \mathcal{F})$ . Rényi divergence satisfies the following relations to total variation distance $V(P, Q) = \int_\mathcal{X} |p - q| \, d\mu$ , squared Hellinger distance $\operatorname{Hel}^2(P, Q) = \int_\mathcal{X} (\sqrt{p} - \sqrt{q})^2 \, d\mu$ , and $\chi^2$ -divergence $\chi^2(P, Q) = \int_\mathcal{X} \frac{(p-q)^2}{q} \, d\mu$ :
- Generalized Pinsker's Inequality: For any order $\alpha \in (0, 1]$ ,
$\frac{\alpha}{2} V^2(P, Q) \le D_\alpha(P \parallel Q).$
- Divergence Ordering Chain:
$\operatorname{Hel}^2(P, Q) \le D_{1/2}(P \parallel Q) \le D(P \parallel Q) \le D_2(P \parallel Q) \le \chi^2(P, Q),$

since $D_{1/2}(P \parallel Q) = -2 \ln(1 - \frac{1}{2}\operatorname{Hel}^2(P, Q))$ and $D_2(P \parallel Q) = \ln(1 + \chi^2(P, Q))$ .
- Equivalence of Orders in $(0, 1)$ : For any $0 < \alpha \le \beta < 1$ ,
$\frac{\alpha}{\beta} \frac{1-\beta}{1-\alpha} D_\beta(P \parallel Q) \le D_\alpha(P \parallel Q) \le D_\beta(P \parallel Q).$
Knowl 11 — Continuity in Distributions and Compactness of Sublevel Sets
theoretical result
Let $P, Q$ be probability distributions on $(\mathcal{X}, \mathcal{F})$ :
- Setwise Topology: For any $\alpha \in (0, \infty]$ , $D_\alpha(P \parallel Q)$ is lower semi-continuous in the pair $(P, Q)$ under the topology of setwise convergence. When $\mathcal{X}$ is finite, $D_\alpha(P \parallel Q)$ is continuous in $Q$ for all $\alpha \in [0, \infty]$ .
- Total Variation Topology: For $\alpha \in (0, 1)$ , $(P, Q) \mapsto D_\alpha(P \parallel Q)$ is uniformly continuous in total variation distance. For $\alpha = 0$ , $(P, Q) \mapsto D_0(P \parallel Q)$ is upper semi-continuous.
- Weak Topology on Polish Spaces: If $\mathcal{X}$ is a Polish space with Borel $\sigma$ -algebra $\mathcal{F}$ , $(P, Q) \mapsto D_\alpha(P \parallel Q)$ is lower semi-continuous in the weak convergence topology for all $\alpha \in (0, \infty]$ .
- Compact Sublevel Sets: If $\mathcal{X}$ is a Polish space, then for any $c \in [0, \infty)$ , fixed distribution $Q$ , and order $\alpha \in [1, \infty]$ , the sublevel set
$\mathcal{S} = \{ P \mid D_\alpha(P \parallel Q) \le c \}$

is convex and compact in the topology of weak convergence.
Knowl 12 — Shtarkov Distribution and Optimal Distributions for Order Infinity
theoretical result
Let $\{P_\theta \mid \theta \in \Theta\}$ be a family of probability distributions on a countable space $\mathcal{X}$ with finite minimax redundancy $R_\infty < \infty$ .
- Shtarkov Distribution: The unique redundancy-achieving distribution $Q_{\text{opt}}$ for order $\alpha = \infty$ is the Shtarkov distribution (normalized maximum likelihood):
$S(x) = \frac{\sup_\theta P_\theta(x)}{\sum_{y \in \mathcal{X}} \sup_\theta P_\theta(y)},$

and for every distribution $Q$ on $\mathcal{X}$ , the worst-case regret satisfies the exact identity:

$\sup_{\theta \in \Theta} D_\infty(P_\theta \parallel Q) = R_\infty + D_\infty(S \parallel Q), \quad \text{where } R_\infty = \ln \sum_{x \in \mathcal{X}} \sup_{\theta \in \Theta} P_\theta(x).$
- Capacity-Achieving Input Distribution: If $\mathcal{X}$ is finite and there exists a maximum likelihood estimator $\hat{\theta}: \mathcal{X} \to \Theta$ such that $P_\theta(x) \le P_{\hat{\theta}(x)}(x)$ for all $x \in \mathcal{X}, \theta \in \Theta$ , then the distribution $\pi_{\text{opt}}$ defined on $\Theta$ by
$\pi_{\text{opt}}(\theta) = S(\{x \in \mathcal{X} \mid \hat{\theta}(x) = \theta\})$

is a capacity-achieving input distribution for order $\alpha = \infty$ .
Knowl 13 — Second-Order Local Asymptotics of Renyi Divergence and Fisher Information
theoretical result
Let $\{P_\theta \mid \theta \in \Theta \subseteq \mathbb{R}\}$ be a sufficiently regular parametric statistical model with Fisher information

$J(\theta) = \mathbb{E}_{P_\theta}\left[ \left( \frac{d}{d\theta} \ln p_\theta(X) \right)^2 \right].$

For any order $\alpha \in (0, \infty)$ and any interior point $\theta$ in parameter space $\Theta$ , the local Taylor approximation of the Rényi divergence $D_\alpha(P_\theta \parallel P_{\theta'})$ as $\theta' \to \theta$ satisfies:

$\lim_{\theta' \to \theta} \frac{1}{(\theta - \theta')^2} D_\alpha(P_\theta \parallel P_{\theta'}) = \frac{\alpha}{2} J(\theta).$

Coverage note — Omitted material comprises standard introductory review formulas (differential Rényi entropy, normal distribution closed forms), intermediate proof lemmas, historical background, and specific counterexample demonstrations (e.g., non-convexity in P for alpha > 1, non-metricity for alpha = 1/2).

References

1.A. Renyi, ‐‐On measures of entropy and information,‐‐ in Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, pp. 547‐–561, 1961.
2.P. Harremoes, ‐‐Interpretations of R enyi entropies and divergences,‐‐ Physica A: Statistical Mechanics and its Applications, vol. 365, no. 1, pp. 57‐–62, 2006.
3.P. D. Grunwald, The Minimum Description Length Principle. The MIT Press, 2007.
4.I. Csiszar, ‐‐Generalized cutoff rates and R enyi’s information measures,‐‐ IEEE Transactions on Information Theory, vol. 41, no. 1, pp. 26‐–34, 1995.
5.T. Zhang, ‐‐From -entropy to KL-entropy: Analysis of minimum infor‐mation complexity density estimation,‐‐ The Annals of Statistics, vol. 34, no. 5, pp. 2180‐–2210, 2006.
6.D. Haussler and M. Opper, ‐‐Mutual information, metric entropy and cumulative relative entropy risk,‐‐ The Annals of Statistics, vol. 25, no. 6, pp. 2451‐–2492, 1997.
7.T. van Erven, When Data Compression and Statistics Disagree: Two Frequentist Challenges for the Minimum Description Length Principle. PhD thesis, Leiden University, 2010.
8.L. Le Cam, ‐‐Convergence of estimates under dimensionality restric‐tions,‐‐ The Annals of Statistics, vol. 1, no. 1, pp. 38‐–53, 1973.
9.L. Birge, ‐‐On estimating a density using Hellinger distance and some other strange facts,‐‐ Probability Theory and Related Fields, vol. 71, pp. 271‐–291, 1986.
10.S. van de Geer, ‐‐Hellinger-consistency of certain nonparametric max‐imum likelihood estimators,‐‐ The Annals of Statistics, vol. 21, no. 1, pp. 14‐–44, 1993.
11.D. Morales, L. Pardo, and I. Vajda, ‐‐Renyi statistics in directed families of exponential experiments,‐‐ Statistics, vol. 34, pp. 151‐–174, 2000.
12.Y. Mansour, M. Mohri, and A. Rostamizadeh, ‐‐Multiple source adap‐tation and the Renyi divergence,‐‐ in Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence (UAI), pp. 367‐–374, 2009.
13.A. O. Hero, B. Ma, O. Michel, and J. D. Gorman, ‐‐Alpha-divergence for classification, indexing and retrieval (revised),‐‐ Tech. Rep. CSPL-334, Communications and Signal Processing Laboratory, The University of Michigan, 2003.
14.J. Aczel and Z. Dar oczy, On Measures of Information and Their Characterizations. Academic Press, 1975.
15.M. Ben-Bassat and J. Raviv, ‐‐Renyi’s entropy and the probability of error,‐‐ IEEE Transactions on Information Theory, vol. 24, no. 3, pp. 324‐–330, 1978.
16.T. van Erven and P. Harremoes, ‐‐R enyi divergence and majorization,‐‐ in Proceedings of the IEEE International Symposium on Information Theory (ISIT), 2010.
17.O. Shayevitz, ‐‐A note on a characterization of Renyi measures and its relation to composite hypothesis testing.‐‐ arXiv:1012.4401v1, Dec. 2010.
18.O. Shayevitz, ‐‐On Renyi measures and hypothesis testing,‐‐ in IEEE International Symposium on Information Theory Proceedings, pp. 800‐–804, 2011.
19.V. S. Huzurbazar, ‐‐Exact forms of some invariants for distributions admitting sufficient statistics,‐‐ Biometrika, vol. 42, no. 3/4, pp. pp. 533‐–537, 1955.
20.F. Liese and I. Vajda, Convex Statistical Distances. Leipzig: Teubner, 1987.
21.M. Gil, ‐‐On Renyi divergence measures for continuous alphabet sources,‐‐ Master’s thesis, Queen’s University, 2011.
22.M. Gil, F. Alajaji, and T. Linder, ‐‐Renyi divergence measures for com‐monly used univariate continuous distributions,‐‐ Information Sciences, vol. 249, pp. 124‐–131, 2013.
23.D. Aldous and P. Diaconis, ‐‐Strong uniform times and finite random walks,‐‐ Advances in Applied Mathematics, vol. 8, pp. 69‐–97, 1987.
24.A. L. Gibbs and F. E. Su, ‐‐On choosing and bounding probability metrics,‐‐ International Statistical Review, vol. 70, pp. 419‐–435, 2002.
25.G. L. Gilardoni, ‐‐On Pinsker’s and Vajda’s type inequalities for Csiszar’s f-divergences,‐‐ IEEE Transactions on Information Theory, vol. 56, no. 11, pp. 5377‐–5386, 2010.
26.D. Pollard, A User’s Guide to Measure Theoretic Probability. Cambridge University Press, 2002.
27.F. Liese and I. Vajda, ‐‐On divergences and informations in statistics and information theory,‐‐ IEEE Transactions on Information Theory, vol. 52, no. 10, pp. 4394‐–4412, 2006.
28.A. N. Shiryaev, Probability. Springer-Verlag, 1996.
29.S. M. Ali and S. D. Silvey, ‐‐A general class of coefficients of divergence of one distribution from another,‐‐ Journal of the Royal Statistical Society, series B, vol. 28, no. 1, pp. 131‐–142, 1966.
30.T. M. Cover and J. A. Thomas, Elements of Information Theory. Wiley, 1991.
31.I. Csiszar, ‐‐I-divergence geometry of probability distributions and min‐imization problems,‐‐ The Annals of Probability, vol. 3, no. 1, pp. 146‐–158, 1975.
32.F. Topse, Entropy, Search, Complexity, vol. 16 of Bolyai Society Mathematical Studies, ch. 8, Information Theory at the Service of Science, pp. 179‐–207. Springer, 2007.
33.R. Sundaresan, ‐‐A measure of discrimination and its geometric proper‐ties,‐‐ in Proceedings of the IEEE International Symposium on Informa‐tion Theory (ISIT), 2002.
34.R. Sundaresan, ‐‐Guessing under source uncertainty with side infor‐mation,‐‐ in Proceedings of the IEEE International Symposium on Information Theory (ISIT), 2006.
35.Y. V. Prokhorov, ‐‐Convergence of random processes and limit theorems in probability theory,‐‐ Theory of Probability and Its Applications, vol. I, no. 2, pp. 157‐–214, 1956.
36.E. C. Posner, ‐‐Random coding strategies for minimum entropy,‐‐ IEEE Transactions on Information Theory, vol. 21, no. 4, pp. 388‐–391, 1975.
37.A. W. van der Vaart and J. A. Wellner, Weak Convergence and Empirical Processes: With Applications to Statistics. Springer, 1996. (Corrected second printing, 2000).
38.M. S. Pinsker, Information and Information Stability of Random Vari‐ables and Processes. Holden-Day, 1964. Translated by A. Feinstein.
39.A. R. Barron, ‐‐Limits of information, Markov chains and projections,‐‐ in Proceedings of the IEEE International Symposium on Information Theory (ISIT), p. 25, 2000.
40.P. Harremoes and K. K. Holst, ‐‐Convergence of Markov chains in information divergence,‐‐ Journal of Theoretical Probability, vol. 22, pp. 186‐–202, 2009.
41.O. Kallenberg, Foundations of Modern Probability. Springer, 1997.
42.A. W. van der Vaart, Asymptotic Statistics. Cambridge University Press, 1998.
43.J. Feldman, ‐‐Equivalence and perpendicularity of Gaussian processes,‐‐ Pacific Journal of Mathematics, vol. 8, no. 4, pp. 699‐–708, 1958.
44.J. Hajek, ‐‐On a property of normal distributions of any stochastic process,‐‐ Czechoslovak Mathematical Journal, vol. 8, no. 4, pp. 610‐–618, 1958. In Russian with English summary.
45.B. J. Thelen, ‐‐Fisher information and dichotomies in equiva‐lence/contiguity,‐‐ The Annals of Probability, vol. 17, no. 4, pp. 1664‐–1690, 1989.
46.S. Kakutani, ‐‐On equivalence of infinite product measures,‐‐ The Annals of Mathematics, vol. 49, no. 1, pp. 214‐–224, 1948.
47.A. Renyi, ‐‐On some basic problems of statistics from the point of view of information theory,‐‐ in Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1: Statistics, pp. 531‐–543, 1967.
48.S. Kullback, Information theory and statistics. Wiley, 1959.
49.T. Nemetz, ‐‐On the -divergence rate for Markov-dependent hypothe‐ses,‐‐ Problems of Control and Information Theory, vol. 3, no. 2, pp. 147‐–155, 1974.
50.Z. Rached, F. Alajaji, and L. L. Campbell, ‐‐Renyi’s divergence and entropy rates for finite alphabet Markov sources,‐‐ IEEE Transactions on Information Theory, vol. 47, no. 4, pp. 1553‐–1561, 2001.
51.I. Csiszar, ‐‐Information projections revisited,‐‐ IEEE Transactions on Information Theory, vol. 49, no. 6, pp. 1474‐–1490, 2003.
52.A. A. Fedotov, P. Harremoes, and F. Topse, ‐‐Refinements of Pinsker’s inequality,‐‐ IEEE Transactions on Information Theory, vol. 49, no. 6, pp. 1491‐–1498, 2003.
53.R. T. Rockafellar, Convex Analysis. Princeton University Press, 1970.
54.B. Ryabko, ‐‐Comments on ‐‐a source matching approach to finding minimax codes‐‐ by Davisson, L. D. and Leon-Garcia, A.,‐‐ IEEE Transactions on Information Theory, vol. 27, no. 6, pp. 780‐–781, 1981. Including also the ensuing Editor’s Note.
55.D. Haussler, ‐‐A general minimax result for relative entropy,‐‐ IEEE Transactions on Information Theory, vol. 43, no. 4, pp. 1276‐–1280, 1997.
56.M. Sion, ‐‐On general minimax theorems,‐‐ Pacific Journal of Mathemat‐ics, vol. 8, no. 1, pp. 171‐–176, 1958.
57.H. Komiya, ‐‐Elementary proof for Sion’s minimax theorem,‐‐ Kodai Mathematical Journal, vol. 11, no. 1, pp. 5‐–7, 1988.
58.Y. M. Shtar’kov, ‐‐Universal sequential coding of single messages,‐‐ Problems of Information Transmission, vol. 23, no. 3, pp. 175‐–186, 1987.
59.R. Sibson, ‐‐Information radius,‐‐ Z. Warscheinlichkeitstheorie verw. Geb., vol. 14, pp. 149‐–160, 1969.
60.J. Naudts, ‐‐Estimators, escort probabilities, and -exponential families in statistical physics,‐‐ Journal of Inequalities in Pure and Applied Mathematics, vol. 5, no. 4, 102, 2004.

Citation

MLA

van Erven, T., and P. Harremoes. “Rényi Divergence and Kullback-Leibler Divergence”. IEEE Transactions on Information Theory, vol. 60, no. 7, 2014, pp. 3797–820, https://doi.org/10.1109/TIT.2014.2320500.

APA

van Erven, T., & Harremoes, P. (2014). Rényi Divergence and Kullback-Leibler Divergence. IEEE Transactions on Information Theory, 60(7), 3797–3820. https://doi.org/10.1109/TIT.2014.2320500

Chicago

van Erven, T., and P. Harremoes. 2014. “Rényi Divergence and Kullback-Leibler Divergence”. IEEE Transactions on Information Theory 60 (7): 3797–3820. https://doi.org/10.1109/TIT.2014.2320500.

Harvard

van Erven, T. and Harremoes, P. (2014) “Rényi Divergence and Kullback-Leibler Divergence”, IEEE Transactions on Information Theory, 60(7), pp. 3797–3820. Available at: https://doi.org/10.1109/TIT.2014.2320500.

Vancouver

1. van Erven T, Harremoes P (2014) Rényi Divergence and Kullback-Leibler Divergence. IEEE Transactions on Information Theory 60:3797–3820

BibTeX

@article{van_Erven_2014, title={Rényi Divergence and Kullback-Leibler Divergence}, volume={60}, ISSN={1557-9654}, url={http://dx.doi.org/10.1109/TIT.2014.2320500}, DOI={10.1109/tit.2014.2320500}, number={7}, journal={IEEE Transactions on Information Theory}, publisher={Institute of Electrical and Electronics Engineers (IEEE)}, author={van Erven, Tim and Harremoes, Peter}, year={2014}, month=July, pages={3797–3820} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Rényi Divergence and Kullback-Leibler Divergence

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Generalized Pythagorean Inequality for alpha-Convex Sets

Knowl 2 — Variational Representation of Renyi Divergence via Kullback-Leibler Divergence

Knowl 3 — Minimax Characterization of Chernoff Information

Knowl 4 — Equivalence of Generalized Channel Capacity and Minimax Redundancy

Knowl 5 — Definition of Renyi Divergence on General Measurable Spaces

Knowl 6 — Convexity and Quasi-Convexity of Renyi Divergence

Knowl 7 — Monotonicity, Continuity, and Concavity of Renyi Divergence in Its Order

Knowl 8 — Approximation via Partitions and Limits of sigma-Algebras

Knowl 9 — Kakutani Dichotomy and Countable Additivity on Product Measures

Knowl 10 — Generalized Pinsker Inequality and Relations to Statistical Distances

Knowl 11 — Continuity in Distributions and Compactness of Sublevel Sets

Knowl 12 — Shtarkov Distribution and Optimal Distributions for Order Infinity

Knowl 13 — Second-Order Local Asymptotics of Renyi Divergence and Fisher Information

References

Citation

BibTeX

Access the Paper