A didactic, line-by-line companion

Understanding the Limitations of Variational Mutual Information Estimators

Jiaming Song & Stefano Ermon, Stanford University. Published at ICLR 2020 (arXiv:1910.06222v2)

How to read this guide

We go through the paper in its own order, a sentence or paragraph at a time. Each excerpt of the original appears in a yellow 📄 Paper block, and the explanation follows right after it. Four other kinds of boxes are used:

💡 Intuition
The idea in plain words, with pictures. Read these even if you skip the math.
🧮 Math unpacked
Derivations written step by step. Every step says why it holds.
🔢 Worked example
Real numbers you can check with a calculator.
⚠️ Careful
Pitfalls, hidden assumptions and typos in the paper.

This part covers the Primer, Abstract and Sections 1–3. It includes an interactive widget with a slider (Widget 1) that runs a small simulation in your browser.

💡 The whole paper in 5 sentences

1. Mutual information (MI) measures how much two variables tell you about each other. It is often estimated by training a neural network, which is called a variational estimator.

2. The authors show that nearly all these estimators work the same way: guess a density ratio r=p(x,y)/(p(x)p(y))r = p(x,y)/(p(x)p(y)), normalize it, then average log⁡r\log r.

3. The normalizing step needs an average of rr over "unpaired" samples. The variance of that average grows like eMIe^{\text{MI}}, so MINE and NWJ need exponentially large batches (and CPC is capped at log⁡n\log n).

4. They propose SMILE, which clips rr to [e−τ,eτ][e^{-\tau}, e^{\tau}] inside that average. This trades a little bias for a big drop in variance.

5. They also propose self-consistency tests (independence, data processing, additivity). No estimator passes all of them on images, which suggests "maximizing MI" in deep learning may not really be about MI.

0 · Primer: the concepts you need

The paper assumes you are comfortable with probability, information theory and some statistics. If you are, skip to the Abstract. If not, these eight short sections cover everything that comes up later.

0.1 Distributions, densities, expectations and sample averages

A random variable XX is a quantity whose value is uncertain, such as the pixels of a randomly chosen image. Its distribution PP says how likely each value is. When XX is continuous we describe PP with a density p(x)p(x): values where pp is high are more likely.

The expectation of a function ff under PP is the "average value of ff if you drew infinitely many samples":

EP[f]  =  ∫f(x) p(x) dx  =  ∫f dP.\E_P[f] \;=\; \int f(x)\,p(x)\,dx \;=\; \int f\, dP .

In practice we never have infinitely many samples. We have nn of them, x1,…,xnx_1,\dots,x_n, and we replace the expectation by a sample average. The paper writes this as EPn\E_{P_n}, where PnP_n is the empirical distribution, which puts weight 1/n1/n on each observed sample:

EPn[f]  =  1n∑i=1nf(xi)  ≈  EP[f].\E_{P_n}[f] \;=\; \frac1n\sum_{i=1}^n f(x_i) \;\approx\; \E_P[f].
💡 Remember

Every estimator in this paper starts from an exact formula with expectations and turns it into something computable by swapping EP\E_P for EPn\E_{P_n}. Most of the paper is about what goes wrong when you make that swap.

0.2 Entropy and KL divergence

The entropy H(X)=−EP[log⁡p(X)]H(X) = -\E_P[\log p(X)] measures uncertainty. The paper uses natural logarithms, so information is measured in nats (1 nat ≈ 1.44 bits).

The Kullback–Leibler (KL) divergence measures how different a distribution PP is from another distribution QQ:

DKL(P ∥ Q)  =  EP ⁣[log⁡p(x)q(x)]  =  EP ⁣[log⁡dPdQ].\KL(P\,\|\,Q) \;=\; \E_P\!\left[\log\frac{p(x)}{q(x)}\right] \;=\; \E_P\!\left[\log \frac{dP}{dQ}\right].

Three facts are used over and over:

  • DKL(P∥Q)≥0\KL(P\|Q)\ge 0, with equality only when P=QP=Q. This is Gibbs' inequality.
  • KL is not symmetric: in general DKL(P∥Q)≠DKL(Q∥P)\KL(P\|Q)\neq \KL(Q\|P).
  • dPdQ\frac{dP}{dQ}, the Radon–Nikodym derivative, is the measure-theory name for the ratio of densities p(x)/q(x)p(x)/q(x). Wherever you see dP/dQdP/dQ, read "p/qp/q".

0.3 Mutual information

The mutual information I(X;Y)I(X;Y) answers the question: how much does knowing YY reduce my uncertainty about XX?

I(X;Y)  =  H(X)−H(X∣Y)  =  DKL( P(X,Y)⏟joint  ∥  P(X)P(Y)⏟product of marginals).I(X;Y) \;=\; H(X) - H(X\mid Y) \;=\; \KL\big(\,\underbrace{P(X,Y)}_{\text{joint}}\;\big\|\;\underbrace{P(X)P(Y)}_{\text{product of marginals}}\big).
H(X|Y) H(Y|X) I(X;Y) shared H(X) H(Y)
MI is the information that XX and YY share: the overlap of their uncertainties.

The KL form is the one the paper uses. Compare two ways of generating a pair (x,y)(x,y):

  • Joint P(X,Y)P(X,Y): draw a real pair, for example an image together with its own caption.
  • Product of marginals P(X)P(Y)P(X)P(Y): draw xx and yy independently, for example an image with the caption of a random other image.

If XX and YY are independent, the two procedures give the same distribution and the MI is 0. The more the real pairs differ from random pairings, the larger the MI.

🔢 Worked examples

Coin copy. XX is a fair coin and Y=XY = X. Knowing YY removes all uncertainty about XX, so I=H(X)=log⁡2≈0.693I = H(X) = \log 2 \approx 0.693 nats, which is exactly 1 bit.

Correlated Gaussians. If (X,Y)(X,Y) are standard normal with correlation ρ\rho, then I=−12log⁡(1−ρ2)I = -\tfrac12\log(1-\rho^2). For ρ=0.5\rho=0.5 this is 0.1440.144 nats, and for ρ=0.99\rho = 0.99 it is 1.961.96 nats. With dd independent such coordinate pairs the MI adds up: I=−d2log⁡(1−ρ2)I = -\tfrac d2 \log(1-\rho^2). This is Eq. (55) of the paper, which the experiments use.

🎛️ Widget 1: joint vs product of marginals, colored by the density ratio

Left: 400 real pairs (xi,yi)(x_i,y_i) from PP. Right: the same xx's paired with shuffled yy's, which is how MINE/NWJ/CPC build samples from Q=P(X)P(Y)Q=P(X)P(Y) inside a mini-batch. The color is log⁡r(x,y)\log r(x,y) with r=p(x,y)/(p(x)p(y))r = p(x,y)/(p(x)p(y)): orange means "much more likely as a real pair", blue means "less likely". Increase ρ\rho and look for the rare orange points on the right.

0.4 The density ratio: the central object of the paper

Define

r⋆(x,y)  =  dPdQ  =  p(x,y)p(x) p(y).r^\star(x,y) \;=\; \frac{dP}{dQ} \;=\; \frac{p(x,y)}{p(x)\,p(y)} .

Then, directly from the definition of KL, I(X;Y)=EP[log⁡r⋆]I(X;Y) = \E_{P}[\log r^\star]. Two properties of r⋆r^\star do all the work in this paper:

  1. It averages to 1 under QQ: EQ[r⋆]=∫pq q=∫p=1\E_Q[r^\star] = \int \frac{p}{q}\,q = \int p = 1. Section 3 is built on this.
  2. Under QQ it is usually tiny but occasionally huge. Most random pairings are implausible (r⋆≪1r^\star\ll 1). Once in a while a random pairing happens to look like a real pair, and then r⋆r^\star is enormous. Those rare huge values are what make the average equal 1. A quantity like this is called heavy-tailed, and its sample averages are very noisy. Section 4 is built on this. You can see it in Widget 1: compare "max r under Q" with "mean r under Q".

0.5 Estimators: bias, variance and MSE

An estimator I^\hat I is a recipe that turns random samples into a number. Because the samples are random, I^\hat I is random too. We judge it by:

Bias
E[I^]−I\E[\hat I] - I: is it right on average?
Variance
E[(I^−EI^)2]\E[(\hat I - \E\hat I)^2]: how much does it jump around from batch to batch?
MSE
E[(I^−I)2]=Bias2+Variance\E[(\hat I - I)^2] = \text{Bias}^2 + \text{Variance}: the overall error.
The bull's-eye is the true MI and each dot is one estimate. The paper's main point: NWJ/MINE are like board 2 (high variance), CPC is like board 3 (high bias, capped), and SMILE aims for board 1.

One fact about averages matters a lot here. If Z1,…,ZnZ_1,\dots,Z_n are i.i.d. (independent and identically distributed) with variance σ2\sigma^2, then

Var⁡ ⁣[1n∑i=1nZi]=σ2n.\Var\!\left[\frac1n\sum_{i=1}^n Z_i\right] = \frac{\sigma^2}{n}.

To keep the error of an average fixed, the batch size nn must grow in proportion to σ2\sigma^2. So if σ2\sigma^2 grows like eMIe^{\text{MI}}, the batch has to grow like eMIe^{\text{MI}} too. That is Theorem 2 in one line.

0.6 Jensen's inequality

For a concave function such as log⁡\log, "the log of the average ≥ the average of the logs":

E[log⁡Z]  ≤  log⁡E[Z],and for convex e(⋅):E[eZ]  ≥  eE[Z].\E[\log Z] \;\le\; \log \E[Z], \qquad\text{and for convex } e^{(\cdot)}:\quad \E[e^Z] \;\ge\; e^{\E[Z]}.
log E[Z] = log 2 ≈ 0.69 E[log Z] ≈ 0.28 log z z=0.5 z=3.5 E[Z]=2
ZZ is 0.5 or 3.5 with equal probability. The chord (the average of the logs) lies below the curve (the log of the average).
⚠️ Why this matters

MINE computes log⁡(sample average)\log(\text{sample average}). By Jensen, E[log⁡EQn[⋅]]≤log⁡EQ[⋅]\E[\log \E_{Q_n}[\cdot]] \le \log \E_Q[\cdot], so the estimate is biased even when the sample average itself is unbiased. Sections 2.2 and 3.1 come back to this.

0.7 What "variational" means here

A variational bound rewrites a hard quantity as the best value of an optimization problem:

hard quantity  =  sup⁡T∈F  objective(T).\text{hard quantity} \;=\; \sup_{T\in\mathcal F}\; \text{objective}(T).

Two consequences follow. (a) Any particular TT gives a lower bound. (b) A neural network TθT_\theta trained by gradient ascent on the objective pushes that lower bound up toward the true value. "Variational MI estimators" are exactly this: a neural network (the critic) is trained to maximize a lower bound on MI.

0.8 "Partition function"

The term comes from statistical physics. When you build a distribution as eT(x)q(x)Z\frac{e^{T(x)}q(x)}{Z}, the constant Z=EQ[eT]Z = \E_Q[e^T] that makes it sum to 1 is called the partition function (normalizer). Every time the paper says "partition function", read "the average of the unnormalized density ratio under QQ". Estimating it from a mini-batch is the bottleneck the paper studies.

Abstract

Variational approaches based on neural networks are showing promise for estimating mutual information (MI) between high dimensional variables.

Classical MI estimators (histograms, nearest neighbours, kernel density estimates) break down in high dimensions. Imagine estimating a density over 784-pixel MNIST images with a histogram. The modern alternative trains a neural network to maximize a lower bound on MI (see 0.7). These are the "variational approaches".

However, they can be difficult to use in practice due to poorly understood bias/variance tradeoffs.

Some estimators systematically under- or over-estimate (bias). Others give wildly different answers from one mini-batch to the next (variance). Before this paper there was no clear theory explaining why.

We theoretically show that, under some conditions, estimators such as MINE exhibit variance that could grow exponentially with the true amount of underlying MI.

First contribution (Theorem 2). If the true MI is II nats, the variance of MINE's normalization term is at least (eI−1)/n(e^{I}-1)/n for a batch of size nn. Going from 5 to 10 nats multiplies this lower bound by about e5≈148e^5\approx 148.

We also empirically demonstrate that existing estimators fail to satisfy basic self-consistency properties of MI, such as data processing and additivity under independence.

Second contribution (Section 4.2 / 6.2). The true MI of real images is unknown, so we cannot check estimators against it. We can check whether they obey rules that true MI must obey, for example "two independent copies of a problem should have twice the MI". The tested estimators break these rules.

Based on a unified perspective of variational approaches, we develop a new estimator that focuses on variance reduction.

Third contribution (Section 3 and Section 5). The authors show that all these estimators are instances of one template (Theorem 1). The template points to the exact term responsible for the variance, the partition function. They then build an estimator, SMILE, that tames that term.

Empirical results on standard benchmark tasks demonstrate that our proposed estimator exhibits improved bias-variance trade-offs on standard benchmark tasks.

On Gaussian toy problems, where the true MI is known, SMILE has a much lower mean-squared error than CPC or NWJ (Section 6.1, Table 2).

1 · Introduction

Mutual information (MI) estimation and optimization are crucial to many important problems in machine learning, such as representation learning (Chen et al., 2016; Zhao et al., 2018b; Tishby & Zaslavsky, 2015; Higgins et al., 2018) and reinforcement learning (Pathak et al., 2017; van den Oord et al., 2018).

Why should ML practitioners care?

  • Representation learning: a good representation zz of an input xx should keep a lot of information about it, so you maximize I(x;z)I(x;z). InfoGAN (Chen et al.) maximizes MI between latent codes and generated images. The Information Bottleneck (Tishby) trades off I(x;z)I(x;z) against I(z;y)I(z;y).
  • Reinforcement learning: curiosity-driven exploration (Pathak) and contrastive predictive coding (van den Oord) use information-based signals as rewards or training objectives.

Note that "estimation" (getting the number) and "optimization" (pushing it up or down during training) are different goals. The paper returns to this distinction in Section 4.2.

However, estimating mutual information from samples is challenging (McAllester & Statos, 2018) and traditional parametric and non-parametric approaches (Nemenman et al., 2004; Gao et al., 2015; 2017) struggle to scale up to modern machine learning problems, such as estimating the MI between images and learned representations.

McAllester & Stratos (the paper misspells it "Statos") proved a sobering result: any distribution-free estimator that gives a high-confidence lower bound on MI from NN samples cannot certify more than about log⁡N\log N nats. Keep this in mind: Section 4.1 rediscovers the same "exponential" barrier from a different angle. "Parametric" means assuming a specific distribution family (e.g. Gaussian). "Non-parametric" means methods like k-nearest neighbours. Both scale badly to images.

Recently, there has been a surge of interest in MI estimation with variational approaches (Barber & Agakov, 2003; Nguyen et al., 2010; Donsker & Varadhan, 1975), which can be naturally combined with deep learning methods (Alemi et al., 2016; van den Oord et al., 2018; Poole et al., 2019).

The three cited classics give the three basic bounds (BA, NWJ, DV) explained in Section 2.2. The modern papers plug neural networks into them. Poole et al. (2019), "On variational bounds of MI", is the closest predecessor of this paper and worth reading alongside it.

Despite their empirical effectiveness in downstream tasks such as representation learning (Hjelm et al., 2018; Velickovi´c et al., 2018), their effectiveness for MI estimation remains unclear. In particular, higher estimated MI between observations and learned representations do not seem to indicate improved predictive performance when the representations are used for downstream supervised learning tasks (Tschannen et al., 2019).

Deep InfoMax (Hjelm) and Deep Graph Infomax (Veličković) learn good representations by maximizing MI estimates. But Tschannen et al. found that a higher MI estimate does not mean better features. That is a red flag: either the estimators do not measure MI well, or MI is not what makes the features good, or both. This paper investigates the first possibility.

In this paper, we discuss two limitations of variational approaches to MI estimation. First, we theoretically demonstrate that the variance of certain estimators, such as MINE (Belghazi et al., 2018), could grow exponentially with the ground truth MI, leading to poor bias-variance trade-offs.

Limitation 1 is theoretical: variance ∝eMI\propto e^{\text{MI}}. "Ground truth MI" means the actual, unknown value. "Poor bias-variance trade-offs" means you can reduce the variance only by accepting a lot of bias, and vice versa.

Second, we propose a set of self-consistency tests over basic properties of MI, and empirically demonstrate that all considered variational estimators fail to satisfy critical properties of MI, such as data processing and additivity under independence. These limitations challenge the effectiveness of these methods for estimating or optimizing MI.

Limitation 2 is empirical: the estimators violate rules any MI must obey. If an estimator does not behave like MI, then maximizing it is not really maximizing MI.

To mitigate these issues, we propose a unified perspective over variational estimators treating variational MI estimation as an optimization problem over (valid) density ratios. This view highlights the role of partition functions estimation, which is the culprit of high variance issues in MINE.

"Valid density ratio" means a non-negative function that averages to 1 under QQ (defined precisely in 2.1). The authors show that every estimator is "pick a valid ratio and average its log under PP". To make a ratio valid you must divide by its average under QQ, the partition function, and estimating that from a mini-batch is what blows up.

To address this issue, we propose to improve MI estimation via variance reduction techniques for partition function estimation. Empirical results demonstrate that our estimators have much better bias-variance trade-off compared to existing methods on standard benchmark tasks.

The variance reduction technique is clipping (Section 5). Clipping a heavy-tailed variable to a bounded range caps its variance, at the price of some bias.

§3 Unified viewMI = sup over ratios §4.1 Variance ∝ e^MItheory (Thm 2) §4.2 Self-consistencytests §5 SMILEclip the ratio §6.2 Image testsMNIST, CIFAR10 §6.1 + §7results, verdict
How the parts of the paper connect.

2 · Background and related work

2.1 Notation

We use uppercase letters to denote a probability measure (e.g., P,QP, Q) and corresponding lowercase letters to denote its density functions (e.g., p,qp, q) unless specified otherwise.

Footnote 1: In the remainder of the paper, we slightly overload "density" for discrete random variables.

PP is the distribution itself, the object that assigns probabilities to events. pp is the function you can evaluate at a point. For discrete variables, "density" means the probability mass function p(x)=Pr⁡[X=x]p(x) = \Pr[X=x]. This is the "overloading" in the footnote.

We use X,YX, Y to denote random variables with separable sample spaces denoted as X\mathcal X and Y\mathcal Y respectively, and P(X)\mathcal P(\mathcal X) (or P(Y)\mathcal P(\mathcal Y)) to denote the set of all probability measures over the Borel σ-algebra on X\mathcal X (or Y\mathcal Y).

Sample space X\mathcal X
The set of possible values of XX, e.g. R20\R^{20} or the set of 28×28 images.
Separable
A technical condition (there is a countable dense subset) that rules out pathological spaces. Every space used in practice satisfies it, so you can ignore it.
Borel σ-algebra
The collection of "reasonable" events (sets) to which probabilities can be assigned: intervals, balls, and anything built from them by countable unions, intersections and complements.
P(X)\mathcal P(\mathcal X)
"All possible probability distributions on X\mathcal X".

Under Q∈P(X)Q\in\mathcal P(\mathcal X), the p-norm of a function r:X→Rr:\mathcal X\to\R is defined as ∥r∥p:=(∫∣r∣p dQ)1/p\|r\|_p := (\int |r|^p\,dQ)^{1/p} with ∥r∥∞=lim⁡p→∞∥r∥p\|r\|_\infty = \lim_{p\to\infty}\|r\|_p. The set of locally p-integrable functions is defined as Lp(Q):={r:X→R∣∥r∥p<∞}L^p(Q) := \{r:\mathcal X\to\R \mid \|r\|_p<\infty\}.

  • ∥r∥1=EQ∣r∣\|r\|_1 = \E_Q|r|: the average absolute value.
  • ∥r∥2=EQ[r2]\|r\|_2 = \sqrt{\E_Q[r^2]}: the root-mean-square.
  • ∥r∥∞\|r\|_\infty: essentially the largest value ∣r∣|r| takes, ignoring sets of probability 0.
  • L∞(Q)L^\infty(Q): the bounded functions. The critics TT in the DV and NWJ bounds are taken from L∞(Q)L^\infty(Q) so that eTe^{T} is guaranteed to have a finite average.

The space of probability measures wrt. QQ is defined as Δ(Q):={r∈L1(Q)∣∥r∥1=1, r≥0}\Delta(Q) := \{r\in L^1(Q)\mid \|r\|_1 = 1,\ r\ge 0\}; we also call this the space of "valid density ratios" wrt. QQ.

Δ(Q)  =  { r  :  r(x)≥0  and  EQ[r]=1 }.\Delta(Q) \;=\; \Big\{\, r \;:\; r(x)\ge 0 \ \text{ and } \ \E_Q[r] = 1 \,\Big\}.
💡 Why "valid density ratio"?

Any r∈Δ(Q)r\in\Delta(Q) can be used to reweight QQ into a new distribution RR with density r(x) q(x)r(x)\,q(x). The new density is non-negative and integrates to ∫r q=EQ[r]=1\int r\,q = \E_Q[r]=1. So r=dR/dQr = dR/dQ is the density ratio between some legitimate distribution RR and QQ. Conversely, every distribution RR that is absolutely continuous w.r.t. QQ arises this way.

Example: let QQ be uniform on [0,1][0,1] and r(x)=2xr(x)=2x. Then r≥0r\ge0 and ∫012x dx=1\int_0^1 2x\,dx = 1, so r∈Δ(Q)r\in\Delta(Q). It reweights the uniform distribution into the triangular density 2x2x. By contrast, r(x)=3xr(x) = 3x integrates to 1.5, so it is not valid.

We use P≪QP\ll Q to denote that PP is absolutely continuous with respect to QQ. We use I^E\hat I_E to denote an estimator for IEI_E where we replace expectations with sample averages.

P≪QP \ll Q means "if QQ says an event is impossible, then PP says so too". It guarantees that dP/dQdP/dQ exists and has no division by zero where PP has mass. For MI, PP is the joint and QQ is the product of marginals. Wherever the joint puts mass, both marginals are positive, so this condition is usually satisfied.

The hat convention: IMINEI_{\text{MINE}} is a population quantity with true expectations. I^MINE\hat I_{\text{MINE}} is the computable version with mini-batch averages. Keep the distinction in mind: Section 4 is entirely about the gap between the two.

2.2 Variational mutual information estimation

The mutual information between two random variables XX and YY is the KL divergence between the joint and the product of marginals:

I(X;Y)=DKL(P(X,Y) ∥ P(X)P(Y))I(X;Y) = \KL\big(P(X,Y)\,\|\,P(X)P(Y)\big)

which we wish to estimate using samples from P(X,Y)P(X,Y); in certain cases we may know the density of marginals (e.g. P(X)P(X)). There are a wide range of variational approaches to variational MI estimation. Variational information maximization uses the following result (Barber & Agakov, 2003):

This is the setting: we get a dataset of pairs (xi,yi)(x_i,y_i) and nothing else, unless we happen to know p(x)p(x) exactly (for example, when XX is noise we generated ourselves).

Lemma 1 · Barber–Agakov (BA)

For two random variables XX and YY:

I(X;Y)=sup⁡qϕ{EP(X,Y)[log⁡qϕ(x∣y)−log⁡p(x)]}=:IBA(qϕ)I(X;Y) = \sup_{q_\phi}\Big\{\E_{P(X,Y)}\big[\log q_\phi(x\mid y) - \log p(x)\big]\Big\} =: I_{\text{BA}}(q_\phi)

where qϕ:Y→P(X)q_\phi:\mathcal Y\to\mathcal P(\mathcal X) is a valid conditional distribution over X\mathcal X given y∈Yy\in\mathcal Y and p(x)p(x) is the probability density function of the marginal distribution P(X)P(X).

qϕq_\phi is a neural network that takes yy and outputs a distribution over xx. For instance, a decoder that outputs the mean and variance of a Gaussian. ϕ\phi are its weights.

🧮 Why Lemma 1 is true (3 lines)
I(X;Y)I(X;Y)
=EP ⁣[log⁡p(x∣y)p(x)]\displaystyle =\E_P\!\left[\log\frac{p(x\mid y)}{p(x)}\right]
since p(x,y)p(x)p(y)=p(x∣y)p(x)\frac{p(x,y)}{p(x)p(y)} = \frac{p(x\mid y)}{p(x)}
=EP ⁣[log⁡qϕ(x∣y)p(x)]+EP(y)[DKL(p(x∣y) ∥ qϕ(x∣y))]\displaystyle =\E_P\!\left[\log\frac{q_\phi(x\mid y)}{p(x)}\right] + \E_{P(y)}\Big[\KL\big(p(x\mid y)\,\|\,q_\phi(x\mid y)\big)\Big]
add and subtract log⁡qϕ(x∣y)\log q_\phi(x\mid y)
≥IBA(qϕ)\displaystyle \ge I_{\text{BA}}(q_\phi)
KL ≥ 0; equality iff qϕ=p(x∣y)q_\phi = p(x\mid y)

So the gap is exactly how badly the decoder qϕq_\phi approximates the true posterior. Training qϕq_\phi by maximum likelihood closes the gap.

⚠️ The catch

You must be able to evaluate log⁡p(x)\log p(x), the true marginal density. Equivalently IBA=H(X)−(cross-entropy of qϕ)I_{\text{BA}} = H(X) - \text{(cross-entropy of } q_\phi), so you need to know the entropy H(X)H(X). For real data such as images you don't.

Another family of approaches perform MI estimation through variational lower bounds to KL divergences. For example, the Mutual Information Neural Estimator (MINE, Belghazi et al. (2018)) applies the following lower bound to KL divergences (Donsker & Varadhan, 1975).

Lemma 2 · Donsker–Varadhan (DV), the basis of MINE

∀P,Q∈P(X)\forall P,Q\in\mathcal P(\mathcal X) such that P≪QP\ll Q,

DKL(P∥Q)=sup⁡T∈L∞(Q){EP[T]−log⁡EQ[eT]}=:IMINE(T).\KL(P\|Q) = \sup_{T\in L^\infty(Q)}\Big\{\E_P[T] - \log\E_Q[e^T]\Big\} =: I_{\text{MINE}}(T).

TT is any bounded function, called the critic or "statistics network". To make the objective large, TT must be high on samples from PP (first term) while keeping eTe^T small on average under QQ (second term). In other words, TT learns to tell PP-samples from QQ-samples.

🧮 Why the DV bound holds, via the "Gibbs distribution" trick

Given any TT, define a new distribution GG by reweighting QQ:   dG=eTEQ[eT] dQ\;dG = \dfrac{e^{T}}{\E_Q[e^T]}\,dQ. Then

EP[T]−log⁡EQ[eT]\E_P[T] - \log\E_Q[e^T]
=EP ⁣[log⁡eTEQ[eT]]=EP ⁣[log⁡dGdQ]\displaystyle = \E_P\!\left[\log\frac{e^T}{\E_Q[e^T]}\right] = \E_P\!\left[\log\frac{dG}{dQ}\right]
the constant goes inside the expectation
=EP ⁣[log⁡dPdQ]−EP ⁣[log⁡dPdG]\displaystyle = \E_P\!\left[\log\frac{dP}{dQ}\right] - \E_P\!\left[\log\frac{dP}{dG}\right]
dGdQ=dPdQ/dPdG\frac{dG}{dQ} = \frac{dP}{dQ}\big/\frac{dP}{dG}
=DKL(P∥Q)−DKL(P∥G)  ≤  DKL(P∥Q)= \KL(P\|Q) - \KL(P\|G) \;\le\; \KL(P\|Q)
KL ≥ 0

Equality holds when G=PG=P, i.e. when T=log⁡dPdQ+cT = \log\frac{dP}{dQ} + c for any constant cc. DV is shift-invariant: adding a constant to TT changes nothing, because the log⁡EQ[eT]\log\E_Q[e^T] term subtracts it back out. Keep eTEQ[eT]\frac{e^T}{\E_Q[e^T]} in mind: it is a normalized ratio and it reappears in Theorem 1.

One could set P=P(X,Y)P = P(X,Y) and Q=P(X)P(Y)Q = P(X)P(Y), TT as a parametrized neural network (e.g. Tθ(x,y)T_\theta(x,y) parametrized by θ\theta), and obtain the estimate by optimizing the above objective via stochastic gradient descent over mini-batches.

In practice, for a batch {(xi,yi)}i=1n\{(x_i,y_i)\}_{i=1}^n:

I^MINE=1n∑iTθ(xi,yi)⏟positive (real) pairs  −  log⁡1n∑ieTθ(xi, yσ(i))⏟shuffled pairs ≈ Q\hat I_{\text{MINE}} = \underbrace{\frac1n\sum_{i} T_\theta(x_i,y_i)}_{\text{positive (real) pairs}} \;-\; \log \underbrace{\frac{1}{n}\sum_{i} e^{T_\theta(x_i,\,y_{\sigma(i)})}}_{\text{shuffled pairs } \approx\, Q}

Here σ\sigma is a random permutation, or you can use all n(n−1)n(n-1) off-diagonal pairs (xi,yj)(x_i,y_j), i≠ji\ne j. Shuffling breaks the dependence between xx and yy and turns joint samples into product-of-marginal samples, exactly as in Widget 1.

However, the corresponding estimator I^MINE\hat I_{\text{MINE}} (where we replace the expectations in Eq. (3) with sample averages) is biased, leading to biased gradient estimates; Belghazi et al. (2018) propose to reduce bias via estimating the partition function EQ[eT]\E_Q[e^T] with exponential moving averages of mini-batches.

🧮 Two sources of bias

(a) Bias of the value. EQn[eT]\E_{Q_n}[e^T] is an unbiased estimate of EQ[eT]\E_Q[e^T], but its log is not: by Jensen, E[log⁡EQneT]≤log⁡EQeT\E[\log \E_{Q_n}e^T]\le \log \E_Q e^T. Since this term is subtracted, I^MINE\hat I_{\text{MINE}} is biased upward relative to IMINE(T)I_{\text{MINE}}(T). That is unpleasant for something advertised as a lower bound.

(b) Bias of the gradient.

∇θlog⁡EQ[eTθ]=EQ[eTθ∇θTθ]EQ[eTθ]\nabla_\theta \log\E_Q[e^{T_\theta}] = \frac{\E_Q[e^{T_\theta}\nabla_\theta T_\theta]}{\E_Q[e^{T_\theta}]}

This is a ratio of expectations, and a ratio of two mini-batch averages is a biased estimate of the ratio of expectations. MINE's fix is to replace the denominator with an exponential moving average (EMA) over many past batches, which is effectively a larger batch.

The variational f-divergence estimation approach (Nguyen et al., 2010; Nowozin et al., 2016) considers lower bounds on f-divergences which can be specialize to KL divergence, and subsequently to mutual information estimation:

An f-divergence is Df(P∥Q)=EQ[f(dP/dQ)]D_f(P\|Q) = \E_Q[f(dP/dQ)] for a convex ff with f(1)=0f(1)=0. KL is the case f(u)=ulog⁡uf(u) = u\log u. Every f-divergence has a variational form Df=sup⁡TEP[T]−EQ[f∗(T)]D_f = \sup_T \E_P[T] - \E_Q[f^*(T)], where f∗f^* is the convex conjugate (Fenchel dual). This is also the basis of f-GAN (Nowozin). For KL, f∗(t)=et−1f^*(t) = e^{t-1}, which gives:

Lemma 3 · Nguyen–Wainwright–Jordan (NWJ)

∀P,Q∈P(X)\forall P,Q\in\mathcal P(\mathcal X) such that P≪QP\ll Q,

DKL(P∥Q)=sup⁡T∈L∞(Q){EP[T]−EQ[eT−1]}=:INWJ(T)\KL(P\|Q) = \sup_{T\in L^\infty(Q)}\Big\{\E_P[T] - \E_Q[e^{T-1}]\Big\} =: I_{\text{NWJ}}(T)

and DKL(P∥Q)=INWJ(T)\KL(P\|Q) = I_{\text{NWJ}}(T) when T=log⁡(dP/dQ)+1T = \log(dP/dQ)+1.

🧮 NWJ from DV in one line

For any u>0u>0, log⁡u≤u/e\log u \le u/e. The tangent line of log⁡\log at u=eu=e is u/eu/e, and log⁡\log is concave, so it lies below its tangent. Apply this with u=EQ[eT]u = \E_Q[e^T]:

INWJ(T)=EP[T]−EQ[eT]e  ≤  EP[T]−log⁡EQ[eT]=IMINE(T)  ≤  DKL(P∥Q).I_{\text{NWJ}}(T) = \E_P[T] - \frac{\E_Q[e^{T}]}{e} \;\le\; \E_P[T] - \log\E_Q[e^T] = I_{\text{MINE}}(T) \;\le\; \KL(P\|Q).

Check the optimum: with T=log⁡r⋆+1T = \log r^\star + 1, we get EQ[eT−1]=EQ[r⋆]=1\E_Q[e^{T-1}] = \E_Q[r^\star]=1 and EP[T]=DKL+1\E_P[T] = \KL + 1, so INWJ=DKL+1−1=DKLI_{\text{NWJ}} = \KL+1-1=\KL. ✓

Unlike DV, NWJ is not shift-invariant. The optimal TT is pinned to log⁡r⋆+1\log r^\star+1, with no free constant. That is the price for removing the log.

The supremum over TT is a invertible function of the density ratio dP/dQdP/dQ, so one could use this approach to estimate density ratios by inverting the function (Nguyen et al., 2010; Nowozin et al., 2016; Grover & Ermon, 2017).

Since T⋆=1+log⁡r⋆T^\star = 1+\log r^\star, once TT is trained you can read off a density-ratio estimate r^=eT−1\hat r = e^{T-1}. This "estimator → density ratio" link is the seed of Section 3.

The corresponding mini-batch estimator (denoted as I^NWJ\hat I_{\text{NWJ}}) is unbiased, so unlike MINE, this approach does not require special care to reduce bias in gradients.

There is no log of an average, just two plain averages, and the average of i.i.d. terms is unbiased. Careful with the wording, though: "unbiased" means E[I^NWJ]=INWJ(T)\E[\hat I_{\text{NWJ}}] = I_{\text{NWJ}}(T) for the current TT. It does not mean the estimate equals the true MI. Section 4 shows that this unbiasedness comes with enormous variance.

Contrastive Predictive Coding (CPC / InfoNCE)

Contrastive Predictive Coding (CPC, van den Oord et al. (2018)) considers the following objective:

ICPC(fθ):=EPn(X,Y)[1n∑i=1nlog⁡fθ(xi,yi)1n∑j=1nfθ(xi,yj)]I_{\text{CPC}}(f_\theta) := \E_{P^n(X,Y)}\left[\frac1n\sum_{i=1}^n \log\frac{f_\theta(x_i,y_i)}{\frac1n\sum_{j=1}^n f_\theta(x_i,y_j)}\right]

where fθ:X×Y→R≥0f_\theta:\mathcal X\times\mathcal Y\to\R_{\ge0} is a neural network parametrized by θ\theta and Pn(X,Y)P^n(X,Y) denotes the joint pdf for nn i.i.d. random variables sampled from P(X,Y)P(X,Y).

💡 CPC is a classification game

Take a batch of nn real pairs. For each xix_i, line up all nn candidates y1,…,yny_1,\dots,y_n. Exactly one of them, yiy_i, is its real partner (the "positive"), and the other n−1n-1 are "negatives". The fraction f(xi,yi)∑jf(xi,yj)\frac{f(x_i,y_i)}{\sum_j f(x_i,y_j)} is a softmax probability of picking the right partner. So

ICPC=log⁡n  −  E[−1n∑ilog⁡softmaxi]⏟InfoNCE cross-entropy loss  ≥0  ≤  log⁡n.I_{\text{CPC}} = \log n \;-\; \underbrace{\E\Big[-\tfrac1n\textstyle\sum_i \log \text{softmax}_i\Big]}_{\text{InfoNCE cross-entropy loss}\;\ge 0}\;\le\;\log n .

Even a perfect classifier only gets the loss down to 0, so CPC can never report more than log⁡n\log n.

score matrix f(xᵢ, yⱼ) (n × n evaluations) ■ diagonal = positives (real pairs) □ off-diagonal = negatives (≈ Q) each row → softmax "which y belongs to xᵢ?"
For a batch of n=6n=6 there are 36 critic evaluations. In general the cost is n2n^2.

CPC generally has less variance but is more biased because its estimate does not exceed log⁡n\log n, where nn is the batch size (van den Oord et al., 2018; Poole et al., 2019). While one can further reduce the bias with larger nn, the number of evaluations needed for estimating each batch with fθf_\theta is n2n^2, which scales poorly. To address the high-bias issue of CPC, Poole et al. proposed an interpolation between ICPCI_{\text{CPC}} and INWJI_{\text{NWJ}} to obtain more fine-grained bias-variance trade-offs.

🔢 Numbers

With the batch size used in the experiments, n=64n = 64, CPC is capped at log⁡64≈4.16\log 64 \approx 4.16 nats. In Figure 1 you will see CPC's curve flatten exactly at the dashed "log(bs)" line, while the true MI climbs to 10. To measure 10 nats you would need n≥e10≈22,000n\ge e^{10}\approx 22{,}000, which means 22,0002≈4.8×10822{,}000^2\approx 4.8\times10^8 critic evaluations per batch.

CPC has low variance because the softmax ratio lies in [0,n][0,n], so each term is bounded. It has high bias because of the cap. NWJ is the opposite. Poole et al.'s interpolation (often called α-InfoNCE) sits in between.

3 · Variational MI estimation as optimization over density ratios

In this section, we unify several existing methods for variational mutual information estimation. We first show that variational mutual information estimation can be formulated as a constrained optimization problem, where the feasible set is Δ(Q)\Delta(Q), i.e. the valid density ratios with respect to QQ.

"Feasible set" is optimization language for "the set of candidates you are allowed to choose from". Here the candidates are the valid density ratios: non-negative functions with EQ[r]=1\E_Q[r]=1.

Theorem 1 · the unifying principle

∀P,Q∈P(X)\forall P,Q\in\mathcal P(\mathcal X) such that P≪QP\ll Q we have

DKL(P∥Q)=sup⁡r∈Δ(Q) EP[log⁡r]\KL(P\|Q) = \sup_{r\in\Delta(Q)}\ \E_P[\log r]

where the supremum is achived when r=dP/dQr = dP/dQ.

💡 Read it like this

"Among all ways of reweighting QQ into a legitimate distribution, choose the one that makes the real samples from PP look most likely (on a log scale). The best you can do is exactly the KL divergence, and you get it by reweighting with the true ratio."

This is just maximum likelihood in disguise. Writing dR=r dQdR = r\,dQ, the quantity EP[log⁡r]\E_P[\log r] is the log-likelihood of PP's samples under RR, minus that under QQ. The best model of PP is PP itself.

🧮 A one-line proof (cleaner than the appendix's)

For r∈Δ(Q)r\in\Delta(Q), let RR be the distribution with dR=r dQdR = r\,dQ. Then

EP[log⁡r]=EP ⁣[log⁡dRdQ]=EP ⁣[log⁡dPdQ]−EP ⁣[log⁡dPdR]=DKL(P∥Q)−DKL(P∥R)  ≤  DKL(P∥Q),\E_P[\log r] = \E_P\!\left[\log\frac{dR}{dQ}\right] = \E_P\!\left[\log\frac{dP}{dQ}\right] - \E_P\!\left[\log\frac{dP}{dR}\right] = \KL(P\|Q) - \KL(P\|R)\;\le\;\KL(P\|Q),

with equality iff R=PR=P, i.e. r=dP/dQr = dP/dQ. ∎ (If P≪̸RP\not\ll R, then EP[log⁡r]=−∞\E_P[\log r]=-\infty and the inequality is trivial.)

⚠️ Why the constraint r∈Δ(Q)r\in\Delta(Q) is everything

Drop the constraint and the supremum is +∞+\infty: take r≡1000r \equiv 1000, and EP[log⁡r]=log⁡1000\E_P[\log r] = \log 1000 regardless of PP and QQ. An estimator is only as good as its enforcement of EQ[r]=1\E_Q[r]=1. Enforcing this needs EQ[r]\E_Q[r], the partition function, which in practice comes from a mini-batch. Hold on to this: it is the root of the variance problem in Section 4.

We defer the proof in Appendix A. The above argument works for KL divergence between general distributions, but in this paper we focus on the special case of mutual information estimation. For the remainder of the paper, we use PP to represent the short-hand notation for the joint distribution P(X,Y)P(X,Y) and use QQ to represent the short-hand notation for the product of marginals P(X)P(Y)P(X)P(Y).

From now on:P≡P(X,Y),Q≡P(X)P(Y),r⋆=dPdQ=p(x,y)p(x)p(y),I(X;Y)=DKL(P∥Q).\textbf{From now on:}\qquad P \equiv P(X,Y),\qquad Q\equiv P(X)P(Y),\qquad r^\star = \frac{dP}{dQ} = \frac{p(x,y)}{p(x)p(y)},\qquad I(X;Y)=\KL(P\|Q).

3.1 A summary of existing variational methods

From Theorem 1, we can describe a general approach to variational MI estimation:

1. Obtain a density ratio estimate – denote the solution as rr;

2. Project rr to be close to Δ(Q)\Delta(Q) – in practice we only have samples from QQ, so we denote the solution as Γ(r;Qn)\Gamma(r;Q_n), where QnQ_n is the empirical distribution of nn i.i.d. samples from QQ;

3. Estimate mutual information with EP[log⁡Γ(r;Qn)]\E_P[\log\Gamma(r;Q_n)].

① Estimate a ratio r(x,y) ≈ p(x,y)/p(x)p(y) neural net: T, f, q_φ, flows… ② Normalize ("project") Γ(r; Qₙ) so that E_Q[Γ] ≈ 1 uses a mini-batch → variance! ③ Average the log Î = E_P[ log Γ(r; Qₙ) ] over real pairs Each estimator = one choice per box.
The unified recipe. The middle box is where the trouble hides.

"Project" is used loosely: it means "fix rr so that it is (approximately) a valid density ratio", usually by dividing by an estimate of its mean under QQ. The approximation comes from having only the samples QnQ_n instead of QQ itself.

We illustrate two examples of variational mutual information estimation that can be summarized with this approach. In the case of Barber-Agakov, the proposed density ratio estimate is rBA=qϕ(x∣y)/p(x)r_{\text{BA}} = q_\phi(x|y)/p(x) (assuming that p(x)p(x) is known), which is guaranteed to be in Δ(Q)\Delta(Q) because

EQ ⁣[qϕ(x∣y)p(x)]=∫qϕ(x∣y)p(x) dP(x) dP(y)=1,ΓBA(rBA,Qn)=rBA\E_Q\!\left[\frac{q_\phi(x|y)}{p(x)}\right] = \int\frac{q_\phi(x|y)}{p(x)}\,dP(x)\,dP(y) = 1,\qquad \Gamma_{\text{BA}}(r_{\text{BA}},Q_n) = r_{\text{BA}}

for all conditional distributions qϕq_\phi.

🧮 Unpacking Eq. (7)
EQ[rBA]\E_Q[r_{\text{BA}}]
=∫ ⁣ ⁣∫qϕ(x∣y)p(x) p(x) p(y) dx dy\displaystyle =\int\!\!\int \frac{q_\phi(x|y)}{p(x)}\,p(x)\,p(y)\,dx\,dy
under QQ, xx and yy are independent: density p(x)p(y)p(x)p(y)
=∫p(y)(∫qϕ(x∣y) dx)⏟=1dy\displaystyle =\int p(y)\underbrace{\left(\int q_\phi(x|y)\,dx\right)}_{=1}dy
p(x)p(x) cancels; qϕ(⋅∣y)q_\phi(\cdot|y) is a distribution
=1=1
p(y)p(y) integrates to 1

So BA's ratio is valid by construction and needs no normalization step: ΓBA\Gamma_{\text{BA}} is the identity, there is no partition function, and there is no variance problem. That is the appeal of generative approaches. The price is that you must know p(x)p(x).

In the case of MINE / Donsker-Varadahn, the logarithm of the density ratio is estimated with Tθ(x,y)T_\theta(x,y); the corresponding density ratio might not be normalized, so one could apply the following normalization for nn samples:

EQn ⁣[eTθEQn[eTθ]]=1,ΓMINE(eTθ,Qn)=eTθEQn[eTθ]\E_{Q_n}\!\left[\frac{e^{T_\theta}}{\E_{Q_n}[e^{T_\theta}]}\right] = 1,\qquad \Gamma_{\text{MINE}}(e^{T_\theta},Q_n) = \frac{e^{T_\theta}}{\E_{Q_n}[e^{T_\theta}]}

where EQn[eTθ]\E_{Q_n}[e^{T_\theta}] (the sample average) is an unbiased estimate of the partition function EQ[eTθ]\E_Q[e^{T_\theta}]; ΓDV(eTθ,Qn)∈Δ(Q)\Gamma_{\text{DV}}(e^{T_\theta},Q_n)\in\Delta(Q) is only true when n→∞n\to\infty.

🧮 Recovering MINE from the recipe

Step ① gives r=eTθr = e^{T_\theta}. Step ② divides by the batch average. Step ③:

EP ⁣[log⁡eTθEQn[eTθ]]=EP[Tθ]−log⁡EQn[eTθ]=I^MINE. ✓\E_P\!\left[\log\frac{e^{T_\theta}}{\E_{Q_n}[e^{T_\theta}]}\right] = \E_P[T_\theta] - \log\E_{Q_n}[e^{T_\theta}] = \hat I_{\text{MINE}}.\ \checkmark

The normalized ratio averages exactly 1 on the nn samples used to normalize it. Under the true QQ it averages EQ[eT]/EQn[eT]\E_Q[e^{T}]/\E_{Q_n}[e^{T}], which is a random number that is only ≈1\approx 1 for large nn. If the batch "missed" the rare points where eTe^T is huge, the denominator is far too small, the ratio is over-inflated, and the estimate jumps. (ΓDV\Gamma_{\text{DV}} in the text is the same as ΓMINE\Gamma_{\text{MINE}}; the paper switches names.)

Similarly, we show ICPCI_{\text{CPC}} is a lower bound to MI in Corollary 2, Appendix A, providing an alternative proof to the one in Poole et al. (2019).

CPC also fits the recipe. Its "ratio" is r=f(xi,yi)/1n∑jf(xi,yj)r = f(x_i,y_i)\big/\tfrac1n\sum_j f(x_i,y_j): it normalizes by an average over the batch of yy's. The appendix shows this ratio is exactly valid (in a cleverly enlarged space), so Theorem 1 immediately makes CPC a lower bound. See Corollary 2 in the paper's Appendix A.

These examples demonstrate that different mutual information estimators can be obtained in a procedural manner by implementing the above steps, and one could involve different objectives at each step. For example, one could estimate density ratio via logistic regression (Hjelm et al., 2018; Poole et al., 2019; Mukherjee et al., 2019) while using INWJI_{\text{NWJ}} or IMINEI_{\text{MINE}} to estimate MI. While logistic regression does not optimize for a lower bound for KL divergence, it provides density ratio estimates between PP and QQ which could be used for subsequent steps.

💡 Mix and match: train with one objective, evaluate with another

The recipe decouples training from evaluation. For example, train a binary classifier D(x,y)=σ(T(x,y))D(x,y)=\sigma(T(x,y)) to tell real pairs (label 1) from shuffled pairs (label 0) with the ordinary cross-entropy loss. With balanced classes, the optimal classifier satisfies

σ(T⋆)=p(x,y)p(x,y)+p(x)p(y)⟹T⋆=log⁡p(x,y)p(x)p(y)=log⁡r⋆.\sigma(T^\star) = \frac{p(x,y)}{p(x,y)+p(x)p(y)}\quad\Longrightarrow\quad T^\star = \log\frac{p(x,y)}{p(x)p(y)} = \log r^\star .

So the classifier's logit is a log-density-ratio estimate (step ①). Plug it into the MINE or NWJ formula for steps ② and ③. SMILE does exactly this (Section 5). Logistic regression is numerically far more stable to train than DV or NWJ, because its loss is bounded and does not involve eTe^{T}.

Table 1, rebuilt and annotated

Summarization of variational estimators of mutual information. The ∈Δ(Q)\in\Delta(Q) column denotes whether the estimator is a valid density ratio wrt. QQ. (✓) means any parameterization is valid; (n→∞n\to\infty) means any parameterization is valid as the batch size grows to infinity; (tr→∞tr\to\infty) means only the optimal parametrization is valid (infinite training cost).

Table 1: the "Γ" column is what each estimator plugs into EP[log⁡Γ]\E_P[\log\Gamma]
CategoryEstimatorParamsΓ(r;Qn)\Gamma(r;Q_n)∈Δ(Q)\in\Delta(Q)?Plain-English reading
GenerativeI^BA\hat I_{\text{BA}}qϕq_\phiqϕ(x∣y)/p(x)q_\phi(x|y)/p(x)✓Always valid (Eq. 7), but needs known p(x)p(x)
GenerativeI^GM\hat I_{\text{GM}} (Eq. 9)pθ,pϕ,pψp_\theta,p_\phi,p_\psipθ(x,y)pϕ(x)pψ(y)\dfrac{p_\theta(x,y)}{p_\phi(x)p_\psi(y)}tr→∞tr\to\inftyThree separate density models. Valid only if all three are perfect.
DiscriminativeI^MINE\hat I_{\text{MINE}}TθT_\thetaeTθ(x,y)EQn[eTθ(x,y)]\dfrac{e^{T_\theta(x,y)}}{\E_{Q_n}[e^{T_\theta(x,y)}]}n→∞n\to\inftyNormalized by a noisy batch average
DiscriminativeI^CPC\hat I_{\text{CPC}}fθf_\thetafθ(x,y)EPn(Y)[fθ(x,y)]\dfrac{f_\theta(x,y)}{\E_{P_n(Y)}[f_\theta(x,y)]}✓Valid in an enlarged space (Cor. 2), but capped at log⁡n\log n
DiscriminativeI^SMILE\hat I_{\text{SMILE}} (Eq. 17)Tθ,τT_\theta,\taueTθ(x,y)EQn[clip⁡(eTθ(x,y),e−τ,eτ)]\dfrac{e^{T_\theta(x,y)}}{\E_{Q_n}[\clip(e^{T_\theta(x,y)},e^{-\tau},e^{\tau})]}n,τ→∞n,\tau\to\inftyMINE with a clipped (tamed) normalizer

3.2 Generative and discriminative approaches to MI estimation

The above discussed variational mutual information methods can be summarized into two broad categories based on how the density ratio is obtained.

• The discriminative approach estimates the density ratio dP/dQdP/dQ directly; examples include the MINE, NWJ and CPC estimators.

• The generative approach estimates the densities of PP and QQ separately; examples include the BA estimator where a conditional generative model is learned. In addition, we describe a generative approach that explicitly learns generative models (GM) for P(X,Y)P(X,Y), P(X)P(X) and P(Y)P(Y):

IGM(pθ,pϕ,pψ):=EP[log⁡pθ(x,y)−log⁡pϕ(x)−log⁡pψ(y)]I_{\text{GM}}(p_\theta,p_\phi,p_\psi) := \E_P\big[\log p_\theta(x,y) - \log p_\phi(x) - \log p_\psi(y)\big]

where pθ,pϕ,pψp_\theta,p_\phi,p_\psi are maximum likelihood estimates of P(X,Y)P(X,Y), P(X)P(X) and P(Y)P(Y) respectively. We can learn the three distributions with generative models, such as VAE (Kingma & Welling, 2013) or Normalizing flows (Dinh et al., 2016), from samples.

The idea of Eq. (9): if you had all three densities, MI would just be EP[log⁡p(x,y)−log⁡p(x)−log⁡p(y)]\E_P[\log p(x,y) - \log p(x) - \log p(y)]. So fit three density models, one for the joint (trained on concatenated [x,y][x,y]), one for xx, one for yy, and plug them in. Normalizing flows give exact log-likelihoods. VAEs give only a lower bound on log⁡p\log p (the ELBO), so with VAEs IGMI_{\text{GM}} is a difference of approximations and not a bound in either direction.

Generative p_θ(x,y) p_φ(x) p_ψ(y) r = p_θ / (p_φ · p_ψ) + needs no Q samples, O(n) cost − needs tractable likelihoods − errors of 3 models don't cancel Discriminative critic T_θ(x,y) ≈ log r real pairs vs shuffled pairs + any architecture, no likelihood − needs Q samples, up to O(n²) − needs normalization (partition fn)
Two ways to get the density ratio.

We summarize various generative and discriminative variational estimators in Table 1.

Differences between two approaches While both generative and discriminative approaches can be summarized with the procedure in Section 3.1, they imply different choices in modeling, estimation and optimization.

• On the modeling side, the generative approaches might require more stringent assumptions on the architectures (e.g. likelihood or evidence lower bound is tractable), whereas the discriminative approaches do not have such restrictions.

Flows must be invertible with a tractable Jacobian determinant, and VAEs need an encoder/decoder pair. A critic can be any network that outputs a number, so it is much more flexible.

• On the estimation side, generative approaches do not need to consider samples from the product of marginals P(X)P(Y)P(X)P(Y) (since it can model P(X,Y),P(X),P(Y)P(X,Y), P(X), P(Y) separately), yet the discriminative approaches require samples from P(X)P(Y)P(X)P(Y); if we consider a mini-batch of size nn, the number of evaluations for generative approaches is Ω(n)\Omega(n) whereas that for discriminative approaches it could be Ω(n2)\Omega(n^2).

Ω(⋅)\Omega(\cdot) means "at least on the order of". A generative model evaluates 3 log-densities per real pair, so about 3n3n evaluations. A discriminative method that uses all pairs (xi,yj)(x_i, y_j) as negatives evaluates the critic n2n^2 times. (The separable critic T(x,y)=g(x)⊤h(y)T(x,y) = g(x)^\top h(y) from Appendix B reduces the network passes to 2n2n plus one n×nn\times n matrix product.)

• On the optimization side, discriminative approaches may need additional projection steps to be close to Δ(Q)\Delta(Q) (such as IMINEI_{\text{MINE}}), while generative approaches might not need to perform this step (such as IBAI_{\text{BA}}).

This is the key asymmetry. Generative ratios are normalized by construction, because each model is a proper density. Discriminative ratios need step ②, and step ② is where exponential variance comes from (next section).

What comes next (not covered in this part)

This guide stops at the end of Section 3. Here is a preview of how the rest of the paper builds on what you have just read:

  • §4.1 Theorem 2: with the optimal ratio r⋆r^\star, the variance of the batch normalizer satisfies Var⁡[EQn[r⋆]]≥(eI(X;Y)−1)/n\Var[\E_{Q_n}[r^\star]] \ge (e^{I(X;Y)}-1)/n. This is the "rare huge values" property from 0.4 made quantitative, and it means MINE/NWJ need batches of size about eMIe^{\text{MI}}.
  • §4.2 Self-consistency tests: independence (I^=0\hat I=0), data processing, and additivity (I^([X1,X2];[Y1,Y2])≈2I^(X;Y)\hat I([X_1,X_2];[Y_1,Y_2]) \approx 2\hat I(X;Y)).
  • §5 SMILE: ISMILE=EP[Tθ]−log⁡EQ[clip⁡(eTθ,e−τ,eτ)]I_{\text{SMILE}} = \E_P[T_\theta] - \log\E_Q[\clip(e^{T_\theta}, e^{-\tau}, e^{\tau})], which tames step ② of the recipe.
  • §6–7: experiments on Gaussians and images, and the conclusion that no estimator passes all the tests.
🌌 The Learner